Levenshtein-Distanz in C als Python-Erweiterung

Code-Stücke können hier veröffentlicht werden.
Antworten
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Sonntag 19. März 2006, 01:26

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... ;-)
--- Heiko.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Sonntag 19. März 2006, 07:19

Nett. Gibt's zwar schon als fix fertiges Modul, aber nett :)
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Mittwoch 26. April 2006, 16:26

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)
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Mittwoch 26. April 2006, 16:35

Extension (am Anfang gross...)
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Mittwoch 26. April 2006, 19:44

Oh, sry, die Methode habe ich vergessen, auf die Liste der nicht klappenden Versionen zu schreiben
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 26. April 2006, 21:47

Warum nutzt du denn nicht einfach die Distutils? Oder schaust mal ob es nicht ein Update der Setuptools gibt?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 26. April 2006, 21:53

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

Egg für Python 2.4
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten