F.31. pg

F.31.1. Concepts du trigramme (ou trigraphe)

Un trigramme est un groupe de trois caractères consécutifs pris dans une chaîne. Nous pouvons mesurer la similarité de deux chaînes en comptant le nombre de trigrammes qu'elles partagent. Cette idée simple est très efficace pour mesurer la similarité des mots dans la plupart des langues.

Note

pg_trgm ignore les caractères qui ne forment pas de mots (donc non alphanumériques) lors de l'extraction des trigrammes d'une chaîne de caractères. Chaque mot est considérée avoir deux espaces en préfixe et une espace en suffixe lors de la détermination de l'ensemble de trigrammes contenu dans la chaîne. Par exemple, l'ensemble des trigrammes dans la chaîne « cat » est « c » (' c'), « ca » (' ca'), « cat » et « at » ('at '). L'ensemble de trigrammes dans la chaîne set of trigrams in the string « foo|bar » est « f », « fo », « foo », « oo », « b », « ba », « bar » et « ar ».

F.31.2. Fonctions et opérateurs

Les fonctions fournies par le module pg_trgm sont affichées dans Tableau F.25, « Fonctions de pg_trgm » alors que les opérateurs sont indiqués dans Tableau F.26, « Opérateurs de pg_trgm ».

Tableau F.25. Fonctions de pg_trgm

Fonction	Retour	Description
`similarity(text, text)`	real	Renvoie un nombre indiquant la similarité des deux arguments. L'échelle du résultat va de zéro (indiquant que les deux chaînes sont complètement différentes) à un (indiquant que les deux chaînes sont identiques).
`show_trgm(text)`	text[]	Renvoie un tableau de tous les trigrammes d'une chaîne donnée. (En pratique, ceci est peu utile, sauf pour le débogage.)
`word_similarity(text, text)`	real	Renvoie un nombre indiquant la similarité de la première chaîne avec le mot le plus similaire de la deuxième chaîne. La fonction recherche dans la deuxième chaîne un mot le plus similaire, pas une sous-chaîne la plus similaire. Le résultat va de zéro (indiquant que les deux chaînes sont complètement différentes) à un (indiquant que la première chaîne est identique à un des mots de la deuxième chaîne).
`show_limit()`	real	Renvoie la limite de similarité utilisée par l'opérateur `%`. Ceci configure la similarité minimale entre deux mots pour qu'ils soient considérés suffisamment proches, par exemple (obsolète).
`set_limit(real)`	real	Configure la limite de similarité actuelle utilisée par l'opérateur `%`. Le limite se positionne entre 0 et 1, elle vaut par défaut 0,3. Renvoie la valeur passée (obsolète).
text `<->` text	real	Renvoie la « distance » entre les arguments, qui vaut un moins la valeur de `similarity()`.
text `<<->` text	real	Renvoie la « distance » entre les arguments, qui est équivalente 1 moins la valeur de `word_similarity()`.
text `<->>` text	real	Commutateur de l'opérateur `<<->`.

Tableau F.26. Opérateurs de pg_trgm

Opérateur	Retour	Description
text `%` text	boolean	Renvoie `true` si les arguments ont une similarité supérieure à la limite configurée par `pg_trgm.similarity_threshold`.
text `<%` text	boolean	Renvoie `true` si son premier argument a un mot similaire dans le deuxième argument et ils ont une similarité qui est supérieure à la limite de similarité du mot courant configurée avec le paramètre `pg_trgm.word_similarity_threshold`.
text `%>` text	boolean	Commutateur de l'opérateur `<%`.

F.31.3. Paramètres GUC

pg_trgm.similarity_threshold (real): Configure la limite actuelle de similarité utilisée par l'opérateur %. La limite doit se situer entre 0 et 1 (la valeur par défaut est 0,3).
pg_trgm.word_similarity_threshold (real): Configure la limite actuelle de similarité utilisée par les opérateurs <% et %>. La limite doit être comprise entre 0 et 1 (la valeur par défaut est 0,6).

F.31.4. Support des index

Le module pg_trgm fournit des classes d'opérateurs pour les index GiST et GIN qui vous permettent de créer un index sur une colonne de type text dans le but d'accélérer les recherches de similarité. Ces types d'index supportent les opérateurs de similarité décrits ci-dessus et supportent de plus les recherches basées sur des trigrammes pour les requêtes LIKE, ILIKE, ~ et ~*. (Ces index ne supportent pas les opérateurs d'égalité ou de comparaison simple, donc vous pouvez aussi avoir besoin d'un index B-tree).

Exemple :

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

ou

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

À ce point, vous aurez un index sur la colonne t que vous pouvez utiliser pour une recherche de similarité. Une requête typique est :

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

Ceci renverra toutes les valeurs dans la colonne texte qui sont suffisamment similaire à word, triées de la meilleure correspondance à la pire. L'index sera utilisé pour accélérer l'opération même sur un grand ensemble de données.

Une variante de la requête ci-dessus est

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Ceci peut être implémenté assez efficacement par des index GiST, mais pas par des index GIN. Cela battra généralement la première formulation quand seulement un petit nombre de correspondances proches est demandé.

De plus, vous pouvez utiliser un index sur la colonne t pour la similarité de mot. Par exemple :

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <% t
  ORDER BY sml DESC, t;

Ceci renverra toutes les valeurs dans la colonne de type texte qui ont un mot suffisamment similaire à word, triées de la meilleure correspondance à la pire. L'index sera utilisé pour en faire une opération rapide même sur de très gros ensembles de données.

Une variante de la requête ci-dessus est :

SELECT t, 'word' <<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Ceci peut être implémenté assez efficacement par des index GiST, mais pas par des index GIN.

À partir de PostgreSQL™ 9.1, ces types d'index supportent aussi les recherches d'index pour LIKE et ILIKE, par exemple

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

La recherche par index fonctionne par extraction des trigrammes à partir de la chaîne recherchée puis en les recherchant dans l'index. Plus le nombre de trigrammes dans la recherche est important, plus efficace sera la recherche. Contrairement à des recherches basées sur les B-tree, la chaîne de recherche ne doit pas avoir un signe de pourcentage sur le côté gauche.

À partir de PostgreSQL™ 9.3, ces types d'index supportent aussi les recherches dans l'index pour les correspondances d'expressions rationnelles (opérateurs ~ et ~*). Par exemple

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

La recherche dans l'index fonctionne en extrayant les trigrammes de l'expression rationnelles et en les recherchant dans l'index. Plus il est possible d'extraire de trigrammes de l'expression rationnelle, plus la recherche dans l'index sera efficace. Contrairement aux recherches dans un B-tree, la chaîne de recherche n'a pas besoin d'être fixe à gauche.

Pour les recherches LIKE ainsi que les recherches dans des expressions rationnelles, gardez en tête qu'un motif sans trigramme extractible sera la cause d'un parcours complet de l'index.

Le choix d'un indexage GiST ou GIN dépend des caractéristiques relatives de performance qui sont discutées ailleurs.

F.31.5. Intégration à la recherche plein texte

La correspondance de trigramme est un outil très utile lorsqu'il est utilisé en conjonction avec un index plein texte. En particulier, il peut aider à la reconnaissance des mots mal orthographiés (ou tout simplement mal saisis), mots pour lesquels le mécanisme de recherche plein texte ne pourra pas faire une reconnaissance.

La première étape est la génération d'une table auxiliaire contenant tous les mots uniques dans les documents :

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

où documents est une table qui a un champ texte bodytext où nous voulons faire nos recherches. La raison de l'utilisation de la configuration simple avec la fonction to_tsvector, au lieu d'une configuration spécifique à la langue, est que nous voulons une liste des mots originaux.

Ensuite, nous créons un index trigramme sur la colonne word :

CREATE INDEX words_idx ON words USING GIN(word gin_trgm_ops);

Maintenant, une requête SELECT similaire à l'exemple précédent peut être utilisée pour suggérer des mots dans les termes de la recherche de l'utilisateur. Un test utile supplémentaire vient à demander que les mots sélectionnés soient aussi d'une longueur similaire au mot mal orthographié.

Note

Comme la table words a été générée comme une table statique, séparée, il sera nécessaire de la regénérer périodiquement pour qu'elle reste raisonnablement à jour avec la collection des documents. Qu'elle soit exactement identique en permanence n'est habituellement pas nécessaire.