Apparatus and methods for searching a pattern in a compressed data
AssigneeReti Corporation
InventorsTsern-Huei Lee, Nai-Lun Huang
Life of this patent
Estimating the term…
Abstract
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.
Claims13
A method for searching a pattern in a compressed data, comprising the steps of:
- receiving a compressed data, the compressed data having a plurality of data chunks;
- obtaining a first data chunk from the compressed data;
- retrieving a first bitmap from a first table based on the first data chunk;
- obtaining a second data chunk from the compressed data;
- retrieving a second bitmap from a second table based on the second data chunk;
- deriving a first result by a bit-wise ANDing the first bitmap with the second bitmap;
- and
- indicating the pattern being present in the compressed data if there is at least one bit set in the first result.
An apparatus for searching a pattern in a compressed data comprising:
- a data receiving unit for receiving compressed data from a data source;
- and
- a content search unit capable of analyzing the received compressed data, the content search unit further being capable of performing the steps of:
- receiving a compressed data, the compressed data having a plurality of data chunks;
- obtaining a first data chunk from the compressed data;
- retrieving a first bitmap from a first table based on the first data chunk;
- obtaining a second data chunk from the compressed data;
- retrieving a second bitmap from a second table based on the second data chunk;
- deriving a first result by a bit-wise ANDing the first bitmap with the second bitmap;
- and
- indicating the pattern being present in the compressed data if there is at least one bit set in the first result.
Dependencies are inferred from the claim text.