lempelZiv
plain-language theorem explainer
Lempel-Ziv compression is defined as the dictionary-based adaptive scheme that reaches the entropy rate in the limit. Researchers deriving data limits from J-cost in Recognition Science cite this when connecting Shannon coding to cost minimization. The entry is supplied as a direct string constant with surrounding comments on entropy rate.
Claim. Lempel-Ziv compression is the dictionary-based adaptive scheme that achieves the entropy rate $h = lim_{n→∞} (1/n) H(X_1, X_2, ..., X_n)$ for stationary sources.
background
The module INFO-003 derives compression limits from J-cost. Shannon's source coding theorem states that average code length is at least the entropy $H(X) = -Σ p(x) log₂ p(x)$, so no scheme beats entropy. In Recognition Science, information carries J-cost and compression lowers it by increasing organization, making the entropy limit the minimum J-cost for faithful representation. Upstream, CostAlgebra.H reparametrizes the shifted cost as $H(x) = J(x) + 1$, turning the Recognition Composition Law into the d'Alembert equation $H(xy) + H(x/y) = 2 H(x) H(y)$. InitialCondition.entropy defines entropy of a configuration as its total defect, with zero defect giving the minimum-entropy state.
proof idea
The definition is a direct string literal assignment. It is followed by a comment block restating the entropy rate for stationary sources and noting the drop from single-symbol entropy to the rate for English text.
why it matters
This definition anchors the module's claim that compression equals J-cost minimization and supplies the concrete scheme (LZ77/LZ78/LZW) that attains the Shannon limit. It supports downstream siblings such as compression_is_jcost_minimization and source_coding_theorem by naming the algorithm that realizes the entropy bound in the Recognition framework. The entry touches the open question of how the phi-ladder and eight-tick octave constrain practical compression rates beyond the asymptotic result.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.