Apresentação para o seminário da disciplina Projeto de Algoritmos II
Tem-se uma maior capacidade de armazenamento em dispositivos de memória (primária e secundária);
Arquivos de grande conteúdo (que estão na RAM) puderam ser manipulados;
Problema: como recuperar uma informação em meio a tantas dentro desse arquivo?
Solução: métodos de pesquisa: sequencial, binária… e pesquisa digital!
Morrison, D. R. (1968). PATRICIA—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4), 514-534.
Usaremos as sete palavras casco, cascalho, cascata, dama, domando, dominar e domínio para representar as árvores.
Algumas definições diferentes foram encontradas:
Optamos por nos ater à definição de árvore PATRICIA como variação de árvore Trie.
Node
¶class Node:
def __init__(self, pos, val, prefixo):
"""
Unidade basica
:param int pos:
:param str val:
:param str prefixo:
"""
self.filhos = [None, None]
self.prefixo = prefixo
self.pos = pos
self.val = ord(val)
def get(self, palavra):
if palavra[:self.pos] != self.prefixo or len(palavra) <= self.pos: return 0
valor = ord(palavra[self.pos])
if valor <= self.val:
return self.filhos[0]
return self.filhos[1]
def derivados(self):
derivados = []
for i in self.filhos:
if type(i) == str: derivados.append(i[:-1])
else: derivados += i.derivados()
return derivados
def __repr__(self):
return "[{}|{}]".format(self.pos, chr(self.val))
Arvore
¶class Arvore:
def __init__(self, raiz):
"""
Inicia a árvore
:param str raiz:
"""
self.raiz = raiz + "$"
def get_intersect(self, p1, p2):
"""
Buca o ponto onde duas strings de diferenciam
:param str p1:
:param str p2:
:return int:
"""
for i in range(len(p1)):
if len(p2) > i:
if p1[i] != p2[i]: return i
def insere(self, palavra):
"""
Insere uma string na árvore
:param str palavra:
:return None:
"""
# print("Inserindo %s" % palavra)
if self.check(palavra):
print("[Erro] Palavra já inserida")
return
palavra += '$'
pai = None
node = self.raiz
i = 0
while 1:
# Caso nó folha
if type(node) == str:
pos = self.get_intersect(palavra, node)
# Caso nó folha é raiz também
if pai is None:
l = sorted([(ord(palavra[pos]), palavra), (ord(node[pos]),node)])
self.raiz = Node(pos, chr(l[0][0]), l[0][1][:pos])
self.raiz.filhos = [k[1] for k in l]
return
# Caso padrão
else:
lado = pai.filhos.index(node)
l = sorted([(ord(palavra[pos]), palavra), (ord(node[pos]),node)])
pai.filhos[lado] = Node(pos, chr(l[0][0]), l[0][1][:pos])
pai.filhos[lado].filhos = [k[1] for k in l]
return
else:
prox = node.get(palavra)
# Caso prefixo não combina
if not prox:
pos = self.get_intersect(palavra, node.prefixo)
l = sorted([(ord(palavra[pos]), palavra), (ord(node.prefixo[pos]),node)])
# Caso raiz
if pai is None:
self.raiz = Node(pos, chr(l[0][0]), palavra[:pos])
self.raiz.filhos = [k[1] for k in l]
return
else:
lado = pai.filhos.index(node)
pai.filhos[lado] = Node(pos, chr(l[0][0]), palavra[:pos])
pai.filhos[lado].filhos = [k[1] for k in l]
return
# Base de iteração
else:
pai = node
node = prox
def check(self, palavra):
palavra += '$'
node = self.raiz
while 1:
if type(node) == str:
return node == palavra
next = node.get(palavra)
if next:
node = next
else:
return False
def remove(self, palavra):
if not self.check(palavra):
print("[Erro] Palavra não encontrada")
return
palavra += '$'
avo = None
pai = None
node = self.raiz
while 1:
if type(node) == str:
if pai is None:
print("[Erro] Não é possível remover único item da arvore")
return
else:
pai.filhos.remove(node)
novo_sucessor = pai.filhos[0]
if avo is None:
self.raiz = novo_sucessor
del pai
return
else:
index = avo.filhos.index(pai)
avo.filhos[index] = novo_sucessor
del pai
return
else:
prox = node.get(palavra)
if pai is None:
pai = node
node = prox
else:
avo = pai
pai = node
node = prox
def derivados(self, prefixo):
"""
Exibe folhas derivadas de determinado prefixo
:param str prefixo:
:return str[]:
"""
tam = len(prefixo)
node = self.raiz
while 1:
if type(node) == str:
if node[:tam] == prefixo:
return [node[:-1]]
else:
return []
else:
if node.prefixo == prefixo or node.prefixo[:tam] == prefixo:
return node.derivados()
next = node.get(prefixo)
if next:
node = next
else:
return []
Realizaremos o mesmo exemplo exposto anteriormente, só que na prática.
tree = Arvore("casco")
tree.raiz
'casco$'
Ao visualizar a raíz, notamos a presença de uma string. Isso quer dizer que estamos em um nó folha, fato este representado pelo $$$ que finaliza a palavra.
type(tree.raiz)
str
Naturalmente, pelo fato desta árvore conter apenas uma palavra, não há uso de objetos Node
, tampouco há a presença de filhos:
try:
tree.raiz.filhos
except AttributeError:
print("Não há filhos!")
Não há filhos!
# tree.raiz.filhos
A inserção de mais uma palavra fará com que o objeto str
seja substituído por um Node
, e que a profundidade da árvore aumente.
tree.insere("cascalho")
tree.raiz
[4|a]
tree.raiz.filhos
['cascalho$', 'casco$']
Sigamos adiante com a adição das demais palavras:
tree.insere("cascata")
tree.insere("dama")
tree.insere("domando")
tree.insere("dominar")
tree.insere("domínio")
Vejamos como a árvore está em relação à imagem vista anteriormente, replicada abaixo por conveniência:
Profundidade 0:
tree.raiz
[0|c]
Profundidade 1:
tree.raiz.filhos
[[4|a], [1|a]]
Profundidade 2:
(tree.raiz.filhos[0].filhos +
tree.raiz.filhos[1].filhos)
[[5|l], 'casco$', 'dama$', [3|a]]
Para efeito ilustrativo, adicionaremos a partir daqui espaços vazios quando houver folhas (objetos Node
sem filho)
Profundidade 3:
(tree.raiz.filhos[0].filhos[0].filhos +
[""] +
[""] +
[""] +
[""] +
tree.raiz.filhos[1].filhos[1].filhos)
['cascalho$', 'cascata$', '', '', '', '', 'domando$', [3|i]]
Profundidade 4:
([""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
[""] +
tree.raiz.filhos[1].filhos[1].filhos[1].filhos)
['', '', '', '', '', '', '', '', '', '', '', '', '', '', 'dominar$', 'domínio$']
A fim de garantir a confiabilidade da estrutura de dados, fizemos um teste intensivo de inserção de palavras, valendo-nos do dicionário em português do Brasil fornecido pelo LibreOffice.
from random import shuffle
def load_dict(path):
with open(path, "r", encoding="utf-8") as file:
return [line.strip("\n") for line in file.readlines()]
Carreguemos o dicionário:
pt_br = load_dict("./dictionaries/palavras.txt")
print(f"O dicionário possui {len(pt_br)} palavras.")
O dicionário possui 320139 palavras.
O teste consiste na inserção, verificação e remoção de palavras de forma aleatória. Dessa forma, precisamos de três cópias do dicionário:
load = pt_br.copy()
check = pt_br.copy()
remove = pt_br.copy()
print(f"load[:5]: {load[:5]}")
print(f"check[:5]: {check[:5]}")
print(f"remove[:5]: {remove[:5]}")
load[:5]: ['a', 'ª', 'à', 'á', 'ã'] check[:5]: ['a', 'ª', 'à', 'á', 'ã'] remove[:5]: ['a', 'ª', 'à', 'á', 'ã']
Vamos utilizar a função shuffle
, do módulo random
, para obter versões aleatorizadas do dicionário:
shuffle(load)
shuffle(check)
shuffle(remove)
print(f"load[:5]: {load[:5]}")
print(f"check[:5]: {check[:5]}")
print(f"remove[:5]: {remove[:5]}")
load[:5]: ['diftógrafo', 'cientifização', 'manolita', 'xantematina', 'ácoros-bastardos'] check[:5]: ['pau-morcego', 'executado', 'catartínico', 'coptotermes', 'alveoliforme'] remove[:5]: ['circungirar', 'colossigmoidostômico', 'francoáceo', 'ofiuroideo', 'asquistítico']
Por fim, seguiremos adiante com o teste propriamente dito. Basicamente, a expectativa é que a primeira palavra inserida seja a primeira da lista load
e termine com a primeira palavra de remove
.
tree = Arvore(load[0])
tree.raiz
'diftógrafo$'
print("Inserindo...")
for word in load[1:]:
# print(f"Inserting {word}...")
tree.insere(word)
if not tree.check(word):
raise ValueError(f"Não pude encontrar a palavra {word}!")
print("Verificando...")
for word in check:
# print(f"Verifying {word}...")
if not tree.check(word):
raise ValueError(f"Não pude verificar que a palavra {word} está mesmo na árvore!")
print("Removendo...")
for word in remove[1:]:
# print(f"Removing {word}...")
tree.remove(word)
if tree.check(word):
raise ValueError(f"Não consegui remover a palavra {word}!")
print("Sucesso.")
Inserindo... Verificando... Removendo... Sucesso.
tree.raiz
'circungirar$'
Perguntas?