Trie

As trie são estruturas em árvore que servem para guardar arrays associativos ou simples, sendo a primeira a aplicação mais comum. Podem substituir com vantagem outras estruturas de dados, como dicionários, listas linkadas ou hashtables.

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áveis

Executáveis

TrieTest

v. 1.9 @ 06-04-2010 às 01:14

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.

Código Fonte

Código Fonte

CharTrie

v. 1.9 @ 06-04-2010 às 01:14

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

TrieTest

v. 1.9 @ 06-04-2010 às 01:14

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.