Como eu faço uma correspondência difusa de nomes de empresas em MYSQL com PHP para auto-completar?

StackOverflow https://stackoverflow.com/questions/369755

Pergunta

Os meus usuários vão importar através de cortar e colar uma grande cadeia que irá conter nomes de empresas.

Eu tenho um banco de dados MYSQL existente e crescente de empresas nomes, cada um com uma company_id único.

Eu quero ser capaz de analisar através da string e atribuir a cada um dos nomes de empresas inputed pelo usuário uma correspondência difusa.

Agora, apenas fazendo um jogo seqüência straight-up, também é lento. ** Will Soundex indexação ser mais rápido? Como posso dar ao usuário algumas opções de como eles estão digitando? **

Por exemplo, alguém escreve: 

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

Eu encontrei os seguintes tópicos que parecem semelhantes a esta pergunta, mas o cartaz não aprovou e eu não tenho certeza se o seu caso de uso é aplicável:

Como para encontrar melhor correspondência difusa para uma cadeia em um grande banco de dados seqüência de

Correspondência de nomes de empresas inexatas em Java

Foi útil?

Solução

Você pode começar com o uso SOUNDEX() , isso provavelmente vai fazer o que você precisa (foto I uma caixa de auto-sugestão de alternativas já existentes para que o usuário está digitando).

As desvantagens de SOUNDEX() são:

  • sua incapacidade de diferenciar cadeias mais longas. Apenas os primeiros caracteres são tidos em conta, cadeias mais longas que divergem no final geram o mesmo valor SOUNDEX
  • o fato da primeira letra deve ser o mesmo ou você não vai encontrar um jogo facilmente. SQL Server tem função de diferença () para dizer o quanto dois valores SOUNDEX estão separados, mas acho que o MySQL não tem nada desse tipo construído em.
  • para MySQL, pelo menos de acordo com a os docs , SOUNDEX é quebrado para a entrada 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, acho que você precisa de olhar para o Levenshtein distância (também chamado "editar distância") de duas cordas e trabalhar com um limiar. Esta é a solução mais complexa (= mais lenta), mas permite a maior flexibilidade.

Principal problema é que você precisa de ambos os cordões para calcular a distância entre eles. Com SOUNDEX você pode armazenar uma SOUNDEX pré-calculadas em sua mesa e comparar / tipo / grupo / filtro sobre isso. Com a distância Levenshtein, você pode achar que a diferença entre "Microsoft" e "Nzcrosoft" é de apenas 2, mas vai demorar muito mais tempo para chegar a esse resultado.

Em qualquer caso, um exemplo função de distância Levenshtein para MySQL podem ser encontradas em codejanitor.com :. Levenshtein Distância como uma função armazenado MySQL (10 de fevereiro de 2007)

Outras dicas

SOUNDEX é um algoritmo OK para isso, mas tem havido recentes avanços sobre este tema. Outro algoritmo foi criado chamado Metaphone, e foi posteriormente revisado para um algoritmo Duplo Metaphone. Eu pessoalmente tenho usado o commons java apache implementação da dupla metaphone e é personalizável e preciso.

Eles têm implementações em muitas outras línguas na página wikipedia para ele, também. Esta pergunta foi respondida, mas se você encontrar qualquer um dos problemas identificados com o SOUNDEX aparecendo em sua aplicação, é bom saber que existem opções. Às vezes, pode gerar o mesmo código para duas palavras muito diferentes. metaphone dupla foi criado para ajudar a cuidar desse problema.

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

Como uma resposta a deficiências no Soundex algoritmo, Lawrence Philips desenvolveu o algoritmo Metaphone para a mesma finalidade. Philips depois desenvolveu uma melhoria para Metaphone, que ele chamou duas vezes Metaphone. Double-Metaphone inclui um muito maior conjunto de regras de codificação que o seu antecessor, lida com um subconjunto de caracteres não-latinos, e retorna um primário e um secundário para codificação representam diferentes pronúncias de uma única palavra em Inglês.

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

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

Em primeiro lugar, gostaria de acrescentar que você deve ter muito cuidado ao utilizar qualquer forma de Fonética / fuzzy Matching Algorithm, como esse tipo de lógica é exatamente isso, difusa ou para colocá-lo de forma mais simples; potencialmente impreciso. Especialmente verdadeiro quando usado para nomes de empresa correspondente.

Uma boa abordagem é buscar confirmação de outros dados, tais como informações de endereço, códigos postais, números de telefone, Geo Coordenadas etc Isto irá ajudar a confirmar a probabilidade dos seus dados serem combinados com precisão.

Há toda uma gama de questões relacionadas com dados B2B Matching demais para ser tratado aqui, eu escrevi mais sobre Nome da Empresa Matching no meu blog, mas em resumo as questões-chave são:

  • Olhando para a seqüência inteira é inútil como a parte mais importante de um nome da empresa não é necessariamente no início da Empresa Nome. ou seja, ‘The Proctor and Gamble Company’ ou ‘United States Federal Reserve ‘
  • abreviações são lugar comum em Empresas Nomes ou seja HP, GM, GE, P & G, D & B etc ..
  • Algumas empresas deliberadamente soletrar seus nomes incorretamente como parte de sua marca e se diferenciar de outras empresas.

Combinando dados exatos é fácil, mas os dados de correspondência não-exatas pode ser muito mais demorado e eu sugiro que você deve considerar como você estará validando os jogos que não são exatas para garantir estes são de qualidade aceitável.

Antes de nós construímos Match2Lists.com, estamos habituados a gastar uma quantidade insalubre de tempo validando partidas fuzzy. Em Match2Lists incorporamos uma poderosa ferramenta de visualização que nos permite rever jogos que não são exatas, isto provou ser uma virada de jogo real em termos de validação de jogo, reduzindo nossos custos e nos permite entregar resultados muito mais rapidamente.

Melhor da sorte !!

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

As suas referências de referência a metodologia Levenshtein para correspondência. Dois problemas. 1. É mais apropriado para medir a diferença entre duas palavras conhecidas, não para a pesquisa. 2. Ele discute uma solução projetada mais para detectar coisas como prova de erros (usando "Levenshtien" para "Levenshtein") em vez de erros de ortografia (onde o usuário não sabe como soletrar, diga "Levenshtein" e tipos em "Levinstein" . normalmente, eu associá-lo com a procura de uma frase em um livro, em vez de um valor de chave em um banco de dados.

EDIT: Em resposta ao comentário -

  1. Can-lhe pelo menos obter os usuários para colocar os nomes de empresas em várias caixas de texto; 2. ou usar um delimitador nome sem ambiguidades (digamos barra invertida); 3. Deixar de fora artigos ( "As") e abreviaturas genéricas (ou você pode filtrar para estes); 4. squoosh os espaços para fora e combinar para que também (assim Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtrar a pontuação; 6. fazer "ou" pesquisas sobre palavras ( "nu" ou "essenciais".) - as pessoas vão inevitavelmente deixar um ou outro para fora às vezes

Test como um louco e usar o loop de feedback dos usuários.

a melhor função para correspondência difusa é levenshtein. é tradicionalmente usado por corretores ortográficos, de modo que pode ser o caminho a percorrer. há uma UDF para isso disponível aqui: http://joshdrew.com/

a desvantagem de usar levenshtein é que ele não escala muito bem. uma idéia melhor poderia ser a de despejar toda a tabela em que um corretor ortográfico arquivo de dicionário personalizado e fazer a sugestão de sua camada de aplicativo em vez da camada de banco de dados.

Esta resposta resulta em pesquisa indexada de quase qualquer entidade utilizando a entrada de 2 ou 3 caracteres ou mais.

Basicamente, criar uma nova tabela com 2 colunas, palavra e chave. Executar um processo na tabela original que contém a coluna a ser difusa procurou. Este processo irá extrair cada palavra individual da coluna original e escrever estas palavras a mesa da palavra junto com a chave original. Durante este processo, que ocorre comumente palavras como 'o', 'e', ??etc, deve ser descartada.

Em seguida, criar vários índices na tabela de palavra, como se segue ...

  • A, índice minúsculas normais na palavra + tecla
  • Um índice no 2º através 5ª personagem-chave +

  • Um índice no 3º a 6 de personagem-chave +

    Como alternativa, criar um índice SOUNDEX () na coluna de palavra.

Uma vez que este está no lugar, vamos dar qualquer entrada do usuário e pesquisar usando texto normal = entrada ou entrada COMO%. Nós nunca fazemos uma entrada COMO% como estamos sempre à procura de uma partida em qualquer um dos 3 primeiros caracteres, que são todos indexados.

Se a tabela original é enorme, você pode particionar a tabela de palavra por pedaços do alfabeto para assegurar a entrada do usuário está sendo reduzida a linhas candidatas imediatamente.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top