Php5 classe arbre inversé (huffman) compression decompression

Soyez le premier à donner votre avis sur cette source.

Vue 17 953 fois - Téléchargée 398 fois

Description

Ce script de compression-décompression créé une arborescence (treeItems)en partant des feuilles et non de la racine:
Il s'agit d'une adaptation simplifiée de l'algo de compression d'huffman.

2 classes treeItems (structure) et huffmanTree(qui embarque les methodes codecs).
3 fonctions de conversion indépendantes.

Utilisation des iterateurs recursifs sur ces classes.
Mais comme je ne maîtrise mal ces bestioles, je ne garantie pas la perfection, juste que cela semble fonctionner.

Voilà prêt à essayer.
exemple:
1: iiiiiiihhh=>gros taux de compression : le chemin étant très court pour chaque octets grâce à la frequence du caracteres i et h => taux:85 à 90%
2: Portez ce vieux whisky au juge blond qui fume : beaucoup de caractères différents sont présents: la conversion doit être autour de 40à45%(faible)

Source / Exemple :


<html>
<head></head>
<body>
<form name="F1" method="POST" action="">
  <textarea name="phrase" rows="10" cols="50" style="font-size:11px">
  </textarea>
  <input type="Submit" value="compresser" name="Valid"/>
</form>

<?php
/**
Convertit une chaine binaire en entier 
avec la taille passée en paramètre optionnel
defaut 16 bits (entiers courts non signés)

  • /
function binStrToInt($sbin,$intSize=16) { $enc=0; for ( $i=0 ; $i < $intSize ; $i++ ) { if ( ( $intSize-$i ) != 1 ) $enc += pow(2*((int)$sbin{$i}+0),($intSize-$i-1)); else $enc += $sbin{$i}; } return $enc; } /** Convertit un entier en chaine binaire avec la taille passée en paramètre optionnel defaut 16 bits (entiers courts non signés)
  • /
function intToBinStr($int,$size=16) { $tmp = $int; $sbin=''; for ($i=0;$i<$size;$i++) { $bit = pow( 2 , $size-$i-1 ); if ( $tmp >= $bit ) { $sbin .= '1'; $tmp = $tmp-$bit; } else $sbin .= '0'; } return $sbin; } /** fonction tri de tableau treeItems retourne le tableau de treeitems trié par ordre decroissant
  • /
function a_sort($nodes) { $cnt=count($nodes); for ($a=0;$a < $cnt;$a++) { for ( $i=$a+1 ; $i < $cnt ; $i++ ) { if ($nodes[$i]->cksize() > $nodes[$a]->cksize()) { $tmp = $nodes[$i]; $nodes[$i] = $nodes[$a]; $nodes[$a] = $tmp; } } } return $nodes; } class treeItems implements recursiveIterator { protected $childnodes = null; protected $value = 0; /** Constructeur privé l'instanciation d'un treeitem se fait par la methode statique create 2 types de tree items sont instanciables: les feuilles et les noeuds
  • /
private function __construct ($args) { if (!is_array($args)) throw new Exception ('Paramètre array attendu'); $nbargs = count($args); if ($nbargs >= 2) { $this->childnodes=new recursiveArrayIterator(array()); foreach($args as $key=>$item) { if (get_class($item)===__CLASS__) { $this->childnodes[]= $item; $this->value += $item->value; } else throw new Exception ('instance de type '.__CLASS__.' attendue'); } } else { if ($nbargs==1) { $this->value = $args[0]; } else throw new Exception ('Paramètres invalides'); } } /** methode implementant l'interface recursiveIterator
  • /
public function current() { return current ($this->childnodes); } /** methode implementant l'interface recursiveIterator
  • /
public function key() { return key($this->childnodes); } /** methode implementant l'interface recursiveIterator
  • /
public function next() { return next($this->childnodes); } /** methode implementant l'interface recursiveIterator
  • /
public function valid() { return ($this->current() !== false); } /** methode implementant l'interface recursiveIterator
  • /
public function rewind() { reset($this->childnodes); } /** methode d'affichage par echo ou print
  • /
public function __toString() { return (string)$this->value; } /** le checksize
  • /
public function cksize(){ return $this->value; } /** la methode de fabrication des treeitems. Le type attendu est géré par le constructeur
  • /
public static function create() { $args = func_get_args(); return new self($args); } /** methode implementant l'interface recursiveIterator
  • /
public function getChildren() { return $this->childnodes; } /** Recupération du nieme (key) child
  • /
public function getChild($key) { if (isset($this->childnodes[$key])) return $this->childnodes[$key]; else return false; } /** methode implementant l'interface recursiveIterator
  • /
public function hasChildren() { return (!is_null($this->childnodes)); } } /** Structure arborescente codec iterative et recursive
  • /
class huffmanTree extends RecursiveArrayIterator { //la racine protected $root; //la chaine source protected $strSrc; //les feuilles pour le dictionnaire protected static $letters=array(); //prefixe pour cle const chars='chr_'; /** Constructeur parametre treeItems, src string
  • /
public function __construct ($root,$srcStr=null) { if (isset($root) && get_class($root)==='treeItems') $this->root=$root; else throw new Exception ('Paramètre de type treeItems attendu'); $this->strSrc = $srcStr; parent::__construct ($this->root); } /** Methode statique de creation de l'arbre d'huffman à partir d'une chaine Permet de créer un dictionnaire
  • /
static public function createFromString ($srcStr=null) { if (is_string($srcStr)) { $srcStr.='.'; //Création des feuilles avec des caractères ascii foreach (count_chars($srcStr, 1) as $i => $val) { if ($i<256) $leaves[self::chars.chr($i)]=$val; else throw new Exception ('Ne supporte que l\'ascii'); } array_multisort($leaves,SORT_DESC,SORT_NUMERIC); $count=count($leaves); foreach($leaves as $key=>$val) { $nodes[]=self::$letters[$key]=treeItems::create($val); } return new self(array_pop(self::createtree($nodes)),$srcStr); } else throw new Exception('erreur d\'argument pour creer le schema'); } /** Methode statique de creation de l'arbre d'huffman à partir d'un dictionnaire. Il s'agit du dictionnaire utilisé pour la compression
  • /
static public function createFromDictionnary ($dictionnary) { if (is_array($dictionnary)) { //Création des feuilles foreach ($dictionnary as $i => $val) { if ($i<255) $leaves[self::chars.chr($i)]=$val; else throw new Exception ('Ne supporte que l\'ascii'); } array_multisort($leaves,SORT_DESC,SORT_NUMERIC); $count=count($leaves); foreach($leaves as $key=>$val) { $nodes[]=self::$letters[$key]=treeItems::create($val); } return new self(array_pop(self::createtree($nodes))); } else throw new Exception('erreur d\'argument pour creer le schema'); } public function fileCompress ($compressFile,$bin,$blocsize=16) { $fp=fopen($compressFile,'wb'); if ($fp) { fwrite($fp,$bin); fclose($fp); } } /** Methode de compression par bloc de 16 bits qui encode en short int.
  • /
public function compress($blocsize=16) { $returnEncoded=''; $rest = $blocsize; $enc=0; $enableCode=''; $restCode=''; /* Compression en chaine binaire chaque caractère est ici compressé en une longueur de n bits égale à la transcodification binaire du chemin entre la racine et la feuille de l'arbre d'huffman
  • /
$length = strlen($this->strSrc); for( $k=0 ; $k < $length ; $k++ ) { $code = $this->encode(self::$letters[self::chars.$this->strSrc{$k}]); $enableCode .= $restCode.substr($code,0,$rest); $restCode = substr($code,$rest); $start = strlen($enableCode); $rest = $blocsize - $start; if ($rest===0) { $enc=pack('S',binStrToInt($enableCode,$blocsize) ); $returnEncoded.=$enc; $start =0; $enc=0; $rest = $blocsize; $enableCode=''; } } if ( !empty($enableCode) && strlen($enableCode)<$blocsize ) { $tmpCode = $enableCode; $tmpCode.=str_repeat('0',$blocsize - strlen($enableCode)); $enc=pack('S',binStrToInt($tmpCode,$blocsize) ); $returnEncoded.=$enc; } return $returnEncoded; } /** Décompression
  • /
public function uncompress($binary,$blocsize=16) { /* Initialisation
  • /
$lng = strlen($binary); $tmpstr=''; $srcStr=''; $ln=1; $test = true; $octets=''; for ($i=0;$i<$lng;$i+=$blocsize/8) { $strbin = @unpack('S',substr($binary,$i,$blocsize/8)); $octets .=intToBinStr($strbin[1],$blocsize); } $lng = strlen($octets); for ($i=0;$i<$lng;$i++) { $tmpstr.=substr($octets,$i,1); $decode = $this->decode($tmpstr); if (!$decode->hasChildren()) $tmpstr=''; foreach(self::$letters as $key=> $val) { if ($decode===$val) { $srcStr .= substr($key,strlen(self::chars)); } } } return substr($srcStr,0,$this->root->cksize()-1); } public function fileUncompress($binfile,$blocsize=16) { $octets=''; $fp = fopen($binfile,'rb'); if ($fp) { while(!feof($fp)) { $buffer .= fread($fp,$blocsize/8); } fclose($fp); } return $this->uncompress($buffer); } public function __get($prop) { if ( property_exists ( get_class($this) , $prop) ) return $this->$prop; else throw new Exception ('Propriété inexistante'); } /** Methode recursive qui retourne une chaine representant le chemin binaire entre la racine et le treeItems passé en paramètre
  • /
private function encode($item,$tmp=false,$initStatic=true) { static $ok = false; if ($tmp===false) { $tmp=$this->root; } if ($initStatic) $ok = false; $path=''; if ($tmp && get_class($tmp)=='treeItems') { if ($tmp->hasChildren()) { $it=$tmp->getChildren(); foreach ($it as $key=>$obj) { if (!$ok) $path = $key.$path; if ($obj === $item) { if (!$ok) { $ok = true; unset ($tmp); return $path; } } else { if (!$ok) $path.=$this->encode($item,$obj,false); if (!$ok) $path = substr($path,0,-1); } } } } return $path; } /** Conception du schema de compression decompression
  • /
static protected function createtree($nodes) { if (count($nodes)>1) { $item1 = array_pop($nodes); $item2 = array_pop($nodes); $nodes[] =treeItems::create($item2,$item1); $nodes = a_sort($nodes); $nodes = self::createtree($nodes); } return $nodes; } /** Methode qui retourne le treeItems correspondant au chemin binaire passé en paramètre depuis la racine
  • /
private function decode($strbin) { $depth = strlen($strbin); $tmp = $this->root; for ($i=0;$i<$depth;$i++) { $test = $tmp->getChild((int)$strbin{$i}); if ( $test!==false ) $tmp = $tmp->getChild((int)$strbin{$i}); } return $tmp; } /** Affichage et retours des stats et infos sur fréquence des caractère Pour ne pas utiliser l'affichage retirer la ligne echo
  • /
public function displaySchema() { $prfxLength = strlen(self::chars); foreach (self::$letters as $key => $val) { $bin[$key][0]=$this->encode($val); $bin[$key][1]=$val->cksize(); echo '<br/>'.substr($key,$prfxLength).'=>'.$bin[$key][0].' => '.$bin[$key][1] ; } return $bin; } } if (isset($_POST['phrase'])) { set_time_limit(0); $phrase = $_POST['phrase']; echo $phrase.'<br/>'; $codecObj = huffmanTree::createFromString($phrase); $binary = $codecObj->compress(); $compressSize =strlen($binary); $rate =(1-($compressSize/strlen($phrase)))*100; echo '<br/>Compression à '.$compressSize.' octets : '.$binary; echo '<br/>Decompression : '.$codecObj->uncompress($binary,16); echo '<br/>Taille Originale : '.strlen($phrase).' octets' ; echo '<br/>Taux De compression : '.$rate.'%' ; echo '<br/>Comparaison avec gzcompress: '; $gz = gzcompress($phrase,9); echo '<br/>GZ: '.$gz; echo '<br/>GZ TAILLE compressée: '.strlen($gz).'octets'; } ?> </body> </html>

Conclusion :


Voilà ce script fonctionne maintenant avec n'importe quelle chaine ascii si la compression et la decompression se fait avec le même arbre(donc si celle ci a lieu dans le même script d'exécution.)
Pour une Compression ou Décompession indépendante l'une de l'autre: Il faudrait stocker des stats générales sur la fréquence des caractères les plus utilisés dans un texte afin de constituer à chaque fois le même arbre et pouvoir l'utiliser indépendament de la compression ou de la décompression.
Pour info la compression n'est que de 50%, donc une optimisation est possible.

Ajout de la comparaison avec gzcompress sur exemple: il s'avère que la compression de la classe est bien meilleure sur les petites chaines : ce n'est pas étonnant car gz se base sur un grand dictionnaire dont la performance ne se fait ressentir que sur les longues chaines.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

poubelle2077
Messages postés
1
Date d'inscription
vendredi 14 avril 2006
Statut
Membre
Dernière intervention
26 avril 2009
-
Hello,

J'ai commencé à lire le code. Cela me semble bien.
Je ne programment plus depuis longtemps avec des pointeurs (c ou C++) et je me posais justement la question de l'implémentation d'un arbre avec un langage ne possédant pas ce type de choses.
L'utilisation des itérateurs et des tableaux me sembles une bonne idée.
Ce que je regrette avec cette technique c'est que l'algo est complètement noyé dans le code. C'est la faut des itérateurs ...
J'ai pas tout lu, mais par exemple mais :

function a_sort($nodes)

Il me semble que uasort fasse exactement ça.

Je continue donc à lire et mes recherches d'implémentation d'arbre.
A+
guill76
Messages postés
193
Date d'inscription
mercredi 24 août 2005
Statut
Membre
Dernière intervention
3 juin 2016
-
Salut, merci.
Pour cela une des methodes possibles est l'utilisation d'une fonction de requete recursive qui te retourne pour chaque objet et dans chaque profondeur de ta hierarchie d'objet l'ensemble des enfants associés à ton objet=> tu dois également stocker le niveau hierarchique des enfants(profondeur) pour déterminer le nombre de '.' à écrire dans ton fichier affiliation.txt (la strucuture de ton arbre).

Ou alors tu fais directement une requête hierarchique si ta DB le permet.
cs_caviar
Messages postés
329
Date d'inscription
samedi 4 janvier 2003
Statut
Membre
Dernière intervention
29 mars 2015
3 -
yepa ! très bon code ... mais question con ...
comment je fais pour l'utiliser à partir d'une requete sur une bdd ?
genre j'ai ma table avec idTruc, IdParentDeTruc, NomDeTruc
et j'aimerai classer tout ça dans un bel arbre comme celui ci ...
possible ?
++
TheSin
Messages postés
331
Date d'inscription
mardi 12 novembre 2002
Statut
Membre
Dernière intervention
10 février 2009
-
certes, ça ne devrait pas, mais bon, c'est PHP qui veut ça et faut donc s'y faire : une clé totalement numérique est toujours considérée comme un index, raison de logique pour simplifier la vie au codeur ^^
guill76
Messages postés
193
Date d'inscription
mercredi 24 août 2005
Statut
Membre
Dernière intervention
3 juin 2016
-
Non non t'as pas à t'en faire, je déconnais à 100%.
Ceci dit je retiens ta solution pour le prefixe sur la clé.
Sinon exact c'est bien la notion de clé et non d'index (je me suis mal exprimé). Mais je ne demords toujours pas du fait que $tab['1'] ne devrait pas dans l'idéal, faire référence à la même adresse que $tab[1].

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.