EDITOR DE TEXTO EM C

Prévia do material em texto

FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
INTRODUÇÃO 
PATRÍCIA é a abreviatura de Practical Algorithm To Retrieve Information Coded In Alphanumeric 
(Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico). Este algoritmo foi 
originalmente criado por Morrison (1968) num trabalho de casamento de cadeias, aplicado à 
recuperação de informação em arquivos de grande porte. Knuth (1973) deu um novo tratamento ao 
algoritmo, reapresentando-o de fôrma mais clara como um caso particular de pesquisa digital, 
essencialmente, um caso de árvore trio binária. 
A árvore PATRÍCIA é uma representação compacta de uma Trie onde os nós que teriam apenas um 
filho são agrupados nos seus antecessores. 
Concebido por Donald Morrison, PATRÍCIA é um algoritmo para realização de buscas em árvores 
com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um 
acrônimo de “Practical Algorithm To Retrieve Information Coded In Alphanumeric”, e o método é 
particularmente útil para tratamento de chaves de tamanho variável extremamente longas, tais como 
títulos e frases. A motivação inicial de Morrison foi otimizar a busca de arquivos em bibliotecas. No 
caso de pesquisas analíticas, os dados podem tirar proveito deste método desde que as informações 
sejam armazenadas como cadeias de texto. E é um caso particular da árvore Radix, que é um tipo de 
árvore de prefixos ou TRIE, em outras palavras, a árvore Patrícia é uma árvore Radix binária. 
UTILIZAÇÃO 
Banco de dados 
A tamanho de uma árvore PATRÍCIA 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 PATRÍCIA 
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 PATRÍCIA, porém 
otimizado para o acesso em disco como a árvore-B. 
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 PATRÍCIA. 
O problema do maior prefixo comum 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
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 PATRÍCIA é 
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. 
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 PATRÍCIA 
para ganho de performance em tempo de execução das operações. 
DESENVOLVIMENTO 
O objetivo deste trabalho é fixar a aprendizagem, aprimorar e ampliar o conhecimento obtido em 
nossas últimas aulas. Espera-se ainda que este exercício sirva de ferramenta para que o aluno treine 
suas habilidades adquiridas neste semestre. 
 O trabalho consiste em produzir um pequeno editor de texto que deverá receber uma palavra e 
armazena-la instantaneamente em uma árvore (Patrícia). A medida que o usuário continuar a digitar 
o texto as palavras já armazenadas deverão ser exibidas para que o mesmo possa seleciona-la 
evitando ter que digita-la por completo novamente. Ao final, o texto digitado deverá ser salvo de 
forma compacta para que venha reduzir ao máximo o número de caracteres a serem armazenados na 
memória. 
Este trabalho foi realizado em quatro etapas: 
1. A implementação da arvore patrícia, a implementação do editor de texto sem a arvore 
patrícia. 
2. A adaptação da arvore patrícia no editor de texto. 
3. E a implementação do algoritmo de compactação utilizando a arvore de Huffman, no caso, 
fizemos uso de um código implementado em um trabalho anterior. 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
Arvore Patrícia 
O algoritmo para construção da árvore Patrícia é baseado no método de pesquisa digital, mas sem 
apresentar 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. A Figura 4.11 apresenta a árvore Patrícia gerada a 
partir das chaves B, C, H, J e Q apresentadas acima. 
 
Na estrutura para a arvore Patrícia temos: um tipo chamado ChaveTipoque definirá o tipo de dados 
a ser inserido na arvore; a variável do tipo IndexAmp definirá se o elemento estará a direita ou a 
esquerda da arvore; o tipi Arvore é um ponteiro para a 
estrutura da arvore. 
 
 
 
Enumeração é um outro método de definir constantes, neste caso o 
NoTipo irá definir se o nó será interno ou externo na arvore; 
Na estrutura No_Patricia temos: a variável Chave, que 
será usada para se ter acesso ao elementos na arvore; os 
ponteiros para as subarvore a esquerda e direita; os 
indexadores dos elementos inseridos; 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
A partir da função Dib Bit é possível identificar 
se o elemento esta na subarvore direita ou na 
subarvore esquerda. 
 
 
 
Esta função cria os nós internos da arvore; 
 
 
 
 
Cria um nó externo na arvore. 
 
 
 
 
 
 
Inserção 
Para inserir a chave K = 100010 na árvore da Figura 4.11, 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. Assim, o bit de índice 1 de K é 1, indicando a subárvore direita, e o bit de 
índice 3 indica a subárvore esquerda que, neste caso, é um nó externo. Isto significa que as chaves J 
e K mantêm o padrão de bits 1xOxxx, assim como qualquer outra chave que seguir este caminho de 
pesquisa. Um novo nó interno repõe o nó J, e este 
juntamente com o nó K serão os nós externos 
descendentes. 0 índice do novo nó interno é dado pelo 
primeiro bit diferente das duas chaves em questão, 
que é o bit de índice 5. Para determinar qual será o 
descendente esquerdo e o direito, é só verificar ovalor 
do bit 5 de ambas as chaves, conforme mostrado na Figura 4.12.FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
Inserir uma string em uma árvore Patrícia é similar a pesquisar por essa string até o ponto onde a 
busca é encerrada, pois a string não é encontrada na árvore. Se a busca é encerrada em uma aresta, 
um novo nó é criado nessa aresta. Esse nó armazena a posição do caractere que distingue a chave 
destino daquela aresta e a chave que se deseja inserir, e tem como filhos o nó que estava na 
extremidade seguinte da aresta e um novo nó com a parte restante da nova chave. Se a busca for 
encerrada em um nó, então um nó filho é criado e o restante da nova chave é usado como rótulo 
para aresta entre 
os dois. 
 
 
 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
Pesquisa 
A busca por uma string em uma arvore PATRÍCIA é similar a busca em uma trie, com a diferença 
de que ao chegar em um nó, é comparado apenas um caractere, contra a comparação de substrings 
inteiras que acontece na Trie. A função de pesquisa utilizada na implementação da arvore, não 
atendeu a necessidade do trabalho, uma vez que ao precisarmos que ele retornasse uma string, ela 
retornava um caracter. Por isso a função Busca foi implementada, mas não foi utilizada por 
apresentar o mesmo problema que a função pesquisa. 
 
EDITOR DE TEXTO 
FUNÇÕES 
 
A função Binario exibe uma tabela do texto digitado 
em binário para que se possa compara com a 
compactação. 
A função esperar para por um tempo especifico a 
execução do programa. 
A função posição possibilita que o programador 
escolha a posição na tela 
que deseja visualizar determinada instrução. 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
As funções mensagens, mensagens2 e mensagens3 têm por objetivo exibir mensagens na tela: 
Carregando dicionário, Sair e salvar, Salvando; 
A função cor recebe como parâmetro uma variável do tipo WORD. Ela possibilita que o 
programador modifique as cores do texto ou do fundo. 
A função linhaAnimada através de um laço exibe uma sequencia de caracteres na tela, dando a idéia 
de animação. Já a função linha também exibe uma sequencia de caracteres na tela, mas dessa vez 
os caracteres estão fixo. 
A função Tela_Ini exibe uma tela inicial, informando o tipo de arquivo a ser trabalhado, no caso .txt 
PRINCIPAL 
Variáveis alocadas dinamicamente: DOC receberá o que será digitado, e vet1 armazenará o que foi 
digitado para posteriormente ser salvo no arquivo; 
Apontador DOC apontará para o arquivo que será 
salvo. Apontador FP apontará para o dicionário que 
será inserido na arvore 
c -receberá os caracteres do dicionário ou um caracter 
que ainda não foi digitado 
pesq - recebe o retorno da pesquisa, para saber se o 
caracter digitado existe ou não na arvore, caso não 
exista ele será inserido na arvore 
a -apontador para arvore patrícia 
strcpy(vet1,""); limpa o lixo na memória das 
variaveis para digitação 
 
Durante a leitura do arquivo e inserção na 
arvore, a exibição do que foi inserido é ignorado 
e convertido em comentário. 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
 
È a partir deste ponto que o editor propriamente dito 
começa a funcionar: 
pesquisa na arvore e retorna o caracter digitado se ele 
existir na arvore ou insere na arvore se ele não existir 
 
TAB é a condição de parada, então compara o caracter 
digitado com \t (tab). 
Compara se o vet1 esta vazio e copia o que esta em 
DOC para o variável vet1, se vet1 não estiver vazio, 
então concatena o que foi digitado com o que ja esta no 
vetor. 
Exibe na tela o que foi digitado 
 
 
 
Uma vez saindo do programa, é possível salva-lo se 
desejar ou não. 
 
 
 
 
 
Opção que permite salvar o arquivo 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
 
Opção que permite sair sem 
salvar o arquivo 
 
 
 
 
 
 
 
 
 
 
 
Exibe na tela a tabela ASCII do que foi salvo 
Compacta usando o método de Huffman 
 
Libera o espaço na memória ocupado pelas variáveis alocadas 
 
 
 
ARVORE DE HUFMAN 
Uma das aplicações interessantes de árvores binárias é a compactação de arquivos usando os 
chamados códigos de Huffman. A codificação de Huffman é um método de compressão que usa 
as probabilidades de ocorrência dossímbolos no conjunto de dados a ser comprimido para 
determinar códigos de tamanho variável para cada símbolo. Ele foi desenvolvido 
em 1952 por David A. Huffman que era, na época, estudante de doutorado noMIT, e foi publicado 
no artigo "A Method for the Construction of Minimum-Redundancy Codes". Os códigos de 
Huffman são códigos binários (atribuídos, por exemplo, a caracteres em um texto) de comprimentos 
variados que são determinados a partir da frequência de uso de um determinado caracter. A idéia 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
central é associar números binários com menos bits aos caracteres mais usados num texto, 
possibilitando a sua compactação. 
A compressão de dados se caracteriza pela diminuição do espaço ocupado por dados em um 
determinado dispositivo. Essa intervenção é feita a partir de diversos algoritmos de compressão que 
visam reduzir assim a quantidade de Bytes para a representação de um dado podendo ser este uma 
imagem, um texto, ou um ficheiro. 
Essa compressão é destinada também para a eliminação de redundância de informações, 
baseando-se no conceito de que muitos dados possuem informações repetidas, e que essa repetição 
de informações pode ou deve ser eliminada de alguma forma. Além dessa compressão para a 
eliminação de informações, existem inúmeros outros motivos para a aplicação desse conceito entre 
estes podemos citar os mais comuns motivos ,como para a administração de um melhor espaço em 
dispositivos de armazenamento como discos rígidos , pendrives entre outros ou simplesmente para o 
maior ganho de tempo na transmissão de informações. 
 E analisando isto será abordado no perante trabalho o conceito de compressão de dados 
baseado na arvore de Huffman um método de compressão que usa as probabilidades da ocorrência 
(repetições) de símbolosno conjunto de dados a ser comprimido. 
O algoritmo de compactação usando os códigos de Huffman tem três fases: 
1. Cálculo da frequência de cada caracter no texto. 
2. Execução do algoritmo de Huffman para construção de uma árvore binária (árvore de 
Huffman). 
3. Codificação propriamente dita. 
O algoritmo de descompactação usando os códigos de Huffman têm duas fases: 
1. Leitura e reconstrução da árvore de Huffman. 
2. Decodificação propriamente dita. 
O conceito do algoritmo de Huffman se baseia na construção de uma árvore binária 
completa com n nós externos e n-1 nós internos, onde os nós considerados externos são 
classificados com as frequência. Ou seja, esse algoritmo se baseia na compressão por repetição de 
informações exemplo citado na seguinte tabela: 
D I F E O U A 
30 40 19 3 10 20 8 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
Nesse caso verificamos que as letras que possuem maior número de repetições {D, I} 
aparecem mais perto da raiz do que as menos redundantes {A, E}, a construção dessa arvore é feita 
de baixo para cima ou seja das folhas para a raiz, começando das letras que apareceram em menor 
numero de vezes ate se chegar a raiz da arvore com a letra que se repetiu o maior numero de vezes. 
Nessa arvore as letras serão representadas nas folhas e os seus vértices internos conterão o numero 
corresponde a frequências de repetições de seus descendentes. Para se encontrar o código 
pertencente a cada símbolo presente na arvore basta percorrer a arvore de Huffman começando da 
raiz ate a folha e assim concatenando cada valor encontrado para os nós da árvore bit(0) ao 
percorrer na subárvore da esquerda e bit (1) ao percorrer a subárvore da direita. 
A tabela de frequência de cada caracter. 
A tabela de frequência de cada caracter refere-se ao numero de vezes que cada caracter se repete 
no texto. O algoritmo de Huffman tem por objetivo a construção de uma árvore binária baseada 
na frequência do uso destas letras em um texto, de modo que as mais frequentemente usadas a 
apareçam mais perto do nó raiz. Esta arvore binária é construída de para cima, ou seja, das folhas 
para a raiz, começando a partir da letra com menos numero de repetição ate chegar a raiz. 
A principio, cada uma das letras forma uma arvore que é composta somente pelo nó raiz, cujo 
conteúdo é a frequência (f) com que esta ocorre no texto. Em seguida, são escolhidas as duas 
arvores com as menores frequências associadas e elas são unidas em uma só arvore cujo valor 
da raiz é a soma do valor destas duas. Este processo será repetido ate que exista somente uma 
única arvore. 
A codificação de Huffman pode ser abordada pelos seguintes passos: 
1. Organizam-se os símbolos em ordem decrescente de probabilidade; 
2. Agrupam-se os dois símbolos de menor probabilidade, dando origem a um novo símbolo 
cuja probabilidade será igual à soma das probabilidades dos símbolos que geraram. Uma 
"nova" fonte é criada e a esta fonte dá-se o nome de fonte reduzida. Essa nova fonte terá um 
elemento a menos em relação à fonte que a gerou. Novamente, organizam-se os símbolos 
em ordem decrescente de probabilidade de ocorrência; 
3. Continua-se executando o passo anterior, formando novas fontes reduzidas, até que só 
restem dois símbolos; 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
4. Com os dois símbolos restantes, faz-se uma atribuição aleatória de 1 para um dos símbolos e 
zero para o outro. Não há necessidade de nenhuma regra nessa atribuição, sendo a mesma 
feita a critério do codificador; 
5. Procede-se com o algoritmo, voltando dos símbolos finais até os símbolos da fonte, fazendo 
atribuição de zeros e uns às palavras do código; 
6. Ao chegar aos símbolos da fonte, a codificação está pronta. 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
CONCLUSÃO 
Concebido por Donald Morrison, PATRÍCIA é um algoritmo para realização de buscas em árvores 
com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um 
acrônimo de “Practical Algorithm To Retrieve Information Coded In Alphanumeric”, e o método é 
particularmente útil para tratamento de chaves de tamanho variável extremamente longas, tais como 
títulos e frases. O algoritmo para a arvore patrícia utilizado nesse trabalho foi baseado no código 
presente no livro “Projeto de Algoritmos com implementação em Pascal e C” de Nivio Ziviani [3], 
e para a compactação foi utilizado a codificação de Huffman. A codificação de Huffman é um 
método de compressão que usa as probabilidades de ocorrência dossímbolos no conjunto de dados a 
ser comprimido para determinar códigos de tamanho variável para cada símbolo. 
Com o desenvolvimento deste trabalho passamos a entender que embora atualmente, os meios de 
armazenamento e de transmissão de dados dos computadores contemporâneos seja bastante alto, 
ainda faz-se necessário o desenvolvimento de algoritmos de compressão cada vez mais eficientes, 
pois os softwares atuais são muito robustos, ocupando mais espaço em disco, e as informações por 
eles manipuladas demasiadamente volumosas, exigindo muito dos meio de armazenamento e de 
transmissão. Daí a importância da compactação de arquivos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Disciplina Integradora Prof. Wanderson Miranda 
Grupo: Grace Kelly, Bruna Cristine, Claudio Monteiro, DjullyFavia, Camila Mariana, Gloria Rayanne 
3º Período – Ciências da Computação 
 
REFERENCIAS BIBLIOGRAFICAS 
 
[1] http://pt.wikipedia.org/wiki/Arvore_Patrícia 
[2] http://en.wikipedia.org/wiki/Radix_tree 
[3] http://www2.dcc.ufmg.br/livros/algoritmos/cap5/codigo/c/5.16a5.21-patricia.c 
[4] http://www.vivaolinux.com.br/script/Compactando-arquivos-de-log-*.txt 
[5] http://www.inf.ufrgs.br/~cagmachado/INF01124/t3.htm 
[6] http://www.decom.ufop.br/guilherme/BCC203/1-2012/seminario_pesquisa-digital.pdf 
[7] http://marciobueno.com/arquivos/ensino/ed2/ED2_06_Trie_Patrícia.pdf 
[8] http://www.gpec.ucdb.br/pistori/disciplinas/ed/aulas_II/cd.htm - 
[9] http://www.ic.unicamp.br/~islene/mc202/lab4/lab4.html> Acessado: 14 de Maio 2015 
[10] http://www.ic.unicamp.br/~rtorres/mc326A_06s2/lab2/enunc.html> 
[11] http://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huffman> 
[12] http://pt.kioskea.net/contents/729-codificacao-de-huffman