标签: huffman-code

你如何使用诸如 NEED 之类的霍夫曼代码对单词进行编码

我目前正在致力于在 Java 中实现基于霍夫曼算法的程序，并且我正处于需要将编码内容输出到文件的阶段。我对如何实现解码所需的标头和 eof 有点困惑。对于目前的标题，我拥有输入文件中出现的所有唯一值及其频率，但在一些文章中，我看到人们用 0 或 1 表示节点，然后是频率（我有点困惑） by 因为它没有说明符号是什么）。

另外，对于我所理解的 EOF，我像符号一样对其进行编码，以便读取和解码，但是我不确定我可以使用什么值来肯定不会出现？我知道它的权重需要为 1，但不确定如何确保它实际上不在文件中。

我不确定这要求我在matlab做什么？编码意味着什么？答案应该是什么格式？谁能帮我解决一下呢？编码8x8图像补丁并打印出结果

我有一个8X8的图像

symbols=[0 20 50 99];
p=[32 8 16 8];
p = p/sum(p);
[dict, avglen] = huffmandict(symbols, p);
A = ...
[99 99 99 99 99 99 99 99 ...
20 20 20 20 20 20 20 20 ...
0 0 0 0 0 0 0 0 ...
0 0 50 50 50 50 0 0 ...
0 0 50 50 50 50 0 0 ...
0 0 50 50 50 50 0 0 ...
0 0 50 50 50 …

JPEG 标准中的霍夫曼表是通过两个步骤从统计数据集合中生成的。步骤之一是实现该图给出的功能/方法：（该图在 JPEG 标准的附件 K 中给出）：

问题就在这里。之前在标准（附录C）中说了这样一句话：

霍夫曼表以 16 字节列表 (BITS) 的形式指定，给出从 1 到 16 的每个代码长度的代码数量。后面是 8 位符号值 (HUFFVAL) 列表，每个符号值是分配一个霍夫曼代码。

显然BITS是 16 个元素的列表。但在上图中，i首先设置为 32( i=32) 然后我们要访问BITS[i]. 可能是我理解错了，所以请有人给我答案。

以下是 JPEG 标准对图片的描述： 图 K.3给出了调整 BITS 列表的过程，以便没有代码长于 16 位。由于符号是针对最长的霍夫曼码配对的，因此每次从该长度类别中删除两个符号。该对的前缀（短一位）被分配给该对中的一个；然后（跳过该前缀长度的 BITS 条目）来自下一个最短非零 BITS 条目的码字被转换为长一位的两个码字的前缀。在 BITS 列表减少到最大代码长度 16 位之后，最后一步从代码长度计数中删除保留的代码点。

这是上图的代码：

void adjustBitLengthTo16Bits(vector<char>&BITS){
    int i=32,j=0;
    while(1){
        if(BITS[i]>0){
            j=i-1;
            j--;
            while(BITS[j]<=0)
                j--;
            BITS[i]=BITS[i]-2;
            BITS[i-1]=BITS[i-1]+1;
            BITS[j+1]=BITS[j+1]+2;
            BITS[j]=BITS[j]-1;
            continue;
        }
        else{
            i--;
            if(i!=16)
                continue;

            while(BITS[i]==0)
                i--;
            BITS[i]--;
            return;
        }
    }
}

我真的很为合并在霍夫曼编码中具有相同“权重”的树的顺序而苦苦挣扎。我查看了很多来源，但它们似乎都只涵盖“简单情况”，其中不超过两个具有相同权重的元素，或者根本没有涵盖整个主题。

假设我有以下要编码的字符串：ABCDEE. （风格基于本网站）
所以我有：

    FREQUENCY       VALUE
    ---------       -----
         1            A
         1            B
         1            C
         1            D
         2            E

我现在开始用两个最小的元素构建树：
问题 1)我是否必须使用A & B或如何决定我应该使用哪些值？我知道它们必须是最小的，但除此之外呢？例如A & D？
这是重要末（可以说，我做到以下几点：）

  2:[A&B]       2:[B&C]
    /  \          /  \
  1:A   1:B     1:B   1:C

以及下表：

    FREQUENCY       VALUE
    ---------       -----
         2          [A&B]
         2          [C&D]
         2            E

问题 2）再次...我应该以什么顺序合并树？例如[A&B]&E或[A&B]&[C&D]
因为，如果我[A&B]&E先合并，树将如下所示：

      4:[A&B&E]
        /   \
    2:[A&B]   2:E
    /   \
  1:A   1:B

（问题3）如何决定2:E …

我需要霍夫曼代码(最好是在python或java中),它可以编码文本而不是一个字符(a = 10, b = 11),而是两个(ab = 11, ag = 10).是否可能,如果可以,我在哪里可以找到它,也许它在互联网的某个地方,我就能找到它？

目前,我正在开发一款需要在iPad上存储大量文本的应用.我的问题是,像生产中实际使用的霍夫曼编码这样的算法吗？我只需要一个非常简单的压缩算法(不会有大量的文本,它只需要一个更有效的存储方法),那么像Huffamn这样的工作呢？我应该调查一些其他类型的压缩库吗？

我最近在C++中构建了一个Huffman编码的CPU实现.我还在CUDA中构建了一个GPU版本以便比较时间,但是在测试CPU的时间时我遇到了一个问题:

当通过压缩大文件进行压力测试时,例如几乎每个字母中的每个字母和其他各种ascii字符的97mb文本文件,我的CPU实现在第一次执行时将花费大约8.3秒.之后,时间显着下降到1.7秒.注意:我只计算CPU计算频率的时间,而不是字符串的编码和写入文件.

任何想法如何可能？我正在关闭所有文件指针,据我所知,不应该缓存任何内容.

如果需要任何源代码,请告诉我,谢谢.

我写了一些我试图修复的有缺陷的Huff压缩代码.我做的第一件事就是将指针切换到auto_ptr(有理由我没有使用另一个智能指针).我创建了一个向量,auto_ptr但是当我尝试将auto_ptr传递给函数时,*(vector.begin())它不起作用.

我的功能代码我试图将所有权传递给(它是一个成员函数为set_node):

struct Node {
    int weight;
    char litteral;
    auto_ptr<Node> childL;
    auto_ptr<Node> childR;
    void set_node(int w, char l, auto_ptr<Node>& L(), auto_ptr<Node>& R()){
        weight = w;
        litteral = l;
        childL = L;
        childR = R;
    }
};

这就是我尝试调用它的方式(p是节点):

p.set_node(w, '*', *nodes->begin(), *(nodes->begin()+1));

这是向量声明的方式:

vector<auto_ptr<Node> >* nodes = new vector<auto_ptr<Node> >;

有可能计算出有多少节点有任意二叉树吗？叶子数和每片叶子的深度是已知的(实际上是霍夫曼树).

我需要它,以便能够在实际构建树之前为树分配所需的内存,并避免以后重新分配内存.