Грамматический код

Прямолинейная грамматика (с начальным символом ß) второго предложения Декларации независимости США . Каждый синий символ обозначает нетерминальный символ ; они были получены в результате gzip -сжатия предложения.

Коды на основе грамматики или сжатие на основе грамматики — это алгоритмы сжатия, основанные на идее создания контекстно-свободной грамматики (CFG) для сжимаемой строки. Примеры включают универсальные сжатия данных без потерь . алгоритмы ^[1] Сжатие последовательности данных $x=x_{1}\cdots x_{n}$ , код, основанный на грамматике, преобразует $x$ в контекстно-свободную грамматику $G$ .Задача нахождения наименьшей грамматики для входной последовательности ( самая маленькая грамматическая задача ), как известно, NP-трудна, ^[2] с теоретической и практической точек зрения предлагается так много алгоритмов грамматического преобразования.Как правило, полученная грамматика $G$ дополнительно сжимается статистическими кодировщиками, такими как арифметическое кодирование .

Примеры и характеристики

Класс грамматических кодов очень широк. Он включает в себя блочные коды , алгоритм многоуровневого сопоставления шаблонов (MPM), ^[3] варианты инкрементального разбора кода Лемпеля-Зива , ^[4] и многие другие новые универсальные алгоритмы сжатия без потерь.Коды, основанные на грамматике, универсальны в том смысле, что они могут асимптотически достичь уровня энтропии любого стационарного эргодического источника с конечным алфавитом.

Практические алгоритмы

Следующие программы сжатия доступны по внешним ссылкам.

Отсюда следует ^[5] — это классический алгоритм сжатия грамматики, который последовательно переводит входной текст в CFG, а затем полученный CFG кодируется арифметическим кодером.
Ремонт ^[6] представляет собой жадный алгоритм, использующий стратегию наиболее частой замены. Производительность сжатия очень высока, хотя требования к объему основной памяти очень велики.
ГЛЗА , ^[7] который создает грамматику, которая может быть сокращена, т. е. содержать повторы, где стоимость энтропийного кодирования для «разъяснения» повторов меньше, чем стоимость создания и энтропийного кодирования правила для их фиксации. (В общем, SLG, оптимальный для сжатия, не является неприводимым, и наименьшая задача грамматики отличается от реальной задачи сжатия SLG.)

См. также

Ссылки

^ Киффер, Дж. К.; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория , 46 (3): 737–754, doi : 10.1109/18.841160.
^ Чарикар, М.; Леман, Э.; Лю, Д.; Паниграхи, Р.; Прабхаракан, М.; Сахай, А.; Шелат, А. (2005), «Маленькая грамматическая проблема», IEEE Trans. Инф. Theory , 51 (7): 2554–2576, doi : 10.1109/tit.2005.850116 , S2CID 6900082.
^ Киффер, Дж. К.; Ян, Э.-Х.; Нельсон, Г.; Косман, П. (2000), «Универсальное сжатие без потерь посредством многоуровневого сопоставления с образцом» , IEEE Trans. Инф. Теория , 46 (4): 1227–1245, номер документа : 10.1109/18.850665 , S2CID 8191526.
^ Зив, Дж.; Лемпель, А. (1978), «Сжатие отдельных последовательностей посредством кодирования с переменной скоростью», IEEE Trans. Инф. Theory , 24 (5): 530–536, doi : 10.1109/TIT.1978.1055934 , hdl : 10338.dmlcz/142945
^ Невилл-Мэннинг, CG; Виттен, И.Х. (1997), «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени», Журнал исследований искусственного интеллекта , 7 (4): 67–82, arXiv : cs/9709102 , doi : 10.1613/jair.374 , hdl : 10289/1186 , S2CID 2957960
^ Ларссон, Нью-Джерси; Моффат, А. (2000), «Сжатие на основе автономного словаря» (PDF) , Proceedings of the IEEE , 88 (11): 1722–1732, doi : 10.1109/5.892708
^ Конрад, Кеннон Дж.; Уилсон, Пол Р. (2016). «Грамматическое сжатие Зива-Лемпеля: достижение степени сжатия текста класса PPM со скоростью декомпрессии класса LZ». Конференция по сжатию данных 2016 (DCC) . п. 586. дои : 10.1109/DCC.2016.119 . ISBN 978-1-5090-1853-6 . S2CID 3116024 .

Внешние ссылки

Обсуждение и доклад GLZA
Описание грамматических кодов с примером
Коды Sequitur. Архивировано 13 октября 2008 г. на Wayback Machine.
Повторное сопряжение кодов
Re-Pair кодирует версию Гонсало Наварро.
GrammarViz 2.0 — реализация Sequitur, Re-Pair и параллельного Re-Pair на Java.

[1] Киффер, Дж. К.; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория , 46 (3): 737–754, doi : 10.1109/18.841160.

[2] Чарикар, М.; Леман, Э.; Лю, Д.; Паниграхи, Р.; Прабхаракан, М.; Сахай, А.; Шелат, А. (2005), «Маленькая грамматическая проблема», IEEE Trans. Инф. Theory , 51 (7): 2554–2576, doi : 10.1109/tit.2005.850116 , S2CID 6900082.

[3] Киффер, Дж. К.; Ян, Э.-Х.; Нельсон, Г.; Косман, П. (2000), «Универсальное сжатие без потерь посредством многоуровневого сопоставления с образцом» , IEEE Trans. Инф. Теория , 46 (4): 1227–1245, номер документа : 10.1109/18.850665 , S2CID 8191526.

[4] Зив, Дж.; Лемпель, А. (1978), «Сжатие отдельных последовательностей посредством кодирования с переменной скоростью», IEEE Trans. Инф. Theory , 24 (5): 530–536, doi : 10.1109/TIT.1978.1055934 , hdl : 10338.dmlcz/142945

[5] Невилл-Мэннинг, CG; Виттен, И.Х. (1997), «Идентификация иерархической структуры в последовательностях: алгоритм линейного времени», Журнал исследований искусственного интеллекта , 7 (4): 67–82, arXiv : cs/9709102 , doi : 10.1613/jair.374 , hdl : 10289/1186 , S2CID 2957960

[6] Ларссон, Нью-Джерси; Моффат, А. (2000), «Сжатие на основе автономного словаря» (PDF) , Proceedings of the IEEE , 88 (11): 1722–1732, doi : 10.1109/5.892708

[7] Конрад, Кеннон Дж.; Уилсон, Пол Р. (2016). «Грамматическое сжатие Зива-Лемпеля: достижение степени сжатия текста класса PPM со скоростью декомпрессии класса LZ». Конференция по сжатию данных 2016 (DCC) . п. 586. дои : 10.1109/DCC.2016.119 . ISBN 978-1-5090-1853-6 . S2CID 3116024 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]