12.6 Lempel–Ziv 符号の最適性

前節の数え上げには，情報源の確率がどこにも現れなかった．見ていたのはフレーズが相異なることだけで，どのフレーズが起こりやすいかは問わなかったからである．そのぶん結論も粗く，前節が行き着いた系 12.5.12 が与えたのは $1$ 文字あたり $3 l o g 2 (| X | + 1) + ⌊ l o g 2 | X | ⌋ + 3$ ビットという，アルファベットだけで決まる定数の上界だけだった．本節は同じ数え上げに確率を入れる．鍵になるのは，同じ長さのフレーズは相異なるので，その確率を足しても $1$ を超えない，という一点である．確率が小さいものを多く並べるほど本数は稼げるが，そのぶん $l o g 2$ の逆数の和が大きくなる．この釣り合いを不等式にしたのが Ziv の不等式であり， $1$ 文字あたりの符号長をエントロピーレートと結びつける橋になる．

フレーズの確率で数え上げを置き換える

補題 12.6.1. $X$ を空でない有限アルファベット， $𝑚$ を $0$ 以上の整数とし， $𝑆$ を $X 𝑚$ の空でない部分集合， $𝑔$ を $X 𝑚$ 上の実数値関数で $𝑆$ のすべての元で正の値をとり $\sum 𝑧 \in 𝑆 𝑔 (𝑧) \leq 1$ を満たすものとすると

| 𝑆 | l o g 2 | 𝑆 | \leq \sum 𝑧 \in 𝑆 l o g 2 1 𝑔 (𝑧)

である．

証明. $𝑀 : = | 𝑆 |$ と置き， $𝑆$ の元を $𝑧 1, \dots, 𝑧 𝑀$ と並べる． $𝑆$ は空でないから $𝑀 \geq 1$ である．定理 1.7.1 を $𝑎 𝑖 : = 1$ ， $𝑏 𝑖 : = 𝑔 (𝑧 𝑖)$ （ $𝑖 = 1, \dots, 𝑀$ ）に当てる． $𝑎 𝑖$ は非負， $𝑏 𝑖$ は仮定より正である． $\sum 𝑖 𝑎 𝑖 = 𝑀$ ， $\sum 𝑖 𝑏 𝑖 = \sum 𝑧 \in 𝑆 𝑔 (𝑧)$ だから

𝑀 l o g 2 𝑀 \sum 𝑧 \in 𝑆 𝑔 (𝑧) \leq 𝑀 \sum 𝑖 = 1 l o g 2 1 𝑔 (𝑧 𝑖)

である．仮定より $0 < \sum 𝑧 \in 𝑆 𝑔 (𝑧) \leq 1$ だから $𝑀 / \sum 𝑧 \in 𝑆 𝑔 (𝑧) \geq 𝑀$ であり， $l o g 2$ は狭義単調増加だから左辺は $𝑀 l o g 2 𝑀$ 以上である． $◻$

形式化: group_card_mul_log_le_sum_neg_log (ソース)

形式化上の注記. 宣言の仮定は本文より弱く，部分集合が空でないことを要さない（空の場合は，左辺の要素数が $0$ で右辺が空の和になり，両辺とも $0$ である）．

補題 12.6.1 は，本数と確率のやりとりをいちばん短い形で述べたものである．左辺は「相異なるものを何個並べたか」の代償であり，右辺は「それぞれがどれだけ珍しいか」の合計である．並べた個数ぶんの確率の和が $1$ を超えられない以上，個数を大きくとれば個々の確率は小さくならざるをえず， $l o g 2$ の逆数の和がそのぶん膨らむ． $𝑔$ が $𝑆$ の上で一様で，しかも総和がちょうど $1$ の場合には，右辺の各項が左辺の $1$ 個あたりのぶんに等しくなり，両辺が一致する．不等式が述べているのはこの向きだけで，一致するのがその場合に限るかどうかは言っていない．次の定理は，これを長さごとに当てる．

定理 12.6.2（Ziv の不等式）. $X$ を空でない有限アルファベット， ${𝑋 𝑖} 𝑖 \geq 0$ を $X$ に値をとる確率変数の列， $𝑘 \geq 1$ とし， $𝑠 1, \dots, 𝑠 𝑘$ を $X$ の文字を並べた空でない有限列で，長さの等しいものはどの二つも相異なるものとする．どの $𝑗$ についても $P r [(𝑋 0, \dots, 𝑋 | 𝑠 𝑗 | - 1) = 𝑠 𝑗] > 0$ であるとし， $L$ をこれらの列の長さの集合とすると

𝑘 l o g 2 𝑘 \leq 𝑘 \sum 𝑗 = 1 l o g 2 1 P r [(𝑋 0, \dots, 𝑋 | 𝑠 𝑗 | - 1) = 𝑠 𝑗] + 𝑘 l o g 2 ∣ L ∣

である．

証明. $𝑘 \geq 1$ だから $L$ は空でない有限集合であり， $𝑑 : = | L | \geq 1$ である．各 $𝑚 \in L$ に対し，長さ $𝑚$ の $𝑠 𝑗$ の全体を $𝑆 𝑚$ ，その個数を $𝑘 𝑚$ と書く．長さの等しいものは相異なるから， $𝑆 𝑚$ は $X 𝑚$ の空でない部分集合で， $\sum 𝑚 \in L 𝑘 𝑚 = 𝑘$ である．

長さごとに補題 12.6.1 を当てる． $𝑚 \in L$ を固定し， $𝑧 \in X 𝑚$ に対し $𝑔 (𝑧) : = P r [(𝑋 0, \dots, 𝑋 𝑚 - 1) = 𝑧]$ と置く．仮定より $𝑔$ は $𝑆 𝑚$ のすべての元で正である．また $𝑆 𝑚$ の相異なる元 $𝑧$ に対する事象 ${(𝑋 0, \dots, 𝑋 𝑚 - 1) = 𝑧}$ は互いに排反だから， $\sum 𝑧 \in 𝑆 𝑚 𝑔 (𝑧) \leq 1$ である．補題 12.6.1 より

𝑘 𝑚 l o g 2 𝑘 𝑚 \leq \sum 𝑧 \in 𝑆 𝑚 l o g 2 1 𝑔 (𝑧)

である．列は長さによって重なりなく分類されるから， $𝑚$ について足すと右辺は $𝑗$ について $1$ から $𝑘$ まで足したものに等しく

\sum 𝑚 \in L 𝑘 𝑚 l o g 2 𝑘 𝑚 \leq 𝑘 \sum 𝑗 = 1 l o g 2 1 P r [(𝑋 0, \dots, 𝑋 | 𝑠 𝑗 | - 1) = 𝑠 𝑗]

を得る．

残るのは左辺と $𝑘 l o g 2 𝑘$ の差である． $L$ に値をとる確率変数 $𝑌$ を $P r [𝑌 = 𝑚] : = 𝑘 𝑚 / 𝑘$ で定める（重みは非負で総和が $1$ である）．定義 1.1.1 より

𝐻 (𝑌) = - \sum 𝑚 \in L 𝑘 𝑚 𝑘 l o g 2 𝑘 𝑚 𝑘 = l o g 2 𝑘 - 1 𝑘 \sum 𝑚 \in L 𝑘 𝑚 l o g 2 𝑘 𝑚

であり， $𝑌$ は $𝑑$ 個の値しかとらないから定理 1.1.5 より $𝐻 (𝑌) \leq l o g 2 𝑑$ である．両辺に $𝑘 > 0$ を掛けて移項すると

𝑘 l o g 2 𝑘 \leq \sum 𝑚 \in L 𝑘 𝑚 l o g 2 𝑘 𝑚 + 𝑘 l o g 2 𝑑

となる．前段の不等式を入れれば主張を得る． $◼$

形式化上の注記. 定理 12.6.2 に対応する単独の宣言は無い．証明の二つの段はどちらも宣言としてあり，長さごとに補題 12.6.1 を当てる段は同じ補題のポインタ先が，長さごとの本数を束ねる段は card_mul_log_le_sum_group_mul_log_add_card_log (InformationTheory/Shannon/LZ78/ZivLengthGrouping.lean) が一般の重みについて述べている．二つを一つにまとめた宣言は，次の系 12.6.3 の形についてしか無い．

系 12.6.3. $X$ を空でない有限アルファベット， ${𝑋 𝑖} 𝑖 \geq 0$ を $X$ に値をとる確率変数の列， $𝑛 \geq 1$ ， $𝑥 \in X 𝑛$ とし， $S (𝑥) = (𝑠 1, \dots, 𝑠 𝑘)$ （定義 12.5.1）と書く． $S (𝑥)$ のどのフレーズ $𝑠$ についても $P r [(𝑋 0, \dots, 𝑋 | 𝑠 | - 1) = 𝑠] > 0$ であるとし， $L (𝑥)$ を $S (𝑥)$ に現れるフレーズの長さの集合とすると

𝑘 l o g 2 𝑘 \leq 𝑘 \sum 𝑗 = 1 l o g 2 1 P r [(𝑋 0, \dots, 𝑋 | 𝑠 𝑗 | - 1) = 𝑠 𝑗] + 𝑘 l o g 2 ∣ L (𝑥) ∣

である．

証明. $𝑛 \geq 1$ だから系 12.5.5 より $𝑘 \geq 1$ である．命題 12.5.3 よりフレーズはどの二つも相異なり，したがって長さの等しいものも相異なる．命題 12.5.4 よりどれも空列でない．仮定より周辺確率はどれも正だから，定理 12.6.2 を $𝑠 1, \dots, 𝑠 𝑘$ に当てればよい． $◼$

形式化上の注記. 系 12.6.3 に対応する宣言 lz78PhraseStrings_mul_log_le_sum_neg_log_marginal_add_overhead (InformationTheory/Shannon/LZ78/ZivMeasureBridge.lean) は，同じ不等式を定常情報源について述べている．本文の主張は定常性を使わないので，宣言のほうが仮定を一つ多くもつ．そのため形式化ポインタは付けない．機械検証が及んでいるのは定常情報源についての形までで，本節が以下で使うのはその範囲である．宣言では，長さ $𝑚$ のフレーズを $X 𝑚$ 上の関数として読み直す写像 toFinVec を経由して周辺確率を与え，和はフレーズの集合の上でとっている．命題 12.5.3 よりフレーズに重複は無いので，これは本文が $𝑗$ について $1$ から $𝑘$ まで足すことと同じである．

系 12.6.3 の右辺に現れるのは，情報源が最初の $| 𝑠 𝑗 |$ 文字でちょうど $𝑠 𝑗$ を出す確率である．いっぽう $𝑠 𝑗$ は $𝑥$ の途中から切り出された断片で，先頭から現れたとは限らない．この二つが噛み合うのは情報源が定常なとき（定義 3.1.1）で，そのとき窓をどこに置いても長さ $𝑚$ の並びの分布は同じだから，右辺は「その断片がどれだけ珍しいか」を場所によらずに測ったものになる．定常でない情報源に対しても系 12.6.3 は成り立つが，右辺が測っているものは断片の出た場所と無関係になってしまう．以下で情報源に定常性を課すのは，この理由による．

不等式の読み方も見ておく．左辺の $𝑘 l o g 2 𝑘$ は定理 12.5.7 の左辺と同じ量で，フレーズ数を長さと比べるときの主役だった．定理 12.5.7 はこれをアルファベットの大きさと $𝑛$ だけで抑えたが，系 12.6.3 はそれを情報源の確率で抑える．第 $2$ 項の $𝑘 l o g 2 | L (𝑥) |$ は，フレーズを長さごとに束ねたことの代償である．長さは $1$ 以上 $𝑛$ 以下だから $| L (𝑥) | \leq 𝑛$ であり，この項は $𝑘 l o g 2 𝑛$ 以下で，ここに系 12.5.8 の抑えを入れても， $𝑛$ で割った値の上界は定数の水準にとどまる．代償を小さくする道は，束ねた個数で測るのをやめて，長さの分布そのもので測ることである．次の借用は，この取り替えを含んでいる．

漸近最適性

ここから先は借りる．先に見取り図を置いておく．示すことは二つに分かれる．

下からの評価，すなわち $1$ 文字あたりの符号長がエントロピーレートを下回らないことは，3.5 節の Shannon–McMillan–Breiman の定理（定理 3.5.2）が，長さ $𝑛$ のブロックの確率の $- 1 𝑛 l o g 2$ をエントロピーレートに寄せることから出る．そこに，Kraft の不等式（定義 4.2.4）を満たす長さの組ではその量を大きく下回る系列がまれである，という評価を合わせる（定義 12.5.9 の符号長がその不等式を満たすことは，前節のはじめに断ったとおり本書では確かめていない）．

上からの評価は，系 12.6.3 の右辺を，記憶を深さ $𝑟$ で打ち切った近似の確率，すなわち次の文字が直前の $𝑟$ 文字だけで決まるとした $𝑟$ 次のマルコフ情報源の確率で読み直すところから始まる．束ね方も，長さだけで束ねるのをやめて，長さと直前の $𝑟$ 文字の対で束ねる形に細かくする．こうして束ねた組ごとに補題 12.6.1 を当てると， $𝑛$ で割った右辺は深さ $𝑟$ の条件付きエントロピー $𝐻 (𝑋 𝑟 ∣ 𝑋 𝑟)$ （定義 1.2.2）に寄る．最後に $𝑟$ を大きくすると，第3章定理 3.2.6 よりその極限がエントロピーレートである．束ねたことの代償も，この道筋の中で消える．定理 12.6.2 の証明で $𝐻 (𝑌) \leq l o g 2 𝑑$ と落としたところが，長さの平均で決まる上界に取り替わるからである．長さの平均は $(\sum 𝑗 | 𝑠 𝑗 |) / 𝑘$ で，これは $𝑛 / 𝑘$ 以下だから，代償は $𝑘 l o g 2 (𝑛 / 𝑘)$ の水準に下がり， $𝑛$ で割った $(𝑘 / 𝑛) l o g 2 (𝑛 / 𝑘)$ は，系 12.5.8 より $𝑘 / 𝑛$ が $0$ に近づくので $0$ に向かう．平均が与えられたときのエントロピーの上界としては定理 10.3.4 の変分上界がある．ただしここで要るのは，どの長さが現れるかによらない形の上界で，本書はそこまでは書き下さない．

見取り図のどの段も本書は書き下さない．とくに難所は， $𝑛$ の極限と深さ $𝑟$ の極限を交換する最後の段である．

Lempel–Ziv 符号の漸近最適性を借りる. 借りるのは， ${𝑋 𝑖}$ をエルゴード的な定常情報源（定義 3.1.1・定義 3.4.1）とすると，確率 $1$ で

ℓ L Z 𝑛 (𝑋 𝑛) 𝑛 ⟶ 𝐻 (X)

が成り立つ，という形である（ $ℓ L Z 𝑛$ は定義 12.5.9 の符号長， $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝐻 (X)$ は定義 3.2.1 のエントロピーレートで，第3章 3.1 節も本章も $l o g$ の底を $2$ にとっているから単位はビットである）．当てる相手は，空でない有限アルファベット $X$ 上のエルゴード的な定常情報源と，定義 12.5.9 の符号長だけである．この借用に依存するのは本節の地の文と例 12.6.4 だけで，ほかの節はこの結論を使わない．本書はこれを証明しない．骨格は定理 12.5.7 の数え上げと系 12.6.3 の不等式で，そこから先は，はじめに置いた見取り図のとおりである．難所として挙げた最後の段が，本書が 3.5 節でやった極限の入れ替えとは別の見積もりになるのは，打ち切りの深さと分解のフレーズ長が絡むからである．いっぽう，この定理は無条件の機械検証済みの定理として形式化されている．3.4 節の Birkhoff の定理や第8章 8.4 節の達成可能性と同じで，本書が証明を載せないことと形式化されていないことは別である．

形式化: lz78_asymptotic_optimality_with_greedy，上からの評価 lz78Greedy_achievability_ae (ソース)，下からの評価 lz78Greedy_converse_ae (ソース)

形式化上の注記. 収束先の書き方だけ断っておく．本文の $𝐻 (X)$ はビットで測ったエントロピーレートで，紐付け先の宣言もビット単位の entropyRate₂ (InformationTheory/Shannon/EntropyRate.lean) に収束すると述べている．第3章 3.2 節が紐付けている entropyRate は自然対数で測ったもので，entropyRate₂ はその定義自体が entropyRate を $l o g 2$ で割ったものである．すなわち二つは同じ量を別の単位で測った別の宣言であり，本節が引くのは entropyRate₂ のほうである．

借りた定理が言っているのは，Lempel–Ziv 符号が万能だということである．ただし定義 12.1.6 の万能符号とは，三つの点で違っている．一つめは対象で，ここだけは広げたことになる．定義 12.1.6 が族 ${𝑃 𝜃} 𝜃 \in Θ$ の分布だけを相手にするのに対し，借りた定理はエルゴード的な定常情報源を相手にし， $1$ 文字ずつの積で書けない，記憶のある情報源もそこに入るからである．二つめは測り方で，こちらは広い狭いが決まらない．冗長度は平均符号長についての量で，借りた定理は確率 $1$ での収束を述べており，どちらかがどちらかを含むわけではないからである．三つめは述べ方で，定義 12.1.6 は冗長度が $0$ に近づくことを求め，借りた定理は $1$ 文字あたりの符号長がエントロピーレートに近づくことを述べる．族の分布については補題 2.3.3 と例 3.2.2 より， $𝐻 (𝑃 𝑛 𝜃) / 𝑛$ もエントロピーレートも $𝐻 (𝑃 𝜃)$ に等しいから，この二つの言い方は同じ内容を指している．それでいて，符号を作るのに使ったのは定義 12.5.1 の分解だけで，情報源の分布はどこにも現れない．

比べる相手は二つある．第2章定理 2.3.2 の符号は分布を知って作られており，定義 12.1.1 の枠組みで言えば，族が $1$ 点のとき，つまり真の分布が分かっている場合にあたる．第3章系 3.5.10 は同じ極限をエルゴード的な定常情報源まで広げたが，そこでも符号を作る側は情報源を知っている．しかもそのうち記憶のあるものは，定義 12.1.1 の族には入らない．族の分布はどれも $1$ 文字ずつの積だからである．本節の符号は，どちらの場合にも情報源を知らないまま同じ極限に届く．

例 12.6.4（二つの偏ったコイン（Lempel–Ziv 符号））. 例 12.1.7 の族 ${𝑃 𝜃} 𝜃 \in {1, 2}$ をとり， $𝜃 \in {1, 2}$ を一つ固定して， ${𝑋 𝑖}$ を $𝑃 𝜃$ の i.i.d. 情報源で，エルゴード的（定義 3.4.1）であるものとする．このとき $𝜃$ がどちらであっても $𝐻 (X) = 𝐻 𝑏 (0.1) = 0.468 \dots$ ビットであり（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー），借用した Lempel–Ziv 符号の漸近最適性より，確率 $1$ で

ℓ L Z 𝑛 (𝑋 𝑛) 𝑛 ⟶ 𝐻 𝑏 (0.1)

である．すなわち，族のどちらが真であっても，符号を取り替えずに同じ値に届く．

証明. 例 3.1.2 より i.i.d. 情報源は定常だから，仮定と合わせて ${𝑋 𝑖}$ はエルゴード的な定常情報源である．エントロピーレートは例 3.2.2 より $𝐻 (X) = 𝐻 (𝑋 0)$ であり， $𝑋 0$ は $𝑃 𝜃$ に従う． $𝑃 1$ も $𝑃 2$ も一方の点の確率が $0.1$ の二値分布だから，どちらでも例 1.1.2 より $𝐻 (𝑋 0) = 𝐻 𝑏 (0.1)$ である．値は $- 0.1 l o g 2 0.1 - 0.9 l o g 2 0.9 = 0.4689 \dots$ ビットである．この情報源に借用した漸近最適性を当てれば結論を得る． $ℓ L Z 𝑛$ は定義 12.5.1 の分解だけから決まる関数で， $𝜃$ を見ずに定まっているから，どちらの $𝜃$ に対しても当てているのは同じ符号長の組である． $◼$

形式化上の注記. 例 12.6.4 に対応する単独の宣言は無い．i.i.d. 情報源のエントロピーレートを $𝐻 (𝑋 0)$ と計算した宣言も，二値エントロピーの値を与えた宣言も無い．借用した漸近最適性そのものは機械検証されているので，足りていないのは，この情報源がその仮定を満たすことと，エントロピーレートの値の計算である．

i.i.d. 情報源がエルゴード的であることは 3.4 節が述べているが，本書はそれを証明していない．そこで例 12.6.4 では，エルゴード性を仮定として置いた．数を並べると，この族について本章がたどった道のりが見える．例 12.1.7 では， $𝜃 = 1$ と決めつけた符号長の組が $𝜃 = 2$ のもとで $1$ 文字あたり $2.535 \dots$ ビットを余計に払い，何も知らないふりをして書き写す組でも $0.531 \dots$ ビットを余計に払っていた（どちらもエントロピーからの超過分である）．型による二段符号は $𝑛 = 1000$ でこれを $0.022$ ビット以下に，混合による符号は $0.003$ ビット以下に抑えた（例 12.2.7・例 12.4.8）．Lempel–Ziv 符号はどちらの分布も見ずに作られていながら， $1$ 文字あたりの符号長がエントロピーレート $0.468 \dots$ ビットに寄る，すなわち超過分が $0$ に向かう（前の四つの値は平均についてのもので，こちらは確率 $1$ での収束だから，測り方は違う）．

借りた定理は片側だけの主張ではない．偏りの大きい情報源では縮み，偏りの無い情報源では縮まない，という両方を含んでいる．一様な i.i.d. 情報源が（例 12.6.4 と同じくエルゴード的だとすれば）そうで，例 1.1.3 と例 3.2.2 よりエントロピーレートは $l o g 2 | X |$ ビットだから， $1$ 文字あたりの符号長はそこに落ち着く．これは各文字をそのまま書き写すのに要する長さで（ $| X |$ が $2$ の冪ならちょうど整数になる），縮んでいない．縮まないことは欠点ではない．エントロピーレートがその情報源の $1$ 文字あたりの不確かさそのものだからである．

本章は，情報源の分布を知らずに符号を作る問題を二つの道筋で扱った．一方は定義 12.1.1 の枠組みで，分布の族が与えられているところから始め，冗長度という一つの量に問題を落とし，型（12.2 節）と推定した分布（12.4 節）の二つの作り方で上から抑え，通信路容量（12.3 節）で下から抑えた．他方は本節までの二つで，族も分布も持ち出さず，一本の系列の中の繰り返しだけを見て符号を作り，それでも $1$ 文字あたりの符号長がエントロピーレートに届くことを見た．前者は「どの分布が真か」を有限個の候補の中で測る問題で，後者は候補を用意しない．同じ「知らずに符号化する」でも，知らなさの測り方が違っている．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．