Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.
=== Принцип скользящего окна ===
Приведенное выше сравнение процесса кодирования с «программированием» может натолкнуть на преждевременный вывод о том, что алгоритм LZ77 относится к [[Методы сжатия с использованием контекстного моделирования|методам контекстного моделирования]]. Поэтому следует отметить, что алгоритм LZ77 принято классифицировать как метод [[Методы сжатия с использованием словаря|словарного сжатия]] данных, когда вместо понятия «скользящего окна» используется термин «динамического словаря».
=== Механизм кодирования совпадений ===
Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие ''совпадения'' (от {{lang-en|match}}). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.
'''abra'''cad ''abra'' 7 4 abra
=== Реализация LZ77 на Си ===
<source lang="c">
/*==============================
Архивирование Алгоритм LZ77
Очень неоптимизированный вариант
Просьба обработать напильничком,
как следует.
==============================*/
#define DICBITS 12 // Log(DICSIZE)
#define DICSIZE (1<<DICBITS) // 4-32kB Размер словаря
#define THRESHOLD 2 // Порог
#define STRBITS 6 // Log(STRMAX-THRESHOLD)
#define STRMAX ((1<<STRBITS)+THRESHOLD) // Мах. длина строки
#define BUFSIZE 0xff00U // Полный размер буфера
#define TEXTSIZE (BUFSIZE-DICSIZE-STRMAX) // Размер буфера текста
#define YES 1
#define NO 0
FILE *first_file, *second_file;
long srcleng=0, fileleng;
unsigned char *srcbuf, *srcstart;
/*==============================
========Функция записи=========
==============================*/
int putbits(int data, int nbits)
{
static int bitcounter=0;
static int outdata=0;
int bit, error;
data<<=(16-nbits);
for( ; nbits > 0 ; nbits-- )
{
if( bitcounter == 8 )
{
bitcounter=0;
error=putc(outdata,second_file);
if( error == EOF )
{
printf("Error writing to Second file.");
return -5;
}
}
outdata<<=1;
bit=( data & 0x8000 ) ? 1:0;
outdata+=bit;
bitcounter++;
data<<=1;
}
}
/*==============================
======Функция Архивирования=====
==============================*/
void compress_stud()
{
// struct stat buf;
unsigned char *position, *pointer; //байт в файле , байт в буфере
int i, dist, offset=0, last=NO, cnt, maxleng;
printf("Compress started.");
// Записываем размер исходного файла
fstat(fileno(first_file),&buf);
fileleng=buf.st_size;
write(fileno(second_file), &fileleng, sizeof(long));
// Читаем файл в буфер по частям размера TEXTSIZE
while((srcleng=fread(srcstart+offset, 1, TEXTSIZE, first_file))>0)
{
if(srcleng < TEXTSIZE ) // Последняя часть текста
{
last=YES;
}
position=srcstart;
pointer=srcbuf;
srcleng+=offset;
while(srcleng>0)
{
printf("\n\nStep - %d\n",srcleng);
maxleng=0;
if((last == NO) && (srcleng < STRMAX)) // Если в буфере текста осталось мало символов, сдвигаем словарь и оставшийся текст в начало буфера и дочитываем следующую часть из файла
{
memcpy(srcbuf,pointer,DICSIZE+(int)srcleng);
offset=(int)srcleng;
break;
}
for( i=DICSIZE-1; i >= 0; i-- )// Ищем самую длинную совпадающую строку в словаре
{
for( cnt=0; cnt < STRMAX; cnt++ )
if( *(position+cnt) != *(pointer+i+cnt) )
break;
if( cnt <= THRESHOLD )// Если длина меньше порога, отбрасываем
continue;
if( cnt == STRMAX )// Если максимальная строка, дальше не ищем
{
dist=DICSIZE-1-i; //позиция
maxleng=STRMAX; //длина
break;
}
if( cnt > maxleng ) // Если очередная строка длиннее уже найденных, сохраняеМ ее длину и позицию
{
dist=DICSIZE-1-i; // позиция
maxleng=cnt; //длина
}
}
if( (last == YES) && (maxleng > srcleng) ) // Проверяем, чтобы не было выхода за границы файла
{
maxleng=(int)srcleng; //обрезаем длину по границу буфера
}
if( maxleng > THRESHOLD )//Если строка достаточно длинная, формируем pointer-код
{
printf("link!\n");
putbits(1,1); //помечаем как ссылку
putbits(dist,DICBITS); //записываем позицию
putbits(maxleng-THRESHOLD-1,STRBITS); //записываем длину
position+=maxleng;
srcleng-=maxleng;
pointer+=maxleng;
}
else // Иначе - chr-код
{
printf("Char!\n");
putbits(0,1); //помечаем как chr-код
putbits(*position,8); //записываем чар код
position++;
srcleng--;
pointer++;
}
}
}
// Записываем оставшиеся биты
putbits(0,8);
printf("\nCompress completed!\n",fileleng);
}
//Разархивирование Алгоритм LZ77
/*==============================
======Функция считывания========
==============================*/
int getbits(int nbits)
{
static int bitcounter=8;
static int indata=0;
int bit, data=0;
for( ; nbits > 0 ; nbits-- )
{
if( bitcounter == 8 )
{
bitcounter=0;
indata=getc(first_file);
}
if( indata == EOF )
{
printf("Error writing to First file.");
return -6;
}
bit=( indata & 0x80 ) ? 1:0;
data<<=1;
data+=bit;
bitcounter++;
indata<<=1;
}
return data;
}
/*==============================
=======Функция Извлечения=======
==============================*/
void decompress_stud()
{
struct stat buf;
unsigned char *pos;
int i, dist, ch, maxleng;
printf("Decompress started.\n");
// Получаем длину исходного файла
read(fileno(first_file),&fileleng,sizeof(long));
pos=srcstart;
while( fileleng > 0 )
{
if( (ch=getbits(1)) == 0 ) // Если chr-код, копируем в буфер текста символ
{
ch=getbits(8);
putc(ch,second_file);
*pos=ch;
pos++;
fileleng--;
}
else // Иначе - копируем maxleng символов из словаря, начиная с позиции dist
{
dist=getbits(DICBITS)+1;
maxleng=getbits(STRBITS)+THRESHOLD+1;
for( i=0; i < maxleng; i++ )
{
*(pos+i)=*(pos+i-dist);
putc(*(pos+i-dist),second_file);
}
pos+=maxleng;
fileleng-=maxleng;
}
if( pos > srcstart+TEXTSIZE ) // Если буфер заполнен, записываем его на диск и сдвигаем словарь в начало буфера
{
memcpy(srcbuf,pos-DICSIZE,DICSIZE);
pos=srcstart;
}
}
printf("\nDecompress completed.");
}
</source>
{{скрытый текст}}
<!--
