哈夫曼树中的唯一标识符节点

Question

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

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

有没有我的节点的唯一标识符，我可以用它来轻松地重建我的树？或者，我是否应该完全不同地接近树的写作？

Answer 1

1. 在霍夫曼算法中，你需要以确定性的方式选择最低的两个频率，两边是相同的。如果有领带，你需要使用符号来打破领带。没有这一点，你不能保证在面对相同的频率时，两边的排序会选择相同的符号。

2. 您不需要发送频率。您需要发送的是符号的位长。长度可以比​​频率更紧凑地编码。您可以根据长度建立一个canonical code，使用符号明确地排列代码。