一种快速解析码长的哈夫曼解码方法

摘要

本发明公开了一种快速解析码长的哈夫曼解码方法，步骤包括：建立一张完备码长码表；在定长码字完备码长码表中检索到与这个哈夫曼码字生成树相对应的码表部分；以最大码字长度截取当前待解析的哈夫曼码流作为索引，检索到的码长码表值即为待解析码流中首个码字码长；提取首个码字即可解析到当前码字所对应的数据；从码流中除去已解析的部分，将剩余码流返回第二步；直至全部码流解析完毕后退出。本发明可以根据索引快速解析码长，从而大大减少解码时间，当最大码长为N时，对于逐位比较解析法，解析其码长时间复杂度为o(N/2)；对于级别比较解析法，对于一个给定的码字，其码长解析时间复杂度为o(1)，极大地提高码长确定速度。

主权项

一种快速解析码长的哈夫曼解码方法，其特征在于，步骤包括：1)基于码流中所包含的所有哈夫曼码字生成树的叶子码字，建立一张完备码长码表；2)对于当前待解析的哈夫曼码流，按照其待解析码字所属的哈夫曼码字生成树，在定长码字完备码长码表中检索到与这个哈夫曼码字生成树相对应的码表部分；3)以最大码字长度截取当前待解析的哈夫曼码流，并将这个截取出的码流数值作为索引，在当前码流哈夫曼码字生成树对应的码长码表部分检索，检索到的当前码长码表值即为当前待解析码流中首个码字码长；4)提取首个码字，在当前哈夫曼码字生成树所对应的符号表中即可解析到当前码字所对应的数据；从码流中除去已解析的部分，将剩余码流返回第二步；直至全部码流解析完毕后退出；上述的构造哈夫曼码字生成树对应的完备码长码表的过程：按照对应的哈夫曼码字生成树，构建最大码长长度的各个比特位为全0到全1的索引，并将所有索引值即码长码表值初始化为0；以哈夫曼生成树的所有叶子码字为前缀，将剩余码字位以全0到全1填充到最大码长长度，将所有同哈夫曼码字前缀的扩充码的码长码表值以对应哈夫曼前缀码的长度赋值。