Cómo buscar fragmentos de texto en una base de datos

Question

¿Existen herramientas de código abierto o comerciales disponibles que permitan la indexación de fragmentos de texto de los contenidos de la base de datos y puedan consultarse desde Java?

Antecedentes de la pregunta es una gran tabla de base de datos MySQL con varios cientos de miles de registros, que contiene varias columnas VARCHAR. En estas columnas, a las personas les gustaría buscar fragmentos de los contenidos, por lo que un índice de texto completo (que se basa en límites de palabras) no ayudaría.

EDITAR: [Agregado a dejar claro por qué estas primeras sugerencias no resolverían el problema:]

Esta es la razón de MySQL construido en el índice de texto completo no va a hacer el trabajo, y tampoco lo hará Lucene o Sphinx, toda de los cuales fueron sugeridos en las respuestas. Ya analicé ambos, pero hasta donde puedo decir, estos están basados ​​en la indexación palabras, excluyendo palabras de parada y haciendo todo tipo de cosas sensatas para una búsqueda de texto completo real. Sin embargo, esto no es adecuado, porque podría estar buscando un término de búsqueda como "oison" que debe coincidir con "Roisonic Street" y con "Poison-Ivy". La diferencia clave aquí es que el término de búsqueda es solo un fragmento del contenido de la columna, que no tiene que estar delimitado por ningún carácter especial o espacio en blanco.

Edit2: [Agregado algo más de información de fondo:] La función solicitada que se va a implementar en base a esto es una búsqueda muy suelto para descripciones de los artículos en un sistema de gestión de mercancías. Los usuarios a menudo no conocen el número de artículo correcto, sino solo una parte del nombre del artículo. Lamentablemente, la calidad de estas descripciones es bastante baja, provienen de un sistema heredado y no se puede cambiar fácilmente. Si, por ejemplo, las personas buscaran un mazo entrarían en "trineo". Con un índice basado en palabras/tokens esto no encontraría las coincidencias que se almacenan como "mazo", pero solo aquellos escuchan "mazo de trineo". Hay todo tipo de variaciones extrañas que deben cubrirse, por lo que un enfoque basado en tokens no es práctico.

Actualmente, lo único que podemos hacer es una consulta LIKE '%searchterm%', lo que desactiva efectivamente el uso de cualquier índice y requiere muchos recursos y tiempo.

Idealmente, cualquier herramienta de este tipo crearía un índice que me permitiera obtener resultados de tales consultas muy rápidamente, para poder implementar una búsqueda tipo foco, solo recuperando los datos "reales" de la tabla MySQL mediante la clave primaria cuando un usuario elige un registro de resultados.

Si es posible, el índice debe ser actualizable (sin necesidad de una reconstrucción completa), ya que los datos podrían cambiar y deberían estar disponibles para la búsqueda inmediata por parte de otros clientes.

Estaría encantado de recibir recomendaciones y/o informes de experiencia.

Edit3: Solución Comercial encontró que "simplemente funciona" A pesar de que tengo un montón de buenas respuestas para esta pregunta, quería señalar aquí, que al final nos fuimos con un producto comercial llamado "búsqueda rápida" , fabricado y vendido por una empresa alemana llamada "HMB Datentechnik". Tenga en cuenta que estoy no afiliado a ellos de alguna manera, porque podría aparecer así cuando continúe y describa lo que su producto puede hacer. Desafortunadamente, su website parece bastante malo y solo es alemán, pero el producto en sí es realmente genial. Actualmente tengo una versión de prueba de ellos, tendrás que contactarlos, no hay descargas, y estoy muy impresionado.

Como no hay documentación completa disponible en línea, intentaré y describiré mis experiencias hasta ahora.

Lo que hacen es crear un archivo de índice personalizado basado en el contenido de la base de datos. Se pueden integrar a través de ODBC, pero por lo que me dicen, los clientes rara vez lo hacen. En su lugar, y esto es lo que probablemente haremos, usted genera una exportación de texto (como CSV) desde su base de datos primaria y la envía a su indexador. Esto le permite ser completamente independiente de la estructura de la tabla real (o cualquier base de datos SQL); de hecho, exportamos datos unidos desde varias tablas. Los índices se pueden actualizar progresivamente más adelante sobre la marcha.

Basado en que su servidor (de unos 250kb aproximadamente, ejecutándose como una aplicación de consola o servicio de Windows) sirve para escuchar las consultas en un puerto TCP. El protocolo está basado en texto y parece un poco "viejo", pero es simple y funciona. Básicamente, acaba de transmitir cuáles de los índices disponibles desea consultar y los términos de búsqueda (fragmentos), delimitados por espacios. Hay tres formatos de salida disponibles, matriz HTML/JavaScript, XML o CSV. Actualmente estoy trabajando en un contenedor Java para el protocolo de cable algo "anticuado". Pero los resultados son fantásticos: actualmente tengo un conjunto de datos de muestra de aproximadamente 500,000 registros con 8 columnas indexadas y mi aplicación de prueba desencadena una búsqueda en las 8 columnas para el contenido de un JTextField en cada golpe de teclado mientras se edita y puede actualizar el visualización de resultados (JTable) en tiempo real! Esto sucede sin ir a la instancia de MySQL de donde provienen los datos. Según las columnas que recibe, puede solicitar el registro "original" consultando MySQL con la clave principal de esa fila (debe incluirse en el índice QuickFind, por supuesto).

El índice es aproximadamente 30-40% del tamaño de la versión de exportación de texto de los datos. La indexación estaba principalmente vinculada a la velocidad de E/S del disco; mis 500,000 registros tomaron aproximadamente uno o dos minutos para procesarse.

Es difícil describir esto, ya que me resultó difícil de creer cuando vi una demostración de un producto interno. Presentaron una base de datos de direcciones de 10 millones de filas y buscaron fragmentos de nombres, direcciones y números de teléfono y al presionar el botón "Buscar", los resultados regresaron en menos de un segundo, todo en un cuaderno. Por lo que me dicen, a menudo se integran con sistemas SAP o CRM para mejorar los tiempos de búsqueda cuando los agentes del centro de llamadas solo entienden los fragmentos de los nombres o las direcciones de una persona que llama.

De todos modos, probablemente no lo describiré mucho mejor. Si necesita algo como esto, definitivamente debe ir a ver esto. Google Translate hace un trabajo razonablemente bueno al traducir su sitio web del alemán al inglés, por lo que este podría ser un buen comienzo.

Answer 1

I have Yo tenía este requerimiento específico, pero mi experiencia me dice que Lucene puede hacer el truco, aunque quizás no solo. Definitivamente lo usaría a través de Solr como lo describe Michael Della Bitta en la primera respuesta. El enlace que dio fue perfecto: léalo para obtener más información.

En pocas palabras, Solr le permite definir FieldTypes personalizados. Estos consisten en un Analizador de tiempo índice y un Analizador de tiempo de consulta.Los analizadores determinan qué hacer con el texto, y cada uno consiste en un Tokenizer y cero a muchos TokenFilters. El Tokenizer divide el texto en fragmentos y luego cada TokenFilter puede agregar, quitar o modificar tokens.

El campo puede por lo tanto terminar indexando algo bastante diferente del texto original, incluyendo tokens múltiples si es necesario. Entonces, lo que quiere es una copia de token múltiple de su texto original, que puede consultar enviando a Lucene algo así como "my_ngram_field: sledge". No hay comodines involucrados :-)

A continuación, siguen un modelo similar al prefijo buscar ofrecido en el archivo solrconfig.xml:

<fieldType name="prefix_token" class="solr.TextField" positionIncrementGap="1"> 
    <analyzer type="index"> 
     <tokenizer class="solr.WhitespaceTokenizerFactory"/> 
     <filter class="solr.LowerCaseFilterFactory" /> 
     <filter class="solr.EdgeNGramFilterFactory" minGramSize="1" maxGramSize="20"/> 
    </analyzer> 
    <analyzer type="query"> 
     <tokenizer class="solr.WhitespaceTokenizerFactory"/> 
     <filter class="solr.LowerCaseFilterFactory" /> 
    </analyzer> 
</fieldType> 

El EdgeNGramFilterFactory es cómo implementar la concordancia de prefijo para autocompletar cuadro de búsqueda. Toma los tokens que provienen de las etapas previas (palabras únicas delimitadas por espacios en blanco transformadas en minúsculas) y las expande en cada subcadena en el borde inicial. sledgehammer = s, sl, sle, trineo, trineo, trineo, trineo, etc.

Debe seguir este patrón, pero reemplace el EdgeNGramFilterFactory con el suyo que tiene todos los NGrams en el campo. El valor predeterminado org.apache.solr.analysis.NGramFilterFactory es un buen comienzo, pero transpone las letras para la corrección ortográfica. Podrías copiarlo y quitarlo, es una clase bastante simple de implementar.

vez que tenga su propia FieldType (llámese ngram_text) utilizando su propio MyNGramFilterFactory, basta con crear su campo original y el campo de n-gramas de este modo:

<field name="title" type="text" indexed="true" stored="true"/> 
    <field name="title_ngrams" type="ngram_text" indexed="true" stored="false"/> 

Entonces dilo a copiar el campo original en la fantasía uno:

<copyField source="title" dest="title_ngrams"/> 

bien, ahora cuando se busca "title_ngrams: trineo" debe obtener una lista de documentos que contienen esta. Luego, en su lista de campo para la consulta, simplemente le dice que recupere el campo llamado título en lugar del campo title_ngrams.

Eso debería ser suficiente como un pequeño empujón para que pueda ajustar las cosas y ajustarlo a niveles de rendimiento sorprendentes con bastante facilidad. En un trabajo anterior teníamos una base de datos con más de diez millones de productos con grandes descripciones de HTML y logramos que Lucene hiciera tanto la consulta estándar como la corrección ortográfica en menos de 200 ms en un servidor de tamaño medio que manejaba varias docenas de consultas simultáneas. Cuando tienes muchos usuarios, el almacenamiento en caché entra y lo hace gritar!

Ah, y la indexación incremental (aunque no en tiempo real) es muy fácil. Incluso puede hacerlo bajo grandes cargas, ya que crea y optimiza el nuevo índice en el fondo y lo autocalienta antes de cambiarlo. Muy elegante.

¡Buena suerte!

Answer 2

Esto puede no ser lo que quieres escuchar, porque supongo que estás tratando de resolver esto con código SQL, pero Lucene sería mi primera opción. También puede crear técnicas de clasificación y mejora bastante ingeniosas con herramientas adicionales. Lucene está escrito en Java, por lo que debería proporcionarle exactamente la interfaz que necesita.

Si usted era una tienda de Microsoft, la mayoría de lo que está buscando está integrado en SQL Server, y se pueden habilitar comodines que le permitirán hacer coincidencias parciales de palabras.

En Lucene y Lucene.Net, puede usar wildcard matches si lo desea. Sin embargo, no se admite el uso de comodines como el primer símbolo en una búsqueda. Si desea utilizar comodines de primer carácter, probablemente necesite implementar algún tipo de índice basado en trie, ya que es una operación costosa en muchos casos para filtrar el conjunto de términos a algo razonable para el tipo del índice más comúnmente necesario para las aplicaciones de búsqueda de texto completo, donde el origen del sufijo es generalmente más valioso.

Al parecer, puede alterar la instancia de Query Parser en Lucene para anular esta regla estableciendo setAllowLeadingWildcard en verdadero.

Estoy bastante seguro de que las búsquedas de comodín en ambos extremos de la palabra son inherentemente ineficientes. Las listas de omisiones se utilizan a veces para mejorar el rendimiento en tales búsquedas con texto sin formato, pero creo que es más probable que encuentres una implementación como esa en algo como grep que una herramienta de indexación de texto generalizada.

Existen otras soluciones para el problema que usted describe donde una palabra puede aparecer deletreada como dos, o viceversa. Consultas borrosas son compatibles en Lucene, por ejemplo. Las variantes ortográficas y morfológicas pueden manejarse utilizando un filtro que ofrezca sugerencias basadas en algún tipo de mecanismo bayesiano o mediante la indexación de trucos, es decir, tomando un corpus de variantes frecuentes y rellenando el índice con esos términos. Incluso he visto conocimiento de los datos estructurados en el motor de texto completo (por ejemplo, agregar el nombre de la ciudad y la palabra "hotel" a los registros de la mesa del hotel, para que sea más probable que "Hoteles de París" incluya un registro de la pensión -casa Caisse des Dépôts.) Aunque no es exactamente un problema trivial, es manejable sin destruir las ventajas de las búsquedas basadas en palabras.

Answer 3

Estoy bastante seguro de que Mysql ofrece una opción de texto completo, y probablemente también sea posible usar Lucene.

Vea aquí los comentarios relacionados

Best efficient way to make a fulltext search in MySQL

Answer 4

Si la tabla es MyISAM, puede usar completos capabilites de búsqueda de texto de MySQL: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html

Si no, el "estándar de la industria" es http://www.sphinxsearch.com/

Algunas ideas sobre qué hacer si usa InnoDB: http://www.mysqlperformanceblog.com/2009/09/10/what-to-do-with-mysql-full-text-search-while-migrating-to-innodb/

Además, una buena presentación que introduce Esfinge y explica la arquitectura + uso http://www.scribd.com/doc/2670976/Sphinx-High-Performance-Full-Text-Search-for-MySQL-Presentation

actualización
Después de haber leído su aclaración a la pregunta - Sphinx puede hacer coincidencias de subcadenas. Debe establecer "enable-star" y crear un índice infijo con el min_infix_length adecuado (1 le dará todas las subcadenas posibles, pero obviamente cuanto más alto sea el conjunto, menor será su índice, y más rápidas serán sus búsquedas). Ver http://sphinxsearch.com/docs/current.html para más detalles.

Answer 5

Utilizaría Apache Solr. La estrategia de indexación es totalmente ajustable (vea http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters), puede leer incrementalmente directamente de su base de datos para poblar el índice (vea DataImportHandler en la misma wiki), y puede consultarse básicamente desde cualquier lenguaje que hable HTTP y XML o algo así como JSON.

Answer 6

Lo que intenta hacer es poco probable que sea mucho más rápido que LIKE '%searchterm%' sin una gran cantidad de código personalizado. El equivalente a LIKE 'searchterm%' debería ser trivial. Podrías hacer lo que estás pidiendo construyendo un índice de todas las posibles palabras parciales que no están cubiertas por el comodín final, pero esto daría como resultado un tamaño de índice increíblemente grande, y sería inusualmente lento para las actualizaciones. Long tokens daría lugar a Bad Things ™. ¿Puedo preguntar por qué necesita esto? Re: Spotlight ... Te das cuenta de que Spotlight no hace esto, ¿verdad? Está basado en token como cualquier otro indexador de texto completo. Por lo general, la expansión de consulta es el método apropiado para obtener coincidencias inexactas, si ese es su objetivo.

Editar:

que tenía un proyecto exactamente como esta en un momento dado; part-numbers para todo tipo de cosas. Finalmente nos decidimos por searchterm* en Xapian, pero creo que Lucene también tiene el equivalente. No encontrará una buena solución que maneje búsquedas de comodines en cualquier lado del token, pero un comodín posterior suele ser más que suficiente para lo que quiere, y sospecho que encontrará que los usuarios se adaptan a su sistema bastante rápido si tienen algún control sobre la limpieza de los datos. Combínalo con la expansión de consultas (o incluso la expansión de tokens limitada) y deberías estar bastante bien configurado. La expansión de consulta convertiría una consulta para "mazo de martillo" en "mazo de martillo * O (mazo * martillo *)" o algo similar. No todas las consultas funcionarán, pero las personas ya están bastante bien formadas para intentar consultas relacionadas cuando algo no funciona, y siempre que al menos una o dos consultas obvias presenten los resultados que esperan, debería estar bien. Su mejor opción es limpiar los datos y organizarlos mejor. Te sorprendería lo fácil que es que esto termine si la versión de todo e implementa una política de edición igualitaria. Tal vez permita que las personas agreguen palabras clave a una entrada y asegúrese de indexarlas, pero establezca límites sobre cuántas se pueden establecer. Demasiados y puede degradar los resultados de búsqueda.

Answer 7

¿qué pasa con el uso de herramientas como las propuestas arriba (lucene, etc.) para indexación de texto completo y que tienen LIKE buscar casos, donde no se encontró nada? (es decir, ejecute LIKE solo después de que la búsqueda indexada de texto completo arrojó cero resultados)

Answer 8

La respuesta exacta a su pregunta es right here Si funcionará lo suficientemente bien para el tamaño de sus datos es otra cuestión.

Answer 9

La búsqueda de Shingle podría hacer el truco.

http://en.wikipedia.org/wiki/W-shingling

Por ejemplo, si se utiliza tejas de 3 caracteres, puede dividir "Roisonic" a: "ROI", "hijo", "ic", y almacenar los tres valores, asociándolos con originales entrada. Al buscar "oison", primero buscará "ois", "iso", "son". Primero, haz coincidir todas las entradas con culebrilla (encontrando la que tiene "hijo"), y luego puedes refinar la búsqueda usando una coincidencia exacta de cuerdas.

Tenga en cuenta que la teja de 3 caracteres requiere que el fragmento en la consulta tenga al menos 5 caracteres de longitud, la teja de 4 caracteres requiere la consulta de 7 caracteres, y así sucesivamente.

Answer 10

Un índice de texto completo "real" que utiliza partes de una palabra sería mucho más grande que el texto fuente y, aunque la búsqueda puede ser más rápida, cualquier actualización o proceso de inserción sería terriblemente lento.

Solo espera que haya algún tipo de patrón en los "errores". Podría aplicar un conjunto de reglas de tipo "AI" al texto entrante y producir una forma canónica del texto que luego podría aplicar índice de texto completo a. Un ejemplo para una regla podría ser dividir una palabra que termina en martillo en dos palabras s/(\ w?) (martillo)/\ 1 \ 2/g o para cambiar "sledg" "trineo" y "sledg" schledge "to" trineo ". Debería aplicar el mismo conjunto de reglas al texto de la consulta. De la forma en que un producto descrito como" mazo martillo "podría coincidir con una búsqueda de" martillo de trineo "