Алгоритмы, структуры данных
5c8b6e8c

LZFG.


LZFG, предложенный Фиалой и Грини [28, алгоритм C2] - это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.

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



Содержание раздела