WikiSort.ru - Не сортированное

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