C++ LZ77压缩

谁借莪１个温暖的怀抱￠ 2022-02-26 13:30 119阅读 0赞

### 文章目录 ###

*   *  引言
     *  压缩过程
     *  如何找最长匹配
     *   *   *  暴力求解
             *  哈希桶
     *  如何区分源文件还是(距离，长度)
     *  压缩文件中的内容
     *  解压缩
     *  遇到的问题
     *  源码

## 引言 ##

> lz77压缩是基于字典做数据压缩的方法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年提出，LZ77算法名字就取于这两个人的名字，77表示是1977年提出

## 压缩过程 ##

LZ77是通过字节来对文件进行压缩，就是将源文件中重复的字节通过（距离，长度）的方式来进行替换，进而达到压缩的目的。  
例如源文件内容为：mnoabczxyuvwabc123456abczxydefgh

上述字符串中出现多次abc，就可以通过长度距离对的方式来进行压缩  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]  
并且我们发现，在上述过程中，只有遇见三个字符才会进行替换，这是为什么？？  
首先，目前距离长度对占两个字节  
一个字符重复？不替换，替换之后文件反而会变得更大  
两个字符重复？不替换，替换之后和原文件大小一样，没必要  
三个字符重复？替换，替换之后三个字符变成两个字节，达到压缩的目的  
结论：大于等于三个字符重复就进行替换

## 如何找最长匹配 ##

通过上面的压缩过程，我们可以发现这样几个问题：  
如何查找最长匹配？  
找到了怎么办？  
未找到怎么办？

#### 暴力求解 ####

首先，我们最容易想到的就是暴力求解，因为暴力求解比较简单，只需从后往前开始匹配即可，意见更长的匹配串进行替换标记，但是暴力求解也太慢了，算法时间复杂度为O(N^2)，查找起来会非常的慢，如果是小文件还好，但要是大文件尼？？

#### 哈希桶 ####

另外一个容易想到的就是采用哈希表，计算出三个字符的哈希地址，进行插入，然后查询起来就会很快了，哈希结构有两种方式：闭散列、开散列。如果采用闭散列的方式，哈希函数该如何设计？如果存在冲突了怎么办？怎么查找最长匹配串，就会出现问题。于是我们采用开散列的方式：哈希桶。  
如果采用普通的哈希桶，因为三个字符也就是三个字节，有2^24种情况，就需要16M的空间，而一个索引占两个字节，所以就需要32M的空间，浪费的空间太大了，维护起来也很麻烦，所以我们采用一种类似于哈希桶的方式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]  
通过上述这种方式，就可以很好的避免空间开销过大的问题，并且能够很快的找到匹配的字符串，这时候只需要判断哪个是最长的就行，效率也大大提高。

**但如果说，找不到最长匹配怎么办？？**  
找不到实际上就是上述的第一步，因为第一步也是第一次插入。

但上述我们针对的都是小文件，如果是一个很大的文件？这时候，一个窗口中的数据是存放不下的，因为我们一个窗口的大小定义的是64k，我们把这个窗口分为两部分，各占32k，如果说数据不够了，就需要补充数据，但如何进行补充数据？？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]

## 如何区分源文件还是(距离，长度) ##

就如上面提到的，进行替换的时候，是没有 () 和 , 的，只有两个数据，那么如何和源文件中的内容加以区分尼？这时候，很容易想到用标记，0 和 1 (注意：这里的标记使用的是bit位)，0表示是源文件的内容，1 表示是(距离，长度)对，这样就能区分了，但这时我们就又需要一个压缩文件，用于存放标记，但在数据完全压缩结束，就可以吧标记文件的内容全部拷贝到压缩文件中，这时候再把标记文件删除即可

## 压缩文件中的内容 ##

第一行：源文件后缀(换行)  
接下来：压缩后的数据（也就是进行(距离，长度)对更换后的数据）  
接下来：标记文件中的数据（事先保存在另一个文件中的）  
接下来：压缩后数据的大小（用于解压缩后判断是否还需要拷贝数据）  
接下来：标记数据的大小（用于将压缩数据和标记数据划分开，知道从哪里开始往后是标记数据）

## 解压缩 ##

LZ77的解压缩过程会非常的简单

1.  准备工作  
    a. 获取源文件大小  
    b. 获取标记数据
2.  开始解压缩  
    读取一个字节，并及时获取一个标记，看当前标记的bit 为0还是1  
    a. 为0 ：当前字符为源字符，直接写入压缩文件  
    b. 为1：(距离，长度)从当前文件指针位置，找到匹配的起始位置，从该位置开始的长度个字符写 入压缩文件中
    
    重复上述过程

## 遇到的问题 ##

1.  一定要看清楚(距离，长度)中的距离占两个字节，而长度占一个字节，在解压缩文件的时候一定要读正确。。
2.  第一次解压缩的时候，将源文件和解压缩后的文件对比，多出来了几个空格？？  
    那是因为没有及时更新缓冲区，比如，文件中的内容为 aaaaab ，这时候写入压缩文件中的数据为a14b，其中的14就是距离长度对 (1, 4)，如果进行解压缩  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 3]

## 源码 ##

[LZ77压缩源码][LZ77]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220226/7acf5f67a3c946a1a4b6a62754169cab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220226/f70a53e705e24d9a8591580601852335.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]: /images/20220226/5844e8d62a8e4a48b3009013c0c4b43a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 3]: /images/20220226/ea4e45c587184f809fa2d2b9c7b17874.png
[LZ77]: https://github.com/1792114384/Project/tree/master/LZ77