本文主要是介绍LZ77编码和部分实现 20级孙溢，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LZ77编码
由Ziv和Lempel于1977年提出，故称为LZ77算法。
编码器通过一个滑动窗口来查看输入序列，其中滑动窗口包含搜索缓冲区和前瞻缓冲区，
搜索缓冲区包含字典——最近编码的数据，而前瞻缓冲区包含要编码的输入数据序列的下一部分，滑动窗口的尺寸是影响压缩性能的关键因素。编码过程为：编码前瞻缓冲区，编码器在编码时会一直在搜索缓冲区搜索直到找到最大匹配字符串。匹配字符串的开始字符串与前瞻缓冲区的距离为“偏移值P”，匹配字符串的长度称为“匹配长度L”。滑动窗口会根据匹配长度向右滑动相应的距离。以 （P，L）a 格式向预编译器发送，其中 （P，L） 是指向匹配项的指针，其中发送的格式分为两种情况：
1.当前瞻缓冲区出现一个搜索缓冲区中没有的字符时，发送为a
2.当前瞻缓冲区的字符能在搜索缓冲区检测到，则发送（P，L）,为没有显示字节的指针。
例如编码ABCBBABCB，设置搜索缓冲区的长度为5，前瞻缓冲区的长度为3，编码过程如下：
- Step1
搜索缓冲区为空，输出结果（0，0）A，窗口右移一位。
- Step2
搜索缓冲区中无B，输出结果为（0，0）B，窗口右移一位。
- Step3
搜索缓冲区中无C，输出结果为（0，0）C，窗口右移一位。
- Step4
搜索缓冲区中有B，偏移量为2，匹配长度为1，输出结果为（2，1），窗口右移一位。
- Step5
搜索缓冲区中有B，由于是从头开始搜索，离第一个B的距离为3，则偏移量为3，匹配长度为1，输出结果为（3，1），窗口右移一位。
- Step6
搜索缓冲区最大匹配字符串为ABC，偏移量为5，匹配长度为3，输出结果为（5，3），窗口右移三位。
- Step7
搜索缓冲区中有B，偏移量为5，匹配长度为1，输出结果为（5，1）,窗口右移一位。
- Step8
前瞻缓冲区中无字符，编码结束。
 |
解码部分的思路如下：
输入指针为（P，L）a，其中 （P，L） 是指向匹配项的指针，这时向解码器提供以下指令：在窗口中返回 P 字节并将 L字节复制到输出。a 是显式字节。
在这里，主要阐述一下编码的算法实现，未做解码部分。
仍以ABCBBABCB为例，设信源发出的消息字符序列为(xi ,0<i<10),
设 xi前i-1个字符已被压缩，当前位置为 xi ，存储记忆容量为 i-1，即只有i-1 长的历史数据可用。在前i-1个字符中寻找是否出现过 xi，如果没有出现过，则记为(0,xi )，然后继续处理 xi之后的字符。如果出现过xi，从搜索缓冲区的第一个字符开始寻找相对应的xi，与此同时，搜索缓冲区的xi和当前的xi都需要向后检索，寻找是否有相同的字符，直到无相同的字符为止，此时字符的个数就是最大匹配长度L。 要注意搜索缓冲区也要相应地向前移L个单位。
编码后的结果应为ABC（2，1）（3，1）（5，3）（5，1），由于不确定是原始字符还是指针，在这里加上预编译头，原始字符前加0，指针类型加1。即输出为（0，A）（0，B）（0，C）（1，2，1）（1，3，1）（1，5，3）（1，5，1），再转换为ASCALL码输出。
部分代码实现，由于不太清楚怎么定位偏移量，和根据编码的长度来移动缓冲区，所以只能实现从ABCBB的输出。
#include<stdio.h>
char lookahead[3];
char search[5];
char input[9]={'A','B','C','B','B','A','B','C','B'};
int trans();
void main()
{
int i=0,j;
for(i;i<3;i++)
trans2(input[i]);//将ABC转换成ASCLL码输出
for(j=2,i=0;j<5;j++)
{
search[j]=input[i];//将ABC移进搜索缓冲区
i++;
}
for(j=3,i=0;i<3;i++)
{
lookahead[i]=input[j];//将BBA输入前瞻缓冲区
j++;
//printf("%d\n",lookahead[i]);
}
for(i=2;i<5;i++)
{
int j=0;
if (lookahead[j]==search[i])
{
if(lookahead[j+1]==search[i+1])
{
if(lookahead[j+2]==search[j+2])
{
printf("%d\n",33);}//偏移长度为3，最大匹配长度也为3
else
printf("%d\n",32);//偏移长度为3，最长匹配长度为2
}
else
printf("%d\n",31);
j=3;
}
else
{
if (lookahead[j]==search[i+1])
{
if(lookahead[j+1]==search[i+2])
printf("%d\n",22);
else
printf("%d\n",21);
j=2;
}
else
{
if(lookahead[j]==search[i+2])
printf("%d/n",11);
j=1;
}
}
}//此时j为偏移值
for(i=0;i<3+j;i++)
search[i]=input[i];
printf("%d\n",search[i]);//更新搜索区的值
}
int trans(char v)
{
int a,b,k,i;
int remainder[30];
a=(int)v;
k=0;
while(a!=0)
{
b=a/2;
k++;
remainder[k]=a-b*2;
a=a/2;
}
for (i=k; i>=1; i--)
{
printf("%d",remainder[i]);
}
printf("\n\n");
return 0;
}//将字符转换成二进制输出
这篇关于LZ77编码和部分实现 20级孙溢的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
