【压缩算法】LZ77算法

一、算法介绍

LZ77算法是采用自适应的字典模型，也就i是将已经编码的信息作为字典，如果要编码的字符曾经出现过，就输出该字符串的出现位置以及长度，否则输出新的字符串。

二、算法思想

它的核心思想是在前面已经出现过的数据中找重复出现的字符，根据局部性原理，入股一个字符串要重复，那么也实在附近重复，远的地方就不要找了，因此设置一个滑动窗口，每次都在这个窗口里面找重复出现的字符。

关于这个滑动窗口的大小，理论上是窗口越大，重复的可能性越高，压缩效率越高。但是窗口太大的话，查找的效率也会降低。
在LZ77算法中设置滑动窗口的大小为32k。

三、算法实现

1. 经过LZ77算法后，一段字符串可以表示为“原文和距离+长度”的形式。我们可以在每一个字符后面都加一个bit位的标志位用于区分“原文”和“距离+长度”，这个bit位为0表示原文，为1表示“长度+距离”
2. 由于滑动窗口只有32k，如果我们对距离采用定长编码的话，最多用两个字节就可以表示。
3. 对于重复的长度我们也采用定长编码，并且规定最多一次匹配255个字符。这样的话用一个字节就可以表示
4. 由于“距离+长度”我们使用3个字节表示，所以当重复的字节数大于等于3的时候，才不会导致我们越压越大。
   

四、算法分析

在滑动窗口匹配数据的时候，我们可以将数据加载到内存中再进行匹配。但是只使用32K的窗口的话，每一次匹配的字符串我们都必须将前32k的内容重新加载一次，这样的话效率简直太低了。
为此，我们可以使用64k的缓存，将要匹配的位置的前32k和后32k内容都读到缓存中，这样的话，我们每处理32k的内容才读一次数据。

五、代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const size_t N = 2 * 32 * 1024;  //64k缓存
enum{ SlipBlock = 32 * 1024 };   //定义一个32K大小的滑块

typedef long long LongType;

class ZipCompress
{
private:
    vector<unsigned char> _windows; //滑块大小
    size_t _frist;
    size_t _last;
public:
    ZipCompress()
    {
        _windows.reserve(N); //开辟一个窗口，大小N
        _frist = 0;
        _last = 0;
    }

    string Compress(const string& filename)
    {
        return  _ZIP_FileCompress(filename);
    }

    string UnCompress(const string& filename)
    {
        return _ZIP_FileUnCompress(filename);
    }
private:
    string  _ZIP_FileCompress(const string& filename)
    {
        assert(filename.c_str());
        string FirstCompressFileName = filename;
        FirstCompressFileName += ".fzip";

        FILE* fInput = fopen(filename.c_str(), "rb+");
        assert(fInput);

        FILE* fOut = fopen(FirstCompressFileName.c_str(), "wb+");
        assert(fOut);

        FILE* pWindows = fopen(filename.c_str(), "rb+"); //定义指向滑动窗口起始位置
        assert(pWindows);

        int ch = 0;
        ch = fgetc(fInput);

        LongType count = 0;
        //从源文件中读入字符，再判断需不需要进行压缩，只有当重复的字符出现3个以上时才压缩
        unsigned char buf = 0;
        int flag = 7; //标记buf处理了几位

        while (ch != EOF)
        {
            long distance = 0;
            int length = 0;
            long OFFSET = ftell(fInput); //文件当前位置距离其实位置的偏移量

            //设置滑动窗口的大小
            if (OFFSET > SlipBlock)
            {
                fseek(pWindows, OFFSET - 1 - SlipBlock, SEEK_SET);//文件指针返回到滑动窗口的起始位置
                distance = SlipBlock;
            }
            else
            {
                fseek(pWindows, 0, SEEK_SET);//如果当前位置偏移量没有滑块大，将窗口指针设置在初始位置
                distance = OFFSET - 1;
            }

            if (distance > 1)
            {
                fseek(fInput, OFFSET - 1, SEEK_SET); //向前退回一个字符
                length = FindRepetition(pWindows, fInput, distance);
                fseek(fInput, OFFSET, SEEK_SET);
            }

            if (length > 0) //有重复的，用1表示有重复的
            {
                fseek(fInput, length - 1, SEEK_CUR);
                buf |= (1 << flag);  //先把flag这一标记 设置成1
                flag--;
                if (flag < 0)
                {
                    fputc(buf, fOut);
                    flag = 7;
                    buf = 0;
                }

                //接下来把distance和length写入
                int pos = 15;
                while (pos >= 0) //处理两个字符的distance
                {
                    if (distance&(1 << pos)) //如果length的第pos位为1
                        buf |= (1 << flag);  //向buf中写1
                    else
                    {
                        buf &= (~(1 << flag));
                    }
                    flag--;
                    if (flag < 0)
                    {
                        fputc(buf, fOut);
                        flag = 7;
                        buf = 0;
                    }
                    pos--;
                }
                pos = 7; //接下来写入Length
                while (pos >= 0)
                {
                    if (length&(1 << pos))  //如果length的第pos位为1
                        buf |= (1 << flag); //向buf中写1
                    else
                        buf &= (~(1 << flag));//向buf中写0
                    flag--;
                    if (flag < 0)       //buf这8位以处理完毕，进行写入
                    {
                        fputc(buf, fOut);
                        flag = 7;
                        buf = 0;
                    }
                    pos--;
                }
                count += 3;  //处理一个distance和一个length,count加三个字符
            }
            else  //这个是普通字符
            {
                buf &= (~(1 << flag));//把flag这一位设置成0
                flag--;
                if (flag < 0) //buf把这9位已经处理完毕准备写入
                {
                    fputc(buf, fOut);
                    flag = 7;
                    buf = 0;
                }

                //接下来处理ch这个字符
                int pos = 7;
                while (pos>=0)
                {
                    if (ch&(1 << pos)) //如果ch的第pos位为1
                        buf |= (1 << flag); //向buf中写1
                    else
                        buf &= (~(1 << flag));//向buf中写0
                    flag--;
                    if (flag < 0)
                    {
                        fputc(buf, fOut);
                        flag = 7;
                        buf = 0;
                    }
                    pos--;
                }
                count++;   //处理一个字符count++
            }
            ch = fgetc(fInput);
        }
        if (flag != 7) //如果最后的bit位不够一个整数，则就在后面补0
        {
            fputc(buf, fOut);
        }
        fwrite(&count, 1, 0, fOut);
        fclose(fInput);
        fclose(fOut);
        fclose(pWindows);
        return FirstCompressFileName;
    }
    string  _ZIP_FileUnCompress(const string& CompressFileName)
    {
        string UnCompressFileName = CompressFileName;
        UnCompressFileName += ".ufzip";

        FILE* fInput = fopen(CompressFileName.c_str(), "rb+");
        assert(fInput);

        FILE* fOut = fopen(UnCompressFileName.c_str(), "wb+");
        assert(fOut);

        FILE* pWindows = fopen(UnCompressFileName.c_str(), "rb+");
        assert(pWindows);

        LongType count;
        fseek(fInput, -8, SEEK_END);
        fread(&count, 1, 8, fInput);

        fseek(fInput, 0, SEEK_SET);
        //解压缩
        int c = 0;
        int ch = 0;
        ch = fgetc(fInput);

        unsigned char buf = 0;
        int status = 0; //用来记录现在是处理字符还是距离和长度
        int flag = 7;
        while (count>0)
        {
            int  distance = 0;
            int length = 0;
            status = ch&(1 << flag);//判断状态
            flag--;
            if (flag < 0)
            {
                ch = fgetc(fInput);
                flag = 7;
            }

            if (status != 0) //这一位为1，表示距离和长度
            {
                //还原distance,连续读取两个字符
                int pos = 15;
                while (pos>=0)
                {
                    if (ch&(1 << flag))
                    {
                        distance |= (1 << pos); //在这一位写1
                    }
                    else
                        distance &= (~(1 << pos));//在这一位写0
                    flag--;
                    if (flag < 0)
                    {
                        ch = fgetc(fInput);
                        flag = 7;
                    }
                    pos--;
                }
                //读取length
                pos = 7;
                while (pos>=0)
                {
                    if (ch&(1 << flag))
                        length |= (1 << pos); //这一位写1
                    else
                        length &= (~(1 << pos));
                    flag--;
                    if (flag < 0)
                    {
                        ch = fgetc(fInput);
                        flag = 7;
                    }
                    pos--;
                }

                //复制滑动窗口中重复的字符
                fflush(fOut);                   //将缓冲区的内容全部都写入文件
                int OFFSET = ftell(fOut);       //记录写入的位置；
                fseek(pWindows, OFFSET - distance, SEEK_SET); //让窗口指针指向窗口起始位置
                while (length--)
                {
                    int c = fgetc(pWindows);
                    fputc(c, fOut);
                }
                count -= 3;
            }
            else //源字符
            {
                int pos = 7;
                while (pos >= 0)
                {
                    if (ch&(1 << flag))
                        buf |= (1 << pos);
                    else
                        buf &= (~(1 << pos));
                    flag--;
                    if (flag < 0)
                    {
                        ch = fgetc(fInput);
                        flag = 7;
                    }
                    pos--;
                }
                fputc(buf, fOut);
                count--;
                buf = 0;
            }
        }
        fclose(fInput);
        fclose(fOut);
        fclose(pWindows);
        return UnCompressFileName;
    }
private:
    int FindRepetition(FILE* pWindows, FILE* fInput, long& distance)
    {
        long OFFSET1 = ftell(pWindows); //记录窗口距离文件开始的距离
        long OFFSET2 = ftell(fInput);   //记录当前要比较的字符串距离文件开始的距离
        int ch = 0;

        if ((size_t)OFFSET2 > _last)
        {
            _windows.clear();
            for (size_t i = 0; i < N; i++)
            {
                _windows.push_back(ch);
            }
            _frist = OFFSET1; //记录加载到窗口的数据的起始位置
            _last = _windows.size() + OFFSET1;
        }
        int length = GetRepetionlength(fInput, distance, OFFSET1);
        return length;
    }

    int   GetRepetionlength(FILE* fInput, long& distance, long pWindowsPos) //得到重复长度
    {
        long OFFSET = ftell(fInput);//得到要比较的字符的位置

        vector<unsigned char> v;
        if (Getch(fInput, v) == false)
        {
            return 0;
        }
        size_t size = OFFSET - pWindowsPos;
        size_t index = pWindowsPos - _frist;

        int length = 0;
        for (; index < size; ++index)
        {
            if (_windows[index] == v[0])
            {
                size_t flag = index;
                size_t i = 0;
                while ((flag < size) && (length < 255))
                {
                    if (i == v.size() - 1)
                    {
                        if (Getch(fInput, v) == false)
                            break;
                    }
                    if (_windows[flag] == v[i])
                    {
                        length++;
                        flag++;
                        i++;
                    }
                    else
                        break;
                }
                if (length >= 3)
                {
                    distance = OFFSET - (index + _frist);
                    return length;  //如果重复出现的字符长度大于3，则就返回重复长度
                }
                length = 0;
            }
        }
        return 0;
    }
    bool Getch(FILE* fInput, vector<unsigned char>& v)
    {
        int ch = 0;

        ch = fgetc(fInput);
        v.push_back(ch);

        if (ch == EOF)
            return false;
        else
            return true;
    }
};