4

ハフマン コードを使用してテキストを圧縮することを考えていますが、可変長(文字列) のシンボルを使用します。例 (アンダースコアをスペースとして使用):

huffman-code | symbol
------------------------------------
00           | _
01           | E
100          | THE
101          | A
1100         | UP
1101         | DOWN
11100        | .
11101        |
1111...
(etc...)

頻度表を作成するにはどうすればよいですか? 重複する問題がいくつかあることは明らかです。シーケンス_THは とほぼ同じ頻度で表示されTHEますが、表では役に立ちません ( と の両方_にTHE短いハフマン コードがあります)。

そのようなアルゴリズムは存在しますか？特別な名前はありますか？頻度表を生成するためのトリックは何ですか? 入力をトークン化する必要がありますか? 文献/ウェブには何も見つかりませんでした。（これはすべて、基数ツリーについても考えさせます）。

私は反復プロセスを使用することを考えていました:

  1. 長さが 1 ～ N のすべてのシンボルのハフマン ツリーを生成する
  2. N>1 で特定のカウントしきい値を下回るすべてのシンボルをツリーから削除します
  3. 2 番目のハフマン ツリーを再生成しますが、今回は前のハフマン ツリーで入力をトークン化します (おそらくルックアップに基数ツリーを使用します)。
  4. 収束するまで（または数回）1まで繰り返します

_THしかし、これでオーバーラップ（ vs ）の問題をどのように防ぐことができるかわかりませんTHE。

4

2 に答える 2

3

テキストを適切にトークン化する限り、オーバーラップの問題を心配する必要はありません。各トークンを単語 (最長連続文字列)、句読点記号、または空白文字 (' '、'\t'、\n') として定義できます。したがって、定義上、トークン/シンボルは重複しません。

しかし、ハフマン コーディングを直接使用することは、シンボル間の依存関係を利用できないため、テキストの圧縮には理想的ではありません。たとえば、「q」の後には「u」が続く可能性が高く、「qu」の後には母音が続く可能性が高く、「thank」の後には「you」が続く可能性が高いなどです。データを一連のルックアップ アドレス、コピー長、および逸脱シンボルに変換することで、この冗長性を利用できる「LZ」のような高次エンコーダを調べることができます。LZ がどのように機能するかの例を次に示します。その後、3 つのストリームのそれぞれにハフマン コーディングを適用して、データをさらに圧縮できます。DEFLATEアルゴリズムはまさにこのように機能します。

于 2014-09-06T15:33:59.807 に答える
1

これは完全な解決策ではありません。

シーケンスとルックアップ テーブルの両方を格納する必要があるため、ストレージ コストを最小限に抑えるシンボルを貪欲に選択できる可能性があります。

ステップ 1: 長さが最大 ​​k のすべてのシンボルを試しに格納し、それらのカウントを追跡する

ステップ 2: 可能性のあるシンボルごとに、節約されるスペース (または圧縮率) を計算します。

Encode_length(symbol) = log(N) - log(カウント(シンボル))

Space_saved(symbol) = length(symbol)*count(symbol) - Encode_length(symbol)*count(symbol) - (length(symbol)+Encode_length(symbol))

N は、すべてのシンボルの合計頻度です (まだわかりませんが、おおよその値でしょうか?)。

ステップ 3: 最適なシンボルを選択し、それと重複する他のシンボルの周波数を減算します。

ステップ 4: シーケンス全体がまだエンコードされていない場合は、次の最適なシンボルを選択します (つまり、ステップ 2 に進みます)。

注: これは単なる概要であり、完全でもなく、計算上も効率的ではありません。実用的な迅速な解決策を探している場合は、krjampani の解決策を使用する必要があります。この答えは純粋に学術的なものです。

于 2014-09-06T15:40:45.000 に答える