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

Возможно ли включить расстояние Левенштейна в запрос регулярного выражения?

Кроме объединения между перестановками. Например, поиск "hello" с L. d. 1

.ello | h.llo | he.lo | hel.o | hell.

Это очень глупо и непригодно для больших чисел Л. д.

2 8
regex levenshtein-distance

2 ответа:

Возможно ли включить расстояние Левенштейна в запрос регулярного выражения?

Нет, не в здравом уме. Реализация - или использование существующего-алгоритма расстояния Левенштейна - это путь.
4

Регулярное выражение можно сгенерировать программно. Я оставлю это в качестве упражнения для читателя, но для вывода этой гипотетической функции (учитывая вход "word") вам нужно что-то вроде этой строки: 

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"
В английском языке сначала вы пытаетесь сопоставить само слово, затем каждую возможную одиночную транспозицию, затем каждую возможную одиночную вставку, затем каждую возможную одиночную пропуск или замену (можно сделать одновременно).

Длина этой строки, данное слово длины n является линейным (и, в частности, не экспоненциальным) с n.

, который является разумным, я думаю.

Вы передаете это в генератор регулярных выражений (например, в Ruby это будет Regexp.new (str)) и БАМ, вы получили сопоставитель для любого слова с расстоянием Дамерау-Левенштейна 1 от данного слова.

(расстояния Дамерау-Левенштейна 2 гораздо сложнее.)

Примечание использование (?> конструкция без обратного следа, которая означает порядок отдельных / ' d выражений в это выходное значение.

Я не мог придумать способа "сжать" это выражение.

EDIT: я заставил его работать, по крайней мере, в Эликсире! https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Я бы не обязательно рекомендовал это (за исключением образовательных целей), так как это приведет вас только к расстояниям 1; законная библиотека D-L позволит вам вычислить расстояния > 1. Хотя, поскольку это регулярное выражение, оно, вероятно, будет работать довольно быстро после построения (обратите внимание, что вы должны сохранить "скомпилированное" регулярное выражение где-то, так как этот код в настоящее время реконструирует его при каждом сравнении!)

7