LZ77


LZ77

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

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

Содержание

LZ77

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

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

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

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

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

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

Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие совпадения (от англ. match). Рассмотрим последовательность из 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      ac
abrac adabra    2      1      ad   
abracad abra    7      4      abra

Выделенные символы отсутствуют в кодирующей последовательности.

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

/*==============================
Архивирование Алгоритм  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.");
}

LZ78

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

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "LZ77" в других словарях:

  • LZ77 — ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zunutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz dazu… …   Deutsch Wikipedia

  • LZ77 — et LZ78 LZ77 et LZ78 sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente… …   Wikipédia en Français

  • LZ77/78 — …   Википедия

  • LZ77 — ● np. m. ►PACK Première version de l algorithme de compression par substitution, publiée en 1977. Son principe est de garder en mémoire les données déjà rencontrées, et quand on rencontre une phrase déjà vue, on la supprime pour ne garder que la… …   Dictionnaire d'informatique francophone

  • LZ77 and LZ78 — are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively [http://www.patentstorm.us/patents/5532693 description.html] .… …   Wikipedia

  • LZ77 et LZ78 — sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d où leurs noms). Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel… …   Wikipédia en Français

  • LZ77 Et LZ78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… …   Wikipédia en Français

  • Lz77 et lz78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… …   Wikipédia en Français

  • LZ77 (Begriffsklärung) — LZ77 ist Bezeichnung für: ein Verfahren zur Datenkompression, siehe LZ77 zwei verschiedene Luftschiffe von Zeppelin während des Ersten Weltkrieges, siehe: Liste aller Zeppeline Baunummer LZ 47 trug die militärische Bezeichnung LZ 77 Baunummer LZ… …   Deutsch Wikipedia

  • LZ 77 — LZ77 ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zu Nutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.