ロスレス データ圧縮をどこまで行うことができるか疑問に思っていました。経験的なテストを実行するためのロスレス アルゴリズムのオンライン シミュレーターを見つけることができませんでした。自分で作ることもできましたが、残念ながらこの期間に十分な時間がありません。それでも、私が持っていた直感に興味があります。それについて説明します。
より一般的なアルゴリズムの 2 つだけを取ってみましょう:Huffman CodingとRun-lenght Enconding.
数字A記号のアルファベットと、そのアルファベットからの記号の任意の長いシーケンスがあるとします。たとえば、次のようになります。
Alphabet = {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, W, Y, Z}
Sequence1 = SFBJNERUSNJGSDKKDEIJGNMSDJDDSUSJNF
Sequence2 = MNMNMNREGUHSDFJUF
Sequence3 = MMMMMNNNNNASDUERJGASIUJMMMNNNUNS
ここで、各シンボルをビットの固定長ワードでコーディングすると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 が減らすことができるより多くの冗長性を導入する可能性が高いからです。
もちろん、これは理論的な論文にすぎません。実際には、他の要因 (計算時間など) を考慮に入れることができるからです... コーディングされる文字列の構成が異なると、異なる結果が生じる可能性があるという事実は言うまでもありません。しかし、まあ... それは私には理にかなっています。:)