Расстояние между регулярным выражением

Question

Можем ли мы вычислить некое расстояние между регулярными выражениями?

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

Answer 1

Вы можете построить детерминированные конечные автоматы для обоих регулярных выражений и сравнить переходы. Разница обоих переходов может затем использоваться для измерения расстояния этих регулярных выражений.

Answer 2

Существует несколько метрик, которые вы можете использовать:

1. Длина действительного совпадения.Некоторые регулярные выражения имеют фиксированный размер, некоторые верхний предел, а некоторые нижний предел.Сравните, насколько похожи их длины или возможные длины.

2. Соответствующие символы.Любое регулярное выражение будет иметь набор символов, которые может содержать совпадение (может быть, все символы).Сравните набор включенных символов.

3. Используйте большой документ и посмотрите, сколько совпадений дает каждое регулярное выражение и сколько из них совпадает.

Вы ищете строгую эквивалентность?

Answer 3

Полагаю, вы могли бы вычислить Расстояние Левенштейна между фактическими строками регулярного эксперимента. Это, безусловно, один из способов измерения «расстояния» между двумя разными строками регулярных выражений.

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

Answer 4

Если у вас есть два регулярных выражения и набор примеров входных данных, вы можете попробовать сопоставить каждый вход с каждым регулярным выражением. Для каждого ввода:

• Если они оба совпадают или оба не совпадают, наберите 0.
• Если один из них совпадает, а другой нет, наберите 1.

Суммируйте этот результат по всем входным данным, и это даст вам «расстояние» между регулярными выражениями. Это даст вам представление о том, как часто два регулярных выражения будут различаться для типичного ввода. Это будет очень медленно вычислять, если ваш набор входных данных большой. Это не будет работать вообще, если оба регулярных выражения не будут совпадать почти со всеми случайными строками, а ваш ожидаемый ввод будет полностью случайным. Например, регулярное выражение 'sgjlkwren' и регулярное выражение 'ueuenwbkaalf', вероятно, никогда не совпадут ни с чем, если их проверять на случайном вводе, поэтому в этой метрике расстояние между ними будет равно нулю. Это может или не может быть то, что вы хотите (вероятно, нет).

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

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

Answer 5

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

Это можно оптимизировать, удаляя общие префиксы / суффиксы. Например. a[0-9]* и a[0-7]* имеют общий префикс a, поэтому вы можете вычислить расстояние между [0-9]* и [0-7]*.

Answer 6

Я думаю, сначала вам нужно понять, как вы видите «разницу» между двумя выражениями. По сути, определите метрику расстояния.

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

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

Тем не менее, я считаю, что мы могли бы что-то придумать, но не в целом, а для одного конкретного и весьма ограниченного случая. У вас есть какой-то пример, чтобы показать нам?