Estruturas de dados eficientes para criar um verificador ortográfico rápido

41

Estou tentando escrever um corretor ortográfico que deve funcionar com um dicionário bastante grande. Eu realmente quero que uma maneira eficiente de indexar os dados do meu dicionário seja usada usando uma distância Damerau-Levenshtein para determinar quais palavras estão mais próximas da palavra com erro de ortografia.

Estou procurando uma estrutura de dados que me daria o melhor compromisso entre a complexidade do espaço e a complexidade do tempo de execução.

Com base no que encontrei na internet, tenho algumas pistas sobre que tipo de estrutura de dados usar:

Trie

trie-500px

Este é o meu primeiro pensamento e parece muito fácil de implementar e deve fornecer uma rápida pesquisa / inserção. A pesquisa aproximada usando Damerau-Levenshtein deve ser simples de implementar aqui também. Mas não parece muito eficiente em termos de complexidade de espaço, já que você provavelmente tem muita sobrecarga com o armazenamento de ponteiros.

Patricia Trie

trie-500px

Isso parece consumir menos espaço que um Trie comum, já que você está basicamente evitando o custo de armazenar os ponteiros, mas estou um pouco preocupado com a fragmentação de dados no caso de dicionários muito grandes como o que tenho.

Árvore de sufixo

sufixo-500px

Não tenho certeza sobre este, parece que algumas pessoas o acham útil na mineração de texto, mas não tenho muita certeza do que isso daria em termos de desempenho para um verificador ortográfico.

Árvore de pesquisa ternária

tst

Eles parecem bem legais e em termos de complexidade devem ser próximos (melhores?) De Patricia Tries, mas não tenho certeza quanto à fragmentação se seria melhor ou pior do que Patricia Tries.

Árvore de explosão

rebentar

Isso parece meio híbrido e não tenho certeza de que vantagem isso teria sobre as tentativas e coisas do tipo, mas li várias vezes que é muito eficiente para a mineração de texto.


Gostaria de obter algum feedback sobre qual estrutura de dados seria melhor usar neste contexto e o que a torna melhor do que as outras. Se estou perdendo algumas estruturas de dados que seriam ainda mais apropriadas para um corretor ortográfico, também estou muito interessado.

Charles Menguy
fonte
Como uma patricia tenta evitar o custo de armazenar os indicadores? É apenas um en.wikipedia.org/wiki/Radix_tree ? Se for esse o caso, então eu acho que ainda guarda muitos pontos, mas você vai ter uma enorme economia de espaço, porque prefixos comuns são armazenados apenas uma vez
Joe
Sem detalhes, a comparação solicitada pode ser impossível. Em particular, qual a densidade do seu dicionário? Até que distância você deseja detectar erros de ortografia (você parece dizer ilimitado)? Qual é a densidade do dicionário + variantes? (Densidade aqui significa a fração de todas as palavras de comprimento contidas no conjunto armazenado.)n
Raphael
11
@linker: Você já tentou todas as variantes do seu dicionário? Dado um caso de uso fixo, essa é provavelmente a maneira mais rápida de descobrir qual estrutura de dados consome quanto espaço.
Raphael
11
É apenas um dicionário básico, apenas uma lista conhecida de palavras escritas corretamente.
Charles Menguy
11
Veja também esta questão mais intimamente relacionada .
Raphael

Respostas:

4

Eu encontrei o mesmo problema, mas adotou uma abordagem diferente. Você pode construir algum tipo de função "hash", que, para palavras semelhantes, fornecerá o número igual ou próximo.

O problema é que a função que dará um resultado "bom" para as palavras com inserção / remoção, dará "ruim" para a transição e vice-versa. Exemplo: mapeie letras para números, letra semelhante para números adjacentes e apenas some-as para cada letra na palavra. Em seguida, crie tabelas de hash com conjuntos para cada chave e encontre a interseção por palavra.

Pode ser que alguns resultados possam ser alcançados se observarmos o "espaço" das palavras. X para alterar a letra, Y para adicionar / remover, Z para transição ou algo assim.

No entanto, essas são apenas idéias abstratas, não tenho tempo suficiente para implementá-las.

MadRunner
fonte
Isto é o que Soundex faz en.wikipedia.org/wiki/Soundex
rgrig
4

Você pode usar uma árvore métrica para pesquisas rápidas, se a força bruta não for possível (tente sempre a força bruta). Encontrar seus vizinhos será possível em , mas a constante em pode ser grande. Você parece ter milhões de strings, portanto pode ser uma boa opção.O(log(n))O

Não armazene as strings na árvore métrica. Apenas armazene um índice e as seqüências de caracteres em uma árvore Patricia.

Não tenho certeza de qual árvore você deve usar. Depende dos seus dados e dos seus requisitos (você precisa inserir rapidamente?). Atualize sua pergunta se achar que uma árvore é mais eficiente que as outras.

Você também pode olhar para ferramentas especializadas, como o lucene.

oao
fonte