データ圧縮のためにハフマン ツリーを効率的に保存するにはどうすればよいですか?

データ圧縮のための効率的なハフマン ツリー ストレージ

ハフマン エンコーディングは、より頻繁な文字に短いコードを割り当てることでデータを最適化します。構築したハフマン木を保存するには、さまざまな手法が存在します。

ツリーサイズを最小化する方法

入力データが小さい場合、効率とオーバーヘッドの間にはトレードオフが存在します。 。より大きなデータセットの場合は、次の方法を検討してください:

• 頻度を保存しない。

• 各ノードの場合:

  • リーフ ノードの場合、1 ビットを出力し、その後に文字/バイト (N ビット) が続きます。
  • リーフ ノードでない場合は、0 ビットを出力し、両方の子ノードを再帰的にエンコードします。

デコード手順:

• ビットを読み取ります。
• 1 の場合、N ビット文字/バイトを読み取り、リーフ ノードを作成します。
• 0 の場合、左右の子ノードを再帰的に読み取ります。

例

入力「AAAABCCCCCCDDEEEEE」を考えます。

• ツリー:

              20
      ----------
      |        8
      |     -------
      12     |     3
  -----   |   -----
  A   C   E   B   D
  6   6   5   1   2

• パス:

  • A: 00
  • B: 110
  • C: 01
  • D: 111
  • E: 10

• エンコードされた出力:

  • ツリー: 001A1C01E01B1D (49 ビット)
  • データ: 00000000000011001010101010111111101010101 (43 ビット)
  • 合計: 92 ビット (12 バイト)

比較

ハフマン エンコードなし:

• 20 文字 * 8 ビット = 160 ビット (20 バイト)

ハフマン エンコードあり:

• 12 バイトのオーバーヘッド

小さなデータに関する考慮事項

小さな入力データの場合は、周波数を保存するアプローチが考えられます。よりスペース効率が高くなります。計算:

• ツリー サイズ = 10 * 文字数 - 1
• エンコード サイズ = 合計(各文字の頻度 * 文字へのパスの長さ)

このアプローチにより、スペースが無駄になる可能性が最小限に抑えられます。

以上がデータ圧縮のためにハフマン ツリーを効率的に保存するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。