Publication Details

Deterministic Finite Automaton with Perfect Hashing for Fast Pattern Matching

KAŠTIL, J.; KOŘENEK, J. Deterministic Finite Automaton with Perfect Hashing for Fast Pattern Matching. Proceedings of Junior Scientist Conference 2008. Vienna: Technical University Wien, 2008. p. 103-104. ISBN: 978-3-200-01612-5.
Czech title
Deterministický konečný automat s perfektním hashováním pro rychlé vyhledávání vzorů
Type
conference paper
Language
English
Authors
Kaštil Jan, Ing., Ph.D.
Kořenek Jan, doc. Ing., Ph.D. (DCSY)
Keywords

Deterministic Finite Automata, FPGA, perfect hashing

Abstract

As todays networks grow very fast, it is necessary to protect networks by security systems such as firewalls and Intrusion Detection Systems. Pattern matching is time critical operation on multigigabit networks for current IDS. Patterns are often described by regular expressions. The paper deals with fast regular expression matching using the Deterministic Finite Automata (DFA) with perfect hash function. We introduce decomposition of the statement to the transformation of the alphabet and fast DFA. We introduced perfect hash to reduce space/speed trade off for DFA transition table.

Published
2008
Pages
103–104
Proceedings
Proceedings of Junior Scientist Conference 2008
ISBN
978-3-200-01612-5
Publisher
Technical University Wien
Place
Vienna
BibTeX 
@inproceedings{BUT30724,
  author="Jan {Kaštil} and Jan {Kořenek}",
  title="Deterministic Finite Automaton with Perfect Hashing for Fast Pattern Matching",
  booktitle="Proceedings of Junior Scientist Conference 2008",
  year="2008",
  pages="103--104",
  publisher="Technical University Wien",
  address="Vienna",
  isbn="978-3-200-01612-5"
}
Back to top