Como o Google “Você quis dizer?” Algoritmo funciona?

Eu tenho desenvolvido um site interno para uma ferramenta de gerenciamento de portfólio. Há muitos dados de texto, nomes de empresas, etc. Tenho ficado muito impressionado com a capacidade de alguns mecanismos de pesquisa de responder rapidamente a consultas com “Você quis dizer: xxxx”.

Eu preciso ser capaz de fazer uma consulta de usuário de forma inteligente e responder não apenas com resultados de pesquisa brutos, mas também com uma pergunta “Você quis dizer?” resposta quando há uma resposta alternativa altamente provável, etc.

[Estou desenvolvendo no asp.net (VB – não segure isso contra mim!)]

ATUALIZAÇÃO: OK, como posso imitar isso sem os milhões de “usuários não pagos”?

  • Gerar erros de digitação para cada termo “conhecido” ou “correto” e realizar pesquisas?
  • Algum outro método mais elegante?

    Aqui está a explicação diretamente da fonte (quase)

    Pesquisa 101!

    a min 22:03

    Vale a pena assistir!

    Basicamente e de acordo com Douglas Merrill, ex-CTO do Google, é assim:

    1) Você escreve uma palavra (grafada incorretamente) no google

    2) Você não encontra o que queria (não clique em nenhum resultado)

    3) Você percebe que digitou errado a palavra para rewrite a palavra na checkbox de pesquisa.

    4) Você encontra o que você quer (você clica nos primeiros links)

    Esse padrão multiplicado por milhões de vezes mostra quais são os erros ortocharts mais comuns e quais são as correções mais “comuns”.

    Desta forma, o Google pode quase instantaneamente oferecer correção ortográfica em todos os idiomas.

    Também isso significa que, se durante a noite todos começarem a soletrar a noite como “nigth”, o Google sugeriria essa palavra.

    EDITAR

    @ ThomasRutter: Douglas descreve-o como “aprendizado de máquina estatística”.

    Eles sabem quem corrige a consulta, porque eles sabem qual consulta vem de qual usuário (usando cookies)

    Se os usuários fizerem uma consulta, apenas 10% dos usuários clicarem em um resultado e 90% voltar e digitar outra consulta (com a palavra corrigida) e, dessa vez, que 90% clicam em um resultado, eles sabem que encontraram uma correção.

    Eles também podem saber se essas são “relacionadas” consultas de dois diferentes, porque eles têm informações de todos os links que eles mostram.

    Além disso, eles agora incluem o contexto na verificação ortográfica, de modo que podem até sugerir palavras diferentes dependendo do contexto.

    Veja esta demonstração do google wave (@ 44m 06s) que mostra como o contexto é levado em consideração para corrigir automaticamente a ortografia.

    Aqui é explicado como funciona o processamento de linguagem natural.

    E finalmente, aqui está uma demonstração incrível do que pode ser feito adicionando tradução automática (@ 1h 12m 47s) à mixagem.

    Eu adicionei âncoras de minuto e segundos aos vídeos para pular diretamente para o conteúdo, se eles não funcionarem, tente recarregar a página ou rolar a mão para a marca.

    Eu encontrei este artigo há algum tempo: Como escrever um corretor ortográfico , escrito por Peter Norvig (diretor de pesquisa da Google Inc.).

    É uma leitura interessante sobre o tópico “correção ortográfica”. Os exemplos estão no Python, mas são claros e simples de entender, e acho que o algoritmo pode ser facilmente traduzido para outros idiomas.

    Abaixo segue uma breve descrição do algoritmo. O algoritmo consiste em duas etapas, preparação e verificação de palavras.

    Etapa 1: Preparação – configurando o database de palavras

    O melhor é se você pode usar palavras de pesquisa reais e sua ocorrência. Se você não tem que um grande conjunto de texto pode ser usado em seu lugar. Conte a ocorrência (popularidade) de cada palavra.

    Etapa 2. Verificação de palavras – encontrar palavras semelhantes às verificadas

    Similar significa que a distância de edição é baixa (tipicamente 0-1 ou 0-2). A distância de edição é o número mínimo de inserções / exclusões / alterações / trocas necessárias para transformar uma palavra em outra.

    Escolha a palavra mais popular da etapa anterior e sugira-a como uma correção (se diferente da própria palavra).

    Para a teoria do algoritmo “você quis dizer”, você pode consultar o Capítulo 3 de Introdução à Recuperação de Informações. Está disponível online gratuitamente. A seção 3.3 (página 52) responde exatamente à sua pergunta. E para responder especificamente a sua atualização, você só precisa de um dictionary de palavras e nada mais (incluindo milhões de usuários).

    Hmm … Eu pensei que o google usava seu vasto corpus de dados (a internet) para fazer um sério NLP (Natural Language Processing).

    Por exemplo, eles têm tantos dados da Internet inteira que podem contar o número de vezes que uma sequência de três palavras ocorre (conhecida como um trigrama ). Então, se eles virem uma frase como: “concerto rosa do frugr”, eles poderão ver que tem poucos accesss, e então encontrar o mais provável “concerto rosa” em seu corpus.

    Eles aparentemente fazem apenas uma variação do que Davide Gualano estava dizendo, então, definitivamente leia esse link. O Google, é claro, usa todas as páginas da web que conhece como um corpus, o que torna seu algoritmo particularmente eficaz.

    Meu palpite é que eles usam uma combinação de um algoritmo de distância de Levenshtein e as massas de dados que coletam em relação às pesquisas que são executadas. Eles podem fazer um conjunto de pesquisas com a distância mais curta de Levenshtein da string de pesquisa inserida e escolher aquela com o maior número de resultados.

    Normalmente, um corretor ortográfico de produção utiliza várias metodologias para fornecer uma sugestão de ortografia. Alguns são:

    • Decida uma maneira de determinar se a correção ortográfica é necessária. Estes podem include resultados insuficientes, resultados que não são específicos ou precisos o suficiente (de acordo com alguma medida), etc.

    • Use um corpo grande de texto ou um dictionary, onde todos, ou a maioria, seja corretamente grafada. Estes são facilmente encontrados online, em locais como o LingPipe . Em seguida, para determinar a melhor sugestão, procure uma palavra que seja a correspondência mais próxima com base em várias medidas. O mais intuitivo é um personagem similar. O que foi demonstrado por meio de pesquisa e experimentação é que duas ou três correspondências de sequência de caracteres funcionam melhor. (bigramas e trigramas). Para melhorar ainda mais os resultados, pese uma pontuação mais alta em uma partida no início ou no final da palavra. Por motivos de desempenho, indexe todas essas palavras como trigramas ou bigramas, de modo que, ao executar uma pesquisa, você converta para n-grama e pesquise via hashtable ou trie.

    • Use heurísticas relacionadas a possíveis erros do teclado com base na localização do personagem. Então, “hwllo” deve ser “olá” porque “w” está perto de ‘e’.

    • Use uma chave fonética (Soundex, Metaphone) para indexar as palavras e procurar possíveis correções. Na prática, isso normalmente retorna resultados piores do que usar a indexação n-gram, conforme descrito acima.

    • Em cada caso, você deve selecionar a melhor correção em uma lista. Isso pode ser uma métrica de distância, como levenshtein, a métrica de teclado, etc.

    • Para uma frase com várias palavras, somente uma palavra pode ser digitada incorretamente. Nesse caso, você pode usar as palavras restantes como contexto para determinar a melhor correspondência.

    Use a distância Levenshtein e crie uma Árvore Métrica (ou tree Slim) para indexar palavras. Em seguida, execute uma consulta 1-Nearest Neighbor e você obteve o resultado.

    O Google aparentemente sugere consultas com melhores resultados, não com as que estão escritas corretamente. Mas neste caso, provavelmente um corretor ortográfico seria mais viável. É claro que você poderia armazenar algum valor para cada consulta, com base em alguma métrica de como os bons resultados retornam.

    Assim,

    1. Você precisa de um dictionary (inglês ou baseado em seus dados)

    2. Gere uma palavra treliça e calcule probabilidades para as transições usando seu dictionary.

    3. Adicione um decodificador para calcular a distância mínima de erro usando sua treliça. É claro que você deve cuidar de inserções e exclusões ao calcular distâncias. Coisa divertida é que o teclado QWERTY maximiza a distância se você apertar as teclas próximas umas das outras (cae iria virar carro, cay viraria gato)

    4. Retorna a palavra que tem a distância mínima.

    5. Em seguida, você pode comparar isso com seu database de consulta e verificar se há melhores resultados para outras correspondências próximas.

    Aqui está a melhor resposta que encontrei , o corretor ortográfico implementado e descrito pelo diretor de pesquisa do Google, Peter Norvig.

    Se você quiser ler mais sobre a teoria por trás disso, você pode ler o capítulo de seu livro .

    A ideia deste algoritmo é baseada em aprendizado de máquina estatístico.

    sobre a sua pergunta como imitar o comportamento sem ter toneladas de dados – por que não usar toneladas de dados coletados pelo google? Faça o download dos resultados do Google Sarch para a palavra incorreta e pesquise “Você quis dizer:” no HTML.

    Eu acho que isso é chamado de mashup hoje em dia 🙂

    Como um palpite … poderia

    1. busca por palavras
    2. se não for encontrado, use algum algoritmo para tentar “adivinhar” a palavra.

    Poderia ser algo da IA ​​como rede Hopfield ou rede de propagação reversa, ou algo mais “identificando impressões digitais”, restaurando dados quebrados, ou correções ortográficas como Davide já mencionou …

    Eu vi algo sobre isso alguns anos atrás, então pode ter mudado desde então, mas aparentemente eles começaram analisando seus logs para os mesmos usuários enviando consultas muito semelhantes em um curto espaço de tempo, e usaram o aprendizado de máquina baseado em como os usuários tinham corrigido si mesmos.

    Simples. Eles têm toneladas de dados. Eles têm statistics para todos os termos possíveis, com base na frequência com que são consultados e quais variações geralmente geram resultados nos quais os usuários clicam … então, quando eles virem que você digitou um erro de ortografia frequente para um termo de pesquisa, vá em frente e proponha a resposta mais usual.

    Na verdade, se o erro de ortografia for o termo pesquisado com mais frequência, o algorythm o levará para o correto.

    Você quer dizer corretor ortográfico? Se é um verificador ortográfico, em vez de uma frase inteira, então eu tenho um link sobre a verificação ortográfica onde o algoritmo é desenvolvido em python. Verifique este link

    Enquanto isso, também estou trabalhando em projetos que incluem a pesquisa de bancos de dados usando texto. Eu acho que isso resolveria seu problema

    Além das respostas acima, caso você queira implementar algo por si mesmo rapidamente, aqui está uma sugestão –

    Algoritmo

    Você pode encontrar a implementação e documentação detalhada deste algoritmo no GitHub .

    • Crie uma fila de prioridade com um comparador.
    • Crie uma Árvore de Pesquisa Ternay e insira todas as palavras em inglês ( da postagem de Norvig ) junto com suas frequências.
    • Comece a percorrer o TST e para cada palavra encontrada no TST, calcule sua Distância de Levenshtein ( LD ) de input_word
    • Se LD ≤ 3, coloque-o em uma Fila Prioritária.
    • Por último extrair 10 palavras da fila de prioridade e exibir.

    A maneira mais fácil de descobrir isso é com a programação dinâmica do Google.

    É um algoritmo que foi emprestado da Information Retrieval e é usado intensamente na bioinformática moderna para ver como são semelhantes as duas seqüências gênicas.

    Solução ideal usa programação dinâmica e recursion.

    Este é um problema muito resolvido com muitas soluções. Basta procurar pelo Google até encontrar algum código-fonte aberto.

    Existe uma estrutura de dados específica – tree de pesquisa ternária – que naturalmente suporta correspondências parciais e correspondências próximas a vizinhas.

    Essa é uma pergunta antiga e estou surpreso que ninguém tenha sugerido o OP usando o Apache Solr.

    O Apache Solr é um mecanismo de pesquisa de texto completo que, além de muitas outras funcionalidades, também fornece verificação ortográfica ou sugestões de consulta. Da documentação :

    Por padrão, os verificadores de ortografia do Lucene classificam as sugestões primeiro pela pontuação do cálculo da distância das seqüências de caracteres e segundo pela freqüência (se disponível) da sugestão no índice.