Da Trigramm-Algorithmus: Fuzzy Matching ohne Zauberei

#algorithms#databases#sql#python

A Trigramm is nur drei aufeinanderfolgende Zeichen, und die Trigramm-Mengen von zwoa Strings zu vergleichn gibt dir an schnellen, tippfehlertoleranten Ähnlichkeitswert zwischn 0 und 1. Des is die Idee hinter PostgreSQLs pg_trgm, und es passt in etwa dreißig Zeiln Python. Dieser Beitrag baut's von Grund auf, zeigt, warum's für Search-as-you-type guat funktioniert, und ordnet's dann dem zu, wos Postgres für di mocht.

Die Kernidee

Nimm a Wort, polster's auf und schieb a Fenster aus drei Zeichen drüber. Für cat, mit zwoa Leerzeichen vorn und oans hinten, kriagst:

sorted(trigrams("cat"))
# ['  c', ' ca', 'at ', 'cat']

Des Polstern zählt. Es lasst Anfang und End vo am Wort ois eigene Merkmale zähln: c taucht nur in Wörtern auf, de mit c anfangen, und at nur in Wörtern, de auf at aufhörn. Ohne Polsterung würdn der erste und letzte Buchstabe vo am Wort in weniger Trigrammen vorkemman ois die Buchstabn in da Mitte.

Um zwoa Strings zu vergleichn, berechnest beide Trigramm-Mengen und nimmst des Verhältnis von dem, wos sie teiln, zu dem, wos sie insgesamt hom. Des is der Jaccard-Index:

similarity(a, b) = |T(a) ∩ T(b)| / |T(a) ∪ T(b)|

Identische Strings kriagn 1,0, Strings ohne gemeinsames Trigramm 0,0, und olles andere liegt dazwischn.

A funktionierende Implementierung

Do is des Ganze, im Stil von pg_trgm gschriebn: Eingabe klein machn, in alphanumerische Wörter zerlegn, jedes Wort polstern und die Trigramme von olle Wörter in oa Menge sammeln.

import re

def trigrams(text):
    grams = set()
    for word in re.findall(r"[a-z0-9]+", text.lower()):
        padded = f"  {word} "
        grams.update(padded[i:i + 3] for i in range(len(padded) - 2))
    return grams

def similarity(a, b):
    ta, tb = trigrams(a), trigrams(b)
    if not ta or not tb:
        return 0.0
    return len(ta & tb) / len(ta | tb)

Diese Version erkennt nur ASCII-Buchstabn und Ziffern, um kurz zu bleibn. A echte Implementierung muass entscheidn, wos für Umlaute und ondere Schriften ois Wortzeichen zählt.

A poar Ergebnisse vom Ausführn:

similarity("word", "two words")      # 0.3636
similarity("Kartoffel", "Kartofel")  # 0.7273
similarity("postgres", "postgresql") # 0.6667
similarity("postgres", "progress")   # 0.2

Die erste Zoi stimmt mit dem Beispiel aus da PostgreSQL-Dokumentation für similarity('word', 'two words') überein, wos a nützlicher Plausibilitätscheck is, dass die Polster-Regeln stimmen.

Die letzten zwoa Zeiln zeigen den interessanten Teil. postgres und postgresql sand eindeutig verwandt und kriagn 0,67. postgres und progress nutzn fost dieselben Buchstabn, aber in ana ondern Reihenfolge, und kriagn nur 0,2. A einfacher Zeichenhäufigkeitsvergleich würd de zwoa ois nahe beieinander bezeichnen. Trigramme erfassn die lokale Reihenfolge, und genau des mocht sie nützlich für Namen und Wörter.

Warum drei?

De Länge vom Fenster is a Kompromiss:

Mit Bigrammen (zwoa Zeichen) teiln fost alle Wortpaare irgendwos, drum wern die Scores verrauscht und die Kandidatenlisten long.
Mit Trigrammen sand die Merkmale spezifisch gnua zum Unterscheidn, und a einzelner Tippfehler beschädigt nur a poar davon.
Mit vier oda mehr Zeichen erzeugn kurze Wörter sehr wenige Merkmale, und a Tippfehler zerstört an größeren Anteil von da Menge.

A einzelner falscher Buchstabe in da Mitte vo am Wort zerstört höchstens drei Trigramme, weil nur drei Fenster diese Position abdeckn. A längeres Wort überlebt also an Tippfehler mit den meisten seiner Trigramme intakt. Drum kriagt Kartofel gegn Kartoffel no immer 0,73, a wenn a Buchstabe fehlt.

Trigramme sand koa Edit-Distanz-Algorithmus. Sie sogn dir ned, wia vül Operationen zwoa Strings trennen, und sie funktionieren bei sehr kurzen Strings am schlechtesten, wo's kaum Merkmale zum Vergleichn gibt. Ihre Stärke is wos ondres: De Trigramm-Mengen kinnan indiziert wern.

Schnö machn mit am invertierten Index

A Query gegn jede Zeiln zu vergleichn funktioniert bei a poar hundert Einträgen und bricht bei Millionen zam. Da Trick is, jedes Trigramm ois Schlüssel in am invertierten Index zu behandeln, der auf die Einträge zeigt, de es enthoitn. A Query muass dann nur Einträge anschaun, de mindestens a Trigramm mit ihr teiln:

from collections import defaultdict

class TrigramIndex:
    def __init__(self, items):
        self.items = list(items)
        self.grams = [trigrams(x) for x in self.items]
        self.postings = defaultdict(set)
        for i, g in enumerate(self.grams):
            for t in g:
                self.postings[t].add(i)

    def search(self, query, threshold=0.3):
        q = trigrams(query)
        candidates = set()
        for t in q:
            candidates |= self.postings.get(t, set())
        hits = []
        for i in candidates:
            g = self.grams[i]
            score = len(q & g) / len(q | g)
            if score >= threshold:
                hits.append((score, self.items[i]))
        return sorted(hits, reverse=True)

Da Index engt des Feld billig ein, und da exakte Score wird nur für die Kandidaten berechnet. Probier's an ana klanen Liste mit Datenbanknamen:

idx = TrigramIndex(["PostgreSQL", "MySQL", "MariaDB", "SQLite",
                    "Postgres-XL", "Redis", "MongoDB"])

idx.search("postgre")
# [(0.583, 'PostgreSQL'), (0.538, 'Postgres-XL')]

idx.search("postgress")
# [(0.615, 'PostgreSQL'), (0.571, 'Postgres-XL')]

Sowohl des abgschnittene postgre ois a des falsch gschriebene postgress finden die richtigen Einträge, und MySQL und SQLite bleibn draußen, a wenn sie die Buchstabn sql mit PostgreSQL teiln. Da Schwellenwert von 0,3 is derselbe Standard, den pg_trgm nutzt.

Des Gleiche in PostgreSQL

In ana Datenbank brauchst des ned söba bauen. De Erweiterung pg_trgm kummt mit den Standard-Contrib-Modulen:

CREATE EXTENSION IF NOT EXISTS pg_trgm;

SELECT similarity('Kartoffel', 'Kartofel');
SELECT show_trgm('cat');

show_trgm gibt die Trigramm-Menge zruck, und similarity den Score, sodass du deine eigene Implementierung dagegn prüfn kannst. Da Operator % is wahr, wenn da Score über dem aktuellen Schwellenwert liegt (pg_trgm.similarity_threshold, standardmäßig 0,3), und <-> gibt die Distanz zruck, de 1 minus die Ähnlichkeit is:

CREATE TABLE products (id serial PRIMARY KEY, name text NOT NULL);

CREATE INDEX products_name_trgm_idx
  ON products USING gin (name gin_trgm_ops);

SELECT name, similarity(name, 'postgress') AS score
FROM products
WHERE name % 'postgress'
ORDER BY score DESC
LIMIT 10;

Da GIN-Index is der invertierte Index aus dem Python-Beispiel, von da Datenbank gwoartet. A Bonus is, dass da söbe Index a LIKE '%term%'- und ILIKE-Abfragen beschleunigt, de normalerweise an sequenziellen Scan erzwingen, weil a B-Baum bei am führenden Wildcard ned hüfn kann. Wennst hauptsächlich Nächster-Nachbar-Sortierung mit ORDER BY name <-> 'postgress' brauchst, passt a GiST-Index mit gist_trgm_ops besser.

Wann ma's nimmt, und wann ned

Trigramm-Matching passt guat für:

Search-as-you-type auf Namen, Titel und Produktlisten
Tippfehlertolerante Suchen, wia die Eingabe von am Nutzer gegn a Liste vo Städte abzugleichn
Wahrscheinliche Duplikate in ana Tabelle mit Kunden- oda Firmennamen finden

Es passt schlecht für:

Sehr kurze Strings, wo oans oda zwoa Zeichen den ganzen Score entscheiden
Semantische Suche, weil car und automobile koa gemeinsames Trigramm hom
Lange Dokumente, wo Volltextsuche mit Stemming und Ranking a bessere Orbeit leistet

Fazit

Da Trigramm-Algorithmus verwandelt unscharfen String-Abgleich in Mengenarithmetik. Wörter polstern, in Drei-Zeichen-Fenster schneiden und die Mengen mit Jaccard vergleichn. Weil sich die Mengen in an invertierten Index legn lassn, skaliert dieselbe Idee von ana Python-Liste bis zu ana Tabelle mit Millionen Zeiln. Wennst eh scho PostgreSQL nutzt, aktivier pg_trgm und füg an GIN-Index dazu, bevor du zu am separaten Suchservice greifst.