返回 登录
23

可视化展示Gzip压缩算法

Gzip基于LZ77算法,它的原理是:将数据文件中已出现过的字符用一个“长度-距离”指针代替,这样就避免了冗余。

下面这段视频,显示了手动输入叙事诗《乌鸦》(The Raven)时的算法运行效果。高亮的文字是之前已输入过的内容。如果你想自己输入文字做实验,可以参考这里的代码

优酷视频链接原始出处

严格来说,LZ77压缩只是Gzip的第一步,下一步是通过哈夫曼编码进一步优化压缩结果。如果你想了解完整的压缩过程,这里有一篇详细的文章解释(英文)

对自然语言来说,许多词语重复出现的频率很高。最近的一些研究更是根据语法的特点,将文本变为一个规则生成树。这里还有一篇论文(PDF),对这方面的研究做了解释。

评论