Введение
Алгоритм сжатия данных без потерь. Коды на основе грамматики, или грамматическое сжатие, – это алгоритмы сжатия, основанные на идее построения контекстно-свободной грамматики (CFG) для сжимаемой строки. Примеры включают универсальные алгоритмы сжатия данных без потерь. Для сжатия последовательности данных алгоритм на основе грамматики преобразует её в контекстно-свободную грамматику. Задача поиска наименьшей грамматики для входной последовательности (задача поиска минимальной грамматики) известна как NP-трудная, поэтому предложено множество алгоритмов преобразования грамматик с теоретической и практической точек зрения. Обычно полученная грамматика дополнительно сжимается с помощью статистических кодировщиков, таких как арифметическое кодирование.
Grammar based codes or Grammar based compression are compression algorithms based on the idea of constructing a context free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar based code transforms into a context free grammar The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP hard, so many grammar transform algorithms are proposed from theoretical and practical viewpoints. Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding.
Примеры и характеристики
Класс грамматических кодов весьма обширен. Он включает в себя блочные коды, многоуровневый алгоритм сопоставления с образцом (MPM), варианты инкрементного синтаксического анализа кода Лемпеля — Зива и множество других новых универсальных алгоритмов сжатия без потерь. Грамматические коды являются универсальными в том смысле, что они могут асимптотически достигать скорости энтропии любого стационарного и эргодического источника с конечным алфавитом.
Практические алгоритмы
Программы сжатия, описанные ниже, доступны по внешним ссылкам. Sequitur – это классический алгоритм сжатия на основе грамматик, последовательно преобразующий входной текст в контекстно-свободную грамматику (CFG), после чего полученная CFG кодируется арифметическим кодировщиком. Re-Pair – это жадный алгоритм, использующий стратегию наиболее частой замены в первую очередь. Он обеспечивает высокую степень сжатия, хотя и требует значительного объема оперативной памяти. GLZA строит грамматику, которая может быть редуцируемой, то есть содержать повторы, при этом стоимость энтропийного кодирования "развёртывания" этих повторов меньше, чем стоимость создания и энтропийного кодирования правила для их описания. (В общем случае, оптимальная с точки зрения сжатия SLG не является нередуцируемой, а задача поиска наименьшей грамматики отличается от реальной задачи сжатия SLG.)