我正在編寫一種霍夫曼編碼/解碼工具，并且正在尋找一種有效的方法來存儲霍夫曼樹，該樹是為了存儲在輸出文件中而創(chuàng)建的。目前，我正在實現(xiàn)兩個不同的版本。這一步將整個文件逐個字符地讀取到內(nèi)存中，并為整個文檔建立一個頻率表。這將只需要輸出一次樹，因此除了輸入文件很小之外，效率不是什么大問題。我正在使用的另一種方法是讀取大約64 KB的數(shù)據(jù)塊，并對其進行頻率分析，創(chuàng)建樹并對其進行編碼。但是，在這種情況下，在每個塊之前，我都需要輸出我的頻率樹，以便解碼器能夠重建其樹并正確解碼編碼的文件。這是效率的體現(xiàn)，因為我想節(jié)省盡可能多的空間。到目前為止，在我的搜索中，我還沒有找到將樹存儲在盡可能小的空間中的好方法，我希望StackOverflow社區(qū)可以幫助我找到一個好的解決方案！
3 回答
炎炎設(shè)計
TA貢獻1808條經(jīng)驗 獲得超4個贊
由于您已經(jīng)必須實現(xiàn)代碼以按字節(jié)組織的流/文件之上處理按位層，因此這是我的建議。
不要存儲實際頻率，解碼不需要它們。但是，您確實需要實際的樹。
因此，對于每個節(jié)點，從根目錄開始：
如果是葉節(jié)點：輸出1位+ N位字符/字節(jié)
如果不是葉節(jié)點，則輸出0位。然后以相同的方式編碼兩個子節(jié)點（先左后右）
要閱讀，請執(zhí)行以下操作：
讀取位。如果為1，則讀取N位字符/字節(jié)，返回其周圍沒有子節(jié)點的新節(jié)點
如果bit為0，則用相同的方式解碼左右子節(jié)點，并用這些子節(jié)點返回周圍的新節(jié)點，但沒有值
葉節(jié)點基本上是沒有子節(jié)點的任何節(jié)點。
使用這種方法，您可以在編寫輸出之前計算出確切的輸出大小，以判斷增益是否足以證明工作的合理性。假設(shè)您有一個鍵/值對字典，其中包含每個字符的出現(xiàn)頻率，其中頻率是實際出現(xiàn)的次數(shù)。
用于計算的偽代碼：
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
樹大小的計算考慮了葉子節(jié)點和非葉子節(jié)點，并且內(nèi)聯(lián)節(jié)點比字符少一個。
SIZE_OF_ONE_CHARACTER將是位數(shù)，而這兩個位數(shù)將為您提供我的樹+編碼數(shù)據(jù)所占用的位數(shù)。
PATH（c）是一個函數(shù)/表，它將產(chǎn)生從根到樹中該字符的位路徑。
這是一個看起來像C＃的偽代碼，它假定一個字符只是一個簡單的字節(jié)。
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);
}
}
一個示例（簡化，使用屬性等）節(jié)點實現(xiàn)：
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次出現(xiàn)* 2位= 12位
B：1次出現(xiàn)* 3位= 3位
C：6次出現(xiàn)* 2位= 12位
D：2次出現(xiàn)* 3位= 6位
E：5次出現(xiàn)* 2位= 10位
編碼字節(jié)的總和是12 + 3 + 12 + 6 + 10 = 43位
將其添加到樹的49位中，輸出將為92位或12個字節(jié)。將其與存儲未經(jīng)編碼的原始20個字符所需的20 * 8個字節(jié)進行比較，您將節(jié)省8個字節(jié)。
最終的輸出（包括開始的樹）如下。流（AE）中的每個字符都被編碼為8位，而0和1只是一個位。流中的空間僅用于將樹與編碼數(shù)據(jù)分開，并且在最終輸出中不占用任何空間。
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位
數(shù)據(jù)：000001100101110111 = 18位
總和：59 + 18 = 77位= 10字節(jié)
由于原始字符是8個位的7個字符= 56，所以這樣的小數(shù)據(jù)塊會有太多開銷。
慕萊塢森
TA貢獻1810條經(jīng)驗 獲得超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”作為指示符可以重復使用前一個塊的樹。
- 3 回答
- 0 關(guān)注
- 843 瀏覽
添加回答
舉報
0/150
提交
取消