Como é que o Google “Você quis dizer?” trabalho algoritmo?

https://stackoverflow.com/questions/307291

08-07-2019
|

Pergunta

Eu tenho vindo a desenvolver um site interno de uma ferramenta de gestão de carteiras. Existe uma grande quantidade de dados de texto, nomes de empresas, etc. Eu tenho realmente impressionado com alguma habilidade motores de busca para muito rapidamente responder a consultas com "Você quis dizer: xxxx".

Eu preciso ser capaz de tomar forma inteligente uma consulta do usuário e responder não só com os resultados de pesquisa cru, mas também com um "Você quis dizer?" resposta quando há uma resposta altamente provável alternativa etc

[Estou desenvolvendo em ASP.NET (VB - Não segure -lo contra mim!)]

UPDATE: OK, como eu pode imitar isso sem os milhões de 'usuários não pagas'?

Gerar erros para cada ou termo 'conhecido' 'correta' e realizar pesquisas?
Algum outro método mais elegante?

Solução

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

Pesquisa 101!

em min 22:03

Vale a pena assistir!

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

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

2) Você não encontrar o que queria (não clique em qualquer resultado)

3) Você percebe que grafada a palavra que você escrever a palavra na caixa de pesquisa.

4) Você encontrar o que deseja (você clica nos primeiros links)

Este padrão multiplicado milhões de vezes, mostra o que são os mais misspells comuns e quais são as correções mais "comuns".

Desta forma, o Google pode quase instantaneamente, correção oferta feitiço em todos os idiomas.

Também Isto significa que se durante a noite todos começam a soletrar noite como google "nigth" sugeriria que a palavra em seu lugar.

Editar

@ThomasRutter: Douglas descrevê-lo como "aprendizagem de máquina estatística".

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

Se os usuários executar uma consulta, e apenas 10% dos usuários clicam em um resultado e 90% vai para trás e digite outra consulta (com a palavra corrigida) e desta vez que 90% cliques em um resultado, então eles sabem eles encontraram uma correção.

Eles também podem saber se aqueles que estão "relacionados" consultas de dois diferentes, porque eles têm informações de todos os links que eles mostram.

Além disso, eles estão agora incluindo o contexto para a verificação ortográfica, para que eles possam até mesmo sugerir palavra diferente dependendo do contexto.

Veja este demo do Google Wave (@ 06s 44m) que mostra como o contexto é levado em conta para corrigir automaticamente a ortografia.

Aqui é explicado como que a linguagem natural de processamento obras.

E, finalmente, aqui é uma demonstração impressionante do que pode ser feito adicionando automática (47s @ 1h 12m) à mistura.

_{Eu adicionei âncoras de minutos e segundos para os vídeos para saltar directamente para o conteúdo, se não funcionar, tente recarregar a página ou rolagem com a mão para a marca.}

Outras dicas

Eu encontrei este artigo há algum tempo: Como escrever um Spelling Corrector , escrito por Peter Norvig (director de investigação do Google Inc.).

É uma leitura interessante sobre o tópico "correção ortográfica". Os exemplos estão em Python, mas é clara e simples de entender, e eu acho que o algoritmo pode ser facilmente traduzidos para outras línguas.

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

Passo 1: Preparação - a criação de banco de dados palavra

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. Contagem a ocorrência (popularidade) de cada palavra.

Passo 2. Palavra verificação - encontrar palavras que são semelhante ao verificado

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

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

Para a teoria da "você quis dizer" algoritmo que você pode se referir a Capítulo 3 do Introduction to Information Retrieval. Ele está disponível on-line gratuitamente. Seção rel="noreferrer"> href="http://nlp.stanford.edu/IR-book/html/htmledition/spelling-correction-1.html" (página 52) exatamente responde a sua questão. E especificamente responder a sua atualização, você só precisa de um dicionário de palavras e nada mais (incluindo milhões de usuários).

Hmm ... Eu pensei que o Google usou seu vasto corpus de dados (internet) para fazer algumas PNL sério (Natural Language Processing).

Por exemplo, eles têm tantos dados de toda a internet que podem contar o número de vezes que uma sequência de três palavra ocorre (conhecido como trigrama ). Então, se eles vêem uma frase como: "concerto frugr rosa", eles poderiam ver que tem alguns hits, em seguida, encontrar o mais provável "* concerto rosa" em seu corpus

Eles aparentemente apenas fazer uma variação do que Davide Gualano estava dizendo, embora, por isso definitivamente ler esse link. Google faz, naturalmente, utilizar todas as páginas da web que ele conhece como um corpus, de modo que faz com que seu algoritmo particularmente eficaz.

Meu palpite é que eles usam uma combinação de um href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow noreferrer"> Levenshtein algoritmo distância

Normalmente, um corrector ortográfico produção utiliza diversas metodologias para fornecer uma sugestão de ortografia. Algumas delas são:

Decidir sobre uma maneira de determinar se a correção de ortografia é necessária. Estes podem incluir resultados insuficientes, resultados que não são suficientemente específica ou precisa (de acordo com alguma medida), etc. Então:

Use um grande corpo de texto ou um dicionário, onde todos, ou a maioria são conhecidos por ser escrito corretamente. Estes são facilmente encontrados on-line, em lugares como LingPipe . Em seguida, para determinar a melhor sugestão que você olha para uma palavra que é a correspondência mais próxima com base em várias medidas. O mais intuitivo é caracteres semelhantes. O que tem sido demonstrado através da investigação e experimentação é que dois ou três jogos de seqüência de caracteres funcionar melhor. (bigramas e trigramas). Para melhorar ainda mais os resultados, pesar uma pontuação mais elevada em cima de um jogo no início, ou no final da palavra. Por motivos de desempenho, indexar todas essas palavras como trigramas ou bigramas, de modo que quando você está realizando uma pesquisa, você converter para n-gram, e pesquisa via hashtable ou trie.
Use heurísticas relacionadas com potenciais erros de teclado com base na localização personagem. De modo que "hwllo" deve ser "Olá" porque 'w' está perto de 'e'.
Use uma chave fonético (Soundex, Metaphone) para indexar as palavras e pesquisar possíveis correções. Na prática, isto normalmente retorna piores resultados do que o uso de indexação n-grama, como descrito acima.
Em cada caso, você deve selecionar a melhor correção de uma lista. Esta pode ser uma distância métrica, como levenshtein, o teclado métrica, etc.
Para uma frase multi-word, apenas uma palavra pode ser mal escrito, no caso de você pode usar as palavras restantes como contexto para determinar a melhor partida que.

Use Levenshtein distância , em seguida, criar uma árvore métrica (ou Magro árvore) para palavras do índice. Em seguida, execute uma consulta Vizinho 1-Nearest, e você tem o resultado.

O Google aparentemente sugere consultas com melhores resultados, não com aquelas que estão escritas corretamente. Mas neste caso, provavelmente um feitiço-corretor seria mais viável, Claro que você pode armazenar algum valor para cada consulta, com base em alguma métrica de como os resultados bom ele retorna.

Assim,

Você precisa de um dicionário (Inglês ou com base em seus dados)
Gerar uma palavra treliça e probabilidades calcular para as transições através do seu dicionário.
Adicionar um decodificador para calcular a distância mínima de erro usando seus treliça. Claro que você deve cuidar de inserções e deleções ao calcular distâncias. coisa divertida é que o teclado QWERTY maximiza a distância se você bater chaves próximos uns dos outros. (cae giraria carro, cay giraria gato)
Voltar a palavra que tem a distância mínima.
Em seguida, você pode comparar isso a seu banco de dados de consulta e verifique se há melhores resultados para outras partidas próximos.

Aqui está a melhor resposta que eu encontrei , corrector ortográfico implementado e descrito por Diretor de Pesquisa do Google Peter Norvig.

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

A idéia deste algoritmo é baseado no aprendizado de máquina estatística.

Como um palpite ... Poderia

busca de palavras
se não for encontrado uso algum algoritmo para tentar "adivinhar" a palavra.

Pode ser algo do AI como rede de Hopfield ou rede de propagação para trás, ou qualquer outra coisa "identificar impressões digitais", restauração de dados quebrados, ou correções de ortografia enquanto Davide já mencionado ...

Eu vi algo sobre isso há alguns anos atrás, por isso pode ter mudado desde então, mas aparentemente eles começou por analisar seus registros para os mesmos usuários que enviam consultas muito semelhantes em um curto espaço de tempo, e máquina usada aprendizagem baseada em como usuários tinham se corrigido.

Simples. Eles têm toneladas de dados. Eles têm estatísticas para cada termo possível, com base em quantas vezes ele é consultado e quais variações de ele geralmente produzir resultados os usuários clicam ... então, quando vêem que você digitou um erro de ortografia frequente para um termo de pesquisa, eles vão em frente e propor a resposta mais comum.

Na verdade, se o erro de ortografia está em vigor o mais frequente procurou prazo, o algorythm vai levá-lo para o caminho certo.

quanto à 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 o incorreta palavra e procurar "Você quis dizer :." no HTML

Eu acho que é chamado mashup hoje em dia: -)

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

Enquanto isso, eu também estou trabalhando em projeto que inclui bancos de dados de pesquisa usando texto. Eu acho que isso iria resolver o seu problema

Esta é uma questão de idade, e eu estou surpreso que ninguém sugeriu que o OP usando Apache Solr.

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

Por padrão, o Lucene verificadores ortográficos classificar sugestões pela primeira vez pelo pontuação do cálculo seqüência de distância e segundo pela frequência (Se disponível) da sugestão no índice.

Além das respostas acima, no caso de você querer implementar algo por si mesmo rapidamente, aqui é uma sugestão -

Algoritmo

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

Criar um Priority Queue com um comparador.
Criar uma árvore Ternay Pesquisa e inserir todas as palavras Inglês (de de Norvig pós ), juntamente com as suas frequências .
Iniciar atravessando o TST e para cada palavra encontrada no TST, calcular a distância Levenshtein ( LD ) a partir input_word
Se LD = 3, em seguida, colocá-lo em uma prioridade da fila.
At Last extrato de 10 palavras a partir do Priority Queue e exibição.

Há uma estrutura de dados específica - ternário procurar árvore -. Que naturalmente suporta partidas parciais e partidas quase vizinho

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

É um algoritmo que foi emprestado de Recuperação de Informação e é muito usado nas modernas bioinformática dia para ver como semelhante duas sequências genéticas são.

Ótima solução utiliza programação dinâmica e recursão.

Este é um problema muito resolvido com muitas soluções. Apenas google até encontrar algum código-fonte aberto.

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

Não afiliado a StackOverflow