如何将Python/Cython的Unicode字符串转换为长整型数组以计算Levenshtein编辑距离

Question

可能重复的问题：
如何修正这个Damerau-Levenshtein实现中的错误？

我有以下的Cython代码（改编自bpbio项目），这个代码用于计算Damerau-Levenshtein编辑距离：

#---------------------------------------------------------------------------
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

这段代码运行得很好，而且速度很快（在我的电脑上每秒可以进行30万到40万次比较）。

现在的挑战是让这段代码也能处理unicode字符串。我正在使用Python 3.1，并从数据库中获取文本，然后将其与查询文本进行匹配。

在将这些字符串编码为bytes后再传递给Cython函数进行比较并不是一个好主意，因为性能会大幅下降（经过测试），而且对于包含7位US ASCII以外字符的文本，结果可能会错误。

虽然Cython手册中提到了unicode字符串，但对于当前的问题帮助不大。

在我看来，unicode字符串可以看作是一个整数数组，每个整数代表一个单独的代码点，而上面的代码基本上已经在处理char数组，所以我猜我应该(1)扩展它以处理C整数数组；(2)添加代码将Python的unicode字符串转换为C数组；(3)然后就能获利了！

( 注意： 这种方法有两个潜在问题：一个是处理unicode代理字符，但我想我知道该怎么处理。另一个问题是unicode代码点并不完全对应于“字符”的概念。我对此非常清楚，但我认为这超出了这个问题的范围。请假设一个unicode代码点就是一个比较单位。）

所以我在这里寻求建议，如何

编写一个快速的Cython函数，接受一个Python的unicode字符串，并返回一个Cython的unsigned int（4字节）数组；
修改上面的代码以处理这些数组，并进行正确的内存分配和释放（这对我来说比较陌生）。

编辑：John Machin指出，奇怪的类型转换char *m1等可能是为了速度和/或内存优化；这些变量仍然被视为数字数组。我意识到这段代码没有防止长字符串可能导致的溢出；当一个数组元素超过127或255时（取决于使用的C编译器），可能会出现错误结果。这对于来自生物信息学项目的代码来说有点令人惊讶。

话虽如此，我只对长度在一百个字符以内的基本相同字符串的精确结果感兴趣。对于我的目的，结果低于60%的相似度可以安全地报告为“完全不同”（通过返回较长文本的长度），所以我想最好是保留char *m1的类型转换，但添加一些代码来检查溢出，并在相似度过低时提前终止。

性能优化内存管理 unicode字符串整数数组 cython 代码点编辑距离 damerau-levenshtein

如何将Python/Cython的Unicode字符串转换为长整型数组以计算Levenshtein编辑距离

3 个回答

撰写回答