Аннотация

Аннотация: Задача оценки сходства двух регулярных выражений (РВ) важна для многих прикладных задач, включая модернизацию программного кода, оптимизацию уже имеющихся выражений и обнаружение дубликатов в базах шаблонов. В частности, решение данной задачи позволит определить, насколько одно выражение является оптимизированной или упрощенной формой другого, сохраняя при этом функциональную эквивалентность. Это особенно актуально при модернизации устаревших решений, повышении производительности систем обработки текста и разработке систем автоматического синтеза или валидации РВ. Задача оценки сходства структур регулярных выражений нетривиальна и может быть решена с применением различных подходов. В данной работе приведены подходы к оценке сходства структур РВ, представленных как строки и как графы. Рассмотрены подходы к оценке сходства структуры РВ как строк, основанные на вычислении расстояния Левенштейна, расстояния Хемминг, расстояния Джаро и расстояния Джаро-Винклера. Представлены два способа представления РВ в виде графа на основе разбора в абстрактное синтаксическое дерево (АСД) встроенным модулем SRE языка программирования Python и разбора в АСД с помощью авторского транслятора. Рассмотрен подход к оценке сходства структуры РВ как графов, основанный на редакционном расстоянии графа. Подходы к оценке сходства структуры РВ апробируются на экспериментальных РВ, полученных из Интернетресурса Regex101. Экспериментальные РВ аппроксимируются с помощью эквивалентных и почти эквивалентных замен конструкций РВ. Приводятся результаты сравнительного анализа всех рассматриваемых подходов с целью выявления лучшего для оценки сходства структур регулярных выражений в зависимости от типа представления РВ и требований к оценке.