Алгоритмы LZ77 и LZ78

LZ77 и LZ78 — алгоритмы сжатие без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы. Оба алгоритма относятся к словарным методам. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78.

LZ77

Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в RLE.

Принципы работи алгоритма

Основная суть алгоритма заключается ето замена повторно вхождения строки ссылкою на предыдущую позицию.

Принцип скользящего окна

Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.

Приведенное выше сравнение процесса кодирования с «программированием» может натолкнуть на преждевременный вывод о том, что алгоритм LZ77 относится к методам контекстного моделирования. Поэтому следует отметить, что алгоритм LZ77 принято классифицировать как метод словарного сжатия данных, когда вместо понятия «скользящего окна» используется термин «динамического словаря».

Механизм кодирования совпадений

Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие совпадения (от Шаблон:Lang-en). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.

В стандартном алгоритме LZ77 совпадения кодируются парой:

• длина совпадения (match length)
• смещение (offset) или дистанция (distance)

В продолжение уже приведенной аналогии с программированием отметим, что в большинстве статей, посвященных алгоритму LZ77, кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в буфере символов на значение смещения и скопировать значение длины символов, начиная с текущей позиции».

Хотя для приверженцев императивного программирования такая интерпретация может показаться интуитивно понятной, она, к сожалению, мало говорит о сущности алгоритма LZ77 как метода сжатия. Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары длина-смещение является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары длина-смещение. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму RLE.

Недостатки

• невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря
• длина подстроки, которую можно закодировать, ограничена размером буфера
• малая эффективность при кодировании незначительного объёма данных

Пример "abracadabra"

              Поз.  Длина    Симв.
 abracadabra    0      0      a
a bracadabra    0      0      b
ab racadabra    0      0      r
abr acadabra    3      1      c
abrac adabra    2      1      d	
abracad abra    7      4      abra

Реализация LZ77 на Си

<source lang="c"> /*============================== Архивирование Алгоритм LZ77 Очень неоптимизированный вариант Просьба обработать напильничком,

                   как следует.

==============================*/

1. define DICBITS 12 // Log(DICSIZE)
2. define DICSIZE (1<<DICBITS) // 4-32kB Размер словаря
3. define THRESHOLD 2 // Порог
4. define STRBITS 6 // Log(STRMAX-THRESHOLD)
5. define STRMAX ((1<<STRBITS)+THRESHOLD) // Мах. длина строки
6. define BUFSIZE 0xff00U // Полный размер буфера
7. define TEXTSIZE (BUFSIZE-DICSIZE-STRMAX) // Размер буфера текста
8. define YES 1
9. 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> Шаблон:Скрытый текст

LZ78

В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует «скользящее» окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу.

Ссылки

• Jacob Ziv, Abraham Lempel. A Universal Algorithm for Sequential Data Compression IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.
• Пример работы алгоритма LZ77 (см. example "abracadabra")
• Описание алгоритма LZ77 в курсе лекций по теории кодирования информации
• Описание алгоритма LZ78 в курсе лекций по теории кодирования информации