145 lines
6 KiB
HTML
145 lines
6 KiB
HTML
|
<?xml version="1.0" encoding="iso-8859-1"?>
|
|||
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
|||
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|||
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr">
|
|||
|
|
<head xml:lang="fr" lang="fr">
|
|||
|
|
<title>TP - Documents et compression - M2-SRI</title>
|
|||
|
|
<meta content="text/html; charset=iso-8859-1" />
|
|||
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
|
|||
|
|
<meta name="description" content="Sujet de la premi<EFBFBD>re s<EFBFBD>ance de travaux
|
|||
|
|
pratiques du cours de «formats de documents et compression» du
|
|||
|
|
master 2 II - SRI" />
|
|||
|
|
<meta name="Author" content="Jean-Baptiste Yun<75>s"/>
|
|||
|
|
<meta name="keywords" content="TP,compression" />
|
|||
|
|
<link href="../cours.css" rel="stylesheet" type="text/css" />
|
|||
|
|
</head>
|
|||
|
|
|
|||
|
|
<body>
|
|||
|
|
|
|||
|
|
<div class="titre">
|
|||
|
|
<h1>Formats de documents et compression - TP 1</h1>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="tdm">
|
|||
|
|
<h2>Sujet</h2>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<p>On se propose de r<>aliser, par <20>tapes successives, un logiciel de
|
|||
|
|
(d<>)compression bas<61> sur la technique RLE et le code de Golomb.</p>
|
|||
|
|
|
|||
|
|
<h2>Le RLE</h2>
|
|||
|
|
|
|||
|
|
<p>Le principe du codage RLE (Run Length Encoding) est d'obtenir <20> partir
|
|||
|
|
d'une suite de nombre suppos<6F>e contenir des r<>p<EFBFBD>titions cons<6E>cutives de m<>mes
|
|||
|
|
valeurs, une suite contenant:</p>
|
|||
|
|
<ul class="disc">
|
|||
|
|
<li>pour toute r<>p<EFBFBD>tition suffisamment longue, la longueur de la suite et
|
|||
|
|
la valeur r<>p<EFBFBD>t<EFBFBD>e,</li>
|
|||
|
|
<li>pour toute r<>p<EFBFBD>tition trop courte, la suite de valeurs sans
|
|||
|
|
modification.</li>
|
|||
|
|
</ul>
|
|||
|
|
<p>Un tel codage n<>cessite en pratique d'ins<6E>rer dans la suite construite des
|
|||
|
|
marqueurs permettant de r<>aliser le d<>codage.</p>
|
|||
|
|
|
|||
|
|
<p>Il est facile d'observer que, par une telle m<>thode, certaines suites sont
|
|||
|
|
«compress<EFBFBD>es»; la longueur de la suite apr<70>s codage est plus
|
|||
|
|
petite que la longueur de la suite originale.</p>
|
|||
|
|
|
|||
|
|
<p class="exemple">La suite <code>aaaaabcbaaaaaabbbbbb</code> (de longueur 20)
|
|||
|
|
pourra<EFBFBD>t <20>tre
|
|||
|
|
encod<EFBFBD>e de fa<66>on <20> produire la suite <code>[RLE]5abcb[RLE]6a[RLE]6b</code> (de
|
|||
|
|
longueur 12).</p>
|
|||
|
|
|
|||
|
|
<div class="todo">
|
|||
|
|
<p><strong>1.</strong> Il est demand<6E> de r<>aliser dans un langage de
|
|||
|
|
programmation de votre choix un
|
|||
|
|
programme d'encodage et de d<>codage RLE (bas<61> sur le principe pr<70>c<EFBFBD>dent). Ce
|
|||
|
|
programme devra permettre d'encoder tout fichier donn<6E> en entr<74>e et produire
|
|||
|
|
en sortie un fichier dont le nom sera <20>tendu en <code>.rl1</code>. Ce
|
|||
|
|
programme devra en outre produire en sortie le taux de compression obtenu.</p>
|
|||
|
|
|
|||
|
|
<p>Ce programme pourra <20>tre param<61>tr<74> de fa<66>on <20> permettre <20> l'utilisateur de
|
|||
|
|
choisir ce qu'il consid<69>re comme <20>tant un caract<63>re de la suite.</p>
|
|||
|
|
|
|||
|
|
<p>On testera ce programme sur une vari<72>t<EFBFBD> de fichiers communs: texte
|
|||
|
|
fran<EFBFBD>ais, binaire, bitmap d'image, etc.</p>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<p>De nombreuses variantes de ce principe sont utilis<69>es. Par exemple, si la
|
|||
|
|
suite consid<69>r<EFBFBD>e est une suite de bits, on peut s'int<6E>resser aux suites de 0
|
|||
|
|
cons<EFBFBD>cutifs situ<74>s entre deux 1.</p>
|
|||
|
|
|
|||
|
|
<p class="exemple">La suite <code>00000100110000000101011</code> peut <20>tre
|
|||
|
|
repr<EFBFBD>sent<EFBFBD>e par la suite <code>52071100</code>.</p>
|
|||
|
|
|
|||
|
|
<div class="todo">
|
|||
|
|
<p><strong>2.</strong> <20>crire un programme (dans le langage de votre choix)
|
|||
|
|
permettant de coder et d<>coder tout fichier consid<69>r<EFBFBD> comme une suite de
|
|||
|
|
bits. Le fichier r<>sultat sera nomm<6D> en utilisant l'extension
|
|||
|
|
<code>.rl2</code>.</p>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="todo">
|
|||
|
|
<p><strong>3.</strong> On <20>tudiera les relations entre cet encodage et le pr<70>c<EFBFBD>dent. Du point de
|
|||
|
|
vue de l'encodage lui-m<>me, de leurs performances relatives, etc.</p>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<div class="todo">
|
|||
|
|
<p><strong>4.</strong> On recherchera la sp<73>cification de formats courants
|
|||
|
|
utilisant le codage RLE. On comparera les techniques employ<6F>es dans ces divers
|
|||
|
|
formats avec celles r<>alis<69>es dans ce TP.</p>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<h2>Le code de Golomb</h2>
|
|||
|
|
<p>En ce qui concerne le RLE du second type et pr<70>c<EFBFBD>demment d<>crit le
|
|||
|
|
probl<EFBFBD>me principal est de trouver un codage ad<61>quat pour la suite des nombres
|
|||
|
|
produits; <em>i.e.</em> comment coder la suite <code>52071100</code> ? Le code
|
|||
|
|
de Golomb permet de construire un codage de longueur variable permettant
|
|||
|
|
d'obtenir une compression raisonnablement efficace.</p>
|
|||
|
|
|
|||
|
|
<h3>Code de Golomb<sub>d</sub></h3>
|
|||
|
|
<p>Pour l'entier <var>n</var>, Golomb<sub>d</sub>(<var>n</var>) est construit
|
|||
|
|
par concat<61>nation du codage unaire du quotient de <var>n</var>/d et du codage
|
|||
|
|
binaire tronqu<71> du reste de <var>n</var>/d.</p>
|
|||
|
|
|
|||
|
|
<p>Le codage unaire d'un entier <var>i</var> est une suite de <var>i</var>
|
|||
|
|
<code>1</code> suivie d'un <code>0</code>. Le nombre <code>5</code> se code
|
|||
|
|
donc <code>111110</code>.</p>
|
|||
|
|
|
|||
|
|
<p>Le codage binaire tronqu<71> de l'entier <var>i</var>,
|
|||
|
|
CBT<sub>d</sub>(<var>i</var>) est obtenu de la fa<66>on suivante:</p>
|
|||
|
|
<ul class="disc">
|
|||
|
|
<li>On appelle <var>c</var> la partie enti<74>re sup<75>rieure du logarithme en
|
|||
|
|
base 2 de d, <em>i.e.</em> le nombre de bits utiles pour <20>crire d en binaire
|
|||
|
|
(par exemple pour 5, <var>c</var>=3).</li>
|
|||
|
|
<li>si <var>i</var><2<sup><var>c</var></sup>-d, <var>i</var> sera cod<6F> en
|
|||
|
|
employant <var>c-1</var> bits.</li>
|
|||
|
|
<li>sinon <var>i</var> sera cod<6F> par les <var>c</var> derniers bits de
|
|||
|
|
2<sup><var>c</var></sup>-(d-<var>i</var>).</li>
|
|||
|
|
</ul>
|
|||
|
|
<p>Ainsi pour d=5, le codage du nombre 23 sera <code>11110110</code>, car
|
|||
|
|
<code>11110</code> est le codage unaire de 4 (23/5=4) et <code>110</code> le
|
|||
|
|
codage sur 3 bits de 6 (on cherche CBT<sub>5</sub>(3), on sait que
|
|||
|
|
2<sup>3</sup>-(5-3)=6).</p>
|
|||
|
|
|
|||
|
|
<p>Comment d<>terminer une valeur ad<61>quate pour d ? Il
|
|||
|
|
suffit de prendre la m<>diane de la suite <20> coder.</p>
|
|||
|
|
|
|||
|
|
<div class="todo">
|
|||
|
|
<p><strong>5 (difficile).</strong> <20>crire un programme permettant de coder et
|
|||
|
|
d<EFBFBD>coder tout fichier consid<69>r<EFBFBD> comme une suite de bits en utilisant le code de
|
|||
|
|
Golomb.</p>
|
|||
|
|
</div>
|
|||
|
|
<hr />
|
|||
|
|
<div class="todo">
|
|||
|
|
<p>Le TP devra <20>tre r<>dig<69> (sous la forme de documents HTML) et rendu avec les
|
|||
|
|
codes sources des programmes; ce au plus une semaine apr<70>s la s<>ance.</p>
|
|||
|
|
</div>
|
|||
|
|
|
|||
|
|
<p><a class="fin" href="http://validator.w3.org/check/referer"><img
|
|||
|
|
src="/~yunes/graphics/vxhtml10" alt="Valid XHTML 1.0!"
|
|||
|
|
/></a><a class="fin" href="http://jigsaw.w3.org/css-validator/"><img
|
|||
|
|
src="/~yunes/graphics/vcss.gif" alt="Valid CSS!" /></a></p>
|
|||
|
|
</body>
|
|||
|
|
</html>
|