Využití Redukce NKA pro Vyhledávání Vzorů v FPGA

On Usage of NFA Reduction for Regular Expressions matching in FPGA

article in a collection out of WoS and Scopus

Czech

Prudký rozvoj počítačových sítí s sebou přináší neustále se zvyšující počet signatur systémů pro detekci nebezpečného provozu. To sebou přináší nutnost redukovat velikost nedeterministických konečných automatů používaných pro akceleraci vyhledávání řetězců popsaných regulárními výrazy. Článek představuje 5 redukčních algoritmů a řešení problematiky korespondence koncových stavů k regulárním výrazů. Představené algoritmy redukce jsou vyhodnoceny jak pro nemodifikované (redukce průměrně 35,1% stavů a 42,7% přechodů), tak pro modifikované algoritmy (redukce průměrně 6,8% stavů  a 4,3% přechodů).

This article describes 5 NFA reduction algorithms and solution of correspondence between final states and regular expressions. Both variants of reduction algorithms are evaluated. Unmodified variants have average reduction 35.1% of states and 42.7% of transitions. Modified variants have average reduction 6.8% of states and 4.3% of transitions and those algorithms preserve correspondence between final states and regular expressions.

NKA, FPGA, Redukce, Vyhledávání vzorů

NFA, FPGA, Reduction, Regular Expressions Matching

KOŠAŘ, V.

2012

10. 9. 2012

Fakulta informačních technologií ČVUT

Milovy

978-80-01-05106-1

Počítačové architektury a diagnostika 2012

97

102

6