バイト編成のストリーム/ファイルの上にビット単位のレイヤーを処理するコードを既に実装する必要があるため、ここに私の提案があります。
実際の周波数は保存しないでください。デコードには必要ありません。ただし、実際のツリーは必要です。
したがって、各ノードについて、ルートから開始します。
- リーフノードの場合: 1 ビット + N ビットの文字/バイトを出力
- リーフノードでない場合は、0 ビットを出力します。次に、両方の子ノード (左が先、次に右が先) を同じ方法でエンコードします。
読むには、次のようにします。
- ビットを読み取ります。1 の場合、N ビットの文字/バイトを読み取り、その周りに子を持たない新しいノードを返します
- ビットが 0 の場合、左右の子ノードを同じ方法でデコードし、それらの子を含むそれらの周りの新しいノードを返しますが、値は返しません。
リーフノードは基本的に、子を持たないノードです。
このアプローチを使用すると、出力を書き込む前に出力の正確なサイズを計算して、努力を正当化するのに十分な利益があるかどうかを判断できます。これは、各文字の頻度を含むキーと値のペアの辞書があることを前提としています。ここで、頻度は実際の出現回数です。
計算用の擬似コード:
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
ツリー サイズの計算では、リーフ ノードと非リーフ ノードが考慮され、インライン ノードは文字数よりも 1 つ少なくなります。
SIZE_OF_ONE_CHARACTER はビット数であり、これらの 2 つは、ツリーに対する私のアプローチ + エンコードされたデータが占有する合計ビット数を示します。
PATH(c) は、ルートからツリー内のその文字までのビットパスを生成する関数/テーブルです。
これを行うための C# 風の疑似コードを次に示します。これは、1 文字が単純なバイトであることを前提としています。
void EncodeNode(Node node, BitWriter writer)
{
if (node.IsLeafNode)
{
writer.WriteBit(1);
writer.WriteByte(node.Value);
}
else
{
writer.WriteBit(0);
EncodeNode(node.LeftChild, writer);
EncodeNode(node.Right, writer);
}
}
読み返すには:
Node ReadNode(BitReader reader)
{
if (reader.ReadBit() == 1)
{
return new Node(reader.ReadByte(), null, null);
}
else
{
Node leftChild = ReadNode(reader);
Node rightChild = ReadNode(reader);
return new Node(0, leftChild, rightChild);
}
}
例 (簡略化、プロパティの使用など) ノードの実装:
public class Node
{
public Byte Value;
public Node LeftChild;
public Node RightChild;
public Node(Byte value, Node leftChild, Node rightChild)
{
Value = value;
LeftChild = leftChild;
RightChild = rightChild;
}
public Boolean IsLeafNode
{
get
{
return LeftChild == null;
}
}
}
特定の例からの出力例を次に示します。
入力: AAAAAABCCCCCCDDEEEEE
周波数:
各文字はわずか 8 ビットなので、ツリーのサイズは 10 * 5 - 1 = 49 ビットになります。
ツリーは次のようになります。
20
----------
| 8
| -------
12 | 3
----- | -----
A C E B D
6 6 5 1 2
したがって、各文字へのパスは次のようになります (0 が左、1 が右)。
- あ：00
- 乙：110
- 子：01
- D:111
- え：10
したがって、出力サイズを計算するには:
- A: 6 オカレンス * 2 ビット = 12 ビット
- B: 1 オカレンス * 3 ビット = 3 ビット
- C: 6 オカレンス * 2 ビット = 12 ビット
- D: 2 オカレンス * 3 ビット = 6 ビット
- E: 5 回 * 2 ビット = 10 ビット
エンコードされたバイトの合計は 12+3+12+6+10 = 43 ビット
これをツリーの 49 ビットに追加すると、出力は 92 ビットまたは 12 バイトになります。これを、エンコードされていない元の 20 文字を格納するために必要な 20 * 8 バイトと比較すると、8 バイト節約できます。
最初のツリーを含む最終的な出力は次のとおりです。ストリーム (AE) の各文字は 8 ビットとしてエンコードされますが、0 と 1 は 1 ビットにすぎません。ストリーム内のスペースは、ツリーをエンコードされたデータから分離するためのものであり、最終出力でスペースを占有しません。
001A1C01E01B1D 0000000000001100101010101011111111010101010
コメントにある具体的な例 AABCDEF については、次のようになります。
入力: AABCDEF
周波数:
- あ：2
- B: 1
- 子：1
- D: 1
- え：1
- 女：1
木：
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1
パス:
- あ：00
- 乙：01
- 子：100
- D:101
- え：110
- 女：111
ツリー: 001A1B001C1D01E1F = 59 ビット
データ: 000001100101110111 = 18 ビット
合計: 59 + 18 = 77 ビット = 10 バイト
元は 8 ビットの 7 文字 = 56 だったので、このような小さなデータのオーバーヘッドが大きすぎます。