Интернет магазин китайских планшетных компьютеров



Компьютеры - LZ77

26 июня 2011


Оглавление:
1. LZ77
2. LZ78



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

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

LZ77

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

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

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

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

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

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

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

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

  • длина совпадения
  • смещение или дистанция

В продолжение уже приведенной аналогии с программированием отметим, что в большинстве статей, посвященных алгоритму 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
#define DICSIZE     // 4-32kB Размер словаря
#define THRESHOLD 2              // Порог
#define STRBITS   6              // Log
#define STRMAX   +THRESHOLD) // Мах. длина строки
#define BUFSIZE   0xff00U        // Полный размер буфера
#define TEXTSIZE  // Размер буфера текста
#define YES       1
#define NO        0
 
FILE *first_file, *second_file;
long srcleng=0, fileleng;
unsigned char *srcbuf, *srcstart;
/*==============================
========Функция записи=========
==============================*/
int putbits
{
        static int bitcounter=0;
        static int outdata=0;
        int bit, error;
        data<<=;
        for
        {
                if
                {
                        bitcounter=0;
                        error=putc;
                        if
                        { 
                                printf; 
                                return -5; 
                        }
                }
        outdata<<=1;
        bit= ? 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;
 
        // Записываем размер исходного файла
 
        fstat,&buf);
        fileleng=buf.st_size;
        write, &fileleng, sizeof);
 
        // Читаем файл в буфер по частям размера TEXTSIZE 
        while)>0)
        {
                if // Последняя часть текста 
                {
                        last=YES; 
                }
                position=srcstart;
                pointer=srcbuf;
                srcleng+=offset;
                while
                {
                        printf;
                        maxleng=0;
 
                        if && ) // Если в буфере текста осталось мало символов, сдвигаем словарь и оставшийся текст в начало буфера и дочитываем следующую часть из файла 
                        {
                                memcpysrcleng);
                                offset=srcleng; 
                                break;
                        }
 
                        for// Ищем самую длинную совпадающую строку в словаре
                        {
                                for
                                if != * ) 
                                break;
 
                                if// Если длина меньше порога, отбрасываем 
                                continue;
 
                                if// Если максимальная строка, дальше не ищем 
                                {
                                        dist=DICSIZE-1-i; //позиция
                                        maxleng=STRMAX; //длина
                                        break; 
                                }
 
                                if // Если очередная строка длиннее уже найденных, сохраняеМ ее длину и позицию
                                {
                                        dist=DICSIZE-1-i; // позиция
                                        maxleng=cnt; //длина
                                }
                        }
 
                        if &&  ) // Проверяем, чтобы не было выхода за границы файла
                        {
                                maxleng=srcleng; //обрезаем длину по границу буфера
                        }
 
                        if//Если строка достаточно длинная, формируем pointer-код
                        {
                                printf;
                                putbits; //помечаем как ссылку
                                putbits; //записываем позицию
                                putbits; //записываем длину
                                position+=maxleng;
                                srcleng-=maxleng;
                                pointer+=maxleng;
                        }
                        else // Иначе - chr-код
                        { 
                                printf;
                                putbits;  //помечаем как chr-код
                                putbits; //записываем чар код
                                position++; 
                                srcleng--; 
                                pointer++;
                        }
                }
        }
 
        // Записываем оставшиеся биты 
        putbits;
 
        printf;
}
 
//Разархивирование Алгоритм  LZ77
 
/*==============================
======Функция считывания========
==============================*/
int getbits
{
        static int bitcounter=8;
        static int indata=0;
        int bit, data=0;
 
        for
        {
                if
                { 
                        bitcounter=0; 
                        indata=getc; 
                }
 
                if
                { 
                        printf; 
                        return -6; 
                }
 
                bit= ? 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;
 
        // Получаем длину исходного файла
        read,&fileleng,sizeof);
        pos=srcstart;
 
        while
                {
                if) == 0 ) // Если chr-код, копируем в буфер текста символ 
                {
                        ch=getbits; 
                        putc; 
                        *pos=ch; 
                        pos++; 
                        fileleng--; 
                }
                else // Иначе - копируем maxleng символов из словаря, начиная с позиции dist
                {
                        dist=getbits+1; 
                        maxleng=getbits+THRESHOLD+1;
                        for
                        {
                                *=*; 
                                putc,second_file); 
                        }
                        pos+=maxleng; 
                        fileleng-=maxleng;
                }
 
                if // Если буфер заполнен, записываем его на диск и сдвигаем словарь в начало буфера
                {
                        memcpy;
                        pos=srcstart;
                }
        }
        printf;
}


Просмотров: 2216


<<< LZ