Tries

Tries

por Bruna Meneguzzi -
Número de respostas: 5

Boa tarde,

Cheguei um pouco atrasada à aula de quinta-feira 10/05 e perdi a explicação inicial sobre Tries. Eu entendi a estrutura, mas fiquei com dúvida no vetor next[]. Quais são os índices do vetor next[]? Ele aponta ao próximo caractere, certo?

No exemplo dado em sala (anexei a imagem), eu tenho ligados ao root B, S, T, então eu presumi que root.next[] apontasse a esses caracteres.. Mas não entendi os índices... seria root.next[B] = B? 

Não sei se consegui explicar minha dúvida, mas agradeço qualquer resposta! ;)

Bruna

Anexo trie.png
Em resposta à Bruna Meneguzzi

Re: Tries

por José Coelho de Pina -

Oi Bruna,

Essa ilustração da trie é simplificada.
Uma ilustração mais realista está mais abaixo.
Note que cada nó é formado por um vetor de referências.

Quais são os índices do vetor next[]?

Na ilustração os índices são os caracteres de 'a' a 'z'.
Na implementação na aula os índices foram os caracteres de 0 a 255 (ASCII estendido).
Caracteres são números inteiros pequenos.
Alguns caracteres produzem um efeito gráfico quando exibido com algum print().
Alguns caracteres produzem um efeito não gráfico. Por exemplo '\n' (newline) ou '\t' (tab),...

Welcome to DrJava. 
> int R = 256 // R de R-Way trie (0 a 255 serão os caracteres)
> int[] v = new int[R] // vetor indexado por 0 a 255
> char c
> c = 'a'  // o mesmo que 97
'a'
> c
'a'
> int i = c
> i
97
> v[c] = 123
123
> v[c]
123
> v[97]
123
> v['\n'] = 27 // o caractere '\n' é o mesmo que 10
27
> v[10]
27
>

Ele aponta ao próximo caractere?

Se x é um Node e c é um caractere, x.next[c] é null ou um Node (=referência/apontador para um Node).
Node é composto por um vetor next[] com R referências para Node e por val

Anexo Screenshot from 2018-05-13 00-40-21.png
Em resposta à José Coelho de Pina

Re: Tries

por Daniel Silva Nunes -

Aproveitando o tópico, gostaria de esclarecer uma questão a respeito de tries nos formatos implementados em TrieST.java e TST.java.

No livro, diz que o "formato" de uma TrieST independe da ordem em que foram feitas inserções e remoções. Há um único formato de trie para um conjunto de chaves. Assim, entendi que a raiz é simplesmente um nó de valor nulo e com um array que tem valores não nulos para as posições correspondentes ao primeiro caractere de cada palavra do conjunto. Assim, se o alfabeto implementado numa TrieST tem R elementos, a raiz pode ter até R "filhos" saindo dela, e a Trie seria assim:

 

Agora numa TST, executando put("are"), put("by") e put("sea"), nessa ordem, a TST que desenhei ficou assim:

E executando as mesmas inserções mas na ordem "sea", "are", "by", a TST ficou assim:

Então, nas Tries ternárias a propriedade de que há um formato único para um conjunto de chaves deixa de valer?

Obrigado!

Em resposta à Daniel Silva Nunes

Re: Tries

por José Coelho de Pina -

Oi Daniel,

Então, nas Tries ternárias a propriedade de que há um formato único para um conjunto de chaves deixa de valer?

Perfeito! maneiro
Os seus exemplos mostram isso.

P.S. Só para registrar, no segundo desenho, o "by" deve estar left do nó que contém "a" e "re" deve estar right, ops, digo mid.

Em resposta à José Coelho de Pina

Re: Tries

por José Coelho de Pina -

Oi Daniel,

P.S. Só para registrar, no segundo desenho, o "by" deve estar left do nó que contém "a" e "re" deve estar right, ops, digo mid.

O seu desenho está perfeito.
Eu é que estava fumado... tímido