2

下のスライドの Sardinas-Patterson アルゴリズムを理解するのに苦労しています。

ここに画像の説明を入力

C1 と C2 を取得するにはどうすればよいですか???

また、インターネットから次の情報を入手しました。

リストに追加されるすべてのダングリング サフィックスはコードワードの有限セットのサフィックスであり、ダングリング サフィックスは多くても 1 回追加できるため、アルゴリズムは有限です。

  • { 0, 01, 11 }. コードワード 0 はプレフィックス 01 であるため、ダングリング サフィックス 1. { 0, 01, 11, 1 } を追加します。コードワード 0 は 01 のプレフィックスですが、ダングリング サフィックス 1 は既にリストに含まれています。コードワード 1 はプレフィックス 11 ですが、ダングリング サフィックス 1 は既にリストに含まれています。他にダングリング サフィックスはないので、このセットは一意にデコード可能であると結論付けます。
  • { 0, 01, 10 }. コードワード 0 はプレフィックス 01 であるため、ダングリング サフィックス 1 をリストに追加します。{0、01、10、1}。コードワード 1 はプレフィックス 10 ですが、ダングリング サフィックス 0 はコードワードです。したがって、コードは一意にデコードできないと結論付けてください。
4

3 に答える 3

9

ウィキの記事は素晴らしい説明です

スライドのCは、wiki記事のSiに対応しています。

これが私からの説明です：

重要な操作は、Cから2つの文字列を取得し、そのうちの1つが他の文字列のプレフィックスである場合は、プレフィックスが削除されたときに残るサフィックスを記録することです。これがC1の取得方法です。

次のC2 、 C 3などを使用します。ここでも、C iの単語の接頭辞であるCの単語を探し、残りの接尾辞を取得しますが、C_iの単語を調べて、プレフィックスであるC。C （i + 1）は、これらのセットの和集合です。

一部のCiにCからの単語が含まれるとすぐに、コードが一意にデコードできないことがわかります。

それで：

C = 1、011、01110、1110、10011

C 1 = 110（（1）110がCにあるため）、0011（（1）0011がCにあるため）、10（（011）10がCにあるため）

C 2 = {10（（1）10がC 1にあるため）、0（（1）0がC 1にあるため）} union {011、（10）011がCにあるため}

于 2012-08-14T04:42:45.247 に答える
5

C1は、CのコードワードがCの他のコードワードのプレフィックスであるかどうかを確認することで検出されます。プレフィックスである場合は、接尾辞がセットC1に追加されます。たとえば、1は1110のプレフィックスであるため、C1に追加されるサフィックス110を取得します。

C2の場合、最初にCのコードワードがC1の他のコードワードのプレフィックスであるかどうかを確認し、次にすべての「ぶら下がっているサフィックス」のセットを作成します。次に、C1がコードのプレフィックスであるかどうかを確認します。 Cの単語は、それが再びすべての「ぶら下がっている接尾辞」のセットを作成する場合。次に、これら2つのセットの和集合を取得すると、C2になります。

うまくいけば、それはちょっと理にかなっています。

于 2012-08-14T04:47:26.450 に答える
4

セットC1とC2は、このウィキペディアの記事のS1とS2に対応しています。

具体的には、C1は、Cから1つの単語を取得し、Cにも含まれる接頭辞を削除した後に残る可能性のある単語のセットです。

C2の場合、Cから単語を取得してC1からプレフィックスを削除した後、またはC1から単語を取得してCからプレフィックスを削除した後に残る可能性のある単語があります。

C3を計算する場合は、Cから単語を取得してC2にある接頭辞を削除した後に残る可能性のある単語と、C2から単語を取得してその接頭辞を削除した後に残る可能性のある単語を取得します。それはCにあります。

したがって、C3は次のようになります：{[空の単語]、0、011、10、11、1110}。空の単語が含まれているため、アルゴリズムは停止し、Cが一意にデコードできないと判断します。

于 2012-08-14T04:40:36.717 に答える