我正在編寫一種霍夫曼編碼/解碼工具，并且正在尋找一種有效的方法來存儲霍夫曼樹，該樹是為了存儲在輸出文件中而創建的。目前，我正在實現兩個不同的版本。這一步將整個文件逐個字符地讀取到內存中，并為整個文檔建立一個頻率表。這將只需要輸出一次樹，因此除了輸入文件很小之外，效率不是什么大問題。我正在使用的另一種方法是讀取大約64 KB的數據塊，并對其進行頻率分析，創建樹并對其進行編碼。但是，在這種情況下，在每個塊之前，我都需要輸出我的頻率樹，以便解碼器能夠重建其樹并正確解碼編碼的文件。這是效率的體現，因為我想節省盡可能多的空間。到目前為止，在我的搜索中，我還沒有找到將樹存儲在盡可能小的空間中的好方法，我希望StackOverflow社區可以幫助我找到一個好的解決方案！
3 回答
炎炎設計
TA貢獻1808條經驗 獲得超4個贊
由于您已經必須實現代碼以按字節組織的流/文件之上處理按位層，因此這是我的建議。
不要存儲實際頻率，解碼不需要它們。但是，您確實需要實際的樹。
因此，對于每個節點，從根目錄開始：
如果是葉節點：輸出1位+ N位字符/字節
如果不是葉節點，則輸出0位。然后以相同的方式編碼兩個子節點（先左后右）
要閱讀，請執行以下操作：
讀取位。如果為1，則讀取N位字符/字節，返回其周圍沒有子節點的新節點
如果bit為0，則用相同的方式解碼左右子節點，并用這些子節點返回周圍的新節點，但沒有值
葉節點基本上是沒有子節點的任何節點。
使用這種方法，您可以在編寫輸出之前計算出確切的輸出大小，以判斷增益是否足以證明工作的合理性。假設您有一個鍵/值對字典，其中包含每個字符的出現頻率，其中頻率是實際出現的次數。
用于計算的偽代碼：
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
樹大小的計算考慮了葉子節點和非葉子節點，并且內聯節點比字符少一個。
SIZE_OF_ONE_CHARACTER將是位數，而這兩個位數將為您提供我的樹+編碼數據所占用的位數。
PATH（c）是一個函數/表，它將產生從根到樹中該字符的位路徑。
這是一個看起來像C＃的偽代碼，它假定一個字符只是一個簡單的字節。
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
頻率：
答：6
B：1
C：6
D：2
E：5
每個字符只有8位，因此樹的大小將為10 * 5-1 = 49位。
這棵樹可能看起來像這樣：
20
----------
| 8
| -------
12 | 3
----- | -----
A C E B D
6 6 5 1 2
因此，每個字符的路徑如下（左為0，右為1）：
A：00
乙：110
C：01
D：111
E：10
因此要計算輸出大?。?/p>
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只是一個位。流中的空間僅用于將樹與編碼數據分開，并且在最終輸出中不占用任何空間。
001A1C01E01B1D 0000000000001100101010101011111111010101010
對于注釋中包含的具體示例AABCDEF，您將獲得以下信息：
輸入：AABCDEF
頻率：
A2
B：1
C：1
D：1
E：1
F：1
樹：
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1
路徑：
A：00
B：01
C：100
D：101
E：110
傳真：111
樹：001A1B001C1D01E1F = 59位
數據：000001100101110111 = 18位
總和：59 + 18 = 77位= 10字節
由于原始字符是8個位的7個字符= 56，所以這樣的小數據塊會有太多開銷。
慕萊塢森
TA貢獻1810條經驗 獲得超4個贊
樹枝是0，樹葉是1。首先遍歷樹的深度以獲取其“形狀”
e.g. the shape for this tree
0 - 0 - 1 (A)
| \- 1 (E)
\
0 - 1 (C)
\- 0 - 1 (B)
\- 1 (D)
would be 001101011
緊隨其后的是具有相同深度一階AECBD的字符的位（閱讀時，您將知道從樹的形狀中期望有多少個字符）。然后輸出該消息的代碼。然后，您將獲得一連串的比特，可以將其劃分為多個字符以進行輸出。
如果要對其進行分塊，則可以測試存儲樹以供下一個卡盤使用，就像重新使用前一個塊的樹一樣有效，并且樹形為“ 1”作為指示符可以重復使用前一個塊的樹。
添加回答
舉報
0/150
提交
取消