Le module pg_trgm
fournit des fonctions et
opérateurs qui permettent de déterminer des similarités de textes
alphanumériques en fonction de correspondances de trigrammes. Il
fournit également des classes d'opérateur accélérant les recherches de
chaînes similaires.
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.
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
« foo|bar
» est
« f
»,
« fo
»,
« foo
»,
« oo
»,
« b
»,
« ba
»,
« bar
» et
« ar
».
Les fonctions fournies par le module pg_trgm
sont affichées dans Tableau F.25 alors que
les opérateurs sont indiqués dans Tableau F.26.
Tableau F.25. Fonctions de pg_trgm
Prenons l'exemple suivant :
# SELECT word_similarity('word', 'two words'); word_similarity ----------------- 0.8 (1 row)
Dans la première chaîne, l'ensemble de trigrammes est
{" w"," wo","ord","wor","rd "}
. Dans la seconde chaîne,
l'ensemble trié de trigrammes est
{" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}
.
L'étendue la plus similaire d'un ensemble trié de trigrammes dans la
seconde chaîne est {" w"," wo","wor","ord"}
, et la
similarité est 0.8
.
Cette fonction renvoie une valeur qui peut être comprise approximativement comme la plus grande similarité entre la première chaîne et toute sous-chaîne de la deuxième chaîne. Néanmoins, cette fonction n'ajoute pas de remplissage aux limites de l'étendue. De ce fait, le nombre de caractères supplémentaires présents dans la deuxième chaîne n'est pas considéré, sauf pour ce qui concerne les limites de mot sans correspondance.
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 la similarité entre l'ensemble de
trigrammes du premier argument et une étendue continue d'un ensemble
trie de trigrammes dans le second argument est plus grande que la
limite de similarité actuelle, telle qu'elle est configurée avec le
paramètre pg_trgm.word_similarity_threshold .
|
text %> text | boolean |
Commutateur de l'opérateur <% .
|
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).
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 texte pour lesquelles il
existe une étendue continue de l'ensemble ordonné de trigrammes qui est
suffisamment similaire à l'ensemble de trigrammes de
word
, trié de la meilleure correspondance à la
pire. L'index sera utilisé pour accélérer l'opération y compris sur des
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.
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é.
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.
Oleg Bartunov <oleg@sai.msu.su>
, Moscou, Université de Moscou,
Russie
Teodor Sigaev <teodor@sigaev.ru>
, Moscou, Delta-Soft Ltd.,
Russie
Alexander Korotkov <a.korotkov@postgrespro.ru>
, Moscou, Postgres Professional, Russie
Documentation : Christopher Kings-Lynne
Ce module est sponsorisé par Delta-Soft Ltd., Moscou, Russie.