我在C中实现了霍夫曼算法.我已经获得了基本功能,直到获得二进制代码字.所以例如,abcd将是100011000或类似的东西.现在的问题是如何在压缩文件中以二进制形式编写此代码.我的意思是如果我正常写它每1和0将是一个字符,所以没有压缩.
我需要用它们的位形式写出1和0.这是可能的C.如果是这样的话怎么样？
这是我在学校设置中遇到的一个问题,但它一直困扰着我,所以我决定在这里问一下.
在霍夫曼压缩中,固定长度序列(字符)用可变长度序列编码.代码序列长度取决于源字符的频率(或概率).
我的问题是:最小的最高字符频率是多少,该字符将由一个位编码？
我刚刚开始学习文件压缩,我遇到了一些障碍.我有一个应用程序将编码一个字符串,如"程序"作为压缩二进制表示"010100111111011000"(注意这仍然存储为一个字符串).
Encoding
g 111
r 10
a 110
p 010
o 011
m 00
现在我需要使用a将此写入文件系统FileOutputStream,我遇到的问题是,如何将字符串"010100111111011000"转换为要写入文件系统的byte[]/ bytes FileOutputStream？
我之前从未使用过bit/bytes,所以我在这里处于死路.
我制作了jpeg解码器,但我没有实现重启标记逻辑.这就是我的程序无法处理某些图像的原因(例如用Photoshop保存的图像:文件 - >另存为 - > jpeg).我想实现重启标记逻辑,但没有详细的在线解释重启标记逻辑如何工作.请任何人都可以告诉我有关重启标记的更多信息,或者建议我在线资源,我可以在其中详细了解它.谢谢!
对于我的任务,我要对霍夫曼树进行编码和解码.我在创建树时遇到问题,而且卡住了.
不要介意打印语句 - 它们只是供我测试并查看函数运行时的输出.
对于第一个for循环,我从我在主块中用于测试的文本文件中获取了所有值和索引.
在第二个for循环中,我将所有内容插入优先级队列.
我对下一步去哪里感到困惑 - 我正在尝试制作节点,但我对如何进展感到困惑.有人能告诉我,如果我这样做的话吗？
def _create_code(self, frequencies):
'''(HuffmanCoder, sequence(int)) -> NoneType
iterate over index into the sequence keeping it 256 elements long, '''
#fix docstring
p = PriorityQueue()
print frequencies
index = 0
for value in frequencies:
if value != 0:
print value #priority
print index #elm
print '-----------'
index = index + 1
for i in range(len(frequencies)):
if frequencies[i] != 0:
p.insert(i, frequencies[i])
print i,frequencies[i]
if p.is_empty():
a = p.get_min()
b = p.get_min()
n1 …我一直在尝试将这段代码移植到python中,但是我在C++中有一些我不太了解的东西(我确实知道一些C++,但这超出了我的范围):
typedef struct huffnode_s
{
struct huffnode_s *zero;
struct huffnode_s *one;
unsigned char val;
float freq;
} huffnode_t;
我没有得到的是huffnode_s本身是如何形成的,我以前从未见过它并且不太了解它.这是什么意思,如果有人可以,那python等同于什么？
从我的算法教科书:
一年一度的县赛马比赛将引进三羽从未参加过比赛的纯种马.很兴奋,你研究他们过去的200场比赛并总结这些比赛的概率分布超过四个结果:第一("第一名"),第二名,第三名和其他.
Outcome Aurora Whirlwind Phantasm
first 0.15 0.30 0.20
second 0.10 0.05 0.30
third 0.70 0.25 0.30
other 0.05 0.40 0.20
哪匹马最可预测？这个问题的一个定量方法是研究可压缩性.将每匹马的历史记录为200个值(第一,第二,第三,其他)的字符串.然后可以使用霍夫曼算法计算编码这些跟踪记录串所需的总位数.这对于Aurora来说是290位,对于Whirlwind来说是380位,对于Phantasm来说是420位(检查它!).Aurora具有最短的编码,因此在强烈意义上是最可预测的.
他们是如何为Phantasm获得420的？我一直得到400字节,如下所示:
首先结合,其他= 0.4,结合第二,第三= 0.6.最终以2位编码每个位置.
有没有我对霍夫曼编码算法误解的东西？
教科书可在此处获得:http://www.cs.berkeley.edu/~vazirani/algorithms.html(第156页).
我正在尝试有效地为一组给定字符构造一个二进制后缀代码及其概率(即一组单词,其中没有一个是任何其他单词的后缀).
我的基本思想是使用霍夫曼算法的实现来构造前缀代码.通过反转代码字,我得到一个无后缀的代码.虽然这个解决方案正在工作,但它似乎不是最佳的,因为我必须反转可变长度的代码字(因此我需要一个结合了位移的查找表).
有没有办法修改霍夫曼算法,以便更有效地创建后缀代码？
我正在尝试实现一个 deflate 压缩器，并且必须决定是使用静态霍夫曼代码压缩块还是创建动态压缩器。
与静态代码相关的长度背后的基本原理是什么？
（这是rfc中包含的表格）
Lit Value Bits
--------- ----
0 - 143 8
144 - 255 9
256 - 279 7
280 - 287 8
我认为静态代码更偏向于纯ascii文本，相反，它看起来更喜欢rle长度的压缩
决定是否使用静态代码的良好启发式是什么？
我正在考虑根据输入数据的样本构建概率分布，并根据静态代码导出的概率计算距离（也许是 EMD？）。
我在想一个像
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 …