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

Question

Есть ли возможность включить расстояние levenshtein в запросе регулярного выражения?

За исключением соединения между перестановками. Как поиск «привет» с L.d. 1

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

Это много глупостей и непригодных для использования в больших количествах L.d.

Answer 1

Есть ли возможность включить расстояние levenshtein в запросе регулярного выражения?

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

Answer 2

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

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$" 

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

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

Это разумно, я думаю.

Вы передаете это генератору регулярных выражений (например, в Ruby это будет Regexp.new (str)) и bam, у вас есть помощник для ЛЮБОГО слова с расстоянием Дамерау-Левенштейна 1 от данного слова.

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

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

я не мог придумать способ, чтобы «компактная», что экспрессия

EDIT:. Я получил его на работу, по крайней мере, в эликсире https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Я не обязательно рекомендую это, хотя (за исключением образовательного! о.е.), так как это приведет вас только к расстояниям 1; законная библиотека DL позволит вам вычислять расстояния> 1. Хотя, поскольку это регулярное выражение, оно, вероятно, будет работать довольно быстро после построения (обратите внимание, что вы должны сохранить «скомпилированное» регулярное выражение где-то, так как этот код в настоящее время восстанавливает его при КАЖДОМ сравнении!)