ダメラウ・レーベネンシュテインの編集距離計算を行う次のCythonコード（bpbioプロジェクトから採用）があります。
#---------------------------------------------------------------------------
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では1秒あたり300,000 ... 400,000の比較）。
課題は、このコードをUnicode文字列でも機能させることです。Python 3.1を実行していて、データベースからテキストを取得し、クエリテキストと照合します。
比較のためにCython関数に渡す前に、これらの文字列をエンコードするbytesことはお勧めできません。パフォーマンスが大幅に低下し（テスト済み）、7ビットのUSASCII以外の文字を含むテキストの結果が正しくない可能性があるためです。
（非常に簡潔な）Cythonマニュアルにはユニコード文字列が記載されていますが、目前の問題にはほとんど役立ちません。
私が見ているように、ユニコード文字列は、それぞれが単一のコードポイントを表す整数の配列として考えることができ、上記のコードは基本的にcharすでにsの配列で動作しているので、 （1）それを拡張する必要があると思います整数のC配列を処理するため。（2） Pythonユニコード文字列をC配列に変換するコードを追加します。（3）利益！
（ 注： このアプローチには2つの潜在的な問題があります：1つはユニコード代理文字の処理ですが、私はそれらをどうするか知っていると思います。もう1つの問題は、ユニコードコードポイントが実際には文字の概念に1：1でマッピングされないことです'。私はそれをよく知っていますが、この質問の範囲外だと思います。1つのUnicodeコードポイントが1つの比較単位であると想定してください。）
だから私はどのように提案を求めています
unsigned intPythonユニコード文字列を受け入れてCythonのC配列（4バイト）を返す高速Cython関数を記述します。これらの配列を処理し、正しいメモリ割り当て/割り当て解除を行うように示されているコードを変更します（これは私にとってかなり異質なことです）。
編集：ジョン・マチンchar *m1は、奇妙なタイプキャストなどはおそらく速度やメモリの最適化のために行われていると指摘しています。これらの変数は、引き続き数値の配列として扱われます。私は、コードが長い文字列で起こりうるオーバーフローを防ぐために何もしていないことに気づきました。1つの配列要素が127または255を超えると、誤った結果が発生する可能性があります（使用するCコンパイラによって異なります）。バイオインフォマティクスプロジェクトからのコードには、ある種驚くべきものがあります。
とは言うものの、私が興味を持っているのは、ほぼ100文字未満のほぼ同一の文字列の正確な結果だけです。60％未満の同一性の結果は、私の目的では「完全に異なる」（長いテキストの長さを返すことによって）として安全に報告される可能性があるため、char *m1キャストをそのままにしておくのが最善だと思いますが、オーバーフローをチェックするためのコードを追加します横行する非類似性の場合の早期中絶。