String-Ähnlichkeit mit Python+SQLite(Levenshtein-Abstand/Bearbeitungsabstand)



string-comparison similarity (1)

Hier ist ein gebrauchsfertiges Beispiel test.py :

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')]

Wichtiger Hinweis: Der Abstand editdist3 ist damit normalisiert

Der Wert 100 wird zum Einfügen und Löschen und der Wert 150 zum Ersetzen verwendet

Hier ist, was Sie unter Windows zuerst tun müssen:

  1. Laden Sie https://sqlite.org/2016/sqlite-src-3110100.zip , https://sqlite.org/2016/sqlite-amalgamation-3110100.zip herunter und entpacken Sie sie

  2. Ersetzen Sie hier C:\Python27\DLLs\sqlite3.dll durch die neue sqlite3.dll . Wenn Sie dies überspringen, erhalten Sie einen sqlite3.OperationalError: The specified procedure could not be found

  3. Lauf:

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

    oder

    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

    (Bei MinGW wäre das: gcc -g -shared spellfix.c -I ~/sqlite-amalgation-3230100/ -o spellfix.dll )

So geht's unter Linux Debian:

(basierend auf dieser Antwort )

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

So machen Sie es unter Linux Debian mit einer älteren Python-Version:

Wenn das Python Ihrer Distribution ein bisschen alt ist, ist eine andere Methode erforderlich. Da das sqlite3 Modul in Python integriert ist, scheint es nicht einfach zu sein, es zu aktualisieren ( pip install --upgrade pysqlite aktualisiert nur das pysqlite-Modul, nicht die zugrunde liegende SQLite-Bibliothek). So funktioniert diese Methode beispielsweise beim import sqlite3; print sqlite3.sqlite_version import sqlite3; print sqlite3.sqlite_version ist 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')]

Gibt es in Python + Sqlite ein Maß für die String-Ähnlichkeit, zum Beispiel mit dem sqlite3 Modul?

Anwendungsbeispiel:

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")')

Diese Abfrage sollte mit der Zeile mit der ID 1 übereinstimmen, nicht jedoch mit der Zeile mit der ID 2:

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

Wie mache ich das in Sqlite + Python?

Anmerkungen zu dem, was ich bisher gefunden habe:

  • Der Levenshtein-Abstand , dh die minimale Anzahl von Einzelzeichenänderungen (Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern, kann nützlich sein, ich bin mir jedoch nicht sicher, ob eine offizielle Implementierung in Sqlite vorhanden ist (ich habe) ein paar benutzerdefinierte Implementierungen gesehen, wie diese )

  • Das Damerau-Levenshtein ist dasselbe, außer dass es auch die Transposition zwischen 2 benachbarten Zeichen erlaubt; Es wird auch als Bearbeitungsentfernung bezeichnet

  • Ich weiß, dass es möglich ist , eine Funktion selbst zu definieren , aber die Implementierung einer solchen Distanz wird nicht trivial sein (es ist wirklich nicht trivial, den Vergleich der Verarbeitung natürlicher Sprache für Datenbanken sehr effizient durchzuführen). Deshalb wollte ich wissen, ob Python / Sqlite bereits über solche Funktionen verfügt ein Werkzeug

  • Sqlite verfügt über FTS-Funktionen (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 */

    Aber ich finde keinen Vergleich von Zeichenfolgen mit einer solchen "Ähnlichkeitsentfernung". Die FTS-Funktionen MATCH oder NEAR scheinen kein Ähnlichkeitsmaß für Buchstabenänderungen usw. zu haben.

  • Darüber hinaus zeigt diese Antwort , dass:

    Die FTS-Engine von SQLite basiert auf Tokens - Schlüsselwörtern, mit denen die Suchmaschine übereinstimmt.
    Eine Vielzahl von Tokenisierern ist verfügbar, sie sind jedoch relativ einfach. Der "einfache" Tokenizer teilt einfach jedes Wort auf und setzt es in Kleinbuchstaben: In der Zeichenfolge "Der schnelle braune Fuchs springt über den faulen Hund" stimmt das Wort "Sprünge" überein, aber nicht "Springen". Der Tokenizer "porter" ist etwas fortgeschrittener und entfernt die Wortkonjugationen , sodass "jumps" und "jumping" übereinstimmen, ein Tippfehler wie "jmups" jedoch nicht.

    Letzteres (die Tatsache, dass "jmups" nicht so ähnlich wie "jumps" gefunden werden kann) macht es für meinen Anwendungsfall leider unpraktisch.





similarity