python - 霍夫曼树中的唯一标识符节点

Question

我正在构建一个Python程序来使用霍夫曼树压缩/解压缩文本文件。以前，我会将频率表存储在压缩文件旁边的 .json 文件中。当我读入压缩数据和.json时，我会从频率表重建解压树。我认为这是一个非常 Eloquent 解决方案。

但是，我遇到了一个奇怪的问题，即中等长度的文件会解压缩成看似随机的字符串。我发现当两个字符出现相同次数时就会出现问题。当我重建我的树时，任何具有匹配频率的字符都有机会被交换。对于大多数文件，特别是大文件和小文件，这不是问题。大多数字母的出现次数比其他字母稍多或稍少。但对于一些中等大小的文件，很大一部分字符与另一个字符出现的次数相同，从而导致乱码。

我的节点是否有一个唯一的标识符，我可以使用它来轻松重建我的树？或者我应该以完全不同的方式来处理树的写作？

Answer 1

1. 在霍夫曼算法中，您需要以两侧相同的确定性方式选择最低的两个频率。如果出现平局，则需要使用该符号来打破平局。否则，您无法保证两侧的排序在面对相同频率时会选择相同的符号。

2. 您不需要发送频率。您需要发送的只是符号的位长度。长度的编码比频率的编码要紧凑得多。您可以构建一个canonical code仅从长度出发，使用符号明确地对代码进行排序。