c++ - indice - fulltext mysql

Crear y usar el índice de búsqueda de texto completo HTML(C++)

Question

Necesito crear un índice de búsqueda para una colección de páginas HTML.

No tengo experiencia en la implementación de un índice de búsqueda, así que cualquier información general sobre cómo crear uno, qué información almacenar, cómo implementar búsquedas avanzadas como "frase completa", clasificación de resultados, etc.

No tengo miedo de construirlo yo mismo, aunque me gustaría utilizar nuevamente un componente existente (o usar uno para comenzar con un prototipo). Estoy buscando una solución accesible desde C ++, preferiblemente sin requerir instalaciones adicionales en tiempo de ejecución. El contenido es estático (por lo que tiene sentido agregar información de búsqueda), pero una búsqueda puede tener que acumular resultados de múltiples repositorios.

Sin embargo, puedo hacer algunas conjeturas: crear una word ==> pages mapa word ==> pages para todas las palabras (relevantes), se puede asignar un rango al mapeo por prominencia (h1> h2> ...> <p> ) y proximidad hasta arriba. Además, se podrían construir búsquedas avanzadas: buscar la frase "homo sapiens" podría enumerar todas las páginas que contengan "homo" y "sapiens" , luego escanear todas las páginas devueltas para las ubicaciones donde ocurren juntas. Sin embargo, hay una gran cantidad de escenarios problemáticos y preguntas sin respuesta, por lo que estoy buscando referencias sobre lo que debería ser una gran cantidad de trabajo existente que de alguna manera escapa a mi google-fu.

[editar por generosidad]
El mejor recurso que encontré hasta ahora es este y los enlaces desde allí. Tengo una hoja de ruta de implementación para un sistema experimental, sin embargo, todavía estoy buscando:

• Material de referencia sobre la creación del índice y pasos individuales
• implementaciones disponibles de pasos individuales
• implementaciones reutilizables (con las restricciones ambientales anteriores)

Answer 1

Atacaría esto con una pequeña base de datos sqlite. Podría tener tablas para ''página'', ''término'' y ''término de página''. ''Page'' tendría columnas como id, text, title y url. ''Término'' tendría una columna que contiene una palabra, así como la ID principal. ''Término de página'' tendría claves externas a una ID de página y una ID de término, y también podría almacenar el peso, calculado a partir de la distancia desde la parte superior y el número de apariciones (o lo que quieras).

Quizás una forma más eficiente sería tener solo dos tablas: ''página'' como antes, y ''término de página'' que tendría la identificación de la página, el peso y un hash de la palabra del término.

Una consulta de ejemplo: desea buscar "foo". Has hash "foo", luego consulta todas las filas de términos de página que tienen ese hash de términos. Clasifique por peso descendente y muestre los diez primeros resultados.

Creo que esto debería ser razonablemente rápido, aunque obviamente depende del número y el tamaño de las páginas en cuestión. Sqlite no es difícil de agrupar y no debería necesitar una instalación adicional.

Answer 2

Las páginas de clasificación es realmente complicado aquí. Con una gran muestra de páginas, puedes usar enlaces bastante para calcular los rangos. De otro modo, debe comprobar cómo se colocan las palabras, y también asegurarse de que su motor no se deje engañar por las páginas de ''diccionario''.

¡Buena suerte!

Answer 3

Dependiendo del tamaño y número de páginas estáticas, es posible que desee ver una solución de búsqueda ya existente.

"¿Cómo se implementa la búsqueda de texto completo para esa tabla de más de 10 millones de filas, mantenerse al día con la carga y mantenerse relevante? Sphinx es bueno en ese tipo de acertijos".

Yo elegiría el motor Sphinx para full text searching . La licencia es GPL pero también tiene una versión commercial disponible. Está destinado a ejecutarse de forma autónoma [2] , pero también puede integrarse en las aplicaciones extrayendo la funcionalidad necesaria (ya sea indexing [1] , searching [3] , stemming , etc.).

Los datos deberían obtenerse analizando los archivos HTML entrada y transformándolos en plain-text usando un analizador sintáctico como el analizador HTML de libxml2 (no lo he usado, pero dicen que puede analizar incluso el HTML con formato incorrecto). Si no está obligado a C/C++ puede echar un vistazo a Beautiful Soup .

Después de obtener los textos sin formato, puede almacenarlos en una base de datos como MySQL o PostgreSQL . Si desea mantener todo incrustado, debe ir con sqlite .

Tenga en cuenta que Sphinx no funciona de sqlite con sqlite , pero hay un intento de agregar soporte ( sphinx-sqlite3 ).

Answer 4

Este proceso generalmente se conoce como recuperación de información . Probablemente encontrará útil este libro en línea .

Bibliotecas existentes

Aquí hay dos soluciones existentes que se pueden integrar completamente en una aplicación sin requerir un proceso separado (creo que ambas compilarán con VC ++).

Xapian es maduro y puede hacer mucho de lo que necesita, desde la indexación hasta la recuperación clasificada. Se requeriría un análisis HTML separado porque, AFAIK, no analiza el html (tiene un programa complementario Omega , que es una interfaz para indexar sitios web).

Lucene es un índice / búsqueda de la biblioteca Apache en Java, con una versión oficial prelanzamiento C lucy , y una versión no oficial C ++ versión CLucene .

Implementando la recuperación de información

Si las opciones anteriores no son viables por alguna razón, aquí hay información sobre los pasos individuales de creación y uso de un índice. Las soluciones personalizadas pueden ir de simples a muy sofisticadas, dependiendo de lo que necesite para su aplicación. Rompí el proceso en 5 pasos

1. Procesamiento de HTML
2. Procesamiento de texto
3. Indexación
4. Recuperación
5. Clasificación

Procesamiento de HTML

Aquí hay dos enfoques

• Stripping La página a la que se refiere discute una técnica generalmente conocida como stripping, que implica eliminar todos los elementos html que no se mostrarán y traducir otros a su forma de visualización. Personalmente, preprocesaré el uso de Perl e indexaré los archivos de texto resultantes. Pero para una solución integrada, particularmente una en la que desee registrar etiquetas de significación (por ejemplo, <h1>, <h2>), es probable que desee imitar la suya. Aquí hay una implementación parcial de una rutina de eliminación de C ++ (aparece en Thinking in C ++ , versión final del libro aquí ), desde la cual se puede construir.

• Análisis Un nivel más alto en complejidad que el de extracción es el análisis html, lo que ayudaría en su caso a registrar etiquetas de significancia. Sin embargo, un buen analizador HTML C ++ es difícil de encontrar . Algunas opciones pueden ser htmlcxx (nunca lo usó, pero está activo y parece prometedor) o hubbub (biblioteca C, parte de NetSurf, pero dice que es portátil).

  Si está tratando con XHTML o está dispuesto a usar un convertidor HTML a XML, puede usar uno de los muchos analizadores XML disponibles. Pero, de nuevo, los convertidores HTML a XML son difíciles de encontrar, el único que conozco es HTML Tidy . Además de la conversión a XHTML, su objetivo principal es corregir las etiquetas faltantes / rotas, y tiene una API que posiblemente podría usarse para integrarlo en una aplicación. Dados los documentos XHTML, hay muchos buenos analizadores XML, por ejemplo, Xerces-C ++ y tinyXML .

Procesamiento de texto

Para inglés al menos, procesar texto a palabras es bastante directo. Sin embargo, hay un par de complicaciones cuando la búsqueda está involucrada.

• Las palabras de detención son palabras conocidas a priori para no proporcionar una distinción útil entre documentos en el conjunto, como artículos y proposiciones. A menudo, estas palabras no están indexadas y filtradas de las secuencias de consulta. Hay muchas listas de palabras prohibidas disponibles en la web, como esta.

• Stemming implica preprocesamiento de documentos y consultas para identificar la raíz de cada palabra para generalizar mejor una búsqueda. Por ejemplo, buscar "foobarred" debería producir "foobarred", "foobarring" y "foobar". El índice se puede generar y buscar solo en las raíces. Los dos enfoques generales para la derivación se basan en el diccionario (búsquedas de la palabra ==> raíz) y se basan en algoritmos. El algoritmo de Porter es muy común y varias implementaciones están disponibles, por ejemplo, C ++ aquí o C aquí . Stemming en la biblioteca Snowball C es compatible con varios idiomas.

• Codificación Soundex Un método para hacer que la búsqueda sea más robusta a los errores de ortografía es codificar palabras con una codificación fonética. Luego, cuando las consultas tengan errores fonéticos, se asignarán directamente a las palabras indexadas. Hay muchas implementaciones, aquí hay una .

Indexación

La palabra de mapa ==> estructura de datos de página se conoce como índice invertido . Está invertido porque a menudo se genera a partir de un índice de página adelante ==> palabras. Los índices invertidos generalmente vienen en dos formas: índice de archivo invertido , que asigna palabras a cada documento en el que ocurren, e índice invertido completo , que asigna palabras a cada posición en cada documento en el que ocurren.

La decisión importante es qué back-end usar para el índice, algunas posibilidades son, en orden de facilidad de implementación:

1. SQLite o Berkly DB : ambos son motores de base de datos con API de C ++ que se integraron en un proyecto sin requerir un proceso de servidor por separado. Las bases de datos persistentes son esencialmente archivos, por lo que se pueden buscar múltiples conjuntos de índices simplemente cambiando el archivo asociado. Usar un DBMS como back-end simplifica la creación, actualización y búsqueda de índices.
2. En la estructura de datos de memoria: si usa un índice de archivo invertido que no es prohibitivamente grande (consumo de memoria y tiempo de carga), esto podría implementarse como std::map<std::string,word_data_class> , usando boost :: serialization para la persistencia
3. En la estructura de datos del disco, he oído hablar de resultados increíblemente rápidos usando archivos mapeados en memoria para este tipo de cosas, YMMV. Tener un índice de archivo invertido implicaría tener dos archivos de índice, uno que represente palabras con algo como struct {char word[n]; unsigned int offset; unsigned int count; }; struct {char word[n]; unsigned int offset; unsigned int count; }; , y la segunda representación de tuplas (palabra, documento) con unsigned int s (palabras implícitas en el desplazamiento del archivo). El offset es el offset del archivo para la primera identificación de documento para la palabra en el segundo archivo, el count es la cantidad de identificadores de documento asociados con esa palabra (número de identificadores para leer del segundo archivo). La búsqueda se reduciría a una búsqueda binaria a través del primer archivo con un puntero en un archivo asignado a la memoria. El inconveniente es la necesidad de rellenar / truncar palabras para obtener un tamaño de registro constante.

El procedimiento para indexar depende del back-end que use. El algoritmo clásico para generar un índice de archivo invertido ( detallado aquí ) comienza con la lectura de cada documento y la extensión de una lista de tuplas (ID de página, palabra), ignorando las palabras duplicadas en cada documento. Una vez procesados ​​todos los documentos, ordene la lista por palabra, luego cópiela en (palabra, (página id1, página id2, ...)).

La biblioteca mifluz gnu implementa índices invertidos con almacenamiento, pero sin análisis de documentos o consultas. GPL, por lo que puede no ser una opción viable, pero le dará una idea de las complejidades involucradas para un índice invertido que admite una gran cantidad de documentos.

Recuperación

Un método muy común es la recuperación booleana, que es simplemente la unión / intersección de documentos indexados para cada una de las palabras de consulta que están unidas con y / y, respectivamente. Estas operaciones son eficientes si los identificadores de documento se almacenan en orden ordenado para cada término, de modo que los algoritmos como std::set_union o std::set_intersection se puedan aplicar directamente.

Hay variaciones en la recuperación, wikipedia tiene una visión general, pero booleano estándar es bueno para muchas / la mayoría de las aplicaciones.

Clasificación

Hay muchos métodos para clasificar los documentos devueltos por la recuperación booleana. Los métodos comunes se basan en el modelo de bolsa de palabras, lo que significa que la posición relativa de las palabras se ignora. El enfoque general es calificar cada documento recuperado con relación a la consulta y clasificar los documentos según su puntaje calculado. Hay muchos métodos de puntuación, pero un buen punto de partida es el término fórmula de frecuencia de documento inverso a la frecuencia .

La idea detrás de esta fórmula es que si una palabra de consulta aparece con frecuencia en un documento, ese documento debe tener una puntuación más alta, pero una palabra que aparece en muchos documentos es menos informativa por lo que esta palabra debe ser ponderada. La fórmula es, a través de los términos de consulta i = 1..N y el documento j

puntaje [j] = sum_over_i (word_freq [i, j] * inv_doc_freq [i])

donde la palabra_freq [i, j] es el número de ocurrencias de la palabra i en el documento j, y

inv_doc_freq [i] = log (M / doc_freq [i])

donde M es el número de documentos y doc_freq [i] es el número de documentos que contiene la palabra i. Tenga en cuenta que las palabras que aparecen en todos los documentos no contribuirán al puntaje. Un modelo de puntuación más complejo que se usa ampliamente es el BM25 , que se incluye tanto en Lucene como en Xapian.

A menudo, la clasificación efectiva para un dominio particular se obtiene ajustando por prueba y error. Un punto de partida para ajustar los rankings por contexto de encabezado / párrafo podría ser inflar word_freq para una palabra basada en el contexto de encabezado / párrafo, por ejemplo, 1 para un párrafo, 10 para un encabezado de nivel superior. Para algunas otras ideas, puede encontrar este documento interesante, donde los autores ajustaron la clasificación BM25 para puntuación posicional (la idea es que las palabras más cercanas al comienzo del documento son más relevantes que las palabras hacia el final).

La cuantificación objetiva del rendimiento de clasificación se obtiene mediante curvas de precisión de recuperación o precisión promedio, detalladas aquí . La evaluación requiere un conjunto ideal de consultas emparejadas con todos los documentos relevantes en el conjunto.