プログラミングスキルを刷新し、ハフマンアルゴリズムを実装しています。今のところ、特殊文字なしの[az]を検討しています。azの確率値は、ウィキペディアから使用されています。
実行すると、ランダムな段落に対して約2倍の圧縮が得られます。しかし、この計算では、元の文字にはそれぞれ8ビット（ASCII）が必要であると想定しています。
しかし、考えてみると、26個のアイテムを表すには、5ビットが必要です。この事実に基づいて計算すると、圧縮率はほぼ1.1に低下します
だから私の質問は、実際のアプリケーションで圧縮率はどのように決定されるのかということです。
2番目の質問-azを表すために5ビットを使用するエンコーダー/デコーダーを作成する場合（たとえば、a = 0、b = 1など）-これも有効な「圧縮」アルゴリズムと見なされますか？
あなたは本質的に正しい答えを持っています。それは、あなたが扱っているのが英語の文字の頻度だけである場合、多くの圧縮を期待することはできないということです。
文字の頻度の知識から生じるゲインを計算する正しい方法は、英語の文字のエントロピーと等しい確率の26記号のアルファベットのエントロピーを考慮することです。
（私は、math.stackexchange.comのようにstackoverflowがTeX方程式を許可することを望みます。それなら、ここにまともな方程式を書くことができます。まあ。）
重要な式は-plog（p）です。ここで、pはそのシンボルの確率であり、対数は2を底とし、ビット単位で答えを取得します。シンボルごとにこれを計算してから、すべてのシンボルを合計します。
次に、理想的な算術符号化スキームでは、26個のシンボルの等確率のセットがシンボルあたり4.70ビットで符号化されます。英語での配布（ウィキペディアの記事の確率を使用）の場合、シンボルあたり4.18ビットを取得します。わずか約11％の削減。
だから、それ自体があなたを買うことができるすべての周波数バイアスです。（それはスクラブルスコアであなたにもっとたくさん買うが、私は逸脱する。）
ハフマン符号化の近似空間でも同じことを見ることができます。ここで、各符号は整数ビット数です。この場合、文字ごとに5ビットを想定することはありません（6つのコードが無駄になります）。等しい確率の26個のシンボルにハフマンコーディングを適用すると、長さが4ビットの6つのコードと、長さが5ビットの20のコードが得られます。これにより、1文字あたり平均4.77ビットになります。英語で発生する文字頻度を使用したハフマンコーディングでは、1文字あたり平均4.21ビットが得られます。エントロピー計算とほぼ同じ12％の削減。
実際のコンプレッサーがこれよりもはるかに優れている方法はたくさんあります。まず、英語全体ではなく、ファイルにあるものの頻度を使用して、ファイルに実際にあるものをコーディングします。これにより、言語に依存せず、実際のコンテンツに合わせて最適化され、存在しないシンボルもコーディングされません。次に、入力を細かく分割して、それぞれに新しいコードを作成できます。ピースが十分に大きい場合、新しいコードを送信するオーバーヘッドは小さく、通常、小さなチャンクで最適化するためにゲインは大きくなります。第三に、高次の効果を探すことができます。単一の文字の頻度の代わりに、前の文字を考慮に入れて、前の文字が与えられた場合の次の文字の確率を調べることができます。これで、追跡する確率が26 ^ 2（文字のみ）になりました。これらは、手元にある実際のデータに対して動的に生成することもできますが、ゲイン、メモリ、および時間を取得するには、より多くのデータが必要になります。メモリと時間を犠牲にして、さらに優れた圧縮パフォーマンスを実現するために、3次、4次などに進むことができます。
ランレングスエンコーディングの実行、一致する文字列の検索、ブロック変換の適用、XMLのトークン化、オーディオまたは画像のデルタコーディングなどによってデータを前処理して、次に利用するエントロピーコーダー。私は算術符号化をほのめかしました。これは、ハフマンの代わりに使用して、非常に可能性の高いシンボルをビット未満でコーディングし、すべてのシンボルを小数ビットの精度でコーディングして、エントロピーステップのパフォーマンスを向上させることができます。
圧縮を構成するものについての質問に戻ると、任意の開始点から始めることができます。たとえば、文字ごとに1つの8ビットバイトを使用して、入力についてアサーションを作成できます。たとえば、すべて小文字です（アサーションがfalseの場合、スキーム失敗）、圧縮効果を評価します。2つの異なる圧縮方式を比較するときに、同じ仮定をすべて使用する限り。データに依存するものはすべて、圧縮データの一部と見なされる必要があることに注意する必要があります。たとえば、データのブロックから派生したカスタムハフマンコードは、そのデータのブロックとともに送信する必要があります。
26文字の場合は5ビットではなく、log（26）/ log（2）=4,7ビットです。これは最大エントロピーですが、特定のエントロピーを知る必要があります。ドイツ語の場合は4,0629です。式R=Hmax-Hを使用できることがわかっている場合は、次を参照してください：http ://de.wikipedia.org/wiki/Entropie_(Informationstheorie ） http://en.wikipedia.org/wiki/Information_theory#Entropy
同じテキストに対して無制限のハフマン符号化圧縮を実行した場合、同じ結果が得られるため、同じテキストのASCII符号化に対して2倍の圧縮が得られていると言っても過言ではありません。あなたのプログラムは期待通りの圧縮を取得していると言いたくなりますが、現在、任意の入力を処理できないという制限があり、その制限が適用されている場合は、ASCIIを介した圧縮を取得するための他のより単純な圧縮スキームもあります。
任意のバイト値を処理するようにアルゴリズムを拡張してみませんか？そうすれば、真のヘッズアップ比較を行うのが簡単になります。