我正在编写一种霍夫曼编码/解码工具，并且正在寻找一种有效的方法来存储霍夫曼树，该树是为了存储在输出文件中而创建的。目前，我正在实现两个不同的版本。这一步将整个文件逐个字符地读取到内存中，并为整个文档建立一个频率表。这将只需要输出一次树，因此除了输入文件很小之外，效率不是什么大问题。我正在使用的另一种方法是读取大约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
因此要计算输出大小：
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
提交
取消