はっきりさせておきますが、これは、任意のソース マテリアルを圧縮できるアルゴリズムという意味での完全な圧縮について話しているのではありません。それは不可能だと認識しています。私が取得しようとしているのは、シャノンエントロピーによって決定されるように、ビットのソース文字列を絶対最大圧縮状態にエンコードできるアルゴリズムです。
ハフマン符号化はある意味で最適であると聞いたことがあると思うので、この暗号化スキームはそれに基づいている可能性があると思いますが、ここに私の問題があります:
ビット文字列を考えてみましょう: a = "101010101010", b = "110100011010".
単純なシャノン エントロピーを使用すると、ビット文字列を 0 と 1 の単純な記号と見なした場合、これらのビット文字列はまったく同じエントロピーを持つはずですが、このアプローチには欠陥があります。単純に 10 の繰り返しのパターンです。これを念頭に置いて、複合シンボル 00、10、01、および 11 のシャノン エントロピーを計算することで、ソースの実際のエントロピーをより正確に把握できます。
これは単なる私の理解であり、私は完全にベースから外れている可能性がありますが、私が理解していることから、エルゴード ソースが真にランダムであるためには、長さ n のエルゴード ソースに対してです。長さ n のシンボル グループすべての統計的確率は、同じ確率である必要があります。
タイトルの質問よりも具体的だと思いますが、主な質問が 3 つあります。
シンボルとして単一ビットを使用するハフマン エンコーディングは、2 ビット シンボルのレベルで文字列を分析したときに発生する明らかなパターンがあっても、最適にビット文字列を圧縮しますか? そうでない場合、最適な圧縮率が見つかるまで、ハフマン コーディングのさまざまな「レベル」(ここで用語を乱用している場合は申し訳ありません) を循環させることで、ソースを最適に圧縮できますか? ハフマンコーディングのさまざまな「ラウンド」を経ることで、場合によっては圧縮率がさらに向上する可能性がありますか? (最初に 5 ビット長のシンボルでハフマン コーディングを行い、次に 4 ビット長のシンボルでハフマン コーディングを行いますか? huff_4bits(huff_5bits(bitstring)))