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