Como você implementa um “Você quis dizer”?[duplicado]

https://stackoverflow.com/questions/41424

09-06-2019
|

Pergunta

Possível duplicata:
Como o Google "você quis dizer?" Trabalho de algoritmo?

Suponha que você já tenha um sistema de pesquisa em seu site.Como você pode implementar o "Você quis dizer:<spell_checked_word>"como o Google faz em alguns consultas de pesquisa?

Solução

Na verdade, o que o Google faz não é trivial e, a princípio, contra-intuitivo.Eles não fazem nada como verificar um dicionário, mas sim usam estatísticas para identificar consultas "semelhantes" que retornaram mais resultados do que a sua consulta. O algoritmo exato, obviamente, não é conhecido.

Existem diferentes subproblemas para resolver aqui, como base fundamental para todas as estatísticas relacionadas ao Processamento de Linguagem Natural, existe um livro obrigatório: Fundação do Processamento Estatístico de Linguagem Natural.

Concretamente, para resolver o problema de similaridade entre palavras/consultas, obtive bons resultados com o uso Editar distância, uma medida matemática de similaridade de strings que funciona surpreendentemente bem.Eu costumava usar Levenshtein, mas pode valer a pena dar uma olhada nos outros.

Soundex - na minha experiência - é uma porcaria.

Na verdade, armazenar e pesquisar com eficiência um grande dicionário de palavras com erros ortográficos e obter recuperação em menos de um segundo não é trivial, sua melhor aposta é fazer uso dos mecanismos existentes de indexação e recuperação de texto completo (ou seja,não o do seu banco de dados), dos quais Lucena é atualmente um dos melhores e coincidentemente portado para muitas plataformas.

Outras dicas

O Dr. Norvig do Google descreveu como funciona;ele até fornece uma implementação Python de 20 linhas:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

Dr Norvig também discute o "você quis dizer" em essa excelente palestra.Dr. Norvig é chefe de pesquisa no Google - quando questionado sobre como "você quis dizer" é implementado, sua resposta é autoritário.

Portanto, é uma verificação ortográfica, presumivelmente com um dicionário dinâmico criado a partir de outras pesquisas ou até mesmo de frases reais da Internet e coisas assim.Mas isso ainda é verificação ortográfica.

SOUNDEX e outros palpites não dão uma olhada, pessoal!

Verificar esse artigo na Wikipedia sobre a distância de Levenshtein.Certifique-se de dar uma boa olhada nas possíveis melhorias.

Fiquei agradavelmente surpreso que alguém tenha perguntado como criar um sistema de sugestão ortográfica de última geração para mecanismos de pesquisa.Trabalho neste assunto há mais de um ano para uma empresa de mecanismos de busca e posso apontar informações de domínio público sobre o assunto.

Como foi mencionado em um post anterior, o Google (e a Microsoft e o Yahoo!) não usam nenhum dicionário predefinido nem empregam hordas de linguistas que ponderam sobre os possíveis erros ortográficos das consultas.Isso seria impossível devido à escala do problema, mas também porque não está claro se as pessoas poderiam realmente identificar corretamente quando e se uma consulta está escrita incorretamente.

Em vez disso, existe um princípio simples e bastante eficaz que também é válido para todas as línguas europeias.Obtenha todas as consultas exclusivas em seus logs de pesquisa, calcule a distância de edição entre todos os pares de consultas, assumindo que a consulta de referência é aquela que tem a contagem mais alta.

Este algoritmo simples funcionará muito bem para muitos tipos de consultas.Se você quiser ir para o próximo nível, sugiro que leia o artigo da Microsoft Research sobre esse assunto.Você pode encontrá lo aqui

O artigo tem uma ótima introdução, mas depois disso você precisará ter conhecimento de conceitos como o Modelo Oculto de Markov.

Eu sugeriria olhar SOUNDEX para encontrar palavras semelhantes em seu banco de dados.

Você também pode acessar o próprio dicionário do Google usando o Solicitação de sugestão de ortografia da API do Google.

Você pode querer dar uma olhada em "Como escrever um corretor ortográfico" artigo.

Acredito que o Google registra todas as consultas e identifica quando alguém faz uma correção ortográfica.Esta correção pode então ser sugerida quando outros fornecerem a mesma primeira consulta.Isso funcionará para qualquer idioma, na verdade, qualquer sequência de caracteres.

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

Acho que isso depende do tamanho do seu site.Em nossa intranet local, que é usada por cerca de 500 funcionários, simplesmente olho as frases de pesquisa que retornaram zero resultados e insiro essa frase de pesquisa com a nova frase de pesquisa sugerida em uma tabela SQL.

Eu chamo essa tabela se nenhum resultado de pesquisa for retornado; no entanto, isso só funciona se o site for relativamente pequeno e só faço isso para frases de pesquisa que são as mais comuns.

Você também pode querer dar uma olhada na minha resposta a uma pergunta semelhante:

"Postagens semelhantes" como funcionalidade usando o MS SQL Server?

Se você tiver traduções específicas do setor, provavelmente precisará de um dicionário de sinônimos.Por exemplo, trabalhei na indústria de joias e havia abreviaturas em nossas descrições como kt - quilate, rd - redondo, cwt - peso em quilates...O Endeca (o mecanismo de busca desse trabalho) possui um dicionário de sinônimos que traduz erros ortográficos comuns, mas requer intervenção manual.

eu faço isso com Lucenade Verificador ortográfico.

Soundex é bom para correspondências fonéticas, mas funciona melhor com nomes de pessoas (foi originalmente desenvolvido para dados de censo)

Confira também Full-Text-Indexing, a sintaxe é diferente da lógica do Google, mas é muito rápida e pode lidar com elementos de linguagem semelhantes.

Soundex e "Rotemização de Porter" (soundex é trivial, não tenho certeza sobre a lematização de Porter).

Existe algo chamado aspell que pode ajudar:http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

Há uma joia de rubi para isso, mas não sei como falar com ela em pythonhttp://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Aqui está uma citação da implementação Ruby

Uso

Aspell permite verificar palavras e sugerir correções.Por exemplo:

  string = "my haert wil go on"

  string.gsub(/[\w\']+/) do |word|
    if !speller.check(word)
      # word is wrong
      puts "Possible correction for #{word}:"
      puts speller.suggest(word).first
    end
  end

Isso produz:

Possível correção para haert:Correção possível do coração para Wil:Vai

Implementar a correção ortográfica para mecanismos de pesquisa de maneira eficaz não é trivial (você não pode simplesmente calcular a distância de edição/levenshtein para cada palavra possível).Uma solução baseada em índices k-gram é descrita em Introdução à recuperação de informações (texto completo disponível online).

Você poderia usar ngram para comparação: http://en.wikipedia.org/wiki/N-gram

Usando o módulo python ngram: http://packages.python.org/ngram/index.html

import ngram

G2 = ngram.NGram([  "iis7 configure ftp 7.5",
                    "ubunto configre 8.5",
                    "mac configure ftp"])

print "String", "\t", "Similarity"
for i in G2.search("iis7 configurftp 7.5", threshold=0.1):
    print i[1], "\t", i[0]

Você entendeu:

>>> 
String  Similarity
0.76    "iis7 configure ftp 7.5"    
0.24    "mac configure ftp"
0.19    "ubunto configre 8.5"

Por que não usar o Google, você quis dizer em seu código. Para saber como, veja aquihttp://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow