YOI 752：ハフマン符号は最適だが、それは符号の長さが整数という縛りの中での最適である

論文752 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/752 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23015146）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi752,
  author = {Yamagishi, Yuuki},
  title = {The Huffman Code Is Optimal, but Only Within the Constraint That Code Lengths Be Whole Numbers},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/752},
  doi = {10.5281/zenodo.23015146},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

ハフマン符号は、平均の長さが最も短い符号として知られる。けれど、その最適はエントロピーに届くことを意味しない。何の中での最適かと、どれだけ届かないかを数える。新しい定理も法則も主張しない。

第一に、確率が $2$ の冪なら、ちょうど届く。$1/2$・$1/4$・$1/8$・$1/8$ で平均の長さ $\mathbf{1.750000}$、エントロピー $\mathbf{1.750000}$（第2節）。

第二に、偏った二記号では、最適な符号が大きく外れる。確率 $0.99$ でエントロピー $\mathbf{0.080793}$ ビットに対し、一記号ずつのハフマンは $\mathbf{1.000000}$ ビット（第3節）。

第三に、これが本稿の芯である。「最適な符号」がエントロピーの $\mathbf{12.377289}$ 倍を使う。長さが整数でなければならず、一記号に $1$ ビットより短い長さを割り当てられないからである（第3節）。

第四に、まとめると近づくが、上から近づくだけである。$2$ 個・$4$ 個・$8$ 個ずつで $\mathbf{0.514950}$・$\mathbf{0.272698}$・$\mathbf{0.157158}$ ビット、差はいつも $1/k$ 未満（第3節）。

第五に、$8$ 個ずつでも、まだ $\mathbf{1.945193}$ 倍、クラフト和はどれも $\mathbf{1.000000}$ で、符号に隙間は無い（第3節）。

第六に、分離子は、各記号の確率が $2$ の冪かである。冪なら一記号ずつで届き、冪でなければまとめる長さを伸ばしても差は消えきらない（第4節）。

キーワード：ハフマン符号、エントロピー、符号の長さ、クラフトの不等式、記号をまとめる符号化、整数の縛り

Abstract

The Huffman code is known as the code of shortest average length. That optimality does not mean reaching the entropy.Optimal within what, and how far short, is counted.No new theorem or law is claimed.

First, with probabilities that are powers of $2$, it arrives exactly、$1/2$, $1/4$, $1/8$, $1/8$: average length $\mathbf{1.750000}$, entropy $\mathbf{1.750000}$ (Section 2).

Second, for two skewed symbols, the optimal code is far off、at probability $0.99$ the entropy is $\mathbf{0.080793}$ bits, while symbol-by-symbol Huffman spends $\mathbf{1.000000}$ bit (Section 3).

Third, and this is the core. The “optimal code” spends $\mathbf{12.377289}$ times the entropy、because lengths must be whole numbers and no symbol can be given less than $1$ bit (Section 3).

Fourth, grouping approaches, but only from above、groups of $2$, $4$ and $8$ give $\mathbf{0.514950}$, $\mathbf{0.272698}$ and $\mathbf{0.157158}$ bits, always within $1/k$ (Section 3).

Fifth, even at $8$, still $\mathbf{1.945193}$ times、every Kraft sum is $\mathbf{1.000000}$, so the code has no gaps (Section 3).

Sixth, the separator is whether each symbol’s probability is a power of $2$、if so, symbol-by-symbol coding arrives; if not, the gap shrinks with grouping but never vanishes (Section 4).

Keywords: Huffman code, entropy, code length, Kraft inequality, coding symbols in groups, whole-number constraint

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/752/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/752 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ