5

LZW 圧縮/解凍を実装する必要がある割り当てのプログラムを作成しています。これには次のアルゴリズムを使用しています。

-圧縮

w = NIL;
   while ( read a character k )
       {
         if wk exists in the dictionary
         w = wk;
         else
         add wk to the dictionary;
         output the code for w;
         w = k;
       }

-減圧

read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
        }

圧縮段階では、辞書エントリのインデックスを表す int を出力するだけです。また、開始辞書は ascii 文字 (0 ～ 255) で構成されます。しかし、解凍段階になると、このエラーが発生します。たとえば、「ブープ」のみで構成されるテキスト ファイルを圧縮すると、次の手順を実行して出力ファイルが生成されます。

w       k       Dictionary          Output

-       b       -                   -
b       o       bo (256)            98 (b)
o       o       oo (257)            111 (o)
o       o       -                   -
oo      p       oop (258)           257 (oo)
p       -       -                   112 (p)

output.txt: 98 111 257 112

次に、ファイルを解凍するときに

w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (error)

257 (oo) はまだ追加されていません。私が困惑しているので、ここでどこが間違っているのか誰にもわかりますか。アルゴリズムがおかしい？

4

2 に答える 2

8

圧縮部分は正しく完全ですが、解凍部分は完全ではありません。コードが辞書にある場合にのみ大文字と小文字を含めます。解凍プロセスは常に圧縮プロセスよりも 1 ステップ遅れているため、デコーダーが辞書にないコードを検出する可能性があります。しかし、それは 1 ステップだけ遅れているため、エンコーディング プロセスが次に追加するものを把握し、デコードされた文字列を正しく出力して、辞書に追加することができます。次のように解凍プロセスを続行するには:

-減圧

read a character k;
   output k;
   w = k;
   while ( read a character k )    
  /* k could be a character or a code. */
        {
         if k exists in the dictionary
         entry = dictionary entry for k;
         output entry;
         add w + entry[0] to dictionary;
         w = entry;
         else
         output entry = w + firstCharacterOf(w);
         add entry to dictionary;
         w = entry;
        }

次に、ファイルを解凍して 257 を確認すると、それが辞書にないことがわかります。しかし、前のエントリが 'o' で、最初の文字も 'o' であることはわかっています。これらを組み合わせると、「oo」になります。oo を出力し、辞書に追加します。次にコード 112 を取得し、それが p であることを確認します。終わり！

w       k          entry        output       Dictionary
        98 (b)                  b   
b       111 (o)    o            o             bo (256)
o       257 (oo)                oo            oo(257)
oo      112(p)                  p

詳細については、Steve Blackstock によるこの説明を参照してください。「icafe」 Java 画像ライブラリ GIF エンコーダーおよびデコーダーのベースとなっている、実際のデコーダーおよびエンコーダーの実装のフローチャートを含むより良いページ。

于 2012-05-04T16:12:45.687 に答える
1

http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welcomeから、あなたはこのケースに陥っていますか?

デコーダーがまだ辞書にないコード Z を受け取った場合はどうなりますか? デコーダーは常にエンコーダーの 1 つのコードの後ろにあるため、エンコーダーが χ の前のコード X を発行したときに、エンコーダーがそれを生成した場合にのみ、Z はエンコーダーのディクショナリに存在できます。したがって、Z は χ + ? である ω をコード化し、デコーダは次のように未知の文字を判別できます。

1) The decoder sees X and then Z.
2) It knows X codes the sequence χ and Z codes some unknown sequence ω.
3) It knows the encoder just added Z to code χ + some unknown character,
4) and it knows that the unknown character is the first letter z of ω.
5) But the first letter of ω (= χ + ?) must then also be the first letter of χ.
6) So ω must be χ + x, where x is the first letter of χ.
7) So the decoder figures out what Z codes even though it's not in the table,
8) and upon receiving Z, the decoder decodes it as χ + x, and adds χ + x to the table as the value of Z.

この状況は、エンコーダーがフォーム cScSc の入力に遭遇するたびに発生します。ここで、c は単一の文字、S は文字列、cS は既に辞書に登録されていますが、cSc は辞書に登録されていません。エンコーダーは cS のコードを発行し、cSc の新しいコードを辞書に入れます。次に、入力内の cSc を確認し (cScSc の 2 番目の c から開始)、挿入したばかりの新しいコードを発行します。上記の議論は、デコーダーが辞書にないコードを受け取るたびに、状況が次のようになることを示しています。

cScSc 形式の入力はありそうにないように思えるかもしれませんが、このパターンは、入力ストリームがかなりの繰り返しによって特徴付けられる場合にかなり一般的です。特に、単一文字の長い文字列 (LZW がエンコードによく使用される種類の画像では一般的) は、この種のパターンを繰り返し生成します。

この特定のケースでは、ウィキペディアのことが当てはまります。X+ はありますか? ここで、X は (o) で、Z はこれまでのところ不明なので、最初の文字は X であり、(oo) を追加して (oo) を表に 257 として追加します。ウィキペディアで読んだことをそのまま続けます。これがどうなるか教えてください。それが解決策でない場合。

于 2012-05-04T14:30:52.647 に答える