Xuan Luo
xuanluo [at] ucla [dot] edu
UCLA Department of Computer Science
Random stuff
- 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.
- random variable monad in Haskell