Levenshtein-Distanz in C als Python-Erweiterung

[modelnine]

Weil's so viel Spaß macht mit dem Python-C-API zu programmieren, hier mal 'ne kleine Implementierung des Levenshtein-Algorithmus in C, zur Benutzung von Python aus:

Code: Alles auswählen

/* Levenshtein Distance for Python, coded in C for speed. */

#include <Python.h>

#define MAX(a,b) ((a)<(b)?(b):(a))
#define MIN3(a,b,c) ((a)>(b)?((c)>(b)?(b):(c)):((a)>(c)?(c):(a)))

static PyObject *levenshtein(PyObject *self, PyObject *args)
{
  char *str1, *str2;
  int slen1, slen2, i, j, *array = NULL;
  PyObject *rv;

  if( !PyArg_ParseTuple(args,"s#s#",&str1,&slen1,&str2,&slen2) )
    return NULL;

  if( !slen1 )
    return PyInt_FromLong(slen2);
  if( !slen2 )
    return PyInt_FromLong(slen1);

  if( !( array = (int*)PyMem_Malloc(sizeof(int)*(slen1+1)*(slen2+1)) ) ) {
    PyErr_SetString(PyExc_MemoryError,"Cannot allocate array of distances");
    return NULL;
  }

  for( i = 0; i <= slen1; i++ )
    array[i*(slen2+1)] = i;
  for( j = 1; j <= slen2; j++ )
    array[j] = j;

  for( i = 0; i < slen1; i++ )
    for( j = 0; j < slen2; j++ )
      array[(i+1)*(slen2+1)+j+1] = MIN3(array[i*(slen2+1)+j+1]+1,
                                        array[(i+1)*(slen2+1)+j]+1,
                                        array[i*(slen2+1)+j] +
                                        (str1[i]==str2[j]?0:1));

  rv = PyInt_FromLong(array[(slen1+1)*(slen2+1)-1]);
  PyMem_Free(array);
  return rv;
}

static PyMethodDef LevenshteinMethods[] = {
  {"levenshtein",levenshtein,METH_VARARGS,
   "Calculate the levenshtein distance between two strings."},
  {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC initlevenshtein()
{
  Py_InitModule("levenshtein",LevenshteinMethods);
}

Und dazu noch den Build-File:

Code: Alles auswählen

# -*- coding: iso-8859-15 -*-

from distutils.core import setup, Extension

levc = Extension('levenshtein',sources=['levenshtein.c'])

setup(name='levenshtein',version='0.1',
      description='Calculates the levenshtein distance between two strings',
      ext_modules=[levc])

Sehr schön einfach und kompakt. Deswegen liebe ich Python; wenn's nicht direkt in Python geht (weil zu langsam) schreib ich ganze 20 Zeilen C, und hab die geschwindigkeitsrelevanten Teile ausgelagert. Und das ganze ohne irgendwie SWIG o.Ä. anfassen zu müssen.

Ahso, wem's wirklich um Geschwindigkeit geht, der wird um:

Code: Alles auswählen

CFLAGS="-O3" python setup.py install

nicht drum rum kommen, das macht bei mir ungefähr noch mal Faktor 3 aus.

Use at your own discretion...

[mawe]

Nett. Gibt's zwar schon als fix fertiges Modul, aber nett

[murph]

Ich kann das nicht installieren, versuche das seit 4h.
meine abänderung:

Code: Alles auswählen

#!/usr/bin/env python

from setuptools import setup, Extension
 
levc = extension('levenshtein',sources=['levenshtein.c'])

setup(name='levenshtein',version='0.1',
      description='Calculates the levenshtein distance between two strings',
      ext_modules=[levc])

murph@murphs:~/PYTHON$ CFLAGS="-03" python setup.py install
Traceback (most recent call last):
File "setup.py", line 5, in ?
levc = extension('levenshtein',sources=['levenshtein.c'])
NameError: name 'extension' is not defined

meine ander version:

Code: Alles auswählen

#!/usr/bin/env python
import setuptools
 
levc = setuptools.extension('levenshtein',sources=['levenshtein.c'])

setuptools.setup(name='levenshtein',version='0.1',
      description='Calculates the levenshtein distance between two strings',
      ext_modules=[levc])

Traceback (most recent call last):
File "./stetup-levenshtein.py", line 5, in ?
levc = setuptools.extension('levenshtein',sources=['levenshtein.c'])
TypeError: 'module' object is not callable

Ich bin am verzweifeln!

murph@murphs:~$ ./tester.py
['Command', 'Distribution', 'Extension', 'Feature', 'Require', '__all__', '__builtins__', '__doc__', '__file__', '__name__', '__path__', '__version__', 'command', 'convert_path', 'depends', 'dist', 'distutils', 'extension', 'find_packages', 'os', 'setup', 'setuptools']

tester.py:

Code: Alles auswählen

#!/usr/bin/env python
import setuptools
print dir(setuptools)

[Rebecca]

Extension (am Anfang gross...)

[murph]

Oh, sry, die Methode habe ich vergessen, auf die Liste der nicht klappenden Versionen zu schreiben

[Leonidas]

Warum nutzt du denn nicht einfach die Distutils? Oder schaust mal ob es nicht ein Update der Setuptools gibt?

[Leonidas]

Also bei mir gehts, sowohl mit Distutils als auch mit Setuptools.

Egg für Python 2.4