Qual algoritmo oferece sugestões em um corretor ortográfico?

Qual algoritmo é normalmente usado ao implementar um verificador ortográfico que é acompanhado de sugestões de palavras?

A princípio, pensei que faria sentido verificar cada nova palavra digitada (se não encontrada no dicionário) em relação à distância de Levenshtein de todas as outras palavras do dicionário e retornar os principais resultados. No entanto, isso parece altamente ineficiente, tendo que avaliar o dicionário inteiro repetidamente.

Como isso normalmente é feito?

Há um bom ensaio de Peter Norvig sobre como implementar um corretor ortográfico. É basicamente uma abordagem de força bruta tentando strings candidatas com uma determinada distância de edição. ( Aqui estão algumas dicas de como você pode melhorar o desempenho do corretor ortográfico usando um Filtro Bloom e um hash de candidato mais rápido .)

Os requisitos para um corretor ortográfico são mais fracos. Você só precisa descobrir que uma palavra não está no dicionário. Você pode usar um filtro Bloom para construir um corretor ortográfico que consome menos memória. Uma versão antiga é descrita em Programming Pearls por Jon Bentley usando 64kb para um dicionário de inglês.

Uma árvore BK é uma abordagem alternativa. Um bom artigo está aqui .

A distância de Levenshstein não é exatamente a distância de edição correta para um corretor ortográfico. Ele conhece apenas inserção, exclusão e substituição. A transposição está faltando e produz 2 para uma transposição de 1 caractere (é 1 exclusão e 1 inserção). A distância Damerau – Levenshtein é a distância correta de edição.

Uma abordagem para gerar sugestões que usei com sucesso, mas nunca vi descritas em qualquer lugar, é pré-calcular as sugestões (ao construir o dicionário) usando funções hash "ruins".

A ideia é examinar os tipos de erros ortográficos que as pessoas cometem e projetar funções hash que atribuam uma grafia incorreta ao mesmo intervalo que sua grafia correta.

Por exemplo, um erro comum é usar a vogal errado, como definate invés de definitiva . Portanto, você cria uma função hash que trata todas as vogais como a mesma letra. Uma maneira fácil de fazer isso é primeiro "normalizar" a palavra de entrada e, em seguida, colocar o resultado normalizado por meio de uma função hash regular. Neste exemplo, a função de normalização pode eliminar todas as vogais, então definitese torna dfnt. A palavra "normalizada" é então hash com uma função hash típica.

Insira todas as palavras do dicionário em um índice auxiliar (tabela de hash) usando esta função hash especial. Os baldes nesta tabela terão listas de colisão mais longas porque a função hash é "ruim", mas essas listas de colisão são essencialmente sugestões pré-calculadas.

Agora, ao encontrar uma palavra com erro ortográfico, você consulta as listas de colisão do depósito que o erro ortográfico mapeia nos índices auxiliares. Ta da: Você tem uma lista de sugestões! Tudo o que você precisa fazer é classificar as palavras nele.

Na prática, você precisará de alguns índices auxiliares com outras funções hash para lidar com outros tipos de erros, como letras transpostas, letras simples / duplas e até mesmo um simplista como o Soundex para detectar erros ortográficos. Na prática, descobri que as pronúncias simplistas são muito úteis e, essencialmente, obsoletas algumas das que foram projetadas para encontrar erros de digitação triviais.

Portanto, agora você procura erros de ortografia em cada um dos índices auxiliares e concatena as listas de colisão antes de classificar.

Lembre-se de que as listas de colisão contêm apenas palavras que estão no dicionário. Com abordagens que tentam gerar grafias alternativas (como no artigo de Peter Norvig), você pode obter (dezenas de) milhares de candidatos que primeiro você precisa filtrar no dicionário. Com a abordagem pré-computada, você obtém talvez algumas centenas de candidatos e sabe que estão todos escritos corretamente, então pode pular direto para a classificação.

Atualização : desde então, encontrei uma descrição de algoritmo semelhante a esta, a pesquisa distribuída FAROO . Esta ainda é uma pesquisa limitada pela distância de edição, mas é muito rápida porque a etapa de pré-cálculo funciona como minha ideia de "funções de hash ruins". FAROO usa apenas um conceito limitado de uma função hash ruim.

Algoritmo

1. Pegue uma palavra com grafia incorreta como entrada.
2. Armazene a lista de palavras em inglês junto com suas frequências em um arquivo de texto.
3. Insira todas as palavras em inglês disponíveis (armazenadas no arquivo de texto) junto com suas frequências (medida de quantas vezes uma palavra é usada no idioma inglês) em uma árvore de busca ternária.
4. Agora atravesse ao longo da Árvore de Busca Ternária -
   • Para cada palavra encontrada na Árvore de Busca Ternária, calcule sua Distância Levensthein da palavra escrita incorretamente.
   • Se Distância Levensthein <= 3, armazene a palavra em uma Fila de prioridade.
   • Se duas palavras têm a mesma distância de edição, aquela com maior frequência é maior. Imprima os 10 itens principais da Fila de prioridade.

Otimização

5. Você pode eliminar as palavras na subárvore do nó atual se a distância de edição da substring da palavra de entrada da palavra atual for maior do que 3.

   ---

   Você pode encontrar a explicação mais detalhada e o código-fonte no projeto github .

Você não precisa saber a distância de edição exata para cada palavra no dicionário. Você pode parar o algoritmo depois de atingir um valor limite e excluir a palavra. Isso economizará muito tempo de computação.

O corretor ortográfico é muito fácil de implementar como no programa de ortografia Unix. O código-fonte está disponível publicamente. A correção pode estar envolvida, uma técnica é fazer edições e verificar novamente se esta nova palavra está no dicionário. Essas novas edições podem ser agrupadas e mostradas ao usuário.

O sistema Unix usa um programa escrito por Mc IllRoy. Uma forma alternativa é usar um Trie que pode ser útil no caso de arquivos grandes.

• Minha experiência Trie
• Experimento tipo Unix

A abordagem unix precisa de muito menos espaço para um dicionário enorme, pois usa um algoritmo de dispersão de hash.