0

Lempel-Ziv 76 の複雑さについて説明してもらえますか? 辞書の文字列の最初の文字で初期化してから、前の部分文字列に後続のブロックが存在するかどうかを確認し、部分文字列が見つかるたびに1文字ずつ成長するという印象を受けました。前の部分文字列に部分文字列が存在しない場合、その部分文字列はブロックと呼ばれ、次の文字が次に検索される部分文字列になります。

例えば、

01011010001101110010

0|1

1 は 0 ではないので、0|1|0

0 は 01 にあるので、0|1|01

01 は 01 にあるので、0|1|011|0

0 は 01011 にあるので、0|1|011|01

01 は 01011 にあるので、0|1|011|010

010 は 01011 にあるため、0|1|011|0100|0

など、 が得られるまで続けます0|1|011|0100|011011|1001|0

必要に応じて最後の文字を繰り返すことができます。

私は何を間違っていますか?文字列 1111111 の場合、分解は 1|111111 であると言われているためです。ありがとう!

4

2 に答える 2

3

私はあなたの分解に同意します:

01011010001101110010 -> 0.1.011.0100.011011.1001.0

また、あなたが言われたことは正しいと思います:

1111111 -> 1.111111

しかし、元の分解にたどり着いた方法は正しくありません。したがって、1111111の分解に関する混乱。あなたの推論によると、次のように思います。

1111111 -> 1.11.1111

これは正しくないと確信しています

既存の一連の単語 (ブロック) への拡張は、その拡張が以前の履歴の部分文字列として以前に表示されているかどうかを確認するほど単純ではありません。それは、Lempel と Ziv が彼らの論文On the Complexity of Finite Sequences で説明している拡張の再現性の概念に要約されます (それがあなたが取り組んでいるものだと思います!)。拡張は、再現できない最短の単語になるように形成されます。過去の履歴から。彼らが説明する拡張の再現性の概念はかなり複雑ですが、要約すると、以前の履歴の開始位置を見つけることができ、そこからその開始位置から履歴の最後にシンボルを順番にコピーできます。拡張子を形成します。

元のシーケンスから、シンボルの位置が 1 から 20 であると仮定します。最初のシンボルは常にそれ自体で単語/ブロックです。

0.

次の拡張は、以前の履歴から再現できません:

0.1 .

次の拡張子は次のとおりです。

0.1。011.

0 または 01 にならない理由は次のとおりです。0 は、位置 1 から最後まで 1 つのシンボルをコピーすることによって、以前の履歴から再現できます。01 は、位置 1 から最後まで 2 つのシンボルをコピーすることで再現できます。011は再現できません。

次の拡張子は次のとおりです。

0.1.011。0100。

0 は、位置 1 から末尾まで 1 つのシンボルをコピーすることで再現できます。01 は、位置 1 から最後まで 2 つのシンボルをコピーすることで再現できます。010 は、位置 1 から末尾まで 3 つのシンボルをコピーすることで再現できます。0100 は再現できません。

等々。

1111111 の分解は次のとおりです。最初のシンボルはそれ自体がブロックです。

1.

次の拡張子は次のとおりです。

1.111111 _

1 は、位置 1 から前の履歴の最後まで 1 つのシンボルをコピーすることで再現できます。11 は、位置 1 から最後まで 2 つのシンボルをコピーすることで再現できます。ここが複雑なところです - この場合、2 つのシンボルをコピーすると、コピーのソースは実際には前の履歴の終わりを超えて拡張されます! つまり、コピーする 2 番目の 1 は、実際には、最初の 1 を末尾にコピーした結果の拡張子の一部です。同様に、111、1111、11111、111111 は、この再帰的なコピープロセスにより、すべて再現可能です。ただし、元のシーケンスの最後に到達したため、最後の拡張子は 111111 と見なされます。

うまくいけば、私の説明はある程度理にかなっています。

于 2012-09-17T05:50:57.663 に答える
2

この論文は、あなたのアルゴリズムの説明に同意しません。この論文によると、以前のパーティションと一致しない場合は、新しいパーティションがあります。行ったように、パーティション化されていない先行シーケンス全体に基づいてパーティションを作成することはできません。したがって、あなたの例では(読みやすいので、 | の代わりに . をパーティションに使用しています):

01011010001101110010

次のように分割します。

    0.1.01.10.100.011.0111.00.10

したがって、LZ76 の重量は 9 です (7 ではありません)。

1111111

次のように分割します。

1.11.111.1

どちらも、最後のパーティションが前のパーティションに含まれている場合の例を示しています。したがって、定義では <= r ではなく < r です。

私は元の論文を持っていないので、この論文が間違っていたかどうかは確認できません。しかし、彼らが元の論文から定義を誤ってコピーしたとは思えません。

于 2012-07-27T18:02:16.747 に答える