AEDII-aula13

Prévia do material em texto

1
Aula 13 – 
 Árvores P.A.T.R.I.C.I.A.
 Hashing (Parte 1)
MC3305
Algoritmos e Estruturas de Dados II
Prof. Jesús P. Mena-Chalco
jesus.mena@ufabc.edu.br
2Q-2014
2
Árvores digitais (Árvore de prefixos)
Uma árvore TRIE (ATRIE) é uma estrutura de dados do 
tipo árvore ordenada que permite a recuperação de 
informação.
A ATRIE é utilizada para armazenar um array associativo 
em que as chaves são normalmente cadeias de caracteres
A chave é uma sequencia de símbolos 
pertencentes a um alfabeto.
As chaves são armazenadas nas 
folhas da árvore, os nós internos são 
parte do caminho que direciona a busca.
Compara digitos da chave 
individualmente
3
TRIE originado de 'Information reTRIEval'
TRIE = digital tree = radix tree = prefix tree
4
Árvores TRIE
As chaves são armazenadas nas 
folhas da árvore, os nós internos são 
parte do caminho que direciona a busca
(os nós internos também podem ser 
chaves).
Palavras/Chaves:
● A
● to
● tea
● ted
● ten
● Inn
● i
● inn 
5
Árvores TRIE
 A busca se inicia na raiz.
 As busca continua com a subárvore 
associado ao símbolo/caratere 
procurado até chegar a uma folha (ou 
nó interno)
Essa estrutura permite fazer buscas 
eficiente de cadeias que 
compartilham prefixo.
6
Árvores TRIE
O método de busca digital é análogo à busca manual em 
dicionários:
Com a primeira letra da palavra são determinadas todas as 
páginas que contêm as palavras iniciadas por aquela letra e 
assim por diante.
A busca de uma chave de 
tamanho m, no pior caso terá 
um custo de O(m)
Independe do número total 
de chaves.
Depende do tamanho da 
chave procurada.
7
Árvores TRIE: Aplicações
Busca por aproximação de correspondência:
Onde podem ser localizadas dados que são semelhantes a 
uma chave informada.
 Corretor Ortográfico
 Auto-preenchimento
8
Árvores TRIE: Aplicações
Corretor ortográfico
Nesse tipo de programas, as palavras são comparadas com 
um dicionário armazenado em arquivo, e se não são 
encontradas, indica-se as opções de correção.
Palavra a ser
comparada/procurada: tex
9
Árvores PATRICIA
Auto-preenchimento
Nesse tipo de programas, a medida que vai digitando são 
exibidas as opções possíves de palavras já utilizadas.
O algoritmo compara a 
existência de correspondência 
na estrutura. 
A cada caractere digitado, são 
apresentadas as opções de 
preenchimento, e no 
momento em que só existir 
um caminho possível a ser 
seguido na TRIE ocorre o 
preenchimento automático
10
Árvores PATRICIA
Auto-preenchimento
Nesse tipo de programas, a medida que vai digitando são 
exibidas as opções possíves de palavras já utilizadas.
11
Árvores P.A.T.R.I.C.I.A.
acrônimo de
Practical Algorithm To Retrieve
Information Coded In Alphanumeric
12
PATRICIA
13
Árvores PATRICIA
TRIE compactada binária.
Caminhos que possuem nós com apenas 1 filho são 
agrupados em uma única aresta.
Diferente das TRIE, não armazena informações nos nós 
internos, apenas contadores e ponteiros para cada sub-
árvore descendente.
Ou seja, nenhuma chave é prefixa de outra. 
14
Árvores PATRICIA
15
PATRICIA: Exemplo de representação
16
PATRICIA: Exemplo de representação
Registro acumulativo que 
integra todos os nós exeto nas folhas.
Identifica qual a posição do caratere
da chave informada que deve ser
analisado
17
PATRICIA: Exemplo de representação
Registro acumulativo que 
integra todos os nós exeto nas folhas.
Identifica qual a posição do caratere
da chave informada que deve ser
analisado
Indica o caractere que deve ser comparado
ao caractere da chave informada.
Similar às ABBs: Se a chave é menor ou 
Igual ao nó, ela é consultada à esquerda,
caso contrário, à direita.
18
PATRICIA: Exemplo de inserção
19
PATRICIA: Exemplo de inserção
Consulta
20
PATRICIA: Exemplo de inserção
Consulta
21
PATRICIA: Exemplo de inserção
Consulta Consulado
Consulta
22
PATRICIA: Exemplo de inserção
Consulta Consulado
Consulta
Consula
23
PATRICIA: Exemplo de inserção
Consulta Consulado
Consulta
Consula
24
PATRICIA: Exemplo de busca
25
PATRICIA: Exemplo de busca
26
PATRICIA: Exemplo de busca
27
PATRICIA: Exemplo de remoção
28
PATRICIA: Exemplo de remoção
29
PATRICIA: Exemplo de remoção
30
PATRICIA: Exemplo de remoção
31
PATRICIA
Vantagem
Permite armazenar um número de posições para qual é 
movido para fentre antes de fazer a próxima comparação.
[elimina comparações desnecessárias → melhora o desempenho]
32
PATRICIA
Desvantagem
Considera apenas 2 subárvores.
Se mais do que duas chaves são distintas na mesma posição 
do caratere, é necessário adicionar nós extras ao índice para 
separa-lo.
[Se n chaves são distintas na mesma posição, então serão necessários 
n-1 nós para separá-los.
Se muitos casos destes acontecem, é preferível utilizar TRIE]
33
Árvores
1960
TRIE
1968
PATRICIA
1972
Symmetric
Binary
B-Trees
1962
AVL
1978
Red-Black
60 70 80 9050
Anos
log(m) → 
log(n) → 
34
Sobre a busca de dados/chaves
35
Busca em tabelas (vetores/arrays)
Para se resolver os problemas de busca, inserção e remoção 
em uma tabela com n elementos, há várias maneiras:
Busca sequencial:
acesso em O(n)
36
Busca em tabelas (vetores/arrays)
Para se resolver os problemas de busca, inserção e remoção 
em uma tabela com n elementos, há várias maneiras:
Busca sequencial:
acesso em O(n)
Busca Binária:
acesso em O(log2(n))
ainda lento se n é grande (log2 (1000000) = 20)
37
Busca em tabelas (vetores/arrays)
Para se resolver os problemas de busca, inserção e remoção 
em uma tabela com n elementos, há várias maneiras:
Busca sequencial:
acesso em O(n)
Busca Binária:
acesso em O(log2(n))
ainda lento se n é grande (log2 (1000000) = 20)
Uso de árvores balanceadas:
acesso em O(log(n))
acesso bem melhor do que na busca sequencial!
Em uma árvore B, o acesso é O(logk(n)), onde k é o tamanho da folha 
(veremos no final do curso)
38
Busca em tabelas (vetores/arrays)
Não é possível achar um método mais rápido?
O(n) não é ruim em memória, mas mesmo um método 
com complexidade logaritmica é custoso.
Acesso a disco é 1.000.000 vezes mais lendo do que em 
memória.
39
Busca em tabelas (vetores/arrays)
Sim!
Tabelas de dispersão (Hash tables)
Busca com acesso médio igual a O(1).
40
Busca em tabelas (vetores/arrays)
Sim!
Tabelas de dispersão (Hash tables)
Busca com acesso médio igual a O(1).
Isso significa “constante” na média.
No pior caso é O(n).
Na medida do possível uma constante pequena.
41
HASHING (tabelas de dispersão)
42
Hashing
Hash
- Fazer picadinho (de carne e vegetais).
- Fazer bagunça.
Através de uma função h(x), a chave x é transformada em 
um endereço de uma tabela.
Como funciona?
43
Armazenamento em tabelas
Suponha que exista n chaves a serem armazenadas em uma 
tabela T, sequencial e de dimensão m.
As posições da tabela se situam no intervalo [0, m-1]
 
0 m-1
T
44
Armazenamento em tabelas
Suponha que exista n chaves a serem armazenadas em uma 
tabela T, sequencial e de dimensão m.
As posições da tabela se situam no intervalo [0, m-1]
Cada tabela é particionada em m compartimentos “buckets”, 
cada um correspondendo a um endereço e podendo 
armazenar r registros.
0 m-1
T
45
Armazenamento em tabelas
Suponha que exista n chaves a serem armazenadas em uma 
tabela T, sequencial e de dimensão m.
As posições da tabela se situam no intervalo [0, m-1]
Cada tabela é particionada em m compartimentos“buckets”, 
cada um correspondendo a um endereço e podendo 
armazenar r registros.
0 m-1
T
Se a tabela está na memória: comum r=1.
Se a tabela está armazenada no disco: 
número de acessos é mais importante do que o uso eficiente da memória. 
cada compartimento ocupa, tipicamente, um bloco de disco.
Vamos considerar somente o primeiro caso (r=1).
46
Acesso direto
Suponha que o número de chaves n seja igual igual ao 
número de compartilhamentos m.
Além disso, considere que os valores das chaves sejam, 
respectivamente, 0, 1, … ,m-1.
47
Acesso direto
Suponha que o número de chaves n seja igual igual ao 
número de compartilhamentos m.
Além disso, considere que os valores das chaves sejam, 
respectivamente, 0, 1, … ,m-1.
Pode se então, usar diretamente o valor de cada chave em 
seu índice de tabela.
→ Cada chave x armazenada no compartilhamento x.
48
Acesso direto
Suponha que o número de chaves n seja igual igual ao 
número de compartilhamentos m.
Além disso, considere que os valores das chaves sejam, 
respectivamente, 0, 1, … ,m-1.
Pode se então, usar diretamente o valor de cada chave em 
seu índice de tabela.
→ Cada chave x armazenada no compartilhamento x.
Essa técnica é chamada de Acesso Direto.
49
Acesso direto
Suponha que o número de chaves n seja igual igual ao 
número de compartilhamentos m.
Além disso, considere que os valores das chaves sejam, 
respectivamente, 0, 1, … ,m-1.
Pode se então, usar diretamente o valor de cada chave em 
seu índice de tabela.
→ Cada chave x armazenada no compartilhamento x.
Essa técnica é chamada de Acesso Direto.
Essa técnica também pode ser utilizada quando n<m, porem 
(m-n) pequeno.
50
Acesso direto
Suponha que o número de chaves n seja igual igual ao 
número de compartilhamentos m.
Além disso, considere que os valores das chaves sejam, 
respectivamente, 0, 1, … ,m-1.
Pode se então, usar diretamente o valor de cada chave em 
seu índice de tabela.
→ Cada chave x armazenada no compartilhamento x.
Essa técnica é chamada de Acesso Direto.
Essa técnica também pode ser utilizada quando n<m, porem 
(m-n) pequeno. As chaves se distribuiriam entre 0,1,...,m-1
Haveriam m-n compartimentos vazios ou espaços.
51
Problemas com o acesso direto
52
Problemas com o acesso direto
As chaves nem sempre são valores numéricos:
Exemplo: chaves com nomes de pessoas.
Solução: Contruir uma representação numérica das chaves.
Função F(chave) → {0,1,...,m-1}
53
Problemas com o acesso direto
As chaves nem sempre são valores numéricos:
Exemplo: chaves com nomes de pessoas.
Solução: Contruir uma representação numérica das chaves.
Função F(chave) → {0,1,...,m-1}
O problema dos espaços é mais grave!
Exemplo: duas chaves 0 e 999.999
Acesso direto: tabela de 1milhão de buckets, sendo que somente dois 
seriam ocupados.
54
Problemas com o acesso direto
As chaves nem sempre são valores numéricos:
Exemplo: chaves com nomes de pessoas.
Solução: Contruir uma representação numérica das chaves.
Função F(chave) → {0,1,...,m-1}
O problema dos espaços é mais grave!
Exemplo: duas chaves 0 e 999.999
Acesso direto: tabela de 1milhão de buckets, sendo que somente dois 
seriam ocupados.
Solução: o uso de tabelas de dispersão.
Precisamos de um bucket para cada chave possível.
55
Tabelas de dispersão (Hashing)
Através da aplicação de uma função conveniente (função de 
dispersão ou função hash), a chave é transformada em um 
endereço de tabela (endereço base).
hash(chave) → {0, 1, … ,m-1} Note: m, não n.
56
Tabelas de dispersão (Hashing)
Através da aplicação de uma função conveniente (função de 
dispersão ou função hash), a chave é transformada em um 
endereço de tabela (endereço base).
O método aproveita a possíbilidade de acesso randômico a 
memória para alcançar uma complexidade média O(1), sendo 
o pior caso, entretanto, O(n)
hash(chave) → {0, 1, … ,m-1} Note: m, não n.
57
Tabelas de dispersão
HASHING: o endereço base gerado pela função de 
dispersão deve parecer aleatório.
58
Tabelas de dispersão
HASHING: o endereço base gerado pela função de 
dispersão deve parecer aleatório.
Isso significa que não deve existir relação óbvia entre a 
chave e a localização do registro correspondente.
59
Tabelas de dispersão
HASHING: o endereço base gerado pela função de 
dispersão deve parecer aleatório.
Isso significa que não deve existir relação óbvia entre a 
chave e a localização do registro correspondente.
Problema:
Duas chaves diferentes podem ser transformadas para o 
mesmo endereço base, de forma que dois registros podem 
ser enviados para um mesmo local de arquivo.
60
Tabelas de dispersão
HASHING: o endereço base gerado pela função de 
dispersão deve parecer aleatório.
Isso significa que não deve existir relação óbvia entre a 
chave e a localização do registro correspondente.
Problema:
Duas chaves diferentes podem ser transformadas para o 
mesmo endereço base, de forma que dois registros podem 
ser enviados para um mesmo local de arquivo.
→ Quando isso ocorre, dizemos que acontece uma colisão, 
que deve ser tratada adequadamente.
61
Exemplo
Tabela, m=12, inicializada vazia.
62
Exemplo
Adicionando a chave “Steve”
h(“Steve”) = 3
63
Exemplo
Adicionando a chave “Steve”
h(“Steve”) = 3
Para buscar “Steve” na tabela: 
● Calcule h(Steve), obtenha 3
● Vá diretamente à posição 3 e 
encontre “Steve”
● Hash table pode ser índice.
64
Exemplo
Adicionando a chave “Spark”
h(“Spark”) = 6
65
Exemplo
Adicionando a chave “Spark”
h(“Spark”) = 6
Para buscar “Zé” na tabela: 
● Calcule h(Zé) = 9.
● Leia a posição 9. Não há nada.
● Conclusão:
Zé não está na tabela.
66
Exemplo
Adicionando a chave “Notes”
h(“Notes”) = 3
h(Notes) == h(Steve)
67
Exemplo
Adicionando a chave “Notes”
h(“Notes”) = 3
h(Notes) == h(Steve)
Colisão
68
Exemplo
Adicionando a chave “Notes”
h(“Notes”) = 3
h(Notes) == h(Steve)
Colisão
Com função hash uniforme, qual a 
chance de colisão?
69
Exemplo
Adicionando a chave “Notes”
h(“Notes”) = 3
h(Notes) == h(Steve)
Colisão
Com função hash uniforme, qual a 
chance de colisão?
Depende:
→ do tamanho da tabela.
→ quantas chaves devem ser armazenadas.
70
Colisão
Existem várias formas de tratar colisões.
Onde armazenar e como encontrar Notes e Steve agora?
Importante: Colisões diminuem a eficiência.
71
Função de dispersão
Uma função de dispersão h transforma uma chave x em um 
endereço base h(x) da tabela de dispersão.
72
Função de dispersão
Uma função de dispersão h transforma uma chave x em um 
endereço base h(x) da tabela de dispersão.
73
Problema dos aniversários
74
Problema dos aniversários
75
Problema dos aniversários
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75