Data compression via textual substitution
From MaRDI portal
Publication:3951542
DOI10.1145/322344.322346zbMath0489.68041OpenAlexW2022126655WikidataQ57479682 ScholiaQ57479682MaRDI QIDQ3951542
James A. Storer, Thomas G. Szymanski
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322344.322346
pattern matchingdictionaryNP- completenesscomplexity of encoding and decodingmacro expansionlower bounds on the amount of compressionmacro schemes
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Data structures (68P05)
Related Items (64)
P-complete problems in data compression ⋮ Collage system: A unifying framework for compressed pattern matching. ⋮ Comparison of LZ77-type parsings ⋮ List partitions ⋮ Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ Factorizing strings into repetitions ⋮ Unnamed Item ⋮ FINDING CHARACTERISTIC SUBSTRINGS FROM COMPRESSED TEXTS ⋮ On the approximation ratio of LZ-end to LZ77 ⋮ A separation of \(\gamma\) and \(b\) via Thue-Morse words ⋮ On stricter reachable repetitiveness measures ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ Concurrent vs. exclusive reading in parallel decoding of LZ-compressed files ⋮ Weighted forward looking adaptive coding ⋮ Grammar-compressed indexes with logarithmic search time ⋮ On updating suffix tree labels ⋮ LZRR: LZ77 parsing with right reference ⋮ On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case ⋮ String Indexing with Compressed Patterns ⋮ Recognition of overlap graphs ⋮ A new graph model and algorithms for consistent superstring problems ⋮ Substring complexities on run-length compressed strings ⋮ Compressed parameterized pattern matching ⋮ Truncated suffix trees and their application to data compression. ⋮ Sensitivity of string compressors and repetitiveness measures ⋮ Random access in persistent strings and segment selection ⋮ Greedy versus optimal analysis of bounded size dictionary compression and on-the-fly distributed computing ⋮ Bidirectional adaptive compression ⋮ Unnamed Item ⋮ Lempel-Ziv-like parsing in small space ⋮ Note on the greedy parsing optimality for dictionary-based text compression ⋮ Unnamed Item ⋮ Dictionary-symbolwise flexible parsing ⋮ Block trees ⋮ Using static suffix array in dynamic application: case of text compression by longest first substitution ⋮ Universal compressed text indexing ⋮ Dictionary-Symbolwise Flexible Parsing ⋮ Lempel-Ziv data compression on parallel and distributed systems ⋮ Practical fixed length Lempel-Ziv coding ⋮ A FULLY COMPRESSED PATTERN MATCHING ALGORITHM FOR SIMPLE COLLAGE SYSTEMS ⋮ SEMI-LOSSLESS TEXT COMPRESSION ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ Colored operads, series on colored operads, and combinatorial generating systems ⋮ Binary image compression via monochromatic pattern substitution: sequential and parallel implementations ⋮ Computing the longest previous factor ⋮ Parallel Lempel Ziv coding ⋮ Forty Years of Text Indexing ⋮ Data compression with long repeated strings ⋮ Optimal encoding of non-stationary sources ⋮ \(LZ\)-based image compression ⋮ Redundancy estimates for the Lempel–Ziv algorithm of data compression ⋮ Finding the longest common nonsuperstring in linear time ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Forward looking Huffman coding ⋮ Bidirectional Text Compression in External Memory ⋮ Direct merging of delta encoded files ⋮ Mining Compressing Sequential Patterns ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Approximation algorithms for the shortest common superstring problem ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem ⋮ Compressed automata for dictionary matching ⋮ Text compression methods
This page was built for publication: Data compression via textual substitution
