Baixe o app para aproveitar ainda mais
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
Compartilhar