Questão 07:
É uma estrutura na
qual as chaves são tratadas caractere a caractere , implementada por
estruturas dinâmicas , na qual cada letra é mantida numa variável
dinâmica. Abaixo temos a construção de uma Trie com as palavras do
enunciado.
Questão 08:
- Constrói-se um
vetor de registros que contém dois campos: dado e apontadorPalavra.
Esse vetor tem o tamanho do número de letras do alfabeto, de forma
ordenada.
- A palavra a ser
pesquisada é lida e a partir do seu primeiro caracter sabe-se a sua
respectiva posição no vetor.
- Acessa-se
diretamente essa posição no vetor. A associação da letra com a
posição no vetor seria através do seu respectivo valor na tabela
ASCII.
- No nó os
caracteres são percorridos e comparados com o da palavra buscada,
caso resulte em verdadeiro uma variável contadora é incrementada e
o próximo caracter é comparado, caso falso apenas passa para outro
caracter.
- Se ao fim da
palavra a variavél contadora for igual ao número de letras da
palavra buscada a consulta resulta em sucesso, caso contraŕio a
palavra buscada não está armazenada.
Este comentário foi removido pelo autor.
ResponderExcluirCom Trie, podemos inserir e encontrar strings em O(k) tempo onde K representa o comprimento de uma única palavra. Isto é obviamente rápido. Isso também é mais rápido do que hashing por causa das maneiras que é implementado. Não é necessário calcular qualquer função de hash. Nenhuma manipulação de colisão é necessária (como fazemos em endereçamento aberto e encadeamento separado).
ResponderExcluirNa trie dinâmica é também aterrado os ponteiros laterais
ResponderExcluirPode ser acrescentado um campo booleano para indicação do final da palavra. Caso o booleano seja verdadeiro é o fim da palavra, caso contrário ainda teria mais carateres.
ResponderExcluirEm relação a questão 7, eu tenho uma dúvida, como que foi feita a montagem da trie? mais especificamente na formação das palavras, eu pego todas as letras que iriam compor a palavra até chegar em NULL?
ResponderExcluirEste comentário foi removido pelo autor.
ResponderExcluirsabendo que a composição de cada no possui:
ResponderExcluir-caracter
-próxima palavra
-próximo caracter
Considere uma palavra com n caracteres a ser inserida:
Na montagem da trie dinamica ao inserir um novo elemento , haverá uma verificação dos caracteres em comum. A partir do momento que o caractere da posição i<=n for diferente, o ponteiro (próxima palavra) do nó , ira receber o caractere diferente(referente a palavra a ser inserida), e o mesmo ira apontar para os próximos caracteres referente a sua palavra caso exista(m) mais caractere(s).
exemplo açai e coco
a->c
ç o
a c
i o
ao inserir coco , como o primeiro caracter ja é diferente entao o ponteiro proxima palavra a letra (a) ira apontar para c que no caso tem como os proximos caracteres oco formando a palavra coco
exemplo jaca e jacare:
note que a palavra jaca em si é uma ''substring'' de jacaré.Ao inserir jacaré você ira percorrer os caracteres j-a-c-a , e como jacaré tem todos os caracteres da palavra jaca então será necessário que o ponteiro (próximo caractere) referente a ultima letra "a" aponte para um caractere vazio e que o apontador (próxima palavra)deste aponte para o caractere "r" que irá apontar para "é".Vale observar que caso fosse utilizado ponteiro (próxima palavra) da ultima letra "a" o caminhamento iria formar a palavra jacré ignorando a letra "a" e reproduzindo uma palavra diferente.
j
a
c
a
()->r
____e
Qual o requisito para a montagem da estrutura da questão 7? por exemplo a palavra Caja, o c da palavra seria a letra no segunda coluna e o resto da mesma seria encontrado no vetor a direita da letra o ao que eu compreendi, mas minha duvida é o porque a montagem se dá dessa maneira.
ResponderExcluirEstrutura Trie dinâmica também pode ser útil para implementação de casamento aproximado de cadeia – quando o usuário da aplicação não tem domínio exato da chave de busca.
ResponderExcluirSobre a sugestão de Wendel de usar um campo booleano para indicar o fim da palavra: creio que essa seja uma péssima solução, já que isso teria que ser aplicado em todos os nós, o que ocasionaria em um grande desperdício de memória.
ResponderExcluirUma aplicação de trie poderia ser por exemplo um dicionário?
ResponderExcluirDessa forma teria uma letra "a" e a partir dela teria várias outras palavras que começam com "a", em seguida teria "b" e assim por diante, usando dessa forma menos espaço de armazenamento, já que iria reaproveitar a variável para várias palavras.
Será viaviáessa aplicação de trie?