摘要 |
A compressed pattern matching based on LZW compressed sequences with a simple bitmap-based realization of the Amir-Benson-Farach algorithm is provided. A suffix trie for a searched pattern is determined and a LZW trie is constructed for a compressed data. For each data chunk in the compressed data a variety of information is determined and a node is added to the LZW trie. The queries used to determine the information are implemented through bitmaps, and allowing identification of all occurrence of the searched pattern.
|