Код на основе грамматики - Grammar-based code

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

Коды на основе грамматики или же Сжатие на основе грамматики находятся сжатие алгоритмы, основанные на идее построения контекстно-свободная грамматика (CFG) для сжатой строки. Примеры включают универсальные сжатие данных без потерь алгоритмы.[1] Чтобы сжать последовательность данных , код на основе грамматики преобразует в контекстно-свободную грамматику .Проблема поиска наименьшей грамматики для входной последовательности (самая маленькая грамматическая проблема ) известен как NP-трудный,[2] так много алгоритмов преобразования грамматики предлагается с теоретической и практической точек зрения. далее сжимается статистическими кодировщиками, такими как арифметическое кодирование.

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

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

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

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

  • Sequitur[5] представляет собой классический алгоритм сжатия грамматики, который последовательно переводит входной текст в CFG, а затем полученный CFG кодируется арифметическим кодером.
  • Ремонт[6] - это жадный алгоритм, использующий стратегию наиболее частой замены первым. Производительность сжатия высока, хотя требования к основному пространству памяти очень велики.
  • GLZA,[7] который конструирует грамматику, которая может быть сокращаемой, то есть содержать повторы, где стоимость энтропийного кодирования «прописывания» повторов меньше затрат на создание и энтропийное кодирование правила для их захвата. (В общем случае SLG, оптимальная для сжатия, не является неприводимой, и задача наименьшей грамматики отличается от реальной проблемы сжатия SLG.)

Смотрите также

Рекомендации

  1. ^ Kieffer, J.C .; Ян, Э.-Х. (2000), «Коды на основе грамматики: новый класс универсальных исходных кодов без потерь», IEEE Trans. Инф. Теория, 46 (3): 737–754, Дои:10.1109/18.841160
  2. ^ Charikar, M .; Lehman, E .; Liu, D .; Panigrahy, R .; Prabharakan, M .; Sahai, A .; Шелат, А. (2005), "Наименьшая грамматическая проблема", IEEE Trans. Инф. Теория, 51 (7): 2554–2576, Дои:10.1109 / tit.2005.850116
  3. ^ Kieffer, J.C .; Yang, E.-H .; Nelson, G .; Косман, П. (2000), «Универсальное сжатие без потерь за счет многоуровневого сопоставления с образцом», IEEE Trans. Инф. Теория, 46 (4): 1227–1245, Дои:10.1109/18.850665
  4. ^ Ziv, J .; Лемпель, А. (1978), «Сжатие отдельных последовательностей с помощью кодирования с переменной скоростью», IEEE Trans. Инф. Теория, 24 (5): 530–536, Дои:10.1109 / TIT.1978.1055934, HDL:10338.dmlcz / 142945
  5. ^ Nevill-Manning, C.G .; Виттен, И. Х. (1997), "Идентификация иерархической структуры в последовательностях: алгоритм линейного времени", Журнал исследований искусственного интеллекта, 7 (4): 67–82, arXiv:cs / 9709102, Дои:10.1613 / jair.374, HDL:10289/1186
  6. ^ Larsson, N.J .; Моффат, А. (2000), «Сжатие на основе автономного словаря» (PDF), Труды IEEE, 88 (11): 1722–1732, Дои:10.1109/5.892708
  7. ^ Конрад, Кеннон Дж .; Уилсон, Пол Р. (2016), «Грамматическое сжатие по Зив-Лемпелю: достижение коэффициентов сжатия текста класса PPM со скоростью декомпрессии класса LZ», Конференция по сжатию данных IEEE: 586, Дои:10.1109 / DCC.2016.119, ISBN  978-1-5090-1853-6

внешняя ссылка