Wie Fuzzy-String-Suche ohne eine schwere Datenbank zu tun?

Question

Ich habe eine Zuordnung von Katalognummern zu Produktnamen:

35 cozy comforter 
35 warm blanket 
67 pillow 

und brauchen eine Suche, die falsch geschriebenen finden würde, gemischte Namen wie „warm cmfrter“.

Wir haben Code mit Edit-Abstand (Difflib), aber es wird wahrscheinlich nicht auf die 18000 Namen skalieren.

Ich habe etwas ähnliches mit Lucene erreicht, aber als PyLucene nur Wraps Java, die Bereitstellung für Endbenutzer komplizieren würde.

SQLite in der Regel nicht über Volltext oder Scoring in zusammengestellt.

Die Xapian bindings wie C++ und einig Lernkurve.

Whoosh ist noch nicht gut dokumentiert, enthält aber eine unzulässige Rechtschreibprüfung.

Was gibt es noch?

Answer 1

Nucular verfügt über Volltextsuche, unterstützt jedoch keine falsch geschriebenen Übereinstimmungen Out-of-the-Box. Sie könnten versuchen, ein zusätzliches Feld zu jedem Eintrag hinzuzufügen, der die SOUNDEX Übersetzung der Begriffe indexiert und dann mit der soundex-Übersetzung der Benutzereingabe sucht. Ich weiß wirklich nicht, wie gut würde das funktionieren ...

Werfen Sie einen Blick auf Advas http://advas.sourceforge.net/news.php, die eine schöne Demo Vergleich verschiedener soundex-alike Methoden hat:

advas/examples Aaron$ python phonetic_algorithms.py 
        soundex  metaphone   nyiis  caverphone 
==================================================================================================== 
schmidt :    S253   sxmtt   sssnad  SKMT111111 
    schmid :    S253   sxmt   sssnad  SKMT111111 
schmitt :    S253   sxmt   sssnatt  SKMT111111 
    smith :    S530   sm0h   snatt  SMT1111111 
    smythe :    S530   smy0h   snatt  SMT1111111 
schmied :    S253   sxmt   sssnaad  SKMT111111 
    mayer :    M600    myr   naaar  MA11111111 
    meier :    M600    mr   naaar  MA11111111 
.... 

Ich weiß nicht, ob Jeder von ihnen ist gut für Ihre unbenannte Sprache ...

Answer 2

Sie werden zu viele falsche positive Ergebnisse mit der SOUNDEX-Implementierung bekommen. Es gibt nur 26.000 (höchstens) mögliche SOUNDEX-Codes.

Obwohl der Metaphone Algorithmus für englische Nachnamen entwickelt wurde, funktioniert er ziemlich gut für Rechtschreibfehler; Ich habe es einmal in einem Filialfinder benutzt und es war ziemlich erfolgreich.

Fügen Sie ein Feld mit der Metaphone-Übersetzung hinzu und passen Sie es an, wenn keine exakte Übereinstimmung gefunden wird. Sie erhalten immer noch falsche Positive, aber weniger mit anderen Algorithmen.

Answer 3

Die übliche Methode, die Bearbeitungsdistanz zwischen zwei Strings zu berechnen, ist ein ziemlich teurer Algorithmus (wenn ich mich richtig erinnere, ist seine Zeitkomplexität quadratisch). Wenn Sie eine andere Zeichenfolgenähnlichkeitsmetrik verwenden, wird Ihr Problem möglicherweise verschwinden.

Eine meiner Lieblingsmethoden für Fuzzy String Matching ist trigrams matching. Der Vergleich von zwei Strings mit dieser Methode hat eine lineare Zeitkomplexität, die viel besser ist als die erwähnte Editierdistanz. Sie können meine Python-Implementierung unter Github finden. Es gibt auch einen PostgreSQL contrib module genau dafür. Es sollte nicht zu schwierig sein, es an die Arbeit mit SQLite3 anzupassen.

Answer 4

Sybase SQL Anywhere hat eine kostenlose Web Edition/Developer Edition und kommt mit Volltextindexierung/Suche und einem FUZZY-Operator (und einigen Implementierungsbeschränkungen).

aus der Dokumentation zu zitieren:

Specifying 'FUZZY "500 main street"' is equivalent to 
'500 OR mai OR ain OR str OR tre OR ree OR eet'. 

Ein anderer Ansatz Scoring auf eine Volltextsuche zu verwenden wäre.

Answer 5

Anscheinend ist der einzige Weg, Fuzzy-Vergleiche schnell zu machen, ist weniger von ihnen zu tun;)

Statt eine weitere n-Gramm-Suche oder die Verbesserung der eine in Whoosh rufen wir jetzt einen Wortindex halten, um alle Einträge zu schreiben, die habe mindestens ein (richtig geschriebenes) Wort mit der Abfrage gemeinsam und verwende difflib, um diese zu bewerten. Funktioniert in diesem Fall gut genug.

Answer 6

sqlite3 unterstützt Python-Callback-Funktionen. Matthew Barnetts Regex (http://code.google.com/p/mrab-regex-hg/) unterstützt nun das ungefähre Matching.

So, wie folgt aus:

try: 
    import regex 
except ImportError: 
    sys.stderr.write("Can't import mrab-regex; see http://pypi.python.org/pypi/regex\n") 
    sys.exit(1) 

def _sqlite3_regex(expr, item): 
    return (not (not regex.search(expr, item))) 

def main(): 
    ... 
    database = sqlite3.connect(dbfile) 
    database.create_function("regexp", 2, _sqlite3_regex) 
    pattern = '(?:%s){e<=%d}' % (queriedname, distance) 
    print [x for x in database.cursor().execute(
     "SELECT * FROM products WHERE (productname regexp '%s')" % pattern)]