Levenshtein Algorithm: An optimization walkthrough

In [1]:

    

%load_ext Cython


    

In [2]:

    

import random
import string

alphanum = string.lowercase + string.uppercase + string.digits
s1 = ''.join(random.choice(alphanum) for _ in xrange(1024))
s2 = ''.join(random.choice(alphanum) for _ in xrange(1024))


    

In [3]:

    

def levenshtein_1_py(s1, s2):

    n1 = len(s1) + 1
    n2 = len(s2) + 1

    m = [[0 for _ in range(n2)] for _ in range(n1)]

    for i in range(0, n1):
        m[i][0] = i

    for j in range(0, n2):
        m[0][j] = j

    for j in range(1, n2):
        for i in range(1, n1):
            if s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = min(m[i-1][j] + 1, m[i][j-1] + 1, m[i-1][j-1] + 1)

    return m[n1-1][n2-1]


    

In [4]:

    

%%cython --annotate
import cython

@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_1(s1, s2):

    cdef n1 = len(s1) + 1
    cdef n2 = len(s2) + 1

    m = [[0 for _ in range(n2)] for _ in range(n1)]

    for i from 0 <= i < n1:
        m[i][0] = i

    for j from 0 <= j < n2:
        m[0][j] = j

    for j from 1 <= j < n2:
        for i from 1 <= i < n1:
            if s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = min(m[i-1][j] + 1, m[i][j-1] + 1, m[i-1][j-1] + 1)

    return m[n1-1][n2-1]


    

    
Out[4]:









    
    
    


Generated by Cython 0.22
 01: import cython
 02: 
 03: @cython.boundscheck(False)
 04: @cython.wraparound(False)
+05: def levenshtein_1(s1, s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_1levenshtein_1(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_1levenshtein_1 = {"levenshtein_1", (PyCFunction)__pyx_pw_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_1levenshtein_1, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_1levenshtein_1(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  PyObject *__pyx_v_s1 = 0;
  PyObject *__pyx_v_s2 = 0;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_1 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_1", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_1") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = values[0];
    __pyx_v_s2 = values[1];
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_1", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_84c0ed59bac34abfc7a3004cad627bec.levenshtein_1", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_levenshtein_1(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_levenshtein_1(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_s1, PyObject *__pyx_v_s2) {
  PyObject *__pyx_v_n1 = 0;
  PyObject *__pyx_v_n2 = 0;
  PyObject *__pyx_v_m = NULL;
  PyObject *__pyx_v_i = NULL;
  PyObject *__pyx_v_j = NULL;
  CYTHON_UNUSED PyObject *__pyx_v__ = NULL;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_1", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_4);
  __Pyx_XDECREF(__pyx_t_6);
  __Pyx_XDECREF(__pyx_t_7);
  __Pyx_AddTraceback("_cython_magic_84c0ed59bac34abfc7a3004cad627bec.levenshtein_1", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XDECREF(__pyx_v_n1);
  __Pyx_XDECREF(__pyx_v_n2);
  __Pyx_XDECREF(__pyx_v_m);
  __Pyx_XDECREF(__pyx_v_i);
  __Pyx_XDECREF(__pyx_v_j);
  __Pyx_XDECREF(__pyx_v__);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__2 = PyTuple_Pack(8, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_m, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_); if (unlikely(!__pyx_tuple__2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__2);
  __Pyx_GIVEREF(__pyx_tuple__2);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_84c0ed59bac34abfc7a3004cad627bec_1levenshtein_1, NULL, __pyx_n_s_cython_magic_84c0ed59bac34abfc7); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_1, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 06: 
+07:     cdef n1 = len(s1) + 1
  __pyx_t_1 = PyObject_Length(__pyx_v_s1); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyInt_FromSsize_t((__pyx_t_1 + 1)); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_v_n1 = __pyx_t_2;
  __pyx_t_2 = 0;
+08:     cdef n2 = len(s2) + 1
  __pyx_t_1 = PyObject_Length(__pyx_v_s2); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyInt_FromSsize_t((__pyx_t_1 + 1)); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_v_n2 = __pyx_t_2;
  __pyx_t_2 = 0;
 09: 
+10:     m = [[0 for _ in range(n2)] for _ in range(n1)]
  __pyx_t_2 = PyList_New(0); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __Pyx_INCREF(__pyx_v_n1);
  PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_v_n1);
  __Pyx_GIVEREF(__pyx_v_n1);
  __pyx_t_4 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_3, NULL); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_4);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  if (likely(PyList_CheckExact(__pyx_t_4)) || PyTuple_CheckExact(__pyx_t_4)) {
    __pyx_t_3 = __pyx_t_4; __Pyx_INCREF(__pyx_t_3); __pyx_t_1 = 0;
    __pyx_t_5 = NULL;
  } else {
    __pyx_t_1 = -1; __pyx_t_3 = PyObject_GetIter(__pyx_t_4); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_3);
    __pyx_t_5 = Py_TYPE(__pyx_t_3)->tp_iternext; if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  }
  __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
  for (;;) {
    if (likely(!__pyx_t_5)) {
      if (likely(PyList_CheckExact(__pyx_t_3))) {
        if (__pyx_t_1 >= PyList_GET_SIZE(__pyx_t_3)) break;
        #if CYTHON_COMPILING_IN_CPYTHON
        __pyx_t_4 = PyList_GET_ITEM(__pyx_t_3, __pyx_t_1); __Pyx_INCREF(__pyx_t_4); __pyx_t_1++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #else
        __pyx_t_4 = PySequence_ITEM(__pyx_t_3, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #endif
      } else {
        if (__pyx_t_1 >= PyTuple_GET_SIZE(__pyx_t_3)) break;
        #if CYTHON_COMPILING_IN_CPYTHON
        __pyx_t_4 = PyTuple_GET_ITEM(__pyx_t_3, __pyx_t_1); __Pyx_INCREF(__pyx_t_4); __pyx_t_1++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #else
        __pyx_t_4 = PySequence_ITEM(__pyx_t_3, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #endif
      }
    } else {
      __pyx_t_4 = __pyx_t_5(__pyx_t_3);
      if (unlikely(!__pyx_t_4)) {
        PyObject* exc_type = PyErr_Occurred();
        if (exc_type) {
          if (likely(exc_type == PyExc_StopIteration || PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();
          else {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        }
        break;
      }
      __Pyx_GOTREF(__pyx_t_4);
    }
    __Pyx_XDECREF_SET(__pyx_v__, __pyx_t_4);
    __pyx_t_4 = 0;
    __pyx_t_4 = PyList_New(0); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_4);
    __pyx_t_6 = PyTuple_New(1); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_6);
    __Pyx_INCREF(__pyx_v_n2);
    PyTuple_SET_ITEM(__pyx_t_6, 0, __pyx_v_n2);
    __Pyx_GIVEREF(__pyx_v_n2);
    __pyx_t_7 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_6, NULL); if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_7);
    __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
    if (likely(PyList_CheckExact(__pyx_t_7)) || PyTuple_CheckExact(__pyx_t_7)) {
      __pyx_t_6 = __pyx_t_7; __Pyx_INCREF(__pyx_t_6); __pyx_t_8 = 0;
      __pyx_t_9 = NULL;
    } else {
      __pyx_t_8 = -1; __pyx_t_6 = PyObject_GetIter(__pyx_t_7); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_6);
      __pyx_t_9 = Py_TYPE(__pyx_t_6)->tp_iternext; if (unlikely(!__pyx_t_9)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    }
    __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
    for (;;) {
      if (likely(!__pyx_t_9)) {
        if (likely(PyList_CheckExact(__pyx_t_6))) {
          if (__pyx_t_8 >= PyList_GET_SIZE(__pyx_t_6)) break;
          #if CYTHON_COMPILING_IN_CPYTHON
          __pyx_t_7 = PyList_GET_ITEM(__pyx_t_6, __pyx_t_8); __Pyx_INCREF(__pyx_t_7); __pyx_t_8++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #else
          __pyx_t_7 = PySequence_ITEM(__pyx_t_6, __pyx_t_8); __pyx_t_8++; if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #endif
        } else {
          if (__pyx_t_8 >= PyTuple_GET_SIZE(__pyx_t_6)) break;
          #if CYTHON_COMPILING_IN_CPYTHON
          __pyx_t_7 = PyTuple_GET_ITEM(__pyx_t_6, __pyx_t_8); __Pyx_INCREF(__pyx_t_7); __pyx_t_8++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #else
          __pyx_t_7 = PySequence_ITEM(__pyx_t_6, __pyx_t_8); __pyx_t_8++; if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #endif
        }
      } else {
        __pyx_t_7 = __pyx_t_9(__pyx_t_6);
        if (unlikely(!__pyx_t_7)) {
          PyObject* exc_type = PyErr_Occurred();
          if (exc_type) {
            if (likely(exc_type == PyExc_StopIteration || PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();
            else {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          }
          break;
        }
        __Pyx_GOTREF(__pyx_t_7);
      }
      __Pyx_DECREF_SET(__pyx_v__, __pyx_t_7);
      __pyx_t_7 = 0;
      if (unlikely(__Pyx_ListComp_Append(__pyx_t_4, (PyObject*)__pyx_int_0))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    }
    __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
    if (unlikely(__Pyx_ListComp_Append(__pyx_t_2, (PyObject*)__pyx_t_4))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
  }
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __pyx_v_m = ((PyObject*)__pyx_t_2);
  __pyx_t_2 = 0;
 11: 
+12:     for i from 0 <= i < n1:
  __pyx_t_10 = __Pyx_PyInt_As_long(__pyx_v_n1); if (unlikely((__pyx_t_10 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  for (__pyx_t_11 = 0; __pyx_t_11 < __pyx_t_10; __pyx_t_11++) {
    __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_11); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_2);
    __pyx_t_2 = 0;
/* … */
  __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_11); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_2);
  __pyx_t_2 = 0;
+13:         m[i][0] = i
    __pyx_t_2 = PyObject_GetItem(__pyx_v_m, __pyx_v_i); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 13; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
    __Pyx_GOTREF(__pyx_t_2);
    if (unlikely(__Pyx_SetItemInt(__pyx_t_2, 0, __pyx_v_i, long, 1, __Pyx_PyInt_From_long, 0, 0, 0) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 13; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
    __pyx_t_11 = __Pyx_PyInt_As_long(__pyx_v_i); if (unlikely((__pyx_t_11 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  }
 14: 
+15:     for j from 0 <= j < n2:
  __pyx_t_11 = __Pyx_PyInt_As_long(__pyx_v_n2); if (unlikely((__pyx_t_11 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  for (__pyx_t_10 = 0; __pyx_t_10 < __pyx_t_11; __pyx_t_10++) {
    __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_10); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_2);
    __pyx_t_2 = 0;
/* … */
  __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_10); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_2);
  __pyx_t_2 = 0;
+16:         m[0][j] = j
    if (unlikely(PyObject_SetItem(PyList_GET_ITEM(__pyx_v_m, 0), __pyx_v_j, __pyx_v_j) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __pyx_t_10 = __Pyx_PyInt_As_long(__pyx_v_j); if (unlikely((__pyx_t_10 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  }
 17: 
+18:     for j from 1 <= j < n2:
  __pyx_t_10 = __Pyx_PyInt_As_long(__pyx_v_n2); if (unlikely((__pyx_t_10 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  for (__pyx_t_11 = 1; __pyx_t_11 < __pyx_t_10; __pyx_t_11++) {
    __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_11); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_2);
    __pyx_t_2 = 0;
/* … */
  __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_11); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_2);
  __pyx_t_2 = 0;
+19:         for i from 1 <= i < n1:
    __pyx_t_12 = __Pyx_PyInt_As_long(__pyx_v_n1); if (unlikely((__pyx_t_12 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 19; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    for (__pyx_t_13 = 1; __pyx_t_13 < __pyx_t_12; __pyx_t_13++) {
      __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_13); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 19; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_2);
      __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_2);
      __pyx_t_2 = 0;
/* … */
    __pyx_t_2 = __Pyx_PyInt_From_long(__pyx_t_13); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 19; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_2);
    __pyx_t_2 = 0;
    __pyx_t_11 = __Pyx_PyInt_As_long(__pyx_v_j); if (unlikely((__pyx_t_11 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  }
+20:             if s1[i-1] == s2[j-1]:
      __pyx_t_2 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_3 = PyObject_GetItem(__pyx_v_s1, __pyx_t_2); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_3);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_2 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_4 = PyObject_GetItem(__pyx_v_s2, __pyx_t_2); if (unlikely(__pyx_t_4 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_4);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_2 = PyObject_RichCompare(__pyx_t_3, __pyx_t_4, Py_EQ); __Pyx_XGOTREF(__pyx_t_2); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
      __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
      __pyx_t_14 = __Pyx_PyObject_IsTrue(__pyx_t_2); if (unlikely(__pyx_t_14 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 20; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      if (__pyx_t_14) {
+21:                 m[i][j] = m[i-1][j-1]
        __pyx_t_2 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_2);
        __pyx_t_4 = PyObject_GetItem(__pyx_v_m, __pyx_t_2); if (unlikely(__pyx_t_4 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_4);
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
        __pyx_t_2 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_2);
        __pyx_t_3 = PyObject_GetItem(__pyx_t_4, __pyx_t_2); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_3);
        __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
        __pyx_t_2 = PyObject_GetItem(__pyx_v_m, __pyx_v_i); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_2);
        if (unlikely(PyObject_SetItem(__pyx_t_2, __pyx_v_j, __pyx_t_3) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        goto __pyx_L15;
      }
      /*else*/ {
 22:             else:
+23:                 m[i][j] = min(m[i-1][j] + 1, m[i][j-1] + 1, m[i-1][j-1] + 1)
        __pyx_t_3 = PyObject_GetItem(__pyx_v_m, __pyx_v_i); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_3);
        __pyx_t_2 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_2);
        __pyx_t_4 = PyObject_GetItem(__pyx_t_3, __pyx_t_2); if (unlikely(__pyx_t_4 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_4);
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
        __pyx_t_2 = PyNumber_Add(__pyx_t_4, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_2);
        __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
        __pyx_t_4 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_4);
        __pyx_t_3 = PyObject_GetItem(__pyx_v_m, __pyx_t_4); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_3);
        __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
        __pyx_t_4 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_4);
        __pyx_t_6 = PyObject_GetItem(__pyx_t_3, __pyx_t_4); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_6);
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
        __pyx_t_4 = PyNumber_Add(__pyx_t_6, __pyx_int_1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_4);
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __pyx_t_6 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_6);
        __pyx_t_3 = PyObject_GetItem(__pyx_v_m, __pyx_t_6); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_3);
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __pyx_t_6 = PyObject_GetItem(__pyx_t_3, __pyx_v_j); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_6);
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        __pyx_t_3 = PyNumber_Add(__pyx_t_6, __pyx_int_1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_3);
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __pyx_t_7 = PyObject_RichCompare(__pyx_t_2, __pyx_t_3, Py_LT); __Pyx_XGOTREF(__pyx_t_7); if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __pyx_t_14 = __Pyx_PyObject_IsTrue(__pyx_t_7); if (unlikely(__pyx_t_14 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
        if (__pyx_t_14) {
          __Pyx_INCREF(__pyx_t_2);
          __pyx_t_6 = __pyx_t_2;
        } else {
          __Pyx_INCREF(__pyx_t_3);
          __pyx_t_6 = __pyx_t_3;
        }
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        __Pyx_INCREF(__pyx_t_6);
        __pyx_t_3 = __pyx_t_6;
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __pyx_t_7 = PyObject_RichCompare(__pyx_t_4, __pyx_t_3, Py_LT); __Pyx_XGOTREF(__pyx_t_7); if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __pyx_t_14 = __Pyx_PyObject_IsTrue(__pyx_t_7); if (unlikely(__pyx_t_14 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;
        if (__pyx_t_14) {
          __Pyx_INCREF(__pyx_t_4);
          __pyx_t_6 = __pyx_t_4;
        } else {
          __Pyx_INCREF(__pyx_t_3);
          __pyx_t_6 = __pyx_t_3;
        }
        __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
        __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
        __pyx_t_2 = __pyx_t_6;
        __Pyx_INCREF(__pyx_t_2);
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __pyx_t_6 = PyObject_GetItem(__pyx_v_m, __pyx_v_i); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
        __Pyx_GOTREF(__pyx_t_6);
        if (unlikely(PyObject_SetItem(__pyx_t_6, __pyx_v_j, __pyx_t_2) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
        __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      }
      __pyx_L15:;
      __pyx_t_13 = __Pyx_PyInt_As_long(__pyx_v_i); if (unlikely((__pyx_t_13 == (long)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 19; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    }
 24: 
+25:     return m[n1-1][n2-1]
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_2 = PyNumber_Subtract(__pyx_v_n1, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 25; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_6 = PyObject_GetItem(__pyx_v_m, __pyx_t_2); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 25; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  __pyx_t_2 = PyNumber_Subtract(__pyx_v_n2, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 25; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_4 = PyObject_GetItem(__pyx_t_6, __pyx_t_2); if (unlikely(__pyx_t_4 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 25; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
  __Pyx_GOTREF(__pyx_t_4);
  __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  __pyx_r = __pyx_t_4;
  __pyx_t_4 = 0;
  goto __pyx_L0;

In [5]:

    

def levenshtein_2_py(s1, s2):

    n1 = len(s1)
    n2 = len(s2)
    
    column = range(n1 + 1)

    for j in range(1, n2 + 1):
        column[0] = j
        last_diag = j - 1
        for i in range(1, n1 + 1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    return column[n1]


    

In [6]:

    

%%cython --annotate
import cython

@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_2(s1, s2):

    cdef n1 = len(s1)
    cdef n2 = len(s2)
    
    column = range(n1 + 1)

    for j in range(1, n2 + 1):
        column[0] = j
        last_diag = j - 1
        for i in range(1, n1 + 1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
    
    return column[n1]


    

    
Out[6]:









    
    
    


Generated by Cython 0.22
 01: import cython
 02: 
 03: @cython.boundscheck(False)
 04: @cython.wraparound(False)
+05: def levenshtein_2(s1, s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_1levenshtein_2(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_1levenshtein_2 = {"levenshtein_2", (PyCFunction)__pyx_pw_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_1levenshtein_2, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_1levenshtein_2(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  PyObject *__pyx_v_s1 = 0;
  PyObject *__pyx_v_s2 = 0;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_2 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_2", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_2") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = values[0];
    __pyx_v_s2 = values[1];
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_2", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_7d6fae36f184c56dadcd01238528ec6d.levenshtein_2", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_levenshtein_2(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_levenshtein_2(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_s1, PyObject *__pyx_v_s2) {
  PyObject *__pyx_v_n1 = 0;
  PyObject *__pyx_v_n2 = 0;
  PyObject *__pyx_v_column = NULL;
  PyObject *__pyx_v_j = NULL;
  PyObject *__pyx_v_last_diag = NULL;
  PyObject *__pyx_v_i = NULL;
  PyObject *__pyx_v_current = NULL;
  PyObject *__pyx_v_cost = NULL;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_2", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_XDECREF(__pyx_t_8);
  __Pyx_XDECREF(__pyx_t_9);
  __Pyx_XDECREF(__pyx_t_10);
  __Pyx_XDECREF(__pyx_t_12);
  __Pyx_AddTraceback("_cython_magic_7d6fae36f184c56dadcd01238528ec6d.levenshtein_2", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XDECREF(__pyx_v_n1);
  __Pyx_XDECREF(__pyx_v_n2);
  __Pyx_XDECREF(__pyx_v_column);
  __Pyx_XDECREF(__pyx_v_j);
  __Pyx_XDECREF(__pyx_v_last_diag);
  __Pyx_XDECREF(__pyx_v_i);
  __Pyx_XDECREF(__pyx_v_current);
  __Pyx_XDECREF(__pyx_v_cost);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple_ = PyTuple_Pack(10, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_column, __pyx_n_s_j, __pyx_n_s_last_diag, __pyx_n_s_i, __pyx_n_s_current, __pyx_n_s_cost); if (unlikely(!__pyx_tuple_)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple_);
  __Pyx_GIVEREF(__pyx_tuple_);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_7d6fae36f184c56dadcd01238528ec6d_1levenshtein_2, NULL, __pyx_n_s_cython_magic_7d6fae36f184c56dad); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_2, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 5; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 06: 
+07:     cdef n1 = len(s1)
  __pyx_t_1 = PyObject_Length(__pyx_v_s1); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyInt_FromSsize_t(__pyx_t_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_v_n1 = __pyx_t_2;
  __pyx_t_2 = 0;
+08:     cdef n2 = len(s2)
  __pyx_t_1 = PyObject_Length(__pyx_v_s2); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyInt_FromSsize_t(__pyx_t_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_v_n2 = __pyx_t_2;
  __pyx_t_2 = 0;
 09: 
+10:     column = range(n1 + 1)
  __pyx_t_2 = PyNumber_Add(__pyx_v_n1, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_3, NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __pyx_v_column = __pyx_t_2;
  __pyx_t_2 = 0;
 11: 
+12:     for j in range(1, n2 + 1):
  __pyx_t_2 = PyNumber_Add(__pyx_v_n2, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __Pyx_INCREF(__pyx_int_1);
  PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_int_1);
  __Pyx_GIVEREF(__pyx_int_1);
  PyTuple_SET_ITEM(__pyx_t_3, 1, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_3, NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  if (likely(PyList_CheckExact(__pyx_t_2)) || PyTuple_CheckExact(__pyx_t_2)) {
    __pyx_t_3 = __pyx_t_2; __Pyx_INCREF(__pyx_t_3); __pyx_t_1 = 0;
    __pyx_t_4 = NULL;
  } else {
    __pyx_t_1 = -1; __pyx_t_3 = PyObject_GetIter(__pyx_t_2); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_3);
    __pyx_t_4 = Py_TYPE(__pyx_t_3)->tp_iternext; if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  }
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  for (;;) {
    if (likely(!__pyx_t_4)) {
      if (likely(PyList_CheckExact(__pyx_t_3))) {
        if (__pyx_t_1 >= PyList_GET_SIZE(__pyx_t_3)) break;
        #if CYTHON_COMPILING_IN_CPYTHON
        __pyx_t_2 = PyList_GET_ITEM(__pyx_t_3, __pyx_t_1); __Pyx_INCREF(__pyx_t_2); __pyx_t_1++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #else
        __pyx_t_2 = PySequence_ITEM(__pyx_t_3, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #endif
      } else {
        if (__pyx_t_1 >= PyTuple_GET_SIZE(__pyx_t_3)) break;
        #if CYTHON_COMPILING_IN_CPYTHON
        __pyx_t_2 = PyTuple_GET_ITEM(__pyx_t_3, __pyx_t_1); __Pyx_INCREF(__pyx_t_2); __pyx_t_1++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #else
        __pyx_t_2 = PySequence_ITEM(__pyx_t_3, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        #endif
      }
    } else {
      __pyx_t_2 = __pyx_t_4(__pyx_t_3);
      if (unlikely(!__pyx_t_2)) {
        PyObject* exc_type = PyErr_Occurred();
        if (exc_type) {
          if (likely(exc_type == PyExc_StopIteration || PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();
          else {__pyx_filename = __pyx_f[0]; __pyx_lineno = 12; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        }
        break;
      }
      __Pyx_GOTREF(__pyx_t_2);
    }
    __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_2);
    __pyx_t_2 = 0;
/* … */
  }
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
+13:         column[0] = j
    if (unlikely(__Pyx_SetItemInt(__pyx_v_column, 0, __pyx_v_j, long, 1, __Pyx_PyInt_From_long, 0, 0, 0) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 13; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
+14:         last_diag = j - 1
    __pyx_t_2 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 14; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_XDECREF_SET(__pyx_v_last_diag, __pyx_t_2);
    __pyx_t_2 = 0;
+15:         for i in range(1, n1 + 1):
    __pyx_t_2 = PyNumber_Add(__pyx_v_n1, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __pyx_t_5 = PyTuple_New(2); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_5);
    __Pyx_INCREF(__pyx_int_1);
    PyTuple_SET_ITEM(__pyx_t_5, 0, __pyx_int_1);
    __Pyx_GIVEREF(__pyx_int_1);
    PyTuple_SET_ITEM(__pyx_t_5, 1, __pyx_t_2);
    __Pyx_GIVEREF(__pyx_t_2);
    __pyx_t_2 = 0;
    __pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_5, NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
    if (likely(PyList_CheckExact(__pyx_t_2)) || PyTuple_CheckExact(__pyx_t_2)) {
      __pyx_t_5 = __pyx_t_2; __Pyx_INCREF(__pyx_t_5); __pyx_t_6 = 0;
      __pyx_t_7 = NULL;
    } else {
      __pyx_t_6 = -1; __pyx_t_5 = PyObject_GetIter(__pyx_t_2); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_5);
      __pyx_t_7 = Py_TYPE(__pyx_t_5)->tp_iternext; if (unlikely(!__pyx_t_7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    }
    __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
    for (;;) {
      if (likely(!__pyx_t_7)) {
        if (likely(PyList_CheckExact(__pyx_t_5))) {
          if (__pyx_t_6 >= PyList_GET_SIZE(__pyx_t_5)) break;
          #if CYTHON_COMPILING_IN_CPYTHON
          __pyx_t_2 = PyList_GET_ITEM(__pyx_t_5, __pyx_t_6); __Pyx_INCREF(__pyx_t_2); __pyx_t_6++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #else
          __pyx_t_2 = PySequence_ITEM(__pyx_t_5, __pyx_t_6); __pyx_t_6++; if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #endif
        } else {
          if (__pyx_t_6 >= PyTuple_GET_SIZE(__pyx_t_5)) break;
          #if CYTHON_COMPILING_IN_CPYTHON
          __pyx_t_2 = PyTuple_GET_ITEM(__pyx_t_5, __pyx_t_6); __Pyx_INCREF(__pyx_t_2); __pyx_t_6++; if (unlikely(0 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #else
          __pyx_t_2 = PySequence_ITEM(__pyx_t_5, __pyx_t_6); __pyx_t_6++; if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          #endif
        }
      } else {
        __pyx_t_2 = __pyx_t_7(__pyx_t_5);
        if (unlikely(!__pyx_t_2)) {
          PyObject* exc_type = PyErr_Occurred();
          if (exc_type) {
            if (likely(exc_type == PyExc_StopIteration || PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();
            else {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
          }
          break;
        }
        __Pyx_GOTREF(__pyx_t_2);
      }
      __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_2);
      __pyx_t_2 = 0;
/* … */
    }
    __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
+16:             current = column[i]
      __pyx_t_2 = PyObject_GetItem(__pyx_v_column, __pyx_v_i); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 16; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __Pyx_XDECREF_SET(__pyx_v_current, __pyx_t_2);
      __pyx_t_2 = 0;
+17:             cost = 0 if s1[i-1] == s2[j-1] else 1
      __pyx_t_8 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_8)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_8);
      __pyx_t_9 = PyObject_GetItem(__pyx_v_s1, __pyx_t_8); if (unlikely(__pyx_t_9 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_9);
      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;
      __pyx_t_8 = PyNumber_Subtract(__pyx_v_j, __pyx_int_1); if (unlikely(!__pyx_t_8)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_8);
      __pyx_t_10 = PyObject_GetItem(__pyx_v_s2, __pyx_t_8); if (unlikely(__pyx_t_10 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_10);
      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;
      __pyx_t_8 = PyObject_RichCompare(__pyx_t_9, __pyx_t_10, Py_EQ); __Pyx_XGOTREF(__pyx_t_8); if (unlikely(!__pyx_t_8)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_9); __pyx_t_9 = 0;
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      __pyx_t_11 = __Pyx_PyObject_IsTrue(__pyx_t_8); if (unlikely(__pyx_t_11 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 17; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;
      if (__pyx_t_11) {
        __Pyx_INCREF(__pyx_int_0);
        __pyx_t_2 = __pyx_int_0;
      } else {
        __Pyx_INCREF(__pyx_int_1);
        __pyx_t_2 = __pyx_int_1;
      }
      __Pyx_XDECREF_SET(__pyx_v_cost, __pyx_t_2);
      __pyx_t_2 = 0;
+18:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_2 = PyNumber_Subtract(__pyx_v_i, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_8 = PyObject_GetItem(__pyx_v_column, __pyx_t_2); if (unlikely(__pyx_t_8 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_8);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_2 = PyNumber_Add(__pyx_t_8, __pyx_int_1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_2);
      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;
      __pyx_t_8 = PyNumber_Add(__pyx_v_last_diag, __pyx_v_cost); if (unlikely(!__pyx_t_8)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_8);
      __pyx_t_10 = PyObject_GetItem(__pyx_v_column, __pyx_v_i); if (unlikely(__pyx_t_10 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_10);
      __pyx_t_9 = PyNumber_Add(__pyx_t_10, __pyx_int_1); if (unlikely(!__pyx_t_9)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_9);
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      __pyx_t_12 = PyObject_RichCompare(__pyx_t_2, __pyx_t_9, Py_LT); __Pyx_XGOTREF(__pyx_t_12); if (unlikely(!__pyx_t_12)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __pyx_t_11 = __Pyx_PyObject_IsTrue(__pyx_t_12); if (unlikely(__pyx_t_11 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_12); __pyx_t_12 = 0;
      if (__pyx_t_11) {
        __Pyx_INCREF(__pyx_t_2);
        __pyx_t_10 = __pyx_t_2;
      } else {
        __Pyx_INCREF(__pyx_t_9);
        __pyx_t_10 = __pyx_t_9;
      }
      __Pyx_DECREF(__pyx_t_9); __pyx_t_9 = 0;
      __Pyx_INCREF(__pyx_t_10);
      __pyx_t_9 = __pyx_t_10;
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      __pyx_t_12 = PyObject_RichCompare(__pyx_t_8, __pyx_t_9, Py_LT); __Pyx_XGOTREF(__pyx_t_12); if (unlikely(!__pyx_t_12)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __pyx_t_11 = __Pyx_PyObject_IsTrue(__pyx_t_12); if (unlikely(__pyx_t_11 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_12); __pyx_t_12 = 0;
      if (__pyx_t_11) {
        __Pyx_INCREF(__pyx_t_8);
        __pyx_t_10 = __pyx_t_8;
      } else {
        __Pyx_INCREF(__pyx_t_9);
        __pyx_t_10 = __pyx_t_9;
      }
      __Pyx_DECREF(__pyx_t_9); __pyx_t_9 = 0;
      __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0;
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_2 = __pyx_t_10;
      __Pyx_INCREF(__pyx_t_2);
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      if (unlikely(PyObject_SetItem(__pyx_v_column, __pyx_v_i, __pyx_t_2) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
+19:             last_diag = current
      __Pyx_INCREF(__pyx_v_current);
      __Pyx_DECREF_SET(__pyx_v_last_diag, __pyx_v_current);
 20: 
+21:     return column[n1]
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_3 = PyObject_GetItem(__pyx_v_column, __pyx_v_n1); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
  __Pyx_GOTREF(__pyx_t_3);
  __pyx_r = __pyx_t_3;
  __pyx_t_3 = 0;
  goto __pyx_L0;

In [7]:

    

%%cython --annotate
import cython

import numpy as np
cimport numpy as np

@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_3(const char* s1, const char* s2):

    cdef int n1 = len(s1)
    cdef int n2 = len(s2)
    cdef int current, last_diag, cost
    cdef int i, j
    
    column = range(n1 + 1)
    
    for j in range(1, n2 + 1):
        column[0] = j
        last_diag = j - 1
        for i in range(1, n1 + 1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    return column[n1]


    

    
Out[7]:









    
    
    


Generated by Cython 0.22
+01: import cython
  __pyx_t_1 = PyDict_New(); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_test, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 02: 
+03: import numpy as np
  __pyx_t_1 = __Pyx_Import(__pyx_n_s_numpy, 0, -1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_np, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 04: cimport numpy as np
 05: 
 06: @cython.boundscheck(False)
 07: @cython.wraparound(False)
+08: def levenshtein_3(const char* s1, const char* s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_1levenshtein_3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_1levenshtein_3 = {"levenshtein_3", (PyCFunction)__pyx_pw_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_1levenshtein_3, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_1levenshtein_3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  char const *__pyx_v_s1;
  char const *__pyx_v_s2;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_3 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_3", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_3") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = __Pyx_PyObject_AsString(values[0]); if (unlikely((!__pyx_v_s1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
    __pyx_v_s2 = __Pyx_PyObject_AsString(values[1]); if (unlikely((!__pyx_v_s2) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_3", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339.levenshtein_3", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_levenshtein_3(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_levenshtein_3(CYTHON_UNUSED PyObject *__pyx_self, char const *__pyx_v_s1, char const *__pyx_v_s2) {
  int __pyx_v_n1;
  int __pyx_v_n2;
  int __pyx_v_current;
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_i;
  int __pyx_v_j;
  PyObject *__pyx_v_column = NULL;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_3", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_10);
  __Pyx_XDECREF(__pyx_t_11);
  __Pyx_XDECREF(__pyx_t_13);
  __Pyx_AddTraceback("_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339.levenshtein_3", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XDECREF(__pyx_v_column);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__7 = PyTuple_Pack(10, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_current, __pyx_n_s_last_diag, __pyx_n_s_cost, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_column); if (unlikely(!__pyx_tuple__7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__7);
  __Pyx_GIVEREF(__pyx_tuple__7);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_24e8ef7b5aeaa688fdbd621ed1748339_1levenshtein_3, NULL, __pyx_n_s_cython_magic_24e8ef7b5aeaa688fd); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_3, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 09: 
+10:     cdef int n1 = len(s1)
  __pyx_t_1 = strlen(__pyx_v_s1); 
  __pyx_v_n1 = __pyx_t_1;
+11:     cdef int n2 = len(s2)
  __pyx_t_1 = strlen(__pyx_v_s2); 
  __pyx_v_n2 = __pyx_t_1;
 12:     cdef int current, last_diag, cost
 13:     cdef int i, j
 14: 
+15:     column = range(n1 + 1)
  __pyx_t_2 = __Pyx_PyInt_From_long((__pyx_v_n1 + 1)); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_range, __pyx_t_3, NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 15; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __pyx_v_column = __pyx_t_2;
  __pyx_t_2 = 0;
 16: 
+17:     for j in range(1, n2 + 1):
  __pyx_t_4 = (__pyx_v_n2 + 1);
  for (__pyx_t_5 = 1; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
    __pyx_v_j = __pyx_t_5;
+18:         column[0] = j
    __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_j); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_GOTREF(__pyx_t_2);
    if (unlikely(__Pyx_SetItemInt(__pyx_v_column, 0, __pyx_t_2, long, 1, __Pyx_PyInt_From_long, 0, 0, 0) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 18; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
+19:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+20:         for i in range(1, n1 + 1):
    __pyx_t_6 = (__pyx_v_n1 + 1);
    for (__pyx_t_7 = 1; __pyx_t_7 < __pyx_t_6; __pyx_t_7+=1) {
      __pyx_v_i = __pyx_t_7;
+21:             current = column[i]
      __pyx_t_2 = __Pyx_GetItemInt(__pyx_v_column, __pyx_v_i, int, 1, __Pyx_PyInt_From_int, 0, 0, 0); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_8 = __Pyx_PyInt_As_int(__pyx_t_2); if (unlikely((__pyx_t_8 == (int)-1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_v_current = __pyx_t_8;
+22:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_8 = 0;
      } else {
        __pyx_t_8 = 1;
      }
      __pyx_v_cost = __pyx_t_8;
+23:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_9 = (__pyx_v_i - 1);
      __pyx_t_2 = __Pyx_GetItemInt(__pyx_v_column, __pyx_t_9, long, 1, __Pyx_PyInt_From_long, 0, 0, 0); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_3 = PyNumber_Add(__pyx_t_2, __pyx_int_1); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_3);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_8 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_2 = __Pyx_GetItemInt(__pyx_v_column, __pyx_v_i, int, 1, __Pyx_PyInt_From_int, 0, 0, 0); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_10 = PyNumber_Add(__pyx_t_2, __pyx_int_1); if (unlikely(!__pyx_t_10)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_10);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_11 = PyObject_RichCompare(__pyx_t_3, __pyx_t_10, Py_LT); __Pyx_XGOTREF(__pyx_t_11); if (unlikely(!__pyx_t_11)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __pyx_t_12 = __Pyx_PyObject_IsTrue(__pyx_t_11); if (unlikely(__pyx_t_12 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_11); __pyx_t_11 = 0;
      if (__pyx_t_12) {
        __Pyx_INCREF(__pyx_t_3);
        __pyx_t_2 = __pyx_t_3;
      } else {
        __Pyx_INCREF(__pyx_t_10);
        __pyx_t_2 = __pyx_t_10;
      }
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      __Pyx_INCREF(__pyx_t_2);
      __pyx_t_10 = __pyx_t_2;
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_11 = __Pyx_PyInt_From_int(__pyx_t_8); if (unlikely(!__pyx_t_11)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_GOTREF(__pyx_t_11);
      __pyx_t_13 = PyObject_RichCompare(__pyx_t_11, __pyx_t_10, Py_LT); __Pyx_XGOTREF(__pyx_t_13); if (unlikely(!__pyx_t_13)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_11); __pyx_t_11 = 0;
      __pyx_t_12 = __Pyx_PyObject_IsTrue(__pyx_t_13); if (unlikely(__pyx_t_12 < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_13); __pyx_t_13 = 0;
      if (__pyx_t_12) {
        __pyx_t_13 = __Pyx_PyInt_From_int(__pyx_t_8); if (unlikely(!__pyx_t_13)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
        __Pyx_GOTREF(__pyx_t_13);
        __pyx_t_2 = __pyx_t_13;
        __pyx_t_13 = 0;
      } else {
        __Pyx_INCREF(__pyx_t_10);
        __pyx_t_2 = __pyx_t_10;
      }
      __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
      __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
      __pyx_t_3 = __pyx_t_2;
      __Pyx_INCREF(__pyx_t_3);
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      if (unlikely(__Pyx_SetItemInt(__pyx_v_column, __pyx_v_i, __pyx_t_3, int, 1, __Pyx_PyInt_From_int, 0, 0, 0) < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 23; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
+24:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 25: 
+26:     return column[n1]
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_3 = __Pyx_GetItemInt(__pyx_v_column, __pyx_v_n1, int, 1, __Pyx_PyInt_From_int, 0, 0, 0); if (unlikely(__pyx_t_3 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 26; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
  __Pyx_GOTREF(__pyx_t_3);
  __pyx_r = __pyx_t_3;
  __pyx_t_3 = 0;
  goto __pyx_L0;

In [8]:

    

%%cython --annotate
import cython

import numpy as np
cimport numpy as np

np.import_array()

@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_4(const char* s1, const char* s2):

    cdef int n1 = len(s1)
    cdef int n2 = len(s2)
    cdef int last_diag, cost, current
    
    cdef Py_ssize_t i, j
    
    cdef Py_ssize_t m1 = n1 + 1
    cdef Py_ssize_t m2 = n2 + 1

    cdef np.ndarray[np.int_t, ndim=1] column = np.zeros(m1, dtype=np.int)
    
    for i in range(m1):
        column[i] = i

    for j in range(1, m2):
        column[0] = j
        last_diag = j - 1
        for i in range(1, m1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    return column[n1]


    

    
Out[8]:









    
    
    


Generated by Cython 0.22
+01: import cython
  __pyx_t_1 = PyDict_New(); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_test, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 02: 
+03: import numpy as np
  __pyx_t_1 = __Pyx_Import(__pyx_n_s_numpy, 0, -1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_np, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 04: cimport numpy as np
 05: 
+06: np.import_array()
  import_array();
 07: 
 08: @cython.boundscheck(False)
 09: @cython.wraparound(False)
+10: def levenshtein_4(const char* s1, const char* s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_1levenshtein_4(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_1levenshtein_4 = {"levenshtein_4", (PyCFunction)__pyx_pw_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_1levenshtein_4, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_1levenshtein_4(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  char const *__pyx_v_s1;
  char const *__pyx_v_s2;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_4 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_4", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_4") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = __Pyx_PyObject_AsString(values[0]); if (unlikely((!__pyx_v_s1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
    __pyx_v_s2 = __Pyx_PyObject_AsString(values[1]); if (unlikely((!__pyx_v_s2) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_4", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_32e394afd1bc7243ecf340cd13c65392.levenshtein_4", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_levenshtein_4(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_levenshtein_4(CYTHON_UNUSED PyObject *__pyx_self, char const *__pyx_v_s1, char const *__pyx_v_s2) {
  int __pyx_v_n1;
  int __pyx_v_n2;
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_current;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  Py_ssize_t __pyx_v_m1;
  Py_ssize_t __pyx_v_m2;
  PyArrayObject *__pyx_v_column = 0;
  __Pyx_LocalBuf_ND __pyx_pybuffernd_column;
  __Pyx_Buffer __pyx_pybuffer_column;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_4", 0);
  __pyx_pybuffer_column.pybuffer.buf = NULL;
  __pyx_pybuffer_column.refcount = 0;
  __pyx_pybuffernd_column.data = NULL;
  __pyx_pybuffernd_column.rcbuffer = &__pyx_pybuffer_column;
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_4);
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_XDECREF(__pyx_t_6);
  { PyObject *__pyx_type, *__pyx_value, *__pyx_tb;
    __Pyx_ErrFetch(&__pyx_type, &__pyx_value, &__pyx_tb);
    __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_column.rcbuffer->pybuffer);
  __Pyx_ErrRestore(__pyx_type, __pyx_value, __pyx_tb);}
  __Pyx_AddTraceback("_cython_magic_32e394afd1bc7243ecf340cd13c65392.levenshtein_4", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  goto __pyx_L2;
  __pyx_L0:;
  __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_column.rcbuffer->pybuffer);
  __pyx_L2:;
  __Pyx_XDECREF((PyObject *)__pyx_v_column);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__7 = PyTuple_Pack(12, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_last_diag, __pyx_n_s_cost, __pyx_n_s_current, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_m1, __pyx_n_s_m2, __pyx_n_s_column); if (unlikely(!__pyx_tuple__7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__7);
  __Pyx_GIVEREF(__pyx_tuple__7);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_32e394afd1bc7243ecf340cd13c65392_1levenshtein_4, NULL, __pyx_n_s_cython_magic_32e394afd1bc7243ec); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_4, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 11: 
+12:     cdef int n1 = len(s1)
  __pyx_t_1 = strlen(__pyx_v_s1); 
  __pyx_v_n1 = __pyx_t_1;
+13:     cdef int n2 = len(s2)
  __pyx_t_1 = strlen(__pyx_v_s2); 
  __pyx_v_n2 = __pyx_t_1;
 14:     cdef int last_diag, cost, current
 15: 
 16:     cdef Py_ssize_t i, j
 17: 
+18:     cdef Py_ssize_t m1 = n1 + 1
  __pyx_v_m1 = (__pyx_v_n1 + 1);
+19:     cdef Py_ssize_t m2 = n2 + 1
  __pyx_v_m2 = (__pyx_v_n2 + 1);
 20: 
+21:     cdef np.ndarray[np.int_t, ndim=1] column = np.zeros(m1, dtype=np.int)
  __pyx_t_2 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = __Pyx_PyObject_GetAttrStr(__pyx_t_2, __pyx_n_s_zeros); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  __pyx_t_2 = PyInt_FromSsize_t(__pyx_v_m1); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_4 = PyTuple_New(1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_4);
  PyTuple_SET_ITEM(__pyx_t_4, 0, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_5 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_5);
  __pyx_t_6 = __Pyx_PyObject_GetAttrStr(__pyx_t_5, __pyx_n_s_int); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
  if (PyDict_SetItem(__pyx_t_2, __pyx_n_s_dtype, __pyx_t_6) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
  __pyx_t_6 = __Pyx_PyObject_Call(__pyx_t_3, __pyx_t_4, __pyx_t_2); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  if (!(likely(((__pyx_t_6) == Py_None) || likely(__Pyx_TypeTest(__pyx_t_6, __pyx_ptype_5numpy_ndarray))))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_7 = ((PyArrayObject *)__pyx_t_6);
  {
    __Pyx_BufFmt_StackElem __pyx_stack[1];
    if (unlikely(__Pyx_GetBufferAndValidate(&__pyx_pybuffernd_column.rcbuffer->pybuffer, (PyObject*)__pyx_t_7, &__Pyx_TypeInfo_nn___pyx_t_5numpy_int_t, PyBUF_FORMAT| PyBUF_STRIDES| PyBUF_WRITABLE, 1, 0, __pyx_stack) == -1)) {
      __pyx_v_column = ((PyArrayObject *)Py_None); __Pyx_INCREF(Py_None); __pyx_pybuffernd_column.rcbuffer->pybuffer.buf = NULL;
      {__pyx_filename = __pyx_f[0]; __pyx_lineno = 21; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    } else {__pyx_pybuffernd_column.diminfo[0].strides = __pyx_pybuffernd_column.rcbuffer->pybuffer.strides[0]; __pyx_pybuffernd_column.diminfo[0].shape = __pyx_pybuffernd_column.rcbuffer->pybuffer.shape[0];
    }
  }
  __pyx_t_7 = 0;
  __pyx_v_column = ((PyArrayObject *)__pyx_t_6);
  __pyx_t_6 = 0;
 22: 
+23:     for i in range(m1):
  __pyx_t_8 = __pyx_v_m1;
  for (__pyx_t_9 = 0; __pyx_t_9 < __pyx_t_8; __pyx_t_9+=1) {
    __pyx_v_i = __pyx_t_9;
+24:         column[i] = i
    __pyx_t_10 = __pyx_v_i;
    *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_10, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_v_i;
  }
 25: 
+26:     for j in range(1, m2):
  __pyx_t_8 = __pyx_v_m2;
  for (__pyx_t_9 = 1; __pyx_t_9 < __pyx_t_8; __pyx_t_9+=1) {
    __pyx_v_j = __pyx_t_9;
+27:         column[0] = j
    __pyx_t_11 = 0;
    *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_11, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_v_j;
+28:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+29:         for i in range(1, m1):
    __pyx_t_12 = __pyx_v_m1;
    for (__pyx_t_13 = 1; __pyx_t_13 < __pyx_t_12; __pyx_t_13+=1) {
      __pyx_v_i = __pyx_t_13;
+30:             current = column[i]
      __pyx_t_14 = __pyx_v_i;
      __pyx_v_current = (*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_14, __pyx_pybuffernd_column.diminfo[0].strides));
+31:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_15 = 0;
      } else {
        __pyx_t_15 = 1;
      }
      __pyx_v_cost = __pyx_t_15;
+32:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_16 = (__pyx_v_i - 1);
      __pyx_t_17 = ((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_16, __pyx_pybuffernd_column.diminfo[0].strides)) + 1);
      __pyx_t_15 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_18 = __pyx_v_i;
      __pyx_t_19 = ((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_18, __pyx_pybuffernd_column.diminfo[0].strides)) + 1);
      if (((__pyx_t_17 < __pyx_t_19) != 0)) {
        __pyx_t_20 = __pyx_t_17;
      } else {
        __pyx_t_20 = __pyx_t_19;
      }
      __pyx_t_19 = __pyx_t_20;
      if (((__pyx_t_15 < __pyx_t_19) != 0)) {
        __pyx_t_20 = __pyx_t_15;
      } else {
        __pyx_t_20 = __pyx_t_19;
      }
      __pyx_t_21 = __pyx_v_i;
      *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_21, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_t_20;
+33:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 34: 
+35:     return column[n1]
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_15 = __pyx_v_n1;
  __pyx_t_6 = __Pyx_PyInt_From_npy_long((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_15, __pyx_pybuffernd_column.diminfo[0].strides))); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 35; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __pyx_r = __pyx_t_6;
  __pyx_t_6 = 0;
  goto __pyx_L0;

In [9]:

    

%%cython --annotate
import cython

import numpy as np
cimport numpy as np

np.import_array()

@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_5(const char* s1, const char* s2):

    cdef int n1 = len(s1)
    cdef int n2 = len(s2)
    cdef int last_diag, cost, current
    
    cdef Py_ssize_t i, j
    
    cdef Py_ssize_t m1 = n1 + 1
    cdef Py_ssize_t m2 = n2 + 1
    
    cdef np.npy_intp* dims = [m1]
    cdef np.ndarray[np.int_t, ndim=1] column = np.PyArray_ZEROS(1, dims, np.NPY_INT, 0)
    
    for i in range(m1):
        column[i] = i

    for j in range(1, m2):
        column[0] = j
        last_diag = j - 1
        for i in range(1, m1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    return column[n1]


    

    
Out[9]:









    
    
    


Generated by Cython 0.22
+01: import cython
  __pyx_t_1 = PyDict_New(); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_test, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 02: 
+03: import numpy as np
  __pyx_t_1 = __Pyx_Import(__pyx_n_s_numpy, 0, -1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_np, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 3; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 04: cimport numpy as np
 05: 
+06: np.import_array()
  import_array();
 07: 
 08: @cython.boundscheck(False)
 09: @cython.wraparound(False)
+10: def levenshtein_5(const char* s1, const char* s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_1levenshtein_5(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_1levenshtein_5 = {"levenshtein_5", (PyCFunction)__pyx_pw_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_1levenshtein_5, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_1levenshtein_5(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  char const *__pyx_v_s1;
  char const *__pyx_v_s2;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_5 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_5", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_5") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = __Pyx_PyObject_AsString(values[0]); if (unlikely((!__pyx_v_s1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
    __pyx_v_s2 = __Pyx_PyObject_AsString(values[1]); if (unlikely((!__pyx_v_s2) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_5", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_3663cb364bef0ea34540c22c724ad2f0.levenshtein_5", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_levenshtein_5(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_levenshtein_5(CYTHON_UNUSED PyObject *__pyx_self, char const *__pyx_v_s1, char const *__pyx_v_s2) {
  int __pyx_v_n1;
  int __pyx_v_n2;
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_current;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  Py_ssize_t __pyx_v_m1;
  Py_ssize_t __pyx_v_m2;
  npy_intp *__pyx_v_dims;
  PyArrayObject *__pyx_v_column = 0;
  __Pyx_LocalBuf_ND __pyx_pybuffernd_column;
  __Pyx_Buffer __pyx_pybuffer_column;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_5", 0);
  __pyx_pybuffer_column.pybuffer.buf = NULL;
  __pyx_pybuffer_column.refcount = 0;
  __pyx_pybuffernd_column.data = NULL;
  __pyx_pybuffernd_column.rcbuffer = &__pyx_pybuffer_column;
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_3);
  { PyObject *__pyx_type, *__pyx_value, *__pyx_tb;
    __Pyx_ErrFetch(&__pyx_type, &__pyx_value, &__pyx_tb);
    __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_column.rcbuffer->pybuffer);
  __Pyx_ErrRestore(__pyx_type, __pyx_value, __pyx_tb);}
  __Pyx_AddTraceback("_cython_magic_3663cb364bef0ea34540c22c724ad2f0.levenshtein_5", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  goto __pyx_L2;
  __pyx_L0:;
  __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_column.rcbuffer->pybuffer);
  __pyx_L2:;
  __Pyx_XDECREF((PyObject *)__pyx_v_column);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__7 = PyTuple_Pack(13, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_last_diag, __pyx_n_s_cost, __pyx_n_s_current, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_m1, __pyx_n_s_m2, __pyx_n_s_dims, __pyx_n_s_column); if (unlikely(!__pyx_tuple__7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__7);
  __Pyx_GIVEREF(__pyx_tuple__7);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_3663cb364bef0ea34540c22c724ad2f0_1levenshtein_5, NULL, __pyx_n_s_cython_magic_3663cb364bef0ea345); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_5, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 10; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 11: 
+12:     cdef int n1 = len(s1)
  __pyx_t_1 = strlen(__pyx_v_s1); 
  __pyx_v_n1 = __pyx_t_1;
+13:     cdef int n2 = len(s2)
  __pyx_t_1 = strlen(__pyx_v_s2); 
  __pyx_v_n2 = __pyx_t_1;
 14:     cdef int last_diag, cost, current
 15: 
 16:     cdef Py_ssize_t i, j
 17: 
+18:     cdef Py_ssize_t m1 = n1 + 1
  __pyx_v_m1 = (__pyx_v_n1 + 1);
+19:     cdef Py_ssize_t m2 = n2 + 1
  __pyx_v_m2 = (__pyx_v_n2 + 1);
 20: 
+21:     cdef np.npy_intp* dims = [m1]
  __pyx_t_2[0] = __pyx_v_m1;
  __pyx_v_dims = __pyx_t_2;
+22:     cdef np.ndarray[np.int_t, ndim=1] column = np.PyArray_ZEROS(1, dims, np.NPY_INT, 0)
  __pyx_t_3 = PyArray_ZEROS(1, __pyx_v_dims, NPY_INT, 0); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 22; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  if (!(likely(((__pyx_t_3) == Py_None) || likely(__Pyx_TypeTest(__pyx_t_3, __pyx_ptype_5numpy_ndarray))))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 22; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_4 = ((PyArrayObject *)__pyx_t_3);
  {
    __Pyx_BufFmt_StackElem __pyx_stack[1];
    if (unlikely(__Pyx_GetBufferAndValidate(&__pyx_pybuffernd_column.rcbuffer->pybuffer, (PyObject*)__pyx_t_4, &__Pyx_TypeInfo_nn___pyx_t_5numpy_int_t, PyBUF_FORMAT| PyBUF_STRIDES| PyBUF_WRITABLE, 1, 0, __pyx_stack) == -1)) {
      __pyx_v_column = ((PyArrayObject *)Py_None); __Pyx_INCREF(Py_None); __pyx_pybuffernd_column.rcbuffer->pybuffer.buf = NULL;
      {__pyx_filename = __pyx_f[0]; __pyx_lineno = 22; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    } else {__pyx_pybuffernd_column.diminfo[0].strides = __pyx_pybuffernd_column.rcbuffer->pybuffer.strides[0]; __pyx_pybuffernd_column.diminfo[0].shape = __pyx_pybuffernd_column.rcbuffer->pybuffer.shape[0];
    }
  }
  __pyx_t_4 = 0;
  __pyx_v_column = ((PyArrayObject *)__pyx_t_3);
  __pyx_t_3 = 0;
 23: 
+24:     for i in range(m1):
  __pyx_t_5 = __pyx_v_m1;
  for (__pyx_t_6 = 0; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
    __pyx_v_i = __pyx_t_6;
+25:         column[i] = i
    __pyx_t_7 = __pyx_v_i;
    *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_7, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_v_i;
  }
 26: 
+27:     for j in range(1, m2):
  __pyx_t_5 = __pyx_v_m2;
  for (__pyx_t_6 = 1; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
    __pyx_v_j = __pyx_t_6;
+28:         column[0] = j
    __pyx_t_8 = 0;
    *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_8, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_v_j;
+29:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+30:         for i in range(1, m1):
    __pyx_t_9 = __pyx_v_m1;
    for (__pyx_t_10 = 1; __pyx_t_10 < __pyx_t_9; __pyx_t_10+=1) {
      __pyx_v_i = __pyx_t_10;
+31:             current = column[i]
      __pyx_t_11 = __pyx_v_i;
      __pyx_v_current = (*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_11, __pyx_pybuffernd_column.diminfo[0].strides));
+32:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_12 = 0;
      } else {
        __pyx_t_12 = 1;
      }
      __pyx_v_cost = __pyx_t_12;
+33:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_13 = (__pyx_v_i - 1);
      __pyx_t_14 = ((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_13, __pyx_pybuffernd_column.diminfo[0].strides)) + 1);
      __pyx_t_12 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_15 = __pyx_v_i;
      __pyx_t_16 = ((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_15, __pyx_pybuffernd_column.diminfo[0].strides)) + 1);
      if (((__pyx_t_14 < __pyx_t_16) != 0)) {
        __pyx_t_17 = __pyx_t_14;
      } else {
        __pyx_t_17 = __pyx_t_16;
      }
      __pyx_t_16 = __pyx_t_17;
      if (((__pyx_t_12 < __pyx_t_16) != 0)) {
        __pyx_t_17 = __pyx_t_12;
      } else {
        __pyx_t_17 = __pyx_t_16;
      }
      __pyx_t_18 = __pyx_v_i;
      *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_18, __pyx_pybuffernd_column.diminfo[0].strides) = __pyx_t_17;
+34:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 35: 
+36:     return column[n1]
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_12 = __pyx_v_n1;
  __pyx_t_3 = __Pyx_PyInt_From_npy_long((*__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_column.rcbuffer->pybuffer.buf, __pyx_t_12, __pyx_pybuffernd_column.diminfo[0].strides))); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 36; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __pyx_r = __pyx_t_3;
  __pyx_t_3 = 0;
  goto __pyx_L0;

In [10]:

    

%%cython --annotate
import cython

from libc.stdlib cimport abort, malloc, free


@cython.boundscheck(False)
@cython.wraparound(False)
def levenshtein_6(const char* s1, const char* s2):

    cdef int n1 = len(s1)
    cdef int n2 = len(s2)
    cdef int last_diag, cost, current
    
    cdef Py_ssize_t i, j
    
    cdef Py_ssize_t m1 = n1 + 1
    cdef Py_ssize_t m2 = n2 + 1
    
    cdef int* column = <int*> malloc(m1 * sizeof(int))
    if not column:
        abort()
    
    for i in range(m1):
        column[i] = i

    for j in range(1, m2):
        column[0] = j
        last_diag = j - 1
        for i in range(1, m1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
    
    current = column[n1]
    free(column)
    return current


    

    
Out[10]:









    
    
    


Generated by Cython 0.22
 01: import cython
 02: 
 03: from libc.stdlib cimport abort, malloc, free
 04: 
 05: 
 06: @cython.boundscheck(False)
 07: @cython.wraparound(False)
+08: def levenshtein_6(const char* s1, const char* s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_1levenshtein_6(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_1levenshtein_6 = {"levenshtein_6", (PyCFunction)__pyx_pw_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_1levenshtein_6, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_1levenshtein_6(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  char const *__pyx_v_s1;
  char const *__pyx_v_s2;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_6 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_6", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_6") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = __Pyx_PyObject_AsString(values[0]); if (unlikely((!__pyx_v_s1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
    __pyx_v_s2 = __Pyx_PyObject_AsString(values[1]); if (unlikely((!__pyx_v_s2) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_6", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_ea7b47679080cdb56ceea0858288dd5a.levenshtein_6", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_levenshtein_6(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_levenshtein_6(CYTHON_UNUSED PyObject *__pyx_self, char const *__pyx_v_s1, char const *__pyx_v_s2) {
  int __pyx_v_n1;
  int __pyx_v_n2;
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_current;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  Py_ssize_t __pyx_v_m1;
  Py_ssize_t __pyx_v_m2;
  int *__pyx_v_column;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_6", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_11);
  __Pyx_AddTraceback("_cython_magic_ea7b47679080cdb56ceea0858288dd5a.levenshtein_6", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple_ = PyTuple_Pack(12, __pyx_n_s_s1, __pyx_n_s_s2, __pyx_n_s_n1, __pyx_n_s_n2, __pyx_n_s_last_diag, __pyx_n_s_cost, __pyx_n_s_current, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_m1, __pyx_n_s_m2, __pyx_n_s_column); if (unlikely(!__pyx_tuple_)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple_);
  __Pyx_GIVEREF(__pyx_tuple_);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_ea7b47679080cdb56ceea0858288dd5a_1levenshtein_6, NULL, __pyx_n_s_cython_magic_ea7b47679080cdb56c); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_6, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 8; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 09: 
+10:     cdef int n1 = len(s1)
  __pyx_t_1 = strlen(__pyx_v_s1); 
  __pyx_v_n1 = __pyx_t_1;
+11:     cdef int n2 = len(s2)
  __pyx_t_1 = strlen(__pyx_v_s2); 
  __pyx_v_n2 = __pyx_t_1;
 12:     cdef int last_diag, cost, current
 13: 
 14:     cdef Py_ssize_t i, j
 15: 
+16:     cdef Py_ssize_t m1 = n1 + 1
  __pyx_v_m1 = (__pyx_v_n1 + 1);
+17:     cdef Py_ssize_t m2 = n2 + 1
  __pyx_v_m2 = (__pyx_v_n2 + 1);
 18: 
+19:     cdef int* column = <int*> malloc(m1 * sizeof(int))
  __pyx_v_column = ((int *)malloc((__pyx_v_m1 * (sizeof(int)))));
+20:     if not column:
  __pyx_t_2 = ((!(__pyx_v_column != 0)) != 0);
  if (__pyx_t_2) {
+21:         abort()
    abort();
    goto __pyx_L3;
  }
  __pyx_L3:;
 22: 
+23:     for i in range(m1):
  __pyx_t_3 = __pyx_v_m1;
  for (__pyx_t_4 = 0; __pyx_t_4 < __pyx_t_3; __pyx_t_4+=1) {
    __pyx_v_i = __pyx_t_4;
+24:         column[i] = i
    (__pyx_v_column[__pyx_v_i]) = __pyx_v_i;
  }
 25: 
+26:     for j in range(1, m2):
  __pyx_t_3 = __pyx_v_m2;
  for (__pyx_t_4 = 1; __pyx_t_4 < __pyx_t_3; __pyx_t_4+=1) {
    __pyx_v_j = __pyx_t_4;
+27:         column[0] = j
    (__pyx_v_column[0]) = __pyx_v_j;
+28:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+29:         for i in range(1, m1):
    __pyx_t_5 = __pyx_v_m1;
    for (__pyx_t_6 = 1; __pyx_t_6 < __pyx_t_5; __pyx_t_6+=1) {
      __pyx_v_i = __pyx_t_6;
+30:             current = column[i]
      __pyx_v_current = (__pyx_v_column[__pyx_v_i]);
+31:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_7 = 0;
      } else {
        __pyx_t_7 = 1;
      }
      __pyx_v_cost = __pyx_t_7;
+32:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_8 = ((__pyx_v_column[(__pyx_v_i - 1)]) + 1);
      __pyx_t_7 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_9 = ((__pyx_v_column[__pyx_v_i]) + 1);
      if (((__pyx_t_8 < __pyx_t_9) != 0)) {
        __pyx_t_10 = __pyx_t_8;
      } else {
        __pyx_t_10 = __pyx_t_9;
      }
      __pyx_t_9 = __pyx_t_10;
      if (((__pyx_t_7 < __pyx_t_9) != 0)) {
        __pyx_t_10 = __pyx_t_7;
      } else {
        __pyx_t_10 = __pyx_t_9;
      }
      (__pyx_v_column[__pyx_v_i]) = __pyx_t_10;
+33:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 34: 
+35:     current = column[n1]
  __pyx_v_current = (__pyx_v_column[__pyx_v_n1]);
+36:     free(column)
  free(__pyx_v_column);
+37:     return current
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_11 = __Pyx_PyInt_From_int(__pyx_v_current); if (unlikely(!__pyx_t_11)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 37; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_11);
  __pyx_r = __pyx_t_11;
  __pyx_t_11 = 0;
  goto __pyx_L0;

In [11]:

    

%%cython --annotate
import cython

from libc.stdlib cimport abort, malloc, free

@cython.boundscheck(False)
@cython.wraparound(False)
cdef int cy_levenshtein(const char* s1, int n1, const char* s2, int n2) nogil:
    cdef int last_diag, cost, current
    cdef Py_ssize_t i, j
    cdef Py_ssize_t m1 = n1 + 1
    cdef Py_ssize_t m2 = n2 + 1
    
    if not n1:
        return n2
    if not n2:
        return n1
    
    cdef int* column = <int*> malloc(m1 * sizeof(int))
    if not column:
        abort()
    
    for i in range(m1):
        column[i] = i

    for j in range(1, m2):
        column[0] = j
        last_diag = j - 1
        for i in range(1, m1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    current = column[n1]
    free(column)
            
    return current

def levenshtein_7(s1, s2):
    return cy_levenshtein(s1, len(s1), s2, len(s2))


    

    
Out[11]:









    
    
    


Generated by Cython 0.22
 01: import cython
 02: 
 03: from libc.stdlib cimport abort, malloc, free
 04: 
 05: @cython.boundscheck(False)
 06: @cython.wraparound(False)
+07: cdef int cy_levenshtein(const char* s1, int n1, const char* s2, int n2) nogil:
static int __pyx_f_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_cy_levenshtein(char const *__pyx_v_s1, int __pyx_v_n1, char const *__pyx_v_s2, int __pyx_v_n2) {
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_current;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  Py_ssize_t __pyx_v_m1;
  Py_ssize_t __pyx_v_m2;
  int *__pyx_v_column;
  int __pyx_r;
/* … */
  /* function exit code */
  __pyx_L0:;
  return __pyx_r;
}
 08:     cdef int last_diag, cost, current
 09:     cdef Py_ssize_t i, j
+10:     cdef Py_ssize_t m1 = n1 + 1
  __pyx_v_m1 = (__pyx_v_n1 + 1);
+11:     cdef Py_ssize_t m2 = n2 + 1
  __pyx_v_m2 = (__pyx_v_n2 + 1);
 12: 
+13:     if not n1:
  __pyx_t_1 = ((!(__pyx_v_n1 != 0)) != 0);
  if (__pyx_t_1) {
+14:         return n2
    __pyx_r = __pyx_v_n2;
    goto __pyx_L0;
  }
+15:     if not n2:
  __pyx_t_1 = ((!(__pyx_v_n2 != 0)) != 0);
  if (__pyx_t_1) {
+16:         return n1
    __pyx_r = __pyx_v_n1;
    goto __pyx_L0;
  }
 17: 
+18:     cdef int* column = <int*> malloc(m1 * sizeof(int))
  __pyx_v_column = ((int *)malloc((__pyx_v_m1 * (sizeof(int)))));
+19:     if not column:
  __pyx_t_1 = ((!(__pyx_v_column != 0)) != 0);
  if (__pyx_t_1) {
+20:         abort()
    abort();
    goto __pyx_L5;
  }
  __pyx_L5:;
 21: 
+22:     for i in range(m1):
  __pyx_t_2 = __pyx_v_m1;
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
    __pyx_v_i = __pyx_t_3;
+23:         column[i] = i
    (__pyx_v_column[__pyx_v_i]) = __pyx_v_i;
  }
 24: 
+25:     for j in range(1, m2):
  __pyx_t_2 = __pyx_v_m2;
  for (__pyx_t_3 = 1; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
    __pyx_v_j = __pyx_t_3;
+26:         column[0] = j
    (__pyx_v_column[0]) = __pyx_v_j;
+27:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+28:         for i in range(1, m1):
    __pyx_t_4 = __pyx_v_m1;
    for (__pyx_t_5 = 1; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
      __pyx_v_i = __pyx_t_5;
+29:             current = column[i]
      __pyx_v_current = (__pyx_v_column[__pyx_v_i]);
+30:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_6 = 0;
      } else {
        __pyx_t_6 = 1;
      }
      __pyx_v_cost = __pyx_t_6;
+31:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_7 = ((__pyx_v_column[(__pyx_v_i - 1)]) + 1);
      __pyx_t_6 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_8 = ((__pyx_v_column[__pyx_v_i]) + 1);
      if (((__pyx_t_7 < __pyx_t_8) != 0)) {
        __pyx_t_9 = __pyx_t_7;
      } else {
        __pyx_t_9 = __pyx_t_8;
      }
      __pyx_t_8 = __pyx_t_9;
      if (((__pyx_t_6 < __pyx_t_8) != 0)) {
        __pyx_t_9 = __pyx_t_6;
      } else {
        __pyx_t_9 = __pyx_t_8;
      }
      (__pyx_v_column[__pyx_v_i]) = __pyx_t_9;
+32:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 33: 
+34:     current = column[n1]
  __pyx_v_current = (__pyx_v_column[__pyx_v_n1]);
+35:     free(column)
  free(__pyx_v_column);
 36: 
+37:     return current
  __pyx_r = __pyx_v_current;
  goto __pyx_L0;
 38: 
+39: def levenshtein_7(s1, s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_1levenshtein_7(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_1levenshtein_7 = {"levenshtein_7", (PyCFunction)__pyx_pw_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_1levenshtein_7, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_1levenshtein_7(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  PyObject *__pyx_v_s1 = 0;
  PyObject *__pyx_v_s2 = 0;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_7 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_7", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_7") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = values[0];
    __pyx_v_s2 = values[1];
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_7", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_fbafdc595ddd05c7e625e6962073908d.levenshtein_7", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_levenshtein_7(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_levenshtein_7(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_s1, PyObject *__pyx_v_s2) {
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_7", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_AddTraceback("_cython_magic_fbafdc595ddd05c7e625e6962073908d.levenshtein_7", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple_ = PyTuple_Pack(2, __pyx_n_s_s1, __pyx_n_s_s2); if (unlikely(!__pyx_tuple_)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple_);
  __Pyx_GIVEREF(__pyx_tuple_);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_1levenshtein_7, NULL, __pyx_n_s_cython_magic_fbafdc595ddd05c7e6); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_7, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 39; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
+40:     return cy_levenshtein(s1, len(s1), s2, len(s2))
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_1 = __Pyx_PyObject_AsString(__pyx_v_s1); if (unlikely((!__pyx_t_1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyObject_Length(__pyx_v_s1); if (unlikely(__pyx_t_2 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_3 = __Pyx_PyObject_AsString(__pyx_v_s2); if (unlikely((!__pyx_t_3) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_4 = PyObject_Length(__pyx_v_s2); if (unlikely(__pyx_t_4 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_5 = __Pyx_PyInt_From_int(__pyx_f_46_cython_magic_fbafdc595ddd05c7e625e6962073908d_cy_levenshtein(__pyx_t_1, __pyx_t_2, __pyx_t_3, __pyx_t_4)); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 40; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_5);
  __pyx_r = __pyx_t_5;
  __pyx_t_5 = 0;
  goto __pyx_L0;

In [12]:

    

%%cython --annotate -f -c-fopenmp --link-args=-fopenmp -c-g
# cython: cdivision=True
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdlib cimport abort, malloc, free

import numpy as np
cimport numpy as np

np.import_array()

from cython.parallel import parallel, prange

cdef int cy_levenshtein(const Py_UNICODE* s1, int n1, const Py_UNICODE* s2, int n2) nogil:
    cdef int last_diag, cost, current
    cdef Py_ssize_t i, j
    cdef Py_ssize_t m1 = n1 + 1
    cdef Py_ssize_t m2 = n2 + 1
    
    if not n1:
        return n2
    if not n2:
        return n1
    
    cdef int* column = <int*> malloc(m1 * sizeof(int))
    if not column:
        abort()
    
    for i in range(m1):
        column[i] = i

    for j in range(1, m2):
        column[0] = j
        last_diag = j - 1
        for i in range(1, m1):
            current = column[i]
            cost = 0 if s1[i-1] == s2[j-1] else 1
            column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
            last_diag = current
            
    current = column[n1]
    free(column)
            
    return current

def levenshtein_8(s1, s2):
    return cy_levenshtein(s1, len(s1), s2, len(s2))


def levenshtein_8_pdist(values):
    # condensed distance representation
    cdef int n = len(values)
    cdef int m = n * (n - 1) // 2
    cdef np.ndarray[np.int_t, ndim=1] result = np.zeros(m, dtype=np.int)
    
    cdef Py_ssize_t i, j
    cdef int offset

    for i in range(n):
        offset = i * n - (i + 1) * (i + 2) // 2
        for j in range(i + 1, n):
            result[offset + j] = cy_levenshtein(values[i], len(values[i]), values[j], len(values[j]))
    
    return result


def levenshtein_8_pdist_parallel(values):
    # condensed distance representation
    cdef int n = len(values)
    cdef int m = n * (n - 1) // 2
    cdef np.ndarray[np.int_t, ndim=1] result = np.zeros(m, dtype=np.int)
    
    cdef Py_ssize_t i, j
    cdef int offset
    
    cdef int* lengths = <int*> malloc(n * sizeof(int))        
    cdef Py_UNICODE** strings = <Py_UNICODE**> malloc(n * sizeof(Py_UNICODE*))

    for i in range(n):
        strings[i] = values[i]
        lengths[i] = len(strings[i])

    with nogil:
        for i in prange(n, schedule='guided'):
            offset = i * n - (i + 1) * (i + 2) // 2
            for j in prange(i + 1, n, schedule='guided'):
                result[offset + j] = cy_levenshtein(strings[i], lengths[i], strings[j], lengths[j])

    free(lengths)
    free(strings)
    
    return result


    

    
Out[12]:









    
    
    


Generated by Cython 0.22
+01: # cython: cdivision=True
  __pyx_t_1 = PyDict_New(); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_test, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 1; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 02: # cython: boundscheck=False
 03: # cython: wraparound=False
 04: 
 05: from libc.stdlib cimport abort, malloc, free
 06: 
+07: import numpy as np
  __pyx_t_1 = __Pyx_Import(__pyx_n_s_numpy, 0, -1); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_np, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 7; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 08: cimport numpy as np
 09: 
+10: np.import_array()
  import_array();
 11: 
 12: from cython.parallel import parallel, prange
 13: 
+14: cdef int cy_levenshtein(const Py_UNICODE* s1, int n1, const Py_UNICODE* s2, int n2) nogil:
static int __pyx_f_46_cython_magic_150fe167507bea5aa06eddab1200f03f_cy_levenshtein(Py_UNICODE const *__pyx_v_s1, int __pyx_v_n1, Py_UNICODE const *__pyx_v_s2, int __pyx_v_n2) {
  int __pyx_v_last_diag;
  int __pyx_v_cost;
  int __pyx_v_current;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  Py_ssize_t __pyx_v_m1;
  Py_ssize_t __pyx_v_m2;
  int *__pyx_v_column;
  int __pyx_r;
/* … */
  /* function exit code */
  __pyx_L0:;
  return __pyx_r;
}
 15:     cdef int last_diag, cost, current
 16:     cdef Py_ssize_t i, j
+17:     cdef Py_ssize_t m1 = n1 + 1
  __pyx_v_m1 = (__pyx_v_n1 + 1);
+18:     cdef Py_ssize_t m2 = n2 + 1
  __pyx_v_m2 = (__pyx_v_n2 + 1);
 19: 
+20:     if not n1:
  __pyx_t_1 = ((!(__pyx_v_n1 != 0)) != 0);
  if (__pyx_t_1) {
+21:         return n2
    __pyx_r = __pyx_v_n2;
    goto __pyx_L0;
  }
+22:     if not n2:
  __pyx_t_1 = ((!(__pyx_v_n2 != 0)) != 0);
  if (__pyx_t_1) {
+23:         return n1
    __pyx_r = __pyx_v_n1;
    goto __pyx_L0;
  }
 24: 
+25:     cdef int* column = <int*> malloc(m1 * sizeof(int))
  __pyx_v_column = ((int *)malloc((__pyx_v_m1 * (sizeof(int)))));
+26:     if not column:
  __pyx_t_1 = ((!(__pyx_v_column != 0)) != 0);
  if (__pyx_t_1) {
+27:         abort()
    abort();
    goto __pyx_L5;
  }
  __pyx_L5:;
 28: 
+29:     for i in range(m1):
  __pyx_t_2 = __pyx_v_m1;
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
    __pyx_v_i = __pyx_t_3;
+30:         column[i] = i
    (__pyx_v_column[__pyx_v_i]) = __pyx_v_i;
  }
 31: 
+32:     for j in range(1, m2):
  __pyx_t_2 = __pyx_v_m2;
  for (__pyx_t_3 = 1; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
    __pyx_v_j = __pyx_t_3;
+33:         column[0] = j
    (__pyx_v_column[0]) = __pyx_v_j;
+34:         last_diag = j - 1
    __pyx_v_last_diag = (__pyx_v_j - 1);
+35:         for i in range(1, m1):
    __pyx_t_4 = __pyx_v_m1;
    for (__pyx_t_5 = 1; __pyx_t_5 < __pyx_t_4; __pyx_t_5+=1) {
      __pyx_v_i = __pyx_t_5;
+36:             current = column[i]
      __pyx_v_current = (__pyx_v_column[__pyx_v_i]);
+37:             cost = 0 if s1[i-1] == s2[j-1] else 1
      if ((((__pyx_v_s1[(__pyx_v_i - 1)]) == (__pyx_v_s2[(__pyx_v_j - 1)])) != 0)) {
        __pyx_t_6 = 0;
      } else {
        __pyx_t_6 = 1;
      }
      __pyx_v_cost = __pyx_t_6;
+38:             column[i] = min(column[i] + 1, column[i-1] + 1, last_diag + cost)
      __pyx_t_7 = ((__pyx_v_column[(__pyx_v_i - 1)]) + 1);
      __pyx_t_6 = (__pyx_v_last_diag + __pyx_v_cost);
      __pyx_t_8 = ((__pyx_v_column[__pyx_v_i]) + 1);
      if (((__pyx_t_7 < __pyx_t_8) != 0)) {
        __pyx_t_9 = __pyx_t_7;
      } else {
        __pyx_t_9 = __pyx_t_8;
      }
      __pyx_t_8 = __pyx_t_9;
      if (((__pyx_t_6 < __pyx_t_8) != 0)) {
        __pyx_t_9 = __pyx_t_6;
      } else {
        __pyx_t_9 = __pyx_t_8;
      }
      (__pyx_v_column[__pyx_v_i]) = __pyx_t_9;
+39:             last_diag = current
      __pyx_v_last_diag = __pyx_v_current;
    }
  }
 40: 
+41:     current = column[n1]
  __pyx_v_current = (__pyx_v_column[__pyx_v_n1]);
+42:     free(column)
  free(__pyx_v_column);
 43: 
+44:     return current
  __pyx_r = __pyx_v_current;
  goto __pyx_L0;
 45: 
+46: def levenshtein_8(s1, s2):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_1levenshtein_8(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_1levenshtein_8 = {"levenshtein_8", (PyCFunction)__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_1levenshtein_8, METH_VARARGS|METH_KEYWORDS, 0};
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_1levenshtein_8(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
  PyObject *__pyx_v_s1 = 0;
  PyObject *__pyx_v_s2 = 0;
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8 (wrapper)", 0);
  {
    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_s1,&__pyx_n_s_s2,0};
    PyObject* values[2] = {0,0};
    if (unlikely(__pyx_kwds)) {
      Py_ssize_t kw_args;
      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
      switch (pos_args) {
        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
        case  0: break;
        default: goto __pyx_L5_argtuple_error;
      }
      kw_args = PyDict_Size(__pyx_kwds);
      switch (pos_args) {
        case  0:
        if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s1)) != 0)) kw_args--;
        else goto __pyx_L5_argtuple_error;
        case  1:
        if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_s2)) != 0)) kw_args--;
        else {
          __Pyx_RaiseArgtupleInvalid("levenshtein_8", 1, 2, 2, 1); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
        }
      }
      if (unlikely(kw_args > 0)) {
        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "levenshtein_8") < 0)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
      }
    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {
      goto __pyx_L5_argtuple_error;
    } else {
      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
    }
    __pyx_v_s1 = values[0];
    __pyx_v_s2 = values[1];
  }
  goto __pyx_L4_argument_unpacking_done;
  __pyx_L5_argtuple_error:;
  __Pyx_RaiseArgtupleInvalid("levenshtein_8", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L3_error;}
  __pyx_L3_error:;
  __Pyx_AddTraceback("_cython_magic_150fe167507bea5aa06eddab1200f03f.levenshtein_8", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __Pyx_RefNannyFinishContext();
  return NULL;
  __pyx_L4_argument_unpacking_done:;
  __pyx_r = __pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_levenshtein_8(__pyx_self, __pyx_v_s1, __pyx_v_s2);
  int __pyx_lineno = 0;
  const char *__pyx_filename = NULL;
  int __pyx_clineno = 0;

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_levenshtein_8(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_s1, PyObject *__pyx_v_s2) {
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8", 0);
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_AddTraceback("_cython_magic_150fe167507bea5aa06eddab1200f03f.levenshtein_8", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  __pyx_L0:;
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__7 = PyTuple_Pack(2, __pyx_n_s_s1, __pyx_n_s_s2); if (unlikely(!__pyx_tuple__7)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__7);
  __Pyx_GIVEREF(__pyx_tuple__7);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_1levenshtein_8, NULL, __pyx_n_s_cython_magic_150fe167507bea5aa0); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_8, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
  __pyx_codeobj__8 = (PyObject*)__Pyx_PyCode_New(2, 0, 2, 0, 0, __pyx_empty_bytes, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_tuple__7, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_kp_s_home_rolando_cache_ipython_cyth, __pyx_n_s_levenshtein_8, 46, __pyx_empty_bytes); if (unlikely(!__pyx_codeobj__8)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 46; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
+47:     return cy_levenshtein(s1, len(s1), s2, len(s2))
  __Pyx_XDECREF(__pyx_r);
  __pyx_t_1 = __Pyx_PyUnicode_AsUnicode(__pyx_v_s1); if (unlikely((!__pyx_t_1) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_2 = PyObject_Length(__pyx_v_s1); if (unlikely(__pyx_t_2 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_3 = __Pyx_PyUnicode_AsUnicode(__pyx_v_s2); if (unlikely((!__pyx_t_3) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_4 = PyObject_Length(__pyx_v_s2); if (unlikely(__pyx_t_4 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_5 = __Pyx_PyInt_From_int(__pyx_f_46_cython_magic_150fe167507bea5aa06eddab1200f03f_cy_levenshtein(__pyx_t_1, __pyx_t_2, __pyx_t_3, __pyx_t_4)); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 47; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_5);
  __pyx_r = __pyx_t_5;
  __pyx_t_5 = 0;
  goto __pyx_L0;
 48: 
 49: 
+50: def levenshtein_8_pdist(values):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_3levenshtein_8_pdist(PyObject *__pyx_self, PyObject *__pyx_v_values); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_3levenshtein_8_pdist = {"levenshtein_8_pdist", (PyCFunction)__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_3levenshtein_8_pdist, METH_O, 0};
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_3levenshtein_8_pdist(PyObject *__pyx_self, PyObject *__pyx_v_values) {
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8_pdist (wrapper)", 0);
  __pyx_r = __pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_2levenshtein_8_pdist(__pyx_self, ((PyObject *)__pyx_v_values));

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_2levenshtein_8_pdist(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_values) {
  int __pyx_v_n;
  int __pyx_v_m;
  PyArrayObject *__pyx_v_result = 0;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  int __pyx_v_offset;
  __Pyx_LocalBuf_ND __pyx_pybuffernd_result;
  __Pyx_Buffer __pyx_pybuffer_result;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8_pdist", 0);
  __pyx_pybuffer_result.pybuffer.buf = NULL;
  __pyx_pybuffer_result.refcount = 0;
  __pyx_pybuffernd_result.data = NULL;
  __pyx_pybuffernd_result.rcbuffer = &__pyx_pybuffer_result;
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_4);
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_XDECREF(__pyx_t_6);
  { PyObject *__pyx_type, *__pyx_value, *__pyx_tb;
    __Pyx_ErrFetch(&__pyx_type, &__pyx_value, &__pyx_tb);
    __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_result.rcbuffer->pybuffer);
  __Pyx_ErrRestore(__pyx_type, __pyx_value, __pyx_tb);}
  __Pyx_AddTraceback("_cython_magic_150fe167507bea5aa06eddab1200f03f.levenshtein_8_pdist", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  goto __pyx_L2;
  __pyx_L0:;
  __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_result.rcbuffer->pybuffer);
  __pyx_L2:;
  __Pyx_XDECREF((PyObject *)__pyx_v_result);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__9 = PyTuple_Pack(7, __pyx_n_s_values, __pyx_n_s_n, __pyx_n_s_m, __pyx_n_s_result, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_offset); if (unlikely(!__pyx_tuple__9)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 50; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__9);
  __Pyx_GIVEREF(__pyx_tuple__9);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_3levenshtein_8_pdist, NULL, __pyx_n_s_cython_magic_150fe167507bea5aa0); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 50; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_8_pdist, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 50; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
  __pyx_codeobj__10 = (PyObject*)__Pyx_PyCode_New(1, 0, 7, 0, 0, __pyx_empty_bytes, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_tuple__9, __pyx_empty_tuple, __pyx_empty_tuple, __pyx_kp_s_home_rolando_cache_ipython_cyth, __pyx_n_s_levenshtein_8_pdist, 50, __pyx_empty_bytes); if (unlikely(!__pyx_codeobj__10)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 50; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
 51:     # condensed distance representation
+52:     cdef int n = len(values)
  __pyx_t_1 = PyObject_Length(__pyx_v_values); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 52; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_v_n = __pyx_t_1;
+53:     cdef int m = n * (n - 1) // 2
  __pyx_v_m = ((__pyx_v_n * (__pyx_v_n - 1)) / 2);
+54:     cdef np.ndarray[np.int_t, ndim=1] result = np.zeros(m, dtype=np.int)
  __pyx_t_2 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = __Pyx_PyObject_GetAttrStr(__pyx_t_2, __pyx_n_s_zeros); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_m); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_4 = PyTuple_New(1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_4);
  PyTuple_SET_ITEM(__pyx_t_4, 0, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_5 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_5);
  __pyx_t_6 = __Pyx_PyObject_GetAttrStr(__pyx_t_5, __pyx_n_s_int); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
  if (PyDict_SetItem(__pyx_t_2, __pyx_n_s_dtype, __pyx_t_6) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
  __pyx_t_6 = __Pyx_PyObject_Call(__pyx_t_3, __pyx_t_4, __pyx_t_2); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  if (!(likely(((__pyx_t_6) == Py_None) || likely(__Pyx_TypeTest(__pyx_t_6, __pyx_ptype_5numpy_ndarray))))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_7 = ((PyArrayObject *)__pyx_t_6);
  {
    __Pyx_BufFmt_StackElem __pyx_stack[1];
    if (unlikely(__Pyx_GetBufferAndValidate(&__pyx_pybuffernd_result.rcbuffer->pybuffer, (PyObject*)__pyx_t_7, &__Pyx_TypeInfo_nn___pyx_t_5numpy_int_t, PyBUF_FORMAT| PyBUF_STRIDES| PyBUF_WRITABLE, 1, 0, __pyx_stack) == -1)) {
      __pyx_v_result = ((PyArrayObject *)Py_None); __Pyx_INCREF(Py_None); __pyx_pybuffernd_result.rcbuffer->pybuffer.buf = NULL;
      {__pyx_filename = __pyx_f[0]; __pyx_lineno = 54; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    } else {__pyx_pybuffernd_result.diminfo[0].strides = __pyx_pybuffernd_result.rcbuffer->pybuffer.strides[0]; __pyx_pybuffernd_result.diminfo[0].shape = __pyx_pybuffernd_result.rcbuffer->pybuffer.shape[0];
    }
  }
  __pyx_t_7 = 0;
  __pyx_v_result = ((PyArrayObject *)__pyx_t_6);
  __pyx_t_6 = 0;
 55: 
 56:     cdef Py_ssize_t i, j
 57:     cdef int offset
 58: 
+59:     for i in range(n):
  __pyx_t_8 = __pyx_v_n;
  for (__pyx_t_1 = 0; __pyx_t_1 < __pyx_t_8; __pyx_t_1+=1) {
    __pyx_v_i = __pyx_t_1;
+60:         offset = i * n - (i + 1) * (i + 2) // 2
    __pyx_v_offset = ((__pyx_v_i * __pyx_v_n) - (((__pyx_v_i + 1) * (__pyx_v_i + 2)) / 2));
+61:         for j in range(i + 1, n):
    __pyx_t_9 = __pyx_v_n;
    for (__pyx_t_10 = (__pyx_v_i + 1); __pyx_t_10 < __pyx_t_9; __pyx_t_10+=1) {
      __pyx_v_j = __pyx_t_10;
+62:             result[offset + j] = cy_levenshtein(values[i], len(values[i]), values[j], len(values[j]))
      __pyx_t_6 = __Pyx_GetItemInt(__pyx_v_values, __pyx_v_i, Py_ssize_t, 1, PyInt_FromSsize_t, 0, 0, 0); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_6);
      __pyx_t_11 = __Pyx_PyUnicode_AsUnicode(__pyx_t_6); if (unlikely((!__pyx_t_11) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __pyx_t_2 = __Pyx_GetItemInt(__pyx_v_values, __pyx_v_i, Py_ssize_t, 1, PyInt_FromSsize_t, 0, 0, 0); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_12 = PyObject_Length(__pyx_t_2); if (unlikely(__pyx_t_12 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
      __pyx_t_2 = __Pyx_GetItemInt(__pyx_v_values, __pyx_v_j, Py_ssize_t, 1, PyInt_FromSsize_t, 0, 0, 0); if (unlikely(__pyx_t_2 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_2);
      __pyx_t_13 = __Pyx_PyUnicode_AsUnicode(__pyx_t_2); if (unlikely((!__pyx_t_13) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __pyx_t_4 = __Pyx_GetItemInt(__pyx_v_values, __pyx_v_j, Py_ssize_t, 1, PyInt_FromSsize_t, 0, 0, 0); if (unlikely(__pyx_t_4 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
      __Pyx_GOTREF(__pyx_t_4);
      __pyx_t_14 = PyObject_Length(__pyx_t_4); if (unlikely(__pyx_t_14 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 62; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
      __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
      __pyx_t_15 = (__pyx_v_offset + __pyx_v_j);
      *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_result.rcbuffer->pybuffer.buf, __pyx_t_15, __pyx_pybuffernd_result.diminfo[0].strides) = __pyx_f_46_cython_magic_150fe167507bea5aa06eddab1200f03f_cy_levenshtein(__pyx_t_11, __pyx_t_12, __pyx_t_13, __pyx_t_14);
      __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
      __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
    }
  }
 63: 
+64:     return result
  __Pyx_XDECREF(__pyx_r);
  __Pyx_INCREF(((PyObject *)__pyx_v_result));
  __pyx_r = ((PyObject *)__pyx_v_result);
  goto __pyx_L0;
 65: 
 66: 
+67: def levenshtein_8_pdist_parallel(values):
/* Python wrapper */
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_5levenshtein_8_pdist_parallel(PyObject *__pyx_self, PyObject *__pyx_v_values); /*proto*/
static PyMethodDef __pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_5levenshtein_8_pdist_parallel = {"levenshtein_8_pdist_parallel", (PyCFunction)__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_5levenshtein_8_pdist_parallel, METH_O, 0};
static PyObject *__pyx_pw_46_cython_magic_150fe167507bea5aa06eddab1200f03f_5levenshtein_8_pdist_parallel(PyObject *__pyx_self, PyObject *__pyx_v_values) {
  PyObject *__pyx_r = 0;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8_pdist_parallel (wrapper)", 0);
  __pyx_r = __pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_4levenshtein_8_pdist_parallel(__pyx_self, ((PyObject *)__pyx_v_values));

  /* function exit code */
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}

static PyObject *__pyx_pf_46_cython_magic_150fe167507bea5aa06eddab1200f03f_4levenshtein_8_pdist_parallel(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_values) {
  int __pyx_v_n;
  int __pyx_v_m;
  PyArrayObject *__pyx_v_result = 0;
  Py_ssize_t __pyx_v_i;
  Py_ssize_t __pyx_v_j;
  int __pyx_v_offset;
  int *__pyx_v_lengths;
  Py_UNICODE **__pyx_v_strings;
  __Pyx_LocalBuf_ND __pyx_pybuffernd_result;
  __Pyx_Buffer __pyx_pybuffer_result;
  PyObject *__pyx_r = NULL;
  __Pyx_RefNannyDeclarations
  __Pyx_RefNannySetupContext("levenshtein_8_pdist_parallel", 0);
  __pyx_pybuffer_result.pybuffer.buf = NULL;
  __pyx_pybuffer_result.refcount = 0;
  __pyx_pybuffernd_result.data = NULL;
  __pyx_pybuffernd_result.rcbuffer = &__pyx_pybuffer_result;
/* … */
  /* function exit code */
  __pyx_L1_error:;
  __Pyx_XDECREF(__pyx_t_2);
  __Pyx_XDECREF(__pyx_t_3);
  __Pyx_XDECREF(__pyx_t_4);
  __Pyx_XDECREF(__pyx_t_5);
  __Pyx_XDECREF(__pyx_t_6);
  { PyObject *__pyx_type, *__pyx_value, *__pyx_tb;
    __Pyx_ErrFetch(&__pyx_type, &__pyx_value, &__pyx_tb);
    __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_result.rcbuffer->pybuffer);
  __Pyx_ErrRestore(__pyx_type, __pyx_value, __pyx_tb);}
  __Pyx_AddTraceback("_cython_magic_150fe167507bea5aa06eddab1200f03f.levenshtein_8_pdist_parallel", __pyx_clineno, __pyx_lineno, __pyx_filename);
  __pyx_r = NULL;
  goto __pyx_L2;
  __pyx_L0:;
  __Pyx_SafeReleaseBuffer(&__pyx_pybuffernd_result.rcbuffer->pybuffer);
  __pyx_L2:;
  __Pyx_XDECREF((PyObject *)__pyx_v_result);
  __Pyx_XGIVEREF(__pyx_r);
  __Pyx_RefNannyFinishContext();
  return __pyx_r;
}
/* … */
  __pyx_tuple__11 = PyTuple_Pack(9, __pyx_n_s_values, __pyx_n_s_n, __pyx_n_s_m, __pyx_n_s_result, __pyx_n_s_i, __pyx_n_s_j, __pyx_n_s_offset, __pyx_n_s_lengths, __pyx_n_s_strings); if (unlikely(!__pyx_tuple__11)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 67; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_tuple__11);
  __Pyx_GIVEREF(__pyx_tuple__11);
/* … */
  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_150fe167507bea5aa06eddab1200f03f_5levenshtein_8_pdist_parallel, NULL, __pyx_n_s_cython_magic_150fe167507bea5aa0); if (unlikely(!__pyx_t_1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 67; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_1);
  if (PyDict_SetItem(__pyx_d, __pyx_n_s_levenshtein_8_pdist_parallel, __pyx_t_1) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 67; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
 68:     # condensed distance representation
+69:     cdef int n = len(values)
  __pyx_t_1 = PyObject_Length(__pyx_v_values); if (unlikely(__pyx_t_1 == -1)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 69; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_v_n = __pyx_t_1;
+70:     cdef int m = n * (n - 1) // 2
  __pyx_v_m = ((__pyx_v_n * (__pyx_v_n - 1)) / 2);
+71:     cdef np.ndarray[np.int_t, ndim=1] result = np.zeros(m, dtype=np.int)
  __pyx_t_2 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_3 = __Pyx_PyObject_GetAttrStr(__pyx_t_2, __pyx_n_s_zeros); if (unlikely(!__pyx_t_3)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_3);
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_m); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_4 = PyTuple_New(1); if (unlikely(!__pyx_t_4)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_4);
  PyTuple_SET_ITEM(__pyx_t_4, 0, __pyx_t_2);
  __Pyx_GIVEREF(__pyx_t_2);
  __pyx_t_2 = 0;
  __pyx_t_2 = PyDict_New(); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_2);
  __pyx_t_5 = __Pyx_GetModuleGlobalName(__pyx_n_s_np); if (unlikely(!__pyx_t_5)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_5);
  __pyx_t_6 = __Pyx_PyObject_GetAttrStr(__pyx_t_5, __pyx_n_s_int); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
  if (PyDict_SetItem(__pyx_t_2, __pyx_n_s_dtype, __pyx_t_6) < 0) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
  __pyx_t_6 = __Pyx_PyObject_Call(__pyx_t_3, __pyx_t_4, __pyx_t_2); if (unlikely(!__pyx_t_6)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __Pyx_GOTREF(__pyx_t_6);
  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
  __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
  if (!(likely(((__pyx_t_6) == Py_None) || likely(__Pyx_TypeTest(__pyx_t_6, __pyx_ptype_5numpy_ndarray))))) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
  __pyx_t_7 = ((PyArrayObject *)__pyx_t_6);
  {
    __Pyx_BufFmt_StackElem __pyx_stack[1];
    if (unlikely(__Pyx_GetBufferAndValidate(&__pyx_pybuffernd_result.rcbuffer->pybuffer, (PyObject*)__pyx_t_7, &__Pyx_TypeInfo_nn___pyx_t_5numpy_int_t, PyBUF_FORMAT| PyBUF_STRIDES| PyBUF_WRITABLE, 1, 0, __pyx_stack) == -1)) {
      __pyx_v_result = ((PyArrayObject *)Py_None); __Pyx_INCREF(Py_None); __pyx_pybuffernd_result.rcbuffer->pybuffer.buf = NULL;
      {__pyx_filename = __pyx_f[0]; __pyx_lineno = 71; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    } else {__pyx_pybuffernd_result.diminfo[0].strides = __pyx_pybuffernd_result.rcbuffer->pybuffer.strides[0]; __pyx_pybuffernd_result.diminfo[0].shape = __pyx_pybuffernd_result.rcbuffer->pybuffer.shape[0];
    }
  }
  __pyx_t_7 = 0;
  __pyx_v_result = ((PyArrayObject *)__pyx_t_6);
  __pyx_t_6 = 0;
 72: 
 73:     cdef Py_ssize_t i, j
 74:     cdef int offset
 75: 
+76:     cdef int* lengths = <int*> malloc(n * sizeof(int))
  __pyx_v_lengths = ((int *)malloc((__pyx_v_n * (sizeof(int)))));
+77:     cdef Py_UNICODE** strings = <Py_UNICODE**> malloc(n * sizeof(Py_UNICODE*))
  __pyx_v_strings = ((Py_UNICODE **)malloc((__pyx_v_n * (sizeof(Py_UNICODE *)))));
 78: 
+79:     for i in range(n):
  __pyx_t_8 = __pyx_v_n;
  for (__pyx_t_1 = 0; __pyx_t_1 < __pyx_t_8; __pyx_t_1+=1) {
    __pyx_v_i = __pyx_t_1;
+80:         strings[i] = values[i]
    __pyx_t_6 = __Pyx_GetItemInt(__pyx_v_values, __pyx_v_i, Py_ssize_t, 1, PyInt_FromSsize_t, 0, 0, 0); if (unlikely(__pyx_t_6 == NULL)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 80; __pyx_clineno = __LINE__; goto __pyx_L1_error;};
    __Pyx_GOTREF(__pyx_t_6);
    __pyx_t_9 = __Pyx_PyUnicode_AsUnicode(__pyx_t_6); if (unlikely((!__pyx_t_9) && PyErr_Occurred())) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 80; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
    (__pyx_v_strings[__pyx_v_i]) = __pyx_t_9;
    __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
+81:         lengths[i] = len(strings[i])
    __pyx_t_10 = __Pyx_Py_UNICODE_strlen((__pyx_v_strings[__pyx_v_i])); 
    (__pyx_v_lengths[__pyx_v_i]) = __pyx_t_10;
  }
 82: 
+83:     with nogil:
  {
      #ifdef WITH_THREAD
      PyThreadState *_save;
      Py_UNBLOCK_THREADS
      #endif
      /*try:*/ {
/* … */
      /*finally:*/ {
        /*normal exit:*/{
          #ifdef WITH_THREAD
          Py_BLOCK_THREADS
          #endif
          goto __pyx_L7;
        }
        __pyx_L7:;
      }
  }
+84:         for i in prange(n, schedule='guided'):
        __pyx_t_8 = __pyx_v_n;
        if (1 == 0) abort();
        {
            #if ((defined(__APPLE__) || defined(__OSX__)) && (defined(__GNUC__) && (__GNUC__ > 2 || (__GNUC__ == 2 && (__GNUC_MINOR__ > 95)))))
                #undef likely
                #undef unlikely
                #define likely(x)   (x)
                #define unlikely(x) (x)
            #endif
            __pyx_t_11 = (__pyx_t_8 - 0) / 1;
            if (__pyx_t_11 > 0)
            {
                #ifdef _OPENMP
                #pragma omp parallel
                #endif /* _OPENMP */
                {
                    #ifdef _OPENMP
                    #pragma omp for firstprivate(__pyx_v_i) lastprivate(__pyx_v_i) lastprivate(__pyx_v_offset) lastprivate(__pyx_v_j) schedule(guided)
                    #endif /* _OPENMP */
                    for (__pyx_t_1 = 0; __pyx_t_1 < __pyx_t_11; __pyx_t_1++){
                        {
                            __pyx_v_i = 0 + 1 * __pyx_t_1;
                            /* Initialize private variables to invalid values */
                            __pyx_v_offset = ((int)0xbad0bad0);
                            __pyx_v_j = ((Py_ssize_t)0xbad0bad0);
+85:             offset = i * n - (i + 1) * (i + 2) // 2
                            __pyx_v_offset = ((__pyx_v_i * __pyx_v_n) - (((__pyx_v_i + 1) * (__pyx_v_i + 2)) / 2));
+86:             for j in prange(i + 1, n, schedule='guided'):
                            __pyx_t_12 = (__pyx_v_i + 1);
                            __pyx_t_13 = __pyx_v_n;
                            if (1 == 0) abort();
                            {
                                __pyx_t_15 = (__pyx_t_13 - __pyx_t_12) / 1;
                                if (__pyx_t_15 > 0)
                                {
                                    #if 0
                                    #pragma omp parallel
                                    #endif /* _OPENMP */
                                    {
                                        #if 0
                                        #pragma omp for firstprivate(__pyx_v_j) lastprivate(__pyx_v_j) schedule(guided)
                                        #endif /* _OPENMP */
                                        for (__pyx_t_14 = 0; __pyx_t_14 < __pyx_t_15; __pyx_t_14++){
                                            {
                                                __pyx_v_j = __pyx_t_12 + 1 * __pyx_t_14;
+87:                 result[offset + j] = cy_levenshtein(strings[i], lengths[i], strings[j], lengths[j])
                                                __pyx_t_16 = (__pyx_v_offset + __pyx_v_j);
                                                *__Pyx_BufPtrStrided1d(__pyx_t_5numpy_int_t *, __pyx_pybuffernd_result.rcbuffer->pybuffer.buf, __pyx_t_16, __pyx_pybuffernd_result.diminfo[0].strides) = __pyx_f_46_cython_magic_150fe167507bea5aa06eddab1200f03f_cy_levenshtein((__pyx_v_strings[__pyx_v_i]), (__pyx_v_lengths[__pyx_v_i]), (__pyx_v_strings[__pyx_v_j]), (__pyx_v_lengths[__pyx_v_j]));
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        #if ((defined(__APPLE__) || defined(__OSX__)) && (defined(__GNUC__) && (__GNUC__ > 2 || (__GNUC__ == 2 && (__GNUC_MINOR__ > 95)))))
            #undef likely
            #undef unlikely
            #define likely(x)   __builtin_expect(!!(x), 1)
            #define unlikely(x) __builtin_expect(!!(x), 0)
        #endif
      }
 88: 
+89:     free(lengths)
  free(__pyx_v_lengths);
+90:     free(strings)
  free(__pyx_v_strings);
 91: 
+92:     return result
  __Pyx_XDECREF(__pyx_r);
  __Pyx_INCREF(((PyObject *)__pyx_v_result));
  __pyx_r = ((PyObject *)__pyx_v_result);
  goto __pyx_L0;

In [ ]:

    




    

In [13]:

    

%timeit -r5 levenshtein_1_py(s1, s2)


    

    




1 loops, best of 5: 2.03 s per loop

In [14]:

    

%timeit -n1 -r5 levenshtein_2_py(s1, s2)


    

    




1 loops, best of 5: 1.56 s per loop

In [15]:

    

%timeit -n1 -r5 levenshtein_1(s1, s2)


    

    




1 loops, best of 5: 1.34 s per loop

In [16]:

    

%timeit -r5 levenshtein_2(s1, s2)


    

    




1 loops, best of 5: 735 ms per loop

In [17]:

    

%timeit -r5 levenshtein_3(s1, s2)


    

    




1 loops, best of 5: 232 ms per loop

In [18]:

    

%timeit -r5 levenshtein_4(s1, s2)


    

    




100 loops, best of 5: 9.13 ms per loop

In [19]:

    

%timeit -r5 levenshtein_5(s1, s2)


    

    




100 loops, best of 5: 9.03 ms per loop

In [20]:

    

%timeit -r5 levenshtein_6(s1, s2)


    

    




100 loops, best of 5: 6.38 ms per loop

In [21]:

    

%timeit -r5 levenshtein_7(s1, s2)


    

    




100 loops, best of 5: 6.35 ms per loop

In [22]:

    

%timeit -r5 levenshtein_8(unicode(s1), unicode(s2))


    

    




100 loops, best of 5: 6.44 ms per loop

In [23]:

    

%time
test_data = [
    ("kitten", "sitting", 3),
    ("kitten", "kitten", 0),
    ("", "", 0),
    ("meilenstein", "levenshtein", 4),
    ("levenshtein", "frankenstein", 6),
    ("confide", "deceit", 6),
    ("CUNsperrICY", "conspiracy", 8),
]
test_functions = [
    levenshtein_1_py,
    levenshtein_2_py,
    levenshtein_1,
    levenshtein_2,
    levenshtein_3,
    levenshtein_4,
    levenshtein_5,
    levenshtein_6,
    levenshtein_7,
]
def test():
    for func in test_functions:
        for s1, s2, dist in test_data:
            assert func(s1, s2) == dist, "%s(%s, %s) != %s" % (func.__name__, s1, s2, dist)
            
test()


    

    




CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 27.2 µs

In [24]:

    

assert levenshtein_8(u"a", u"b\xf1") == 2
def test():
    for s1, s2, dist in test_data:
        assert levenshtein_8(unicode(s1), unicode(s2)) == dist, (s1, s2, dist)
test()


    

In [25]:

    

words = !shuf -n1000 /usr/share/dict/words
words = [s.decode('utf-8') for s in words]

assert np.allclose(levenshtein_8_pdist(words), levenshtein_8_pdist_parallel(words))


    

In [26]:

    

from scipy.spatial.distance import squareform

squareform(levenshtein_8_pdist_parallel(words))


    

    
Out[26]:





array([[  0.,   8.,   8., ...,   8.,   7.,   5.],
       [  8.,   0.,  11., ...,  10.,   8.,   9.],
       [  8.,  11.,   0., ...,   8.,  10.,   9.],
       ..., 
       [  8.,  10.,   8., ...,   0.,  10.,   9.],
       [  7.,   8.,  10., ...,  10.,   0.,   9.],
       [  5.,   9.,   9., ...,   9.,   9.,   0.]])

In [27]:

    

%timeit -r5 levenshtein_8_pdist(words)


    

    




1 loops, best of 5: 340 ms per loop

In [28]:

    

%timeit -r5 levenshtein_8_pdist_parallel(words)


    

    




1 loops, best of 5: 270 ms per loop