标签: huffman-code

我正在编写一个霍夫曼编码/解码工具,我正在寻找一种有效的方法来存储创建的存储在输出文件内部的霍夫曼树.

目前我正在实施两种不同的版本.

1. 这个文件逐个字符地将整个文件读入内存,并为整个文档构建频率表.这只需要输出一次树,因此除了输入文件很小之外,效率不是很大的问题.
2. 我正在使用的另一种方法是读取一块大小为64千字节的数据,并对其进行频率分析,创建一个树并对其进行编码.但是,在这种情况下,在每个块之前,我将需要输出我的频率树,以便解码器能够重新构建其树并正确解码编码文件.这是效率确实到位的地方,因为我想节省尽可能多的空间.

到目前为止,在我的搜索中,我还没有找到一种在尽可能小的空间中存储树的好方法,我希望StackOverflow社区可以帮助我找到一个好的解决方案!

我被告知霍夫曼编码被用作无损数据压缩算法,但我也被告知真实数据压缩软件不使用霍夫曼编码,因为如果密钥分散不够分散,压缩文件甚至可能比orignal更大文件.

这让我想知道哈夫曼编码是否存在任何实际应用？

什么是允许在文件中随机读/写的最佳压缩算法？

我知道任何自适应压缩算法都是不可能的.

我知道霍夫曼编码是不可能的.

有没有人有更好的压缩算法,允许随机读/写？

我认为你可以使用任何压缩算法,如果你用块写它,但理想情况下我不想一次解压缩整个块.但是,如果您有关于简单方法的建议以及如何知道块边界,请告诉我.如果这是您的解决方案的一部分,请告诉我您想要读取的数据是否跨越块边界时要执行的操作？

在您的答案的上下文中,请假设有问题的文件是100GB,有时我想读取前10个字节,有时我想读取最后19个字节,有时我想阅读17中间的字节..

我有一个编码霍夫曼算法的任务.我把整个问题整理在脑海中,但我在文件处理方面遇到了一些麻烦.

问题是:该算法应该压缩任何类型的文件.

我的解决方案:将文件读取为字节数组,然后使用int array[256]={0}每个字节,获取int n相应的值并递增array[n].如果我没说清楚,请告诉我.

所以,我做了很多研究,但不明白如何从任何类型的文件中获取字节以及如何处理它们.

有人可以帮我弄清楚我在哪里得到这个错误.我知道它可能是双重删除或类似的东西.对于背景,这是霍夫曼树的一个实现,你可以在维基百科上轻松实现.

CharCountNode类实现

int main()
{
  ifstream input;
  input.open("input.txt");

  MinPriorityQueue<CharCountNode> heap;
  map<char, int> m;

  while(input.good())
    m[input.get()] += 1;

  for( map<char, int>::const_iterator it = m.begin(); it != m.end(); ++it )
    heap.enqueue(CharCountNode(it->first, it->second));


  while(heap.getSize() > 1)
  {
    CharCountNode a, b, parent;

    a = heap.dequeue();
    b = heap.dequeue();
    parent = CharCountNode('*', a.getCount() + b.getCount());

    parent.left = &a;
    parent.right = &b;

    heap.enqueue(parent);
  }
}

以下块由Huffman块标记嵌套

-HUFF---------------------------------------------------------------------0084-
  10    0    1    2    4    3    4    6    5    6    8    a    9    4    2    3
   0    1    2   11    0    3    4   21    5   12   31    6   41   51   61   13
  22   71   81   91   a1   14   32   b1   d1   f0   15   23   35   42   b2   c1
   7   16   24   33   52   72   73   e1   25   34   43   53   62   74   82   94
  a2   f1   26   44   54   63   64   92   93   c2   d2   55   56   84 …

我们有一个用霍夫曼编码编码的数据库.这里的目的是在GPU上复制它与相关的解码器; 然后在GPU上解码数据库,并在这个解码的数据库上执行操作,而无需将其复制回CPU上.

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

我的两个问题是:

• 你知道是否存在任何有效的霍夫曼编码GPU版本
• 如果没有,你认为存在一个适用于GPU的霍夫曼算法(即控制结构较少).或许您知道(并且您可以提供参考)有效的霍夫曼解码在GPU上无法有效.

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

我在Windows下使用纯霍夫曼代码实现了一个简单的压缩器.但我不太了解如何快速解码压缩文件,我的错误算法是:

枚举代​​码表中的所有霍夫曼代码,然后将其与压缩文件中的位进行比较.结果是可怕的结果:解压缩3MB文件需要6个小时.

你能提供更高效的算法吗？我应该使用Hash还是什么？

更新:根据我朋友Lin的建议,我已经用状态表实现了解码器.我认为这种方法应该优于travesal huffman tree,6s内3MB.

谢谢.

刚刚构建了一个小型webapp,用于预览生成URL的HTML文档:包含base64编码数据中的HTML(以及所有内联CSS和Javascript).问题是,URL:s很快就会变得有点长.什么是"事实上的"标准方式(最好是通过Javascript)首先压缩字符串而不丢失数据？

PS; 前段时间我在学校读到过Huffman和Lempel-Ziv,我记得很享受LZW :)

编辑:

解决方案; 看起来像rawStr => utf8Str => lzwStr => base64Str是要走的路.我正在进一步努力在utf8和lzw之间实现huffman压缩.到目前为止的问题是,当编码为base64时,太多的字符会变得很长.

我在C中实现了霍夫曼算法.我已经获得了基本功能,直到获得二进制代码字.所以例如,abcd将是100011000或类似的东西.现在的问题是如何在压缩文件中以二进制形式编写此代码.我的意思是如果我正常写它每1和0将是一个字符,所以没有压缩.

我需要用它们的位形式写出1和0.这是可能的C.如果是这样的话怎么样？