java nlp fuzzy-search

Fuzzy string search library en Java



nlp fuzzy-search (8)

Estoy buscando una biblioteca de alto rendimiento de Java para la búsqueda de cadenas difusas.

Existen numerosos algoritmos para encontrar cadenas similares, distancia Levenshtein, Daitch-Mokotoff Soundex, n-grams, etc.

¿Qué implementaciones Java existen? Pros y contras para ellos? Estoy al tanto de Lucene, ¿alguna otra solución o Lucene es la mejor?

Encontré esto, ¿alguien tiene experiencia con ellos?

Puede probar la biblioteca Completely , se basa en el preprocesamiento de texto para crear un índice en la memoria para responder de manera eficiente (borrosas) en grandes conjuntos de datos. A diferencia de Lucene y otras bibliotecas de búsqueda de texto completas, la API es pequeña y fácil de comenzar.

Puedes probar bitap. Estaba jugando con Bitap escrito en ANSI C y fue bastante rápido que haya implementación de Java en http://www.crosswire.org .

Puedes usar Apache Lucene, pero dependiendo del caso de uso, esto puede ser demasiado pesado. Para búsquedas borrosas muy simples puede ser un poco complejo de usar y (corregirme si estoy equivocado) requiere que construya un índice.

Si necesita un algoritmo simple en línea (= no mantener un índice), puede usar el algoritmo borroso de Bitap . Encontré una implementación en Java here . Su código se ajusta en un solo método relativamente corto con una firma que casi se explica a sí misma:

public static List<Integer> find(String doc, String pattern, int k)

Apache Commons StringUtils tiene una implementación del algoritmo de Levenshtein para la coincidencia de cadenas difusas. Se puede ver como la versión difusa de String.equals , Bitap es como la versión difusa de String.indexOf y aún utiliza la medida de distancia de Levenshtein. Por lo general, es más eficiente que ingenuamente usar Levenshtein para comparar el patrón de búsqueda con cada subcadena que posiblemente pueda coincidir.

Notas :

  • El algoritmo Bitap parece ser más útil para alfabetos relativamente pequeños, por ejemplo, ASCII simple. De hecho, la versión de Simon Watiau que he vinculado arroja una ArrayIndexOutOfBoundsException en caracteres que no son ASCII (> = 128) por lo que tendrá que filtrarlos.

  • Intenté usar Bimap en una aplicación para buscar por nombre una lista de personas en la memoria. Encontré que una distancia de 2 de Levenhstein da demasiados falsos positivos. Una distancia de Levenhstein de 1 funciona mejor, pero no puede detectar un error tipográfico en el que intercambias dos letras, por ejemplo, "William" y "Willaim". Puedo pensar en algunas formas de resolver esto, por ejemplo

    1. realice una búsqueda difusa solo cuando una búsqueda exacta no encuentre coincidencias (y muestre un mensaje al usuario sobre esto)
    2. ajuste Bitap para usar la distancia Damerau-Levenshtein donde un intercambio tiene una distancia de 1 en lugar de 2. De acuerdo con wikipedia , esto es posible, pero no pude encontrar una implementación existente en Java.
    3. en lugar de "contiene" haz un "startsWith". Las herramientas de búsqueda difusa contienen una versión de prefijo de Damerau-Levenshtein, pero me dio una ArrayIndexOutOfBoundsException
    4. ajustar el algoritmo para introducir el ranking de resultados de búsqueda donde los resultados exactos obtienen una puntuación más alta

    Si vas a hacer 2 o 4, puede ser mejor usar una biblioteca de búsqueda de texto completo como Lucene de todos modos.

  • Puede encontrar más información sobre búsqueda difusa en este blog . Su autor también creó una implementación en Java llamada BitapOnlineSearcher , pero requiere que use java.io.Reader junto con una clase de alfabeto. Es Javadoc escrito en ruso.

Si en su mayoría está comparando cadenas cortas y quiere algo portátil y liviano, puede usar el conocido algoritmo python fuzzywuzzy portado a Java .

Puedes leer más sobre esto here

SimMetrics es probablemente lo que necesita: http://sourceforge.net/projects/simmetrics/

Tiene varios algoritmos para calcular varios sabores de editar-distancia.

Lucene es un motor de búsqueda de texto completo muy poderoso, pero la búsqueda FT no es exactamente lo mismo que la coincidencia difusa de cadenas (por ejemplo, dada una lista de cadenas, encuentre la que sea más similar a alguna cadena candidata).

Apache Lucene es la única forma, creo. No conozco ninguna mejor búsqueda lib.

Apache Lucene (TM) es una biblioteca de motores de búsqueda de texto de alto rendimiento y con todas las características escritas completamente en Java. Es una tecnología adecuada para casi cualquier aplicación que requiera búsqueda de texto completo, especialmente multiplataforma.