Код, основанный на грамматике
-
Основы кодов на основе грамматики
- Алгоритмы сжатия, основанные на построении контекстно-свободных грамматик (CFG) для сжимаемых строк.
- Примеры включают универсальные алгоритмы сжатия без потерь.
-
Сложность задачи нахождения наименьшей грамматики
- Задача нахождения наименьшей грамматики является NP-сложной.
-
Статистическое сжатие
- Созданные грамматики дополнительно сжимаются статистическими кодировщиками, например, арифметическим кодированием.
-
Примеры и характеристики кодов на основе грамматики
- Широкий класс кодов, включая блочные коды, MPM и инкрементальные синтаксические анализаторы.
- Универсальность в достижении уровня энтропии стационарных эргодических источников с конечным алфавитом.
-
Практические алгоритмы сжатия
- Sequitur: классический алгоритм, преобразующий текст в CFG и кодирующий его арифметическим кодером.
- Повторное сопряжение: жадный алгоритм с высокой производительностью сжатия, но большими требованиями к памяти.
- GLZA: алгоритм, создающий грамматику с повторяющимися элементами, где затраты на энтропийное кодирование меньше, чем на создание правил для их фиксации.
-
Дополнительные ресурсы
- Ссылки на программы сжатия и обсуждение алгоритмов.
- Ссылки на документацию и описание кодов на основе грамматики.
- Ссылки на логические коды, заархивированные в Wayback Machine.
- Реализация GrammarViz 2.0 для последовательного, повторного сопряжения и параллельного повторного сопряжения в Java.
Полный текст статьи: