ヘッダーなしの出力を生成する可逆圧縮アルゴリズムを知っている人はいますか? たとえば、圧縮に使用されたハフマン木を保存しませんか? ハードコーディングされたハフマンツリーについては触れませんが、出力にメタデータを保存せずに入力を圧縮および解凍できるアルゴリズムがあるかどうか知りたいです。それとも、これは理論的にも不可能ですか?
5 に答える
もちろん可能です。特に、LZ ファミリーのコンプレッサーは、圧縮 (または圧縮解除) の進行に伴ってオンラインで辞書が構築されるため、圧縮されたデータ自体以外には何も出力する必要がありません。これらの LZ タイプのアルゴリズムの参照実装がたくさんあります。たとえば、LZMA、7zip のコンポーネント。
ランレングスエンコーディングはその一例です
適応ハフマン符号化はまさにそれを行います。より一般的には、適応コーディングという用語は、この特性を持つエントロピー コードを説明するために使用されます。ランレングス エンコーディング (RLE)やLempel-Ziv-Welch (LZW)など、一部の辞書コードにもこのプロパティがあります。
lzoが思い浮かびます。OpenVPNで使用されており、素晴らしい結果が得られています
ヘッダーレス圧縮出力を使用した圧縮アルゴリズムを探しているのはなぜですか?
おそらく (a) 低遅延のストリーミング圧縮/解凍を必要とする双方向電話のようなシステムを使用している。Zach Scrivena が言及した圧縮アルゴリズムの適応コーディング カテゴリと、 Diego Sevilla と Javier が言及した辞書圧縮アルゴリズムの LZ ファミリは、この種のアプリケーションに最適です。これらのアルゴリズムの実際の実装では、通常、先頭に 1 ~ 2 バイトのメタデータがありますが ((b) アプリケーションでは役に立たなくなります)、レイテンシーにはほとんどまたはまったく影響しません。
おそらく (b) あなたは主に暗号化に興味があり、圧縮されたテキストに固定のメタデータ ヘッダー "crib" がない限り、compress-before-encrypt によってセキュリティ プロパティが改善されると聞いています。最新の暗号化アルゴリズムは (私たちが知る限り) そのような「cribs」に対して脆弱ではありませんが、偏執的である場合は、「全単射圧縮」 ( a、b、cなど) に興味があるかもしれません。受信機がそのような圧縮された出力を取得する場合、送信エラー (反転したビット、挿入されたビット、削除されたビットなど) を検出することはできません (これらのアルゴリズムは (a) アプリケーションには特に有用ではありません)。
おそらく (c) 他の理由でヘッダーレス圧縮に興味があるでしょう。魅力的に聞こえますが、その理由は何ですか?