\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}
\input{epsf}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 818 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 5710 -- Estruturas de Dados}
\end{center}

\begin{center}
{\bf Primeiro semestre de 1999}
\end{center}

\begin{center}
{\large  Exercício-Programa 4 -- Entrega: {\bf 24 de junho de 1999}}

\vspace{0.3cm}
Códigos de Huffman 
\end{center}


Uma aplica\c c\~ao interessante de \'arvores bin\'arias em codifica\c c\~ao
de dados a serem transmitidos e compacta\c c\~ao de arquivos s\~ao os 
c\'odigos de Huffman. Para enviar uma mensagem atrav\'es de um cabo de 
transmiss\~ao os caracteres da mensagem s\~ao enviados um a um 
modificados atrav\'es de alguma tabela de codifica\c c\~ao. Em geral,
esse c\'odigo \'e um n\'umero bin\'ario. Como a velocidade de transmiss\~ao
depende do comprimento deste c\'odigo, \'e interessante tornar a mensagem
o mais curta poss\'\i vel. Um algoritmo de determina\c c\~ao de c\'odigos
bin\'arios para caracteres baseado na freq\"u\^encia de uso destes
caracteres foi sugerida por Huffman. A id\'eia \'e associar n\'umeros 
bin\'arios com menos bits aos caracteres mais usados nos textos. Se voc\^e
quiser saber mais sobre c\'odigos de Huffman, consulte o \'otimo livro
\cite{Leiserson}. 

Por exemplo, suponha que a mensagem seja composta pelos caracteres 
A, B, C, D, E e R e que o n\'umero de vezes que estas letras 
s\~ao usadas na mensagem seja resp. 22, 8, 10, 12, 18 e 7. A id\'eia  
\'e construir uma \'arvore bin\'aria baseada na freq\"u\^encia de
uso destas letras de tal forma que as folhas correspondam \`as letras; e 
as letras mais freq\"uentemente usadas (como A e E) est\~ao mais pr\'oximas
da raiz que as menos usadas (como B e R). Para isso, construiremos a 
\'arvore bin\'aria a partir das folhas, colocando nos n\'os internos
um n\'umero correspondente \`a soma da freq\"u\^encia dos seus descendentes. 

A seguir, mostramos a constru\c c\~ao da \'arvore bin\'aria para o 
exemplo mostrado acima. Em cada passo do algoritmo teremos uma cole\c c\~ao
de \'arvores bin\'arias. \`A raiz de cada uma dessas \'arvores est\'a
associado um n\'umero (freq\"u\^encia de seus descendentes). Escolhemos 
ent\~ao, as duas \'arvores dessa cole\c c\~ao com menor freq\"u\^encia e
as transformamos numa s\'o, ligando-as a uma nova raiz cujo valor ser\'a
dado pela soma dos valores das duas sub\'arvores. Observe o exemplo
abaixo: 
$$ \epsffile{ep4f1.eps} $$
Selecionamos as duas \'arvores de menor valor (8 e 7) e as juntamos em 
uma \'arvore s\'o. 
$$ \epsffile{ep4f2.eps} $$
Repetindo o processo, escolhemos as \'arvores com raiz (10 e 12). 
$$ \epsffile{ep4f3.eps} $$
Agora escolhemos (18 e 15), 
$$ \epsffile{ep4f4.eps} $$
Depois (22 e 22), 
$$ \epsffile{ep4f5.eps} $$
E finalmente (33 e 44). 
$$ \epsffile{ep4f6.eps} $$
Associamos, ent\~ao, \`a \'arvore final assim constru\'\i da 0 \`as 
arestas que ligam o v\'ertice com seu filho esquerdo e 1 \`as arestas
que ligam o v\'ertice com seu filho direito. O c\'odigo correspondente
a cada letra ser\'a ent\~ao formado pelo n\'umero bin\'ario associado 
ao caminho da raiz at\'e a folha correspondente. No caso acima, temos
a seguinte tabela: 
\[
\begin{tabular}{ll}
A & 10 \\
B & 011 \\
C & 110 \\
D & 111 \\
E & 00 \\
R & 010 
\end{tabular} \]
No exemplo acima pudemos diminuir o tamanho da codifica\c c\~ao de todos 
os caracteres, mas dependendo da \'arvore isso nem sempre acontece. 

Utilizando a tabela acima, a mensagem ABRACADABRA ser\'a codificada pela
seq\"u\^encia de bits 1001101010110101111001101010. Assim, pudemos 
compactar a mensagem original de 88 bits para 28 bits. 

O objetivo deste exerc\'\i cio--programa \'e construir um compactador
de arquivos baseado na estrat\'egia mostrada acima. Duas estrat\'egias 
poss\'\i veis de compacta\c c\~ao s\~ao as seguintes: 
\begin{itemize}
\item \'arvore fixa.\\
A id\'eia \'e inicialmente ler diversos tipos de textos (programas, 
arquivos de dados, textos escritos), contando o n\'umero de ocorr\^encias
de cada caractere. A partir de ent\~ao seu programa montar\'a a \'arvore
como descrito neste enunciado, e usar\'a a mesma \'arvore para compactar
e descompactar os textos. 
\item \'arvore vari\'avel. \\
Para cada texto lido constr\'oi-se a ``\'arvore \'otima'' para aquele texto
e compacta o texto usando essa \'arvore. A desvantagem nesse caso \'e que
devemos guardar essa \'arvore junto com o arquivo compactado para 
descompactar futuramente. 
\end{itemize}
Compare essas duas estrat\'egias (em porcentagem de compacta\c c\~ao, 
tempo de processamento, etc.) e compare tamb\'em seu programa com 
pacotes comerciais de compacta\c c\~ao de textos. 

Nesse exerc\'\i cio--programa, al\'em da listagem e do disquete, voc\^e
deve entregar um pequeno relat\'orio com seus testes comparando as 
diversas estrat\'egias (pode implementar outras!) e os pacotes comerciais. 

\begin{thebibliography}{9}

\bibitem{Leiserson} T. H. Cormen, C. E. Leiserson, R. L. Rivest, 
{\em Introduction to Algorithms}
(1990), McGraw Hill. 

\bibitem{huffman} D. A. Huffman, ``A Method for the Construction of Minimum 
Redundancy Codes'', {\em Proceedings IRE} 10, 40, 1098 -- 1101 (1952). 

\bibitem{lelewer} D. A. Lelewer, D. S. Hirschberg, ``Data Compression'', {\em ACM} 19,
3, 261--296 (1987). 
\end{thebibliography}
\end{document}