L'algorithme des trigrammes : la recherche floue sans magie

#algorithms#databases#sql#python

Un trigramme n'est que trois caractères consécutifs, et comparer les ensembles de trigrammes de deux chaînes donne un score de similarité rapide et tolérant aux fautes de frappe entre 0 et 1. C'est l'idée derrière pg_trgm de PostgreSQL, et cela tient en une trentaine de lignes de Python. Cet article le construit de zéro, montre pourquoi il fonctionne bien pour la recherche au fil de la frappe, puis le rapproche de ce que Postgres fait pour vous.

L'idée de base

Prenez un mot, complétez-le par des espaces et faites glisser une fenêtre de trois caractères dessus. Pour cat, avec deux espaces devant et un derrière, on obtient :

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

Le remplissage compte. Il fait que le début et la fin d'un mot comptent comme des caractéristiques à part entière : c n'apparaît que dans les mots qui commencent par c, et at que dans les mots qui finissent par at. Sans remplissage, la première et la dernière lettre d'un mot apparaîtraient dans moins de trigrammes que les lettres du milieu.

Pour comparer deux chaînes, on calcule les deux ensembles de trigrammes et l'on prend le rapport entre ce qu'ils partagent et ce qu'ils ont au total. C'est l'indice de Jaccard :

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

Des chaînes identiques obtiennent 1,0, des chaînes sans aucun trigramme en commun 0,0, et tout le reste se situe entre les deux.

Une implémentation fonctionnelle

Voici l'ensemble, écrit dans le style de pg_trgm : mettre l'entrée en minuscules, la découper en mots alphanumériques, compléter chaque mot et rassembler les trigrammes de tous les mots dans un seul ensemble.

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)

Cette version ne reconnaît que les lettres ASCII et les chiffres, pour rester courte. Une vraie implémentation doit décider de ce qui compte comme caractère de mot pour les trémas et les autres écritures.

Quelques résultats à l'exécution :

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

Le premier nombre correspond à l'exemple de la documentation PostgreSQL pour similarity('word', 'two words'), ce qui est une bonne vérification que les règles de remplissage sont justes.

Les deux dernières lignes montrent la partie intéressante. postgres et postgresql sont clairement liés, et obtiennent 0,67. postgres et progress utilisent presque les mêmes lettres mais dans un ordre différent, et n'obtiennent que 0,2. Une simple comparaison de fréquences de caractères jugerait ces deux mots proches. Les trigrammes capturent l'ordre local, et c'est précisément ce qui les rend utiles pour les noms et les mots.

Pourquoi trois ?

La longueur de la fenêtre est un compromis :

Avec des bigrammes (deux caractères), presque chaque paire de mots partage quelque chose, si bien que les scores deviennent bruités et que les listes de candidats s'allongent.
Avec des trigrammes, les caractéristiques sont assez spécifiques pour discriminer, et une seule faute de frappe n'en abîme que quelques-unes.
Avec quatre caractères ou plus, les mots courts produisent très peu de caractéristiques, et une faute de frappe détruit une plus grande part de l'ensemble.

Une seule lettre erronée au milieu d'un mot casse au plus trois trigrammes, car seules trois fenêtres couvrent cette position. Un mot plus long survit donc à une faute de frappe avec la plupart de ses trigrammes intacts. C'est pourquoi Kartofel obtient encore 0,73 face à Kartoffel, bien qu'il manque une lettre.

Les trigrammes ne sont pas un algorithme de distance d'édition. Ils ne vous disent pas combien d'opérations séparent deux chaînes, et ils fonctionnent le moins bien sur de très courtes chaînes, où il y a à peine de caractéristiques à comparer. Leur force est ailleurs : les ensembles de trigrammes peuvent être indexés.

L'accélérer avec un index inversé

Comparer une requête à chaque ligne marche pour quelques centaines d'entrées et s'effondre pour des millions. L'astuce consiste à traiter chaque trigramme comme une clé d'un index inversé qui pointe vers les entrées qui le contiennent. Une requête n'a alors à regarder que les entrées qui partagent au moins un trigramme avec elle :

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)

L'index restreint le champ à peu de frais, et le score exact n'est calculé que pour les candidats. Essayons sur une petite liste de noms de bases de données :

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

Le postgre tronqué comme le postgress mal orthographié trouvent les bonnes entrées, et MySQL et SQLite restent dehors, bien qu'ils partagent les lettres sql avec PostgreSQL. Le seuil de 0,3 est la valeur par défaut qu'utilise pg_trgm.

La même chose dans PostgreSQL

Dans une base de données, inutile de construire cela soi-même. L'extension pg_trgm est livrée avec les modules contrib standard :

CREATE EXTENSION IF NOT EXISTS pg_trgm;

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

show_trgm renvoie l'ensemble de trigrammes, et similarity le score, de sorte que vous pouvez vérifier votre propre implémentation avec. L'opérateur % est vrai lorsque le score dépasse le seuil actuel (pg_trgm.similarity_threshold, 0,3 par défaut), et <-> renvoie la distance, qui vaut 1 moins la similarité :

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;

L'index GIN est l'index inversé de l'exemple Python, tenu à jour par la base de données. Bonus : le même index accélère aussi les requêtes LIKE '%term%' et ILIKE, qui imposent normalement un balayage séquentiel, car un arbre B ne peut rien pour un joker en tête. Si vous avez surtout besoin d'un classement par plus proche voisin avec ORDER BY name <-> 'postgress', un index GiST avec gist_trgm_ops convient mieux.

Quand l'utiliser, et quand pas

La correspondance par trigrammes convient bien pour :

la recherche au fil de la frappe sur des noms, des titres et des listes de produits
les recherches tolérantes aux fautes, comme faire correspondre la saisie d'un utilisateur à une liste de villes
retrouver des doublons probables dans une table de noms de clients ou d'entreprises

Elle convient mal pour :

les chaînes très courtes, où un ou deux caractères décident de tout le score
la recherche sémantique, puisque car et automobile n'ont aucun trigramme en commun
les longs documents, où la recherche plein texte avec racinisation et classement fait un meilleur travail

À retenir

L'algorithme des trigrammes transforme la recherche floue de chaînes en arithmétique d'ensembles. Complétez les mots, découpez-les en fenêtres de trois caractères et comparez les ensembles avec Jaccard. Comme ces ensembles peuvent être mis dans un index inversé, la même idée passe d'une liste Python à une table de plusieurs millions de lignes. Si vous utilisez déjà PostgreSQL, activez pg_trgm et ajoutez un index GIN avant de recourir à un service de recherche distinct.