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

Алгоритм LZFG

LZFG, предложенный Фиалой и Грини – это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и декодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя разными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска и помещением в выходной файл позиции в дереве.

LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобранной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по существу неограниченной длины, показывающую как много символов должно быть скопировано. Закодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов используются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.