问题标签 [huffman-code]

我一直在尝试实现一个霍夫曼解码器，由于解码算法的选择不理想，我的初始尝试性能低下。

我以为我尝试使用表查找来实现霍夫曼解码。但是，我有点坚持生成子表，并希望有人能指出我正确的方向。

前缀代码是一组代码，因此没有代码是另一个代码的前缀。例如，以下集合是前缀代码：

与n = 8会员。我认为这些通常是用某种类型的霍夫曼树创建的。

我的问题是：你能帮我创建一个函数来生成一个包含“n”个成员的二进制前缀代码吗？

像这样的东西：

list<int> GenerateBinaryPrefixCodes(int n);

此外，在比特的总和最小化的意义上，要求是“最优的”。

我更喜欢 C/C++/C#/类似的答案。这不是真正的家庭作业，但我这样标记它，因为听起来这将是一个很好的硬件问题。

谢谢！

我在这里尝试了很多不同的东西，但似乎无法让它发挥作用。输入是“abbcccddddeeeee”，它给出了一个频率分别为 1、2、3、4、5 的链表 a、b、c、d、e。

但是，出于某种原因，它似乎根据我运行的许多不同的测试给了我以下树：

如果有人能帮助我，那真是太棒了，我非常非常沮丧。

谢谢！

所以目前我有一个创建霍夫曼树的程序。树由具有以下字段的“Hnodes”组成： 右（指向右孩子） 左（指向左孩子） 代码（整数字符串，理想情况下，0 和 1 将成为该节点的霍夫曼代码） 字符（节点中包含的字符）。

我通过从链表中添加节点来创建霍夫曼树——我知道树是正确创建的。当我创建树时，我告诉节点，当我给它一个父节点时，如果它是父节点的“右”，它的代码字符串是 1，如果左 0。但是显然在创建整个树之后，每个节点都是只会有 0 或 1，但还没有像 00100101 这样的字符串。我的问题是，现在我有了这棵树，我可以遍历它吗？我理解这个想法是给每个孩子它的父母的代码+孩子自己的代码，但我不明白如何遍历树来完成这个。

先感谢您。

我有一个管理大量字符串的应用程序。字符串是类似路径的格式，有很多共同的部分，但没有明确的规则。它们不是文件系统上的路径，但可以这样考虑。我显然需要优化内存消耗，但又不会牺牲很大的性能。

我正在考虑 2 个选项：
- 实现一个compressed_string存储压缩数据的类，但我需要一个固定的字典，我现在找不到这个库。我不想要字节上的霍夫曼，我想要文字上的霍夫曼。
- 在字符串部分实现某种flyweight模式。

这个问题看起来很常见，我想知道最好的解决方案是什么，或者是否有人知道针对此问题的库。

谢谢

我已经使用优先级队列在 Java 中实现了 Huffman 编码算法，其中我从根到叶遍历树，并根据符号在输入中出现的次数将编码示例设为 #=000011。一切都很好，树的构建很好，编码正如预期的那样：但是我得到的输出文件比原始文件大。我目前在遍历树的左节点和右节点时将“0”和“1”附加到字符串。可能我最终使用每个字符的所有 8 位，它对压缩没有帮助。我猜这些位需要转换为字符值。这样这些字符使用的位数少于 8，因此我得到了原始文件的压缩版本。您能否告诉我如何通过在 Java 中操作字符和减少位来实现压缩？谢谢

如何使用霍夫曼确定字符串中固定长度代码的每个字符需要多少位？我有一个想法，你计算一个字符串中不同字符的数量，而不是你在二进制中显示该数字，这样这将是固定长度，但它不起作用。例如，在字符串“letty lotto 喜欢很多棒棒糖”中......除了引号之外有 10 个不同的字符（因为 10 = 0101（4 位），我认为这意味着所有字符都可以用 4 位表示），现在f 的频率为 1，编码为 11111（5 位）而不是 4。

我有以下字符串，我想对其进行霍夫曼编码并有效地存储到一个位数组中：

中符号的频率为sequence：

我将其翻译成霍夫曼代码字典：

然后，我使用 Pythonbitstring包将字符串逐个字符地转换为BitArray类的实例，我称之为bitArray，其中包含用其各自的霍夫曼代码编码的每个字符的位：

这是以字节为单位的位数组：

我必须使用tobytes()而不是bytes，因为我生成的位数组不会均匀地分成 8 位段。

当我计算BitArray表示的存储效率（位数组和输入字符串的大小之比）时，我得到的性能比不编码输入字符串时更差：

我是否正确测量存储效率？（如果我对更长的输入字符串进行编码，这个比率会提高，但它似乎接近 0.28 左右的渐近极限。我想确认这是否是衡量事物的正确方法。）

编辑

以下两种方法产生不同的答案：

我不确定该相信哪个。但是在将数据写入存储的过程中，我认为我需要字节表示，这使我倾向于选择第一个结果。

我正在用 Python 编写一个网络爬虫，它将在 MySQL 数据库中存储大量页面的 HTML 代码。在开始处理数据之前，我想确保我的存储和处理方法是最佳的。我想：

• 最小化数据库中使用的存储空间——可能通过缩小 HTML 代码、霍夫曼编码或其他某种形式的压缩。我想保持全文搜索该字段的可能性 - 我不知道像霍夫曼编码这样的压缩算法是否允许这样做。

• 最大限度地减少编码和存储大量行所需的处理器使用量。

有没有人对此或类似问题有任何建议或经验？鉴于 Python 将需要大量 HTTP 请求和正则表达式以及任何最佳压缩，Python 是否是执行此操作的最佳语言？

所以我需要为我的学校作业编写霍夫曼压缩/解压缩，并且我在使用优先级队列来存储频率时遇到了麻烦。

让我头疼的两个文件是HCNode.hpp和main.cpp. 在HCNode.hpp我重载的文件中bool operator<(const HCNode& other) 以及main.cpp当我尝试初始化这样的优先级队列时：

编译器向我抛出了一堆错误

编辑：这是错误之一

/usr/include/c++/4.6/bits/stl_queue.h:391:9: 从 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = HCNode, _Sequence = std::vector, _Compare = std::less]'<br> compress.cpp:134:59: 从这里实例化

大多数错误似乎来自与图书馆的某种冲突。

没关系，修复了问题，老师的代码不完整。不过感谢那些看过这篇文章的人。