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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ROLZ2-ROLZ3

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

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

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

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

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

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