昨天看了下LZSS.C，就是那个4/6/1989 Haruhiko Okumura的经典代码。
很久没有研究算法了，又没有详细的描述，只能从代码和注释里面去理解。还真花了我不少时间。
首先讲解压，LZSS的编码是1 byte的flag，从低到高，如果bit=1，原样输出1 byte，如果bit=0，读取2 byte，输出长度和缓冲区位置保存在这2 byte中。
其实标准的LZSS我还是第一碰到，以前碰到的多是输出长度和回溯距离的组合。LZSS则多了一个缓冲区，一般大小N = 4096（0x1000），也就是12 bits，缓冲区位置占掉了12 bits，那么输出长度就只能占用4 bits。考虑到bit=0时至少要占用2 bytes，所以输出长度为2时刚刚盈亏平衡，所以一般来说输出长度是从3开始的。在代码中THRESHOLD = 2，意思其实是长度必须大于2。这样的话输出长度的范围就是3-18。代码中F = 18，F就是最大的输出长度。
我碰到到是一个改版，N = 0x800，也就是11 bits，输出长度变成了5 bits，THRESHOLD = 1，最后输出长度的范围是2-33。个人觉得THRESHOLD改成1实在是浪费了一个珍贵的输出长度编码。
用了缓冲区和不用缓冲区的区别，我看就是多了一个字符串，就是缓冲区一开始填充的值。LZSS.C中默认填充的是空格，那么大概是专门为文本文件设计的。一般还是填充0比较多。具体怎么回事下面再描述。
缓冲区的大小N，一开始先填充N-F区域，然后一边解压，一边循环的从N-F开始填充字符。一般来说开头的字符很难形成重复，所以LZSS压缩的特征往往是FF xx xx xx ..(8 bytes) FF xx xx xx...(8 bytes)，到后面出现大量重复了，就难以辨认了。如果一开头是一段空格的话，那么第一段就可以(pos = N-F-1, len = 8)，这样就可以输出8个空格。如果不用缓冲区的话，开头的8个空格就要变成(空格), (N-F, 7)，算是节约了1个byte。
下面讲压缩，其实最简单的压缩就是做一个for循环，从头到尾一个个比较，最后保留匹配长度最大的那个。这样的话复杂度是O(n*N*F)，其中n是待压缩文本的大小，F是最大输出长度，这个值很小可以不管，N就是缓冲区大小或者回溯距离，只要n和N不是很大，速度都是秒的。
LZSS.C中提供了一个优化的算法，其实整个代码也就这段有看头。首先定义了3个数组，lson, rson, dad组成了一颗二叉树，lson, dad的大小都是N+1，要注意rson[N]/dad[N]其实并没有被用到，N这个值在程序中被定义成NIL，故意多开一个只是为了方便。这种为了方便的情况出现很多，就不多说了。
然后是rson在N+1的基础上还多出了256，这是为了存放1 byte的所有编码，其实就是根。我觉得其实可以新开一个数组的，没有必要用rson这个名字。rson其实用来保存大于等于的字符串，lson保存小于的字符串。dad就是保存dad。至于什么叫做大于等于，用过strcmp总有体会吧，或者看看下面的说明。
算法我用例子来说明吧，比如一段文字：
--- 我 是 标 尺 ---
1234 567 89012 345678
abcd abc abcde abcdef
注：为了方便起见，rson['a']的含义其实是rson[N+1+'a']，文本位置从1开始，1其实是N-F
1）读取a，找到rson['a']，这个值初始为NIL，那么写入位置1。
2）读取b-d，rson['b']-rson['d']等于2-4
3.a）又读取a，此时rson['a'] = 1, 那么比较两个字符串（从1开始的和从5开始的），比较下来长度=3，比较的最后一步是位置8的'a'-位置4的'd'，cmp<0，所以此时检查lson[1]，lson[1]当然还是NIL，所以不再比较了，把lson[1]设置成4。意思就是说1和4，都是'a'开头的字符串，4比1小。
3.b）下面是输出和补充字符，首先输出(1, 3)，至于怎么写flag和那2byte我就不讲了。然后读入3 bytes，考虑如果本算法已经执行了一段时间了，填充区已经填满，那么读入的时候就占用了先前的字符，那么此时还要删除先前字符的节点。读的同时位置6开始的'bc'也要添加入树中，不过就算匹配长度超过2，也不会输出罢了。
4）读取位置8的'a'，rson['a] = 1, 比较两个字符串（位置8和位置1开始的字符串），最后结果是cmp = 'e'-'a' > 0，len = 4，检查rson[1] = NIL，那么写入rson[1] = 8，后面的步骤和3.b一样。
5）读取位置12的'e'，rson['e'] = 12
6）读取位置13的'a'，rson['a'] = 1，比较两个字符串（位置13和位置1开始的字符串），最后结果是cmp = 'e'-'a' > 0，len = 4，检查rson[1] = 8，那么再比较这两个字符串（位置13和位置8开始的字符串），最后结果是cmp = 'f' - 'a' > 0，len = 5，再检查rson[8] = NIL，那么rson[8] = 13。最后输出的就是(8, 5)。
解释到这里应该就很清楚了，这里面有这样一个关系，就是如果当前字符串比这个节点大，那么只有往右支找才有前途，反之亦然。这个很好想，比如说根是'abcde'，左支是'abcaa'，根和左支的相同字符数是3，如果当前字符串是'abz'，和根的相同字符数是2，还小于3，那么到左支去也就是平手，如果当前字符串是'abcdz'，和根的相同字符数是4，那已经超过左支了。现在我是变化当前字符串，如果当前字符串不变，和根的相同字符数是N，根的左支所有的子节点和根的相同字符数如果大于N，也最多和根平手，如果小于N，就肯定输了。去右支，虽然可能碰到'az'这种更差情况，但'abcdzaaa'这种更好情况也只可能在右支出现。所以说去右支才有前途。
最后还有个有意思的东西，就是在正式读取待压缩数据前，会将N-F前的F个字符加入到树中，作用我刚刚提到过，在开头有8个空格的情况下，可以节省1byte，此时的输出时(pos = N-F-1, len = 8)，那么只要添加一个字符不就行了么。其实考虑开头不是空格的情况，一段代码在中间部分出现了缩进（显然很多人喜欢将tab转成4个空格），于是依次出现了4个空格，8个空格，12个空格等等。一般的回溯距离+输出长度的话，编码会是这样的(空格), (-1, 3),...,(-x1, 4), (-4, 4),...,(-x2, 8), (-4, 4)，那么标准的LZSS，且加入过F个空格的话，编码就简单多了：(N-F-4, 4),...,(N-F-8, 8), ..., (N-F-12, 12)
算法中还有些删除节点，边界判断之类的东西，这都是基础的东西，不讲了。这个优化算法的效率应该是O(n*logN*F)
6/10/2010 10:50:00 AM 初稿
2010年6月24日21:37:34 补充：
关于效率有点问题，优化算法每一个字符都要添加进二叉树中，所以效率是O(n*logN*F)，但是用循环遍历的不需要添加每一个字符，找到一个匹配串之后，指针就向后移动了。所以效率应该是O(r*n*N*F)，新增的系数r接近压缩率，但比压缩率要小，这个值不妨认为是0.1。那么只有在logN < 0.1N的时候优化算法才划算。所以N应该大于2^6。