A unifying framework for compressed pattern matching
- 20 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We introduce a general framework which is suitable to capture an essence of compressed pattern matching according to various dictionary based compressions, and propose a compressed pattern matching algorithm for the frame-work. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW), byte-pair encoding, and the static dictionary based method. Technically, our pattern matching algorithm extends that for LZW compressed text presented by Amir, Benson and Farach.Keywords
This publication has 13 references indexed in Scilit:
- Direct pattern matching on compressed textPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Multiple pattern matching in LZW compressed textPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Pattern Matching in Text Compressed by Using AntidictionariesPublished by Springer Nature ,1999
- A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed TextPublished by Springer Nature ,1999
- Shift-And Approach to Pattern Matching in LZW Compressed TextPublished by Springer Nature ,1999
- Fast searching on compressed text allowing errorsPublished by Association for Computing Machinery (ACM) ,1998
- An improved pattern matching algorithm for strings in terms of straight-line programsPublished by Springer Nature ,1997
- Pattern matching in compressed textsPublished by Springer Nature ,1995
- A Technique for High-Performance Data CompressionComputer, 1984
- Data compression via textual substitutionJournal of the ACM, 1982