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

114

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?

Mithrax
fonte

Respostas:

203

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.

Thomas Jung
fonte
2
1 para a referência BK-Tree relativamente desconhecida. É assim que empresas como o Google, trabalhando com a quantidade de dados do Real-World TM, estão fazendo isso.
NoozNooz42
2
Há uma explicação muito melhor sobre as árvores BK aqui .
Ian Boyd
17

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.

Adrian McCarthy
fonte
Obrigado por fazer referência ao algoritmo SymSpell de Faroos. Embora ambos os algoritmos estejam pré-calculando possíveis erros de digitação e usando uma tabela de hash para pesquisa rápida, a principal diferença é que o SymSpell garante detectar todos os erros ortográficos possíveis até uma certa distância de edição (neste aspecto, SymSpell é equivalente ao algoritmo de Peter Norvig, apenas 3..6 ordens de magnitude mais rápido), enquanto seu algoritmo está usando uma abordagem heurística que detectará apenas um subconjunto limitado de todos os erros ortográficos teoricamente possíveis (portanto, seu custo de pré-cálculo pode ser menor).
Wolf Garbe
O algoritmo SymSpell explicitamente pré-calcula e armazena possíveis erros de digitação, meu esquema de "hash ruim" não. Para o inglês, é trivial adicionar apenas um hash fonético simplista que cubra muito terreno (por exemplo, "terradacktle" -> "pterodáctilo", que tem uma distância de edição de 6). Concedido, se você precisar de pesquisas multilíngues, então pode ser muito mais difícil.
Adrian McCarthy
Com certeza, ao explorar o conhecimento empírico sobre erros de digitação prováveis ​​(e restringir-se a eles), você economiza tempo e espaço pré-cálculo. Mas para cobrir todos os erros ortográficos possíveis, o SymSpell precisa pré-calcular apenas uma pequena fração deles. Uma palavra de 5 letras tem cerca de 3 milhões de erros ortográficos possíveis dentro de uma distância de edição máxima de 3, mas com SymSpell você precisa pré-calcular e armazenar apenas 25 exclusões. Isso é importante para pesquisa difusa / similaridade além da correção ortográfica, onde não existe conhecimento empírico.
Wolf Garbe
7

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

  1. 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 .
amarjeetAnand
fonte
Hmm, a distância Levenshtein de 'ralador' para 'maior' neste caso não seria suficiente, já que 'ralador' também é uma palavra de dicionário. ;-)
Tony Brasunas
1
@TonyBrasunas, sim você tem razão. Mas o programa irá realmente retornar uma lista de 10 palavras no caso de 'ralador' como entrada e irá sugerir 'ralador' com distância de edição de 0 e também 'maior' com distância de edição de 1. O que pode ser de alguma ajuda. ;)
amarjeetAnand
Se um candidato tem uma distância de 2, mas é extremamente frequente, e outro candidato tem uma distância de 1, mas é extremamente raro, como você classifica os dois? Na abordagem acima, o item raro sempre venceria, esse é o resultado certo?
speedplane
@speedplane Sim. o raro vai ganhar. E acho que é o resultado certo. Porque o que esperamos é a palavra mais próxima, com base na grafia da palavra de entrada. Se você ainda estiver em dúvida, pense assim --- suponha que haja uma palavra rara que o usuário digitou corretamente. Agora sua distância é 0, mas a frequência é muito baixa. Agora, nas sugestões, devemos listar esta palavra rara (com distância 0) no topo (porque menos a distância de edição ganha) e outras palavras com distância 1-2-3, abaixo.
amarjeetAnand
3

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.

Petr Peller
fonte
1

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.

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

Harisankar Krishna Swamy
fonte