ROLZ
|
ROLZ (от англ. Reduced Offset LZ — алгоритм Лемпела-Зива с сокращёнными смещениями) — словарный алгоритм сжатия данных, близкий к LZ77, но использующий некоторые контекстные приёмы для уменьшения числа активных смещений. Само понятие ROLZ впервые ввёл Malcolm Taylor в своём архиваторе RK в 1999 году и данный алгоритм является одним из наиболее современных подходов к построению быстрых эффективных алгоритмов сжатия. В стандартном LZ77 совпадения кодируются парой:
Проблема этой схемы в том, что при кодировании имеется избыточность. Например, при размере словаря в 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:
Оба алгоритма для сокращения активных смещений используют контекст первого порядка, также они способны использовать таблицу размером до 32 000 смещений для каждого контекста.
Но главной отличительной особенностью этих алгоритмов является использование оптимального разбора при кодировании. Динамическое программирование (Dynamic Programming) — приём, применяемый здесь, способен просчитывать оптимальную последовательность литералов/совпадений на много шагов вперёд, учитывая при выборе реальную стоимость кодирования литерала или совпадения. |
