サルディナス・パターソンアルゴリズム

符号理論において、サルディナス・パターソンアルゴリズムは、与えられた可変長コードが一意に復号可能かどうかを多項式時間で判定する古典的なアルゴリズムであり、1953年に発表したオーガスト・アルバート・サルディナスとジョージ・W・パターソンにちなんで名付けられました。 ^{[ 1 ]}このアルゴリズムは、2つの異なるコードワードへの分解を許容する文字列を体系的に探索します。クヌースが報告しているように、このアルゴリズムは、当時すでに符号理論でよく知られていたにもかかわらず、約10年後の1963年にフロイドによって再発見されました。 ^{[ 2 ]}

コードを検討してください ${\displaystyle \{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}}\,\}}$^{このコードは、Berstel [ 3 ]}の例に基づいており、文字列が一意に復号できないコードの例です。

011101110011

符号語のシーケンスとして解釈できる

01110 – 1110 – 011、

しかし、それはコードワードのシーケンスとしても表される。

011 – 1 – 011 – 10011。

このエンコードされた文字列の2つの可能な復号化は、cdbとbabeによって与えられます。

一般的に、コードワードは次の考え方で見つけることができます。最初のラウンドでは、2つのコードワードを選択します。${\displaystyle x_{1}}$そして$\displaystyle y_1}}$そのため${\displaystyle x_{1}}$は接頭辞です$\displaystyle y_1}}$つまり、 ${\displaystyle x_{1}w=y_{1}}$何らかの「ぶら下がり接尾辞」のために${\displaystyle w}$最初に試してみる${\displaystyle x_{1}={\texttt {011}}}$そして${\displaystyle y_{1}={\texttt {01110}}}$ぶら下がり接尾辞は${\displaystyle {\texttt {w}}={\texttt {10}}}$2つのシーケンスを見つけることができれば${\displaystyle x_{2},\ldots ,x_{p}}$そして${\displaystyle y_{2},\ldots ,y_{q}}$次のようなコードワード ${\displaystyle x_{2}\cdots x_{p}=wy_{2}\cdots y_{q}}$そうすれば終わりです: なぜなら、その文字列は${\displaystyle x=x_{1}x_{2}\cdots x_{p}}$あるいは、次のように分解することもできます。${\displaystyle y_{1}y_{2}\cdots y_{q}}$そして、目的の文字列は少なくとも2つの異なるコードワードへの分解を持つことがわかった。

第2ラウンドでは、2つの異なるアプローチを試します。最初の試みは、wを接頭辞とする符号語を探すことです。すると、新しいダングリングサフィックスwが得られ、これを使って検索を続けることができます。最終的に、それ自体が符号語（または空語）であるダングリングサフィックスに遭遇した場合、2つの分解を持つ文字列が存在することがわかっているので、検索は終了します。2番目の試みは、それ自体がwの接頭辞である符号語を探すことです。この例では、次のようになります。${\displaystyle w={\texttt {10}}}$、そしてシーケンス1はコードワードです。したがって、次のように続けることもできます。${\displaystyle w={\texttt {0}}}$新しいぶら下がり接尾辞として。

このアルゴリズムは、形式言語の商を用いて最も簡潔に記述できる。一般に、2 つの文字列の集合DとNに対して、(左) 商は${\displaystyle N^{-1}D}$は、 Nからいくつかの接頭辞を取り除いてDから得られる残余語として定義される。正式には、${\displaystyle N^{-1}D=\{\,y\mid xy\in D~{\textrm {and}}~x\in N\,\}}$では、${\displaystyle C}$は、与えられた符号における符号語の（有限）集合を表す。

アルゴリズムはラウンドで進行し、各ラウンドでは、上述のように1つのぶら下がり接尾辞だけでなく、すべての潜在的なぶら下がり接尾辞の（有限）集合も保持します。ラウンド1から開始します。${\displaystyle i=1}$潜在的なぶら下がり接尾辞の集合は、次のように表される。${\displaystyle S_{i}}$セット${\displaystyle S_{i}}$帰納的に以下のように定義される。

$${\displaystyle S_{1}=C^{-1}C\setminus \{\varepsilon \}}$$。ここで、記号${\displaystyle \varepsilon }$空の単語を表します。

${\displaystyle S_{i+1}=C^{-1}S_{i}\cup S_{i}^{-1}C}$すべての${\displaystyle i\geq 1}$。

アルゴリズムは集合を計算します${\displaystyle S_{i}}$昇順${\displaystyle i}$. そのうちの 1 つが${\displaystyle S_{i}}$Cの単語または空の単語が含まれている場合、アルゴリズムは終了し、与えられたコードは一意に復号できないと回答します。それ以外の場合は、一度セットが${\displaystyle S_{i}}$ 以前に遭遇したセットと等しい${\displaystyle S_{j}}$と${\displaystyle j<i}$そうなると、アルゴリズムは原理的には無限ループに陥ってしまう。しかし、無限ループを続ける代わりに、与えられたコードは一意に解読可能であると答える。

左側のボックスで、指定されたコードに対するアルゴリズムの実行例を参照してください。小文字と大文字は、それぞれコードと「ぶら下がり接尾辞」文字列を表します。${\displaystyle S_{2}}$コードワードbが検出されると (赤色で表示)、アルゴリズムは停止します。右側のボックスは、アルゴリズムの実行中に収集された方程式を使用して、例の文字列 1110011 が複数のエンコーディング ( db、aae ) を持つことを示す方法を示しています。

すべてのセット${\displaystyle S_{i}}$は有限個のコードワードの接尾辞の集合であり、 の候補は有限個しかない。${\displaystyle S_{i}}$. いずれかのセットを 2 回訪問するとアルゴリズムが停止するため、アルゴリズムは無限に継続することはできず、常に終了する必要があります。より正確には、アルゴリズムが考慮するダングリングサフィックスの総数は、入力のコードワードの長さの合計に最大で等しいため、アルゴリズムはこの入力長の関数として多項式時間で実行されます。各ダングリングサフィックスとコードワードの比較を高速化するためにサフィックス ツリーを使用することで、アルゴリズムの時間は O( nk ) に制限できます。ここで、nはコードワードの合計長、kはコードワードの数です。^{[ 4 ]}アルゴリズムはパターン マッチングマシンを使用して実装できます。^{[ 5 ]}アルゴリズムは、対数空間のみを使用する非決定性チューリング マシンで実行するように実装することもできます。一意の解読可能性をテストする問題はNL 完全であるため、この空間制限は最適です。^{[ 6 ]}

アルゴリズムが正しいこと、つまり常に正しい答えを出すことの証明は、 Salomaa ^{[ 7 ]}および Berstel ら^{[ 8 ]}の教科書に見られます。

• クラフトの不等式は、場合によっては、与えられたコードが一意に解読可能である可能性を迅速に排除する方法を提供する。
• 接頭符号とブロック符号は、定義上一意に復号可能な重要な符号の種類である。
• 情報理論のタイムライン
• ポストの対応問題はこれと似ているが、決定不能である。

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010).コードとオートマタ. 数学とその応用百科事典. 第 129巻. ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-0-521-88831-8. Zbl 1187.94001 . 
• Berstel, Jean; Reutenauer, Christophe (2011).非可換有理数列とその応用. 数学とその応用百科事典. 第 137巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-19022-0. Zbl 1250.68007 . 
• Knuth, Donald E. (2003年12月). 「Robert W Floyd、追悼」. SIGACT News . 34 (4): 3–13 . doi : 10.1145/954092.954488 . S2CID 35605565 . 
• Rodeh, M. (1982). "接尾辞木に基づく一意解読可能性の高速テスト（通信）". IEEE Transactions on Information Theory . 28 (4): 648–651 . doi : 10.1109/TIT.1982.1056535 .。
• Apostolico, A.; Giancarlo, R. (1984). 「パターンマッチングマシンによる一意解読可能性の高速テストの実装」. Information Processing Letters . 18 (3): 155– 158. doi : 10.1016/0020-0190(84)90020-6 .。
• Rytter, Wojciech (1986). 「一意解読可能性問題の空間複雑性」. Information Processing Letters . 23 (1): 1– 3. doi : 10.1016/0020-0190(86)90121-3 . MR 0853618 . 。
• サロマア、アルト（1981）。形式言語理論の宝石。ピットマン出版。ISBN 0-273-08522-0. Zbl 0487.68064 . 
• サルディナス、オーガスト・アルバート、パターソン、ジョージ・W. ( 1953)、「符号化メッセージの一意分解のための必要十分条件」、IRE会議記録、1953 年全国大会、第 8 部：情報理論、pp. 104–108 。

さらに読む

• ロバート・G・ギャラガー：情報理論と信頼性の高い通信。ワイリー、1968年