stringtranslate.com

Búsqueda de trigramas

La búsqueda de trigramas es un método de búsqueda de texto cuando no se conoce con precisión la sintaxis o la ortografía exacta del objeto de destino [1] o cuando las consultas pueden ser expresiones regulares . [2] Encuentra objetos que coinciden con el número máximo de tres cadenas de caracteres consecutivas (es decir, trigramas ) en los términos de búsqueda ingresados, que generalmente son coincidencias cercanas. [3] Se puede esperar que dos cadenas con muchos trigramas compartidos sean muy similares. [4] Los trigramas también permiten crear de manera eficiente índices de motores de búsqueda para búsquedas que son expresiones regulares o coinciden con el texto de manera inexacta. Los índices pueden acelerar significativamente las búsquedas. [5] [6] Se puede especificar un umbral para el número de coincidencias de trigramas como punto de corte, después de que un resultado no coincida. [4]

El uso de trigramas para acelerar búsquedas es una técnica utilizada en algunos sistemas de búsqueda de código , en situaciones en las que pueden resultar útiles consultas que sean expresiones regulares, [5] [2] [7] en motores de búsqueda como Elasticsearch , [8] así como en bases de datos como PostgreSQL . [4]

Ejemplos

Considere la cadena "alice". Los trigramas de la cadena serían "ali", "lic" y "ice", sin incluir los espacios. [5] La búsqueda de esta cadena en una base de datos con un índice basado en trigramas implicaría encontrar qué objetos contienen la mayor cantidad posible de los tres trigramas.

Como ejemplo concreto del uso de la búsqueda de trigramas para buscar una consulta de expresión regular, considere la búsqueda de la cadena ab[cd]e, donde los corchetes indican que el tercer carácter en la cadena que se busca podría ser co d. En esta situación, se podría consultar el índice para objetos que tengan los dos trigramas abcy bceo los dos trigramas abdy bde. Por lo tanto, encontrar esta consulta no implicaría ninguna coincidencia de cadena , y podría simplemente consultar el índice directamente, lo que puede ser más rápido en la práctica. [2]

Véase también

Referencias

  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 eficientemente ciertos tipos de datos económicos y considera que esta técnica es particularmente útil cuando los usuarios del sistema tienen poco contexto para la estructura de los datos.
  2. ^ abc 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. Número de identificación del sujeto  16701550.
  4. ^ abc "F.33. pg_trgm". Documentación de PostgreSQL . 2022-05-12 . Consultado el 2022-05-28 .
  5. ^ abc "Búsqueda rápida con índices de texto de trigramas de PostgreSQL". GitLab . 2016-03-18 . Consultado el 2022-05-28 .
  6. ^ Zobel, Justin; Moffat, Alistair; Sacks-Davis, Ron (1993). "Búsqueda de términos parcialmente especificados en léxicos de gran tamaño mediante archivos comprimidos invertidos" (PDF) . Conferencia sobre bases de datos de gran tamaño (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 de 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 exitosos obtenidos con el uso de este estilo de búsqueda.
  7. ^ "Big Grep". resources.sei.cmu.edu . Consultado el 12 de junio de 2022 .También se denomina 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 .