Collage system: A unifying framework for compressed pattern matching.

DOI10.1016/S0304-3975(02)00426-7zbMath1038.68045OpenAlexW2111487449MaRDI QIDQ1874240

Masayuki Takeda, Tetsuya Matsumoto, Yusuke Shibata, Takuya Kida, Setsuo Arikawa, Ayumi Shinohara

Publication date: 22 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00426-7

zbMATH Keywords

systemData compressionString matchingCompressed pattern matchingCollage

Mathematics Subject Classification ID

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

Related Items

On stricter reachable repetitiveness measures ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Linear-time text compression by longest-first substitution ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Straight-line programs: a practical test (extended abstract) ⋮ Substring complexities on run-length compressed strings ⋮ Unified compression-based acceleration of edit-distance computation ⋮ Block trees ⋮ Universal compressed text indexing ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Two fast constructions of compact representations of binary words with given set of periods ⋮ A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS ⋮ Functional programs as compressed data ⋮ A Run-Time Efficient Implementation of Compressed Pattern Matching Automata ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA ⋮ A fully linear-time approximation algorithm for grammar-based compression ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Compressed automata for dictionary matching

Uses Software

• Agrep

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Matching patterns in strings subject to multi-linear transformations
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Pattern matching in compressed texts
• Data compression via textual substitution
• Efficient pattern matching with scaling
• Fast Pattern Matching in Strings
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Optimal Two-Dimensional Compressed Matching
• Universal lossless compression via multilevel pattern matching
• Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
• Grammar-based codes: a new class of universal lossless source codes
• Efficient algorithms for Lempel-Ziv encoding