Huffman Coding
ハフマン符号（Huffman Coding）は David Huffman が 1952 年に発表した接頭符号の構成アルゴリズムである。高頻度の記号に短い符号、低頻度の記号に長い符号を割り当て、エントロピーの下界に到達する。
目的
記号の出現頻度が既知のとき、可逆圧縮のための最適な接頭符号を構成する。DEFLATE、JPEG、MP3 のバックエンドである。
メカニズム
記号の頻度を数えてハフマン木を構築する。最低頻度の 2 ノードを繰り返し新たな親にマージし、根だけが残るまで続ける。根から葉への経路（左 0、右 1）が各記号の符号を与える。高頻度記号は短い経路を得る。
ユースケース
- DEFLATE のエントロピー符号化段階
- JPEG/MP3 のエントロピー符号化段階
- テキスト圧縮のバックエンド