LHARC中的动态限长编码压缩算法(3)
2015-06-23 01:00
导读：代码长度的缩减会带来一个十分关键的问题:当码树各结点值是静态的时候,一字符对应了某一高层结点后,此结点的所有下层枝叶将不能再对应其它字符,否
代码长度的缩减会带来一个十分关键的问题:当码树各结点值是静态的时候,一字符对应了某一高层结点后,此结点的所有下层枝叶将不能再对应其它字符,否则一些代码将是另一些代码的前缀,这将使还原过程无法进行。因此代码缩减将使编码路径数减少,一些后继字符将无法由码树编码。为此,该算法采取的策略是:按字符出现的次序将它们集中排列在码树的一侧叶子上,通过移动和交换分枝点之值的方法,使各层结点之值重新组合,从而使被占用结点的下属枝叶可“稼接”到未用的结点上。因此,当高层结点被占用后,其下属结点仍可使用,不会减少编码路径数。具体来说,当一后继字符出现并且其对应叶子的父结点已被占用,它将改变原有的编码路径,通过搜索找出一个未用的上层结点并由此得到其代码。
同样,当一字符须上升一层时,并不是升到其父结点中,而是升到上层中一个未用过的结点之中。当该字符再度出现时,它将沿新路径得到其代码,此代码的长度不仅为原代码长度减1,而且此代码的各个位也与原代码不同。下面以一具体例子加以说明。
设字符串为ababcabdabc……各字符的编码路径如图2所示。其中的Xi表示X的第i次出现。
@@09A04901.GIF;图2 字符编码路径示意图@@
由此可看出,由该算法给出的编码方法是逐步达到最佳码长的。一字符的压缩代码不仅与字符出现的次数有关(长度不同),而且与字符在文件中的位置有关(编码路径不同)。
LHARC建立了两个表专门用来记录码树的占用情况及各字符出现的次数,以便确定对码树的各种调整。当压缩后的数据达到32K时,将对表及码树进行“重组”,删除表中部分累积的数据后再继续进行压缩,以后将每隔16K“重组”一次。
（科教论文网 Lw.nsEAc.com编辑整理）
作者：傅晓玲
