Open AccessMemory‐efficient parallel string matching scheme using distributed pattern grouping without matching vectors
Author(s) -
Kim HyunJin
Publication year - 2016
Publication title -
electronics letters
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.375
H-Index - 146
ISSN - 1350-911X
DOI - 10.1049/el.2015.4548
Subject(s) - string searching algorithm , deterministic finite automaton , pattern matching , computer science , approximate string matching , matching (statistics) , string (physics) , regular expression , finite state machine , string metric , algorithm , bit array , commentz walter algorithm , theoretical computer science , mathematics , artificial intelligence , statistics , mathematical physics , programming language , ecology , type (biology) , biology
A memory‐efficient bit‐split deterministic finite automata (DFAs)‐based string matching scheme with multiple string matchers is proposed. When multiple patterns can be matched in bit‐split DFAs, the matching vector is required for a state to indicate which patterns are matched. In the proposed scheme, patterns are iteratively grouped into multiple unique sets of patterns using the graph colouring of a unique graph. Since a pattern cannot be a suffix of other patterns in a bit‐split DFA, only one pattern can be matched in a string matcher. Therefore, in order to reduce the hardware overhead, the matching vector can be removed in each string matcher. Compared with other previous works, the memory requirements are reduced by 45.3–11.2% on average.