Biblioteca de pesquisa de string difusa em Java

Eu estou procurando uma biblioteca Java de alto desempenho para busca de string difusa.

Existem numerosos algoritmos para encontrar cordas similares, distância de Levenshtein, Daitch-Mokotoff Soundex, n-gramas etc.

Quais implementações Java existem? Prós e contras para eles? Estou ciente de Lucene, qualquer outra solução ou Lucene é o melhor?

Eu encontrei estes, alguém tem experiência com eles?

  • SimMetrics
  • NGramJ

Commons Lang tem uma implementação da distância de Levenshtein .

O Commons Codec tem uma implementação de soundex e metaphone .

Você pode usar o Apache Lucene, mas dependendo do caso de uso, isso pode ser muito pesado. Para pesquisas fuzzy muito simples, pode ser um pouco complexo de usar e (corrija-me se eu estiver errado) requer que você construa um índice.

Se você precisa de um simples algoritmo online (= não manter um índice), você pode usar o algoritmo Fuzzy Bitap . Eu encontrei uma implementação em Java aqui . Seu código se encheckbox em um único método relativamente curto com uma assinatura quase auto-explicativa:

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

O Apache Commons StringUtils possui uma implementação do algoritmo Levenshtein para correspondência de String fuzzy. Ele pode ser visto como a versão fuzzy de String.equals , o Bitap é como a versão fuzzy de String.indexOf e ainda usa a medida de distância Levenshtein. Geralmente, é mais eficiente do que ingenuamente usar o Levenshtein para comparar o padrão de pesquisa com cada substring que poderia corresponder.

Notas :

  • O algoritmo Bitap parece ser mais útil para alfabetos relativamente pequenos, por exemplo, ASCII simples. Na verdade, a versão do Simon Watiau que eu criei linkou para lançar um ArrayIndexOutOfBoundsException em caracteres não-ASCII (> = 128), então você terá que filtrá-los.
  • Eu tentei usar o Bimap em um aplicativo para pesquisar uma lista de pessoas na memory pelo nome. Descobri que uma distância de Levenhstein de 2 dá muitos falsos positivos. Uma distância Levenhstein de 1 funciona melhor, mas não pode detectar um erro de digitação onde você troca duas letras, por exemplo, “William” e “Willaim”. Eu posso pensar em algumas maneiras de resolver isso, por exemplo

    1. faça uma pesquisa difusa apenas quando uma pesquisa exata não encontrar nenhuma correspondência (e mostrar uma mensagem para o usuário sobre isso)
    2. ajuste o Bitap para usar a distância Damerau-Levenshtein, onde um swap tem distância 1 em vez de 2. Segundo a Wikipedia , isso é possível, mas não consegui encontrar uma implementação existente em Java.
    3. em vez de “contém” faça um “startsWith”. As ferramentas de pesquisa difusas contém uma versão de prefixo de Damerau-Levenshtein, mas me deu uma ArrayIndexOutOfBoundsException
    4. ajustar o algoritmo para introduzir a sorting do resultado de pesquisa em que as correspondências exatas são mais altas

    Se você for fazer 2 ou 4, pode ser melhor usar uma biblioteca de pesquisa de texto completo adequada como o Lucene.

  • Mais informações sobre pesquisas difusas podem ser encontradas neste blog . O autor também criou uma implementação em Java chamada BitapOnlineSearcher , mas requer que você use java.io.Reader junto com uma class Alphabet. É Javadoc é escrito em russo.

Se você está principalmente comparando strings curtas e quer algo portátil e leve, você pode usar o conhecido algoritmo python fuzzywuzzy portado para Java .

Você pode ler mais sobre isso aqui

SimMetrics é provavelmente o que você precisa: http://sourceforge.net/projects/simmetrics/

Tem vários algoritmos para calcular vários sabores de distância de edição.

O Lucene é um mecanismo de pesquisa de texto completo muito poderoso, mas a pesquisa FT não é exatamente a mesma coisa que uma correspondência de cadeia de caracteres difusa (por exemplo, uma lista de cadeias de caracteres me acha a mais semelhante a uma cadeia de caracteres candidata).

Você pode tentar bitap. Eu estava jogando com bitap escrito em ANSI C e foi muito rápido, há implementação de java em http://www.crosswire.org .

Você pode tentar a biblioteca Completamente , ela se baseia no pré-processamento de texto para criar um índice na memory para responder de forma eficiente a buscas (difusas) em grandes conjuntos de dados. Ao contrário do Lucene e de outras bibliotecas de pesquisa de texto com todos os resources, a API é pequena e fácil de começar.

Apache Lucene é o único caminho, eu acho. Eu não conheço melhor busca lib.

O Apache Lucene (TM) é uma biblioteca de mecanismo de pesquisa de texto de alto desempenho e repleta de resources, escrita inteiramente em Java. É uma tecnologia adequada para praticamente qualquer aplicativo que exija pesquisa de texto completo, especialmente entre plataformas.

    Intereting Posts