P.A.T.R.I.C.I.A. TREE
Carla Martins
Celso Feilstrecker
Eduardo Gonçalves
Emanuele Andrea Klein
Fausto Tomazi
O QUE É ?
• PATRICIA é a abreviatura de Pratical Algorithm To
Retrieve Information Coded In Alphanumeric (algoritmo
prático para recuperar informações codificadas em
alfanumérico).
• Estrutura de dados proposta por D.R. Morrison, a
PATRICIA TREE, é uma árvore digital binária onde os
bits individuais das chaves são usados para decidir a
ramificação que deverá ser seguida.
A PATRICIA TREE UTILIZA ...
• Índice baseado em um dicionário Trie com
supressão de comparações desnecessárias e tem a
capacidade de pular para frente para eliminar
comparações, sendo uma variação de uma árvore
para as situações em que as chaves são muito
similares, ou seja, tem muitos caracteres em
comum.
QUAL A UTILIDADE ?
• É útil para indexar chaves grandes e tamanho
variável, como por exemplo, títulos ou frases
textuais.
• É útil também para o controle do plágio, pois
detecta se em um texto há cópias evidentes
de um documento, artigo, etc... [1]
ESTRUTURA e COMPONENTES:
N,L
AFASTAMENTO
AFASTOU
Onde:
•N é o número de caracteres que devem ser
avançados para comparação.
•L é a letra a ser comparada.
•Afastamento<Afastou, por isso se encontra na
subávore esquerda. São as chaves externas.
INSERÇÃO:
Cada nodo de uma árvore PATRÍCIA contém o
número de posições que será movido adiante e o
caractere que será comparado. Um sinal de
comparação ( <= ) indica que deve ir para a
subárvore esquerda e um sinal ( > ) indica uma
subárvore a direita.
Palavras a serem comparadas: afastamento e afastou.
6,A
AFASTAMENTO
AFASTOU
INSERÇÃO:
Palavras a serem comparadas: afastamento e afastou.
A F A S T A MENTO
=== == #
A F A S T O U
Ele lê cada caractere, até localizar um diferente. No nodo, ele contará a
partir do 1º nodo pesquisado até o que ele localizou diferente.
Avança 5 caracteres e verifica se a letra diferente é maior do que a da
comparação. Caso seja maior, a palavra ficará na sub-árvore direita. Como
é o caso do exemplo.
5,A
AFASTAMENTO
AFASTOU
FUNCIONAMENTO:
Outro exemplo passo a passo, supomos que temos as
seguintes palavras: marcante ; marcenaria ; maratona .
As palavras serão inseridas na ordem de chegada :
1ª - Comparação ( marcante ) < = (marcenaria) 4º
caractere diferente.
4,A
MARCANTE
MARCENARIA
FUNCIONAMENTO:
Outro exemplo passo a passo, supomos que temos as
seguintes palavras: marcante ; marcenaria ; maratona .As
palavras serão inseridas na ordem de chegada :
1ª - Comparação ( marcante ) < = (marcenaria) 4º
caractere diferente.
M
A
R
4,A
C
A - E
N N
T A
E R
MARCANTE
MARCENARIA
I
A
2 ª - Comparação ( maratona) < = ( marcante) 4º
caractere diferente.
3, A
MARATONA
1, A
MARCANTE
MARCENARIA
Consulta:
1,A
DAMA
2,A
DOMANDO
DOMINAR
2,A
DOMÍNIO
Procurar pela palavra “domando”:
1. No caso do exemplo, ele solicita que avance 1 caractere para fazer a
comparação, ou seja, compara-se o 2º caractere com o caractere
descrito no campo “Compara com”, nesse caso está comparando as
letras “O” com “A” .
2. Como o 2º caractere é maior do que o do nodo, seguirá pela
subávore direita.
3. Aqui, ele encontrará outro nodo para fazer a comparação. Conforme
exemplo, ele avançará dois caracteres a partir do último pesquisa.
Comparará o 4º caractere com a letra indicada.
4. Como são iguais, segue para a sub-árvore esquerda.
5. Neste caso, localizamos a palavra consultada.
Retirada
•Primeiramente é utilizada a consulta para localizar o nodo
a ser excluído.
•Não esquecendo que nossa árvore possui duas estruturas
de nodos os folhas que armazenam as chaves e os nãofolha que controlam a estrutura para uma caminhamento
correto),
Basta fazer com que o nodo controlador que apontava para
o controlador do nosso folha localizado agora passe
apontar diretamente para o controlador seguinte.
Exemplo da Retirada:
Partindo da seguinte arvore:
1,I
MISSÃO
Vamos excluir a palavra “missão”.
3,A
MONTANHA
MONTE
Após excluída a palavra “missão”, a arvore fica assim:
4,A
MONTANHA
Ocorreu a atualização do ponteiro que
de 3 passou para 4.
MONTE
Fontes:
[1] Pereira Jr., Álvaro R. Mecanismo de Detecção de Cópias de
Documentos da Web.
• Página Prof. Ari Ricardo Goetze. http://inf.unisinos.br/~ari