Un trigram es un grupo de tres caracteres consecutivos tomados de una cadena. Podemos medir la similitud de dos cadenas contando el número de trigramas que comparten. Esta idea tan sencilla resulta ser muy eficaz para medir la similitud de palabras en muchos idiomas naturales.

Las funciones proporcionadas por el módulo pg_trgm se muestran en la Table F.26, y los operadores en la Table F.27.

Considera el siguiente ejemplo:

# SELECT word_similarity('word', 'two words');
 word_similarity
-----------------
             0.8
(1 row)

En la primera cadena, el conjunto de trigramas es {" w"," wo","wor","ord","rd "}. En la segunda cadena, el conjunto ordenado de trigramas es {" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}. La extensión más similar de un conjunto ordenado de trigramas en la segunda cadena es {" w"," wo","wor","ord"}, y la similitud es 0.8.

Esta función devuelve un valor que se puede entender aproximadamente como la mayor similitud entre la primera cadena y cualquier subcadena de la segunda cadena. Sin embargo, esta función no añade relleno a los límites de la extensión. Por lo tanto, no se considera la cantidad de caracteres adicionales presentes en la segunda cadena, excepto por los límites de las palabras que no coinciden.

Al mismo tiempo, strict_word_similarity selecciona una extensión de palabras en la segunda cadena. En el ejemplo anterior, strict_word_similarity seleccionaría la extensión de una sola palabra 'words', cuyo conjunto de trigramas es {" w"," wo","wor","ord","rds","ds "}.

# SELECT strict_word_similarity('word', 'two words'), similarity('word', 'words');
 strict_word_similarity | similarity
------------------------+------------
               0.571429 |   0.571429
(1 row)

Por lo tanto, la función strict_word_similarity es útil para encontrar la similitud con palabras completas, mientras que word_similarity es más adecuada para encontrar la similitud para partes de palabras.

El módulo pg_trgm proporciona clases de operadores de índices GiST y GIN que te permiten crear un índice sobre una columna de tipo text con el fin de realizar búsquedas de similitud muy rápidas. Estos tipos de índices admiten los operadores de similitud descritos anteriormente y, adicionalmente, admiten búsquedas de índices basadas en trigramas para consultas LIKE, ILIKE, ~, ~* y =. Las comparaciones de similitud no distinguen entre mayúsculas y minúsculas en una compilación por defecto de pg_trgm. Los operadores de desigualdad no están admitidos. Ten en cuenta que estos índices pueden no ser tan eficientes como los índices B-tree ordinarios para el operador de igualdad.

Ejemplo:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

o

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

La clase de operadores GiST gist_trgm_ops aproxima un conjunto de trigramas como una firma de mapa de bits (bitmap signature). Su parámetro entero opcional siglen determina la longitud de la firma en bytes. La longitud por defecto es 12 bytes. Los valores válidos de la longitud de la firma están entre 1 y 2024 bytes. Las firmas más largas conducen a una búsqueda más precisa (escaneando una fracción más pequeña del índice y menos páginas de heap), a costa de un índice de mayor tamaño.

Ejemplo de creación de este tipo de índice con una longitud de firma de 32 bytes:

CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));

A partir de este momento, tendrás un índice en la columna t que puedes usar para búsquedas de similitud. Una consulta típica es:

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

Esto devolverá todos los valores en la columna de texto que sean lo suficientemente similares a word, ordenados del mejor resultado al peor. El índice se utilizará para que esta sea una operación rápida incluso sobre conjuntos de datos muy grandes.

Una variante de la consulta anterior es:

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Esto puede implementarse de manera bastante eficiente mediante índices GiST, pero no con índices GIN. Generalmente superará a la primera formulación cuando solo se desee un número pequeño de las coincidencias más cercanas.

También puedes usar un índice en la columna t para similitud de palabras o similitud estricta de palabras. Las consultas típicas son:

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <% t
  ORDER BY sml DESC, t;

y

SELECT t, strict_word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <<% t
  ORDER BY sml DESC, t;

Esto devolverá todos los valores en la columna de texto para los cuales existe una extensión continua en el conjunto de trigramas ordenados correspondiente que es lo suficientemente similar al conjunto de trigramas de word, ordenados del mejor resultado al peor. El índice se utilizará para hacer de esta una operación rápida incluso sobre conjuntos de datos muy grandes.

Las posibles variantes de las consultas anteriores son:

SELECT t, 'word' <<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

y

SELECT t, 'word' <<<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

Esto puede implementarse de manera bastante eficiente mediante índices GiST, pero no con índices GIN.

A partir de PostgreSQL 9.1, estos tipos de índices también admiten búsquedas de índices para LIKE y ILIKE, por ejemplo:

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

La búsqueda del índice funciona extrayendo trigramas de la cadena de búsqueda y luego buscándolos en el índice. Cuantos más trigramas haya en la cadena de búsqueda, más eficaz será la búsqueda del índice. A diferencia de las búsquedas basadas en B-tree, la cadena de búsqueda no necesita estar anclada a la izquierda.

A partir de PostgreSQL 9.3, estos tipos de índices también admiten búsquedas de índices para coincidencias de expresiones regulares (operadores ~ y ~*), por ejemplo:

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

La búsqueda del índice funciona extrayendo trigramas de la expresión regular y luego buscándolos en el índice. Cuantos más trigramas se puedan extraer de la expresión regular, más eficaz será la búsqueda del índice. A diferencia de las búsquedas basadas en B-tree, la cadena de búsqueda no necesita estar anclada a la izquierda.

Tanto para las búsquedas con LIKE como con expresiones regulares, ten en cuenta que un patrón sin trigramas extraíbles degenerará en un escaneo completo del índice.

La elección entre la indexación GiST y GIN depende de las características de rendimiento relativas de GiST y GIN, que se discuten en otra parte de la documentación.

La coincidencia de trigramas es una herramienta muy útil cuando se utiliza en conjunción con un índice de texto completo (full text index). En particular, puede ayudar a reconocer palabras de entrada mal escritas que no coincidirán directamente con el mecanismo de búsqueda de texto completo.

El primer paso es generar una tabla auxiliar que contenga todas las palabras únicas de los documentos:

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

donde documents is una tabla que tiene un campo de texto bodytext que deseamos buscar. La razón para usar la configuración simple con la función to_tsvector, en lugar de usar una configuración específica de idioma, es que queremos una lista de las palabras originales (sin derivar / unstemmed).

A continuación, crea un índice de trigramas en la columna de palabras:

CREATE INDEX words_idx ON words USING GIN (word gin_trgm_ops);

Ahora, se puede utilizar una consulta SELECT similar al ejemplo anterior para sugerir correcciones ortográficas para palabras mal escritas en los términos de búsqueda del usuario. Una prueba adicional útil es requerir que las palabras seleccionadas tengan también una longitud similar a la de la palabra mal escrita.

Sitio de desarrollo de GiST: http://www.sai.msu.su/~megera/postgres/gist/

Sitio de desarrollo de Tsearch2: http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

Oleg Bartunov <[email protected]>, Moscú, Universidad de Moscú, Rusia

Teodor Sigaev <[email protected]>, Moscú, Delta-Soft Ltd., Rusia

Alexander Korotkov <[email protected]>, Moscú, Postgres Professional, Rusia

Documentación: Christopher Kings-Lynne

Este módulo está patrocinado por Delta-Soft Ltd., Moscú, Rusia.