IEEE Transactions on Information Theory · 1997 · 88 citations · 15 references
ComputingComputer ScienceAlgorithmsComputational LinguisticsNatural Language ProcessingCoding TheoryData CompressionLossless Data CompressionLossy Data CompressionParsingUniversal CodingCompression BoundsEntropy In Data CompressionLempel-ziv CodingLempel-ziv CompressionLossless Source CodingLossy Source CodingUniversal Coding For Markov SourcesVariable-length Coding
The Lempel-Ziv codes are universal variable-to-fixed length codes that have become virtually standard in practical lossless data compression. For any given source output string from a Markov or unifilar source, we upper-bound the difference between the number of binary digits needed to encode the string and the self-information of the string. We use this result to demonstrate that for unifilar or Markov sources, the redundancy of encoding the first n letters of the source output with the Lempel-Ziv incremental parsing rule (LZ'78), the Welch modification (LZW), or a new variant is O((ln n)/sup -1/), and we upper-bound the exact form of convergence. We conclude by considering the relationship between the code length and the empirical entropy associated with a string.
15
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948 · 80.7K citations
Information Theory and Reliable Communication
David A. Bell · Electronics and Power · 1969 · 4K citations