Levenshtein distance in regular expression

Question

is there possiblity how to include levenshtein distance in regular expression query?

Except making union between permutations. Like searching "hello" with L.d. 1

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

this is a lot stupid and un-usable for larger numbers of L.d.

Answer 1

is there possiblity how to include levenshtein distance in regular expression query?

No, not in a sane way. Implementing - or using an existing - Levenshtein distance algorithm is the way to go.

Answer 2

You can generate the regex programmatically. I will leave that as an exercise for the reader, but for the output of this hypothetical function (given an input of "word") you want something like this string:

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

In English, first you try to match on the word itself, then on every possible single transposition, then on every possible single insertion, then on every possible single omission or substitution (can be done simultaneously).

The length of that string, given a word of length n, is linear (and notably not exponential) with n.

Which is reasonable, I think.

You pass this to your regex generator (like in Ruby it would be Regexp.new(str)) and bam, you got a matcher for ANY word with a Damerau-Levenshtein distance of 1 from a given word.

(Damerau-Levenshtein distances of 2 are far more complicated.)

Note use of the (?> non-backtracing construct which means the order of the individual |'d expressions in that output matter.

I could not think of a way to "compact" that expression.

EDIT: I got it to work, at least in Elixir! https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

I wouldn't necessarily recommend this though (except for educational purposes) since it will only get you to distances of 1; a legit D-L library will let you compute distances > 1. Although since this is regex, it would probably work pretty fast once constructed (note that you should save the "compiled" regex somewhere since this code currently reconstructs it on EVERY comparison!)