标签: huffman-code

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

关于生成霍夫曼树的快速教程

对霍夫曼树感到困惑.在上面的链接的末尾附近,它显示剩下2个元素的树,然后是完成的树.我对它的分支方式感到困惑.霍夫曼树需要分支的特定方式吗？

例如,57:*及其右子35:*分支到右侧.它可能是35分支到左边,22分支到右边？另外,为什么不是22:*与15:4配对 - 它只是与20:5配对以创建一棵新树.

从最初的观察看来,除了叶子的频率加起来父节点的值之外,树似乎不需要平衡或具有任何特定顺序.创建具有相同数据的霍夫曼树的两个人最终会得到不同的编码值吗？

我听说Jpeg使用的是Hufman代码.什么是霍夫曼代码？

我在想一个像

takeChunkUntil :: [a] -> ([a] -> Bool) -> ([a], [a])

希望偷懒。

它从第一个列表中取出元素，直到它们中的一组满足谓词，然后返回该子列表以及其余元素。

解答一些问题：
最终目标是使某些东西可以懒惰地读取Huffman代码。因此，如果您有一串字符串（在此表示为Bool，）bs，则可以编写代码take n $ decode huffmanTree bs以获取前n个编码值，同时仅消耗bs必要的数量。如果您愿意，我会发布更多详细信息和尝试的解决方案。这可能会很长：)（请注意，我是一位学生给这个问题的辅导老师，但我没有试图帮助他，因为这超出了我，但是我现在很好奇。）

续：整个过程在这里：

霍夫曼树的定义：

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

目标：编写一个懒惰的解码函数，该函数返回一对解码后的值和一个布尔值，指示是否有剩余的值不够长而无法解码为一个值。注意：我们使用布尔来表示：True = 1，False = 0。

decode :: BTree a -> [Bool] -> ([a], Bool)

这就是本质：我编写的第一个函数是对一个值进行解码的函数。如果输入列表为空，则返回Nothing，否则返回解码值和剩余的“位”。

decode1 :: BTree a -> [Bool] -> Maybe (a, [Bool])
decode1 (Leaf v) bs = Just (v, bs)
decode1 …

我需要能够在压缩的大量文件(.txt)中搜索文本.压缩可以改为其他东西,甚至可以变成专有的.我想避免解压缩所有文件并压缩(编码)搜索字符串并在压缩文件中搜索.这应该可以使用霍夫曼压缩与所有文件的相同码本.我不想重新发明轮子,所以..任何人都知道,做这样的事情或霍夫曼算法实现和测试,或者一个更好的主意库？

提前致谢

在什么条件下,霍夫曼编码使字符串不可压缩？当所有角色以相同的频率/概率出现时？如果是这样,那怎么能证明这是真的呢？

这是瘦的(向下滚动以查看问题):我正在使用Huffman Encoding来压缩文件(对于一个项目).我制作了地图,并将所有内容都变成了一个字符串,如下所示:

00101010001100001110011101001101111011111011

现在,我需要将其转换为实际的二进制字符串,在当前状态下,它只是一个1和0的字符串.

这是问题所在:

1s和0s的字符串长度为17,747,595个字符,它实际上正在减速到550,000左右

这是我的代码:

<?php

$i=0
$len = strlen($binaryString);

while ($i < $len){
    $section = substr($binaryString,$i,$i+8);
    $out .= chr(bindec($section));
    $i=$i+8;
}

?>

如何才能使这个效率足以运行1700万个字符串？

非常感谢您的支持!

我正在研究一个霍夫曼编码程序,我差不多完成但是我陷入无限递归循环.有谁知道这出错了？

这是我得到的错误:

Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:130)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)
at java.io.PrintStream.write(PrintStream.java:476)
at java.io.PrintStream.print(PrintStream.java:619)
at java.io.PrintStream.println(PrintStream.java:756)
at HuffmanNode.buildTree(hw4.java:63)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)

并且输出连续5:1,5:4,5:2,重复

我的数据文件如下所示:

a
a
a
a
d
d
d
d
d
d
d
d
k
k
k
k
k
k
f
f
f
f
f
f
h
h
h
h
h
h
b
b
b
b
b
b
b …

我正在考虑使用霍夫曼代码来压缩文本，但使用可变长度的符号（字符串）。例如（使用下划线作为空格）：

huffman-code | symbol
------------------------------------
00           | _
01           | E
100          | THE
101          | A
1100         | UP
1101         | DOWN
11100        | .
11101        |
1111...
(etc...)

如何构建频率表？显然存在一些重叠问题，序列_TH出现的频率几乎与 一样THE，但在表中毫无用处（_和THE都有短霍夫曼代码）。

这样的算法存在吗？它有一个特殊的名字吗？生成频率表有哪些技巧？我需要对输入进行标记吗？我在文献/网络中没有找到任何内容。（所有这些让我也想到了基数树）。

我正在考虑使用迭代过程：

1. 为长度为 1 到 N 的所有符号生成哈夫曼树
2. 从树中删除所有 N>1 且低于特定计数阈值的符号
3. 重新生成第二棵霍夫曼树，但这次用前一个树对输入进行标记（可能使用基数树进行查找）
4. 重复1直到我们收敛（或几次）

但我不知道如何防止重叠（_THvs THE）的问题。

我刚刚完成了霍夫曼压缩算法的创建。我使用 bytearray() 将压缩文本从字符串转换为字节数组。我正在尝试解压缩我的霍夫曼算法。但我唯一担心的是我无法将字节数组转换回字符串。是否有任何内置函数可以用来将我的字节数组（带有变量）转换回字符串？如果没有，是否有更好的方法将我的压缩字符串转换为其他内容？我尝试使用 byte_array.decode() 并得到以下结果：

print("Index: ", Index) # The Index


# Subsituting text to our compressed index

for x in range(len(TextTest)):

    TextTest[x]=Index[TextTest[x]]


NewText=''.join(TextTest)

# print(NewText)
# NewText=int(NewText)


byte_array = bytearray() # Converts the compressed string text to bytes
for i in range(0, len(NewText), 8):
    byte_array.append(int(NewText[i:i + 8], 2))


NewSize = ("Compressed file Size:",sys.getsizeof(byte_array),'bytes')

print(byte_array)

print(byte_array)

print(NewSize)

x=bytes(byte_array)
x.decode()

UnicodeDecodeError：“utf-8”编解码器无法解码位置 0 中的字节 0x88：起始字节无效