如何将python/cythonunicode字符串转换为长整数数组，以进行levenshtein编辑distan

Question

Possible Duplicate:
How to correct bugs in this Damerau-Levenshtein implementation?

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

#---------------------------------------------------------------------------
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字符串一起工作。我运行的是python3.1并从数据库中检索文本，然后将这些文本与查询文本相匹配。在

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

Cython手册（非常简洁）确实提到了unicode字符串，但对于当前的问题几乎没有帮助。在

在我看来，一个unicode字符串可以想象成一个整数数组，每个数组代表一个代码点，上面的代码基本上已经在chars的数组上操作了，所以我的猜测是我应该（1）扩展它来处理C个整数数组；（2）添加将python unicode字符串转换为C数组的代码；（3）profit！。在

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

所以我在征求建议

• 编写一个快速Cython函数，该函数接受python unicode字符串并返回Cythonunsigned ints（4字节）；

• 修改显示的代码来处理这些数组，并执行正确的内存分配/释放（这对我来说是很陌生的东西）。

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

也就是说，我只对不到100个字符的基本相同字符串的精确结果感兴趣。结果在60%以下的相同性可以安全地报告为“完全不同”（通过返回较长文本的长度），因此我想最好保留char *m1类型转换，但添加一些代码以防止过度相似和早期流产。在

Answer 1

警告莱克特：我从来没有这样做过。下面是我将尝试的一个粗略的草图。在

您将需要使用PyUnicode_AsUnicode函数和下一个函数PyUnicode\u GetSize。在声明中，当前有char，请改用Py_UNICODE。假设使用窄（UCS2）构建，您将复制内部结构，并在执行过程中转换代理项对。对于宽（UCS4）构建，您可以直接对内部结构进行操作。在

Answer 2

我结束这个问题是因为我找到了一个更好的算法。。。with its own problems.那边见。在

Answer 3

使用ord()将字符转换为其整数代码点。它使用unicode或str字符串类型中的字符：

codepoints = [ord(c) for c in text]