スタート-ステップ-ストップコーディングスキームに対する最適なパラメーターを計算するにはどうすればよいですか？

Question

開始ステップ停止コードは、比較的小さい数を圧縮するために使用されるデータ圧縮技術です。

コードは次のように機能します。開始、ステップ、停止の3つのパラメーターがあります。 Startは、最初の数を計算するために使用されるビットの量を決定します。 Stepは、実行時にエンコードに追加するビット数を決定し、stopは、数値のエンコードに使用されるビットの最大量を決定します。

したがって、エンコーディングの長さは、l = start + step * iで与えられます。

＆quot; i＆quot;特定のコードの値は、単項を使用してエンコードされます。つまり、1ビットの数とそれに続く終了0ビットです。ストップに達した場合、終端の0ビットをドロップできます。 iがゼロの場合、0ビットのみを書き込みます。

そのため、（1、2、5）開始ステップ停止コードは次のように機能します。

値0、エンコード：0 0
値1、エンコード：0 1
値2、エンコード：10 000
値9、エンコード：10 111
値10、エンコード：11 00000
値41、エンコード：11 11111

では、いくつかの数字を含むファイルが与えられた場合、そのファイルの最適な開始-ステップ-終了コードをどのように計算できますか？最適なパラメーターは、圧縮率が最大になるものとして定義されます。

Answer 1

これらの＆quot; start-step-stop＆quot;コードは、ハフマンコードを呼び出す別の方法のように見えます。それらを計算するための擬似コードの概要については、基本的なテクニックをご覧ください。 p>

本質的に、これはアルゴリズムが行うことです：

ハフマンエンコーディングを開始する前に、圧縮する各シンボルの統計を収集する必要があります（圧縮するファイル内の合計頻度）。

バイナリツリーを作成した後、その情報を使用して最も頻繁に使用されるシンボルはツリーの最上部にあり（したがって、使用するビット数が少ない）、エンコードに prefixがないコード。エンコーディングに共通の接頭辞が含まれている場合、圧縮解除があいまいになる可能性があるため。

ハフマンエンコーディングの終了時、開始値は最も浅いリーフノードの深さになり、ステップは常に1になります（論理的にこれは理にかなっています。なぜ必要以上のビットを強制するのか、一度に1つずつ追加するだけです） 、）、ストップ値は最も深いリーフノードの深さになります。

頻度統計がソートされていない場合、O（nlog n）が必要です。頻度でソートされている場合、O（n）で実行できます。

ハフマン符号は、このタイプのエンコーディングに対して最高の平均圧縮を保証します。

  

ハフマンは最も多くの   これの効率的な圧縮方法   タイプ：個人の他のマッピングなし   ソースシンボルの一意の文字列   ビットはより小さな平均を生成します   実際のシンボルの出力サイズ   周波数は   コードを作成します。

これは、問題に対する理想的な解決策を実装するのに役立ちます。

編集：同様ですが、これはOPが探していたものではありません。

これらのコードの作成者による学術論文は、開始ステップ停止コード、開始停止コード。ただし、著者はセクション2の終わり近くで最適な開始-ステップ-停止を取得する方法について簡単に説明します。これには、統計ランダム変数の使用、または最適な組み合わせのブルートフォース資金が含まれます。ファイルの事前知識がない場合、アルゴリズムはO（（log n）^ 3）です。

これがお役に立てば幸いです。

Answer 2

私が使用したアプローチは、単純なブルートフォースソリューションでした。アルゴリズムは次の基本手順に従いました。

1. ファイル内の各数値の頻度をカウントします。同じパスで、ファイル内の数字の合計数を計算し、最大数をmaxNumberとして決定します。

2. 各数値の確率を、その頻度をファイル内の数値の合計量で割ったものとして計算します。

3. ＆quot; optimalStop＆quot;を決定します。 log2（maxNumber）と等しい。これは、シャノン情報理論のようにmaxNumberを表すために使用する理想的なビット数であるため、特定の数のエンコードに使用される最適な最大ビット量の合理的な推定値です。

4. すべての＆quot; start＆quot;に対して1から「optimalStop」までの値手順5〜7を繰り返します。

5. すべての＆quot; step＆quot;に対して1から（＆quot; optimalStop＆quot;-＆quot; start＆quot;）/ 2までの値、ステップ6を繰り返します＆amp; 7：

6. 「停止」を計算します; 「optimalStop」に最も近い値整数iに対してstop = start + step * iを満たすもの。

7. このエンコードで使用されるビットの平均数を計算します。これは、各数値の確率に特定のエンコーディングのビット長を乗じて計算できます。

8. 平均ビット数が最小のエンコーディングを選択します。