问题描述
我已经在互联网上阅读了一篇文章,并且知道通过从根进行解码的自然方式,但我想用查找表更快地解码。
输入: 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
我的问题是:
-
由于可变长度,它表示
是什么意思,它通过取一些字符串
来确定长度?如何确定长度?
最大代码长度 -
如何生成查找表以及如何使用它?
长度为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 ofmax 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:
What does it means
due to variable length, it determine the length by taking a bit of string ofmax code length
? How to determine the length?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.
这篇关于具有查找表的霍夫曼码的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!