プレフィックスコード

プレフィックス コードは、コードシステムの一種で、「プレフィックス プロパティ」を備えていることで区別されます。プレフィックス プロパティでは、システム内のコード ワード全体が、システム内の他のコード ワードのプレフィックス(最初のセグメント) になっていないことが必要です。これは固定長コードの場合は当然当てはまりますが、可変長コードの場合は考慮する点にすぎません。

たとえば、コード {9, 55} のコードにはプレフィックス プロパティがありますが、{9, 5, 59, 55} で構成されるコードにはプレフィックス プロパティがありません。これは、「5」が「59」のプレフィックスであり、「55」のプレフィックスでもあるためです。プレフィックス コードは一意にデコード可能なコードです。完全で正確なシーケンスが与えられれば、受信者は単語間に特別なマーカーを必要とせずに各単語を識別できます。ただし、一意にデコード可能なコードでもプレフィックス コードではないものがあります。たとえば、プレフィックス コードの逆は一意にデコード可能ですが (サフィックス コードです)、必ずしもプレフィックス コードであるとは限りません。

プレフィックスコードは、プレフィックスフリーコード、プレフィックス条件コード、瞬時コードとも呼ばれます。ハフマン符号化はプレフィックスコードを導出する多くのアルゴリズムの1つに過ぎませんが、コードがハフマンアルゴリズムによって生成されていない場合でも、プレフィックスコードは「ハフマンコード」とも広く呼ばれています。コンマフリーコードという用語は、プレフィックスフリーコードの同義語として適用されることもあります^{[1] [2]}が、ほとんどの数学の本や記事（例^{[3] [4]}）では、コンマフリーコードはプレフィックスコードのサブクラスである自己同期コードを意味するために使用されます。

プレフィックス コードを使用すると、メッセージは、アウトオブバンドマーカーや (あるいは)メッセージ内の単語を囲む単語間の特別なマーカーなしで、連結されたコード ワードのシーケンスとして送信できます。受信者は、有効なコード ワードを形成するシーケンスを繰り返し見つけて削除することで、メッセージを明確にデコードできます。これは、プレフィックス プロパティのないコード (例: {0, 1, 10, 11}) では一般に不可能です。コード ワードの先頭の "1" を読み取った受信者は、それが完全なコード ワード "1" なのか、単にコード ワード "10" または "11" のプレフィックスなのかを知りません。そのため、文字列 "10" は、単一のコード ワードとして解釈することも、単語 "1" と "0" の連結として解釈することもできます。

可変長ハフマン コード、国別呼び出しコード、 ISBNの国と発行者部分、UMTS W-CDMA 3G ワイヤレス標準で使用されるセカンダリ同期コード、およびほとんどのコンピュータ マイクロアーキテクチャの命令セット(マシン言語) は、プレフィックス コードです。

プレフィックス コードはエラー訂正コードではありません。実際には、メッセージは最初にプレフィックス コードで圧縮され、その後、伝送前にチャネル コーディング(エラー訂正を含む) で再度エンコードされます。

一意にデコード可能なコードには、同じコードワード長を持つプレフィックスコードが存在します。^[5] クラフトの不等式は、一意にデコード可能なコードで可能なコードワード長の集合を特徴付けます。^[6]

コード内のすべてのワードが同じ長さである場合、そのコードは固定長コード、またはブロック コードと呼ばれます (ただし、ブロック コードという用語は、チャネル コーディングにおける固定サイズのエラー訂正コードにも使用されます)。たとえば、ISO 8859-15 の文字は常に 8 ビット長です。UTF -32/UCS-4 の文字は常に 32 ビット長です。ATMセルは常に 424 ビット (53 バイト) 長です。固定長kビットの固定長コードは、最大ソース シンボルをエンコードできます。 ${\displaystyle 2^{k}}$

固定長コードは必然的にプレフィックス コードになります。最長プレフィックスの長さに合うように、短いプレフィックスに固定シンボルをパディングすることで、任意のコードを固定長コードに変換できます。あるいは、このようなパディング コードを使用して冗長性を導入し、自動修正や同期を可能にすることもできます。ただし、一部の単語が他の単語よりも送信される可能性がはるかに高い状況では、固定長エンコードは非効率的です。

切り捨てバイナリ符号化は、シンボル数nが 2 の累乗ではない場合に対処するために、固定長コードを単純に一般化したものです。ソース シンボルには長さkとk +1 のコードワードが割り当てられます。ここで、k は2 ^k < n ≤ 2 ^k+1となるように選択されます。

ハフマン符号化は、可変長プレフィックス コードを作成するためのより洗練された手法です。ハフマン符号化アルゴリズムは、コード ワードが持つべき頻度を入力として受け取り、コード ワード長の加重平均を最小化するプレフィックス コードを作成します。(これは、エントロピーの最小化と密接に関連しています。) これは、エントロピー符号化に基づくロスレス データ圧縮の形式です。

一部のコードでは、通常のデータとは異なる特別な「カンマ」記号（センチネル値とも呼ばれる）でコードワードの終わりを示します。 ^[7]これは、文中の単語間のスペースに似ています。スペースは、1 つの単語が終了し、別の単語が始まる場所を示します。すべてのコードワードがカンマで終了し、コードワード内の他の場所にカンマが表示されない場合、コードは自動的にプレフィックスフリーになります。ただし、記号全体をカンマ専用に予約することは、特に記号の数が少ない言語では非効率的です。モールス信号は、カンマを含む可変長コードの一般的な例です。文字間の長い休止と単語間のさらに長い休止は、1 つの文字（または単語）が終了し、次の文字が始まる場所を認識するのに役立ちます。同様に、フィボナッチ コーディングでは、すべてのコードワードの終了を示すために「11」を使用します。

自己同期コードは、フレーム同期を可能にするプレフィックス コードです。

サフィックスコードとは、他のどのサフィックスでもない単語の集合、つまりプレフィックスコードの逆である単語の集合である。プレフィックスコードと同様に、このような単語の連結としての文字列の表現は一意である。ビフィックスコードは、プレフィックスコードとサフィックスコードの両方である単語の集合である。^[8] 最適なプレフィックスコードは、平均長が最小のプレフィックスコードである。つまり、プレフィックスコードCの確率を持つn個の記号のアルファベットを想定する。C ' が別のプレフィックスコードで、がC'のコードワードの長さである場合、となる。^[9]${\displaystyle p(A_{i})}$${\displaystyle \lambda '_{i}}$${\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}$

プレフィックス コードの例には次のものがあります。

• 可変長ハフマン符号
• 国番号
• チェン・ホー符号化
• ISBNの国と出版社の部分
• UMTS W-CDMA 3Gワイヤレス標準で使用されるセカンダリ同期コード
• VCR Plus+ コード
• Unicode変換形式、特にUnicode文字をエンコードするためのUTF-8システム。これはプレフィックスフリーコードであり、自己同期コードでもある^[10]
• 可変長量

プレフィックス コードを構築するために一般的に使用される手法には、ハフマン コードや以前のシャノン-ファノ コード、次のようなユニバーサル コードなどがあります。

• エリアスデルタコーディング
• エリアスガンマコーディング
• エリアス オメガコーディング
• フィボナッチコーディング
• レーベンシュタインコーディング
• 単項コーディング
• ゴロムライスコード
• ストラドリングチェッカーボード（プレフィックスコードを生成する単純な暗号化技術）
• バイナリコーディング^[11]

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010) 。コードとオートマトン。数学とその応用百科事典。第129巻。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-88831-8.ZBL1187.94001  。​
• エリアス、ピーター(1975)。「ユニバーサルコードワードセットと整数の表現」。IEEE Trans. Inf. Theory . 21 (2): 194–203. doi :10.1109/tit.1975.1055349. ISSN  0018-9448. Zbl  0298.94011.
• DA ハフマン、「最小冗長コードの構築方法」、IRE 会議録、1952 年 9 月、pp. 1098–1102 (ハフマンのオリジナル記事)
• プロフィール: デビッド・A・ハフマン、サイエンティフィック・アメリカン、1991年9月、pp. 54-58 (背景記事)
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Pressおよび McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 16.3、pp. 385–392。 
•  この記事には、連邦規格 1037Cのパブリック ドメイン マテリアルが組み込まれています。一般調達局。2022 年 1 月 22 日にオリジナルからアーカイブされました。

• コード、ツリー、プレフィックスプロパティ (Kona Macphee 著)