Collage system: A unifying framework for compressed pattern matching.

DOI10.1016/S0304-3975(02)00426-7MaRDI QIDQ1874240zbMATH OpenOpenAlexFDO

Authors T. Kida, Tetsuya Matsumoto, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, S. Arikawa

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

CollageCompressed pattern matchingData compressionString matchingsystem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1786459
• A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS
• scientific article; zbMATH DE number 1615280
• Compressed automata for dictionary matching
• Compressed automata for dictionary matching

Cites work

• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• Efficient algorithms for Lempel-Ziv encoding
• Efficient pattern matching with scaling
• Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. I. Without context models
• Fast Pattern Matching in Strings
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Grammar-based codes: a new class of universal lossless source codes
• scientific article; zbMATH DE number 1615280 (Why is no real title available?)
• scientific article; zbMATH DE number 1615281 (Why is no real title available?)
• scientific article; zbMATH DE number 1629861 (Why is no real title available?)
• scientific article; zbMATH DE number 2185628 (Why is no real title available?)
• scientific article; zbMATH DE number 2185629 (Why is no real title available?)
• scientific article; zbMATH DE number 2185630 (Why is no real title available?)
• scientific article; zbMATH DE number 1263249 (Why is no real title available?)
• scientific article; zbMATH DE number 1044854 (Why is no real title available?)
• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• scientific article; zbMATH DE number 742992 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Matching patterns in strings subject to multi-linear transformations
• Optimal Two-Dimensional Compressed Matching
• Pattern matching in compressed texts
• Universal lossless compression via multilevel pattern matching

Cited in

(23)

• Linear-time text compression by longest-first substitution
• Universal compressed text indexing
• Unified compression-based acceleration of edit-distance computation
• On stricter reachable repetitiveness measures
• Block trees
• Compressed automata for dictionary matching
• A fully linear-time approximation algorithm for grammar-based compression
• Grammar-compressed indexes with logarithmic search time
• scientific article; zbMATH DE number 1615280 (Why is no real title available?)
• Towards approximate matching in compressed strings: local subsequence recognition
• Self-indexed Text Compression Using Straight-Line Programs
• A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA
• A Run-Time Efficient Implementation of Compressed Pattern Matching Automata
• Straight-line programs: a practical test (extended abstract)
• scientific article; zbMATH DE number 1786459 (Why is no real title available?)
• Two fast constructions of compact representations of binary words with given set of periods
• Optimal rank and select queries on dictionary-compressed text
• Random access to grammar-compressed strings and trees
• Functional programs as compressed data
• A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS
• Substring complexities on run-length compressed strings
• Repetitiveness measures based on string morphisms
• Pattern matching on run-length grammar-compressed strings in linear time

Describes a project that uses

Uses Software

• Agrep

This page was built for publication: Collage system: A unifying framework for compressed pattern matching.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874240)