Aula 5: Pesquisa em Memória Primária e Algoritmos

ALGORITMOS E ESTRUTURAS DE DADOS II Professor Alison Zille Lopes IFNMG Campus Salinas AULA 5 PESQUISA EM MEMÓRIA PRIMÁRIA INTRODUÇÃO Pesquisar é recuperar informação a partir de uma grande massa de informação previamente armazenada A informação é dividida em registros Cada registro possui uma chave para ser usada na pesquisa Objetivo da pesquisa Encontrar uma ou mais ocorrências de registros com chaves iguais à chave de pesquisa 2 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp INTRODUÇÃO Tabela associada a entidades de vida curta criadas na memória interna durante a execução de um programa Arquivo geralmente associado a entidades de vida mais longa armazenadas em memória externa A escolha do método de pesquisa mais adequado a uma determinada aplicação depende principalmente da Quantidade dos dados envolvidos Estabilidade do arquivo se este está ou não sujeito a inserções e remoções constantes 3 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp INTRODUÇÃO É importante considerar os algoritmos de pesquisa como Tipos Abstratos de Dados com um conjunto de operações associado a uma estrutura de dados de tal forma que haja uma independência de implementação para as operações Operações mais comuns 1 Inicializar a estrutura de dados 2 Pesquisar um ou mais registros com determinada chave 3 Inserir um novo registro 4 Retirar um registro específico 5 Ordenar um arquivo para obter todos os registros em ordem de acordo com a chave 6 Ajuntar dois arquivos para formar um arquivo maior 4 INTRODUÇÃO Dicionário nome comumente utilizado para descrever uma estrutura de dados para pesquisa Dicionário é um tipo abstrato de dados com as operações Inicializa Pesquisa Insere Retira Analogia com um dicionário da língua portuguesa Chaves palavras Registros entradas associadas com cada palavra Pronúncia Definição Sinônimos Outras informações 5 PESQUISA SEQUENCIAL A pesquisa sequencial é o método de pesquisa mais simples A partir do primeiro registro as chaves são verificadas sequencialmente até encontrar a chave procurada Pesquisa Sequencial Pesquisa retorna o conjunto de dados ou o índice do registro desejado Caso não esteja presente retorna nulo ou um valor de índice inválido A implementação não suporta mais de um registro com uma mesma chave Para aplicações com esta característica é necessário incluir um argumento a mais na função Pesquisa para conter o índice a partir do qual se quer pesquisar 6 PESQUISA BINÁRIA A pesquisa em tabela pode ser mais eficiente se os registros forem mantidos em ordem Para saber se uma chave está presente na tabela 1 Compare a chave com o registro que está na posição do meio da tabela 2 Se a chave é menor então o registro procurado está na primeira metade da tabela 3 Se a chave é maior então o registro procurado está na segunda metade da tabela 4 Repita o processo até que a chave seja encontrada ou fique apenas um registro cuja chave é diferente da procurada significando uma pesquisa sem sucesso 7 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp EXEMPLOS 1 E 2 PESQUISA SEQUENCIAL E BINÁRIA 16 8 EXEMPLO 1 PESQUISA SEQUENCIAL 16 9 EXEMPLO 2 PESQUISA BINÁRIA 16 10 ÁRVORE DE BUSCA A árvore de pesquisa é uma estrutura de dados muito eficiente para armazenar informação Particularmente adequada quando existe necessidade de considerar todos ou alguma combinação de 1 Acesso direto e sequencial eficientes 2 Facilidade de inserção e retirada de registros 3 Boa taxa de utilização de memória 4 Utilização de memória primária e secundária 11 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp ÁRVORE BINÁRIA DE BUSCA Na árvore binária para qualquer nó que contenha um registro 1 Todos os registros com chaves menores estão na subárvore à esquerda 2 Todos os registros com chaves maiores estão na subárvore à direita 12 R E D ÁRVORE BINÁRIA DE BUSCA Árvore Binária de Busca sem Balanceamento O nível do nó raiz é 0 Se um nó está no nível i então a raiz de suas subárvores estão no nível i 1 A altura de um nó é o comprimento do caminho mais longo deste nó até um nó folha A altura de uma árvore é a altura do nó raiz 13 5 3 7 6 2 4 1 Altura da árvore 4 ÁRVORE BINÁRIA DE BUSCA Após construída a árvore pode ser necessário percorrer todos os registros que compõem a tabela ou arquivo Existe mais de uma ordem de caminhamento em árvores mas a mais útil é a chamada ordem de caminhamento central O caminhamento central é mais bem expresso em termos recursivos 1 caminha na subárvore esquerda na ordem central 2 visita a raiz 3 caminha na subárvore direita na ordem central Uma característica importante do caminhamento central é que os nós são visitados de forma ordenada 14 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp EXEMPLO 3 ÁRVORE DE BUSCA BINÁRIA 15 ÁRVORE BINÁRIA DE BUSCA ANÁLISE O número de comparações em uma pesquisa com sucesso melhor caso Cn O1 pior caso Cn On caso médio Cn Olog n O tempo de execução dos algoritmos para árvores binárias de pesquisa dependem muito do formato das árvores 16 Uma lista Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp ÁRVORE BINÁRIA DE BUSCA BALANCEADA Árvore completamente balanceada nós externos aparecem em no máximo dois níveis adjacentes Minimiza tempo médio de pesquisa para uma distribuição uniforme das chaves onde cada chave é igualmente provável de ser usada em uma pesquisa Contudo custo para manter a árvore completamente balanceada após cada inserção é muito alto 17 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp ÁRVORE BINÁRIA DE BUSCA BALANCEADA Para inserir a chave 1 na árvore à esquerda e obter a árvore à direita é necessário movimentar todos os nós da árvore original 18 5 3 7 6 2 4 4 2 6 5 1 3 7 Nó interno conectado à direita e à esquerda Nó externo não apresenta uma das conexões ÁRVORE BINÁRIA DE BUSCA BALANCEADA Assim seria mais adequado usar uma solução intermediária que possa manter árvore quase balanceada em vez de mantêla completamente balanceada Objetivo Procurar obter bons tempos de pesquisa próximos do tempo ótimo da árvore completamente balanceada mas sem pagar muito para inserir ou retirar da árvore Existem várias heurísticas baseadas no princípio acima Tais heurísticas utilizam critérios como redução na diferença das alturas de subárvores de cada nó da árvore redução do comprimento do caminho interno soma do nível de cada nó entre outros 19 PESQUISA DIGITAL A pesquisa digital usa a representação das chaves para estruturar os dados na memória Por exemplo a representação de um número em binário A representação de um string com uma sequência de caracteres A pesquisa digital está para árvores binárias de pesquisa como radixsort está para os métodos de ordenação Pesquisa não é baseada em comparação de chaves mas sim em processamento feito sob a chave 20 PESQUISA DIGITAL TRIE Uma Trie é uma árvore Mária cujos nós são vetores de M componentes com campos correspondentes aos dígitos ou caracteres que formam as chaves Cada nó no nível i representa o conjunto de todas as chaves que começam com a mesma sequência de i dígitos ou caracteres Este nó especifica uma ramificação com M caminhos dependendo do i 1ésimo dígito ou caractere de uma chave 21 PESQUISA DIGITAL TRIE Considerando as chaves como sequência de bits isto é M 2 temos uma Trie binária Cada nó no nível i representa o conjunto de todas as chaves que começam com a mesma sequência de i bits Cada nó tem duas ramificações uma para as chaves cujo bit i1 é zero e outra para chaves cujo bit i1 é um 22 PESQUISA DIGITAL TRIE O algoritmo de pesquisa digital é semelhante ao de pesquisa em árvore exceto que em vez de se caminhar na árvore de acordo com o resultado de comparação entre chaves caminhase de acordo com os bits de chave 23 J Q H C B 0 0 0 0 0 1 1 1 1 1 1 0 B 010010 C 110010 H 000110 J 100001 Q 000101 PESQUISA DIGITAL TRIE Fazse uma pesquisa na árvore com a chave a ser inserida Se o nó externo em que a pesquisa terminar for vazio criase um novo nó externo nesse ponto contendo a nova chave Exemplo a inserção da chave W 011011 Se o nó externo contiver uma chave criase um ou mais nós internos cujos descendentes conterão a chave já existente e a nova chave Exemplo inserção da chave K 010001 24 J Q H C B 0 0 0 0 0 1 1 1 1 1 1 0 W K 1 1 0 0 PESQUISA DIGITAL TRIE Vantagens O formato das tries não depende da ordem em que as chaves são inseridas Depende apenas dos valores das chaves Balanceamento natural Inserção e busca numa trie com N chaves aleatórias requer aproximadamente log N comparações de bits no caso médio Não depende do tamanho da chave O pior caso é limitado pelo número de bits das chaves 25 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp PESQUISA DIGITAL TRIE Desvantagens Caminhos de uma única direção acontecem quando chaves compartilham vários bits em comum Por exemplo as chaves B 01000 e C 11000 são idênticas exceto no último bit bit mais significativo Requer inspeção de todos os bits da chave independente do número de registros na trie Os registros são armazenados apenas nas folhas o que desperdiça memória em nós intermediários 26 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp EXEMPLO 4 TRIE PESQUISA DIGITAL PATRICIA PATRICIA Practical Algorithm To Retrieve Information Coded In Alphanumeric foi criado por Morrison D R 1968 para aplicação em recuperação de informação em arquivos de grande porte Knuth D E 1973 deu um novo tratamento algoritmo representadoo de forma mais clara como um caso particular de pesquisa digital essencialmente um caso de árvore trie binária Sedgewick R 1988 apresentou novos algoritmos de pesquisa e de inserção baseados nos algoritmos propostos por Knuth Gonnet GH e BaezaYates R 1991 propuzeram também outros algoritmos 28 Fonte httpwww2dccufmgbrlivrosalgoritmosslidesphp PESQUISA DIGITAL PATRICIA O algoritmo para construção da árvore PATRICIA é baseado no método de pesquisa digital mas sem o inconveniente citado para o caso das Tries O problema de caminhos de uma só direção é eliminado por meio de uma solução simples e elegante cada nó interno da árvore contém o índice do bit a ser testado para decidir qual ramo tomar 29 0 2 2 5 J Q H C B B 010010 C 110010 H 000110 J 100001 Q 000101 PESQUISA DIGITAL PATRICIA Para inserir a chave K 010001 na árvore à esquerda a pesquisa inicia pela raiz e termina quando se chega ao nó externo contendo J Os índices dos bits nas chaves estão ordenados da esquerda para a direita Bit de índice 0 de K é 1 a subárvore direita Bit de índice 2 subárvore esquerda que neste caso é um nó externo Chaves J e K mantêm o padrão de bits xxx0x1 assim como qualquer outra chave que seguir este caminho de pesquisa Novo nó interno repõe o nó J e este com nó K serão os nós externos descendentes O índice do novo nó interno é dado pelo 1 bit diferente das 2 chaves em questão que é o bit de índice 4 Para determinar qual será o descendente esquerdo e o direito verifique o valor do bit 4 de ambas as chaves 30 0 2 2 5 J Q H C B 0 2 2 5 J Q H C B 4 K PESQUISA DIGITAL PATRICIA A inserção da chave W 011011 ilustra um outro aspecto Os bits das chaves K e W são comparados a partir do primeiro bit menos significativo para determinar em qual índice eles diferem nesse caso no índice 1 Portanto o ponto de inserção agora será no caminho de pesquisa entre os nós internos de índice 0 e 2 Criase aí um novo nó interno de índice 1 cujo descendente direito é um nó externo contendo W e cujo descendente esquerdo é a subárvore de raiz de índice 2 31 0 2 2 5 J Q H C B 4 K 1 W EXEMPLO 5 PATRICIA HASHING A maioria dos métodos de pesquisa vistos até agora buscam informações armazenadas com base na comparação de suas chaves Para obtermos algoritmos eficientes armazenamos os elementos ordenados e tiramos proveito dessa ordenação algoritmos mais eficientes de busca mostrados até o momento demandam esforço computacional Olog n Hashing tabela de dispersão ou método de cálculo de endereço No caso médio é possível encontrar a chave em tempo constante 33 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING Índices em arranjos arrays ou listas lineares são utilizados para acessar informações Através do índice as operações sobre arranjos são realizadas no tempo O1 No entanto se quisermos acessar uma informação de um determinado valor não é O1 Alunos2 Ana Clara Qual o índice de Laís Como acessar este dado 34 0 1 2 3 4 5 Mara Alcides Ana Clara Carlos Laís Paulo Alunos Fonte httpwww2icuffbrboeresslideseded13pdf HASHING Logo o ideal é utilizar parte da informação em sua recuperação Hash é uma generalização da noção mais simples de um arranjo comum sendo uma estrutura de dados do tipo dicionário Dicionários são estruturas especializadas em prover as operações de inserir pesquisar e remover A ideia central do Hash é utilizar uma função aplicada sobre parte da informação chave para retornar o índice onde a informação deve ou deveria estar armazenada 35 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING Esta função que mapeia a chave para um índice de um arranjo é chamada de Função de Hashing Função de Hashing é a responsável por gerar um índice a partir de uma determinada chave O ideal é que a função forneça índices únicos para o conjunto das chaves de entrada possíveis A função de Hashing é extremamente importante pois ela é responsável por distribuir as informações pela Tabela Hash Estrutura de Dados Hash 36 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING Exemplo 37 CPF Índice 12345609800 Função de Hashing 19 14353408223 37 34523198695 50 85475643645 85 19 12345609800 João da Silva Av Canal Nº 45 37 14353408223 Maria Duarte Rua das Flores N 23 50 34523198695 Celso Dias Av Sempre Verde N 123 85 85475643645 Paula Camargo Av Perimetral N 76 Tabela Hash HASHING Tabela Hash é uma estrutura de dados especial que armazena as informações desejadas associando chaves Objetivo a partir de uma chave fazer uma busca rápida e obter o valor desejado Como representar Tabelas Hash Vetor cada posição do vetor guarda uma informação Se a função de hashing aplicada a um conjunto de elementos determinar as informações I1 I2 In então o vetor V1 n é usado para representar a tabela hash Vetor Lista Encadeada o vetor contém ponteiros para as listas que representam as informações 38 Fonte httpwww2icuffbrboeresslideseded13pdf EXEMPLO1 HASHING Considere que você deseja construir uma tabela hash que comporte 10 elementos inteiros positivos sendo a função de hash x 10 resto da divisão por 10 1 indica que não existe elemento naquela posição Ao inserir os inteiros 34 45 67 78 e 89 nesta tabela hash teríamos 39 Fonte httpdainfctutfpredubrmaurofonsecalibexefetchphpmediacursosif63cif63ced07hashpdf i 0 1 2 3 4 5 6 7 8 9 tabelaHashi 1 1 1 1 34 45 1 67 78 89 EXEMPLO1 HASHING int funcaoHashint chave return chave 10 void insereHashint tabelaHash10 int chave tabelaHashfuncaoHashchave chave int buscaHashint tabelaHash10 int chave int k k funcaoHashchave if tabelaHashk chave return k return 1 40 HASHING PERFEITO Hashing Perfeitor Para quaisquer chaves x e y diferentes a função de hashing produz saídas diferentes Exemplo Armazenamento de uma determinada turma de um curso específico Cada aluno é identificado unicamente por sua matrícula typedef struct aluno int matricula 4 bytes char nome81 1 byte 81 81 bytes char email41 1 byte 41 41 bytes Aluno Total 126 bytes 41 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING PERFEITO O número de dígitos efetivos na matrícula são 7 Para permitir um acesso a qualquer aluno em ordem constante podemos usar o número de matrícula do aluno como índice de um vetor Um problema é que pagamos um preço alto para ter esse acesso rápido Porque Resposta Visto que a matrícula é composta de 7 dígitos então podemos esperar uma matrícula variando de 0000000 a 9999999 Portanto precisaríamos dimensionar um vetor com DEZ Milhões de elementos 42 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING PERFEITO Como a estrutura de cada aluno ocupa 126 bytes então seriam necessários reservar 1260000000 bytes ou seja acima de 1 GByte de memória Na prática teríamos em torno de 50 alunos cadastrados por turma do curso sendo necessários na realidade 7300 12650 bytes Como evitar desperdício de alocação Resposta Utilizando um vetor de ponteiros em vez de um vetor de estruturas Alocação dos alunos cadastrados seria realizada dinamicamente Portanto considerando que cada ponteiro ocupa 4 bytes o gasto excedente de memória seria 40000000 bytes 38 MBytes 43 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING PERFEITO Como economizar mais usando hashing perfeito ao construir a tabela hash Resposta Identificando as partes significativas da chave 97 1 12 34 Essas partes serão utilizadas para definir a dimensão da tabela hash Considerando a parte da chamada do aluno podemos dimensionar uma tabela com 100 elementos Aluno tabelaAlunos100 44 Fonte httpwww2icuffbrboeresslideseded13pdf Chamada do aluno Código do curso Período de ingresso Ano de ingresso HASHING PERFEITO Função que aplicada sobre matrículas de alunos retorna os índices da tabela Supondo que a turma seja do 2º semestre de 2005 código 052 e do curso de Sistemas de Informação código 35 Qual seria a função de hashing perfeito int funcaoHashint matricula int valor matricula 523500 ifvalor 0 valor 99 return valor return 1 Sendo mat uma variável com a matrícula acesso tabelaAlunofuncaoHashmat 45 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING IMPERFEITO Hashing Imperfeito Existem chaves x e y diferentes para as quais a função de hashing utilizada produz saídas iguais Exemplo Suponha que queiramos armazenar as seguintes chaves C H A V E e S em um vetor de 7 posições 06 conforme a seguinte função int funcaoHashchar chave return chave7 46 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING IMPERFEITO Segundo a Tabela ASCII C 67 H 72 A 65 V 86 E 69 e S 83 47 Fonte httpwww2icuffbrboeresslideseded13pdf chave ASC II funcaoHashchave C 67 4 H 72 2 A 65 2 V 86 2 E 69 6 S 83 6 HASHING COLISÕES Quando duas ou mais chaves geram o mesmo endereço da Tabela Hash dizemos que houve uma colisão É comum ocorrer colisões Principais causas em geral o número N de chaves possíveis é muito maior que o número de entradas disponíveis na tabela não se pode garantir que as funções de hashing possuam um bom potencial de distribuição espalhamento 48 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING COLISÕES Por causa das colisões muitas Tabelas Hash são aliadas com algumas outras estruturas de dados para solucionar os problemas de colisão são elas Listas Encadeadas Árvores Balanceadas e dentro da própria tabela Um bom método de resolução de colisões é essencial não importando a qualidade da função de hashing Há diversas técnicas de resolução de colisão sendo as mais comuns enquadradas em duas categorias Encadeamento Endereçamento Aberto Rehash 49 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING COLISÕES ENCADEAMENTO A informação é armazenada em estruturas encadeadas Considerando o exemplo apresentado para o Hashing Imperfeito 50 Fonte httpwww2icuffbrboeresslideseded13pdf chave ASC II funcaoHashchave C 67 4 H 72 2 A 65 2 V 86 2 E 69 6 S 83 6 0 1 2 3 4 5 6 H A V C E S HASHING COLISÕES ENDEREÇAMENTO ABERTO REHASH No endereçamento aberto a informação é armazenada na própria Tabela Hash As colisões são resolvidas por uma segunda função de hash A técnica mais simples é o ReHash Linear também conhecida por Lista Linear Linear Probing ou Sondagem Esta técnica considera a tabela hash como uma lista linear o elemento seguinte ao último tabelaHashn1 é o primeiro tabelaHash0 e trata as colisões inserindo o elemento na primeira posição livre seguinte Isso se aplica tanto na inserção de novos elementos quanto na busca 51 HASHING COLISÕES ENDEREÇAMENTO ABERTO REHASH O ReHash Linear apresenta sérias desvantagens tendência de formação de grupos de posições ocupadas consecutivas A primeira posição vazia na prática pode ficar muito longe daquela dada pela função de hash Considerando o exemplo apresentado para o Hashing Imperfeito 52 chave ASC II funcaoTabelachave C 67 4 H 72 2 A 65 2 V 86 2 E 69 6 S 83 6 HASHING COLISÕES ENDEREÇAMENTO ABERTO REHASH Inserindo as chaves na ordem anterior e utilizando ReHash Linear para resolver as colisões teríamos 53 i 0 1 2 3 4 5 6 tabelaHashi S H A C V E i 0 1 2 3 4 5 6 tabelaHashi C i 0 1 2 3 4 5 6 tabelaHashi H C i 0 1 2 3 4 5 6 tabelaHashi H A C i 0 1 2 3 4 5 6 tabelaHashi H A C V i 0 1 2 3 4 5 6 tabelaHashi H A C V E HASHING COLISÕES BREVE ANÁLISE Cada um dos métodos apresentados tem seus prós e contras ReHash Duplo hash usa melhor a memória mas depende de um tamanho de tabela que permita que os dados continuem bem esparsos A Lista encadeada é interessante mas precisa de alocação rápida de memória A escolha de um ou outro depende da análise particular do caso A probabilidade de colisão pode ser reduzida usando uma tabela suficientemente grande em relação ao número total de posições a serem ocupadas 54 Fonte httpwww2icuffbrboeresslideseded13pdf HASHING LIMITAÇÕES O Hash é uma estrutura de dados do tipo dicionário Não permite armazenar elementos repetidos Não permite recuperar elementos sequencialmente ordenado Para otimizar a função de Hash é necessário conhecer a natureza e domínio da chave a ser utilizada No pior caso a complexidade das operações pode ser On Caso em que todos os elementos inseridos colidirem Hash com endereçamento aberto pode necessitar de redimensionamento 55 Fonte httpwww2icuffbrboeresslideseded13pdf