Обзор алгоритмов сжатия без потерь

Алгоритм LZJ

LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в строю его вариантов. Первоначально предполагаемый словарь LZJ содержит каждую уникальную строку из уже просмотренной части текста, ограниченную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пределах от 0 до H-1 (годится H около 8192). Для гарантированной кодировки каждой строки, в словарь включается множество исходных символов. Когда словарь полон, он сокращается удалением строки, появлявшейся во входе только один раз.

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