Trie: a árvore de prefixos, passo a passo

Dezasseis palavras formam uma árvore, com uma letra por nó. As palavras que começam da mesma maneira partilham o início do percurso: car, card e cart passam pelos mesmos nós c, a, r. Um anel duplo assinala o nó onde termina uma palavra. Escreva uma palavra, escolha uma operação e acompanhe cada passo.

Exemplo resolvido — Trie: a árvore de prefixos, passo a passo

Trie, pesquisa de “car”: letras lidas	3, palavra guardada
Tabela de dispersão sem colisões: letras lidas	6
Palavras que começam por “car”	6: car, card, care, careful, cargo, cart
Tabela de dispersão: palavras lidas (todas)	16
A inserção de “car” acrescenta	0 nós: 0 bytes à trie, 0 à lista
Nós da trie, um por prefixo distinto	30 para 70 letras (57,1% partilhadas)
Trie com nós de 18 bytes, incluindo a raiz	558
Trie com nós de 209 bytes, um ponteiro por letra	6.479

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Trie: a árvore de prefixos, passo a passo

Uma trie, ou árvore de prefixos, guarda um conjunto de palavras numa árvore com um nó por prefixo distinto. A raiz representa o prefixo vazio. Cada aresta corresponde a uma letra, pelo que o percurso da raiz até um nó forma o prefixo desse nó. Um nó fica assinalado quando o seu prefixo é uma palavra completa guardada na árvore. Palavras com o mesmo início partilham essa parte do percurso. Uma pesquisa segue as letras da palavra a partir da raiz; uma pesquisa por prefixo chega ao nó do prefixo e lista todos os nós assinalados abaixo dele. Edward Fredkin deu o nome à estrutura em 1960, a partir de retrieval, e pretendia que se pronunciasse como a palavra inglesa tree.

O que significa cada símbolo

W: o número de palavras na lista
L: o número total de letras dessas palavras
N: o número de nós, um por prefixo distinto, sem contar a raiz

Pressupõe: Usam-se letras minúsculas de a a z, 1 byte por letra e ponteiros de 64 bits. Nenhuma das estruturas inclui bytes de alinhamento nem espaço adicional usado pelo gestor de memória. A pesquisa binária conta cada par de letras que compara e para no primeiro par diferente; chegar ao fim de uma palavra não tem custo. A tabela de dispersão não tem colisões, o melhor caso possível. O nó de 18 bytes mantém os filhos por ordem alfabética, permitindo que a pesquisa pare assim que ultrapassa a letra procurada.

A pesquisa binária lê c, a, r 4 vezes; a trie lê-as uma vez 🖖

Clique em Pesquisar car. A trie segue uma letra por passo e encontra car assinalado como palavra: 3 letras. A pesquisa binária nas mesmas 16 palavras ordenadas consulta catch, careful, card e car. Como todas começam por ca, cada comparação lê 3 letras antes de decidir em que direção continuar: 12 ao todo. A tabela de dispersão lê 3 letras para calcular uma posição e mais 3 para verificar a palavra que aí encontra: 6. Para pesquisar as 16 palavras guardadas, a trie lê 70 letras, a tabela de dispersão 140 e a pesquisa binária 169. Os prefixos comuns que poupam nós à trie tornam as comparações da pesquisa binária mais longas. Se guardarmos todas as 17 576 sequências de 3 letras, de aaa a zzz, a pesquisa binária precisa de ler, em média, 26,4 letras para encontrar uma delas; a trie continua a ler 3.

Uma lista ordenada também permite o preenchimento automático. Uma tabela de dispersão tem de ler todas as palavras 🖖

Clique em Começam por car. A trie percorre c, a, r e visita os 8 nós abaixo de car: 11 nós ao todo, dos quais 6 assinalam o fim de uma palavra. As palavras dog, plan e as restantes ficam fora do percurso. Numa lista ordenada, as palavras que começam por car ficam juntas, o que também permite limitar a pesquisa. A pesquisa binária encontra a primeira em 5 consultas. A leitura em sequência recolhe as 6 e para em cat, a primeira palavra que não corresponde ao prefixo: 12 palavras lidas. Uma tabela de dispersão distribui car, card e cargo por posições sem relação entre si; tem, por isso, de ler e verificar as 16 palavras. Ao acrescentar palavras, a trie tem uma vantagem sobre a lista ordenada. Clique em Inserir carpet: a trie acrescenta 3 nós sem deslocar nenhum, enquanto a lista ordenada desloca os ponteiros de 11 palavras uma posição para abrir espaço.

Mesmo partilhando 40 de 70 letras, a trie ocupa 2,6 vezes o espaço da lista 🖖

As 16 palavras têm 70 letras, que a trie guarda em 30 nós: car, card, care e outras palavras partilham os nós c, a, r. Cada nó, porém, precisa de guardar mais do que a letra. Na representação compacta, contém 1 byte para a letra, 1 byte para a marca de fim de palavra e 2 ponteiros de 8 bytes, um para o primeiro filho e outro para o irmão seguinte. São 18 bytes por nó; com a raiz, os 31 nós ocupam 558. A lista simples guarda cada letra num byte, mais um byte de fim de palavra e um ponteiro de 8 bytes por palavra: 214. Se cada nó tiver um ponteiro para cada letra do alfabeto, permitindo que cada passo seja um acesso por índice a um vetor, a trie ocupa 6 479 bytes, 30 vezes o espaço da lista. Com palavras de, no máximo, 14 letras, como neste exemplo, acrescentar uma palavra só ocupa menos espaço na trie se não criar nenhum nó, como aconteceria com plan numa trie que já contivesse planet, ou se criar apenas 1 nó e tiver pelo menos 10 letras. A representação compacta também tem um custo em tempo: para encontrar cada letra, percorre os nós irmãos. A pesquisa de doorbell exige então 10 comparações, mais uma do que a pesquisa binária.

Problema resolvido na íntegra

Quanta partilha é necessária para a trie ocupar menos espaço? 4 passos
Clique em Palavras longas: 85 letras em 21 nós, com três quartos das letras partilhadas. Mesmo assim, a trie com nós de 18 bytes ocupa 396 bytes, contra os 157 da lista. Entre as listas cujas palavras têm todas k letras, a situação mais favorável à trie é aquela em que a lista contém todas as palavras possíveis. Com os custos em bytes usados nesta página, qual é o menor k para o qual essa trie ocupa menos espaço do que a lista simples?

Abrir este problema na ferramenta
1. Na página, temos 21 nós mais a raiz: 22 × 18 = 396 bytes. A lista guarda 85 letras e, por cada uma das 8 palavras, um byte de fim de palavra e um ponteiro de 8 bytes: 85 + 9 × 8 = 157.
  
  $22 \times 18 = 396, 85 + 9 \times 8 = 157$
2. Há 26^k sequências possíveis de k letras. A lista que contém todas essas palavras ocupa, portanto, (k + 9) × 26^k bytes.
  
  $list = (k + 9) \cdot 2 6^{k}$
3. A trie precisa de um nó por cada sequência de 1 a k letras: 26 + 26² + … + 26^k, um pouco menos de 26/25 × 26^k. Acrescentando a raiz e multiplicando por 18, a trie ocupa pouco menos de 18,72 × 26^k bytes.
  
  $N = 26 + 2 6^{2} + \dots + 2 6^{k} = \frac{26}{25} (2 6^{k} - 1), 18 (N + 1) < 18.72 \cdot 2 6^{k}$
4. A lista passa a ocupar mais espaço quando k + 9 ultrapassa 18,72, o que acontece pela primeira vez com k = 10. Para k = 9, a trie ocupa mais 4,0% do que a lista; para k = 10, ocupa menos 1,5%.
  
  $k + 9 > 18.72 ⟺ k \geq 10 : \frac{trie}{list} = 1.040 (k = 9), 0.985 (k = 10)$
Resposta

10 letras, com todas as 26¹⁰ palavras na lista, cerca de 1,4 × 10¹⁴ palavras. Com nós de 209 bytes, a mesma soma exige que k + 9 ultrapasse aproximadamente 217: palavras de 209 letras.

$k = 10, 2 6^{10} \approx 1.4 \times 1 0^{14} words$

Percurso de aprendizagem

O que custa pouco numa estrutura de dados

Referências (3)

The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.