COPIED FROM https://gist.github.com/steveash (public domain license)
Implementation of the OSA (optimal string alignment) which is similar
to the Damerau-Levenshtein in that it allows for transpositions to
count as a single edit distance, but is not a true metric and can
over-estimate the cost because it disallows substrings to edited more than
once. See wikipedia for more discussion on OSA vs DL
See Algorithms on Strings, Trees and Sequences by Dan Gusfield for more
information.
This also has a set of local buffer implementations to avoid allocating new
buffers each time, which might be a premature optimization