For Review Only Fast Pattern Matching via k-bit Filtering Based Text Decomposition
Jeffrey Scott Vitter, Bojian Xu · 2010
This study explores an alternative way of storing text les to answer exact match queries faster. We decompose the original le into two parts as lter and payload. The lter part contains the most informativek bits of each byte, and the remaining bits of the bytes are concatenated in order of appearance to generate the payload. We refer to this structure as k-bit ltered format. When an input pattern is to be searched on the k-bit ltered structure, the same decomposition is performed on the pattern. The k bits from each byte of the pattern form the pattern lter bit sequence, and the rest is the payload. The pattern lter is rst scanned on the lter part of the le. At each match position detected in the lter part, the pattern payload is veried against the corresponding location in the payload part of the text. Thus, instead of searching an m-byte pattern on an n-byte text, rst k m bits are scanned on k n bits, followed by a verication of (8 k) m bits on the respective locations of the matching positions. Experiments conducted on natural language texts, plain ASCII DNA sequences, and random byte sequences showed that the search performance with the proposed scheme is on average two times faster than the tested best exact pattern matching algorithms. The highest gain is obtained on plain ASCII DNA sequences. We also developed an eectiv e bitwise pattern matching algorithm of possible independent interest within this study.