Коды на основе грамматики или сжатие на основе грамматики - это алгоритмы сжатия , основанные на идее построения контекстно-свободной грамматики (CFG) для сжатой строки. Примеры включают универсальные алгоритмы сжатия данных без потерь . [1] Для сжатия последовательности данных код на основе грамматики преобразуется в грамматику без контекста . Проблема поиска наименьшей грамматики для входной последовательности ( наименьшая грамматическая проблема ) известна как NP-трудная [2], поэтому предлагается множество алгоритмов преобразования грамматики с теоретической и практической точек зрения. Как правило, произведенная грамматикадополнительно сжимается статистическими кодировщиками, такими как арифметическое кодирование .
Примеры и характеристики [ править ]
Класс грамматических кодов очень широк. Он включает в себя блочные коды , варианты инкрементального синтаксического анализа кода Лемпеля-Зива , [3] алгоритм многоуровневого сопоставления с образцом (MPM) [4] и многие другие новые универсальные алгоритмы сжатия без потерь. Коды на основе грамматики универсальны в том смысле, что они могут асимптотически достичь скорости энтропии любого стационарного эргодического источника с конечным алфавитом.
Практические алгоритмы [ править ]
Следующие программы сжатия доступны по внешним ссылкам.
- Sequitur [5] - это классический алгоритм сжатия грамматики, который последовательно переводит входной текст в CFG, а затем созданный CFG кодируется арифметическим кодером.
- Re-Pair [6] - это жадный алгоритм, использующий стратегию наиболее частой замены первым. Производительность сжатия высока, хотя требования к основному пространству памяти очень велики.
- GLZA , [7], который конструирует грамматику, которая может быть сокращаемой , т. Е. Содержать повторы, где стоимость энтропийного кодирования «прописывания» повторов меньше затрат на создание и энтропийное кодирование правила для их захвата. (В общем случае SLG, оптимальная для сжатия, не является неприводимой, и задача наименьшей грамматики отличается от реальной проблемы сжатия SLG.)
См. Также [ править ]
Ссылки [ править ]
- ^ Киффер, JC; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория , 46 (3): 737-754, DOI : 10,1109 / 18,841160
- ^ Charikar, M .; Lehman, E .; Liu, D .; Panigrahy, R .; Прабхаракан, М .; Sahai, A .; Шелат, А. (2005), «Наименьшая грамматическая проблема», IEEE Trans. Инф. Теория , 51 (7): 2554-2576, DOI : 10,1109 / tit.2005.850116
- ^ Киффер, JC; Yang, E.-H .; Nelson, G .; Косман, П. (2000), «Универсальное сжатие без потерь с помощью многоуровневого сопоставления с образцом» , IEEE Trans. Инф. Теория , 46 (4): 1227-1245, DOI : 10,1109 / 18,850665
- ^ Ziv, J .; Lempel, A. (1978), "Сжатие отдельных последовательностей посредством кодирования с переменной скоростью", IEEE Trans. Инф. Теория , 24 (5): 530-536, DOI : 10,1109 / TIT.1978.1055934 , ЛВП : 10338.dmlcz / 142945
- ^ Невилл-Мэннинг, CG; Виттен, IH (1997), «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени», журнал исследований искусственного интеллекта , 7 (4): 67–82, arXiv : cs / 9709102 , doi : 10.1613 / jair.374 , hdl : 10289/1186
- ^ Ларссон, Нью-Джерси; Моффат, A. (2000), "Offline словарь-Based Compression" (PDF) , Труды IEEE , 88 (11): 1722-1732 гг, DOI : 10,1109 / 5,892708
- ^ Конрад, Кеннон Дж .; Уилсон, Пол Р. (2016), "Грамматический Зив-Зива Сжатие: Достижение PPM-класса коэффициентов масштабирования текста сжатия с LZ-класса декомпрессионной Speed", IEEE конференции сжатия данных : 586, DOI : 10,1109 / DCC.2016.119 , ISBN 978-1-5090-1853-6
Внешние ссылки [ править ]
- Обсуждение GLZA и документ
- Описание грамматических кодов с примером
- Секвитур коды
- Повторное сопряжение кодов
- Re-Pair кодирует версию Гонсало Наварро.
- GrammarViz 2.0 - реализация Sequitur, Re-Pair и параллельного Re-Pair в Java.
