标签: huffman-code

我正在做一个学校项目,在文本上实现霍夫曼代码.第一部分当然需要对文本进行频率分析.除了巨型开关和一系列计数器之外还有更好的方法吗？

即:

int[] counters

for(int i = 0; i <inString.length(); i++)
{
switch(inString[i])
    case 'A':
    counters[0]++;
.
.
. 

我想做所有字母数字字符和标点符号.我正在使用c ++.

    template<class T>
    void huffman(MinHeap<TreeNode<T>*> heap, int n)
    {
      for(int i=0;i<n-1;i++)
      {
        TreeNode<T> *first = heap.pop();
        TreeNode<T> *second = heap.pop();
        TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data);
        heap.push(bt);
      }
    }

在我的C++数据结构基础 教科书中,它给出了霍夫曼编码的2页定义,以及上面的代码.对我来说,这本书不够详细,所以我已经完成了谷歌搜索,我学会了霍夫曼编码的过程.教科书声称在上面的代码末尾,制作了霍夫曼树.但对我来说这似乎是错误的,因为霍夫曼树不是一个完整的树,但上面的代码似乎总是给出一个完整的树,因为heap.push().那么有人可以向我解释这段代码是如何没有错的吗？

我试图通过将字母及其相应的值保存到地图然后将地图插入优先级队列来实现霍夫曼编码.我尝试声明队列时收到参数转换错误.究竟我应该把它作为参数？我在这里是我最好的猜测.

void main()
{
 ifstream doc("doc.txt"); 
 map<char, int> C;
 char letter;
 while(!doc.eof()){
  doc.get(letter);
  if(letter >= 'a' && letter <= 'z')
   C[letter]++;
 }
 priority_queue<int, map<char,int>, greater<int> > Q(C); //also tried greater<map<char,int>>
 /*map<char, int>::const_iterator it;
 for(it = C.begin(); it != C.end(); it++)
  cout<<it->first<<" "<<it->second<<endl;*/
}

我觉得有点愚蠢的问这个,但彻底的谷歌搜索并没有得到答案.非常感谢您的帮助!

对于生成的字母表不是二进制的情况,是否容易推广霍夫曼编码树？例如,如果我想通过三元写出来压缩一些文本,我仍然可以为每个字符构建一个无前缀的编码系统.霍夫曼结构的直接推广(使用k-ary树而不是二叉树)是否仍能正常有效地工作？或者这种结构是否会导致编码方案效率极低？

我试图解决一些霍夫曼编码问题，但我总是得到不同的码字值（值而不是长度）。例如，如果字符 'c' 的码字是 100，在我的解决方案中它是 101。

下面是一个例子：

字符频率码字我的解决方案
   一个 22 00 10
   乙 12 100 010
   24 01 11
   D 6 1010 0110
   E 27 11 00
   传真 9 1011 0111

两种解决方案的码字长度相同，并且不存在作为另一个码字前缀的码字。

这是否使我的解决方案有效？或者它必须只有 2 个解决方案，最佳的一个并翻转最佳的位？

我正在研究霍夫曼编码，我已经用一个构建了字符频率表

std::map<char,int> frequencyTable;

然后我构建了霍夫曼树，然后我以这种方式构建了代码表：

std::map<char,std::vector<bool> > codes;

现在我将逐个字符地读取输入文件，并通过代码表对它们进行编码，但我不知道如何将位写入二进制输出文件。有什么建议吗？

更新：现在我正在尝试使用这些功能：

void Encoder::makeFile()
{
char c,ch;
unsigned char ch2;
while(inFile.get(c))
{
    ch=c;
    //send the Huffman string to output file bit by bit
    for(unsigned int i=0;i < codes[ch].size();++i)
    {
        if(codes[ch].at(i)==false){
            ch2=0;
        }else{
            ch2=1;
        }
        encode(ch2, outFile);
    }
}
ch2=2; // send EOF
encode(ch2, outFile);

inFile.close();
outFile.close();
}

和这个：

void Encoder::encode(unsigned char i, std::ofstream & outFile)
{
int bit_pos=0; //0 to 7 (left to right) on the byte block
unsigned char c; //byte block …

霍夫曼编码涉及的步骤是相当连续的。所以，我想知道如何在支持并行实现的任何平台（如 GPU、多核处理器等）上实现霍夫曼编码时引入并行性？

二叉树(以及因此有序的森林)可以表示为二进制字符串.二进制字符串是通过预先遍历二叉树获得的,每个节点记录1,每个空子树记录一个0(空链接).

这意味着如果我给了一个二叉树,我可以进行前序遍历并生成二进制序列表示.

相反也可能吗？如果我给出了这个二进制序列11011000101101010001,我可以绘制二叉树吗？

当我尝试将节点推入霍夫曼树的堆时，出现以下错误：

TypeError：“ HeapNode”和“ HeapNode”的实例之间不支持“ <”

    class HuffmanCoding:
        def __init__(self, path):
            self.path = path
            self.heap = []
            self.codes = {}
            self.reverse_mapping = {}

        def make_heap(self, frequency):
            for key in frequency:
                node = HeapNode(key, frequency[key])
                heapq.heappush(self.heap, node)

节点类：

    class HeapNode:
        def __init__(self, char, freq):
            self.char = char
            self.freq = freq
            self.left = None
            self.right = None

        def __cmp__(self, other):
            if(other == None):
                return -1
            if(not isinstance(other, HeapNode)):
                return -1
            return self.freq > other.freq

该错误是由以下原因引起的：

    heapq.heappush(self.heap, node)

完整代码由github.com/bhrigu123提供

我在使用 huffmandict 和 huffmanenco 时在 Octave 中遇到了问题。

这是我的错误：

错误：huffmanenco：SIG 的所有元素必须是 [1,N] 范围内的整数

这是我的代码：

inputSig = [1 1 2 6 6 6 6 4 5 5];
list_symb = [1 2 6 4 5];
list_proba = [0.2, 0.1, 0.4, 0.1, 0.2];
dict = huffmandict(list_symb,list_proba);
code = huffmanenco(inputSig,dict);

我的决定是

dict =
{
 [1,1] =  1
 [1,2] = 0   1
 [1,3] = 0   0   1
 [1,4] = 0   0   0   0
 [1,5] = 0   0   0   1
}

所以我的错误在于这条线

code = huffmanenco(inputSig,dict);

因为我的 dict …