Cap 5 - Pesquisa em Memória Primária

Pesquisa em MemriaPrimria

ltima alterao: 10 de Outubro de 2006

Transparncias elaboradas por Fabiano C. Botelho, Leonardo Rocha, Leo-nardo Mata e Nivio Ziviani

Projeto de Algoritmos - Cap.5 Pesquisa em Memria Primria 1

Pesquisa em Memria Primria

Introduo - Conceitos Bsicos Pesquisa Seqencial Pesquisa Binria rvores de Pesquisa

rvores Binrias de Pesquisa semBalanceamento

rvores Binrias de Pesquisa comBalanceamento rvores SBB Transformaes para Manuteno da

Propriedade SBB

Pesquisa Digital Trie Patricia

Transformao de Chave (Hashing) Funes de Transformao Listas Encadeadas Endereamento Aberto Hashing Perfeito


Introduo - Conceitos Bsicos

Estudo de como recuperar informao a partirde uma grande massa de informaopreviamente armazenada.

A informao dividida em registros. Cada registro possui uma chave para ser

usada na pesquisa.

Objetivo da pesquisa:Encontrar uma ou mais ocorrncias deregistros com chaves iguais chave depesquisa.

Pesquisa com sucesso X Pesquisa semsucesso.


Introduo - Conceitos BsicosTabelas

Conjunto de registros ou arquivos TABELAS

Tabela:Associada a entidades de vida curta, criadasna memria interna durante a execuo deum programa.

Arquivo:Geralmente associado a entidades de vidamais longa, armazenadas em memriaexterna.

Distino no rgida:tabela: arquivo de ndicesarquivo: tabela de valores de funes.


Escolha do Mtodo de Pesquisa maisAdequado a uma DeterminadaAplicao

Depende principalmente:1. Quantidade dos dados envolvidos.2. Arquivo estar sujeito a inseres e

retiradas freqentes.

se contedo do arquivo estvel importante minimizar o tempo depesquisa, sem preocupao com o temponecessrio para estruturar o arquivo


Algoritmos de Pesquisa TiposAbstratos de Dados

importante considerar os algoritmos depesquisa como tipos abstratos de dados,com um conjunto de operaes associado auma estrutura de dados, de tal forma que hajauma independncia de implementao paraas operaes.

Operaes 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 especfico.5. Ordenar um arquivo para obter todos os

registros em ordem de acordo com achave.

6. Ajuntar dois arquivos para formar umarquivo maior.


Dicionrio

Nome comumente utilizado para descreveruma estrutura de dados para pesquisa.

Dicionrio um tipo abstrato de dadoscom as operaes:1. Inicializa2. Pesquisa3. Insere4. Retira

Analogia com um dicionrio da lnguaportuguesa: Chaves palavras Registros entradas associadas com

cada palavra: pronncia definio sinnimos outras informaes

Projeto de Algoritmos - Cap.5 Pesquisa em Memria Primria Seo 5.1 7

Pesquisa Seqencial

Mtodo de pesquisa mais simples: a partirdo primeiro registro, pesquiseseqencialmente at encontrar a chaveprocurada; ento pare.

Armazenamento de um conjunto de registrospor meio do tipo estruturado arranjo.


Pesquisa Seqencial

package cap5;import cap4. Item ; / / vide programa do captulo 4public class Tabela {

private Item registros [ ] ;private int n;

public Tabela ( int maxN) {this . registros = new Item[maxN+1];this .n = 0;

}public int pesquisa ( Item reg ) {

this . registros [0] = reg ; / / sentinelaint i = this .n;while ( this . registros [ i ] .compara ( reg) != 0) i;return i ;

}public void insere ( Item reg) throws Exception {

i f ( this .n == ( this . registros . length 1))throw new Exception ( "Erro : A tabela esta cheia" ) ;

this . registros[++this .n] = reg;}

}


Pesquisa Seqencial

Cada registro contm um campo chave queidentifica o registro.

A Interface Item definida no captulo 4 foiutilizada por permitir a criao de mtodosgenricos.

Alm da chave, podem existir outroscomponentes em um registro, os quais notm influncia nos algoritmos.

O mtodo pesquisa retorna o ndice do registroque contm a chave passada comoparmetro no registro reg ; caso no estejapresente, o valor retornado zero.

Essa implementao no suporta mais de umregistro com a mesma chave.


Pesquisa Seqencial

Utilizao de um registro sentinela naposio zero do array:1. Garante que a pesquisa sempre termina:

se o ndice retornado por Pesquisa forzero, a pesquisa foi sem sucesso.

2. No necessrio testar se i > 0, devido aisto: o anel interno da funo Pesquisa

extremamente simples: o ndice i decrementado e a chave de pesquisa comparada com a chave que est noregistro.

isto faz com que esta tcnica sejaconhecida como pesquisa seqencialrpida.


Pesquisa SeqencialAnlise

Pesquisa com sucesso:

melhor caso : C(n) = 1

pior caso : C(n) = n

caso medio : C(n) = (n+ 1)/2

Pesquisa sem sucesso:

C (n) = n+ 1.

O algoritmo de pesquisa seqencial amelhor escolha para o problema depesquisa em tabelas com at 25 registros.


Pesquisa Binria

Pesquisa em tabela pode ser maiseficiente Se registros forem mantidosem ordem

Para saber se uma chave est presente natabela1. Compare a chave com o registro que est

na posio do meio da tabela.2. Se a chave menor ento o registro

procurado est na primeira metade databela

3. Se a chave maior ento o registroprocurado est na segunda metade databela.

4. Repita o processo at que a chave sejaencontrada, ou fique apenas um registrocuja chave diferente da procurada,significando uma pesquisa sem sucesso.


Exemplo de Pesquisa Binria para aChave G

1 2 3 4 5 6 7 8

Chaves iniciais: A B C D E F G HA B C D E F G H

E F G HG H


Algoritmo de Pesquisa binria

O algoritmo foi feito com um mtodo daclasse Tabela apresentada anteriormente.

public int binaria ( Item chave) {i f ( this .n == 0) return 0;int esq = 1 , dir = this .n, i ;do {

i = (esq + dir ) / 2 ;i f (chave.compara ( this . registros [ i ] ) > 0) esq = i + 1;else dir = i 1;

} while ( (chave.compara ( this . registros [ i ] ) != 0)&& (esq


Pesquisa BinriaAnlise

A cada iterao do algoritmo, o tamanho databela dividido ao meio.

Logo: o nmero de vezes que o tamanho databela dividido ao meio cerca de log n.

Ressalva: o custo para manter a tabelaordenada alto:a cada insero na posio p da tabelaimplica no deslocamento dos registros a partirda posio p para as posies seguintes.

Conseqentemente, a pesquisa binria nodeve ser usada em aplicaes muitodinmicas.


rvores de Pesquisa A rvore de pesquisa uma estrutura de

dados muito eficiente para armazenarinformao.

Particularmente adequada quando existenecessidade de considerar todos ou algumacombinao de:1. Acesso direto e seqencial eficientes.2. Facilidade de insero e retirada de

registros.3. Boa taxa de utilizao de memria.4. Utilizao de memria primria e

secundria.

Projeto de Algoritmos - Cap.5 Pesquisa em Memria Primria Seo 5.3.1 17

rvores Binrias de Pesquisa semBalanceamento

Para qualquer n que contenha um registro

R

E D

Temos a relao invariante

E R D

1. Todos os registros com chaves menoresesto na subrvore esquerda.

2. Todos os registros com chaves maioresesto na subrvore direita.


rvores Binrias de Pesquisa semBalanceamentoExemplo

2 4 6

3 7

5

1

O nvel do n raiz 0. Se um n est no nvel i ento a raiz de suas

subrvores esto no nvel i+ 1.

A altura de um n o comprimento docaminho mais longo deste n at um n folha.

A altura de uma rvore a altura do n raiz.


Implementao do Tipo Abstrato deDados Dicionrio usando a Estruturade Dados rvore Binria de PesquisaEstrutura de dados:

Contm as operaes inicializa, pesquisa,insere e retira.

A operao inicializa implementada peloconstrutor da classe ArvoreBinaria.


Implementao do Tipo Abstrato deDados Dicionrio usando a Estruturade Dados rvore Binria de Pesquisapackage cap5;import cap4. Item ; / / vide programa do captulo 4public class ArvoreBinaria {

private static class No {Item reg;No esq, dir ;

}private No raiz ;

/ / Entram aqui os mtodos privados das transparncias 21, 22 e26

public ArvoreBinaria ( ) {this . raiz = null ;

}public Item pesquisa ( Item reg ) {

return this .pesquisa ( reg , this . raiz ) ;}public void insere ( Item reg ) {

this . raiz = this . insere ( reg , this . raiz ) ;}public void ret i ra ( Item reg ) {

this . raiz = this . ret i ra ( reg , this . raiz ) ;}

}


Mtodo para Pesquisar na rvorePara encontrar um registro com uma chavereg:

Compare-a com a chave que est na raiz . Se menor, v para a subrvore esquerda. Se maior, v para a subrvore direita. Repita o processo recursivamente, at que a

chave procurada seja encontrada ou um nfolha atingido.

Se a pesquisa tiver sucesso ento o registrocontendo a chave passada em reg retornado.

private Item pesquisa ( Item reg , No p) {i f (p == null ) return null ; / / Registro no encontradoelse i f ( reg.compara (p. reg) < 0)

return pesquisa ( reg , p.esq) ;else i f ( reg.compara (p. reg) > 0)

return pesquisa ( reg , p. dir ) ;else return p. reg;

}


Procedimento para Inserir na rvore Atingir uma referncia null em um processo

de pesquisa significa uma pesquisa semsucesso.

Caso se queira inseri-lo na rvore, areferncia null atingida justamente o pontode insero.

private No insere ( Item reg , No p) {i f (p == null ) {

p = new No ( ) ; p. reg = reg;p.esq = null ; p. dir = null ;

}else i f ( reg.compara (p. reg) < 0)

p.esq = insere ( reg , p.esq) ;else i f ( reg.compara (p. reg) > 0)

p. dir = insere ( reg , p. dir ) ;else System.out . print ln ( "Erro : Registro ja existente" ) ;return p;

}


Programa para Criar a rvorepackage cap5;import java . io . ;import cap4.MeuItem; / / vide programa do captulo 4public class CriaArvore {

public static void main ( String [ ] args ) throws Exception {ArvoreBinaria dicionario = new ArvoreBinaria ( ) ;BufferedReader in = new BufferedReader (

new InputStreamReader (System. in ) ) ;int chave = Integer . parseInt ( in . readLine ( ) ) ;while (chave > 0) {

MeuItem item = new MeuItem (chave) ;dicionario . insere ( item) ;chave = Integer . parseInt ( in . readLine ( ) ) ;

}}

}


Procedimento para Retirar x da rvore Alguns comentrios:

1. A retirada de um registro no to simplesquanto a insero.

2. Se o n que contm o registro a serretirado possui no mximo umdescendente a operao simples.

3. No caso do n conter dois descendentes oregistro a ser retirado deve ser primeiro: substitudo pelo registro mais direita

na subrvore esquerda; ou pelo registro mais esquerda na

subrvore direita.


Exemplo da Retirada de um Registroda rvore

2 4 6

3 7

5

1

Assim: para retirar o registro com chave 5 narvore basta troc-lo pelo registro com chave 4 oupelo registro com chave 6, e ento retirar o nque recebeu o registro com chave 5.


Mtodo para retirar reg da rvore

private No antecessor (No q, No r ) {i f ( r . dir != null ) r . dir = antecessor (q, r . dir ) ;else { q. reg = r . reg ; r = r .esq; }return r ;

}private No ret ira ( Item reg , No p) {

i f (p == null )System.out . print ln ( "Erro : Registro nao encontrado" ) ;

else i f ( reg.compara (p. reg) < 0)p.esq = ret ira ( reg , p.esq) ;

else i f ( reg.compara (p. reg) > 0)p. dir = ret ira ( reg , p. dir ) ;

else {i f (p. dir == null ) p = p.esq;else i f (p.esq == null ) p = p. dir ;else p.esq = antecessor (p, p.esq) ;

}return p;

}


Outro Exemplo de Retirada de N

bye

and

be

easy

to

and to

be

to

be

and

be

and to

bye


Caminhamento Central

Aps construda a rvore, pode sernecessrio percorrer todos os registros quecompem a tabela ou arquivo.

Existe mais de uma ordem de caminhamentoem rvores, mas a mais til a chamadaordem de caminhamento central.

O caminhamento central mais bemexpresso em termos recursivos:1. caminha na subrvore esquerda na ordem

central;2. visita a raiz;3. caminha na subrvore direita na ordem

central.

Uma caracterstica importante docaminhamento central que os ns sovisitados de forma ordenada.


Caminhamento Central

Percorrer a rvore:

2 4 6

3 7

5

1

usando caminhamento central recupera aschaves na ordem 1, 2, 3, 4, 5, 6 e 7.

Caminhamento central e impresso da rvore:public void imprime ( ) { this . central ( this . raiz ) ; }

private void central (No p) {i f (p != null ) {

central (p.esq) ;System.out . print ln (p. reg. toString ( ) ) ;central (p. dir ) ;

}}


Anlise

O nmero de comparaes em uma pesquisacom sucesso:

melhor caso : C(n) = O(1),

pior caso : C(n) = O(n),

caso medio : C(n) = O(log n).

O tempo de execuo dos algoritmos pararvores binrias de pesquisa dependemmuito do formato das rvores.


Anlise

1. Para obter o pior caso basta que as chavessejam inseridas em ordem crescente oudecrescente. Neste caso a rvore resultante uma lista linear, cujo nmero mdio decomparaes (n+ 1)/2.

2. Para uma rvore de pesquisa randmica onmero esperado de comparaes pararecuperar um registro qualquer cerca de1, 39 log n, apenas 39% pior que a rvorecompletamente balanceada.

Uma rvore A com n chaves possui n+ 1 nsexternos e estas n chaves dividem todos osvalores possveis em n+ 1 intervalos. Umainsero em A considerada randmica seela tem probabilidade igual de acontecer emqualquer um dos n+ 1 intervalos.

Uma rvore de pesquisa randmica com nchaves uma rvore construida atravs de ninseres randmicas sucessivas em umarvore inicialmente vazia.


rvores Binrias de Pesquisa comBalanceamento

rvore completamente balanceada nsexternos aparecem em no mximo dois nveisadjacentes.

Minimiza tempo mdio de pesquisa para umadistribuio uniforme das chaves, onde cadachave igualmente provvel de ser usada emuma pesquisa.

Contudo, custo para manter a rvorecompletamente balanceada aps cadainsero muito alto.

Para inserir a chave 1 na rvore do exemplo esquerda e obter a rvore direita do mesmoexemplo necessrio movimentar todos osns da rvore original.

Exemplo:

2 4 6 1 3 5 7

3 7

5

2 6

4


Uma Forma de Contornar esteProblema

Procurar soluo intermediria que possamanter rvore quase-balanceada, em vezde tentar manter a rvore completamentebalanceada.

Objetivo: Procurar obter bons tempos depesquisa, prximos do tempo timo da rvorecompletamente balanceada, mas sem pagarmuito para inserir ou retirar da rvore.

Heursticas: existem vrias heursticasbaseadas no princpio acima.

Gonnet e Baeza-Yates (1991) apresentamalgoritmos que utilizam vrios critrios debalanceamento para rvores de pesquisa,tais como restries impostas: na diferena das alturas de subrvores de

cada n da rvore, na reduo do comprimento do caminho

interno ou que todos os ns externos apaream

no mesmo nvel.


Uma Forma de Contornar esteProblema

Comprimento do caminho interno:corresponde soma dos comprimentos doscaminhos entre a raiz e cada um dos nsinternos da rvore.

Por exemplo, o comprimento do caminhointerno da rvore esquerda na figura datransparncia anterior 8 = (0 + 1 + 1 + 2 + 2 + 2).

Projeto de Algoritmos - Cap.5 Pesquisa em Memria Primria Seo 5.3.2.1 35

rvores SBB rvores B estrutura para memria

secundria. (Bayer R. e McCreight E.M.,1972)

rvore 2-3 caso especial da rvore B. Cada n tem duas ou trs subrvores. Mais apropriada para memria primria. Exemplo: Uma rvore 2-3 e a rvore B

binria correspondente(Bayer, R. 1971)

1 3,4 6 8,9 11

102,5

7

1 3 4 6

52

8 9 11

10

7


rvores SBB rvore 2-3 rvore B binria (assimetria

inerente)1. Referncias esquerda apontam para um

n no nvel abaixo.2. Referncias direita podem ser verticais

ou horizontais.Eliminao da assimetria nas rvores Bbinrias rvores B binrias simtricas(Symmetric Binary B-trees SBB)

rvore SBB uma rvore binria com 2 tiposde referncias: verticais e horizontais, tal que:1. todos os caminhos da raiz at cada n

externo possuem o mesmo nmero dereferncias verticais, e

2. no podem existir dois refernciashorizontais sucessivos.

4 6 7 8 10

93

21

5


Transformaes para Manuteno daPropriedade SBB

O algoritmo para rvores SBB usatransformaes locais no caminho deinsero ou retirada para preservar obalanceamento.

A chave a ser inserida ou retirada sempreinserida ou retirada aps o referncia verticalmais baixo na rvore.

Dependendo da situao anterior inseroou retirada, podem aparecer dois refernciashorizontais sucessivos

Neste caso: necessrio realizar umatransformao.

Transformaes Propostas por Bayer R.1972

(a) Esquerdaesquerda (EE)

(b) Esquerdadireita (ED)

2 3

1

1 2 3

1

2

3

2

31 321 2

1 3


Estrutura e operaes do dicionriopara rvores SBB

Diferenas da rvore sem balanceamento: constantes Horizontal e Vertical :

representam as inclinaes dasreferncias s subrvores;

campo propSBB : utilizado para verificarquando a propriedade SBB deixa de sersatisfeita

campos incE e incD : indicam o tipo dereferncia (horizontal ou vertical) que saido n.

A operao inicializa implementada peloconstrutor da classe ArvoreSBB .

As demais operaes so implementadasutilizando mtodos privados sobrecarregados.


Estrutura e operaes do dicionriopara rvores SBB

package cap5;import cap4. Item ; / / vide programa do captulo 4public class ArvoreSBB {

private static class No {Item reg ; No esq, dir ; byte incE , incD;

}private static final byte Horizontal = 0;private static final byte Vertical = 1;private No raiz ; private boolean propSBB;

/ / Entram aqui os mtodos privados das transparncias 21, 40,41 e 48

public ArvoreSBB ( ) {this . raiz = null ; this .propSBB = true ;

}public Item pesquisa ( Item reg ) {

return this .pesquisa ( reg , this . raiz ) ; }public void insere ( Item reg ) {

this . raiz = insere ( reg , null , this . raiz , true ) ; }public void ret i ra ( Item reg ) {

this . raiz = this . ret i ra ( reg , this . raiz ) ; }/ / Entra aqui o mtodo para imprimir a rvore da tranaparn-

cia 29}


Mtodos para manuteno dapropriedade SBB

private No ee (No ap) {No ap1 = ap.esq; ap.esq = ap1. dir ; ap1. dir = ap;ap1. incE = Vertical ; ap. incE = Vertical ; ap = ap1;return ap;

}private No ed (No ap) {

No ap1 = ap.esq; No ap2 = ap1. dir ; ap1. incD = Vertical ;ap. incE = Vertical ; ap1. dir = ap2.esq; ap2.esq = ap1;ap.esq = ap2. dir ; ap2. dir = ap; ap = ap2;return ap;

}private No dd (No ap) {

No ap1 = ap. dir ; ap. dir = ap1.esq; ap1.esq = ap;ap1. incD = Vertical ; ap. incD = Vertical ; ap = ap1;return ap;

}private No de (No ap) {

No ap1 = ap. dir ; No ap2 = ap1.esq; ap1. incE = Vertical ;ap. incD = Vertical ; ap1.esq = ap2. dir ; ap2. dir = ap1;ap. dir = ap2.esq; ap2.esq = ap; ap = ap2;return ap;

}


Mtodo para inserir na rvore SBBprivate No insere ( Item reg , No pai , No fi lho , boolean filhoEsq ) {

i f ( f i lho == null ) {f i lho = new No ( ) ; f i lho . reg = reg;f i lho . incE = Vertical ; f i lho . incD = Vertical ;f i lho .esq = null ; f i lho . dir = null ;i f ( pai != null )

i f ( filhoEsq ) pai . incE = Horizontal ; else pai . incD = Horizontal ;this .propSBB = false ;

}else i f ( reg.compara ( f i lho . reg) < 0) {

f i lho .esq = insere ( reg , f i lho , f i lho .esq, true ) ;i f ( ! this .propSBB)

i f ( f i lho . incE == Horizontal ) {i f ( f i lho .esq. incE == Horizontal ) {

f i lho = this .ee ( f i lho ) ; / / transformao esquerda-esquerdai f ( pai != null )

i f ( filhoEsq ) pai . incE=Horizontal ; else pai . incD=Horizontal ;}

else i f ( f i lho .esq. incD == Horizontal ) {f i lho = this .ed ( f i lho ) ; / / transformao esquerda-direita

i f ( pai != null )i f ( filhoEsq ) pai . incE=Horizontal ;else pai . incD=Horizontal ;

}}else this .propSBB = true ;

}

/ / Continua na prxima transparncia


Mtodo para inserir na rvore SBBelse i f ( reg.compara ( f i lho . reg) > 0) {

f i lho . dir = insere ( reg , f i lho , f i lho . dir , false ) ;i f ( ! this .propSBB)

i f ( f i lho . incD == Horizontal ) {i f ( f i lho . dir . incD == Horizontal ) {

f i lho = this .dd ( f i lho ) ; / / transformao direita-direitai f ( pai != null )

i f ( filhoEsq ) pai . incE=Horizontal ; else pai . incD=Horizontal ;}else i f ( f i lho . dir . incE == Horizontal ) {

f i lho = this .de ( f i lho ) ; / / transformao direita-esquerdai f ( pai != null )

i f ( filhoEsq ) pai . incE=Horizontal ; else pai . incD=Horizontal ;}

}else this .propSBB = true ;

}else {

System.out . print ln ( "Erro : Registro ja existente" ) ;this .propSBB = true ;

}return f i lho ;

}


Exemplo

Insero de uma seqncia de chaves emuma rvore SBB inicialmente vazia.1. rvore esquerda obtida aps a

insero das chaves 7, 10, 5.2. rvore do meio obtida aps a insero

das chaves 2, 4 na rvore anterior.3. rvore direita obtida aps a insero

das chaves 9, 3, 6 na rvore anterior.

4 6 7

3

2 10

95

1075 2 4 7 10

5


Procedimento Retira

Assim como o mtodo insere mostradoanteriormente, o mtodo retira possui umaverso privada, que foi sobrecarregada comuma interface que contm um parmetro amais que a sua verso pblica.

O mtodo privado retira utiliza trs mtodosauxiliares, a saber: esqCurto (dirCurto) chamado quando um

n folha (que referenciado por umareferncia vertical) retirado da subrvore esquerda (direita), tornando-a menor naaltura aps a retirada;

Quando o n a ser retirado possui doisdescendentes, o mtodo antecessorlocaliza o n antecessor para ser trocadocom o n a ser retirado.


Mtodo auxiliar esqCurto para retiradada rvore SBB/ / Folha esquerda retirada => rvore curta na altura esquerdaprivate No esqCurto (No ap) {

i f (ap. incE == Horizontal ) {ap. incE = Vertical ; this .propSBB = true ;

}else i f (ap. incD == Horizontal ) {

No ap1 = ap. dir ; ap. dir = ap1.esq; ap1.esq = ap; ap = ap1;i f (ap.esq. dir . incE == Horizontal ) {

ap.esq = this .de (ap.esq) ; ap. incE = Horizontal ;}else i f (ap.esq. dir . incD == Horizontal ) {

ap.esq = this .dd (ap.esq) ; ap. incE = Horizontal ;}this .propSBB = true ;

}else {

ap. incD = Horizontal ;i f (ap. dir . incE == Horizontal ) {

ap = this .de (ap) ; this .propSBB = true ;}else i f (ap. dir . incD == Horizontal ) {

ap = this .dd (ap) ; this .propSBB = true ;}

} return ap;}


Mtodo auxiliar dirCurto para retiradada rvore SBB/ / Folha direita retirada => rvore curta na altura direitaprivate No dirCurto (No ap) {

i f (ap. incD == Horizontal ) {ap. incD = Vertical ; this .propSBB = true ;

}else i f (ap. incE == Horizontal ) {

No ap1 = ap.esq; ap.esq = ap1. dir ; ap1. dir = ap; ap = ap1;i f (ap. dir .esq. incD == Horizontal ) {

ap. dir = this .ed (ap. dir ) ; ap. incD = Horizontal ;}else i f (ap. dir .esq. incE == Horizontal ) {

ap. dir = this .ee (ap. dir ) ; ap. incD = Horizontal ;}this .propSBB = true ;

}else {

ap. incE = Horizontal ;i f (ap.esq. incD == Horizontal ) {

ap = this .ed (ap) ; this .propSBB = true ;}else i f (ap.esq. incE == Horizontal ) {

ap = this .ee (ap) ; this .propSBB = true ;}

} return ap;}


Mtodo auxiliar antecessor para retiradada rvore SBBprivate No antecessor (No q, No r ) {

i f ( r . dir != null ) {r . dir = antecessor (q, r . dir ) ;i f ( ! this .propSBB) r = this . dirCurto ( r ) ;

}else {

q. reg = r . reg;r = r .esq;i f ( r != null ) this .propSBB = true ;

}return r ;

}


Mtodo retira para retirada da rvoreSBBprivate No ret ira ( Item reg , No ap) {

i f (ap == null ) {System.out . print ln ( "Erro : Registro nao encontrado" ) ;this .propSBB = true ;

}else i f ( reg.compara (ap. reg) < 0) {

ap.esq = ret ira ( reg , ap.esq) ;i f ( ! this .propSBB)

ap = this .esqCurto (ap) ;}else i f ( reg.compara (ap. reg) > 0) {

ap. dir = ret i ra ( reg , ap. dir ) ;i f ( ! this .propSBB) ap = this . dirCurto (ap) ;

}else { / / encontrou o registro

this .propSBB = false ;i f (ap. dir == null ) {

ap = ap.esq;i f (ap != null ) this .propSBB = true ;

}else i f (ap.esq == null ) {

ap = ap. dir ;i f (ap != null )

this .propSBB = true ;}else {

ap.esq = antecessor (ap, ap.esq) ;i f ( ! this .propSBB)

ap = this .esqCurto (ap) ;}

}return ap;

}


Exemplo

Dada a rvore:

4 6 7

3

2 10

95

1075 2 4 7 10

5

Resultado obtido quando se retira umaseqncia de chaves da rvore SBB mais direita acima: A rvore esquerda obtida aps a

retirada da chave 7 da rvore direitaacima.

A rvore do meio obtida aps a retiradada chave 5 da rvore anterior.

A rvore direita obtida aps a retiradada chave 9 da rvore anterior.

4 6

3

2

5 9

10 2 3

4

6

9

10 2 3

4

106


Exemplo: Retirada de Ns de SBB

Caso 1:

1a chamada DirCurto

2a chamadaDirCurto

2 chamadas DirCurto

4

2

1 3 6 12

104

2 106

1 36t

2 4

1 3 6 10

Caso 2:

4

2 10

1 3 6 8 12

4

2

1 3

106 8

4

2

1 3 6 10

8

1a chamada DirCurto


Exemplo: Retirada de Ns de SBBCaso 3:

Se nodo 8 tem filho:

4

2

1 3

6 10

5 8 12

4

2 6 10

1 3 5 8

4

2 6

1 3 5 8 10

4

2 6 10

1 3 5 8 9 12

4

2

1 3

6 10

5 8 9

4

2 6

1 3 5 8 10

9

4

2 6 9

1 3 5 8 10


Anlise

Nas rvores SBB necessrio distinguir doistipos de alturas:1. Altura vertical h necessria para manter

a altura uniforme e obtida atravs dacontagem do nmero de refernciasverticais em qualquer caminho entre a raize um n externo.

2. Altura k representa o nmero mximode comparaes de chaves obtida atravsda contagem do nmero total dereferncias no maior caminho entre a raize um n externo.

A altura k maior que a altura h sempre queexistirem referncias horizontais na rvore.

Para uma rvore SBB com n ns internos,temos que

h k 2h.


Anlise

De fato Bayer (1972) mostrou quelog(n+ 1) k 2 log(n+ 2) 2.

Custo para manter a propriedade SBB Custo para percorrer o caminho de pesquisapara encontrar a chave, seja para inser-la oupara retir-la.

Logo: O custo O(log n). Nmero de comparaes em uma pesquisa

com sucesso na rvore SBB

melhor caso : C(n) = O(1),

pior caso : C(n) = O(log n),

caso medio : C(n) = O(log n).

Observe: Na prtica o caso mdio para Cn apenas cerca de 2% pior que o Cn para umarvore completamente balanceada, conformemostrado em Ziviani e Tompa (1982).


Pesquisa Digital

Pesquisa digital baseada na representaodas chaves como uma seqncia decaracteres ou de dgitos.

Os mtodos de pesquisa digital soparticularmente vantajosos quando as chavesso grandes e de tamanho varivel.

Um aspecto interessante quanto aos mtodosde pesquisa digital a possibilidade delocalizar todas as ocorrncias de umadeterminada cadeia em um texto, com tempode resposta logartmico em relao aotamanho do texto. Trie Patrcia


Trie

Uma trie uma rvore M -ria cujos ns sovetores de M componentes com camposcorrespondentes aos dgitos ou caracteresque formam as chaves.

Cada n no nvel i representa o conjunto detodas as chaves que comeam com a mesmaseqncia de i dgitos ou caracteres.

Este n especifica uma ramificao com Mcaminhos dependendo do (i+ 1)-simo dgitoou caractere de uma chave.

Considerando as chaves como seqnciade bits (isto , M = 2), o algoritmo depesquisa digital semelhante ao depesquisa em rvore, exceto que, em vez dese caminhar na rvore de acordo com oresultado de comparao entre chaves,caminha-se de acordo com os bits dechave.


Exemplo

Dada as chaves de 6 bits:

B = 010010

C = 010011

H = 011000

J = 100001

M = 101000

00

100

0

11

11

0 1

CB

H J Q


Insero das Chaves W e K na TrieBinria

00

100

0

11

11

0 1

CB

H J Q

Faz-se uma pesquisa na rvore com a chave aser inserida. Se o n externo em que a pesquisaterminar for vazio, cria-se um novo n externonesse ponto contendo a nova chave, exemplo: ainsero da chave W = 110110.

Se o n externo contiver uma chave cria-se um oumais ns internos cujos descendentes contero achave j existente e a nova chave. exemplo:insero da chave K = 100010.

00

0

00

00

11

11

1

11

0 1

CB

H

J K

QW


Consideraes Importantes sobre asTries

O formato das tries, diferentemente dasrvores binrias comuns, no depende daordem em que as chaves so inseridas e simda estrutura das chaves atravs dadistribuio de seus bits.

Desvantagem: Uma grande desvantagem das tries a

formao de caminhos de uma s direopara chaves com um grande nmero debits em comum.

Exemplo: Se duas chaves diferiremsomente no ltimo bit, elas formaro umcaminho cujo comprimento igual aotamanho delas, no importando quantaschaves existem na rvore.

Caminho gerado pelas chaves B e C.


Patricia - Practical Algorithm ToRetrieve Information Coded InAlphanumeric

Criado por Morrison D. R. 1968 paraaplicao em recuperao de informao emarquivos de grande porte.

Knuth D. E. 1973 novo tratamentoalgoritmo.

Reapresentou-o de forma mais clara comoum caso particular de pesquisa digital,essencialmente, um caso de rvore triebinria.

Sedgewick R. 1988 apresentou novosalgoritmos de pesquisa e de inserobaseados nos algoritmos propostos porKnuth.

Gonnet, G.H e Baeza-Yates R. 1991propuzeram tambm outros algoritmos.


Mais sobre Patricia

O algoritmo para construo da rvorePatricia baseado no mtodo de pesquisadigital, mas sem apresentar o inconvenientecitado para o caso das tries.

O problema de caminhos de uma s direo eliminado por meio de uma soluo simples eelegante: cada n interno da rvore contm ondice do bit a ser testado para decidir qualramo tomar.

Exemplo: dada as chaves de 6 bits:

B = 010010

C = 010011

H = 011000

J = 100001

Q = 101000

B C

H J Q

3

1

3

6


Insero da Chave K

B C

H J Q

3

1

3

6

Para inserir a chave K = 100010 na rvore acima, apesquisa inicia pela raiz e termina quando se chega aon externo contendo J.

Os ndices dos bits nas chaves esto ordenados daesquerda para a direita. Bit de ndice 1 de K 1 asubrvore direita Bit de ndice 3 subrvore esquerdaque neste caso um n externo.

Chaves J e K mantm o padro de bits 1x0xxx, assimcomo qualquer outra chave que seguir este caminhode pesquisa.

Novo n interno repe o n J, e este com n K seroos ns externos descendentes.

O ndice do novo n interno dado pelo 1o bit diferentedas 2 chaves em questo, que o bit de ndice 5. Paradeterminar qual ser o descendente esquerdo e odireito, verifique o valor do bit 5 de ambas as chaves.

B C

H

3

6 5 Q

3

1

J K


Insero da Chave W

A insero da chave W = 110110 ilustra umoutro aspecto.

Os bits das chaves K e W so comparados apartir do primeiro para determinar em qualndice eles diferem, sendo, neste caso, os dendice 2.

Portanto: o ponto de insero agora ser nocaminho de pesquisa entre os ns internos dendice 1 e 3.

Cria-se a um novo n interno de ndice 2,cujo descendente direito um n externocontendo W e cujo descendente esquerdo asubrvore de raiz de ndice 3.

B C

H

3

6

2

1

5

J K

3 W

Q


Estrutura de dados e operaes darvore Patricia

Em uma rvore Patricia existem dois tipos dens diferentes: internos e externos. Paraimplementar essa caracterstica foi utilizado omecanismo de herana e polimorfismo dalinguagem Java.

package cap5;public class ArvorePatricia {

private static abstract class PatNo { }private static class PatNoInt extends PatNo {

int index;PatNo esq, dir ;

}private static class PatNoExt extends PatNo { char chave; }

private PatNo raiz ;private int nbitsChave;

/ / Entram aqui os mtodos privados das transparncias 64, 65 e 68public ArvorePatricia ( int nbitsChave) {

this . raiz = null ; this .nbitsChave = nbitsChave;}public void pesquisa (char k){ this .pesquisa (k, this . raiz ) ; }public void insere (char k){ this . raiz = this . insere (k, this . raiz ) ; }

}


Mtodos Auxiliares/ / Retorna o i-simo bit da chave k a partir da esquerdaprivate int bit ( int i , char k) {

i f ( i == 0) return 0;int c = ( int )k;for ( int j = 1; j


Mtodos Auxiliares

Mtodo para criar n externo:private PatNo criaNoExt (char k) {

PatNoExt p = new PatNoExt ( ) ;p.chave = k;return p;

}

Mtodo para pesquisa:private void pesquisa (char k, PatNo t ) {

i f ( this .eExterno ( t ) ) {PatNoExt aux = (PatNoExt) t ;i f (aux.chave == k) System.out. println ( "Elemento encontrado" ) ;else System.out. println ( "Elemento nao encontrado" ) ;

}else {

PatNoInt aux = (PatNoInt) t ;i f ( this . bit (aux.index, k) == 0) pesquisa (k, aux.esq);else pesquisa (k, aux. dir ) ;

}}


Descrio Informal do Algoritmo deInsero

Cada chave k inserida de acordo com ospassos abaixo, partindo da raiz:1. Se a subrvore corrente for vazia, ento

criado um n externo contendo a chave k(isso ocorre somente na insero daprimeira chave) e o algoritmo termina.

2. Se a subrvore corrente for simplesmenteum n externo, os bits da chave k socomparados, a partir do bit de ndiceimediatamente aps o ltimo ndice daseqncia de ndices consecutivos docaminho de pesquisa, com os bitscorrespondentes da chave k deste nexterno at encontrar um ndice i cujosbits difiram. A comparao dos bits a partirdo ltimo ndice consecutivo melhoraconsideravelmente o desempenho doalgoritmo. Se todos forem iguais, a chavej se encontra na rvore e o algoritmotermina; seno, vai-se para o Passo 4.


Descrio Informal do Algoritmo deInsero

Continuao:3. Caso contrrio, ou seja, se a raiz da

subrvore corrente for um n interno,vai-se para a subrvore indicada pelo bitda chave k de ndice dado pelo ncorrente, de forma recursiva.

4. Depois so criados um n interno e um nexterno: o primeiro contendo o ndice i e osegundo, a chave k. A seguir, o n interno ligado ao externo pela referncia subrvore esquerda ou direita,dependendo se o bit de ndice i da chave kseja 0 ou 1, respectivamente.

5. O caminho de insero percorridonovamente de baixo para cima, subindocom o par de ns criados no Passo 4 atchegar a um n interno cujo ndice sejamenor que o ndice i determinado noPasso 2. Esse o ponto de insero e opar de ns inserido.


Algoritmo de inseroprivate PatNo insereEntre (char k , PatNo t , int i ) {

PatNoInt aux = null ;i f ( ! this .eExterno ( t ) ) aux = (PatNoInt) t ;i f ( this .eExterno ( t ) | | ( i < aux. index ) ) { / / Cria um novo n

externoPatNo p = this .criaNoExt (k) ;i f ( this . b i t ( i , k) == 1) return this . criaNoInt ( i , t , p) ;else return this . criaNoInt ( i , p, t ) ;

} else {i f ( this . b i t (aux. index , k) == 1)

aux. dir = this . insereEntre (k , aux. dir , i ) ;else aux.esq = this . insereEntre (k , aux.esq, i ) ;return aux;

}}

private PatNo insere (char k , PatNo t ) {i f ( t == null ) return this .criaNoExt (k) ;else {

PatNo p = t ;while ( ! this .eExterno (p) ) {

PatNoInt aux = (PatNoInt)p;i f ( this . b i t (aux. index , k) == 1) p = aux. dir ;else p = aux.esq;

}PatNoExt aux = (PatNoExt)p;int i = 1; / / acha o primeiro bit diferentewhile ( ( i this .nbitsChave) {

System.out . println ( "Erro : chave ja esta na arvore" ) ;return t ;

}else return this . insereEntre (k , t , i ) ;

}}


Transformao de Chave (Hashing) Os registros armazenados em uma tabela

so diretamente endereados a partir de umatransformao aritmtica sobre a chave depesquisa.

Hash significa:1. Fazer picadinho de carne e vegetais para

cozinhar.2. Fazer uma baguna. (Websters New

World Dictionary)


Transformao de Chave (Hashing) Um mtodo de pesquisa com o uso da

transformao de chave constitudo de duasetapas principais:1. Computar o valor da funo de

transformao, a qual transforma a chavede pesquisa em um endereo da tabela.

2. Considerando que duas ou mais chavespodem ser transformadas em um mesmoendereo de tabela, necessrio existirum mtodo para lidar com colises.

Qualquer que seja a funo detransformao, algumas colises iro ocorrerfatalmente, e tais colises tm de serresolvidas de alguma forma.

Mesmo que se obtenha uma funo detransformao que distribua os registros deforma uniforme entre as entradas da tabela,existe uma alta probabilidade de havercolises.


Transformao de Chave (Hashing) O paradoxo do aniversrio (Feller,1968,

p. 33), diz que em um grupo de 23 ou maispessoas, juntas ao acaso, existe uma chancemaior do que 50% de que 2 pessoascomemorem aniversrio no mesmo dia.

Assim, se for utilizada uma funo detransformao uniforme que enderece 23chaves randmicas em uma tabela detamanho 365, a probabilidade de que hajacolises maior do que 50%.

A probabilidade p de se inserir N itensconsecutivos sem coliso em uma tabela detamanho M :

p =M 1M

M 2M

. . . M N + 1M

=

=Ni=1

M i+ 1M

=M !

(M N)!MN


Transformao de Chave (Hashing) Alguns valores de p para diferentes valores deN ,onde M = 365.

N p

10 0,88322 0,52423 0,49330 0,303

Para N pequeno a probabilidade p pode seraproximada por p N(N1))

730. Por exemplo,

para N = 10 ento p 87, 7%.


Funes de Transformao

Uma funo de transformao deve mapearchaves em inteiros dentro do intervalo[0..M 1], onde M o tamanho da tabela.

A funo de transformao ideal aquelaque:1. Seja simples de ser computada.2. Para cada chave de entrada, qualquer

uma das sadas possveis igualmenteprovvel de ocorrer.

Como as transformaes sobre as chavesso aritmticas, deve-se transformar aschaves no-numricas em nmeros.

Em Java, basta realizar uma converso decada caractere da chave no numrica paraum nmero inteiro.


Mtodo mais Usado

Usa o resto da diviso por M .

h(K) = K mod M,

onde K um inteiro correspondente chave.

Cuidado na escolha do valor de M . M deveser um nmero primo, mas no qualquerprimo: devem ser evitados os nmerosprimos obtidos a partir de

bi jonde b a base do conjunto de caracteres(geralmente b = 64 para BCD, 128 paraASCII, 256 para EBCDIC, ou 100 para algunscdigos decimais), e i e j so pequenosinteiros.


Transformao de Chaves NoNumricas

As chaves no numricas devem sertransformadas em nmeros:

K =n1i=0

chave[i] p[i],

n o nmero de caracteres da chave. chave[i] corresponde representao ASCII

ou Unicode do i-simo caractere da chave.

p[i] um inteiro de um conjunto de pesosgerados randomicamente para 0 i n 1.

Vantagem de se usar pesos: Dois conjuntosdiferentes de pesos p1[i] e p2[i], 0 i n 1,levam a duas funes de transformaoh1(K) e h2(K) diferentes.


Transformao de Chaves NoNumricas

Programa que gera um peso para cadacaractere de uma chave constituda de ncaracteres:

private int [ ] geraPesos ( int n) {int p[ ] = new int [n] ;java . u t i l .Random rand = new java . u t i l .Random ( ) ;for ( int i = 0; i < n; i ++) p[ i ] = rand. nextInt (M) + 1;return p;

}

Implementao da funo detransformao:

private int h ( String chave, int [ ] pesos) {int soma = 0;for ( int i = 0; i < chave. length ( ) ; i++)

soma = soma + (( int )chave.charAt ( i ) ) pesos[ i ] ;return soma % this .M;

}


Listas Encadeadas

Uma das formas de resolver as colises simplesmente construir uma lista linearencadeada para cada endereo da tabela.Assim, todas as chaves com mesmoendereo so encadeadas em uma listalinear.

Exemplo: Se a i-sima letra do alfabeto representada pelo nmero i e a funo detransformao h(Chave) = Chave mod M utilizada para M = 7, o resultado da inserodas chaves P E S Q U I S A na tabela oseguinte:

Por exemplo, h(A) = h(1) = 1,h(E) = h(5) = 5, h(S) = h(19) = 5, e assimpor diante.

T

-

-

-

-

-

-

-

nil

nil

UA

-

-

nilnil

P - I - nilQ - nil

E - S - S - nil6543210


Estrutura e operaes do dicionriopara listas encadeadas

Em cada entrada da lista devem serarmazenados uma chave e um registro dedados cujo tipo depende da aplicao.

A classe interna Celula utilizada pararepresentar uma entrada em uma lista dechaves que so mapeadas em um mesmoendereo i da tabela, sendo 0 i M 1.

O mtodo equals da classe Celula usadopara verificar se duas clulas so iguais (isto, possuem a mesma chave).

A operao inicializa implementada peloconstrutor da classe TabelaHash.


Estrutura e operaes do dicionriopara listas encadeadaspackage cap5. listaenc ;import cap3.autoreferencia . Lista ; / / vide Programas do ca-ptulo 3public class TabelaHash {

private static class Celula {String chave; Object item;public Celula ( String chave, Object item ) {

this .chave = chave; this . item = item;}public boolean equals (Object obj ) {

Celula cel = (Celula)obj ;return chave.equals ( cel .chave) ;

}}private int M; / / tamanho da tabelaprivate Lista tabela [ ] ;private int pesos [ ] ;public TabelaHash ( int m, int maxTamChave) {

this .M = m; this . tabela = new Lista [ this .M] ;for ( int i = 0; i < this .M; i++)

this . tabela [ i ] = new Lista ( ) ;this .pesos = this .geraPesos (maxTamChave) ;

}/ / Entram aqui os mtodos privados da transparncia 76.



Estrutura e operaes do dicionriopara listas encadeadas

public Object pesquisa ( String chave) {int i = this .h (chave, this .pesos) ;i f ( this . tabela [ i ] . vazia ( ) ) return null ; / / pesquisa

sem sucesso

else {Celula cel=(Celula) this . tabela [ i ] . pesquisa(

new Celula(chave, null ) ) ;i f ( cel == null ) return null ; / / pesquisa sem sucessoelse return cel . item;

}}public void insere ( String chave, Object item ) {

i f ( this .pesquisa (chave) == null ) {int i = this .h (chave, this .pesos) ;this . tabela [ i ] . insere (new Celula (chave, item ) ) ;

}else System.out . print ln ( "Registro ja esta presente" ) ;

}public void ret i ra ( String chave) throws Exception {

int i = this .h (chave, this .pesos) ;Celula cel = (Celula) this . tabela [ i ] . ret i ra (

new Celula (chave, null ) ) ;i f ( cel == null )

System.out . print ln ( "Registro nao esta presente" ) ;} }


Anlise

Assumindo que qualquer item do conjuntotem igual probabilidade de ser endereadopara qualquer entrada da tabela, ento ocomprimento esperado de cada listaencadeada N/M , em que N representa onmero de registros na tabela e M o tamanhoda tabela.

Logo: as operaes pesquisa, insere e retiracustam O(1 +N/M) operaes em mdia,sendo que a constante 1 representa o tempopara encontrar a entrada na tabela, e N/M , otempo para percorrer a lista. Para valores deM prximos de N , o tempo torna-seconstante, isto , independente de N .


Endereamento Aberto

Quando o nmero de registros a seremarmazenados na tabela puder serpreviamente estimado, ento no havernecessidade de usar listas encadeadas paraarmazenar os registros.

Existem vrios mtodos para armazenar Nregistros em uma tabela de tamanho M > N ,os quais utilizam os lugares vazios na prpriatabela para resolver as colises. (Knuth,1973, p.518)

No Endereamento aberto todas as chavesso armazenadas na prpria tabela, sem ouso de listas encadeadas em cada entradadela.

Existem vrias propostas para a escolha delocalizaes alternativas. A mais simples chamada de hashing linear, onde a posiohj na tabela dada por:

hj = (h(x) + j) mod M, para 1 j M 1.


Exemplo

Se a i-sima letra do alfabeto representadapelo nmero i e a funo de transformaoh(chave) = chave mod M utilizada paraM = 7,

ento o resultado da insero das chavesL U N E S na tabela, usando hashing linearpara resolver colises mostrado abaixo.

Por exemplo, h(L) = h(12) = 5,h(U) = h(21) = 0, h(N) = h(14) = 0,

h(E) = h(5) = 5, e h(S) = h(19) = 5.

T

UNS

LE6

543210


Estrutura e operaes do dicionriousando endereamento aberto

A tabela agora constituda por um arranjode clulas.

A classe interna Celula utilizada pararepresentar uma clula da tabela.

A operao inicializa implementada peloconstrutor da classe TabelaHash.

As operaes utilizam alguns mtodosauxiliares durante a execuo.


Estrutura e operaes do dicionriousando endereamento abertopackage cap5.endaberto;public class TabelaHash {

private static class Celula {String chave; Object item ; boolean retirado ;public Celula ( String chave, Object item ) {

this .chave = chave; this . item = item;this . retirado = false ;

}public boolean equals (Object obj ) {

Celula cel = (Celula)obj ;return chave.equals ( cel .chave) ;

}}private int M; / / tamanho da tabelaprivate Celula tabela [ ] ;private int pesos [ ] ;

/ / Entram aqui os mtodos privados da transparncia 76public TabelaHash ( int m, int maxTamChave) {

this .M = m; this . tabela = new Celula [ this .M] ;for ( int i = 0; i < this .M; i++)

this . tabela [ i ] = null ; / / vaziothis .pesos = this .geraPesos (maxTamChave) ;

}/ / Continua na prxima transparncia



public Object pesquisa ( String chave) {int indice = this .pesquisaIndice (chave) ;i f ( indice < this .M) return this . tabela [ indice ] . item;else return null ; / / pesquisa sem sucesso

}public void insere ( String chave, Object item ) {

i f ( this .pesquisa (chave) == null ) {int in ic ia l = this .h (chave, this .pesos) ;int indice = in ic ia l ; int i = 0;while ( this . tabela [ indice ] != null &&

! this . tabela [ indice ] . retirado &&i < this .M)

indice = ( in ic ia l + (++ i )) % this .M;i f ( i < this .M) this . tabela [ indice ] =

new Celula (chave, item) ;else System.out . print ln ( "Tabela cheia" ) ;

} else System.out . print ln ( "Registro ja esta presente" ) ;}




public void ret i ra ( String chave) throws Exception {int i = this .pesquisaIndice (chave) ;i f ( i < this .M) {

this . tabela [ i ] . retirado = true ;this . tabela [ i ] .chave = null ;

} else System.out . print ln ( "Registro nao esta presente" ) ;}private int pesquisaIndice ( String chave) {int in ic ia l = this .h (chave, this .pesos) ;int indice = in ic ia l ; int i = 0;while ( this . tabela [ indice ] != null &&

!chave.equals ( this . tabela [ indice ] .chave) &&i < this .M) indice = ( in ic ia l + (++ i )) % this .M;

i f ( this . tabela [ indice ] != null &&chave.equals ( this . tabela [ indice ] .chave))

return indice ;else return this .M; / / pesquisa sem sucesso

}}


Anlise

Seja = N/M o fator de carga da tabela.Conforme demonstrado por Knuth (1973), ocusto de uma pesquisa com sucesso

C(n) =1

2

(1 +

1

1 )

O hashing linear sofre de um mal chamadoagrupamento(clustering) (Knuth, 1973,pp.520521).

Este fenmeno ocorre na medida em que atabela comea a ficar cheia, pois a inserode uma nova chave tende a ocupar umaposio na tabela que esteja contgua aoutras posies j ocupadas, o que deteriorao tempo necessrio para novas pesquisas.

Entretanto, apesar do hashing linear ser ummtodo relativamente pobre para resolvercolises os resultados apresentados sobons.

O melhor caso, assim como o caso mdio, O(1).


Vantagens e Desvantagens deTransformao da ChaveVantagens:

Alta eficincia no custo de pesquisa, que O(1) para o caso mdio.

Simplicidade de implementao.Desvantagens:

Custo para recuperar os registros na ordemlexicogrfica das chaves alto, sendonecessrio ordenar o arquivo.

Pior caso O(N).


Hashing Perfeito

Se h(xi) = h(xj) se e somente se i = j, entono h colises, e a funo de transformao chamada de funo de transformaoperfeita ou funo hashing perfeita(hp).

Se o nmero de chaves N e o tamanho databela M so iguais ( = N/M = 1), entotemos uma funo de transformaoperfeita mnima.

Se xi xj e hp(xi) hp(xj), ento a ordemlexicogrfica preservada. Nesse caso,temos uma funo de transformaoperfeita mnima com ordem preservada.


Vantagens e Desvantagens de UmaFuno de Transformao Perfeita

No h necessidade de armazenar a chave,pois o registro localizado sempre a partir doresultado da funo de transformao.

Uma funo de transformao perfeita especfica para um conjunto de chavesconhecido.

A desvantagem no caso o espao ocupadopara descrever a funo de transformao hp.

Entretanto, possvel obter um mtodo comM 1, 25N , para valores grandes de N .


Algoritmo de Czech, Havas e Majewski Czech, Havas e Majewski (1992, 1997)

propem um mtodo elegante baseado emgrafos randmicos para obter uma funode transformao perfeita com ordempreservada.

A funo de transformao do tipo:

hp(x) = (g(h1(x)) + g(h2(x))) mod N,

na qual h1(x) e h2(x) so duas funes noperfeitas, x a chave de busca, e g umarranjo especial que mapeia nmeros nointervalo 0 . . .M 1 para o intervalo0 . . . N 1.


Problema Resolvido Pelo Algoritmo

Dado um grafo no direcionado G = (V,A),onde |V | = M e |A| = N , encontre umafuno g : V [0, N 1], definida comohp(a = (u, v) A) = (g(u) + g(v)) mod N .

Em outras palavras, estamos procurando umaatribuio de valores aos vrtices de G talque a soma dos valores associados aosvrtices de cada aresta tomado mdulo N um nmero nico no intervalo [0, N 1].

A questo principal como obter uma funog adequada. A abordagem mostrada a seguir baseada em grafos e hipergrafosrandmicos.


Exemplo

Chaves: 12 meses do ano abreviados paraos trs primeiros caracteres.

Objetivo: obter uma funo de transformaoperfeita hp de tal forma que o i-simo ms mantido na (i 1)-sima posio da tabelahash:

Chave x h1(x) h2(x) hp(x)jan 10 11 0fev 1 2 1mar 8 9 2abr 1 3 3mai 0 5 4jun 10 9 5jul 0 3 6

ago 5 6 7set 4 1 8out 0 1 9nov 3 2 10dez 4 7 11


Grafo Randmico gerado

O problema de obter a funo g equivalentea encontrar um grafo no direcionadocontendo M vrtices e N arestas.

3

6

9

1

2

5

48

7

110

10

4

11

8

63

1

10

9

7

2

0

5

Os vrtices so rotulados com valores nointervalo 0 . . .M 1

As arestas definidas por (h1(x), h2(x)) paracada uma das N chaves x.

Cada chave corresponde a uma aresta que rotulada com o valor desejado para a funohp perfeita.

Os valores das duas funes h1(x) e h2(x)definem os vrtices sobre os quais a aresta incidente.


Obteno da Funo g a Partir doGrafo

Passo importante: conseguir um arranjo gde vrtices para inteiros no intervalo0 . . . N 1 tal que, para cada aresta(h1(x), h2(x)), o valor dehp(x) = g(h1(x)) + g(h2(x))) mod N seja igualao rtulo da aresta.

Algoritmo:1. Qualquer vrtice no processado

escolhido e feito g[v] = 0.2. As arestas que saem do vrtice v so

seguidas e o valor g(u) do vrtice udestino rotulado com o valor dadiferena entre o valor da aresta (v, u) eg(v), tomado mod N .

3. Procura-se o prximo componenteconectado ainda no visitado e osmesmos passos descritos acima sorepetidos.


Seguindo o Algoritmo para Obter g noExemplo dos 12 Meses do Ano

3

6

9

1

2

5

48

7

110

10

4

11

8

63

1

10

9

7

2

0

5

Chave x h1(x) h2(x) hp(x) v : g(v)jan 10 11 0 0 0fev 1 2 1 1 9mar 8 9 2 2 4abr 1 3 3 3 6mai 0 5 4 4 11

(a) jun 10 9 5 (b) 5 4jul 0 3 6 6 3

ago 5 6 7 7 0set 4 1 8 8 0out 0 1 9 9 2nov 3 2 10 10 3dez 4 7 11 11 9


Problema

Quando o grafo contm ciclos: omapeamento a ser realizado pode rotular denovo um vrtice j processado e que tenharecebido outro rtulo com valor diferente.

Por exemplo, se a aresta (5, 6), que a arestade rtulo 7, tivesse sido sorteada para aaresta (8, 11), o algoritmo tentaria atribuir doisvalores distintos para o valor de g[11].

Para enxergar isso, vimos que se g[8] = 0,ento g[11] deveria ser igual a 7, e no igualao valor 9 obtido acima.

Um grafo que permite a atribuio de doisvalores de g para um mesmo vrtice, no vlido.

Grafos acclicos no possuem este problema. Um caminho seguro para se ter sucesso

obter antes um grafo acclico e depois realizara atribuio de valores para o arranjo g.Czech, Havas e Majewski (1992).


Primeiro Refinamento doProcedimento para Atribuir Valores aoArranjo gboolean rotuleDe ( int v , int c , Grafo G, int g [ ] ) {

boolean grafoRotulavel = true ;i f (g[v ] != Indefinido ) i f (g[v ] != c)

grafoRotulavel = false ;else {

g[v] = c;for (u G. listaAdjacentes (v))

rotuleDe (u, (G.aresta (v,u) g[v]) % N, g) ;}return grafoRotulavel ;

}boolean atribuig (Grafo G, int g [ ] ) {

boolean grafoRotulavel = true ;for ( int v = 0; v < M; v++) g[v] = Indefinido ;for ( int v = 0; v < M; v++)

i f (g[v] == Indefinido )grafoRotulavel = rotuleDe (v, 0 , G, g) ;

return grafoRotulavel ;}


Algoritmo para Obter a Funo deTransformao Perfeitavoid obtemHashingPerfeito ( ) {

Ler conjunto de N chaves;Escolha um valor para M ;do {

Gera os pesos p1[i] e p2[i] para0 i maxTamChave 1 ;

Gera o grafo G = (V,A) ;grafoRotulavel = atribuig (G, g) ;

} while ( ! grafoRotulavel ) ;Retorna p1 , p2 e g ;

}


Estruturas de dados e operaes paraobter a funo hash perfeitapackage cap5.fhpm;import java . io . ;import cap7. l istaadj . arranjo .Grafo ; / / vide Programas do captulo7public class FHPM {

private int p1[ ] , p2 [ ] ; / / pesos de h1 e h2private int g [ ] ; / / funo gprivate int N; / / nmero de chavesprivate int M; / / nmero de vrticesprivate int maxTamChave, nGrafosGerados, nGrafosConsiderados;private final int Indefinido = 1;/ / Entram aqui os mtodos privados das transparncias 76, 103 e 104public FHPM ( int maxTamChave, int n, float c ) {

this .N = n; this .M = ( int ) (cthis .N) ;this .maxTamChave = maxTamChave; this .g = new int [ this .M] ;

}public void obtemHashingPerfeito ( String nomeArqEnt)

throws Exception {BufferedReader arqEnt = new BufferedReader (

new FileReader (nomeArqEnt) ) ;String conjChaves[ ] = new String [ this .N] ;this .nGrafosGerados = 0;this .nGrafosConsiderados = 0; int i = 0;



Estruturas de dados e operaes paraobter a funo hash perfeita

while ( ( i < this .N) &&((conjChaves[ i ] = arqEnt. readLine ( ) ) != null ) ) i ++;

i f ( i != this .N)throw new Exception ( "Erro : Arquivo de entrada possui"+

"menos que "+this .N + " chaves" ) ;

boolean grafoRotulavel = true ;do {

Grafo grafo = this .geraGrafo (conjChaves) ;grafoRotulavel = this . atribuig ( grafo ) ;

}while ( ! grafoRotulavel ) ;arqEnt.close ( ) ;

}public int hp ( String chave) {

return (g[h (chave, p1) ] + g[h (chave, p2)]) % N;}/ / Entram aqui os mtodos pblicos dos Programas 106 e 107

}


Gera um Grafo sem Arestas Repetidase sem Self-Loopsprivate Grafo geraGrafo ( String conjChaves [ ] ) {

Grafo grafo ; boolean grafoValido ;do {

grafo = new Grafo ( this .M, this .N) ; grafoValido = true ;this .p1 = this .geraPesos ( this .maxTamChave) ;this .p2 = this .geraPesos ( this .maxTamChave) ;for ( int i = 0; i < this .N; i ++) {

int v1 = this .h (conjChaves[ i ] , this .p1) ;int v2 = this .h (conjChaves[ i ] , this .p2) ;i f ( (v1 == v2 ) | | grafo .existeAresta(v1, v2) ) {

grafoValido = false ; grafo = null ; break;} else {

grafo . insereAresta (v1, v2, i ) ;grafo . insereAresta (v2, v1, i ) ;

}}this .nGrafosGerados ++;

} while ( ! grafoValido ) ;return grafo ;

}


Rotula Grafo e Atribui Valores para OArranjo gprivate boolean rotuleDe ( int v , int c , Grafo grafo ) {

boolean grafoRotulavel = true ;i f ( this .g[v ] != Indefinido ) {

i f ( this .g[v ] != c ) {this .nGrafosConsiderados++; grafoRotulavel = false ;

}} else {

this .g[v] = c;i f ( ! grafo . listaAdjVazia (v ) ) {

Grafo.Aresta adj = grafo . primeiroListaAdj (v ) ;while ( adj != null ) {

int u = adj .peso () this .g[v ] ;i f (u < 0) u = u + this .N;grafoRotulavel = rotuleDe(adj . vertice2 () ,u,grafo ) ;i f ( ! grafoRotulavel ) break ; / / sai do loopadj = grafo .proxAdj (v ) ;

}}

}return grafoRotulavel ;

}



Rotula Grafo e Atribui Valores para OArranjo gprivate boolean atribuig (Grafo grafo ) {

boolean grafoRotulavel = true ;for ( int v = 0; v < this .M; v++) this .g[v] = Indefinido ;for ( int v = 0; v < this .M; v++) {

i f ( this .g[v] == Indefinido )grafoRotulavel = this . rotuleDe (v, 0 , grafo ) ;

i f ( ! grafoRotulavel ) break;}return grafoRotulavel ;

}


Mtodo para salvar no disco a funode transformao perfeitapublic void salvar ( String nomeArqSaida) throws Exception {

BufferedWriter arqSaida = new BufferedWriter (new FileWriter (nomeArqSaida) ) ;

arqSaida. write ( this .N + " (N) \n" ) ;arqSaida. write ( this .M + " (M) \n" ) ;arqSaida. write ( this .maxTamChave + " (maxTamChave) \n" ) ;

for ( int i = 0; i < this .maxTamChave; i++)arqSaida. write ( this .p1[ i ] + " " ) ;

arqSaida. write ( " (p1) \n" ) ;

for ( int i = 0; i < this .maxTamChave; i++)arqSaida. write ( this .p2[ i ] + " " ) ;

arqSaida. write ( " (p2) \n" ) ;

for ( int i = 0; i < this .M; i++)arqSaida. write ( this .g[ i ] + " " ) ;

arqSaida. write ( " (g) \n" ) ;

arqSaida. write ( "No. grafos gerados por geraGrafo: " +this .nGrafosGerados + " \n" ) ;

arqSaida. write ( "No. grafos considerados por atribuig : " +( this .nGrafosConsiderados + 1) + " \n" ) ;

arqSaida.close ( ) ;}


Mtodo para ler do disco a funo detransformao perfeitapublic void ler ( String nomeArqFHPM) throws Exception {

BufferedReader arqFHPM = new BufferedReader (new FileReader (nomeArqFHPM)) ;

String temp = arqFHPM.readLine( ) , valor = temp.substring(0 ,temp.indexOf ( " " ) ) ;

this .N = Integer .parseInt ( valor ) ;temp = arqFHPM.readLine ( ) ; valor = temp.substring(0 ,

temp.indexOf ( " " ) ) ;this .M = Integer .parseInt ( valor ) ;temp = arqFHPM.readLine ( ) ; valor = temp.substring(0 ,

temp.indexOf ( " " ) ) ;this .maxTamChave = Integer .parseInt ( valor ) ;temp = arqFHPM.readLine ( ) ; int inicio = 0;this .p1 = new int [ this .maxTamChave] ;for ( int i = 0; i < this .maxTamChave; i ++) {

int fim = temp.indexOf ( , inicio ) ;valor = temp.substring( inicio , fim ) ;inicio = fim + 1; this .p1[ i ] = Integer .parseInt ( valor ) ;

}temp = arqFHPM.readLine ( ) ; inicio = 0;this .p2 = new int [ this .maxTamChave] ;for ( int i = 0; i < this .maxTamChave; i ++) {

int fim = temp.indexOf ( , inicio ) ;valor = temp.substring( inicio , fim ) ;inicio = fim + 1; this .p2[ i ] = Integer .parseInt ( valor ) ;

}temp = arqFHPM.readLine ( ) ; inicio = 0;this .g = new int [ this .M] ;for ( int i = 0; i < this .M; i ++) {

int fim = temp.indexOf ( , inicio ) ; valor =temp.substring( inicio , fim ) ;inicio = fim + 1; this .g[ i ] = Integer .parseInt ( valor ) ;

}arqFHPM.close ( ) ;

}


Programa para gerar uma funo detransformao perfeitapackage cap5;import java . io . ;import cap5.fhpm.FHPM; / / vide transparncia 101public class GeraFHPM {

public static void main ( String [ ] args ) {BufferedReader in = new BufferedReader (

new InputStreamReader (System. in ) ) ;try {

System.out . print ( "Numero de chaves: " ) ;int n = Integer .parseInt ( in . readLine ( ) ) ;System.out . print ( "Tamanho da maior chave: " ) ;int maxTamChave = Integer .parseInt ( in . readLine ( ) ) ;System.out . print ( "Nome do arquivo com chaves a serem lidas : " ) ;String nomeArqEnt = in .readLine ( ) ;System.out . print ( "Nome do arquivo para gravar a FHPM: " ) ;String nomeArqSaida = in .readLine ( ) ;FHPM fhpm = new FHPM (maxTamChave, n, 3) ;fhpm.obtemHashingPerfeito (nomeArqEnt) ;fhpm.salvar (nomeArqSaida) ;

} catch (Exception e) {System.out . println (e.getMessage ( ) ) ; }}

}


Programa para testar uma funo detransformao perfeitapackage cap5;import java . io . ;import cap5.fhpm.FHPM; / / vide transparncia 101public class TestaFHPM {

public static void main ( String [ ] args ) {BufferedReader in = new BufferedReader (

new InputStreamReader (System. in ) ) ;try {

System.out . print ( "Nome do arquivo com a FHPM: " ) ;String nomeArqEnt = in .readLine ( ) ;FHPM fhpm = new FHPM (0 , 0 , 0);fhpm. ler (nomeArqEnt) ;System.out . print ( "Chave: " ) ; String chave = in .readLine ( ) ;while ( !chave.equals ( "aaaaaa" ) ) {

System.out . println ( " Indice : " + fhpm.hp (chave) ) ;System.out . print ( "Chave: " ) ; chave = in .readLine ( ) ;

}} catch (Exception e) {System.out . println (e.getMessage ( ) ) ; }

}}


Anlise

A questo crucial : quantas interaes sonecessrias para obter um grafo G = (V,A)que seja rotulvel?

Para grafos arbitrrios, difcil achar umasoluo para esse problema, isso se existir talsoluo.

Entretanto, para grafos acclicos, a funo gexiste sempre e pode ser obtida facilmente.

Assim, a resposta a esta questo depende dovalor de M que escolhido no primeiro passodo algoritmo.

Quanto maior o valor de M , mais esparso ografo e, conseqentemente, mais provvelque ele seja acclico.


Anlise

Segundo Czech, Havas e Majewski (1992),quando M 2N a probabilidade de geraraleatoriamente um grafo acclico tende parazero quando N cresce.

Isto ocorre porque o grafo se torna denso, e ogrande nmero de arestas pode levar formao de ciclos.

Por outro lado, quando M > 2N , aprobabilidade de que um grafo randmicocontendo M vrtices e N arestas seja acclico aproximadamente

M 2N

M,

E o nmero esperado de grafos gerados atque o primeiro acclico seja obtido :

M

M 2N


Anlise

Para M = 3N o nmero esperado deiteraes

3, em mdia,

aproximadamente 1,7 grafos sero testadosantes que aparea um grafo acclico.

Logo, a complexidade de tempo para gerar afuno de transformao proporcional aonmero de chaves a serem inseridas natabela hash, desde que M > 2N .

O grande inconveniente de usar M = 3N oespao necessrio para armazenar o arranjog.

Por outro lado, considerar M < 2N podeimplicar na necessidade de gerar muitosgrficos randmicos at que um grafo acclicoseja encontrado.


Outra Alternativa

No utilizar grafos tradicionais, mas simhipergrafos, ou r-grafos, nos quais cadaaresta conecta um nmero qualquer r devrtices.

Para tanto, basta usar uma terceira funo h3para gerar um trigrafo com arestasconectando trs vrtices, chamado de3-grafo.

Em outras palavras, cada aresta uma triplado tipo (h1(x), h2(x), h3(x)), e a funo detransformao dada por:

h(x) = (g(h1(x)) + g(h2(x)) + g(h3(x))) mod N.


Outra Alternativa

Nesse caso, o valor de M pode ser prximo a1, 23N .

Logo, o uso de trigrafos reduz o custo deespao da funo de transformao perfeita,mas aumenta o tempo de acesso aodicionrio.

Alm disso, o processo de rotulao nopode ser feito como descrito.

Ciclos devem ser detectados previamente,utilizando a seguinte propriedade de r-grafos:

Um r-grafo acclico se e somente se aremoo repetida de arestas contendoapenas vrtices de grau 1 (isto , vrticessobre os quais incide apenas uma aresta)elimina todas as arestas do grafo.


Experimentos

# Chaves # Chamadas # Chamadas TempogeraGrafo atribuig (s)

10 3586 1 0.13020 20795 16 0.21730 55482 24 0.39040 52077 33 0.43250 47828 19 0.46260 27556 10 0.31370 26265 17 0.35180 161736 92 1.54390 117014 106 1.228

100 43123 26 0.559

Documents

Cap 5 - Pesquisa em Memória Primária