Der Trigramm-Algorithmus: Unscharfes Matching ohne Magie

#algorithms#databases#sql#python

Ein Trigramm besteht aus drei aufeinanderfolgenden Zeichen, und der Vergleich der Trigramm-Mengen zweier Strings liefert einen schnellen, tippfehlertoleranten Ähnlichkeitswert zwischen 0 und 1. Das ist die Idee hinter pg_trgm von PostgreSQL, und sie passt in etwa dreißig Zeilen Python. Dieser Beitrag baut sie von Grund auf, zeigt, warum sie sich gut für die Suche beim Tippen eignet, und bildet sie dann auf das ab, was Postgres für dich erledigt.

Die Kernidee

Nimm ein Wort, polstere es auf und schiebe ein Fenster von drei Zeichen darüber. Für cat, mit zwei Leerzeichen davor und einem dahinter, ergibt sich:

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

Das Auffüllen ist wichtig. Dadurch zählen Anfang und Ende eines Wortes als eigene Merkmale: c kommt nur in Wörtern vor, die mit c beginnen, und at nur in Wörtern, die auf at enden. Ohne Auffüllen würden der erste und letzte Buchstabe eines Wortes in weniger Trigrammen vorkommen als die Buchstaben in der Mitte.

Um zwei Strings zu vergleichen, berechnet man beide Trigramm-Mengen und bildet das Verhältnis dessen, was sie teilen, zu dem, was sie insgesamt haben. Das ist der Jaccard-Index:

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

Identische Strings erreichen 1,0, Strings ohne gemeinsames Trigramm 0,0, und alles andere landet dazwischen.

Eine funktionierende Implementierung

Hier ist das Ganze im Stil von pg_trgm: die Eingabe in Kleinbuchstaben umwandeln, in alphanumerische Wörter zerlegen, jedes Wort auffüllen und die Trigramme aller Wörter in einer 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 der Kürze halber nur ASCII-Buchstaben und Ziffern. Eine echte Implementierung muss entscheiden, was für Umlaute und andere Schriften als Wortzeichen gilt.

Einige Ergebnisse beim Ausführen:

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

Die erste Zahl entspricht dem Beispiel in der PostgreSQL-Dokumentation für similarity('word', 'two words') – eine nützliche Plausibilitätsprüfung, dass die Auffüllregeln stimmen.

Die letzten beiden Zeilen zeigen den interessanten Teil. postgres und postgresql sind offensichtlich verwandt und erreichen 0,67. postgres und progress verwenden fast dieselben Buchstaben in anderer Reihenfolge und erreichen nur 0,2. Ein einfacher Vergleich der Zeichenhäufigkeiten würde diese beiden als nah beieinander einstufen. Trigramme erfassen die lokale Reihenfolge, und genau das macht sie für Namen und Wörter nützlich.

Warum drei?

Die Länge des Fensters ist ein Kompromiss:

Bei Bigrammen (zwei Zeichen) teilen fast alle Wortpaare etwas, die Werte werden verrauscht und die Kandidatenlisten lang.
Bei Trigrammen sind die Merkmale spezifisch genug, um zu unterscheiden, und ein einzelner Tippfehler beschädigt nur wenige davon.
Bei vier oder mehr Zeichen erzeugen kurze Wörter sehr wenige Merkmale, und ein Tippfehler zerstört einen größeren Anteil der Menge.

Ein falscher Buchstabe mitten im Wort zerstört höchstens drei Trigramme, weil nur drei Fenster diese Position abdecken. Ein längeres Wort übersteht einen Tippfehler daher mit den meisten seiner Trigramme. Deshalb erreicht Kartofel gegen Kartoffel noch immer 0,73, obwohl ein Buchstabe fehlt.

Trigramme sind kein Edit-Distanz-Algorithmus. Sie sagen nicht, wie viele Operationen zwei Strings trennen, und sie funktionieren bei sehr kurzen Strings am schlechtesten, wo es kaum Merkmale zum Vergleichen gibt. Ihre Stärke liegt woanders: Die Trigramm-Mengen lassen sich indizieren.

Mit einem invertierten Index schnell machen

Eine Anfrage mit jeder Zeile zu vergleichen funktioniert bei ein paar hundert Einträgen und bricht bei Millionen zusammen. Der Trick ist, jedes Trigramm als Schlüssel in einem invertierten Index zu behandeln, der auf die Einträge zeigt, die es enthalten. Eine Anfrage muss dann nur Einträge ansehen, die mindestens ein Trigramm mit ihr teilen:

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)

Der Index grenzt das Feld billig ein, und der exakte Wert wird nur für die Kandidaten berechnet. Probiere es an einer kleinen Liste von Datenbanknamen aus:

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 das abgeschnittene postgre als auch das falsch geschriebene postgress finden die richtigen Einträge, und MySQL und SQLite bleiben draußen, obwohl sie die Buchstaben sql mit PostgreSQL teilen. Der Schwellenwert von 0,3 ist derselbe Standard, den pg_trgm verwendet.

Dasselbe in PostgreSQL

In einer Datenbank muss man das nicht selbst bauen. Die Erweiterung pg_trgm wird mit den Standard-Contrib-Modulen ausgeliefert:

CREATE EXTENSION IF NOT EXISTS pg_trgm;

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

show_trgm gibt die Trigramm-Menge zurück und similarity den Wert, sodass du deine eigene Implementierung dagegen prüfen kannst. Der Operator % ist wahr, wenn der Wert über dem aktuellen Schwellenwert liegt (pg_trgm.similarity_threshold, standardmäßig 0,3), und <-> liefert die Distanz, also 1 minus die Ähnlichkeit:

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;

Der GIN-Index ist der invertierte Index aus dem Python-Beispiel, von der Datenbank gepflegt. Ein Bonus ist, dass derselbe Index auch LIKE '%term%'- und ILIKE-Abfragen beschleunigt, die normalerweise einen sequenziellen Scan erzwingen, weil ein B-Baum bei einem führenden Platzhalter nicht helfen kann. Brauchst du hauptsächlich die Sortierung nach nächsten Nachbarn mit ORDER BY name <-> 'postgress', passt ein GiST-Index mit gist_trgm_ops besser.

Wann man es nutzt und wann nicht

Trigramm-Matching passt gut für:

Suche beim Tippen in Namen, Titeln und Produktlisten
tippfehlertolerante Abfragen, etwa die Eingabe eines Nutzers mit einer Liste von Städten abzugleichen
wahrscheinliche Duplikate in einer Tabelle mit Kunden- oder Firmennamen finden

Es passt schlecht für:

sehr kurze Strings, bei denen ein oder zwei Zeichen den ganzen Wert bestimmen
semantische Suche, denn car und automobile haben keine gemeinsamen Trigramme
lange Dokumente, bei denen Volltextsuche mit Stemming und Ranking besser arbeitet

Fazit

Der Trigramm-Algorithmus verwandelt unscharfes String-Matching in Mengenarithmetik. Die Wörter auffüllen, in Drei-Zeichen-Fenster zerlegen und die Mengen mit Jaccard vergleichen. Weil sich die Mengen in einen invertierten Index legen lassen, skaliert dieselbe Idee von einer Python-Liste bis zu einer Tabelle mit Millionen Zeilen. Wenn du ohnehin PostgreSQL betreibst, aktiviere pg_trgm und füge einen GIN-Index hinzu, bevor du zu einem separaten Suchdienst greifst.