问题标签 [huffman-code]

我们有一个用霍夫曼编码编码的数据库。这里的目的是在 GPU 上复制它及其相关的解码器；然后在 GPU 上，解码数据库并在这个解码的数据库上做一些事情，而不是在 CPU 上复制回来。

我远不是霍夫曼专家，但我知道的少数人表明它似乎是一种基本上基于控制结构的算法。有了基础算法，恐怕会出现很多序列化的操作。

我的两个问题是：

• 你知道是否存在任何用于霍夫曼编码的高效 GPU 版本
• 如果没有，您认为是否存在适用于 GPU 的 Huffman 算法（即控制结构较少）。或者您可能知道（并且您可以提供参考）高效的霍夫曼解码在 GPU 上效率不高。

我看到了其他限制，但它们并不重要： - GPU 无法非常有效地处理树：二叉树可以存储在经典数组中 - 工作负载可能难以平衡：我们稍后会看到

从我的算法教科书：

一年一度的县赛马将带来三匹从未相互竞争过的纯种马。兴奋地，你研究了他们过去的 200 场比赛，并将这些总结为四个结果的概率分布：第一（“第一名”）、第二、第三和其他。

哪匹马最容易预测？解决这个问题的一种定量方法是查看可压缩性。将每匹马的历史记录为一串 200 个值（第一、第二、第三、其他）。然后可以使用霍夫曼算法计算对这些跟踪记录字符串进行编码所需的总比特数。这适用于 Aurora 290 位，Whirlwind 380 位，Phantasm 420 位（检查一下！）。Aurora 具有最短的编码，因此在强烈的意义上是最可预测的。

他们是如何获得 420 的 Phantasm 的？我不断收到 400 个字节，如下所示：

结合第一，其他 = 0.4，结合第二，第三 = 0.6。最终以 2 位编码每个位置。

我对霍夫曼编码算法有什么误解吗？

此处提供教科书：http ://www.cs.berkeley.edu/~vazirani/algorithms.html （第 156 页）。

对于一个项目，我必须将二进制字符串转换为（一个数组）字节并将其写入二进制文件。

假设我有一个句子使用霍夫曼编码转换为代码字符串。例如，如果句子是：“你好” h = 00 e = 01, l = 10, o = 11

那么字符串表示将是 0001101011。

我如何将其转换为字节？<-- 如果这个问题没有意义，那是因为我对位/字节按位移位以及所有与操作 1 和 0 有关的知识知之甚少。

这是我在学校环境中遇到的一个问题，但它一直困扰着我，所以我决定在这里问它。

在霍夫曼压缩中，固定长度的序列（字符）用可变长度的序列编码。代码序列长度取决于源字符的频率（或概率）。

我的问题是：最低最高字符频率是多少，该字符将用一位编码？

在我的 C++ 数据结构基础 教科书中，它给出了霍夫曼编码的 2 页定义，以及上面的代码。对我来说，这本书不够详细，所以我做了谷歌搜索，了解了霍夫曼编码的过程。教科书声称在上面的代码末尾，生成了一个霍夫曼树。但对我来说这似乎是错误的，因为霍夫曼树不一定是完整的树，但上面的代码似乎总是给出完整的树，因为heap.push(). 那么有人可以向我解释这段代码如何没有错吗？

我正在尝试通过读取文件并计算每个字母空格符号的频率等来创建霍夫曼树。我正在使用优先队列将项目从最小到最大排队但是当我将它们插入队列时它们没有正确排队这是我的代码。包霍夫曼；

导入 java.io.FileNotFoundException；导入 java.io.FileReader；导入 java.util.ArrayList；导入 java.util.PriorityQueue；导入 java.util.Scanner；

公共类霍夫曼{

}

在 buildTree() 方法中是我遇到问题的地方。我试图做的是队列频率对象，其中包含字母/空格/符号和频率作为频率类是这样的。公共类频率实现 Comparable { private String s; 私人诠释 n;

}

我怎样才能让优先队列使用频率数将它们从最小到最大排队？

我之前问过的我的霍夫曼树还有另一个问题！这是代码：

现在需要做的是我需要创建一个方法来搜索树以找到特定字符的二进制代码（011001 等）。做这个的最好方式是什么？我想也许我会在树中进行正常搜索，就好像它是一棵 AVL 树，如果它更大则向右移动，如果它更小则向左移动。

但是因为节点不使用整数双精度等，而仅使用包含字符作为字符串或 null 的对象来表示它不是叶子，而只是根。另一种选择是按顺序运行以找到我正在寻找的叶子，但同时我将如何确定我是向右走这么多次还是离开这么多次来获得角色。

我正在尝试做的是找到实际获取每个字符的二进制代码。因此，如果我试图编码aabbbcccc我将如何创建一个字符串来保存二进制代码，左转为 0，右转为 1。

让我感到困惑的是，您无法确定任何东西在哪里，因为树显然不平衡，并且无法确定角色是在您所在位置的右侧还是左侧。所以你必须搜索整棵树，但如果你找到一个不是你要找的节点，你必须回溯到另一个根才能找到其他叶子。

嗨，我试图弄清楚如何递归搜索树以查找字符和二进制代码以获取该字符。基本上目标是找到字符的代码，然后将其写入文件。文件编写器部分我可以做没有问题，但真正的问题是将二进制代码放入字符串中。当我在寻找角色时。请帮忙！

这是递归方法的代码：

这是频率类：

公共类频率实现 Comparable { private String s; 私人诠释 n; 公共频率离开；公共频率权；私有字符串双数；私有字符串叶；

}

我一直在研究这个霍夫曼树生成器：

代码试图做的英语是

将所有字符及其频率添加到优先级队列中，从最低频率到最高频率。接下来为 ArrayList al 的大小（包含所有字符）将前两个出列然后设置一个新根以具有左右子节点，它们是出列的 2 个节点，然后插入具有 2 个出列的组合频率的新根项目进入优先队列。这就是方法应该做的所有事情。

这种方法应该构建霍夫曼树，但它构建不正确我已经按照代码手动构建了树，但我在纸上得到的与程序不同！由不同程序生成的正确答案与我的解决方案不同。输入数据（字母和频率）是：

至于我从中读取的文本无关紧要，因为频率已经在这里了。我需要做的 2 就是从这些频率构建树。

我正在研究一棵霍夫曼树，并且试图弄清楚如何遍历树以找到具有我正在寻找的字符的节点。在搜索树时，我需要使用 1 和 0（0 左 1 右）保留通往我正在寻找的节点的路径字符串。我怎样才能做到这一点？