Код, основанный на грамматике

• Основы кодов на основе грамматики

  • Алгоритмы сжатия, основанные на построении контекстно-свободных грамматик (CFG) для сжимаемых строк. 
  • Примеры включают универсальные алгоритмы сжатия без потерь. 

• Сложность задачи нахождения наименьшей грамматики

  • Задача нахождения наименьшей грамматики является NP-сложной. 

• Статистическое сжатие

  • Созданные грамматики дополнительно сжимаются статистическими кодировщиками, например, арифметическим кодированием. 

• Примеры и характеристики кодов на основе грамматики

  • Широкий класс кодов, включая блочные коды, MPM и инкрементальные синтаксические анализаторы. 
  • Универсальность в достижении уровня энтропии стационарных эргодических источников с конечным алфавитом. 

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

  • Sequitur: классический алгоритм, преобразующий текст в CFG и кодирующий его арифметическим кодером. 
  • Повторное сопряжение: жадный алгоритм с высокой производительностью сжатия, но большими требованиями к памяти. 
  • GLZA: алгоритм, создающий грамматику с повторяющимися элементами, где затраты на энтропийное кодирование меньше, чем на создание правил для их фиксации. 

• Дополнительные ресурсы

  • Ссылки на программы сжатия и обсуждение алгоритмов. 
  • Ссылки на документацию и описание кодов на основе грамматики. 
  • Ссылки на логические коды, заархивированные в Wayback Machine. 
  • Реализация GrammarViz 2.0 для последовательного, повторного сопряжения и параллельного повторного сопряжения в Java.