// Tunstall 符号化 - 可変長から固定長への最適圧縮
可変長シーケンスを固定長コードにマッピングします。
記号の確率分布に基づいて辞書を構築します。
固定長コードによりシンプルで高速なデコードが可能です。
Tunstall 符号化では、可変長シーケンスからなる辞書を生成し、それらを固定長の二進コードに対応付けます。単一シンボルから開始し、最も確率の高いシーケンスを選んで、アルファベットの各シンボルを付加して拡張する操作を繰り返します。これにより、より高い確率を持つシーケンスに専用のコードワードが割り当てられる、可変長から固定長への最適な符号が得られます。
テキスト: 'aabaa'、P(a)=0.8, P(b)=0.2 辞書構築 (3ビットコード): 初期: a, b 'a' を展開: aa, ab aa を展開: aaa, aab ab を展開: aba, abb 最終的な辞書 (8コード): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 エンコード: 'aabaa' → 001 100 (aab + aa)
Tunstall 符号化は、入力が可変長・出力が固定長となるエントロピー符号化方式です。Huffman (固定長→可変長) とは異なり、Tunstall は可変長のソースシーケンスを固定長コードワードに対応付けるため、一定ビットレートが必要なアプリケーションに適しています。
Huffman: 固定長入力 → 可変長出力 (例: 'a' → '0', 'b' → '10'). Tunstall: 可変長入力 → 固定長出力 (例: 'aa' → '000', 'ab' → '001'). Tunstall はハードウェア実装や同期の観点で有利ですが、一般的に圧縮率はやや低くなります。
単一シンボルから開始します。その後、1) 最も確率の高いシーケンスを見つける、2) それを取り除き、すべての 1 シンボル拡張を追加する、3) 希望する辞書サイズ (n ビットコードなら 2^n) に達するまで繰り返します。
Tunstall 符号化は音声圧縮、画像符号化、固定レートの出力が必要な場面で使われます。特に、可変長コードがタイミングを複雑にするハードウェア実装やリアルタイムシステムで有用です。