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

9

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

За исключением создания союза между перестановками. Как поиск "привет" с Л.Д. 1

<code>.ello | h.llo | he.lo | hel.o | hell.
</code>

это очень глупо и непригодно для больших количеств L.d.

Ваш Ответ

2   ответа
5

ression query?

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

хорошо, я подожду, если кто-то ответит, в противном случае я отмечу ваш ответ как правильный :-) zdenda.online
7

упражнение для читателя, но для вывода этой гипотетической функции (с вводом слова "quot;) вы хотите что-то вроде этой строки:

"^(?>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 от данного слова.

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

Обратите внимание на использование конструкции (? & Gt; non-backtracing, которая означает порядок отдельных выражений | 'в этой выходной информации.

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

РЕДАКТИРОВАТЬ: Я получил его на работу, по крайней мере, в эликсире!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

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

Похожие вопросы