Practical and flexible pattern matching over Ziv-Lempel compressed text.

DOI10.1016/j.jda.2003.12.002zbMath1108.68474OpenAlexW2052224223MaRDI QIDQ878012

Gonzalo Navarro, Mathieu Raffinot

Publication date: 25 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2003.12.002

zbMATH Keywords

Bit-parallelismCompressed pattern matchingLZ77LZ78LZWZiv-Lempel compression

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

The complexity of compressed membership problems for finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Data compression with factor automata
• Faster approximate string matching
• Speeding up two string-matching algorithms
• Approximate string matching on Ziv--Lempel compressed text
• A fast string searching algorithm
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• A locally adaptive data compression scheme
• Universal codeword sets and representations of the integers
• Fast Pattern Matching in Strings
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• A Method for the Construction of Minimum-Redundancy Codes