2010 · 29 citations · 8 references
ComputingComputer ScienceAlgorithmsData StructuresNatural Language ProcessingCoding TheoryData CompressionLossless Data CompressionLossy Data CompressionString AlgorithmsCompressed Data StructuresCompressionCompression AlgorithmsCompression TechniquesLow-complexity Compression AlgorithmsString Compression
We present a technique that compresses a string $w$ by enumerating all the substrings of $w$. The substrings are enumerated from the shortest to the longest and in lexicographic order. Compression is obtained from the fact that the set of the substrings of a particular length gives a lot of information about the substrings that are one bit longer. A linear-time, linear-space algorithm is presented. Experimental results show that the compression efficiency comes close to that of the best PPM variants. Other compression techniques are compared to ours.
8
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
Arithmetic coding for data compression
Ian H. Witten, Radford M. Neal, John G. Cleary · Communications of the ACM · 1987 · 2.9K citations · Full text
A Block-sorting Lossless Data Compression Algorithm
Michael T. Burrows, D. J. Wheeler · 1994 · 2.4K citations