具有查找表的霍夫曼码 [英] Huffman code with lookup table

问题描述

我已经在互联网上阅读了一篇文章，并且知道通过从根进行解码的自然方式，但我想用查找表更快地解码。

 
输入：
 abcdaabaaabaaa
代码数据
 0 a 
 10 b 
 110 c 
 111 d 
 

文章说，由于可变长度，它通过取一点
的最大代码长度的字符串并使用它作为索引来确定长度。

 
输出：010110111001000010000
索引索引（二进制）需要的代码位
 0 000 a 1 
 1 001 a 1 
 2 010 a 1 
 3 011 a 1 
 4 100 b 2 
 5 101 b 2 
 6 110 c 3 
 7 111 d 3 
 

我的问题是：

1. 由于可变长度，它表示是什么意思，它通过取一些字符串
最大代码长度来确定长度？如何确定长度？




2. 如何生成查找表以及如何使用它？

解决方案

长度为3位。所以你从你的流（010）取前3位，并使用它索引表。这给出代码'a'和bits = 1。从输入流中消耗1位，输出代码，然后继续。在第二个周围你会得到（101），索引为'b'和2位等。

要建立表，使其大到1 << max_code_length，并填写详细信息，就像将索引解码为huffman代码一样。如果你看看你的例子，所有开始为'0'的索引都是a，开始于'10'的索引是b，依此类推。

I have read an article on Internet and know that the natural way of decoding by traversing from root but I want to do it faster with a lookup table.

After reading, I still cannot get the points.

ex:

input:"abcdaabaaabaaa"
code   data
0      a
10     b
110    c
111    d

The article says that due to variable length, it determine the length by taking a bit of string of max code length and use it as index.

output:"010110111001000010000"
Index    Index(binary)    Code    Bits required
0        000              a       1
1        001              a       1
2        010              a       1
3        011              a       1
4        100              b       2
5        101              b       2
6        110              c       3
7        111              d       3

My questions are:

1. What does it means due to variable length, it determine the length by taking a bit of string of max code length? How to determine the length?

2. How to generate the lookup table and how to use it? What is the algorithm behind?

解决方案

For your example, the maximum code length is 3 bits. So you take the first 3 bits from your stream (010) and use that to index the table. This gives code, 'a' and bits = 1. You consume 1 bit from your input stream, output the code, and carry on. On the second go around you will get (101), which indexes as 'b' and 2 bits, etc.

To build the table, make it as large as 1 << max_code_length, and fill in details as if you are decoding the index as a huffman code. If you look at your example all the indices which begin '0' are a, indices beginning '10' are b, and so on.

这篇关于具有查找表的霍夫曼码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！