如何将python/cython unicode字符串转换为长整数数组,以执行levenshtein编辑距离[重复]

可能重复:
How to correct bugs in this Damerau-Levenshtein implementation?

我有以下内容 Cython 代码(改编自 bpbio 项目)确实如此 Damerau Levennshtein编辑距离 计算:

#---------------------------------------------------------------------------
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上每秒进行300000到400000次比较)。

挑战是使这段代码也能与Unicode字符串一起工作。我正在运行python 3.1并从数据库中检索文本,然后将其与查询文本匹配。

将这些字符串编码为 bytes 在将它们传递给cython函数进行比较之前,这不是一个好主意,因为性能会受到很大的影响(经过测试),并且对于包含7bit-us-ascii以外字符的任何文本,结果都可能是错误的。

《赛通手册》(非常简洁)确实提到了Unicode字符串,但对于目前的问题几乎没有帮助。

如我所见,一个Unicode字符串可以被看作一个整数数组,每个整数代表一个代码点,上面的代码基本上是在 char 是的,所以我想我应该 (1) 扩展它以处理整数的C数组; (2) 添加代码以将python unicode字符串转换为C数组; (3) 利润!.

( 注: 这种方法有两个潜在的问题:一个是处理Unicode代理字符,但我想我知道如何处理这些字符。另一个问题是,Unicode代码点并没有真正将1:1映射到“字符”的概念。我很清楚这一点,但我认为这超出了这个问题的范围。请假设一个Unicode码位是一个比较单位。)

所以我在征求建议

• 编写一个快速cython函数,该函数接受python unicode字符串并返回cython的C数组。 unsigned int S(4字节);

• 修改显示的代码以处理这些数组,并执行正确的内存分配/释放操作(这对我来说是非常陌生的事情)。

编辑 : John Machin 指出了奇怪的类型 char *m1 ETC可能用于速度和/或内存优化;这些变量仍然被视为数字数组。我认识到代码并不能防止长字符串溢出;当一个数组元素超过127或255(取决于使用的C编译器)时,可能会出现错误的结果。对来自生物信息学项目的代码有点惊讶。

也就是说,我只对不到100个字符左右的基本相同字符串的精确结果感兴趣。结果低于60%的相同性可以安全地报告为“完全不同”(通过返回较长文本的长度),所以我想最好是离开 CHAR*M1 在适当的地方强制转换,但是添加一些代码来检查溢出和早期流产,以防出现严重的差异。