注:哈夫曼和LZSS算法不是同一种算法,先用哈夫曼再用LZSS算法压缩后会发现经哈夫曼压缩后再用LZSS压缩文件会变大,具体原因不明
LZSS原理:
把编码位置置于输入数据流的开始位置。
在前向缓冲器中查找窗口中最长的匹配串
① Pointer :=匹配串指针。
② Length :=匹配串长度。
判断匹配串长度Length是否大于等于最小匹配串长度(MIN_LENGTH) ,
如果“是”:输出指针,然后把编码位置向前移动Length个字符。
如果“否”:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动一个字符。
如果前向缓冲器不是空的,就返回到步骤2。
例:编码字符串如表03-05-3所示,编码过程如表03-05-4所示。现说明如下:
“步骤”栏表示编码步骤。
“位置”栏表示编码位置,输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏的输出为:
① 如果匹配串本身的长度Length >= MIN_LENGTH,输出指向匹配串的指针,格式为(Back_chars, Chars_length)。该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”。
② 如果匹配串本身的长度Length >= MIN_LENGTH,则输出真实的匹配串。
表:输入数据流
位置 1 2 3 4 5 6 7 8 9 10 11
字符 A A B B C B B A A B C
表:编码过程(MIN_LENGTH = 2)
步骤 位置 匹配串 输出
1 1 -- A
2 2 A A
3 3 -- B
4 4 B B
5 5 -- C
6 6 B B (3,2)
7 8 A A B (7,3)
8 11 C C