algorithm - 有没有可能在GPU中实现哈夫曼解码？

Question

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

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

我的两个问题是:

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

我看到了其他约束，但它们并不重要: - GPU 处理树的效率不是很高:二叉树可以存储在经典数组中 - 工作量可能难以平衡:我们会在之后看到

Answer 1

霍夫曼编码的问题是你不能快进。即:您必须线性地逐位解码。

因此它不是并行的理想选择。

如果您可以决定编码，您可以完美地逐 block 编码，以便能够独立解码每个 block 。