Correspondência aproximada de string

Question

Eu sei que essa pergunta foi feita muito tempo. Quero uma sugestão sobre a qual o algoritmo é adequado para a correspondência aproximada de strings.

O aplicativo é especificamente para correspondência de nomes da empresa e nada mais.

O maior desafio é provavelmente o nome final da empresa e curto, exemplo, exemplo: 1. Companya Pty Ltd vs Companya Pty. Ltd. VS Companya 2. Wes Engineering vs Wes Engineering (ocorrência extremamente rara)

Você acha que a distância de edição de Levenshtein é adequada?

Estou usando C#

Atenciosamente, máx

Answer 1

Existem várias métricas de distância da corda que você pode usar.

eu recomendaria Jaro-Winkler. Ao contrário da edição de edição, onde o resultado de uma comparação está em unidades discretas de edições, o JW oferece uma pontuação de 0-1. É especialmente adequado para nomes próprios. Veja também Este bom tutorial e isso é tão pergunta.

Não trabalhei com C#, mas aqui estão algumas implementações da JW que encontrei online:

Impl 1 (Eles também têm uma versão net de pontos se você olhar para a lista de arquivos)

Impl 2

---

Se você quiser fazer uma correspondência um pouco mais sofisticada, pode tentar fazer alguma normalização personalizada de formas de palavras que ocorrem em nomes de empresas como como ltd/limited, inc/incorporated, corp/corporation Para explicar a insensibilidade do caso, abreviações etc. dessa maneira, se você calcular

distance (normalize("foo corp."), normalize("FOO CORPORATION") )

Você deve ter o resultado em 0 em vez de 14 (que é o que você obteria se você calcule o Levenshtein Edit-Distância).

Answer 2

Sim, a distância de Levenshtein é adequada para isso. Funcionará para todos aqueles que você listou pelo menos.

Você também pode usar SoundEx, mas acho que você não precisará disso.

Answer 3

Nestes exemplos simples, apenas remover todos os caracteres não alfa-numéricos oferece uma correspondência e é o mais fácil de fazer o que você pode pré-computar os dados de cada lado, depois faça uma correspondência direta que será muito mais rápida do que Cruz multiplicando e calculando a distância de edição.

Answer 4

Eu já forneci minha resposta em outra pergunta.

https://stackoverflow.com/a/30120166/2282794

Eu trabalhei em um sistema realmente de grande escala, com requisitos de correspondência de nomes semelhantes sobre os quais você falou. A correspondência de nomes não é muito direta e a ordem dos nomes do primeiro e do sobrenome pode ser diferente. Os algoritmos simples de combinação de nomes difusos falham miseravelmente em tais cenários.

Se queremos apenas falar sobre os algoritmos aproximados de correspondência de string, existem muitos. Poucos deles são: Jaro-Winkler, Editar Distância (Levenshtein), Algoritmos Baseados em Jaccard, SoundEx/Fonética etc. Um Google simples nos daria todos os detalhes. Você pode implementar todos eles em C#

A ironia é que eles trabalham enquanto você tenta combinar duas dadas as seqüências de entrada. Tudo bem teoricamente e para demonstrar a maneira como combina com a correspondência de cordas confusa ou aproximada.

No entanto, o ponto grosseiramente discreto é: como usamos o mesmo nas configurações de produção. Nem todo mundo que eu conheço que estava procurando um algoritmo aproximado de correspondência de cordas sabia como eles poderiam resolver o mesmo no ambiente de produção.

Eu poderia ter falado sobre o Lucene, específico para Java, mas há Lucene para .Net também.

https://lucenenet.apache.org/