問題タブ [lossless-compression]

ロスレス データ圧縮をどこまで行うことができるか疑問に思っていました。経験的なテストを実行するためのロスレス アルゴリズムのオンライン シミュレーターを見つけることができませんでした。自分で作ることもできましたが、残念ながらこの期間に十分な時間がありません。それでも、私が持っていた直感に興味があります。それについて説明します。

より一般的なアルゴリズムの 2 つだけを取ってみましょう:Huffman CodingとRun-lenght Enconding.

数字A記号のアルファベットと、そのアルファベットからの記号の任意の長いシーケンスがあるとします。たとえば、次のようになります。

ここで、各シンボルをビットの固定長ワードでコーディングするとn、圧縮されていないシーケンス、つまり長いNビットが得られます。

ハフマンを使用してシーケンスをコーディングする場合、Hビットの代わりにNビットを使用して、ビットのスペースを節約(1-H/N)*100%します。

RLE を使用して同じシーケンスをコーディングすると、Rビットを使用して を節約でき(1-R/N)*100%ます。

1つだけ使用するよりも省スペースを実現できるRLE + Huffmanか、適用するとどうなるでしょうか。Huffman + RLE

私にはかなり基本的なアイデアのように思えますが、グーグルで検索しても、このトピックに関する興味深いものは見つかりませんでした。

EDIT：うーん、最初にRLEを使用すると、単一シンボルの固定長コードとの対応が失われるため、ハフマンを使用できなくなるとはおそらく考えていませんでした。ただし、最初に Huffman を使用し、その後で RLE を使用することも可能です。

ところで、私はそのロジックに興味があります。つまり、複数の可逆圧縮アルゴリズムを連続して使用するということです。

編集 2: Mark Adler の返信にコメントしているときに、自分の質問に対する答えを見つけた可能性があることに気付きました。これです：

シンボルからシンボルへのコードであるハフマンは、検出にどのように影響しますか?

次のコードがあるとしましょう: AABCABAAB. プレーン バイナリでは、次のようにエンコードされます00 00 01 10 00 01 00 00 01(obv スペースは読みやすさのためだけです)。ハフマンはそれを次のようにコーディングします0 0 11 10 0 11 0 0 11。スペースは、文字列が変更されていないことをさらに示しているため、このスコープ (シンボル単位) でコードに近づいていると仮定すると、まったく同じ量の繰り返しを検出することができます。

これにより、コードをビット単位で分析するという別のポイント (これはすでに非常に長いコメントになっているため、ここでは説明しません) にたどり着きました。

だから、私は実際に結論に達したと思います: 私たちが知っているように、辞書 (または置換ベース) エンコーダーは可変数のシンボルを固定長コードワードにグループ化しますが、ハフマン (または他のエントロピーエンコーダー) は固定長シンボルをコード化します可変数のビットに変換し、エントロピーを最小に近似します。したがって、Huffman を最初に実行させるのは無意味です (計算の無駄でしかありません)。なぜなら、他のアルゴリズムは、 Huffman が減らすことができるより多くの冗長性を導入する可能性が高いからです。

もちろん、これは理論的な論文にすぎません。実際には、他の要因 (計算時間など) を考慮に入れることができるからです... コーディングされる文字列の構成が異なると、異なる結果が生じる可能性があるという事実は言うまでもありません。しかし、まあ... それは私には理にかなっています。:)

テキストファイルに基づいてオブジェクトを作成できるクラスを作成する方法を見つけようとしています。インターフェイス Readable にメソッド String asString() があり、クラス内のメソッド Readable read(String s) が文字列 s に基づいて Readable オブジェクトを構築する場合、(read(String s).asString()) になります。 equals(s)、書き込み/読み取り対象の Readable 型にプリミティブ引数しかない場合、リフレクションを使用して読み取りを簡単に書き込むことができましたが、コンストラクターが文字列との間で簡単に変換するためにそれらを書き込む方法がわかりません任意の順序で任意の量の Readable クラスを取ります。プリミティブのみを使用する場合、asString メソッドは次のように読み取ります。

Class.forName はプリミティブでは機能しないため、記号は任意の文字であり、String.split を使用できます。i と d は、フィールド n と d のプリミティブ型を指定します。この問題では、ネストされた Readables の約 7 層が必要ですが、そのうちのいくつかには、任意の量の Readables のコンテナーがあります。文字列に基づいて読み取りメソッドを記述する方法は理解できましたが、必要な情報をすべて保持しながら、オブジェクトを文字列に圧縮するにはどうすればよいでしょうか?

特定のロスレス圧縮アルゴリズムを使用してファイルを圧縮する場合、実行時間や結果の圧縮率をどのように予測できますか? ローカル圧縮の時間と圧縮率がわかれば、現在利用可能なネットワーク スループットに基づいてネットワーク圧縮の時間を簡単に計算できるため、特にローカル圧縮に関心があります。

サイズ、冗長性、タイプなど、ファイルに関する情報があるとします (単純にするためにテキストと言えます)。おそらく、実際の以前の測定からの統計データがいくつかあります。実行時間や圧縮率の予測を実行するには、他に何が必要でしょうか (非常に大まかなものであっても)。

ローカル圧縮だけでは、ファイルのサイズが影響します。これは、ストレージ メディア (SD カード、ハード ドライブ) との間で実際にデータを読み書きすることが、実行全体のより多くの部分を占めるためです。

ほとんどの圧縮アルゴリズムはデータの小さなブロック (100kb 程度) を圧縮することで機能するため、実際の圧縮部分はおそらく冗長性/タイプに依存します。たとえば、大きな HTML/Javascript ファイルは冗長性が高いため、圧縮率が高くなります。

スケジュールの問題もあると思いますが、おおよその目安としては無視していいでしょう。

これは、私の頭の中にある静かな質問です。オーバーヘッドの少ないコード (サーバー上など) が、実際の圧縮を実行する前にファイルを圧縮するのにかかる時間を予測できるかどうか疑問に思っていましたか?

このクラスを使用して、シリアル化されたクラスを文字列にエンコードおよびデコードし、元に戻します。

このデータは URL で使用されるため、encode 関数で文字列を圧縮し、decompress 関数で解凍したいと考えています。

データをどこでどのように圧縮するかについて、私は少し行き詰まっています。シリアル化の直後にそれを行うか、文字列だけを圧縮しますか?

どんな助けでも大歓迎です！

rg。エリック

圧縮後のファイル、ファイル、またはファイルのディレクトリの最終的なサイズを見積もりたいと思います。これを推定/計算できるプログラムまたはスクリプトを探しています。

何か案は？

このようなツールは、コマンド ラインからアクセスできる必要があります (Linux/Mac の場合)。gz一般的に使用されるロスレス圧縮アルゴリズム ( 、bzip2、zipなど)のすべてまたはほとんどで動作する場合、最も便利です。さまざまな方法の圧縮率（または同等の用途の結果のファイルサイズ）がリストされていれば、ボーナスポイントです。このようなツールは、出力を生成する前にファイルをスキャンすることを十分に期待していますが、可能であれば、実際の圧縮は避けたいと考えています。

問題がある場合は、これを汎用にすることをお勧めします。

• 簡単に圧縮できるASCIIテキストファイル、バイナリデータ、およびその間のすべてを含む、あらゆる種類のファイルでうまく機能するはずです。(もちろん、これは圧縮アルゴリズム/ツールに大きく依存します。)
• さまざまな圧縮アルゴリズム/ツールで動作するはずです

次の BASH スクリプトは、1種類の圧縮アルゴリズムに対して必要なことを実行しますが、カウントされません (見積もりが必要です)。

私は主にこれをより大きなファイル (ギガバイトより大きい) に使用します。そのため、実際の圧縮ではなく、推定値のみが必要です。

無限の深さのハッシュ チェーンに基づく LZ77/LZ4 (エントロピー エンコーディングなし) ベースの圧縮アルゴリズムを実装しました。うまく機能し、速度も許容範囲ですが、圧縮率は LZ4 に近いです。ドキュメントを読んで LZ4 プロジェクトのソース コードを閲覧すると、深さ 1 のハッシュ チェーンが使用されていることは理解できますが、実装の深さを 1 に修正すると、LZ4 のパフォーマンスが向上します。

LZ4 一致検索アルゴリズム (高速スキャン) の仕組みがわかりません。誰かがそれを説明できますか？

ありがとう。