A Dedicated Computer Architecture Framework for Large Scale Multi-string-matching Complete Automaton

Multiple string matching to handle massive amount of data could be implemented via a complete automaton. But it is difficult to implement because of computational complexity and processing speed, especially in real time. A dedicated computer architecture framework, which makes it possible, is proposed in this paper. The features of this architecture are as following: tree node is expressed by two elements instead of general three elements. The core of this architecture is hierarchical memory, including register, fast memory and mass memory, rather than computational unit. The processing unit is comparator rather than calculator. Finally the effects of parameter change to the hardware complexity are discussed also. The space complexity of this architecture is O(|P|) rather than O(|P|*|N|), and the hardware complexity is O(|N|/|P|) rather than O(|N|*|P|), where |P| is the number of state and |N| is the size of state transition table.