Trouver des correspondances approximatives avec la recherche floue

Cette page explique comment utiliser une recherche approximative dans le cadre d'une recherche en texte intégral.

En plus d'effectuer des recherches exactes de jetons à l'aide des fonctions SEARCH et SEARCH_SUBSTRING, Spanner accepte également les recherches approximatives (ou floues). Les recherches approximatives permettent de trouver des documents correspondants malgré de petites différences entre la requête et le document.

Spanner est compatible avec les types de recherche approximative suivants :

Recherche approximative basée sur les N-grammes
Recherche phonétique à l'aide de Soundex

Utiliser une recherche approximative basée sur les n-grammes

La recherche approximative basée sur les n-grammes repose sur la même tokenisation de sous-chaîne que celle requise par une recherche de sous-chaîne. La configuration du tokenizer est importante, car elle affecte la qualité et les performances de la recherche. L'exemple suivant montre comment créer une requête avec des mots mal orthographiés ou orthographiés différemment pour trouver des correspondances approximatives dans l'index de recherche.

Schéma

GoogleSQL

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (
    TOKENIZE_SUBSTRING(AlbumTitle, ngram_size_min=>2, ngram_size_max=>3,
                      relative_search_types=>["word_prefix", "word_suffix"])) HIDDEN
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsIndex
ON Albums(AlbumTitle_Tokens)
STORING (AlbumTitle);

PostgreSQL

Cet exemple utilise spanner.tokenize_substring.

CREATE TABLE albums (
  albumid character varying NOT NULL,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (
    spanner.tokenize_substring(albumtitle, ngram_size_min=>2, ngram_size_max=>3,
                      relative_search_types=>'{word_prefix, word_suffix}'::text[])) VIRTUAL HIDDEN,
PRIMARY KEY(albumid));

CREATE SEARCH INDEX albumsindex
ON albums(albumtitle_tokens)
INCLUDE (albumtitle);

Requête

La requête suivante recherche les albums dont le titre est le plus proche de "Hatel Kaliphorn", comme "Hotel California".

GoogleSQL

SELECT AlbumId
FROM Albums
WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn")
ORDER BY SCORE_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn") DESC
LIMIT 10

PostgreSQL

Cet exemple utilise spanner.score_ngrams et spanner.search_ngrams.

SELECT albumid
FROM albums
WHERE spanner.search_ngrams(albumtitle_tokens, 'Hatel Kaliphorn')
ORDER BY spanner.score_ngrams(albumtitle_tokens, 'Hatel Kaliphorn') DESC
LIMIT 10

Optimiser les performances et le rappel pour une recherche approximative basée sur les n-grammes

L'exemple de requête de la section précédente effectue une recherche en deux phases, à l'aide de deux fonctions différentes :

SEARCH_NGRAMS trouve tous les albums candidats qui ont des n-grammes partagés avec la requête de recherche. Par exemple, les n-grammes de trois caractères pour "Californie" incluent [cal, ali, lif, ifo, for, orn, rni, nia] et ceux pour "Kaliphorn" incluent [kal, ali, lip, iph, pho, hor, orn]. Les n-grammes partagés dans ces ensembles de données sont [ali, orn]. Par défaut, SEARCH_NGRAMS correspond à tous les documents comportant au moins deux n-grammes partagés. Par conséquent, "Kaliphorn" correspond à "California".
SCORE_NGRAMS classe les correspondances par similarité. La similarité de deux chaînes est définie comme un ratio de N-grammes distincts partagés par rapport aux N-grammes distincts non partagés :

$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

En général, la requête de recherche est la même pour les fonctions SEARCH_NGRAMS et SCORE_NGRAMS. La méthode recommandée consiste à utiliser l'argument avec des paramètres de requête plutôt qu'avec des littéraux de chaîne, et à spécifier le même paramètre de requête dans les fonctions SEARCH_NGRAMS et SCORE_NGRAMS.

Spanner dispose de trois arguments de configuration qui peuvent être utilisés avec SEARCH_NGRAMS :

Les tailles minimale et maximale des n-grammes sont spécifiées avec les fonctions TOKENIZE_SUBSTRING ou TOKENIZE_NGRAMS. Nous ne recommandons pas les n-grammes d'un caractère, car ils peuvent correspondre à un très grand nombre de documents. En revanche, les n-grammes longs empêchent SEARCH_NGRAMS de détecter les mots courts mal orthographiés.
Nombre minimal de n-grammes auxquels SEARCH_NGRAMS doit correspondre (défini avec les arguments min_ngrams et min_ngrams_percent dans SEARCH_NGRAMS). Des nombres plus élevés accélèrent généralement la requête, mais réduisent le rappel.

Pour trouver un bon équilibre entre performances et rappel, vous pouvez configurer ces arguments en fonction de la requête et de la charge de travail spécifiques.

Nous vous recommandons également d'inclure un LIMIT interne pour éviter de créer des requêtes très coûteuses lorsqu'une combinaison de n-grammes populaires est rencontrée.

GoogleSQL

SELECT AlbumId
FROM (
  SELECT AlbumId,
        SCORE_NGRAMS(AlbumTitle_Tokens, @p) AS score
  FROM Albums
  WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, @p)
  LIMIT 10000  # inner limit
)
ORDER BY score DESC
LIMIT 10  # outer limit

PostgreSQL

Cet exemple utilise spanner.score_ngrams et spanner.search_ngrams. Le paramètre de requête $1 est lié à "Hatel Kaliphorn".

SELECT albumid
FROM
  (
    SELECT albumid, spanner.score_ngrams(albumtitle_tokens, $1) AS score
    FROM albums
    WHERE spanner.search_ngrams(albumtitle_tokens, $1)
    LIMIT 10000
  ) AS inner_query
ORDER BY inner_query.score DESC
LIMIT 10

Recherche approximative basée sur les n-grammes et mode requête amélioré

En plus de la recherche approximative basée sur les n-grammes, le mode requête amélioré gère également certains mots mal orthographiés. Il existe donc un certain chevauchement entre les deux fonctionnalités. Le tableau suivant récapitule les différences :

	Recherche de correspondance partielle basée sur les n-grammes	Mode requête amélioré
Coût	Nécessite une tokenisation de sous-chaîne plus coûteuse basée sur des n-grammes	Nécessite une tokenisation en texte intégral moins coûteuse
Types de requêtes de recherche	Fonctionne bien avec les documents courts contenant quelques mots, comme un nom de personne, de ville ou de produit	Fonctionne aussi bien avec des documents de n'importe quelle taille qu'avec des requêtes de recherche de n'importe quelle taille
Recherche de mots partiels	Effectue une recherche de sous-chaîne qui tolère les fautes d'orthographe	Ne prend en charge que la recherche de mots entiers (`SEARCH_SUBSTRING` ne prend pas en charge l'argument `enhance_query`)
Mots mal orthographiés	Prend en charge les mots mal orthographiés dans l'index ou la requête	Ne prend en charge que les mots mal orthographiés dans la requête
Corrections	Trouve les correspondances mal orthographiées, même si elles ne sont pas de vrais mots	Corrige les fautes d'orthographe pour les mots courants et connus

Effectuer une recherche phonétique avec Soundex

Spanner fournit la fonction SOUNDEX pour trouver les mots qui s'écrivent différemment, mais qui se prononcent de la même façon. Par exemple, SOUNDEX("steven"), SOUNDEX("stephen") et SOUNDEX("stefan") sont tous "s315", tandis que SOUNDEX("stella") est "s340". SOUNDEX est sensible à la casse et ne fonctionne que pour les alphabets latins.

La recherche phonétique avec SOUNDEX peut être implémentée avec une colonne générée et un index de recherche, comme illustré dans l'exemple suivant :

GoogleSQL

CREATE TABLE Singers (
  SingerId INT64,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN,
  Name STRING(MAX),
  NameSoundex STRING(MAX) AS (LOWER(SOUNDEX(Name))),
  NameSoundex_Tokens TOKENLIST AS (TOKEN(NameSoundex)) HIDDEN
) PRIMARY KEY(SingerId);

CREATE SEARCH INDEX SingersPhoneticIndex ON Singers(AlbumTitle_Tokens, NameSoundex_Tokens);

PostgreSQL

Cet exemple utilise spanner.soundex.

CREATE TABLE singers (
  singerid bigint,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.tokenize_fulltext(albumtitle)) VIRTUAL HIDDEN,
  name character varying,
  namesoundex character varying GENERATED ALWAYS AS (lower(spanner.soundex(name))) VIRTUAL,
  namesoundex_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.token(lower(spanner.soundex(name))) VIRTUAL HIDDEN,
PRIMARY KEY(singerid));

CREATE SEARCH INDEX singersphoneticindex ON singers(albumtitle_tokens, namesoundex_tokens);

La requête suivante associe "stefan" à "Steven" sur SOUNDEX, ainsi qu'à AlbumTitle contenant "chat" :

GoogleSQL

SELECT SingerId
FROM Singers
WHERE NameSoundex = LOWER(SOUNDEX("stefan")) AND SEARCH(AlbumTitle_Tokens, "cat")

PostgreSQL

SELECT singerid
FROM singers
WHERE namesoundex = lower(spanner.soundex('stefan')) AND spanner.search(albumtitle_tokens, 'cat')

Étapes suivantes

En savoir plus sur la tokenisation et les tokenizers Spanner
En savoir plus sur les index de recherche
En savoir plus sur les requêtes de recherche en texte intégral

Trouver des correspondances approximatives avec la recherche floue Restez organisé à l'aide des collections Enregistrez et classez les contenus selon vos préférences.

Utiliser une recherche approximative basée sur les n-grammes

GoogleSQL

PostgreSQL

GoogleSQL

PostgreSQL

Optimiser les performances et le rappel pour une recherche approximative basée sur les n-grammes

GoogleSQL

PostgreSQL

Recherche approximative basée sur les n-grammes et mode requête amélioré

Effectuer une recherche phonétique avec Soundex

GoogleSQL

PostgreSQL

GoogleSQL

PostgreSQL

Étapes suivantes

Trouver des correspondances approximatives avec la recherche floue