Xuan Luo

efficient Levenshtein distance algorithm with lazy evaluation in OO languages: Java, Python

This is an algorithm published in 1992 to compute the Levenshtein distance between two strings in O(|A|(1 + D A B)) time, which is faster than the regular O(|A||B|) dynamic programming implementation when the distance is small (i.e. the strings are very similar). It uses lazy evaluation to avoid unnecessary evaluations. As an exercise I implemented it in Java and Python, strict-evaluation languages without any direct lazy features. It (or some better algorithm) probably has already been made by other people a long time ago.