clev.c

#include <Python.h>


int min(int a, int b, int c) {
    int m = a;
    if (b < a) { m = b; };
    if (c < m) { m = c; };
    return m;
}

/* void chars_from_unicode(char *s, Py_UNICODE **chars, Py_ssize_t *len) { */
/*     PyUnicodeObject *uo_s = PyUnicode_FromString(s); */
/*     *len = PyUnicode_GetSize(uo_s); */
/*     *chars = PyUnicode_AS_UNICODE(uo_s); */
/* } */


/* int levenshtein(const char *s1, const char *s2) { */
/*  */
/*     PyObject *uo_s1 = PyUnicode_FromString(s1); */
/*     PyObject *uo_s2 = PyUnicode_FromString(s2); */
/*  */
/*     Py_ssize_t len_s1 = PyUnicode_GetSize(uo_s1); */
/*     Py_ssize_t len_s2 = PyUnicode_GetSize(uo_s2); */
/*  */
/*     Py_UNICODE *chars_s1 = PyUnicode_AS_UNICODE(uo_s1); */
/*     #<{(| Py_UNICODE *chars_s2 = PyUnicode_AS_UNICODE(uo_s2); |)}># */
/*  */
/*  */
/*     #<{(| Py_UNICODE *chars_s1; |)}># */
/*     #<{(| Py_ssize_t len_s1; |)}># */
/*     #<{(| chars_from_unicode(s1, *chars_s1, *len_s1); |)}># */
/*     #<{(|  |)}># */
/*     #<{(| Py_UNICODE *chars_s2; |)}># */
/*     #<{(| Py_ssize_t len_s2; |)}># */
/*     #<{(| chars_from_unicode(s2, *chars_s2, *len_s2); |)}># */
/*  */
/*  */
/*     int v0[len_s2], v1[len_s2]; */
/*  */
/*     char c1, c2; */
/*  */
/*     int i, j, x; */
/*  */
/*     for (x = 0; x <= len_s2; x++) { */
/*         v1[x] = x; */
/*     }; */
/*  */
/*     for (i = 0; i < len_s1; i++) { */
/*         c1 = chars_s1[i]; */
/*  */
/*         for (x = 0; x <= len_s2; x++) { */
/*             v0[x] = v1[x]; */
/*         }; */
/*  */
/*         v1[0]++; */
/*  */
/*         for (j = 1; j <= len_s2; j++) { */
/*             c2 = s2[j - 1]; */
/*             if (c1 == c2) { */
/*                 v1[j] = v0[j - 1]; */
/*             } */
/*             else { */
/*                 v1[j] = 1 + min(v0[j - 1], v0[j], v1[j - 1]); */
/*             } */
/*         } */
/*     } */
/*  */
/*     printf("s1: %d; s2: %d\n", len_s1, len_s2); */
/*  */
/*     return v1[len_s2]; */
/* } */


/* int main(int argc, char *argv[]) { */
/*   printf("%d\n", levenshtein(argv[1], argv[2])); */
/*   return 0; */
/* } */


static PyObject *
clev_levenshtein(PyObject *self, PyObject *args)
{
    PyObject *uo_s1;
    PyObject *uo_s2;

    if(!PyArg_ParseTuple(args, "UU", &uo_s1, &uo_s2)) {
        return NULL;
    };

    Py_ssize_t len_s1 = PyUnicode_GetSize(uo_s1);
    Py_ssize_t len_s2 = PyUnicode_GetSize(uo_s2);

    Py_UNICODE *chars_s1 = PyUnicode_AS_UNICODE(uo_s1);
    Py_UNICODE *chars_s2 = PyUnicode_AS_UNICODE(uo_s2);


    /* Py_UNICODE *chars_s1; */
    /* Py_ssize_t len_s1; */
    /* chars_from_unicode(s1, *chars_s1, *len_s1); */
    /*  */
    /* Py_UNICODE *chars_s2; */
    /* Py_ssize_t len_s2; */
    /* chars_from_unicode(s2, *chars_s2, *len_s2); */


    int v0[len_s2], v1[len_s2];

    char c1, c2;

    int i, j, x;

    for (x = 0; x <= len_s2; x++) {
        v1[x] = x;
    };

    for (i = 0; i < len_s1; i++) {
        c1 = chars_s1[i];

        for (x = 0; x <= len_s2; x++) {
            v0[x] = v1[x];
        };

        v1[0]++;

        for (j = 1; j <= len_s2; j++) {
            c2 = chars_s2[j - 1];
            if (c1 == c2) {
                v1[j] = v0[j - 1];
            }
            else {
                v1[j] = 1 + min(v0[j - 1], v0[j], v1[j - 1]);
            }
        }
    }

    return Py_BuildValue("i", v1[len_s2]);

};


static PyMethodDef LevMethods[] = {
    {
        "levenshtein", clev_levenshtein, METH_VARARGS,
        "Calculate Levenshtein distance between given strings"
    },
    { NULL, NULL, 0, NULL }
};

PyMODINIT_FUNC
initclev(void) {
    (void) Py_InitModule("clev", LevMethods);
}