The complete-tree-like matching mc-DFA and their implementation
Yi‐Shiung Yeh, Shyr-Shen Yu, Ta-Shan Tsui · Journal of Interdisciplinary Mathematics · 2003
In this paper we propose a new structure of matching multi-class automata(shortly mcDFA) called the complete-tree-like-matching mc-DFA (shortly ctlm-mcDFA) which is based on the idea of properly arranging the pointer of the leaves of a complete tree to establish an automaton which can accept all words of the length equal to or less than the height of the complete tree. Mc-DFA can perform multi-class keywords matching concurrently within one pass while the matching deterministic finite automata (shortly DFA) cannot do. For classes of short keywords the complete-tree-like-matching mc-DFA can be constructed quickly and preserve all the benefits owned by mc-DFA model. Furthermore the ctlm-mcDFA possesses the good property that the keywords of each class can be inserted and deleted easily.