\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{multicol}
\usepackage{textcomp}
\usepackage{pstricks,pst-plot,pst-text,pst-tree,pst-eps,pst-fill,pst-node,pst-math,pst-coil,pstricks-add,pst-xkey}

\newtheorem{proposition}[theorem]{Proposition}

\begin{document}

\title{Codage binaire et compression}
\subtitle{Journée des mathématiques}
\author{Lycée Janot}
\date{}

\begin{frame}
  \titlepage
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%CODAGE BINAIRE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}{Codage binaire : le principe}

\begin{center}
\Large
Caractère
\\\pause
$\downarrow$% {Table ascii}
\\
Nombre décimal entre 0 et 127
\\\pause 
$\downarrow$% {Table ascii}
\\
Nombre binaire entre 0 et 1111111\\[20pt]\pause

Caractère $\Leftrightarrow$ 7 bits $\leftrightsquigarrow$ 1 octet\\
\end{center}
\end{frame}



\begin{frame}{Codage binaire : exemple }

\begin{center}
{\scriptsize
\begin{tabular}{|*{7}{c|}}
 \hline
 B&i&n&a&i&r&e\\  \hline\pause
 66&105&110&97&105&114&101\\  \hline \pause
 01000010&01101001&01101110&01100001&01101001&01110010&01100101 \\ \hline
\end{tabular}
}
\end{center}
\pause
\Large
donc :
\begin{center}Binaire $\Leftrightarrow$ {\scriptsize01000010011010010110111001100001011010010111001001100101}\end{center}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%COMPRESSION PAR REPETITION RLE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}{Compression RLE : le principe}
\Large
\begin{itemize}
\item run-length encoding. \pause
\item Toute suite de bits ou de caractères identiques est remplacée par un couple (nombre d'occurrences ; bit ou caractère répété). \pause 
\item Le résultat comporte en général moins de caractères, bien que ce ne soit pas une obligation.\pause
        \begin{itemize}
	\item AAAAAAAAZZEEEEEER donne : 8A2Z6E1R, ce qui est beaucoup plus court. \pause
	\item WBWBWBWBWB donne : 1W1B1W1B1W1B1W1B1W1B ce qui est deux fois plus long.
	\end{itemize}
\end{itemize}

\end{frame}


\begin{frame}{Compression RLE : exemple }
\Large
\begin{center}
Binaire 
\\\pause
$\downarrow$% codage binaire
\\
{\scriptsize01000010011010010110111001100001011010010111001001100101}
\\\pause
$\downarrow$% RLE
\\
10-11-40-11-20-21-10-11-20-11-10-20-10-31-20-21-40-11-10-21-10-11-20-31-20-21-20-11-10-11
\\\pause
$\downarrow$% Table ascii
\\

\end{center}


\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%COMPRESSION PAR Huffman
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Compression Huffman : le principe}
\begin{itemize}
\item Idée : coder ce qui est fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement.\pause
\item Étapes : 
      \begin{itemize}
      \item estimation des fréquences d'apparition des charactères
      \item création d'un arbre
      \item encodage du texte selon l'arbre
      \end{itemize}\pause
\item Inconvenients :\\ lire tout le fichier avant de comprimer.\\ 
      Pour décomprimer il faut connaître les codes et donc la table, qui est ajoutée devant le fichier, aussi bien pour transmettre que stocker, ce qui diminue la compression, surtout pour les petits fichiers.\\
      Plusieurs variantes de Huffman existent pour supprimer ces defauts.
\end{itemize}

\end{frame}

\begin{frame}{Exemple}
Supposons que la répartition des lettres d'un texte par nombres d'occurrences décroissants soit :
\begin{center}
\begin{tabular}{|*{7}{c|}}
 \hline
 e&a&d&c&b&f&g\\ \hline
 100&70&35&30&25&10&5\\ \hline
\end{tabular}
\end{center}
\pause
On remplace les deux lettres les moins fréquentes de la liste triée par une lettre (fictive) f+g  de nombre d'occurence 10+5=15 que l'on insère, en respectant l'ordre dans la liste triée. On obtient :
\begin{center}
\begin{tabular}{|*{6}{c|}}
 \hline
 e&a&d&c&b&f+g\\ \hline
 100&70&35&30&25&15\\ \hline
\end{tabular}
\end{center}
$$\pstree{\TC}{\Tcircle{f} \Tcircle{g}}$$
\end{frame}


\begin{frame}{Exemple}
%On recommence en remplacant $b : 25$ et $f+g : 15$ par $b+f+g$ de poids 40.\pause
\begin{center}
\begin{tabular}{|*{6}{c|}}
 \hline
 e&a&d&c&b&f+g\\ \hline
 100&70&35&30&25&15\\ \hline
\end{tabular}
\end{center}\pause
$$\pstree{\TC}{
  \pstree{\Tcircle{b}}{}
  \pstree{\TC}{\Tcircle{f} \Tcircle{g}}
                   }$$
\pause

\begin{center}
\begin{tabular}{|*{5}{c|}}
 \hline
 e&a&b+f+g&d&c\\ \hline
 100&70&40&35&30\\ \hline
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Exemple}
%On recommence en remplacant $c : 30$ et $d : 35$ par $d+c$ de poids 65.\pause
\begin{center}
\begin{tabular}{|*{5}{c|}}
 \hline
 e&a&b+f+g&d&c\\ \hline
 100&70&40&35&30\\ \hline
\end{tabular}
\end{center}
\pause
$$\pstree{\TC}{\Tcircle{d} \Tcircle{c}}$$
\pause
\begin{center}
\begin{tabular}{|*{4}{c|}}
 \hline
 e&a&d+c&b+f+g\\ \hline
 100&70&65&40\\ \hline
\end{tabular}
\end{center}
\end{frame}


\begin{frame}{Exemple}
%On assemble $b+f+g : 40$ et $d+c : 65$.\pause
\begin{center}
\begin{tabular}{|*{4}{c|}}
 \hline
 e&a&d+c&b+f+g\\ \hline
 100&70&65&40\\ \hline
\end{tabular}
\end{center}
\pause
$$\pstree[nodesep=5pt,levelsep=1cm]{\TC}{
   \pstree{\TC}{\Tcircle{d} \Tcircle{c}}
   \pstree{\TC}{\pstree{\Tcircle{b}}{}
		\pstree{\TC}{\Tcircle{f} \Tcircle{g}}}
                }$$
\pause
\begin{center}
\begin{tabular}{|*{3}{c|}}
 \hline
 d+c+b+f+g&e&a\\ \hline
 105&100&70\\ \hline
\end{tabular}
\end{center}
\end{frame}



\begin{frame}{Exemple}
%On assemble alors a avec e, puis a + e avec d + c + b + f + g, on obtient enfin
\begin{center}
\begin{tabular}{|*{3}{c|}}
 \hline
 d+c+b+f+g&e&a\\ \hline
 105&100&70\\ \hline
\end{tabular}
\end{center}
\pause
$$\pstree[nodesep=5pt,levelsep=1cm]{\TC}{
     \pstree{\TC}{\Tcircle{e} \Tcircle{a}}
     \pstree{\TC}{\pstree{\TC}{\Tcircle{d} \Tcircle{c}}
		  \pstree{\TC}{\pstree{\Tcircle{b}}{}
		  \pstree{\TC}{\Tcircle{f} \Tcircle{g}}}
		  }
		  }$$
\pause
\begin{center}
\begin{tabular}{|*{7}{c|}}
 \hline
 e&a&d&c&b&f&g\\ \hline 
 00&01&100&101&110&1110&1111\\ \hline
\end{tabular}
\end{center}
\end{frame}




\begin{frame}{Exemple}
On obtient :
\begin{center}
\begin{tabular}{|*{7}{c|}}
 \hline
 e&a&d&c&b&f&g\\ \hline 
 100&70&35&30&25&10&5\\ \hline
 00&01&100&101&110&1110&1111\\ \hline
\end{tabular}\\ \pause
La longueur du texte vaut 
$$(70 + 100) \times 2 + (25 + 30 + 35) \times 3 + (10 + 5) \times 4 = 340 + 270 + 60 = 670 \text{bits}$$ \pause
au lieu de 
$$(100+70+35+30+25+10+5)\times8=2200 \text{bits}$$
\end{center}
\end{frame} 
 

\end{document}
