Patricia (1)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Practical
Algorithm
To
Retrieve
Information 
Coded 
In 
Alphanumeric
Integrantes do grupo:
Ate o momento 
Rodrigo melo dos Santos 
Algoritmo Prático para Recuperar Informações Codificadas em Alfanuméricas
ÁRVORE PATRICIA
Origem
Foi desenvolvida em 1968 por Donald R. Morrison para aplicações de recuperação de informação em arquivos de grande porte;
Trie Compactada Binária;
Uma Trie usa cada uma das partes de uma chave, por vez, para determinar a sub-árvore. Por outro lado, a árvore PATRICIA escolhe um elemento da chave (armazenando a sua posição) para determinar a sub-árvore. Isso remove a necessidade de nós com apenas um descendente.
Caminhos que contém nós com apenas 1 filho são agrupados em uma única aresta;
Patrícia é abreviatura de Practical Algorithm To Retrieve Information Coded In Alphanumeric (Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico)
Arvore Patrícia 
O algoritmo para construção da árvore Patrícia é baseado no método de pesquisa digital, mas sem apresentar o inconveniente das tries. 
 É construída a partir da árvore binária de prefixo. 
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 caractere a ser testado para decidir qual subárvore seguir.
Exemplos de funcionamento
Identifica a posição do caractere da chave informada para ser analisado;
Apresenta o caractere que deve ser comparado ao da chave informada, se a chave é menor ou igual ao nodo ela é consultada à esquerda se não à direita.
Exemplo 
Inserção X = B
B = 010010
C = 010011
H = 011000
 J = 100001
Q = 101000
K = 100010
W = 110110
B
Inserção X = J
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
B
J
1
0
Inserção X = H
 1
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
B
J
0
B e H seguem o padrão 0xxxxx
Inserção X = H
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
J
0
B e H seguem o padrão 0xxxxx
O 3º bit diferencia B de H
3
B
H
1
0
1
Inserção X = Q
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
J
0
J e Q seguem o padrão 
1xxxxx.
3
B
H
1
0
1
Inserção X = Q
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
0
J e Q seguem o padrão 
1xxxxx.
O 3º bit diferencia J de Q
3
B
H
1
0
1
3
J
Q
0
1
Inserção X = C
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
0
B e C seguem o padrão 
0x0xxx.
3
B
H
1
0
1
3
J
Q
0
1
Inserção X = C
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
0
B e C seguem o padrão 
0x0xxx.
O 6º bit diferencia B de C
3
H
1
0
1
3
J
Q
0
1
6
B
C
0
1
Inserção X = K
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
0
J e K seguem o padrão 
1x0xxx.
3
H
1
0
1
3
J
Q
0
1
6
B
C
0
1
Inserção X = K
 
B = 010010
C = 010011
H = 011000
J = 100001
Q = 101000
K = 100010
W = 110110
1
0
J e K seguem o padrão 
1x0xxx.
O 5º bit diferencia J de K
3
H
1
0
1
3
Q
0
1
6
B
C
0
1
5
J
K
0
1
Exemplo de inserção
Palavra 1 = Consultório 
Palavra 2 = Consultar
Cascalho, cascata
Encontrada diferença no sexto caractere.
Alocação do nodo Pai armazenamento do registro.
6,a
cascalho
cascata
Exemplo de consulta
Busca por “Consultório”
7,a
Consulado
1,a
Consultar
Consultório
Etapas: 
1) Primeiro Nodo Informa pra Comparar 7º Caractere da Palavra com “a”. 
2) Como “t” é maior que “a” desloca-se pra sub-árvore da direita. 
3) Compara-se agora o 8º Caractere da Chave com “a”.
4) Como “ó” é maior que ele, percorre a sub-árvore da direita e acha a palavra.
Exemplo de deleção
Apagar “Consulado”
7,a
1,a
Consulado
Consultar
Consultório
8,a
Consultar
Consultório
Etapas: 
1) Primeiro busca-se e Apaga-se a Palavra “Consulado” da Árvore.
 
2) Soma-se o valor do Campo Avançar do Nó Pai a Todos os nós Filhos.
Árvore Patrícia: Algoritmo de inserção
1. Se a subárvore atual for vazia, é criado um nó de informação com a chave X (isto ocorre somente na inserção da primeira chave) e o algoritmo termina 2. Se a subárvore atual for simplesmente um nó de informação, os bits da chave X são comparados, a partir do bit de índice imediatamente após o último índice da seqüência de índices consecutivos do caminho de pesquisa, com os bits correspondentes da chave X deste nó de informação, até encontrar um índice i cujos bits sejam diferentes – A comparação dos bits a partir do último índice consecutivo melhora o desempenho do algoritmo: se todos forem iguais, a chave já se encontra na árvore e o algoritmo termina; senão, vai para o passo 4
Árvore Patrícia: Algoritmo de inserção
3. Se a raiz da subárvore atual for um nó de desvio, deve-se prosseguir para a subárvore indicada pelo bit da chave X de índice dado pelo nó atual, de forma recursiva 4. Criar um nó de desvio e um nó de informação: o primeiro contendo o índice i e o segundo a chave X. A seguir, o nó de desvio é ligado ao de informação pelo ponteiro de subárvore esquerda ou direita, dependendo se o bit de índice i da chave X seja 0 ou 1, respectivamente 5. O caminho de inserção é percorrido novamente de baixo para cima, subindo com o par de nós criados no passo 4 até chegar a um nó de desvio cujo índice seja menor que o índice i determinado no passo 2: este é o ponto de inserção e o par de nós é inserido
APLICAÇÕES
Banco de Dados
O tamanho de uma árvore PATRICIA não depende do tamanho das chaves inseridas nela. Cada nova chave adiciona no máximo um novo nó na árvore. Diferente da árvore-B, a árvore PATRICIA cresce lentamente mesmo com a inserção de um número grande de strings, por causa da alta compressão inerente da estrutura. O ScaleDB é uma estrutura baseada na árvore PATRICIA, porém otimizado para o acesso em disco como a árvore-B.
APLICAÇÕES
Busca em redes P2P
Uma questão importante em sistemas P2P é como localizar pontos que contém informação relevante para uma determinada consulta. Para isso, cada ponto capaz de tomar decisões de roteamento precisa manter um índice com os caminhos dos arquivos XML dos vizinhos. Esses índices podem ser eficientemente armazenados em árvores PATRICIA.
APLICAÇÕES
O problema do maior prefixo comum
Encontrar o maior prefixo comum é um problema antigo com diversas aplicações, desde o problema de strings em comum até busca de IP em roteadores de Internet. Com o uso da árvore PATRICIA é possível realizar as funções de Buscarprefixo(x) e Inserir(x) com complexidade de tempo O(log|x|), e Deletar(x) em O(1), onde |x| é o número de bits usados para codificar x. Ou seja, depende apenas de |x| e não do tamanho da estrutura de dados.
APLICAÇÕES
Ganho de eficiência com documentos XML
A medida em que XML se torna o padrão para troca de informações na Internet, como acessar precisamente dados salvos em arquivos XML aparece como um problema crucial para ser resolvido. A estrutura de indexação usada em XML pode ser substituída por uma estrutura do tipo PATRICIA para ganho de performance em tempo de execução das operações.
Bibliografia 
https://marciobueno.com/
http://www.inf.ufrgs.br/
https://pt.wikipedia.org/
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/
pluzzardi.w.pw/PATRICIA_Monica_2008.ppt