Básicamente, hay dos técnicas utilizadas para la búsqueda de texto completo sobre grandes corpúsculos: listas de publicación y matrices de sufijos.
Una lista de publicación es una lista de pares (term, document_id), opcionalmente con una posición en el documento. Si lo ordena o lo clasifica por término, tiene un índice de texto completo que puede buscarse de manera eficiente.
Existen varias técnicas para hacer que las listas de publicaciones sean más pequeñas, de acceso más rápido, más rápidas de actualizar y más flexibles, algunas a costa de la precisión. Lucene es probablemente el mejor indexador de textos basado en la lista de publicaciones disponible en la actualidad, y (a diferencia de su comentario anterior) puede indexar el texto encontrado en archivos PDF, Microsoft Word, etc. El Lucene.net project vinculado por Thomas Maierhofer parece un puerto bastante razonable, aunque, por supuesto, siempre estarás un poco a la vanguardia de lo que está sucediendo en la versión de Java.
Para un corpus que es mucho más grande que la memoria, prácticamente tiene que almacenar la lista de publicaciones en el disco. Esto dificulta el uso de un simple árbol de búsqueda binaria para acceder a él: si tiene cien mil documentos de diez mil palabras cada uno, tiene mil millones de publicaciones, lo que significa que su árbol de búsqueda binaria tiene una profundidad mínima de 30. El problema es que que los 30 nodos en la ruta desde la raíz del árbol a la hoja, en general, se ubicarán en diferentes partes de su disco, por lo que el disco debe buscar 30 veces para encontrar las publicaciones para un término. Eso es aproximadamente 2½ segundos, que es prohibitivamente lento.
Sin embargo, hay una versión modificada de la estructura de datos del árbol binario llamada "B-tree" que puede trabajar. Lucene usa una estructura de datos simple que se parece mucho a un árbol B, pero admite actualizaciones masivas de forma mucho más sencilla. Escribí una versión muy simple de esta misma estructura de datos en mi propio dumbfts project, que implementa un motor de búsqueda de texto completo para mi correo electrónico en algunas páginas de Python. Lo uso todos los días, es software libre, y funciona bastante bien para lo que lo uso, pero no es exactamente un sistema de búsqueda de clase mundial como Lucene.
Como ejemplo de hacer que las listas de publicaciones sean más pequeñas a costa de la precisión, el libro Managing Gigabytes (y el mg4j project) tiene una estructura de datos llamada "tabla hash perfecta mínima firmada", que en realidad no almacena los términos fueron indexados, solo hashes de ellos. Entonces, hay una pequeña probabilidad de un falso positivo: tienes que recuperar los documentos que supuestamente contienen el término para confirmar que realmente lo hacen.
Los arreglos de sufijo, que son una versión mucho más compacta y ligeramente más lenta de radix trees (aka tries), son implementados por GLIMPSE y algunos otros programas, pero básicamente han caído en desuso en estos días. Tienen cierta flexibilidad que no está presente en la estructura de datos de la lista de publicación; permiten búsquedas de expresiones regulares y búsquedas con errores ortográficos, por ejemplo, pero no son tan rápidos. Ha habido algunos trabajos recientes con Burrows-Wheeler Transform, que se basa en matrices de sufijos, y proporciona un algoritmo de compresión en el que el archivo comprimido es ¡el índice de texto completo! La versión mejor documentada de esto se llama FM-index, aunque he oído que hay versiones anteriores de la técnica, tal vez no publicadas.Sin embargo, a diferencia de las otras técnicas descritas anteriormente, creo que esto no funciona cuando los documentos son archivos PDF o algo así. Todavía puedes usar el mismo enfoque de extraer una versión de texto de cada página e indexar eso, pero no lo haces. No obtenga el beneficio de comprimir el documento original.
Mi conocido Tim escribió una muy buena serie introductoria de publicaciones en el blog on search en 2003, que todavía son geniales. Cubren estas cosas (a excepción de los desarrollos recientes) con mucha más profundidad.
Ravi: ¿Este es el tipo de información que estás buscando?
Edit: gracias por arreglar mi formateo, Martin!
Antes que nada, ¿hay alguna razón por la que tiene que construir la suya propia? Hay buenos proyectos de código abierto como Lucene (y NLucene para .NET) que tienen incorporada mucha de esta funcionalidad. A menos que tengas que construir desde cero, utilizaría esta. Incluso si lo hace, comenzaría con la fuente de un proyecto como este. Realmente no hay solo una mejor técnica de búsqueda. Hay una bolsa entera de ellos basada en el contenido y para lo que buscas. Por favor, danos más detalles. –
@ Anthony Gracias Anthony.Sé que hay buenos proyectos de código abierto disponibles para implementar aplicaciones de búsqueda. Pero puede suponer que quiero construirlo desde cero. Sin una razón específica. Y como pregunté antes, me preguntaba, ¿puede ser útil el uso de árboles de búsqueda binarios? Lo digo porque lo leí en algún lado hace mucho tiempo y olvidé el concepto. Veamos si alguien ayuda. –
No creo que pueda obtener una respuesta mejor porque todas las técnicas de búsqueda, incluidas Windows Search 4.0, Google Desktop Search, etc. utilizan indexación internamente y usan árboles B + y se utilizan principalmente para indexar en todas las bases de datos existentes actualmente en el mercado. Y, sinceramente, aparte de la indexación, no existe un método más rápido y el rendimiento de la indexación depende del algoritmo que elija. –