Cómo encontrar coincidencias aproximadas con la búsqueda aproximada

En esta página, se describe cómo usar una búsqueda aproximada como parte de una búsqueda de texto completo.

Además de realizar búsquedas exactas de tokens con las funciones SEARCH y SEARCH_SUBSTRING, Spanner también admite búsquedas aproximadas (o difusas). Las búsquedas aproximadas encuentran documentos coincidentes a pesar de las pequeñas diferencias entre la búsqueda y el documento.

Spanner admite los siguientes tipos de búsqueda aproximada:

  • Búsqueda aproximada basada en n-gramas
  • Búsqueda fonética con Soundex

La búsqueda aproximada basada en n-gramas se basa en la misma tokenización de subcadenas que requiere una búsqueda de subcadenas. La configuración del tokenizador es importante, ya que afecta la calidad y el rendimiento de la búsqueda. En el siguiente ejemplo, se muestra cómo crear una búsqueda con palabras mal escritas o escritas de forma diferente para encontrar coincidencias aproximadas en el índice de búsqueda.

Esquema

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

En este ejemplo, se usa 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);

Consulta

La siguiente búsqueda encuentra los álbumes con títulos más cercanos a "Hatel Kaliphorn", como "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

En este ejemplo, se usan spanner.score_ngrams y 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

Optimiza el rendimiento y la recuperación para una búsqueda aproximada basada en n-gramas

La consulta de ejemplo de la sección anterior realiza la búsqueda en dos fases, con dos funciones diferentes:

  1. SEARCH_NGRAMS encuentra todos los álbumes candidatos que tienen n-gramas compartidos con la búsqueda. Por ejemplo, los n-gramas de tres caracteres para "California" incluyen [cal, ali, lif, ifo, for, orn, rni, nia] y, para "Kaliphorn", incluyen [kal, ali, lip, iph, pho, hor, orn]. Los n-gramas compartidos en estos conjuntos de datos son [ali, orn]. De forma predeterminada, SEARCH_NGRAMS coincide con todos los documentos que tienen al menos dos n-gramas compartidos, por lo que "Kaliphorn" coincide con "California".
  2. SCORE_NGRAMS clasifica las coincidencias por similitud. La similitud de dos cadenas se define como una proporción de n-gramas compartidos distintos con respecto a los n-gramas no compartidos distintos:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Por lo general, la búsqueda es la misma en las funciones SEARCH_NGRAMS y SCORE_NGRAMS. La forma recomendada de hacerlo es usar el argumento con parámetros de consulta en lugar de con literales de cadena, y especificar el mismo parámetro de consulta en las funciones SEARCH_NGRAMS y SCORE_NGRAMS.

Spanner tiene tres argumentos de configuración que se pueden usar con SEARCH_NGRAMS:

  • Los tamaños mínimo y máximo para los n-gramas se especifican con las funciones TOKENIZE_SUBSTRING o TOKENIZE_NGRAMS. No recomendamos los n-gramas de un solo carácter porque podrían coincidir con una gran cantidad de documentos. Por otro lado, los n-gramas largos hacen que SEARCH_NGRAMS no detecte palabras cortas con errores ortográficos.
  • Es la cantidad mínima de n-gramas que SEARCH_NGRAMS debe coincidir (se establece con los argumentos min_ngrams y min_ngrams_percent en SEARCH_NGRAMS). Por lo general, los números más altos hacen que la búsqueda sea más rápida, pero reducen la recuperación.

Para lograr un buen equilibrio entre el rendimiento y la recuperación, puedes configurar estos argumentos para que se ajusten a la consulta y la carga de trabajo específicas.

También recomendamos incluir un LIMIT interno para evitar crear consultas muy costosas cuando se encuentra una combinación de n-gramas populares.

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

En este ejemplo, se usan spanner.score_ngrams y spanner.search_ngrams. El parámetro de búsqueda $1 está vinculado a "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

Comparación entre la búsqueda parcial basada en n-gramas y el modo de búsqueda mejorado

Junto con la búsqueda parcial basada en n-gramas, el modo de búsqueda mejorado también controla algunas palabras con errores ortográficos. Por lo tanto, hay cierta superposición entre las dos funciones. En la siguiente tabla, se resumen las diferencias:

Búsqueda parcial basada en n-gramas Modo de búsqueda mejorado
Costo Requiere una tokenización de subcadenas más costosa basada en n-gramas. Requiere una tokenización de texto completo menos costosa
Tipos de búsquedas Funciona bien con documentos cortos con pocas palabras, como el nombre de una persona, el nombre de una ciudad o el nombre de un producto. Funciona igual de bien con documentos y búsquedas de cualquier tamaño.
Búsqueda de palabras parciales Realiza una búsqueda de subcadena que permite errores ortográficos. Solo admite la búsqueda de palabras completas (SEARCH_SUBSTRING no admite el argumento enhance_query).
Palabras con errores ortográficos Admite palabras mal escritas en el índice o la búsqueda Solo admite palabras mal escritas en la búsqueda.
Correcciones Encuentra cualquier coincidencia con errores ortográficos, incluso si la coincidencia no es una palabra real. Corrige errores ortográficos de palabras comunes y conocidas

Realiza una búsqueda fonética con Soundex

Spanner proporciona la función SOUNDEX para encontrar palabras que se escriben de manera diferente, pero suenan igual. Por ejemplo, SOUNDEX("steven"), SOUNDEX("stephen") y SOUNDEX("stefan") son todos "s315", mientras que SOUNDEX("stella") es "s340". SOUNDEX distingue mayúsculas de minúsculas y solo funciona con alfabetos basados en el latín.

La búsqueda fonética con SOUNDEX se puede implementar con una columna generada y un índice de búsqueda, como se muestra en el siguiente ejemplo:

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

En este ejemplo, se usa 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 siguiente búsqueda hace coincidir "stefan" con "Steven" en SOUNDEX, junto con AlbumTitle que contiene "cat":

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

¿Qué sigue?