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. Las búsquedas aproximadas encuentran documentos coincidentes a pesar de las pequeñas diferencias entre la consulta 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 la búsqueda de subcadenas. La configuración del tokenizador es importante, ya que afecta a la calidad y al rendimiento de la búsqueda. En el siguiente ejemplo se muestra cómo crear una consulta 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 consulta busca los álbumes cuyos títulos sean los más parecidos 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

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

La consulta de ejemplo de la sección anterior busca en dos fases, usando dos funciones diferentes:

  1. SEARCH_NGRAMS busca todos los álbumes candidatos que tengan n-gramas compartidos con la consulta de búsqueda. Por ejemplo, los n-gramas de tres caracteres de "California" incluyen [cal, ali, lif, ifo, for, orn, rni, nia], y los de "Kaliphorn", [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 tengan 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 relación entre los n-gramas compartidos distintos y los n-gramas no compartidos distintos:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Normalmente, la consulta de 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 de los n-gramas se especifican con las funciones TOKENIZE_SUBSTRING(/spanner/docs/reference/standard-sql/search_functions#tokenize_substring) o TOKENIZE_NGRAMS. No recomendamos usar n-gramas de un carácter porque podrían coincidir con un número muy elevado de documentos. Por otro lado, los n-gramas largos provocan que SEARCH_NGRAMS no detecte palabras cortas mal escritas.
  • Número mínimo de n-gramas que debe coincidir con SEARCH_NGRAMS (se define con los argumentos min_ngrams y min_ngrams_percent en SEARCH_NGRAMS). Los números más altos suelen acelerar la consulta, pero reducen la recuperación.

Para conseguir 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 encuentre 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 usa el parámetro de consulta $1, que 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

Búsqueda aproximada basada en n-gramas frente al modo de consulta mejorado

Además de la búsqueda aproximada basada en n-gramas, el modo de consulta mejorado también gestiona algunas palabras mal escritas. Por lo tanto, hay cierta superposición entre las dos funciones. En la siguiente tabla se resumen las diferencias:

Búsqueda aproximada basada en n-gramas Modo de consulta mejorado
Coste Requiere una tokenización de subcadenas más cara basada en n-gramas. Requiere una tokenización de texto completo menos costosa
Tipos de consultas de búsqueda Funciona bien con documentos cortos con pocas palabras, como nombres de personas, ciudades o productos Funciona igual de bien con documentos y consultas de búsqueda de cualquier tamaño
Búsqueda de palabras parciales Realiza una búsqueda de una subcadena que permite errores ortográficos. Solo admite búsquedas de palabras completas (SEARCH_SUBSTRING no admite el argumento enhance_query)
Palabras con errores ortográficos Admite palabras con errores ortográficos en el índice o en la consulta Solo admite palabras con errores ortográficos en la consulta
Correcciones Busca cualquier coincidencia con errores ortográficos, aunque no sea una palabra real. Corrige los errores ortográficos de palabras comunes y conocidas

Hacer una búsqueda fonética con Soundex

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

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 consulta relaciona "stefan" con "Steven" en SOUNDEX, así como 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')

Siguientes pasos