graph - google - algoritmo de busqueda ejemplo

adaptación de búsqueda de texto para algoritmos de comparación gráfica/molécula

Question

Estoy buscando un motor de búsqueda de texto para un tipo de búsqueda de texto no tradicional y quiero consejos sobre qué herramienta (Lucene, Sphinx, Xapian u otra cosa) es la más adecuada para mí, además de consejos sobre dónde empezar.

Tengo moléculas representadas como gráficos (átomos y enlaces). Tengo una manera de enumerar todos los subgrafos de hasta el tamaño k. Al ser técnico, las entradas son SMILES y la salida es SMARTS canónico y el número de veces que ocurre cada subgráfico / SMARTS.

Por ejemplo, si la molécula de entrada es " CCO ", los resultados canónicos son {"C": 2, "O": 1, "CC": 1, "OC": 1, "CCO": 1} y si el la molécula es " SCO ", luego los resultados canónicos son {"C": 1, "S": 1, "O": 1, "CS": 1, "OC": 1, "SCO": 1}. Estos son pequeños ejemplos. Para la molécula real obtuve alrededor de 500 "palabras", que parecen "CC (C) O", "CCCOCC", "cn" y "cccc (c) O".

Mirar las moléculas como una colección de cadenas características más recuentos significa que debería poder utilizar una herramienta de búsqueda de texto para hacer comparaciones en el nivel de texto, con la esperanza de que tengan sentido en el nivel de química.

Por ejemplo, puedo usar similitud coseno tal vez con el peso tf-idf y encontrar moléculas similares buscando subpatrones similares. Con los ejemplos "CCO" y "SCO" anteriores, la similitud del coseno es (2 * 1 + 1 * 1 + 1 * 1) / sqrt (2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1) / sqrt (6 * (1 * 1)) = 4 / sqrt (8 * 6) = 0.58.

Para otro ejemplo, si quiero encontrar moléculas que contengan una subestructura "CCS" entonces puedo hacer una búsqueda de índice invertida rápida basada en los conteos (las moléculas deben tener al menos 2 "C" s, al menos 1 "CS", y así sucesivamente) antes de abordar el problema de isomorfismo del subgrafo NP. Es decir, los métodos basados ​​en texto pueden actuar como un filtro para rechazar discrepancias obvias.

Estoy tratando de descubrir las soluciones de texto que existen, pero es un poco desalentador. No necesito detener las palabras, no necesito derivar, no me importa el orden de las palabras; No necesito muchas de las características que existen. Necesito la capacidad de mantener vectores de palabras, ya que es importante saber si aparece "C" 2 veces o 3.

¿Qué motor de búsqueda de texto es el más apropiado para mí? Se parece a Lucene, especialmente con el trabajo en Mahout. ¿Puede recomendar qué partes de la documentación mirar o tutoriales relevantes? Los que he encontrado están destinados a búsquedas de texto completo, con derivación y otras características que no necesito.

Answer 1

Hmm ... realmente no sé qué son SMARTS, o cómo funciona la similitud química. Si desea usar lucene, primero considere usar solr. Como sus datos están en gráficos, puede echar un vistazo a neo4j con el componente solr. Además, ¿este problema estaría más relacionado con el documento cercano a los duplicados? Para ayudar con eso hay una serie de algoritmos LSH, Spotsigs, shingling y simhash. Ojalá pudiera ser de más ayuda.

Answer 2

No uses lucene O Solr. Los modelos internos son anticuados y improvisados; aunque hacen un buen trabajo. Encuentre un motor con los criterios mínimos (si desea hacer un mapa dentro de un motor de texto) BM25F totalmente compatible. Si lo buscaba y quería escalabilidad, rendimiento y una comunidad de soporte de bajo costo, francamente iría con SQL Server y cubos. La creación de licencias con SQL Server podría ser un bloqueador completo. Buena suerte.

Answer 3

EDITAR: Puede que lo haya entendido mejor ahora. Desea comparar gráficos, representados como cadenas. Las cuerdas tienen "palabras" que pueden repetirse. Puedes usar Lucene, en cuyo caso respaldo la sugerencia de usar Solr. Básicamente, cada documento Solr consistirá en un solo campo; El campo contendrá la cadena, que sugiero que desenrolles: escribe CC lugar de C:2 . Si usa un espacio para separar las palabras, puede usar un WhiteSpaceAnalyzer. Si usa otro separador, es posible que necesite escribir un analizador personalizado, que no es tan difícil de hacer.

¿Es esta una buena idea? No estoy seguro. Este es el por qué:

1. Lucene (y Solr) no usan similitud de coseno como tal, sino Lucene Semejanza , que mezcla coseno, TF / IDF y puntuación booleana, con algunas modificaciones específicas. Esto funciona bien para la mayoría de los casos de uso de texto, pero puede ser diferente de lo que necesita.
2. ¿Necesita comparar resultados de diferentes búsquedas? Si lo hace, es difícil hacerlo con Solr, ya que normalizó cada búsqueda hasta un valor máximo de 1.

Le sugiero que pruebe Solr para obtener una pequeña muestra de su base de datos. Si Solr trabaja para ti, bien. De lo contrario, el herpes zoster y los min-hashes probablemente sean el camino a seguir. La minería de datos masivos por Rajaraman y Ullman es un libro gratuito reciente sobre estos temas. Te sugiero que lo leas. Cubre la búsqueda de cadenas similares en montañas de datos. Creo que el diferenciador es: ¿necesitas una intersección relativamente grande? Si es así, usa shingling y min-hashes. Si no, tal vez Solr es suficiente.