标签: huffman-code

我正在开发一个文件压缩程序.我们目前正在实现.ZIP archiver standart,这样当生成压缩的.ZIP归档器时,任何其他信誉良好的压缩器(如7zip)都可以完全理解/解压缩它.

我们现在正在开发基于RFC 1951的DEFLATE算法
我们有LZ77的变体和具有固定代码的霍夫曼编码完美地兼容RFC,因此使用Literal-Length + Distance值.

关于动态霍夫曼编码我目前能够从一些压缩数据中提取霍夫曼树(通过另一个可靠的压缩器压缩),但是当它开始解压缩真实数据时,我得到的值不正确.
可能我正在以错误的方式读树.

我没有具体地找到任何人正确解释这些树的值存储在压缩数据上的方式.

我假设编码数据遵循相同的文字长度值(0~285)+距离(0~30)及其相应的每字节/距离的额外比特,如RFC中所解释的那样,固定霍夫曼编码的方式相同.

这种存储在固定霍夫曼编码上的方式是将霍夫曼代码与代码中最高有效位存储在存储器中的最低有效位上.通过这种方式,您可以逐位向下导航编码树.霍夫曼代码的
额外位以相反的方式存储.

动态霍夫曼编码是否以相同的方式存储它们？

有什么我缺少的或我应该知道的吗？

我已经压缩了一个binary file使用Huffman encoding. 现在我试图找到compression efficiency.

在我的二进制文件中，我有符号（0 和 1 的一堆）和频率（符号的重复）。假设我有：

symbol :0 freq : 173
symbol :1 freq : 50
symbol :2 freq : 48
symbol :3 freq : 45 

文件大小为 (173+50+48+45)*8= 2528（如果我计算大小的方式正确？如果我错了，请纠正我。（在调试时我得到 2536）（还有 8 个我不知道知道为什么 ？）

压缩后我得到encoding这样的

symbol : 0 Code : 1
symbol : 1 Code : 00
symbol : 2 Code : 011
symbol : 3 Code : 010

有人可以告诉我如何使用这些信息获得这个二进制文件的霍夫曼压缩效率吗？（我尝试在谷歌上搜索，但没有二进制文件的样本，它们有一些浮点类型的频率，我无法理解如何将它们与我的二进制文件相关联）。非常感谢。这样做的算法（c/c++/c#）也很受欢迎。

我想知道我们可以在多大程度上进行无损数据压缩；我无法找到无损算法的在线模拟器来执行一些经验测试。我可以自己做一个，但不幸的是我这段时间没有足够的时间；我仍然对我的直觉很好奇，我将对此进行解释。

让我们仅采用两种更流行的算法：Huffman Coding和Run-lenght Enconding。

假设我们有一个数字A符号的字母表和来自该字母表的任意长的符号序列：例如：

Alphabet  = {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, X, W, Y, Z}
Sequence1 =  SFBJNERUSNJGSDKKDEIJGNMSDJDDSUSJNF
Sequence2 =  MNMNMNREGUHSDFJUF
Sequence3 =  MMMMMNNNNNASDUERJGASIUJMMMNNNUNS

现在，如果我们只用一个固定长度的n比特字对每个符号进行编码，我们就会得到未压缩的序列，即长N比特。

如果我们使用 Huffman 编码一个序列，我们将使用H位而不是N位，从而节省(1-H/N)*100%位空间。

如果我们使用 RLE 编码相同的序列，我们将使用R位，节省(1-R/N)*100%.

我想知道，如果我们申请RLE + Huffman或者Huffman + RLE我们可以比仅使用其中之一节省更多空间会发生什么。

对我来说，这似乎是一个非常基本的想法，但是在谷歌上搜索我没有找到关于这个主题的任何有趣的东西。

编辑： …

构建霍夫曼树输入的步骤是独特字符的数组以及它们的出现频率和输出是霍夫曼树.

1. 为每个唯一字符创建一个叶节点,并构建所有叶节点的最小堆(Min Heap用作优先级队列.频率字段的值用于比较最小堆中的两个节点.最初,最不频繁的字符位于根)

2. 从最小堆中提取具有最小频率的两个节点.

3. 创建一个频率等于两个节点频率之和的新内部节点.将第一个提取的节点作为其左子节点,将另一个提取的节点作为其右子节点.将此节点添加到最小堆.

4. 重复步骤#2和#3,直到堆只包含一个节点.其余节点是根节点,树已完成.

在堆中,一个节点最多可以有2个子节点,对吧？

因此,如果我们想对三元系统中的编码字(即使用符号0,1和2的编码字)推广霍夫曼算法,我们能做什么？我们是否必须创建一个树,其中所有节点都有3个子节点？

编辑:

我认为它会如下.

构建霍夫曼树输入的步骤是独特字符的数组以及它们的出现频率和输出是霍夫曼树.

1. 为每个唯一字符创建一个叶节点,并构建所有叶节点的最小堆

2. 从最小堆中提取具有最小频率的三个节点.

3. 创建一个频率等于三个节点频率之和的新内部节点.将第一个提取的节点作为其左子节点,将第二个提取的节点作为其中间子节点,将第三个提取的节点作为其右子节点.将此节点添加到最小堆.

4. 重复步骤#2和#3,直到堆只包含一个节点.其余节点是根节点,树已完成.

我们如何证明该算法产生最优的三元码？

编辑2:假设我们的频率为5,9,12,13,16,45.

它们的数量是偶数,所以我们添加一个频率为0的虚节点.我们把它放在数组的末尾吗？那么,它会如下吗？

那么我们会有以下堆吗？

然后:

然后:

或者我明白错了？

我正在写一个Huffman文件,我在那里将规范代码的代码长度存储在文件的标题中.在解码过程中,我能够重新生成规范代码并将它们存储到一个std::map<std:uint8_it, std::vector<bool>>.实际数据被读入单个数据std::vector<bool>.在任何人建议我使用之前std::bitset,让我澄清一下,霍夫曼代码的位长可变,因此,我正在使用std::vector<bool>.所以,鉴于我有我的符号和相应的规范代码,我如何解码我的文件？我不知道从哪里开始.有人可以向我解释我如何解码这个文件,因为我在搜索时找不到与之相关的任何内容.

我对这个问题的希望（参见底部）希望对我的放气过程进行尽可能多的布置，并且我可以（可能非常）误解了我所在的领域。希望最后，这个问题可以成为一个方便的资源。

Zlib标头

前两个字节等于zlib压缩的标头，格式为（credit）

---CMF---  ---FLG---
0111.1000  1101.0101
CINF -CM-  +-||
           | |+- FCHECK
           | +-- FDICT
           +---- FLEVEL

从RFC 1950开始，从右到左：

1. FCHECK（1.0101）-验证CMF和FLG为16位无符号整数是31的倍数

2. FDICT（0）-如果设置，表示在FLG之后紧随其后的预设DICT

3. FLEVEL（11）-压缩“强度” [0-3]

4. CM（1000）-用于压缩方法，其中CM = 8 ==“放气”压缩方法

5. CINF（0111）-指示使用的滑动窗口的大小，其中CINF = 7 == 32K滑动窗口

数据块头

NEW BYTE中的后三位等于霍夫曼编码块的标头：

---CMF---  ---FLG---  NEW BYTE
0111.1000  1101.0101  11101100
                           |-|
                           | +- BFINAL
                           +--- BTYPE

从RFC 1951右到左：

1. BFINAL（0）-如果这是最后一个数据块，则设置为（1）

2. BTYPE（10）-霍夫曼编码：（00）无；（01）修正霍夫曼码；（10）动态代码；（11）无效

霍夫曼密码

从这里开始，我将假设BTYPE =（10）

下列值会立即进行：

NEW BYTE                NXT BYTE                  
(11101)100       ->     101)(11101)   ->   0111111(1
       |-|
       | +- BFINAL
       +--- BTYPE

1. HLIT （11101）-5位长度/文字代码，增加了257个（257-286） …

所以我制作了一个应该进行霍夫曼编码的程序.将我的答案与正确答案进行比较时,并非所有答案都匹配.

我有

[("a","0"),("c","100"),("b","101"),("d","110"),("f","1110"),("e","1111")]

正确的答案是

[('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]

正确的树是

然而我的方法给了我一点点改变.在分支30上,我使用0来到D而不是1.

所以这让我想知道,这两个答案都是正确的吗？毕竟他们都有相同的字符串长度.

如果我错了,有人可以解释原因吗？

如果有人想要它,我的代码是在下面的Haskell中编写的

mergHufffman::(String,Int) -> (String,Int) -> (String,Int)
mergHufffman x y =  (fst x ++ fst y, snd x + snd y)

data HTree a = Leaf a | Branch (HTree a) (HTree a) deriving Show

treeHuff::[(String,Int)] -> HTree (String,Int)
treeHuff (x:[]) = Leaf x
treeHuff (x:y:[])
        | snd x < snd y = Branch (Leaf x) (Leaf y)
        | snd x > snd y = Branch (Leaf y) (Leaf x)
treeHuff (x:y:z:list) …

我使用Huffman算法创建了一个Python脚本来压缩文本。说我有以下字符串：

string = 'The quick brown fox jumps over the lazy dog'

运行我的算法将返回以下“位”：

result = '01111100111010101111010011111010000000011000111000010111110111110010100110010011010100101111100011110001000110101100111101000010101101110110111000111010101110010111111110011000101101000110111000'

通过将结果的位数与输入字符串进行比较，该算法似乎有效：

>>> print len(result), len(string) * 8
194 344

但是现在出现了一个问题：如何将其写入文件，同时仍然能够对其进行解码。您只能按字节而不是按位写入文件。通过将“代码”写为字节，根本就没有压缩！

我是计算机科学的新手，而在线资源对我来说并不有用。非常感谢所有帮助！

编辑：请注意，我的代码是这样的（在另一个输入字符串的情况下'xxxxxxxyzz'）：

{'y': '00', 'x': '1', 'z': '10'}

我创建结果字符串的方式是按照输入字符串的顺序将这些代码串联起来：

result = '1111111001010'

如何从该结果返回到原始字符串？还是我完全错了？谢谢！

当我们使用霍夫曼编码方法进行编码时，我们是否也应该考虑空格？

我正在尝试学习Haskell，但发现它确实很困难，并且在线资源并不多。我似乎对递归调用的外观有一些基本的了解，希望将其指向正确的方向。我正在尝试插入一棵树，并返回每个叶节点（其中存储了符号）以及到达那里的路径。（因此输入（Fork（Leaf x）（Leaf y））将具有输出[[x，[False]），（y，[True]）]）。我的代码如下所示：

data htree a = Leaf a | Fork (htree a) (htree a) deriving (Show, Eq)

encode :: htree a -> [(a, [Bool])]
encode (Leaf a) = [(a, ????)]

我知道这没什么不值得的。我已经确定了基本情况，即到达叶子时，返回存储在叶子处的符号以及到达那里的路径。左为假，右为真。我不确定如何将所有这些信息放在一起以继续我的代码。我会在这里提供任何形式的指导。