Hispanopedia Wiki
Articulo de referencia

Trigram search

Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known [ 1 ] or when queries may be regular expressions ....

Hispanopedia WikiContenido en espanolLectura gratuita

Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known[1] or when queries may be regular expressions.[2] It finds objects which have the most matches against three-character substrings (i.e. trigrams) of the search terms, which are generally near matches.[3] Two strings with many shared trigrams can be expected to be very similar.[4] Trigrams also allow for efficiently creating search engine indexes for searches that are regular expressions or match the text inexactly. Indexes can significantly accelerate searches.[5][6] A threshold for number of trigram matches can be specified as a cutoff point, after a result is unmatched.[4]

Using trigrams for accelerating searches is a technique used in some systems for code searching, in situations in which queries that are regular expressions may be useful,[5][2][7] in search engines such as Elasticsearch,[8] as well as in databases such as PostgreSQL.[4]

Examples

Consider the string "alice". The trigrams of the string would be "ali", "lic", and "ice", not including spaces.[5] Searching for this string in a database with a trigram-based index would involve finding which objects contain as many of the three trigrams as possible.

As a concrete example of using trigram search to search for a regular expression query, consider searching for the string ab[cd]e, where the brackets denote that the third character in the string being searched for could be c or d. In this situation, one could query the index for objects that have the two trigrams abc and bce or the two trigrams abd and bde. Thus, finding this query would involve no string matching, and could just query the index directly, which can be faster in practice.[2]

See also

References

  1. ↑ Hardarson, Omar (1997). "Codificación interactiva de la actividad económica mediante búsqueda de trigramas en BLAISE III" (PDF) . Grupo Internacional de Usuarios de Blaise .Nota: Este artículo analiza la búsqueda de trigramas como una forma de codificar de manera eficiente ciertos tipos de datos económicos, y concluye que esta técnica es particularmente útil cuando los usuarios del sistema tienen poco contexto sobre la estructura de los datos.
  2. 1 2 3 Cox, Russ (enero de 2012). "Coincidencia de expresiones regulares con un índice de trigramas o cómo funcionaba la búsqueda de código de Google" .
  3. ↑ Adams, Elizabeth; Meltzer, Arnold (1 de marzo de 1993). «Trigramas como elemento de índice en la recuperación de texto completo: observaciones y resultados experimentales» . Actas de la conferencia ACM de 1993 sobre informática - CSC '93 . págs. 433–439 . doi : 10.1145/170791.170891 . ISBN  0897915585. S2CID 16701550 . 
  4. 1 2 3 "F.33. pg_trgm" . Documentación de PostgreSQL . 12/05/2022 . Consultado el 28/05/2022 .
  5. 1 2 3 "Búsqueda rápida mediante índices de texto de trigramas de PostgreSQL" . GitLab . 18 de marzo de 2016. Consultado el 28 de mayo de 2022 .
  6. ↑ Zobel, Justin; Moffat, Alistair; Sacks-Davis, Ron (1993). "Búsqueda de términos parcialmente especificados en grandes léxicos mediante archivos invertidos comprimidos" (PDF) . Conferencia sobre bases de datos muy grandes (VLDB) .Nota: Este artículo de investigación no utiliza el término "búsqueda de trigramas", pero parece ser el primer ejemplo en la literatura del uso de n-gramas como índices, y se cita en el artículo de Russ Cox como el primer ejemplo de la estructura de un índice inverso basado en trigramas. El artículo también cita resultados de rendimiento satisfactorios obtenidos con este tipo de búsqueda.
  7. ↑ "Big Grep" . resources.sei.cmu.edu . 11 de agosto de 2017. Consultado el 12 de junio de 2022 .También llamado BigGrep. Utiliza n-gramas (no siempre 3),
  8. ↑ "Tokenizador de N-gramas | Guía de Elasticsearch [ 8.2 ] | Elastic" . www.elastic.co . Consultado el 28 de mayo de 2022 .