Ef2a36908f1daa4f6c90ebc85e38bec4
LZ77数据压缩算法

1 前言

  数据压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。

2 概述

  Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法(A Universal Algorithm for Sequential Data Compression )”的论文,论文中描述的算法被后人称为LZ77算法。值得说的是,LZ77严格意义上来说不是一种算法,而是一种编码理论。

3 重点概念

3.1 前向缓冲区

  前向缓冲区为待编码区的一段编码。例如待编码数据为ABBCA,选取前向缓冲区数据大小为4,则开始编码时的前向缓冲区中的数据为ABBC。

3.2 滑动窗口

  滑动窗口是个历史缓冲器,它被用来存放输入流的前n个字节的有关信息。在每一次匹配之后,滑动窗口需要向前滑动。滑动的距离根据匹配的结果决定。

4 算法流程

(1)设置编码位置为输入流的开始
(2)在滑窗的待编码区查找搜索区中的最大匹配字符串
(3)如果找到字符串,输出(偏移值, 匹配长度), 窗口向前滑动“匹配长度”
(4)如果没有找到,输出待编码区的第一个字符,窗口向前滑动一个单位
(5)如果待编码区不为空,回到步骤2

  例如有字符串:ABABCBABABCAD。设置滑动窗口大小为8,前向缓冲区大小为4。说明字符串的压缩过程

编码过程:



解码过程:


  通过数据的编码与解码过程可以看出LZ77为无损压缩算法。

5 代码实现

编码代码:

```

//lz77编码压缩过程
int lz77_compress(const unsigned char *original, unsigned char **compressed, int size)
{
unsigned char window[LZ77_WINDOW_SIZE], buffer[LZ77_BUFFER_SIZE], *comp, *temp, next;
int offset, length, remaining, hsize, ipos, opos, tpos, i;
int token, tbits;

//初始化 
*compressed = NULL;
memset(window, 0, LZ77_WINDOW_SIZE);
memset(buffer, 0, LZ77_BUFFER_SIZE);

//向头信息中写入源数据字节数 
hsize = sizeof(int);
comp = (unsigned char *)malloc(hsize);
memcpy(comp, &size, sizeof(int)); 

ipos = 0;//ipos指向源数据中正在处理的字节
//从源数据中取数据到缓冲区中 
for(i = 0; i < LZ77_BUFFER_SIZE && ipos < size; i++)
{
    buffer[i] = original[ipos];
    ipos++;
} 

opos = hsize * 8;//opos是压缩数据bit的位置 
remaining = size;

while(remaining > 0)
{
    //标记 = type + offset(在window中) + length + next 
    //next就是不匹配的字符  
    //tbit表示生成标记长度 
    if((length = compare_win(window, buffer, &offset, &next)) != 0)
    {
        //能找到type为1 
        token = 0x0000_0001 << (LZ77_PHRASE_BITS - 1);
        token = token | (offset << LZ77_PHRASE_BITS - LZ77_TYPE_BITS - LZ77_WINOFF_BITS);
        token = token | (length << LZ77_PHRASE_BITS - LZ77_TYPE_BITS - LZ77_WINOFF_BITS - LZ77_BUFLEN_BITS);
        token = token | next;

        tbits =  LZ77_PHRASE_BITS;
    }
    else
    {
        //没找到 ,标记就是原符号 
        token = 0x0000_0000;
        token = token | next;

        tbits = LZ77_SYMBOL_BITS;
    } 

    //s数据处理为大端模式 
    token = htonl(token);

    //往压缩区填数据
    for(i = 0; i < tbits; i++)
    {
        if(opos % 8 == 0)
        {
            temp = (unsigned char *)realloc(comp, (opos / 8) + 1);
            comp = temp;
        }

        //根据长度tbits取一位一位压缩
        tpos = (sizeof(unsigned long) * 8) - tbits + i; 
        bit_set(comp, opos, bit_get((unsigned char *)&token, tpos));
    } 

    length++;//length是匹配数据字节长度

    //左移更新window把buffer中以编码的字符移到window 
    memmove(&window[0], &window[length], LZ77_WINDOW_SIZE - length); 
    memmove(&window[LZ77_WINDOW_SIZE - length], &buffer[0], length);

    //更新buffer中内容,做移除已经编码的字符,从源数据中调入新字符 
    memmove(&buffer[0], &buffer[length], LZ77_BUFFER_SIZE - length);
    for(i = LZ77_BUFFER_SIZE - length; (i < LZ77_BUFFER_SIZE) &&(ipos < size); i++)
    {
        buffer[i] = original[ipos];
        ipos++;
    }
    remaining = remaining - length;

} 

*compressed = comp;
return ((opos - 1) / 8) + 1; 

}

//从window中匹配buffer中最长字符串;offset返回window中匹配首位置;next返回buffer字符串后不匹配第一个字符位置
//返回匹配最长字符串的长度
static int compare_win(const unsigned char *window, const unsigned char *buffer, int *offset, unsigned char *next)
{
int match, longest, i, j, k;
*offset = 0;
longest = 0;
*next = buffer[0];

//最外面循环在window中第1个字符-第n个字符,第2个-第n个一个....., 第n-1个到第n个 
for(k = 0; k < LZ77_WINDOW_SIZE; k++)
{
    i = k;
    j = 0;
    match = 0;

    //在最外层循环的一个中找buffer能匹配的最长字符串 (从buffer第一个符号开始) 
    while(i < LZ77_WINDOW_SIZE && j < LZ77_BUFFER_SIZE - 1)
    {
top Created with Sketch.