问题标签 [huffman-code]

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

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

而且我知道霍夫曼编码是不可能的。

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

我认为如果你将它写成块，你可以使用任何压缩算法，但理想情况下我不希望一次解压缩整个块。但是，如果您对执行此操作的简单方法以及如何知道块边界有任何建议，请告诉我。如果这是您的解决方案的一部分，请让我知道当您要读取的数据跨越块边界时您会做什么？

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

您如何使用霍夫曼代码（例如 NEED）对单词进行编码

谁能告诉我在java中使用可变长度位字符串解码二进制数据的最佳方法？

例如：

二进制数据为 10101000 11100010 01100001 01010111 01110001 01010110

我可能需要找到以下 01、100、110、1110、1010 中的任何一个的第一个匹配项...

在这种情况下，匹配将是 1010。然后我需要对其余的二进制数据执行相同的操作。位串最长可达 16 位并跨越字节边界。

基本上，我正在尝试使用从标题中的 Huffman 表创建的位字符串对 Huffman 解码 jpeg。我可以做到，只是它非常混乱，我首先将包括二进制数据在内的所有内容都转换为 Stringbuffers，我知道这不是正确的方法。

在我将所有内容加载到字符串缓冲区之前，我尝试只使用二进制数字，但我当然不能忽略像 00011 这样的代码中的前导 0。我确信必须有一些聪明的方法使用位运算符等来做这个，但我一直盯着解释位掩码和左移等的页面，我仍然不知道！

非常感谢您的帮助！

编辑：

感谢所有的建议。我已经采用了二叉树方法，因为它似乎是 Huffman 东西的标准方法。确实有意义，因为霍夫曼代码是使用树创建的。我还将研究存储需要在大整数中搜索的二进制数据。不知道如何将多个答案标记为正确，但同样感谢。

我以为我可以自己解决这个问题，但我似乎根本没有前进。

好的，背景：

我需要根据 jpg 文件中的 FFC4、DHT（定义霍夫曼表）标头提供的信息创建一个霍夫曼代码树。DHT 标头以这种方式定义 Huffman 表：

1) 一系列 16 字节。每个字节定义有多少个符号具有 n 位数的霍夫曼码，其中 n 是字节在序列中的位置。（这有什么意义吗？！！）例如，十六进制的原始数据是：

00 01 05 01 01 01 ... 00

这意味着：

2) 在 16 个字节列表之后是​​实际符号本身。例如：

00 01 02 03 04 05 06 07 08 09 0A 0B

3）结合这两部分我们看到它们是：
00码1位。
01 2 位代码：因此从列表中取出第一个符号：00
05 3 位代码：因此从列表中取出接下来的 5 个符号：01 02 03 04 05
.. 依此类推

4）最后，我们必须从上面的信息中计算出实际的霍夫曼码。如果您是数学天才，您可能已经发现这些代码可以通过简单地为每个新代码以特定位长度递增适当位数的二进制数来计算。当位长增加时，只需增加二进制数，然后将其加倍并继续。当你手工画出许多这样的二叉树时，其他人就会很明显......

5）所以这是我用来计算霍夫曼代码并将它们存储在数组中的代码：（首先我读取1处的数据）并将其放入数组中：dhtBitnum）

一旦我生成了霍夫曼代码并按顺序存储它们，我就可以按照它们在 2) 中出现的顺序添加它们引用的符号。这可能不是非常优雅，但它似乎至少可以工作并创建正确的表。

6）如果有人仍然遵循这一点，你应该得到一枚奖牌。

7) 现在的问题是我想将此信息存储在二叉树中，以便以后可以有效地解码 jpg 图像数据，而不是每次都搜索数组。不幸的是，我无法直接从上述 jpg 标题中提供的信息中找出一种干净有效的方法来执行此操作。
我能想到的唯一方法是首先计算出上面的霍夫曼代码，然后实现一些方法，根据需要创建节点并将符号保存在适当的位置，使用代码作为各种地址。然而，这似乎是一种重复我需要的信息的方式，我相信一定有一个更好、更简单的方法。

8）因此，如果有人理解我的胡言乱语，我将非常感谢您提出一些建议。我意识到这是一个非常具体的问题，但如果没有别的，上面的信息可能对某人有帮助。我对此还是很陌生，所以请原谅我的无知，特别欢迎易于理解的代码！

我正在尝试实现用于压缩的霍夫曼算法，这需要将可变长度的位写入文件。C++ 中是否有任何方法可以将 1 位粒度的可变长度数据写入文件？

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

目前我正在实施两个不同的版本。

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

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

作为与我关于存储霍夫曼树的有效方法的问题相关的后续问题，我想知道搜索二叉树（基于霍夫曼编码输出）和存储到特定节点的路径的最快和最有效的方法是什么.

这是我目前拥有的：

• 将根节点加入队列
• 当队列不为空时，将项目从队列中弹出
  • 检查它是否是我们正在寻找的
    • 是的：跟随一个头指针回到根节点，而在每个节点上我们访问检查它是左还是右并记下它。
    • 跳出搜索
  • 将左右节点入队

由于这是一棵霍夫曼树，我正在寻找的所有条目都将存在。以上是广度优先搜索，这被认为是霍夫曼树的最佳选择，因为源中的项目更频繁地在树中较高以获得更好的压缩，但是我无法找到跟踪的好方法我们如何使用我放在节点中的头指针不回溯就到达特定节点。

在这种情况下，我还以相反的顺序获取所有右/左路径，例如，如果我们从头到根，我们发现从根开始是右、左、左，我们得到左， 左右。或二进制的 001 ，当我正在寻找的是以有效的方式获得 100 时。

还建议将从根到节点的路径存储为节点内的单独值，但是如果我们有一个大于我们为此目的创建的变量可以容纳的位数的树，那么这将崩溃，并且在那点存储数据也会占用大量内存。

我已经使用霍夫曼算法实现了文件压缩，但我遇到的问题是要启用压缩文件的解压缩，使用的编码树或代码本身也应该写入文件。问题是：我该怎么做？在压缩文件的开头编写编码树的最佳方法是什么？

我正在编写一个 C++ 程序来将 BMP 图像转换为 JPEG。

这是我试图遵循的基本算法：

1. 将 RGB 颜色空间转换为 Y,Cb,Cr..
2. 将 Cb 和 Cr 向下采样 2（这意味着对于 2*2 的每个方形块有 4 个不同的 Y 值，但 1 个 Cb 和 1 个 Cr 值
3. 将 DCT 应用于每个 8*8 像素的数据单元...
4. 然后使用标准的 Cb 和 Cr 量化表对 DCT 系数进行量化。
5. 做之字形排序。
6. 使用霍夫曼编码分别对直流和交流系数进行编码。
7. 写入正确的标头并将霍夫曼编码值写入文件...

我已经验证我正确地执行了上述操作，但我仍然遇到以下问题：

• 生成的 JPEG 未正确显示。
• 我制作了一个小的 8*8 24 位（颜色深度）bmp 文件，完全填充了颜色值 R=10 B=10 和 G=100...所有 64 个像素都是相同的颜色..
• 我在每一步得到的数据如下......
  • BMP 标头大小为 40
  • 标头大小 40
  • 宽度 8
  • 身高 8
  • 飞机数量 1
  • 每像素位数 24
  • 图像尺寸 194
  • x 分辨率每米像素 2834
  • y 分辨率每米像素 2834
  • 颜色数 0
  • 小鬼颜色数 0
  • (R,B,G)=(10,10,100)的Y Cb Cr换算为(62,-29,-37)

所以让我们首先考虑 Y 分量。

Y 分量的 DCT 系数为：

在量化之后，对于 Y 分量，我得到的单个数据单元的锯齿形排序是这样的。

现在上述之字形顺序数组的霍夫曼编码为：

• Y直流编码：00111110
• Y ac 编码：1010（对于 ac 霍夫曼表（亮度 Y）EOB 值为 1010）
• Cb和Cr分量的类似哈夫曼编码如下：
• cb直流编码：11000010
• cb ac 编码：01（对于 ac 霍夫曼表（色度 Cb,Cr）EOB 值为 01）
• cr直流编码：110101110
• cr 交流编码：01

• 我得到的最终霍夫曼代码是：

  001111101010110000100111010111001 长度33

所以为了使它能被8整除，填充1就完成了。

这里每个 0 或 1 实际上是一个位，需要按原样存储在 JPEG 文件中，但由于我们不能逐位写入文件，因此总共取 8 位并转换为基数中的整数值10 并存储到一个 1 字节的字符中。

任何人都可以就我哪里出错提供任何建议吗？

对于我正在进行的项目，我需要在 O(n) 空间中实现 Burrows-Wheeler 的 MoveToFront 转换。但是，出于某种原因，我的代码适用于我抛出的大多数值，但不是全部。

我的实现看起来像这样：

关于我在这里做错了什么有什么建议吗？当遇到非字母数字字符时，这似乎不起作用（即编码本身，似乎 /* 等会搞砸）。