Словарные методы сжатия данных

Пример

Попробуем сжать строку "кот_ломом_колол_слона" длиной 21 символ. Пусть длина буфера равна 7 символам, а размер словаря больше длины сжимаемой строки. Условимся также, что:

Для кодирования i нам достаточно 5 битов, для j нужно 3 бита, и пусть символы требуют 1 байта для своего представления. Тогда всего мы потратим 12·(5+3+8) = 192 бита. Исходно строка занимала 21·8 = 168 битов, т.е. LZ77 кодирует нашу строку еще более расточительным образом. Не следует также забывать, что мы опустили шаг кодирования конца последовательности, который потребовал бы еще как минимум 5 битов (размер поля i = 5 битам).

Процесс кодирования можно описать следующим образом.

while ( ! DataFile.EOF() ){
    /*найдем максимальное совпадение, в match_pos получим 
    смещение i, в match_len - длину j, в unmatched_sym 
    - первый несовпавший символ st+1+j; считаем также, что в 
    функции find_match учитывается ограничение на длину 
    совпадения 
    */
  
    find_match (match_pos, match_len, unmatched_sym);
    /*запишем в файл сжатых данных описание найденной 
    фразы, при этом длина битового представления i 
    задается константой OFFS_LN, длина представления 
    j - константой LEN_LN, размер символа s принимаем 
    равным 8 битам
    */
  
    CompressedFile.WriteBits (match_pos, OFFS_LN);
    CompressedFile.WriteBits (match_len, LEN_LN);
    CompressedFile.WriteBits (unmatched_sym, 8);
    for (i = 0; i <= match_len; i++){
      // прочтем очередной символ
      
      c = DataFile.ReadSymbol();     
      //удалим из словаря одну самую старую фразу
      
      DeletePhrase ();
      /*добавим в словарь одну фразу, начинающуюся с 
      первого символа буфера
      */
      
      AddPhrase ();
      /*сдвинем окно на 1 позицию, добавим в конец буфера 
      символ с
      */
      
      MoveWindow(c);
    }
  }
  
  CompressedFile.WriteBits (0, OFFS_LN);

Пример подтвердил, что способ формирования кодов в LZ77 неэффективен и позволяет сжимать только сравнительно длинные последовательности. До некоторой степени сжатие небольших файлов можно улучшить, используя коды переменной длины для смещения i. Действительно, даже если мы используем словарь в 32 кбайт, но закодировали еще только 3 кбайт, то смещение реально требует не 15, а 12 битов. Кроме того, происходит существенный проигрыш из-за использования кодов одинаковой длины при указании длин совпадения j. Например, для уже упоминавшейся электронной версии романа "Бесы" были получены следующие частоты использования длин совпадения (см. табл. 2.4):

Из таблицы следует, что в целях минимизации закодированного представления для j = 6 следует использовать код наименьшей длины, так как эта длина совпадения встречается чаще всего.

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

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

Алгоритм декодирования может иметь следующий вид.

for (;;) {
    // читаем смещение
    match_pos = CompressedFile.ReadBits (OFFS_LN);
  
    if (!match_pos)
      // обнаружен признак конца файла, выходим из цикла
      break;   
    
    // читаем длину совпадения
    match_len = CompressedFile.ReadBits (LEN_LN);

    for (i = 0; i < match_len; i++) {
      //находим в словаре очередной символ совпавшей фразы
      
      c = Dict (match_pos + i);
      
      /*сдвигаем словарь на 1 позицию, добавляем в его начало с */
      MoveDict (c)
    
      /*записываем очередной раскодированный символ в 
      выходной файл */
      DataFile.WriteSymbol (c);
    }
    
    /*читаем несовпавший символ, добавляем его в словарь и 
    записываем в выходной файл
    */
    
    c = CompressedFile.ReadBits (8);
    MoveDict (c)
    DataFile.WriteSymbol (c);
  }

Алгоритмы со скользящим окном характеризуются сильной несимметричностью по времени - кодирование значительно медленнее декодирования, поскольку при сжатии много времени тратится на поиск фраз.

Алгоритм LZSS

Алгоритм LZSS позволяет достаточно гибко сочетать в выходной последовательности символы и указатели (коды фраз), что до некоторой степени устраняет присущую LZ77 расточительность, проявляющуюся в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski) [2.10].

Идея алгоритма заключается в добавление к каждому указателю и символу однобитового префикса $$f$$, позволяющего различать эти объекты. Иначе говоря, однобитовый флаг $$f$$ указывает тип и, соответственно, длину непосредственно следующих за ним данных. Такая техника позволяет:

Пример

Закодируем строку "кот_ломом_колол_слона" из предыдущего примера и сравним коэффициент сжатия для LZ77 и LZSS.

Пусть мы переписываем символ в явном виде, если текущая длина максимального совпадения буфера и какой-то фразы словаря меньше или равна 1. Если мы записываем символ, то перед ним выдаем флаг со значением 0, если указатель - то со значением 1. Если имеется несколько совпадающих фраз одинаковой длины, то выбираем ближайшую к буферу.

Процесс кодирования представлен в табл. 2.5

Таким образом, для кодирования строки по алгоритму LZSS нам потребовалось 17 шагов: 13 раз символы были переданы в явном виде, и 4 раза мы применили указатели. Заметим, что при работе по алгоритму LZ77 нам потребовалось всего лишь 12 шагов. С другой стороны, если задаться теми же длинами для i и j, то размер закодированных по LZSS данных равен 13·(1+8) + 4·(1+5+3) = 153 битам. Это означает, что строка действительно была сжата, так как ее исходный размер 168 битов.

Рассмотрим алгоритм сжатия подробнее.

const int THRESHOLD = 1, // порог для включения словарного кодирования
  // размер представления смещения, в битах
  OFFS_LN = 14,
  
  // размер представления длины совпадения, в битах
  LEN_LN = 4; 

  const int WIN_SIZE = (1 << OFFS_LN), // размер окна
  BUF_SIZE = (1 << LEN_LN) - 1; // размер буфера
  
  //функция вычисления реального положения символа в окне
  inline int MOD (int i) { return i  (WIN_SIZE-1); };
  
  ...

  //собственно алгоритм сжатия
  int buf_sz = BUF_SIZE;

  /* инициализация: заполнение буфера, поиск совпадения
    для первого шага*/
  while ( buf_sz ) {
    if ( match_len > BUF_SIZE) match_len = BUF_SIZE;
    if ( match_len <= THRESHOLD ) {
      /*если длина совпадения меньше порога (1 в 
      примере), то запишем в файл сжатых данных флаг и 
      символ; pos определяет позицию начала буфера*/
  
      CompressedFile.WriteBit (0);
      CompressedFile.WriteBits (window [pos], 8);
      // это понадобится при обновлении словаря
      
      match_len = 1; 
    }else{
      /*иначе запишем флаг и указатель, состоящий из 
      смещения и длины совпадения
      */
    
      CompressedFile.WriteBit (1);
      CompressedFile.WriteBits (match_offs, OFFS_LN);
      CompressedFile.WriteBits (match_len, LEN_LN);
    }

    for (int i = 0; i < match_len; i++) {
      /*удалим из словаря фразу, начинающуюся в позиции 
      MOD (pos+buf_sz)
      */
    
      DeletePhrase ( MOD (pos+buf_sz) );
      if ( (c = DataFile.ReadSymbol ()) == EOF) buf_sz--;
      // мы в конце файла, надо сократить буфер
       else window [MOD (pos+buf_sz)] = c;
      /*иначе надо добавить в конец буфера новый символ*/

      pos = MOD (pos+1); // сдвиг окна на 1 символ
    
      if (buf_sz) AddPhrase (pos, match_offs, match_len);
      /*если в буфере еще что-то есть, то добавим в 
      словарь новую фразу, начинающуюся в позиции pos; 
      считаем, что в функции AddPhrase одновременно 
      выполняется поиск максимального совпадения 
      между буфером и фразами словаря
      */
    }
  }
  CompressedFile.WriteBit (1); 
  CompressedFile.WriteBits (0, OFFS_LN); // знак конца файла
}

Алгоритм LZ78

Алгоритм LZ78 был опубликован в 1978 году [2.13], и впоследствии стал "отцом" семейства словарных методов LZ78.

Алгоритмы этой группы не используют скользящего окна и в словарь помещают не все встречаемые при кодировании строки, а лишь "перспективные" с точки зрения вероятности последующего использования. На каждом шаге в словарь вставляется новая фраза, которая представляет собой сцепление (конкатенацию) одной из фраз S словаря, имеющей самое длинное совпадение со строкой буфера, и символа s. Символ s является символом, следующим за строкой буфера, для которой найдена совпадающая фраза S. В отличие от семейства LZ77, в словаре не может быть одинаковых фраз.

Кодер порождает только последовательность кодов фраз. Каждый код состоит из номера (индекса) n "родительской" фразы S, или префикса, и символа s.

В начале обработки словарь пуст. Далее, теоретически, словарь может расти бесконечно, т.е. на его рост сам алгоритм не налагает ограничений. На практике при достижении определенного объема занимаемой памяти словарь должен очищаться полностью или частично.

Пример

И еще раз закодируем строку "кот_ломом_колол_слона" длиной 21 символ. Для LZ78 буфер, в принципе, не требуется, поскольку достаточно легко так реализовать поиск совпадающей фразы максимальной длины, что последовательность незакодированных символов будет просматриваться только один раз. Поэтому буфер показан только с целью большей доходчивости примера. Фразу с номером 0 зарезервируем для обозначения конца сжатой строки, номером 1 будем задавать пустую фразу словаря.

Строку удалось закодировать за 13 шагов. Так как на каждом шаге выдавался один код, сжатая последовательность состоит из 13 кодов. Возможно использование 15 номеров фраз (от 0 до 14), поэтому для представления n посредством кодов фиксированной длины нам потребуется 4 бита. Тогда размер сжатой строки равен 13·(4+8) = 156 битам.

Ниже приведен пример реализации алгоритма сжатия LZ78.

n = 1;
  while ( ! DataFile.EOF() ){
    s = DataFile.ReadSymbol; // читаем очередной символ
    /*пытаемся найти в словаре фразу, представляющую 
    собой конкатенацию родительской фразы с номером n и 
    символа s; функция возвращает номер искомой фразы 
    в phrase_num; если же фразы нет, то phrase_num 
    принимает значение 1, т.е. указывает на пустую фразу
    */

    FindPhrase (phrase_num, n, s);
    if (phrase_num != 1) n = phrase_num;
      /*такая фраза имеется в словаре, продолжим поиск 
      совпадающей фразы максимальной длины
      */
    else {
      /*такой фразы нет, запишем в выходной файл код;
      INDEX_LN - это константа, определяющая длину 
      битового представления номера n
      */
      
      CompressedFile.WriteBits (n, INDEX_LN);
      CompressedFile.WriteBits (s, 8);    
      AddPhrase (n, s); // добавим фразу в словарь  
      n = 1; // подготовимся к следующему шагу
    }  
  }
  
  // признак конца файла
  CompressedFile.WriteBits (0, INDEX_LN);

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

for (;;){
    // читаем индекс родительской фразы
    n = CompressedFile.ReadBits (INDEX_LN);
    
    if (!n) break; // конец файла
    
    // читаем несовпавший символ s
    s = CompressedFile.ReadBits (8);
    
    /*находим в словаре позицию начала фразы с индексом n 
    и ее длину
    */
  
    GetPhrase (pos, len, n)
    /*записываем фразу с индексом n в файл 
    раскодированных данных
    */
  
    for (i = 0; i < len; i++) DataFile.WriteSymbol (Dict[pos+i]);
    // записываем в файл символ s
    DataFile.WriteSymbol (s); 
    AddPhrase (n, s); // добавляем новую фразу в словарь
  }

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

Несмотря на относительную быстроту кодирования LZ78, при грамотной реализации алгоритма оно все же медленнее декодирования, соотношение скоростей равно обычно 3:2.

Интересное свойство LZ78 заключается в том, что если исходные данные порождены источником с определенными характеристиками (он должен быть стационарнымМногомерные распределения вероятностей генерации последовательностей (слов) из n символов не меняются во времени, причем n - любое конечное число и эргодическимСреднее по времени равно среднему по числу реализаций; иначе говоря, для оценки свойств источника достаточно только одной длинной сгенерированной последовательности ), то коэффициент сжатия приближается по мере кодирования к минимальному достижимому [2.13]. Иначе говоря, количество битов, затрачиваемых на кодирование каждого символа, в среднем равно так называемой энтропии источника. Но, к сожалению, сходимость медленная, и на данных реальной длины алгоритм ведет себя не лучшим образом. Так, например, коэффициент сжатия текстов в зависимости от их размера обычно колеблется от 3.5 до 5 битов/символ. Кроме того, нередки ситуации, когда обрабатываемые данные порождены источником с ярко выраженной нестационарностью. Поэтому при оценке реального поведения алгоритма следует относиться с большой осторожностью к теоретическим выкладкам, обращая внимание на выполнение соответствующих условий.

Доказано, что аналогичным свойством сходимости обладает и классический алгоритм LZ77, но скорость приближения к энтропии источника меньше, чем у алгоритма LZ78 [2.12].

Список архиваторов и компрессоров