ROLZ

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

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

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

Главная проблема такой схемы в том, что появляется некоторая избыточность при кодировании. Например, при размере словаря всего в 4 КБ — у нас имеется 4096 вариантов смещении, а при словаре в 1 МБ — 1048576. Интуитивно понятно, что большинство смещений просто не будет использовано и мы имеем дело с избыточностью.

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

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

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 с тем лишь отличием, что для сокращения активных смещений используются контексты переменной длинны, вместо контекстов фиксированного порядка.

ROLZ (Malcolm Taylor, 1999)

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

Следует отметить, что 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 — для максимального сжатия, при незначительной потере в скорости распаковки.

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

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

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

См. также

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

Ссылки

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