如何将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字符串并返回一个Cythonunsigned int
s的C数组(4个字节);
修改显示的代码以处理这些数组并执行正确的内存分配/解除分配(这对我来说是非常陌生的东西)。
编辑:John Machin指出,好奇的类型转换char *m1
等可能是为了速度和/或内存优化而完成的;这些变量仍被视为数字数组。我意识到代码没有做任何事情来防止长字符串可能溢出;当一个数组元素超过127或255(取决于所使用的C编译器)时,可能会出现错误结果。来自生物信息学项目的代码令人惊讶。
那说,我只对大致相同的字符串的精确结果感兴趣,这些字符串少于100个字符左右。结果低于60%的同一性可以为我的目的安全地报告为“完全不同”(通过返回较长文本的长度),所以我想最好留下char *m1
演员阵容,但添加一些代码来检查在猖獗的不相似的情况下溢出和早期堕胎。
没有找到相关结果
已邀请:
3 个回复
搁手
将字符转换为整数代码点。它适用于
或
字符串类型的字符:
bab
,请改用Py_UNICODE。大概有一个狭窄的(UCS2)构建,你将复制内部结构,转换代理对。使用广泛的(UCS4)构建,您可以直接在内部结构上运行。
糕泰灌