Biblioteca ligera de búsqueda difusa

Question

¿Puede sugerir alguna biblioteca ligera de búsqueda de texto difuso?

Lo que quiero hacer es permitir que los usuarios encuentren datos correctos para los términos de búsqueda con errores tipográficos.

Podría usar motores de búsqueda de texto completo como Lucene, pero creo que es una exageración.

Editar:
Para hacer más clara la pregunta aquí es un escenario principal para esa biblioteca:
tengo una gran lista de cadenas. Quiero poder buscar en esta lista (algo así como el intellisense de MSVS), pero debería ser posible filtrar esta lista por cadenas que no están presentes pero lo suficientemente cerca de alguna cadena que esté en la lista.
Ejemplo:

• Rojo
• verde
• azul

Cuando escribo 'Gren' o 'Geen' en un cuadro de texto, quiero ver 'verde' en el resultado conjunto.

El idioma principal de los datos indexados será el inglés.

Creo que Lucene es pesado para esa tarea.

actualización:

he encontrado un producto a juego mis requisitos. Es ShuffleText.
¿Conoces alguna alternativa?

Answer 1

@aku - los enlaces a las bibliotecas de trabajo de soundex están justo en la parte inferior de la página.

En cuanto a la distancia Levenshtein, el Wikipedia article on that también tiene implementaciones enumeradas en la parte inferior.

Answer 2

Soundex es muy 'Inglés' en su codificación - Daitch-Mokotoff funciona mejor para muchos nombres, especialmente nombres europeos (germánicos) y judíos. En mi mundo centrado en el Reino Unido, es lo que uso.

Wiki here.

Answer 3

Lucene es muy escalable — lo que significa que también es bueno para pequeñas aplicaciones. Puede crear un índice en la memoria muy rápidamente si eso es todo lo que necesita.

Para la búsqueda difusa, realmente necesita decidir qué algoritmo desea usar. Con la recuperación de información, utilizo una técnica n-gram con Lucene con éxito. Pero esa es una técnica de indexación especial, no una "biblioteca" en sí misma.

Sin saber más acerca de su aplicación, no será fácil recomendar una biblioteca adecuada. ¿Cuantos datos estás buscando? ¿Qué formato son los datos? ¿Con qué frecuencia se actualizan los datos?

Answer 4

Si puede elegir utilizar una base de datos, le recomiendo usar PostgreSQL y su fuzzy string matching functions.

Si puede usar Ruby, le sugiero que busque en el amatch library.

Answer 5

no se hayan indicado su plataforma de desarrollo, pero si su PHP entonces sugiero que busque en la lubrary Zend Lucene:

http://ifacethoughts.net/2008/02/07/zend-brings-lucene-to-php/ http://framework.zend.com/manual/en/zend.search.lucene.html

Como lámpara de su mucho más ligero que Lucene en Java, y puede ampliarse fácilmente para otros tipos de archivos, siempre que pueda encontrar una biblioteca de conversión o un convertidor de línea cmd; hay muchas soluciones de OSS para hacerlo.

Answer 6

Pruebe Walnutil - basado en Lucene API - integrado a SQL Server y Oracle DBs. Puede crear cualquier tipo de índice y luego usarlo. Para una búsqueda simple puede usar algunos métodos de walnutilsoft, para casos de búsqueda más complicados puede usar la API de Lucene. Consulte el ejemplo basado en web donde se usaron índices creados a partir de Herramientas de Walnutil. También puede ver algunos ejemplos de código escritos en Java y C# que puede usar para crear diferentes tipos de búsqueda. Esta herramienta es gratuita. http://www.walnutilsoft.com/

Answer 7

Una solución potente y liviana es sphinx.

Es más pequeño que Lucene y admite la desambiguación.

Está escrito en C++, es rápido, probado en combate, tiene bibliotecas para cada env y es utilizado por las grandes empresas, como craigslists.org

Answer 8

Comprobar este enlace out.It utiliza las métricas de distancia levenshtein pero es mucho más rápido. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html

Answer 9

No estoy seguro de qué tan bien Lucene es adecuado para la búsqueda difusa, la biblioteca personalizada sería una mejor opción. Por ejemplo, esta búsqueda se realiza en Java y funciona bastante rápido, pero está hecha a medida para tal tarea: http://www.softcorporation.com/products/people/