Source Latex
\documentclass[12pt]{article}
%\usepackage{french}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage{a4wide}
\usepackage{graphicx}
\usepackage{epsf}
\usepackage{pst-all}
\usepackage{ifthen}
\usepackage{calc}
\usepackage{pst-all}
\usepackage{hyperref}
\hypersetup{
pdfauthor={Yoann Morel},
pdfsubject={Matlab},
pdftitle={Initiation et travaux pratiques en Matlab},
pdfkeywords={Matlab, simulation, programmation,
compression de données, traitement données, type de données}
}
\hypersetup{
colorlinks = true,
linkcolor = red,
anchorcolor = red,
citecolor = blue,
filecolor = red,
urlcolor = red
}
\voffset=-1cm
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\bge}{\begin{equation}}\nwc{\ene}{\end{equation}}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}
\nwc{\ct}{\centerline}
\nwc{\V}[1]{\overrightarrow{#1}}
\nwc{\la}{\left\{}\nwc{\ra}{\right\}}
\nwc{\lp}{\left(}\nwc{\rp}{\right)}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}
\nwc{\bgsk}{\bigskip}
\nwc{\vsp}{\vspace{0.1cm}}
\nwc{\vspd}{\vspace{0.2cm}}
\nwc{\vspt}{\vspace{0.3cm}}
\nwc{\vspq}{\vspace{0.4cm}}
\newcounter{ntp}%[section]
\setcounter{ntp}{1}
\newenvironment{TP}[1]{%
\setcounter{equation}{0}\setcounter{subsection}{0}
\section*{ \underline{TP \arabic{ntp} :} #1}
\addcontentsline{toc}{section}{\underline{TP \arabic{ntp} :}\ #1}
\stepcounter{ntp}}{}
\nwc{\bgTP}{\begin{TP}}\nwc{\enTP}{\end{TP}}
\def\N{{\rm I\kern-.1567em N}} % Doppel-N
\def\No{\N_0} % Doppel-N unten 0
\def\R{{\rm I\kern-.1567em R}} % Doppel R
\def\C{{\rm C\kern-4.7pt % Doppel C
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Z{{\sf Z\kern-4.5pt Z}} % Doppel Z
% grec et autres
\nwc{\lbd}{\lambda}
\nwc{\vphi}{\varphi}
\nwc{\ga}{\gamma}
\def\epsi{\varepsilon}
\def\tht{\theta}
\nwc{\tm}{\times}
\nwc{\ul}{\underline}
\nwc{\scp}[1]{\scriptsize{#1}}
\author{Y. Morel}
\date{}
\headheight=0cm
\textheight=26cm
\topmargin=-1.8cm
\footskip=.8cm
\textwidth=17.6cm
\oddsidemargin=-1.cm
%\parindent=0.2cm
\usepackage{fancyhdr}
\newenvironment{centerpage}{\vspace*{\fill}}{
\protect\vspace*{\fill}}
\begin{document}
\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}
\lfoot{Y. Morel - \url{https://xymaths.fr/Matlab/}}
\rfoot{Compression de données - \thepage/\pageref{LastPage}}
\cfoot{}
\vspace*{1cm}
\nwc{\TPtop}{}
\newlength{\lgr}
\newlength{\TPtopLarge}
\newlength{\EXX}
\newlength{\Tlgr}
\newlength{\TopHeight}
\newlength{\TopTitleHeight}
\newcommand{\ChapTitle}[3]{
\renewcommand{\TPtop}{{\LARGE\bf #1} {\Huge\bf#2}}
\settowidth{\lgr}{\LARGE\bf #1}
\settowidth{\TPtopLarge}{\TPtop}
\settoheight{\EXX}{\LARGE X}
\settowidth{\Tlgr}{\LARGE T}
\setlength{\Tlgr}{0.5\Tlgr}
\settototalheight{\TopHeight}{\fbox{\bgmp{\linewidth}\begin{center}{\LARGE\bf#3}\end{center}\enmp}}
%%
\noindent
\bgmp{\linewidth}
\psline(\lgr,\EXX)(1.1\lgr,\EXX)
\psline(\TPtopLarge,\EXX)(\linewidth,\EXX)%
(\linewidth,-1.\TopHeight)(\Tlgr,-1.\TopHeight)%
(\Tlgr,-0.05)
\TPtop
\vspace{-0.5\EXX}
\begin{center}
{\LARGE\bf#3}
\end{center}
\enmp%
\vspace{0.5cm}
}
\setcounter{ntp}{6}
\ChapTitle{TP}{\thentp}{Compression de données}
\addcontentsline{toc}{section}{\ul{TP \arabic{ntp} :}\ Compression de données}
Un message, ou texte, numérique est une suite de nombres binaires
(de 0 et 1). Cette suite de nombres provient, par exemple, du
codage binaire d'un texte alphanumérique (en français par exemple...).
Chaque caractère du texte, les lettres de l'alphabet (y compris les
caractères spéciaux : espaces, virgules,...) sont remplacés par un
nombre à $b$ chiffres constitué de 0 et 1.
En général, on utilise un codage de chaque lettre sur 8 bits,
i.e. une séquence de 8 chiffres binaires. On peut ainsi coder
différemment $2^8=256$ caractères : c'est le code ASCII.
Ainsi un texte alphanumérique composé de $N$ caractères est
représenté par $N\times 8$ bits, soit $N$ octets.
Le but de ce TP est de mettre en \oe uvre une méthode de compression
de données, i.e. une méthode de réduction du nombre d'octets utilisés
pour coder un message.
Il arrive fréquement qu'un texte donné présente des répétitions :
des caractères utilisés bien sûr (seulement 26 lettres composent
notre alphabet...), mais aussi répétitions de mots complets, voir
séquences de mots...
C'est cette observation qui est à la base des méthodes de
compression : au lieu de coder un message par une suite de nombres
binaires directement issue du codage de chaque caractère successif
constituant le message, on code le message suivant deux listes :
la liste des mots utilisés (bien sûr sans répétition cette fois),
ou dictionnaire, et la liste des positions de chaque mots du
dictionnaire dans le message original.
Sous réserve d'un nombre assez important de répétitions des mots du
dictionnaire utilisé, la taille de ces deux listes peut-être bien
moindre que celle du codage direct du message.
\bgsk
\bgit
\item[1-] Ecrire une fonction Matlab générant un message de $N$
mots codés sur 8 bits (soit un message de $8N$ bits, ou $N$ octets,
au total), n'utilisant (ou répétant) que $n$ mots d'un
dictionnaire.
On pourra commencer par créer le dictionnaire comme étant une
matrice (ou tableau) à $n$ lignes (une pour chaque mot) et $8$
colonnes; chaque ligne de ce tableau étant une suite aléatoire de 8
chiffres binaires.
Ensuite, le message peut se construire en choisissant aléatoirement
des mots dans ce dictionnaire, que l'on concaténera.
\vspd
Ce message étant construit, on considère par la suite que ce
dictionnaire est inconnu; seul le message de $N$ mots est donné.
\bgsk
\item[2-] Ecrire une fonction Matlab {\it Compress} qui permet de
compresser ce message.
Le principe de cette fonction est le suivant.
On part du premier mot du message (premier octet), on l'ajoute à
au dictionnaire (liste des mots du message, sans répétition),
on recherche dans le message les autres occurences de ce mot, et
on enregistre dans un tableau la position dans ce message de ces
occurences.
On réitère ensuite le procédé à partir du mot suivant dans le message
qui n'est pas encore dans le dictionnaire.
On crée ainsi deux tableaux : le premier est le dictionnaire, le
deuxième contient la position de chacun des mots du dictionnaire
dans le message
\vspd
On pourra construire une fonction intermédiaire retournant le
$n^{\mbox{\scriptsize{ème}}}$ mot du message.
\bgsk
\item[3-] Ecrire une fonction Matlab {\it DeCompress} permettant,
à partir des deux tableaux précédants de reconstruire le message,
et s'assurer ainsi que l'on a bien un codage équivalent du message
original.
\bgsk
\item[4-] Calculer le taux de compression obtenu, i.e. le ratio
taille des deux tableaux "compressés" sur taille du message
initial.
\enit
\label{LastPage}
\end{document}
Télécharger le fichier source 
