ROLZ

ROLZ (от англ. Reduced Offset LZ — алгоритм Лемпела-Зива с сокращёнными смещениями) — словарный алгоритм сжатия данных, близкий к LZ77, но использующий некоторые контекстные приёмы для уменьшения числа активных смещений. Само понятие ROLZ впервые ввёл Malcolm Taylor в своём архиваторе RK в 1999 году и данный алгоритм является одним из наиболее современных подходов к построению быстрых эффективных алгоритмов сжатия.

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

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

Проблема этой схемы в том, что при кодировании имеется избыточность. Например, при размере словаря в 4 Кбайт имеется 4096 вариантов смещения. Понятно, что большинство смещений не будет использовано, и если из 4096 вариантов используется, например, только 512, то для кодирования смещения достаточно 9 бит вместо 12 (сокращение на 25 %).

Варианты алгоритма

Многими авторами предпринималась попытка сократить возможные значения смещений, среди них можно отметить:

LZFG-C2

Авторы: Edward R. Fiala, Daniel H. Greene, 1989 год.

Совпадения кодируются не парой [длина, смещение], а специальным индексом, соответствующим определённой строке в словаре. Иными словами, одинаковые фразы имеют одинаковый индекс, за счёт чего и обеспечивается экономное кодирование совпадений.

LZRW4

Автор: Ross Williams, 1991 год.

По сути LZRW4 аналогичен ROLZ. Хотя автором и не предпринималось создание полноценной программы, в приведённом демонстрационном компрессоре можно видеть схему ROLZ в её черновом варианте.

LZP1-LZP4

Автор: Charles Bloom, 1995 год.

LZP — алгоритм словарного сжатия, который при кодировании совпадения обходится без смещений вовсе. Это возможно благодаря тому, что смещения относительно текущего контекста запоминаются в специальной таблице и компрессор с декомпрессором оперируют этой таблицей одинаковым образом.

LZ77-PM

Авторы: Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter, 1995 год.

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

RK ROLZ

По описанию автора этот алгоритм представляет собой быстрый алгоритм Лемпела-Зива с большим словарём, который способен охватывать большие дистанции в словаре одновременно быстро и эффективно.

Следует отметить, что RK является коммерческим архиватором с закрытым исходным кодом и многие детали использованных алгоритмов не были раскрыты. Но благодаря отдельным людям тайна была приоткрыта и даже было написано несколько бесплатных программ на данном алгоритме сжатия.

Итак, для сокращения активных смещений используется контекст фиксированного порядка. В оригинале это контекст первого порядка (т.е. один символ, предшествующий текущему символу), также возможно использование других контекстов - скажем, контекста второго порядка (два символа, предшествующих текущему) и т. д.

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

// найдём самое длинное совпадение
 
context = buf[position - 1]; // текущий контекст первого порядка
 
max_match = 0; // длина совпадения для кодирования
index = 0; // индекс совпадения (match index)
   
for (i = 0; i < TAB_SIZE; i++) { // для каждого сохранённого смещения в таблице для данного контекста
  offset = tab[context][i]; // найдем смещение
 
  match_length = get_match(offset); // найдем длину совпадения
 
  if (match_length > max_match) { // найдено более длинное совпадение 
    max_match = match_length;
    index = i; // сохраним индекс 
  }
}
 
// обновим таблицу
 
for (i = TAB_SIZE - 1; i > 0; i--) // сначала сдвинем все смещения вверх, удалив самое старое
  tab[context][i] = tab[context][i - 1];
   
tab[context][0] = position; // затем добавим текущее смещение 
 
// закодируем литерал или совпадение
 
if (max_match >= MIN_MATCH) { 
  encode_match_length(max_match); // закодируем длину совпадения
  encode_match_index(index); // закодируем индекс совпадения
  position += max_match;
}
else { // совпадения нужной длины не найдено
  encode_literal(buf[position]); // закодируем литерал
  position++;
}

Это простейший способ. На практике перебор, скажем, 1024 смещений на каждом шаге может занять слишком много времени. Для ускорения поиска может быть использовано хеширование и различные структуры для быстрого поиска, применяемые в широко распространённых реализациях алгоритмов семейства LZ77.

В оригинальном ROLZ литералы кодируются с использованием контекстной модели первого порядка и это не случайно. Дело в том, что данная схема кодирует большее число литералов, если сравнивать со стандартным LZ77, так как очень короткие совпадения будут просто не тронуты ROLZ схемой. Например, при использовании контекста первого порядка и при минимальной длине совпадения в три символа актуальная длина минимального совпадения будет равна четырём (1 (контекст) + 3 (минимальная длина совпадения) = 4). Контекстная модель первого порядка или более сложная модель PPM 1-0 при кодировании литералов способна компенсировать данный недостаток алгоритма.

ROLZ2-ROLZ3

Автор: Malcolm Taylor, 2005 год.

Эти алгоритмы представляют собой дальнейшее развитие ROLZ:

• ROLZ2 — был разработан с целью обеспечения максимальной скорости распаковки.
• ROLZ3 — для максимального сжатия, при незначительной потере в скорости распаковки.

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

• ROLZ2 для кодирования литералов использует простую и быструю модель первого порядка.
• ROLZ3 использует более сложную CM (Context Mixing) модель второго порядка.

Но главной отличительной особенностью этих алгоритмов является использование оптимального разбора при кодировании. Динамическое программирование (Dynamic Programming) — приём, применяемый здесь, способен просчитывать оптимальную последовательность литералов/совпадений на много шагов вперёд, учитывая при выборе реальную стоимость кодирования литерала или совпадения.

См. также

• Арифметическое сжатие
• LZW

Ссылки

• Домашняя страница RK и WinRK Архивная копия от 23 апреля 2007 на Wayback Machine
• Компрессор BALZ Архивная копия от 1 февраля 2009 на Wayback Machine (Public Domain)
• Компрессор QUAD Архивная копия от 22 марта 2007 на Wayback Machine (LGPL)
• Описание и исходные коды LZRW1-LZRW4 — теоретическое обоснование преимуществ ROLZ
• Описание и исходные коды различных вариантов LZP и LZCB
• Arturo Campos. Описание алгоритма LZP