PostgreSQLLa base de données la plus sophistiquée au monde.

F.29. pg_trgm

Le module pg_trgm fournit des fonctions et opérateurs qui permettent de déterminer des similarités de textes en fonction de correspondances de trigrammes. Il fournit également des classes d'opérateur accélérant les recherches de chaînes similaires.

F.29.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]

Note

Une chaîne 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 '). (Les espaces de début et de fin de chaînes sont importantes.)

F.29.2. Fonctions et opérateurs

Tableau F.27. 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.)
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.
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.

Tableau F.28. 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 set_limit.

F.29.3. 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 l'opérateur de similarité % (et aucun autre opérateur, donc vous pouvez aussi créer un index btree standard).

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.

Le choix d'un indexage GiST ou GIN dépend des caractéristiques relatives de performance qui sont discutées ailleurs. Comme règle de base, un index GIN est plus rapide pour la recherche qu'un index GiST mais plus lent pour la construction et la mise à jour ; donc GIN est préférable pour des données statiques et GiST pour des données souvent mises à jour.

F.29.4. 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');
  

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]

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.

F.29.6. Auteurs

Oleg Bartunov , Moscou, Université de Moscou, Russie

Teodor Sigaev , Moscou, Delta-Soft Ltd., Russie

Documentation : Christopher Kings-Lynne

Ce module est sponsorisé par Delta-Soft Ltd., Moscou, Russie.