Coder un algorithme de compression Huffman en PHP
Posté : 05 nov. 2015, 15:58
Bonjour,
avant toute chose je tiens à préciser que je ne m'attends pas à ce qu'on me crache des réponses toutes faites, je suis ici pour vraiment comprendre et surmonter mon problème.
Alors voilà, j'ai commencé le php il y a environ 2 mois, jusqu'à présent on avait des exercices assez simples à faire, pas de problème.
Mais maintenant, on doit rendre un algorithme de compression Huffman codé en php. Je sais ce qu'est Huffman, mais le problème c'est que je n'ai AUCUNE idée de comment commencer, je n'y arrive simplement pas.. Notre prof nous a mis 2 fichiers à disposition: un nommé "huffman-squelette.php" dans lequel il y a un include d'un 2ème fichier, nommé lui "entropie-include.php".
Je suis donc venu ici en espérant que qqn puisse me mettre sur la bonne voie, je voudrais vraiment commencer à coder mais après des heures passées devant ce squelette sans pouvoir avancer je perds un peu espoir...
Voici les 2 fichiers:
huffman-squelette.php
entropie-include.php
avant toute chose je tiens à préciser que je ne m'attends pas à ce qu'on me crache des réponses toutes faites, je suis ici pour vraiment comprendre et surmonter mon problème.
Alors voilà, j'ai commencé le php il y a environ 2 mois, jusqu'à présent on avait des exercices assez simples à faire, pas de problème.
Mais maintenant, on doit rendre un algorithme de compression Huffman codé en php. Je sais ce qu'est Huffman, mais le problème c'est que je n'ai AUCUNE idée de comment commencer, je n'y arrive simplement pas.. Notre prof nous a mis 2 fichiers à disposition: un nommé "huffman-squelette.php" dans lequel il y a un include d'un 2ème fichier, nommé lui "entropie-include.php".
Je suis donc venu ici en espérant que qqn puisse me mettre sur la bonne voie, je voudrais vraiment commencer à coder mais après des heures passées devant ce squelette sans pouvoir avancer je perds un peu espoir...
Voici les 2 fichiers:
huffman-squelette.php
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Compresseur Huffman</title>
</head>
<body>
<h1>Compresseur Huffman</h1>
<?php
require("entropie-include.php");
# décommenter pour passer en mode test (cf exercice 2)
# $test_mode = 1;
$texte = "";
if (isset($_POST["texte"])) {
$texte = $_POST["texte"];
list ($occurences, $total) = occurences($texte);
if (isset($test_mode)) {
# pour tester avec l'exercice du cours!
$texte = "correct";
$total = 64;
$occurences = array("e" => 15,
"r" => 12,
"c" => 11,
"o" => 10,
"t" => 9,
"l" => 4,
"m" => 2,
"k" => 1);
echo "<p>Mode de test!</p>";
}
?>
<p>La chaîne fait <?php echo $total; ?> symbole(s) dont
<?php echo count($occurences) ?> unique(s).
Les symboles se répartissent comme suit:
<ul>
<?php dump($occurences); ?>
</ul></p>
<?php
if ($total) {
$entropie = calculer_entropie($occurences, $total);
?>
<p>L'entropie calculée vaut: <?php echo $entropie; ?></p>
<?php
}
$code = huffman($occurences);
?>
<p>Voici la table de codage Huffman:
<ul>
<?php dump($code); ?>
</ul></p>
<p>Et voici votre texte compressé (sous forme de 0 et de 1 textuels):
<?php echo compress($texte, $code); ?>
</p>
<?php
}
?>
<h2>Texte à compresser</h2>
<form action="" method="post">
<p><textarea name="texte" rows="10" cols="60"><?php echo htmlentities($texte, ENT_XHTML, "ISO-8859-1"); ?></textarea>
<input type="submit" />
</p>
</form>
</body>
</html>
<?php
/**
* @param string à échapper
* @return string échappée
*/
function html_protect($s) {
return (ctype_graph($s)
? htmlentities($s, ENT_XHTML, "ISO-8859-1")
: "ASC " . join(", ", array_map("ord", str_split($s))));
}
/**
* @param array[string]string $a tableau associatif à afficher, suppose
* que $value est déjà échappé
*/
function dump ($a) {
foreach ($a as $key => $value) {
echo "<li>" . html_protect($key) . ": " . $value . "</li>";
}
}
/**
* @param array[string]integer tableau associatif symbole => occurence
* @return array[string]string tableau associatif symbole => code
*/
function huffman($o) {
global $test_mode;
$code = array();
# à compléter ...
return $code;
}
/**
* @param string $t texte dont les symboles sont à compresser
* @param array[string]string tableau associatif symbole => code
* @return string chaîne de bits en format texte
*/
function compress($t, $c) {
$s = "";
# à compléter
return $s;
}
?>entropie-include.php
<?php
/**
* @param string $t source dont les symboles sont à compter
* @return array(array[string]integer tableau associatif symbole => occurences,
* integer nombre d'occurences totales) tableau
*
* inconvénients de cette implémentation:
* - calcul de strlen($t) *et* de $total
* - mise en mémoire du tampon entier sous forme de tableau,
* ce qui gaspille de la mémoire
* -> une meilleure implémentation serait possible si le programme
* principal nous appelait ligne par ligne pour compléter
* un tableau d'occurence, par exemple! ou si l'on consommait
* dans la fonction occurences() une entrée fichier, par exemple.
*/
function occurences($t) {
return array(array_count_values(split_str($t), strlen($t)));
}
/* variante plus manuelle */
function occurences_more_manual($t) {
$a = array();
# définition d'une fonction anonyme qui a besoin d'utiliser
# une référence au tableau local $a à la fonction occurences
# pour pouvoir le modifier
$callback = function ($val, $index) use (&$a) {
if (!array_key_exists($val, $a)) {
$a[$val] = 0;
}
$a[$val]++;
};
# appliquer la fonction anonyme à l'ensemble du tableau
if (strlen($t)) {
array_walk(str_split($t), $callback);
}
return array($a, strlen($t));
}
/**
* @param array[string]integer $o tableau associatif symbole => occurences
* @param integer $t nombre total d'occurences
* @return float valeur de l'entropie sur $o
*
* alternative: array_map() et array_sum() pour éviter la boucle manuelle
*/
function calculer_entropie($o, $t) {
$H = 0;
foreach ($o as $symbol => $count) { /* ou sans le $symbol => */
$Pi = $count/$t;
$Hi = -log($Pi)/log(2); /* ou voir 2e argument de la fonction log() */
$H += $Pi * $Hi;
}
return $H;
}
?>
