LZ77算法学习

起因

没事打算啃下压缩算法原理

正文

压缩

1. 直接开始写原理吧
2. 比如个字符串aabcaacdcaaac, 我们设定一个为4的缓冲区。
3. 步骤
   
   1. [...a]abcaacdcaaac aabcaacdcaaac
      
      1. 这里先丢一个进入缓冲区，由于缓冲区就一个字符其余都是null，因此就直接保留不需要替换。
   2. [..aa]bcaacdcaaac a(1,1)bcaacdcaaac
      
      1. 第二个a进入缓冲区的时候，就会对缓冲区内进行检索，发现a是重复的，然后再对第一个入缓冲区的a的右侧的字符进行匹配，发现第一个a的右侧是a，第二个a的右侧是b，因此就停止匹配。
      2. 这里就将原来的字符串进行更改，将第二个a更改为（1，1），括号中的第一个数字1是开始字符匹距离匹配字符的距离。这里可以把这个距离看成两个字符中间的字符+1，就比如在缓冲区域中的"aa"，两个字符中间是没有字符的，所以其距离+1就为1。第二个数字则为连续匹配上的数字，这里连续匹配只连续匹配上了1个字符“a”因此结果就为1。
      3. 注意：这里的更改不会对这个字符串进行更改，而是对结果字符串进行更改，当前运行的字符串比如“abcaacdcaa”，查询时还是用缓冲区的方式查询[..aa]bcaacdcaa，但会在结果处理的时候创建一个字符串，是对这个字符串进行修改，这个时候结果字符串就变成了"a(1,1)bcaacdcaa"。
   3. [.aab]caacdcaaac a(1,1)bcaacdcaaac
      
      1. 当b进入缓冲区的时候，就对缓冲区内进行查找，发现没有匹配的就跳过，进行下一个字符的查找。
   4. [aabc]aacdcaaac a(1,1)bcaacdcaaac
      
      1. 当c进入缓冲区的时候，也是一样，就对缓冲区内进行查找，发现没有匹配的就跳过，进行下一个字符的查找。
   5. a[abca]acdcaaac a(1,1)bc(3,1)acdcaaac
      
      1. 当缓冲区满了过后，下一个字符进入缓冲区时，就会把缓冲区中最后一个字符挤出去（这里是从有右往左看）。
      2. 当a进入时进行匹配，发现能够匹配上最后的一个字符a，之间间隔了“bc”，因此他们的距离就是3。
      3. 然后查看连续字符，原有字符a的右边边为b，新加入的a的右边为c，因此无法连续，只有a一个连续字符，连续值就记为1。
   6. aa[bcaa]cdcaaac a(1,1)bc(3,1)(1,1)cdcaaac
      
      1. 当a入缓冲区的时候，匹配到的a，并且判断他们之间没有字符，因此距离为1。
      2. 并且原有字符a右侧是a，新加入字符右侧为c，因此停止匹配，连续值为1。
   7. aab[caac]dcaaac a(1,1)bc(3,1)(1,1)(3,1)dcaaac
      
      1. c加入后匹配到有c，距离为3。
      2. 原有c右侧为a，新加入c右侧为d，停止匹配，连续值为1。
   8. aabc[aacd]caaac a(1,1)bc(3,1)(1,1)(3,1)dcaaac
      
      1. 没有匹配跳过
   9. aabca[acdc]aaac a(1,1)bc(3,1)(1,1)(3,1)d(2,1)aaac
      
      1. 加入c后，匹配到c，距离为2。
      2. 原有c右侧为d，新加入c右侧为a，停止匹配，连续值为1.
   10. aabcaa[cdca]aac a(1,1)bc(3,1)(1,1)(3,1)d(2,1)aaac
       
       1. 加入a过后，没有匹配跳过。
   11. aabcaac[dcaa]ac a(1,1)bc(3,1)(1,1)(3,1)d(2,1)a(1,2)c
       
       1. 加入a后，匹配到a，距离为1。
       2. 原a右侧为a，新a右侧为a，加入a，连续值+1为2。此时缓冲区内为aabcaacd[caaa]c。进行下一次迭代匹配旧a右侧为a，新a右侧为c，终止匹配，连续值最终为2。
   12. aabcaacdc[aaac] a(1,1)bc(3,1)(1,1)(3,1)d(2,1)a(1,2)c
       
       1. 加入c后，没有匹配到内容，跳过。
4. 结论
   
   1. 因此最终结果为a(1,1)bc(3,1)(1,1)(3,1)d(2,1)a(1,2)c ，这就是压缩到过程，压缩的好处就在于将原先的字符通过算法的方式变成了以数字存储的元组形式，这样能够有效压缩空间。比如一个字符a用ascii码来表示需要97，二进制表示为0110 0001，但如果变成了(1,1)这样或许会多出一些，但如果遇到连续的比如(10,9)，这种就可以节约出很大一部分的空间。

解压

1. 就不一个一个逆了，现在已经是凌晨了顶不住了。

   

2. 直接贴文章的内容吧

   
   
   1. 压缩过的文本其实是由一系列的这种 (d, 1) 标记对和字母组成，标记对无法直接找到相匹配的字母。在解压过程中，字母保持不变，这种标记对转换为其指向位置的字母。下面看一个解压的例子：
   2. abc(3, 2)(1, 1)
   3. 复制代码字母 abc 保持不变，标记对 (3, 2) 表示从当前位置向左移动 3 个单位，然后取出 2 个字母，因此其转换为 ab。现在原始文本变成了这样 abcab(1, 1)，最后的一个标记对表示从当前位置向左移动 1 个单位，然后取出 1 个字母，因此转换为 b。最终解压完成的文本为 abcabb。

3. 就提一点，这个是从左往右看，就是反着来就行。具体看原理。

总结

我是犯了什么大病，大半夜跑来看算法原理，看完了还要写文章，写着写着又把自己绕进去了。

参考文章

https://juejin.cn/post/6844904168142929933

本文链接：