Лучший алгоритм сравнения строк для регулярных выражений

Question

Учитывая регулярное выражение, я хочу сравнить его со списком других регулярных выражений и вывести оценку сходства.

Существует несколько алгоритмов расстояния редактирования (например, расстояние Левенштейна), но они не сравниваются регулярные выражения, например:

R1:       [a-z0-9]+
R2:       [0-9]{1}[a-z0-9]+
Distance: 9

В приведенном выше примере оба регулярных выражения очень похожи, однако имеют довольно большое расстояние редактирования. Я полагаю, что подход с использованием символьных n-грамм был бы более подходящим для таких случаев.

Какой алгоритм / подход вы бы рассмотрели для этой проблемы?

Answer 1

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

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

Даже не рассматривая внутренности самостоятельно (не является незначительным предупреждением), я рекомендую посмотреть, возможно ли изменить механизм регулярных выражений (или использовать некоторый ранее существующий код отладки или тестирования) для вывода соответствующих метаданных обработки правил, промежуточных оценок, если хотите, из которых Затем вы можете рассчитать совокупный. Движки в конечном итоге выполняют свою работу детерминистически, так что это теоретически возможно.

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