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

[править] См. также

[править] Внешние ссылки


 Для улучшения статьи желательно?:
Источник — «http://ru.wikipedia.org/wiki/ROLZ»
На других языках