Búsqueda dinámica y visualización.

Question

Tengo una gran carga de documentos, archivos de texto, que quiero buscar contenido relevante. He visto una herramienta de búsqueda, no recuerdo dónde, que implementó un buen método como lo describo en mi requisito a continuación.

Mi requisito es el siguiente:

• Necesito una función de búsqueda optimizada: Suministro a esta función de búsqueda con una lista (una o más) de palabras parcialmente completas (o completas) separadas por espacios.
• La función luego encuentra todos los documentos que contienen palabras que comienzan o son iguales a la primera palabra, luego busca estos documentos encontrados de la misma manera usando la segunda palabra, y así sucesivamente, al final de los cuales devuelve una lista que contiene el texto real palabras encontradas vinculadas con los documentos (nombre y ubicación) que los contienen, para completar la lista de palabras.
• Los documentos deben contener todos las palabras en la lista.
• Quiero usar esta función para realizar una búsqueda a medida que se escribe para poder mostrar y actualizar los resultados en una estructura similar a un árbol en tiempo real.

Un posible enfoque para una solución que se me ocurrió es el siguiente: Creo una base de datos (lo más probable es que use mysql) con tres tablas: 'Documentos', 'Palabras' y 'Word_Docs'.

• 'Documentos' tendrá (idDoc, Nombre, Ubicación) de todos los documentos.
• 'Palabras' tendrá (idWord, Word), y será una lista de palabras únicas de todos los documentos (una palabra específica aparece solo una vez).
• 'Word_Docs' tendrá (idWord, idDoc), y será una lista de combinaciones de identificación únicas para cada palabra y documento en el que aparezca.

La función se llama con el contenido de un cuadro de edición en cada pulsación de tecla (excepto el espacio):

• la cadena está tokenizada
• (aquí mis ruedas giran un poco): estoy seguro de que se puede construir una sola instrucción SQL para devolver el conjunto de datos requerido: (actual_words, doc_name, doc_location); (No soy un número activo con SQL), ¿alternativamente una secuencia de llamadas para cada token y analizar los idDocs que no se repiten?
• luego se devuelve este conjunto de datos (/ list / array)

Luego se muestra el contenido de la lista devuelta:

por ejemplo: llamado con: " seq sta cod " muestra:

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(y así sucesivamente)

¿Es esta una forma óptima de hacerlo? La función debe ser rápida, o debe ser llamada solo cuando se toca un espacio? ¿Debería ofrecer la terminación de palabras? (Obtuve las palabras en la base de datos) Al menos esto evitaría llamadas inútiles a la función para palabras que no existen. Si se completa la palabra: ¿cómo se implementaría?

(¿Quizás SO también podría usar este tipo de solución de búsqueda para explorar las etiquetas? (en la esquina superior derecha de la página principal))

Answer 1

Lo que estás hablando se conoce como un índice invertido o lista de publicación, y Funciona de manera similar a lo que propones y lo que propone Mecki. Hay mucha literatura sobre índices invertidos ahí fuera; El artículo de Wikipedia es un buen lugar para comenzar.

Mejor, en lugar de intentar compilarlo usted mismo, use una implementación de índice invertido existente. Tanto MySQL como las versiones recientes de PostgreSQL tienen indexación de texto completo de forma predeterminada. También puede consultar Lucene para obtener una solución independiente. Hay muchas cosas a considerar al escribir un índice invertido bueno , incluyendo tokenización, derivación, consultas de varias palabras, etc., etc., y una solución precompilada hará todo esto por usted.

Answer 2

La forma más rápida es sin utilizar una base de datos, ya que si realiza la búsqueda manualmente con datos optimizados, puede superar fácilmente el rendimiento de búsqueda seleccionado. La forma más rápida, suponiendo que los documentos no cambien muy a menudo, es crear archivos de índice y usarlos para encontrar las palabras clave. El archivo de índice se crea así:

1. Encuentra todas las palabras únicas en el archivo de texto. Eso es dividir el archivo de texto por espacios en palabras y agregar cada palabra a una lista a menos que ya se encuentre en esa lista.

2. Tome todas las palabras que haya encontrado y ordénelas alfabéticamente; La forma más rápida de hacerlo es utilizar Three-Way Radix QuickSort . Este algoritmo es difícil de superar en rendimiento al ordenar cadenas.

3. Escriba la lista ordenada en el disco, una palabra por línea.

4. Cuando ahora desee buscar en el archivo de documento, ignórelo por completo, en su lugar, cargue el archivo de índice en la memoria y utilice la búsqueda binaria para averiguar si una palabra está en el archivo de índice o no. La búsqueda binaria es difícil de superar cuando se buscan listas grandes ordenadas.

Alternativamente, puede combinar el paso (1) y el paso (2) dentro de un solo paso. Si usa InsertionSort (que utiliza la búsqueda binaria para encontrar la posición de inserción correcta para insertar un nuevo elemento en una lista ya ordenada), no solo tiene un algoritmo rápido para averiguar si la palabra ya está en la lista o no, en el caso no lo es, inmediatamente obtienes la posición correcta para insertarlo y si siempre insertas una nueva así, automáticamente tendrás una lista ordenada cuando llegues al paso (3).

El problema es que necesita actualizar el índice cada vez que cambia el documento ... sin embargo, ¿no sería esto también cierto para la solución de base de datos? Por otro lado, la solución de base de datos le ofrece algunas ventajas: puede usarla, incluso si los documentos contienen tantas palabras, que los archivos de índice ya no cabrían en la memoria (es poco probable, ya que incluso una lista de todas las palabras en inglés encajar en la memoria de cualquier PC de usuario promedio); sin embargo, si necesita cargar archivos de índice de una gran cantidad de documentos, entonces la memoria puede convertirse en un problema. De acuerdo, puede solucionarlo utilizando trucos inteligentes (por ejemplo, buscar directamente dentro de los archivos que asignó a la memoria usando mmap y así sucesivamente), pero estos son los mismos trucos que las bases de datos ya utilizan para realizar búsquedas rápidas. ¿la rueda? Además, también puede evitar problemas de bloqueo entre la búsqueda de palabras y la actualización de índices cuando un documento ha cambiado (es decir, si la base de datos puede realizar el bloqueo por usted o puede realizar la actualización o las actualizaciones como una operación atómica). Para una solución web con llamadas AJAX para actualizaciones de listas, el uso de una base de datos es probablemente la mejor solución (mi primera solución es bastante adecuada si se trata de una aplicación que se ejecuta localmente y está escrita en un lenguaje de bajo nivel como C).

Si tiene ganas de hacerlo todo en una sola llamada de selección (lo que podría no ser óptimo, pero cuando actualiza dinámicamente el contenido web con AJAX, por lo general se presenta como la solución que causa menos dolores de cabeza), debe UNIRSE a las tres tablas juntos. Mayo SQL está un poco oxidado, pero lo intentaré:

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

Bueno, quizás esta no sea la selección más rápida ... Supongo que se puede hacer más rápido. De todos modos, encontrará todos los documentos coincidentes que contengan al menos una palabra, luego agrupará todos los documentos iguales por ID, contará cuántos se han agrupado en togetehr y, finalmente, solo mostrará resultados donde NumOfHits (el número de palabras encontradas de la declaración IN) es igual al número de palabras dentro de la instrucción IN (si busca 10 palabras, X es 10).

Answer 3

No estoy seguro acerca de la sintaxis (esta es la sintaxis del servidor SQL), pero:

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

Es decir, sin usar like. Con cosas similares son MUCHO más complejas.

Answer 4

Google Desktop Search o una herramienta similar podría cumplir con sus requisitos.