可能的重复：
如何纠正 Damerau-Levenshtein 实施中的错误？ https://stackoverflow.com/questions/3431933/how-to-correct-bugs-in-this-damerau-levenshtein-implementation
我有以下内容Cython http://docs.cython.org/index.html代码（改编自bpbio http://code.google.com/p/bpbio/source/browse/trunk/seqfind/seqfind.pyx项目）达默劳-编辑距离计算：
#---------------------------------------------------------------------------
cdef extern from "stdlib.h":
ctypedef unsigned int size_t
size_t strlen(char *s)
void *malloc(size_t size)
void *calloc(size_t n, size_t size)
void free(void *ptr)
int strcmp(char *a, char *b)
char * strcpy(char *a, char *b)
#---------------------------------------------------------------------------
cdef extern from "Python.h":
object PyTuple_GET_ITEM(object, int)
void Py_INCREF(object)
#---------------------------------------------------------------------------
cdef inline size_t imin(int a, int b, int c):
if a < b:
if c < a:
return c
return a
if c < b:
return c
return b
#---------------------------------------------------------------------------
cpdef int editdistance( char *a, char *b ):
"""Given two byte strings ``a`` and ``b``, return their absolute Damerau-
Levenshtein distance. Each deletion, insertion, substitution, and
transposition is counted as one difference, so the edit distance between
``abc`` and ``ab``, ``abcx``, ``abx``, ``acb``, respectively, is ``1``."""
#.........................................................................
if strcmp( a, b ) == 0: return 0
#.........................................................................
cdef int alen = strlen( a )
cdef int blen = strlen( b )
cdef int R
cdef char *ctmp
cdef size_t i
cdef size_t j
cdef size_t achr
cdef size_t bchr
#.........................................................................
if alen > blen:
ctmp = a;
a = b;
b = ctmp;
alen, blen = blen, alen
#.........................................................................
cdef char *m1 = <char *>calloc( blen + 2, sizeof( char ) )
cdef char *m2 = <char *>calloc( blen + 2, sizeof( char ) )
cdef char *m3 = <char *>malloc( ( blen + 2 ) * sizeof( char ) )
#.........................................................................
for i from 0 <= i <= blen:
m2[ i ] = i
#.........................................................................
for i from 1 <= i <= alen:
m1[ 0 ] = i + 1
achr = a[ i - 1 ]
for j from 1 <= j <= blen:
bchr = b[ j- 1 ]
if achr == bchr:
m1[ j ] = m2[ j - 1 ]
else:
m1[ j ] = 1 + imin( m1[ j - 1 ], m2[ j - 1 ], m2[ j ] )
if i != 1 and j != 1 and achr == b[ j - 2 ] and bchr == a[ i - 2 ]:
m1[ j ] = m3[ j - 1 ]
#.......................................................................
m1, m2 = m2, m1
strcpy( m3, m2 )
#.........................................................................
R = <int>m2[ blen ]
#.........................................................................
# cleanup:
free( m3 )
free( m1 )
free( m2 )
#.........................................................................
return R
该代码运行良好且快速（在我的 PC 上每秒进行 300,000...400,000 次比较）。
挑战在于使该代码也能与 unicode 字符串一起使用。我正在运行 Python 3.1 并从数据库中检索文本，然后将其与查询文本相匹配。
将这些字符串编码为bytes在将它们传递给 Cython 函数进行比较之前不是一个好主意，因为性能会受到相当大的影响（经过测试），并且对于包含 7 位 US ASCII 之外的字符的任何文本，结果可能是错误的。
（非常简洁）Cython 手册确实提到了 unicode 字符串，但对当前的问题几乎没有帮助。
在我看来，unicode 字符串可以被认为是一个整数数组，每个整数代表一个代码点，上面的代码基本上是在数组上运行的char已经是了，所以我猜我应该(1)扩展它来处理 C 整数数组；(2)添加代码以将 python unicode 字符串转换为 C 数组；(3)利润！。
( Note: 这种方法有两个潜在的问题：一个是处理 unicode 代理字符，但我想我知道如何处理这些字符。另一个问题是 unicode 代码点并没有真正 1:1 映射到“字符”的概念。我很清楚这一点，但我认为这超出了这个问题的范围。请假设一个 unicode 代码点是一个比较单位。）
所以我寻求建议如何
Edit: 约翰·梅钦 https://stackoverflow.com/users/84270/john-machin指出了奇怪的类型转换char *m1等可能是为了速度和/或内存优化而完成的；这些变量仍然被视为数字数组。我意识到该代码没有采取任何措施来防止长字符串可能发生的溢出；当一个数组元素超过 127 或 255（取决于所使用的 C 编译器）时，可能会出现错误结果。对于来自生物信息学项目的代码有点令人惊讶。
也就是说，我只对少于一百个字符左右的基本相同的字符串的精确结果感兴趣。出于我的目的，低于 60% 相同性的结果可以安全地报告为“完全不同”（通过返回较长文本的长度），所以我想最好保留char *m1强制转换到位，但添加一些代码来检查溢出和早期中止，以防出现严重的差异。
