Similitud de cadenas con Python + Sqlite (distancia de Levenshtein / edición)

¿Existe una medida de similitud de cadena disponible en Python + Sqlite, por ejemplo, con el módulo sqlite3 ?

Ejemplo de caso de uso:

 import sqlite3 conn = sqlite3.connect(':memory:') c = conn.cursor() c.execute('CREATE TABLE mytable (id integer, description text)') c.execute('INSERT INTO mytable VALUES (1, "hello world, guys")') c.execute('INSERT INTO mytable VALUES (2, "hello there everybody")') 

Esta consulta debe coincidir con la fila con ID 1, pero no con la ID 2:

 c.execute('SELECT * FROM mytable WHERE dist(description, "He lo wrold gyus") < 6') 

¿Cómo hacer esto en Sqlite + Python?

Notas sobre lo que he encontrado hasta ahora:

  • La distancia de Levenshtein , es decir, el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra, puede ser útil, pero no estoy seguro de que exista una implementación oficial en Sqlite (He visto algunas implementaciones personalizadas, como esta )

  • El Damerau-Levenshtein es el mismo, excepto que también permite la transposición entre 2 caracteres adyacentes; también se le llama la distancia de edición

  • Sé que es posible definir una función por mi cuenta, pero la implementación de tal distancia no será trivial (hacer comparaciones de procesamiento de lenguaje natural de manera súper eficiente para bases de datos es realmente no trivial), por eso quería ver si Python / Sqlite ya cuenta con características una herramienta

  • Sqlite tiene características FTS (Full Text Seach): FTS3 , FTS4 , FTS5

     CREATE VIRTUAL TABLE enrondata1 USING fts3(content TEXT); /* FTS3 table */ CREATE TABLE enrondata2(content TEXT); /* Ordinary table */ SELECT count(*) FROM enrondata1 WHERE content MATCH 'linux'; /* 0.03 seconds */ SELECT count(*) FROM enrondata2 WHERE content LIKE '%linux%'; /* 22.5 seconds */ 

    pero no encuentro la comparación de cadenas con esa “distancia de similitud”, las características FTS MATCH o NEAR no parecen tener una medida de similitud con los cambios de letras, etc.

  • Además, esta respuesta muestra que:

    El motor FTS de SQLite se basa en tokens, palabras clave que el motor de búsqueda intenta hacer coincidir.
    Hay una variedad de tokenizadores disponibles, pero son relativamente simples. El tokenizer “simple” simplemente divide cada palabra y la coloca en minúscula: por ejemplo, en la cadena “El zorro marrón rápido salta sobre el perro perezoso”, la palabra “salta” coincidirá, pero no “saltará”. El tokenizer “porter” es un poco más avanzado, eliminando las conjugaciones de las palabras, de modo que “saltos” y “saltos” coincidan, pero un error tipográfico como “jmups” no coincide.

    El último (el hecho de que “jmups” no se puede encontrar como similar a “saltos”) hace que sea poco práctico para mi caso de uso, lamentablemente.

Aquí hay un ejemplo de test.py listo para usar:

 import sqlite3 db = sqlite3.connect(':memory:') db.enable_load_extension(True) db.load_extension('./spellfix') # for Linux #db.load_extension('./spellfix.dll') # <-- UNCOMMENT HERE FOR WINDOWS db.enable_load_extension(False) c = db.cursor() c.execute('CREATE TABLE mytable (id integer, description text)') c.execute('INSERT INTO mytable VALUES (1, "hello world, guys")') c.execute('INSERT INTO mytable VALUES (2, "hello there everybody")') c.execute('SELECT * FROM mytable WHERE editdist3(description, "hel o wrold guy") < 600') print c.fetchall() # Output: [(1, u'hello world, guys')] 

Nota importante: la distancia editdist3 se normaliza para que

el valor de 100 se utiliza para la inserción y eliminación y 150 se utiliza para la sustitución


Esto es lo que debe hacer primero en Windows:

  1. Descargue https://sqlite.org/2016/sqlite-src-3110100.zip , https://sqlite.org/2016/sqlite-amalgamation-3110100.zip y descomprímalos

  2. Reemplace C:\Python27\DLLs\sqlite3.dll por el nuevo sqlite3.dll desde aquí . Si se salta esto, obtendrías un sqlite3.OperationalError: The specified procedure could not be found más tarde

  3. Correr:

     call "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\vcvarsall.bat" 

    o

     call "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\vcvarsall.bat" x64 cl /I sqlite-amalgamation-3110100/ sqlite-src-3110100/ext/misc/spellfix.c /link /DLL /OUT:spellfix.dll python test.py 

    (Con MinGW, sería: gcc -g -shared spellfix.c -I ~/sqlite-amalgation-3230100/ -o spellfix.dll )

Aquí está cómo hacerlo en Linux Debian:

(basado en esta respuesta )

 apt-get -y install unzip build-essential libsqlite3-dev wget https://sqlite.org/2016/sqlite-src-3110100.zip unzip sqlite-src-3110100.zip gcc -shared -fPIC -Wall -Isqlite-src-3110100 sqlite-src-3110100/ext/misc/spellfix.c -o spellfix.so python test.py 

Aquí es cómo hacerlo en Linux Debian con una versión anterior de Python:

Si el Python de tu distribución es un poco antiguo, requerirá otro método. Como sqlite3 módulo sqlite3 está incorporado en Python, no parece sencillo actualizarlo ( pip install --upgrade pysqlite solo actualizaría el módulo pysqlite, no la biblioteca SQLite subyacente). Por lo tanto, este método funciona, por ejemplo, si import sqlite3; print sqlite3.sqlite_version import sqlite3; print sqlite3.sqlite_version es 3.8.2:

 wget https://www.sqlite.org/src/tarball/27392118/SQLite-27392118.tar.gz tar xvfz SQLite-27392118.tar.gz cd SQLite-27392118 ; sh configure ; make sqlite3.c ; cd .. gcc -g -fPIC -shared SQLite-27392118/ext/misc/spellfix.c -I SQLite-27392118/src/ -o spellfix.so python test.py # [(1, u'hello world, guys')]