我已经使用huffman算法实现了文件压缩,但我遇到的问题是,要启用压缩文件的解压缩,使用的编码树或代码本身也应该写入文件.问题是:我该怎么做？在压缩文件的开始处编写编码树的最佳方法是什么？
我正在编写霍夫曼编码.这是我的计划的开始:
using namespace std;
//Counting methods
int *CountCharOccurence(string text)
{
int *charOccurrence = new int[127];
for(int i = 0; i < text.length(); i++)
{
charOccurrence[text[i]]++;
}
return charOccurrence;
}
void DisplayCharOccurence(int *charOccurrence)
{
for(int i = 0; i < 127; i++)
{
if(charOccurrence[i] > 0)
{
cout << (char)i << ": " << charOccurrence[i] << endl;
}
}
}
//Node struct
struct Node
{
public:
char character;
int occurrence;
Node(char c, int occ) {
character = c;
occurrence = occ; …假设A是一个数组,其中A [0]保持字母表的第0个字母的频率.
计算代码长度的最有效(*)方法是什么？不确定,但我想效率可以是内存使用或所需的步骤.
所有我感兴趣的是数组L,其中L[0]的字母,其中代码来自内置了频率阵列的规范哈夫曼树的0个字母包含代码长度(比特数).
我想用压缩技术而不是Huffman和Adaptive Huffman算法来压缩DNA序列,我使用c#作为编程语言.任何人都可以带我到算法.注意:我想要无损压缩
我正在使用霍夫曼算法开发文件压缩器,现在我面临的问题是:
通过使用该算法:stackoverflow,我得到以下结果:
a,c,e,f,k,l,r,s,t,v,w = 1 time repeated
o = 2 times repeated
a,c,e,f,k,l,r,s,t,v,w = 7.69231%
and
o = 15.3846%
所以我开始插入二进制树,这将得到结果:
o=00
a=010
e=0110
c=0111
t=1000
s=1001
w=1010
v=1011
k=1100
f=1101
r=1110
l=1111
这意味着树中角色的路径,考虑0为左,1为右.
然后单词"stackoverflow"将是:100110000100111010011111000010110110111011011111001010
好吧,我想将整个值放入一个二进制文件中,这将导致47位,这将是6字节,但我只能使它成为47字节,因为最小值将被放入一个文件与fwrite或者fprintf是1byte,使用sizeof(某事物).
比我的问题是:我如何只在我的文件中打印一下？
需要一些帮助才能理解DEFLATE编码的工作原理.我知道这是LZSS算法和霍夫曼编码的组合.
所以让编码例如"Deflate late".参数:[搜索缓冲区:8kb和前瞻缓冲区4kb]嗯,LZSS算法的输出是"Deflate <5,4>"下一步使用静态霍夫曼编码来减少冗余.这是我的问题,我不知道如何用霍夫曼编码这对<5,4>.
D 000
f 001
l 010
a 011
t 100
_ 101
e 11
好吧,根据这个表,字符串"Deflate"写成000 11 001 010 011 100 11 101.下一步是编码对(5,4).根据书"数据压缩 - 完整参考"的长度为4的固定前缀码是258,接着是距离5的固定前缀码(码4 + 1额外比特).
这可以概括为:
长度4 - > 258 - > 0000010
距离5 - > 4 + 1额外位 - > 00100 | 0
因此,编码的字符串被写为[header:1 01] 000 11 001 010 011 100 11 101 0000010 001000 [block-of-block:0000000],但是如果我创建一个huffman树,它不再是静态的huffman,对？
美好的一天
假设我们开始使用如下文本文件:
a 00
b 01
c 10
d 11
00000001011011
该算法将是您使用前缀来构建霍夫曼树的典型算法,在遍历树时读取编码位,直到到达叶子,然后在该叶子处返回字符.
有人可以解释我如何确定运行时间和空间复杂度？
我试图理解PNG中的压缩 - 但我似乎
在网上找到很多矛盾的信息...我想了解 - 在LZ77部分中如何进行搜索:带链表的哈希表？这是在deflate中定义的吗？或在zlib中实现？有搜索方法的选择吗？ - PNG编码器/解码器可以为压缩设置一些参数(策略,过滤器等),还是PNG有默认值？ - LZ77部分做贪婪或懒惰的评估吗？或者这也是一个选择？ - 最后:2个霍夫曼树,它们是在第三棵树中压缩的,而且它们都被编码了？或者只用它们的代码长度编码的2棵树？
zlib实现是否与其他deflate实现不同？也许这就是我所有的困惑来自哪里？
感谢您的任何帮助!!我的新工作需要这个
LuCu
您好我正在尝试实现Canonical霍夫曼编码,但我不懂wiki和谷歌指南,我需要更抽象地解释...
我试过这个:1.获取常规霍夫曼编码长度代码的列表.像这样:
A - code: 110, length: 3.
B - code: 111, length: 3.
C - code: 10, length 2.
D - code: 01, length 2.
E - code: 00, length 2.
Run Code Online (Sandbox Code Playgroud)C - code: 10, length 2. D - code: 01, length 2. E - code: 00, length 2. A - code: 110, length: 3. B - code: 111, length: 3.
现在我不知道如何继续......
tnx很多