Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

LZ77编码原理

  首先,LZ77不是一种算法,而是一种编码理论。同Huffman编码一样,只定义了原理,并没有定义如何实现。基于这种理论来实现的算法才称为LZ77算法,或者人们更愿意称为LZ77变种。实际上这类算法已经有很多了,比如LZSS、LZB、LZH,等(怎么没有LZSB呢←_←)。
  LZ77本身并不是压缩,它只是把数据分析成了可供压缩的一个序列而已。也就是说,也就是说,如果把LZ77看做一个函数的话,它的参数是数据,而返回值则是一个结构序列,而如果把这个结构序列实体化它是不定义的。
  LZ77中有这么几个概念:Window、SB(Search Buffer)、LB(Lookahead Buffer)。Window是由SB和LB组成的。下面的演示动画中,整个矩形框(包括蓝色和红色)就是Window,红色的部分是SB,蓝色的部分是LB。Window和SB的大小由于具体的算法决定的,下面的演示动画中为了方便说明,把Windonw的取值变得很小,实际算法中比这个大的多。

  LZ77工作流程中,Window会在整个数据上滑动。每次滑动都会把LB中的字符串在SB中寻找最长的匹配。记录这个匹配到的串到当前字符的距离和匹配到的串的长度,并和它的下一个字符一起作为结果输出。当然并不是时候都能匹配到,在没有匹配时距离和匹配串长度都按0来计。而这个匹配的过程并么有定义,由具体的算法来决定。有些算法中会抛弃掉太短的匹配,比如只有一个字母相同时如果算法决定匹配它不划算就无视掉它。
  上面的演示动画中,每次匹配都会得到一个由两个数字和一个数据组成的结构项,整个匹配过程结束后得到的结果就是由这些结构项组成的序列。这就是LZ77的工作。至于这个序列要如何使用,实际上就是具体的算法来定义了。只要找到一种对这个结构项序列的优秀存储方案就是一个优秀的压缩算法。

  参考:http://jens.quicknote.de/comp/LZ77-JensMueller.pdf
网名:
54.224.247.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^