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

  可能重复:   如何更正Damerau-Levenshtein实施中的错误? 我有以下Cython代码(改编自bpbio项目),它执行Damerau-Levenenshtein编辑距离计算:
#---------------------------------------------------------------------------
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并从数据库中检索文本,然后将其与查询文本进行匹配。 在将这些字符串传递给Cython函数进行比较之前将这些字符串编码为
bytes
并不是一个好主意,因为性能会受到很大影响(测试),并且对于任何包含7bit US ASCII以外字符的文本,结果可能都是错误的。 (非常简洁的)Cython手册确实提到了unicode字符串,但对手头的问题几乎没有帮助。 正如我所看到的,一个unicode字符串可以被设想为一个整数数组,每个代表一个代码点,上面的代码基本上是在arrays2ѭs的数组上运行,所以我的猜测是我应该(1)扩展它处理C数组的整数; (2)添加代码将python unicode字符串转换为C数组; (3)利润! (注意:这种方法存在两个潜在问题:一个是处理unicode代理字符,但我想我知道如何处理这些问题。另一个问题是unicode代码点实际上没有将1:1映射到'字符的概念'。我很清楚这一点,但我认为这超出了这个问题的范围。请假设一个unicode代码点是一个比较单位。) 所以我要求建议如何 编写一个快速的Cython函数,它接受一个python unicode字符串并返回一个Cython
unsigned int
s的C数组(4个字节); 修改显示的代码以处理这些数组并执行正确的内存分配/解除分配(这对我来说是非常陌生的东西)。 编辑:John Machin指出,好奇的类型转换
char *m1
等可能是为了速度和/或内存优化而完成的;这些变量仍被视为数字数组。我意识到代码没有做任何事情来防止长字符串可能溢出;当一个数组元素超过127或255(取决于所使用的C编译器)时,可能会出现错误结果。来自生物信息学项目的代码令人惊讶。 那说,我只对大致相同的字符串的精确结果感兴趣,这些字符串少于100个字符左右。结果低于60%的同一性可以为我的目的安全地报告为“完全不同”(通过返回较长文本的长度),所以我想最好留下
char *m1
演员阵容,但添加一些代码来检查在猖獗的不相似的情况下溢出和早期堕胎。     
已邀请:
使用
ord()
将字符转换为整数代码点。它适用于
unicode
str
字符串类型的字符:
codepoints = [ord(c) for c in text]
    

bab

警告:我从来没有这样做过。以下是我尝试过的草图。 您将需要使用PyUnicode_AsUnicode函数和下一个函数PyUnicode_GetSize。在声明中,当前有
char
,请改用Py_UNICODE。大概有一个狭窄的(UCS2)构建,你将复制内部结构,转换代理对。使用广泛的(UCS4)构建,您可以直接在内部结构上运行。     
我关闭了这个问题,因为我找到了一个更好的算法......有自己的问题。在那边见。     

要回复问题请先登录注册