Compressed parameterized pattern matching

DOI10.1016/J.TCS.2015.09.015MaRDI QIDQ897868zbMATH OpenOpenAlexFDO

Authors Richard Beal, Donald Adjeroh

Publication date 8 December 2015

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.09.015

zbMATH Keywords

Huffman codesp-borderp-matchp-stringparameterized borderparameterized matchingparameterized stringlossless compressioncompressed pattern matchingcatenateLZSSpACparameterized arithmetic codingTunstall codes

Mathematics Subject Classification ID

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

Recommendations

• Pattern matching in compressed texts
• Let sleeping files lie: Pattern matching in Z-compressed files.
• scientific article; zbMATH DE number 1003304
• String matching in Lempel-Ziv compressed strings
• Parameterized searching with mismatches for run-length encoded strings

Cites work

• scientific article; zbMATH DE number 2185629 (Why is no real title available?)
• scientific article; zbMATH DE number 1306895 (Why is no real title available?)
• scientific article; zbMATH DE number 910912 (Why is no real title available?)
• A method for compressing test data based on Burrows-Wheeler transformation
• A theory of parameterized pattern matching
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Alphabet dependence in parameterized matching
• Approximate string matching on Ziv--Lempel compressed text
• Compressed matching in dictionaries
• Compression of individual sequences via variable-rate coding
• Counting Parameterized Border Arrays for a Binary Alphabet
• Data compression via textual substitution
• Efficient Algorithms for the Inverse Sort Transform
• Efficient pattern matching for RNA secondary structures
• Fast parameterized matching with \(q\)-grams
• Faster suffix tree construction with missing suffix links
• Generalization of a suffix tree for RNA structural pattern matching
• Lightweight parameterized suffix array construction
• Multiple matching of parameterized patterns
• On-line construction of parameterized suffix trees for large alphabets
• Optimal pattern matching in LZW compressed strings
• Parameterized longest previous factor
• Parameterized matching with mismatches
• Parameterized pattern matching: Algorithms and applications
• Parameterized searching with mismatches for run-length encoded strings
• Pattern matching in compressed texts and images
• The structural border array
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Two-dimensional parameterized matching
• Universal data compression based on the Burrows-Wheeler transformation: theory and practice
• Using Lossless Data Compression in Data Storage Systems: Not for Saving Space
• Variations of the parameterized longest previous factor
• p-suffix sorting as arithmetic coding

Cited in

(4)

• Parameterized searching with mismatches for run-length encoded strings
• Structural Pattern Matching - Succinctly.
• Improving Time and Space Complexity for Compressed Pattern Matching
• A brief history of parameterized matching problems

This page was built for publication: Compressed parameterized pattern matching

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