как преобразовать строку python / cython unicode в массив длинных целых чисел, чтобы сделать расстояние редактирования Левенштейна [дубликат]

Возможный дубликат:
Как исправить ошибки в этой реализации Дамерау-Левенштейна?

У меня есть следующее Цитон код (адаптированный из проекта 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

Код работает хорошо и быстро (300,000...400 000 сравнений в секунду на моем ПК).

Задача состоит в том, чтобы заставить этот код работать со строками Юникода как хорошо. я запускаю Python 3.1 и извлекаю тексты из базы данных, которые затем сопоставляются с текстом запроса.

Кодирование этих строк в bytes перед передачей их в функцию Cython для сравнения не является хорошей идеей, так как производительность значительно пострадает (проверено), и результаты, вероятно, будут неверными для любого текста, содержащего символы за пределами 7-битного US ASCII.

В (очень кратком) руководстве по Cython упоминаются строки unicode, но вряд ли они полезны для решения данной проблемы.

На мой взгляд, строку unicode можно представить как массив целых чисел, каждый из которых представляет одну кодовую точку, и приведенный выше код в основном уже работает с массивами chars, поэтому я предполагаю, что я должен (1) расширьте его для обработки c массивов целых чисел; (2) добавьте код для преобразования строки Юникода python в массив C; (3) прибыль!.

( Примечание: существует две потенциальные проблемы с этим подходом: работает с юникодными суррогатными символами, но я думаю, что знаю, что с ними делать. другая проблема заключается в том, что кодовые точки Юникода на самом деле не сопоставляют 1:1 с понятием "символы". мне это хорошо известно, но я считаю, что это выходит за рамки данного вопроса. пожалуйста, предположим, что одна кодовая точка Юникода является одной единицей сравнения.)

Поэтому я прошу предложения, как

• Напишите быструю функцию Cython, которая принимает строку Python unicode и возвращает C массив Cython unsigned ints (4 байта);

• Модифицируйте код, показанный для обработки этих массивов, и сделайте правильные выделения / освобождения памяти (это довольно чуждый материал для меня).

Править: Джон Мэчин указал, что любопытные typecasts char *m1 etc, вероятно, сделаны для оптимизации скорости и/или памяти; эти переменные все еще рассматриваются как массивы чисел. я понимаю, что код не делает ничего, чтобы предотвратить возможное переполнение с помощью длинные строки; ошибочные результаты могут возникнуть, когда один элемент массива превышает 127 или 255 (в зависимости от используемого компилятора C). что-то удивительное для кода, поступающего из биоинформационного проекта.

Тем не менее, меня интересуют только точные результаты для практически идентичных строк, состоящих менее чем из ста символов или около того. результаты ниже 60% одинаковости могут для моих целей быть безопасно сообщены как "совершенно разные" (возвращая длину более длинного текста), поэтому я думаю, что лучше всего будет оставьте приведения char *m1 на месте, но добавьте некоторый код для проверки на переполнение и преждевременный аборт в случае необузданного несоответствия.