Como faço uma correspondência fuzzy de nomes de empresas no MYSQL com o PHP para preenchimento automático?

Meus usuários importarão por meio de recortar e colar uma string grande que conterá nomes de empresas.

Eu tenho um database MYSQL existente e crescente de nomes de empresas, cada um com um company_id exclusivo.

Eu quero ser capaz de analisar a seqüência e atribuir a cada um dos nomes de empresa inseridos pelo usuário uma correspondência difusa.

Agora, apenas fazendo uma sequência de caracteres em seqüência, também é lento. ** A indexação do Soundex será mais rápida? Como posso dar ao usuário algumas opções enquanto elas estão digitando? **

Por exemplo, alguém escreve:

 Microsoft -> Microsoft
 Bare Essentials -> Bare Escentuals
 Polycom, Inc. -> Polycom

Eu encontrei os tópicos a seguir que parecem semelhantes a essa pergunta, mas o pôster não foi aprovado e não tenho certeza se seu caso de uso é aplicável:

Como encontrar a melhor correspondência difusa para uma cadeia de caracteres em um database de cadeias de caracteres grande

Correspondência de nomes de empresas inexatos em Java

Você pode começar usando SOUNDEX() , isso provavelmente fará o que for necessário (imagino uma checkbox de sugestão automática de alternativas já existentes para o que o usuário está digitando).

As desvantagens do SOUNDEX() são:

  • sua incapacidade de diferenciar cordas mais longas. Somente os primeiros caracteres são considerados, strings maiores que divergem no final geram o mesmo valor SOUNDEX
  • o fato de que a primeira letra deve ser a mesma ou você não encontrará uma correspondência facilmente. O SQL Server tem a function DIFFERENCE () para dizer o quanto dois valores SOUNDEX estão separados, mas acho que o MySQL não tem nada desse tipo embutido.
  • para o MySQL, pelo menos de acordo com os documentos , SOUNDEX é quebrado para input unicode

Exemplo:

 SELECT SOUNDEX('Microsoft') SELECT SOUNDEX('Microsift') SELECT SOUNDEX('Microsift Corporation') SELECT SOUNDEX('Microsift Subsidary') /* all of these return 'M262' */ 

Para necessidades mais avançadas, eu acho que você precisa olhar para a distância de Levenshtein (também chamada de “distância de edição”) de duas seqüências de caracteres e trabalhar com um limite. Esta é a solução mais complexa (= mais lenta), mas permite maior flexibilidade.

A principal desvantagem é que você precisa das duas strings para calcular a distância entre elas. Com o SOUNDEX você pode armazenar um SOUNDEX pré-calculado em sua tabela e comparar / classificar / agrupar / filtrar isso. Com a distância de Levenshtein, você pode achar que a diferença entre “Microsoft” e “Nzcrosoft” é apenas 2, mas levará muito mais tempo para chegar a esse resultado.

Em qualquer caso, um exemplo da function de distância Levenshtein para o MySQL pode ser encontrado em codejanitor.com: Levenshtein Distance como uma function armazenada do MySQL (10 de fevereiro de 2007) .

SOUNDEX é um algoritmo OK para isso, mas houve avanços recentes neste tópico. Outro algoritmo foi criado, chamado Metaphone, e foi posteriormente revisado para um algoritmo Double Metaphone. Eu usei pessoalmente a implementação de java metapache do apache commons e é personalizável e preciso.

Eles também têm implementações em muitos outros idiomas na página da Wikipedia. Esta pergunta foi respondida, mas se você encontrar algum dos problemas identificados com o SOUNDEX aparecendo na sua aplicação, é bom saber que existem opções. Às vezes, pode gerar o mesmo código para duas palavras realmente diferentes. O metapofone duplo foi criado para ajudar a cuidar desse problema.

Roubado da wikipedia: http://en.wikipedia.org/wiki/Soundex

Como resposta às deficiências do algoritmo Soundex, Lawrence Philips desenvolveu o algoritmo Metaphone para o mesmo propósito. A Philips posteriormente desenvolveu uma melhoria para a Metaphone, que ele chamou de Double-Metaphone. O Double-Metaphone inclui um conjunto de regras de codificação muito maior que o seu antecessor, manipula um subconjunto de caracteres não latinos e retorna uma codificação primária e secundária para considerar as diferentes pronúncias de uma única palavra em inglês.

Na parte inferior da página do duplo metafone, eles têm implementações para todos os tipos de linguagens de programação: http://en.wikipedia.org/wiki/Double-Metaphone

Implementação em Python e MySQL: https://github.com/AtomBoy/double-metaphone

Em primeiro lugar, gostaria de acrescentar que você deve ter muito cuidado ao usar qualquer forma de Algoritmo de Correspondência Fonética / Fuzzy, pois esse tipo de lógica é exatamente isso, Fuzzy ou, para simplificar; potencialmente impreciso. Especialmente verdadeiro quando usado para correspondência de nomes de empresas.

Uma boa abordagem é buscar a confirmação de outros dados, como informações de endereço, códigos postais, números de telefone, coordenadas geográficas, etc. Isso ajudará a confirmar a probabilidade de seus dados serem correspondidos com precisão.

Há toda uma série de questões relacionadas à correspondência de dados B2B demais para serem abordadas aqui. Escrevi mais sobre Correspondência de nomes de empresas no meu blog, mas, em resumo, os principais problemas são:

  • Observar toda a seqüência de caracteres é inútil, pois a parte mais importante de um nome da empresa não está necessariamente no início do nome da empresa. ou seja, “The Proctor and Gamble Company” ou “Reserva Federal dos Estados Unidos”
  • Abreviaturas são comuns em nomes de empresas, como HP, GM, GE, P & G, D & B, etc.
  • Algumas empresas deliberadamente soletram seus nomes incorretamente como parte de sua marca e se diferenciam de outras empresas.

A correspondência de dados exatos é fácil, mas a correspondência de dados não exatos pode ser muito mais demorada e eu sugiro que você considere como você validará as correspondências não exatas para garantir que elas sejam de qualidade aceitável.

Antes de criarmos o Match2Lists.com, gastávamos pouco tempo validando correspondências difusas. Em Match2Lists, incorporamos uma poderosa ferramenta de visualização que nos permite rever correspondências não exatas, o que provou ser uma verdadeira mudança no jogo em termos de validação de partidas, reduzindo nossos custos e nos permitindo entregar resultados com muito mais rapidez.

Melhor da sorte !!

Aqui está um link para a discussão php das funções soundex no mysql e php. Eu começaria de lá, em seguida, expandir para seus outros requisitos não tão bem definidos.

Sua referência faz referência à metodologia Levenshtein para correspondência. Dois problemas. 1. É mais apropriado medir a diferença entre duas palavras conhecidas, não para pesquisar. 2. Ele discute uma solução projetada mais para detectar coisas como erros de prova (usando “Levenshtien” para “Levenshtein”) em vez de erros de ortografia (onde o usuário não sabe soletrar, digamos “Levenshtein” e digita “Levinstein”) Eu costumo associá-lo à procura de uma frase em um livro em vez de um valor de chave em um database.

EDIT: Em resposta ao comentário –

  1. Você pode pelo menos fazer com que os usuários coloquem os nomes da empresa em várias checkboxs de texto; 2. ou use um delimitador de nome não ambíguo (por exemplo, barra invertida); 3. deixar de fora artigos (“The”) e abreviaturas genéricas (ou você pode filtrar por estes); 4. Esprema os espaços e combine por isso também (então Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtre a pontuação; 6. Faça buscas nas palavras “OU” (“nuas” ou “essenciais”) – as pessoas inevitavelmente deixarão uma ou a outra às vezes.

Teste como louco e use o ciclo de feedback dos usuários.

a melhor function para correspondência difusa é levenshtein. é tradicionalmente usado por verificadores ortocharts, então esse pode ser o caminho a percorrer. há um UDF disponível aqui: http://joshdrew.com/

A desvantagem de usar o levenshtein é que ele não vai escalar muito bem. uma ideia melhor seria despejar a tabela inteira em um arquivo de dictionary personalizado do corretor ortográfico e fazer a sugestão a partir da camada do aplicativo, em vez da camada do database.

Esta resposta resulta em pesquisa indexada de quase qualquer entidade usando input de 2 ou 3 caracteres ou mais.

Basicamente, crie uma nova tabela com 2 colunas, palavra e chave. Execute um processo na tabela original contendo a coluna a ser fuzzy pesquisada. Esse processo extrairá todas as palavras individuais da coluna original e as gravará na tabela de palavras juntamente com a chave original. Durante esse processo, palavras comuns como ‘the’, ‘e’, ​​etc, devem ser descartadas.

Nós então criamos vários índices na tabela de palavras, como segue …

  • Um índice normal em minúsculas na palavra + chave
  • Um índice do segundo ao quinto caractere + chave
  • Um índice do 3º ao 6º caractere + chave

    Como alternativa, crie um índice SOUNDEX () na coluna da palavra.

Uma vez que isto está no lugar, tomamos qualquer input do usuário e procuramos usando a palavra normal = input ou LIKE input%. Nós nunca fazemos uma input LIKE%, pois estamos sempre procurando uma correspondência em qualquer um dos 3 primeiros caracteres, que são todos indexados.

Se a sua tabela original é massiva, você pode particionar a tabela de palavras em blocos do alfabeto para garantir que a input do usuário seja reduzida às linhas candidatas imediatamente.

Pode ser tarde demais, mas pode ajudar os outros. Verifique este link para fora.Ele usa as métricas de distância levenshtein, mas é muito mais rápido. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html

Intereting Posts