Информационные системы и технологии МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ УДК 004.627 В.В. МУРОМЦЕВ, В.В. ЛОМАКИН, В.В. МИШУНИН ПОДХОД К УЛУЧШЕНИЮ АЛГОРИТМОВ ГРАММАТИЧЕСКОГО СЖАТИЯ Рассмотрены вопросы построения алгоритмов грамматического сжатия. <...> Рассмотрен алгоритм SEQUITUR, являющийся одним из наиболее известных алгоритмов, использующийся при построении кодов, основанных на грамматиках. <...> Предложен подход к улучшению алгоритмов грамматического сжатия. <...> Ключевые слова: сжатие; сжатие без потерь; грамматические модели; контекстносвободная грамматика; алгоритм SEQUITUR. <...> Поэтому, несмотря на существенный прогресс в развитии устройств, использующихся для передачи и хранения данных, проблема сжатия данных остается актуальной. <...> Существует множество методов и алгоритмов сжатия данных. <...> Наименее исследованы алгоритмы сжатия, основанные на использовании грамматических моделей. <...> Такие алгоритмы будем называть алгоритмами грамматического сжатия. <...> Развитие методов и алгоритмов грамматического сжатия актуально, поскольку их применение в ряде случаев позволяет не только сжать данные, но и выявить полезные структурные зависимости в данных. <...> В работе рассматриваются некоторые вопросы построения алгоритмов грамматического сжатия без потерь, наиболее известный из алгоритмов этого класса и один из подходов к улучшению таких алгоритмов. <...> В работе [1] для сжатия цепочки x используется контекстно-свободная (КС) грамматика , где N – множество нетерминальных символов, T – множество терминальных символов, R – множество КС-правил, S – начальный нетерминальный символ. цепочку x. <...> Сжатие исходной цепочки x без потерь осуществляется в два этапа: 1) на основе анализа цепочки x строится грамматика x 2) грамматика x G кодируется. <...> Восстановление исходных данных также осуществляется в два этапа: 1) декодируется грамматика x G , 2) цепочка x выводится на основании x x G . преобразования <...>