Trie

Entre as suas características principais estão a alta velocidade de pesquisa (com larga vantagem sobre pesquisas binárias), assim como inserção e remoção de itens, escalabilidade limitada apenas pela memória de sistema disponível, e estrutura altamente propícia para pesquisas de proximidade com wildcards.

As trie são usadas intensivamente em aplicações de dicionário, como o auto-complete dos telemóveis.

A listagem completa duma trie é feita de forma natural em ordem lexicográfica, independentemente do tipo de dados que guarda, não necessitando de qualquer algoritmo de ordenação.

Postas do blog relacionadas:

Trie - Uma estrutura de alta performance de pesquisa
Trie, o regresso - usar embedded resource
Trie contra-ataca – uso de wildcards em pesquisas, correcções e limpeza
Trie, o confronto final – contagem e eliminação

Executável e libraria. Contém o dicionário de palavras disponibilizado pela Universidade do Minho que se encontra aqui em forma de resource embebida no executável.

Classe CharTrie - Trie para tipos de dados char/string.

Executável command line interface para testar a estrutura trie. Neste momento, está a carregar um ficheiro de texto que deve ser incluído como resource e a usar a CharTrie como dicionário de aproximação com wildcards.