ハッシュ型オートマトンによる文字列検索の並列化手法

This paper proposes a hash automaton to efficiently implement string matching in hardware. The proposed method applies a hash function to both a text and patterns to scale down the logic of the string matching and improve the throughput of it. The automaton which is constructed from all patterns shrinks since a hash function reduces searching space. In addition, a hash function generates multiple texts, which have no dependency with each other, from a single text. It is therefore possible to process the texts generated by the hash function in parallel or in a pipelined manner. The method is implemented on a reconfigurable processor DAP/DNA. The method achieves a throughput of 664 Mbytes per second with one DAP/DNA chip.