タンストールコーディング

コンピュータサイエンスと情報理論において、タンストール符号化は、ロスレスデータ圧縮に使用されるエントロピー符号化の一種です。

タンストール符号化は、ジョージア工科大学在学中のブライアン・パーカー・タンストールが1967年に博士論文で発表したテーマである。その論文のテーマは「ノイズのない圧縮コードの合成」であった^[1]。

その設計はLempel-Zivの前身です。

ハフマン符号化やレンペル・ジフ符号化などの可変長符号とは異なり、タンストール符号化はソースシンボルを固定数のビットにマッピングする符号である。 ^[2]

タンストール符号とレンペル・ジフ符号はどちらも可変長ワードを固定長符号で表現します。^[3]

一般的なセット符号化とは異なり、Tunstall 符号化は、可変長のコードワードを使用して確率的ソースを解析します。

^[4]によれば 、十分に大きな辞書の場合、ソース文字あたりのビット数はソースの エントロピーに任意に近くなることが示されています。${\displaystyle H(U)}$

このアルゴリズムでは、入力として入力アルファベットと、各単語入力の確率分布が必要です。また、計算する辞書のサイズの上限となる任意の定数 も必要です。問題の辞書 は確率のツリーとして構築され、各エッジは入力アルファベットの文字に関連付けられています。アルゴリズムは次のようになります。 ${\displaystyle {\mathcal {U}}}$${\displaystyle C}$${\displaystyle D}$

D := 葉のツリー。各文字ごとに 1 つずつあります。${\displaystyle |{\mathcal {U}}|}$${\displaystyle {\mathcal {U}}}$
その間：${\displaystyle |D|<C}$
    最も可能性の高い葉を葉のある木に変換します。
${\displaystyle |{\mathcal {U}}|}$

文字列「hello, world」をエンコードするとします。さらに、入力アルファベット には文字列「hello, world」の文字、つまり「h」、「e」、「l」、「,」、「」、「w」、「o」、「r」、「d」のみが含まれていると仮定します (やや非現実的です)。したがって、入力文字列での統計的な出現に基づいて、各文字の確率を計算できます。たとえば、文字 L は 12 文字の文字列に 3 回出現します。その確率は です。 ${\displaystyle {\mathcal {U}}}$${\displaystyle 3 \over 12}$

ツリーを初期化し、まず葉のツリーから始めます。各単語はアルファベットの文字に直接関連付けられます。こうして得られた 9 つの単語は、固定サイズのビット出力にエンコードできます。 ${\displaystyle |{\mathcal {U}}|=9}$${\displaystyle \lceil \log _{2}(9)\rceil =4}$

次に、最も確率の高い葉 (ここでは) を取り、それを各文字につき 1 つずつの別の葉のツリーに変換します。これらの葉の確率を再計算します。たとえば、2 つの文字のシーケンス L は 1 回発生します。文字の後に L が続くシーケンスが 3 回発生するとすると、結果として得られる確率は になります。 ${\displaystyle w_{1}}$${\displaystyle |{\mathcal {U}}|=9}$${\displaystyle {1 \over 3}\cdot {3 \over 12}={1 \over 12}}$

17 個のワードが得られ、それぞれを固定サイズのビット出力にエンコードできます。 ${\displaystyle \lceil \log _{2}(17)\rceil =5}$

さらに繰り返して、毎回 単語の数を増やすことができることに注意してください。${\displaystyle |{\mathcal {U}}|-1=8}$

タンストール符号化では、解析操作の前に、アルゴリズムがアルファベットの各文字の確率分布を知る必要があります。この問題は、ハフマン符号化でも同様です。

固定長のブロック出力を必要とするため、同様の辞書ベースの設計を持ちながら可変サイズのブロック出力を持つLempel–Zivよりも劣ります。 ^{[説明が必要]}

これは、多項式スクランブルなどによってスクランブルされたデータを読み取る（送信する）ために使用される Tunstall コードの例です。この特定の例は、ストリーム内のデータの基数を 2 から 3 に変更するのに役立ち、コストのかかる基数変更ルーチンを回避します。基数変更では、読み取りの「効率」によって特に制限されます。理想的には、平均してビットを使用してコードを読み取る必要があります。これにより、コードごとに最大ビットを使用する義務がある新しい基数を使用するときに、読み取りによって、そもそも基数変更を使用している送信の効率マージンが低下することがなくなります。したがって、異なる基数を持つチャネル間でデータを効率的に送信するために、読み取りから基数変更までのメカニズムを使用できます。たとえば、マッピング コード（未使用のコードが多数ある）と比較して効率を高めて、MLT-3 チャネル間でバイナリ データを送信します。 ${\textstyle \log _{n}}$${\textstyle \log _{n}}$

本質的には、完全にスクランブルされたバイナリ データ、つまり「暗黙のデータ」を、基数 3 のチャネルを使用して送信する目的で読み取っています。3 進タンストール ツリーのリーフ ノードを参照してください。ご覧のとおり、読み取りの結果、最初の桁は「B」になります。これは、長さ 2 の暗黙のデータからの読み取りを試行するため、暗黙の確率が 25% であるため、25% の確率です。「B」のような読み取りではそれ以上読み取られませんが、75% の確率で「A」または「C」が読み取られ、別のコードが必要になります。したがって、読み取りの効率は 2.75 (サイズ 7 のハフマン コードの平均長) / 1.75 (1 桁または 2 桁の基数 3 のタンストール コードの平均長) =となり、要件どおりに に非常に近くなり、効率が になります。その後、基数 3 のチャネルを使用してシンボルを効率的に送信できます。 ${\textstyle 1.57142857}$${\textstyle \log _{2}3=1.5849625}$${\textstyle 99.15\%}$

ウィキメディア・コモンズには、タンストール符号化に関連するメディアがあります。