Original title:
Měření spolehlivosti vyhledávání vzorů
Translated title:
Reliability Measurement of the Pattern Matching
Authors:
Dvořák, Milan ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor) Document type: Master’s theses
Year:
2012
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce se zabývá metodami vyhledávání vzorů pomocí konečných automatů a popisuje některé optimalizace těchto algoritmů. Dále rozebírá návrh a implementaci metodiky pro měření spolehlivosti vyhledávání na základě srovnávání s výsledky PCRE knihovny. Experimentální měření byla provedena pro konečný automat s perfektním hašováním a chybující přechodovou tabulkou. Nakonec je prezentováno výsledné hodnocení spolehlivosti algoritmu spolu s návrhem řešení zjištěných problémů.
This thesis deals with the pattern matching methods based on finite automata and describes their optimizations. It presents a methodology for the measurement of reliability of pattern matching methods, by comparing their results to the results of the PCRE library. Experiments were conducted for a finite automaton with perfect hashing and faulty transition table. Finally, the resulting reliability evaluation of the algorithm is shown and possible solutions of the identified problems are proposed.
Keywords:
finite automaton; pattern matching; PCRE; perfect hashing; regular expression; reliability; Snort; konečný automat; PCRE; perfektní hašování; regulární výraz; Snort; spolehlivost; vyhledávání vzorů
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/53685