Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Building a Levenstein Automata for fast string searching
Difference between en1 and en2, changed 108 character(s)
Paul Masurel offers a great article about the Levenstein automata : [link](http://fulmicoton.com/posts/levenshtein/)↵

He offers an algorithm to compute if the levenstein distance between two strings is less than or equal to D.

The naive algorithm is fairly straightforward : ↵

~~~~~↵
def levenshtein(s1, s2, D=2):↵
"""↵
Returns True iff the two string↵
s1 and s2 is lesser or equal to D↵
"""↵
if D == -1:↵
return False↵
if len(s1) < len(s2):↵
return levenshtein(s2, s1)↵
if len(s2) == 0:↵
return len(s1) <= D↵
return (levenshtein(s1[1:], s2[1:], D-1)   # substitution\↵
or levenshtein(s1, s2[1:], D-1)       # insertion\↵
or levenshtein(s1[1:], s2, D-1)       # deletion\↵
or (↵
# character match↵
(s1 == s2) and \↵
levenshtein(s1[1:], s2[1:], D)↵
))↵
~~~~~↵

This basically tries all possibilities which is with exponential complexity if we don't save any of the calls.↵

He offers a better algorithm but for the last week I have been trying to understand how it works, here it is : ↵

~~~~~↵

def levenshtein(s1, s2, D=2):↵
"""↵
Returns True iff the edit distance between↵
the two strings s1 and s2 is lesser or↵
equal to D↵
"""↵
if len(s1) == 0:↵
return len(s2) <= D↵
if len(s2) == 0:↵
return len(s1) <= D↵
# assuming s1 is NOT used to build s2,↵
if D > 0:↵
if levenshtein(s1[1:], s2, D - 1):↵
# deletion↵
return True↵
if levenshtein(s1[1:], s2[1:], D - 1):↵
# substitution↵
return True↵
# assuming s1 is used to build s2↵
for d in range(min(D+1, len(s2))):↵
# d is the position where s1↵
# might be used.↵
# it is also the number of character↵
# that are required to be inserted before↵
# using s1[d].↵
if s1 == s2[d]:↵
if levenshtein(s1[1:], s2[d+1:], D - d):↵
return True↵
return False↵
~~~~~↵

It would be great if anyone can shed some light on how this works! Thanks!

#### History

Revisions Rev. Lang. By When Δ Comment
en2 intptr 2015-10-03 17:36:52 108
en1 intptr 2015-10-03 17:36:07 2089 Initial revision (published)