Compression.ru last hot news:
Pattern matching is one of the fundamental operations in data processing. The compressed pattern matching attracts attention recently. The idea is to perform a faster search on compressed data in comparison with a decompression followed by a usual search and, that's more important, faster, than with an ordinary search in the original uncompressed data.
Links
2 links were found
|
Huffman area, LZW area, LZSS area, CompressedPattern area
|
This paper describes a few searching algorithms to be used on compressed files. An AC type algorithm for searching in Huffman encoded files, a KMP type algorithm for LZ derivatives and a BM type algorithm for searching in files compressed by Byte-Pair-Encoding (BPE). BPE gave results upto 3 times faster than those achieved by agrep.
Created: 12/06/2005
by Sachin Garg
More...
|
www.i.kyushu-u.ac.jp/~takeda/papers/IPSJ40.pdf
|
Papers content, CompressedPattern area
|
Byte pair encoding (BPE) is a simple universal text compression scheme with fast decompression which requires small work space which allows decompression of an arbitrary part of the original text. Compression is rather slow with ratios less than Lempel-Ziv type compression. This paper, brings out a potential advantage of BPE compression showing that it is very suitable from a practical view point of compressed pattern matching, where the goal is to find a pattern directly in
compressed text without decompressing it explicitly.
Created: 12/06/2005
by Sachin Garg
More...
|
www.i.kyushu-u.ac.jp/~ayumi/papers/CIAC2000.pdf
