This is a great implementation, thanks. For those of you who need this to be fast and achieve the theoretical bounds, you may want to do something like this usi

This is a great implementation, thanks. For those of you who need this to be fast and achieve the theoretical bounds, you may want to do something like this using a finite-state transducer toolkit. Here's an example with OpenFst: http://www.openfst.org/twiki/bin/view/FST/FstExamples http://www.openfst.org/twiki/bin/view/FST/FstExamples (halfway down under "Edit Distance"). (And OpenFst has a Python wrapper now.)