問題タブ [lempel-ziv-76]

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

例えば、

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 であると言われているためです。ありがとう！

lempel-ziv デコード メソッドで indexError を取得します。これは私のコードです。サイズが 3 になることはわかっていますが、len(LT) はちょうど 2 です。しかし、擬似コードを python コードに変換しただけです。

これはエラーメッセージです：

これは Google にとって信じられないほど難しい質問でした。私は gzip や Zip や deflate を探しているわけではありません。使用したいアルゴリズムは「圧縮」と呼ばれますが、それは一般的に圧縮を実装しようとしているという意味ではありません。特定のアルゴリズムを探しています。

compressUnix ライクなシステムのコマンド ライン ツールで使用される適応型 Lempel-Ziv アルゴリズムを探しています。Content-Encoding: compressヘッダーを受信したときに使用する必要があると HTTP が言うアルゴリズムを探しています。man compressこれは、POSIX シェルで入力したときに説明されているアルゴリズムであり、このウィキペディアの記事.

この圧縮アルゴリズムは非常に古く、ほとんどすべての実用的な目的で gzip、Zip、deflate などに置き換えられていることを理解しています。しかし、私はペット プロジェクトとして C++ でサーバーを作成しており、IANA はこの Unix の「圧縮」アルゴリズムを、すべてのサーバーがサポートすべきエンコーディングの 1 つとして指定しています。

このcompressユーティリティは、長い間 (POSIX の前から) Unix シェルの一部であり、標準の C 言語実装がないとは信じられません。への呼び出しを使用したり、シェルで圧縮を実行したりすることもできますが(別のプロセスを作成する...うーん)、アルゴリズムを実行可能ファイルにコンパイルするよりもはるかに効率的ではありません。systemexec

このアルゴリズムの標準 C 実装/ライブラリはありますか?

受信者が uncompress ユーティリティで読み取ることを期待しているため、.Z (圧縮) ファイルを作成する必要があります。しかし、Linux ホストに圧縮パッケージをインストールする可能性はありません。

gzip コマンドで圧縮された .Z ファイル (適応型 Lempel-Ziv コーディングを使用) を取得する方法はありますか?