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

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

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

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

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

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

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.

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.

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.$\mathcal O(\log (n))$$\mathcal 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.