CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 27 17:56:44

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

Class et Objet ( POO )

> PHP5 CLASSE ARBRE INVERSÉ (HUFFMAN) COMPRESSION DECOMPRESSION

PHP5 CLASSE ARBRE INVERSÉ (HUFFMAN) COMPRESSION DECOMPRESSION

Information sur la source

Note :

9,33 / 10

Catégorie :Class et Objet ( POO ) Classé sous :arbre, huffman, compression, décompression, php5 Niveau :Initié Date de création :20/01/2007 Date de mise à jour :18/02/2007 15:11:09 Vu / téléchargé :15 521 / 219

Auteur : guill76

Ecrire un message privé

Commentaire sur cette source (15)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

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

<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>

<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.

Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Huffman
- tree
  - about.html 1 149 octets
  - demomenu.txt 686 octets
  - filiation.txt 1 150 octets
  - readme.txt 2 172 octets
  - tree_collapse.gif 115 octets
  - tree_end.gif 107 octets
  - tree_expand.gif 117 octets
  - tree_leaf.gif 116 octets
  - tree_space.gif 88 octets
  - tree_split.gif 110 octets
  - tree_vertline.gif 108 octets
  - treeMenu.cls.php 9 003 octets
  - treemenu.inc.original8 425 octets
- demotreemenu.php 1 612 octets
- demotreemenu.php.original1 389 octets
- example.php 1 990 octets
- huffman3.php 12 876 octets

Télécharger le zip

Historique

20 janvier 2007 23:48:37 :: ..
21 janvier 2007 17:20:50 :: classe et mehtode ajoutée pour exemple d'encodage
21 janvier 2007 21:19:38 :: Voilà pour les itérateurs.
21 janvier 2007 22:51:26 :: ajour du decode.
22 janvier 2007 23:25:05 :: Ajout d'un exemple de compression.
22 janvier 2007 23:41:22 :: viré un echo de test dans la boucle
23 janvier 2007 23:23:43 :: ça marche.
24 janvier 2007 20:32:18 :: Debuggage sur dernier caractere incorrect + nettoyage, optimisations et explications complémentaires N'hésitez pas à critiquer mon code.
24 janvier 2007 23:43:42 :: .
02 février 2007 20:14:16 :: Création de l'arbre par tri récursif (détermination du chemin le plus court pour les grandes fréquences de caractères).
09 février 2007 23:25:05 :: Encapsulation des methodes de creation de l'arbre, de compression ,et de decompression
10 février 2007 10:53:55 :: le constructeur de l'arbre public devient privé: public était une erreur car l'objet ne peut être construit que la par methode createFrom.
10 février 2007 12:10:35 :: Ajout d'une comparaison avec gz.
11 février 2007 15:03:34 :: remise en public du constructeur j'avais oublié l'héritage. certes c'est peu élégant mais tant pis.
18 février 2007 12:59:15 :: ajout de l'affichage arborescent du schéma de compression + mise en ligne d'une vieille source sympathique de tree menu (bjorge Dijkstra) ré adaptée rapidement à php5. script à lancer example.php
18 février 2007 15:11:09 :: snapshot

Sources du même auteur

CLASSE FEUILLE DE TEMPS PHP5

PHP 5 CLASSES DE REDIRECTION DES EXCEPTIONS DANS UN SYSTÈME...

[PHP5]AUTHENTICATION MANAGER

PHP 5 CLASSE CALENDRIER QUI RENVOIE LA DATE CLIQUÉE DANS 1 É...

DATASOURCE : ABSTRACTION DE DONNÉES

Toutes les sources de guill76

Sources de la même categorie

GÉNÉRATION AUTOMATIQUE DE FICHIER .CLASS.PHP EN FONCTION D'U... par ig3

CLASSE D'OBJET DE CRYPTAGE ET DÉCRYPTAGE DE CHAINES DE CARAC... par 8Tnerolf8

MY.DEVIANTART API par inwebo

CLASSE DE GESTION DE "VARIABLES GLOBALES D'ENVIRONNEMENT" par pifou25

COLLECTION.CLASS.MIN.PHP par thunderhunter

Toutes les sources de la catégorie Class et Objet ( POO )

Sources en rapport avec celle ci

MY.BOOKMARKS par inwebo

M.V.C M.E.D par faceme

TODO LIST (AJAX/PHP5) par VinceMonkeyz

CLASSE WIKILOC par aKheNathOn

CALENDRIER EN 70 LIGNES par tchconst

Commentaires et avis

Commentaire de TheSin le 21/01/2007 17:37:25

Pourquoi tu poste ton code source incomplet ? (je fait référence aux fonctions pour l'itérativité)

Commentaire de guill76 le 21/01/2007 17:50:46

j'ai besoin de plus maitriser les itérateurs pour le faire.
Ici j'ai mis une fonction récursive (encode) qui peut pallier pour une certaine utilisation mais qui n'offre pas le potentiel des itérateurs.
Donc voilà en attendant que je maitrise , c'était pour montrer une orientation possible que j'ai mis ces méthodes.
C'est aussi pour çà que je n'ai mis que débutant.

Commentaire de guill76 le 23/01/2007 13:06:30

Oups, je me suis aperçu d'une etourderie, la boucle foreach dans la quelle j'encode ne compresse pas, je rectifierai plus tard avec un exemple plus sympa.
En fait il faut décaler tous les bits à gauche et faire une sorte de concatenation avec les codes suivants pour remplir complétement chaque octet.

Commentaire de TheSin le 23/01/2007 15:18:39

lol, ok pour la réponse du 21, j'avais pas vu ;-)
je te conseille d'aller voir une des sources de malalam pour voir les itérateurs de plus près ;-)

Commentaire de guill76 le 23/01/2007 19:24:39

je les ai déjà vues, mais bon dans mon cas et après reflexion, je suis sur que j'ai de toute facon besoin d'une fonction recursive spécialisée.

Commentaire de guill76 le 25/01/2007 21:07:52

Je sais que ce n'est pas d'une grande utilité (bzcompress existe déjà avec ce principe), mais si ça peut familiariser les débutants avec certaines notions fondamentales, c'est toujours ça de gagner.

Commentaire de TheSin le 26/01/2007 09:47:12

a bin moi je suis pas d'accord avec toi guill76.
je suis sûr que ça aurait pû permettre à des collègues de ma classe de comprendre plus facillement les algorithmes de compression ;-) (sujet de maths sup', soutenance et programme en C à faire en 3 jours).
Bref, je trouve ta source très utile, de plus avec l'itérativité peu souvent utilisée en PHP ;-)

Commentaire de guill76 le 02/02/2007 21:34:59

Ouh la Par contre y a gros un bug sur les entiers : un défaut de php.
Ce sont les tableaux php qui gérent mal les entiers en string comme index: aucune différenciation entre $tab['1'] et $tab[1] (grossiéééééééééer) et même si je fais $tab[(string)$index].
Mais je ne critique pas que php, y a aussi 1 autre bug sur mon script cette fois, encore sur le dernier caractère, (je coyais qu'il était pourtant réglé celui là) mais maintenant il apparait sur les longues chaines.

Commentaire de guill76 le 02/02/2007 22:17:40

(Humeur: D'ailleurs je critique aussi N.S que je ne veux absolument pas comme président, à moins qu'il réussisse, à partir d'une analyse ADN, à retouver le mec qui a développé les tableaux PHP, même si, je ne souhaite même pas non plus à ce developpeur de séjourner en cabanne.
Au final, et d'un point de vue égoïste, si il passait, je pourrais aussi m'expatrier dans un autre pays et ça me permettrait de voir autre chose ;-))

Commentaire de TheSin le 03/02/2007 17:37:22

Faut pas en avoir à celui (voire ceux) qui a codé les tableaux PHP, mais directement à Rasmur Lerdorf, puisque c'est certainement lui qui a choisi que le PHP devait être un langage simple.
L'un des principes de PHP c'est bien les conversions de variables automatiques, et des tableaux, à la base de tous les langages, sont indexés numériquement, et donc n'ont pas de clé.
Si tu veux lui mettre une clé et non un index à la place, t'as qu'à simplement rajouter un carcatère alphabêtique à la chaîne ;)
Donc : $tab[ 'car' . (string)$index]

Commentaire de guill76 le 05/02/2007 23:50:06

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].

Commentaire de TheSin le 07/02/2007 07:31:25

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 ^^

Commentaire de caviar le 22/01/2008 12:16:37

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 ?
++

Commentaire de guill76 le 23/01/2008 15:43:54

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.

Commentaire de poubelle2077 le 26/04/2009 22:55:34 9/10

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+

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

décompression de fichiers... [ par ChocoBiscuit ] Salut tout le monde....Existe t'il un utilitaire de decompression pour les fichiers .gz???Si oui, où, et surtout comment cela fonctionne...Sinon... be differnec entre php 4 et php5 [ par hardelgylls ] Bonjourpetite question :j'ai passer un oral et l'examinateur m'a demandé quel était la différence entre php4 et php5. et la gros blanc, est ce que qqu Doc PHP5 sniff sniff [ par slhuilli ] Bonjour, Bonsoir,Je suis a la recherche d'un PDF qui recenserait les mots-clefs + explications (bref un bouquin complet) sur PHP 5 qui parait-il est taille d'une page avant et après compression [ par ilvec ] Bonjour,j'utiliser la fonction ob_start("ob_gzhandler") pour compresser mes pages, mais pour savoir si c'est vraiment utile, je voudrais connaitre la Pb passage PHP4 -> PHP5 [ par Galmiza ] Salut,J'ai acheté un bouquin pour débuter le PHP.J'ai suivi a la lettre les instructions du livre:-installer EasyPHP 1.7-installer PHP 5.0..-lancer Ea Cohabitation PHP4 PHP5 sur même serveur ! [ par Zacland ] Ce n'est pas une question, mais je me doute que certaines personnes veulent essayer de faire cohabiter 2 versions de PHP sur un même serveur Apache... Un caractére se trouve t'il dans ma chaîne... [ par juki_webmaster ] Bonsoir,Je travaille depuis 14h cette apres-midi sur une fonction alternative d'une fonction connu et disponible uniquement sur php5, je fait cette fo PHP5 en PHP3 [ par el shaddai ] J'ai développé une partie de site en PHP5. MAlheureusement , chargé chez FREE, ils n'utilisent que PHP3. Y a t-il une manip simple pour qur du PHP5 pa PHP5 et MySQL 4.1.7 [ par TMT ] J'ai installé PHP5 et MySQL sur mon Windows XP avec IIS. J'ai bien activé le module php_mysql dans le fichier php.ini Là mon problème est qu-à chaque php4 vers php5 [ par aurelielaugraud ] Bonjour, Je suis passée de php4 à php5 pour utiliser la librairie graphique GD. Seulement, un programme que j'avais précédemment faire refuse de fonct

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

RE : REMPLIR UN TABLEAU à PARTIR DE LA FIN par Jeromedu79

RE : MYSQL_FETCH_ASSOC par moumenxavi

RE : MYSQL_FETCH_ASSOC par inwebo

RE : REMPLIR UN TABLEAU à PARTIR DE LA FIN par inwebo

RE : CHANGER LE CONTENU D'UNE PAGE WEB EN PHP EN CLIQUAN SUR UN BOUTON (J'AI BESOIN D'AIDE) par inwebo

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Realisation d-une version 2 d-un site e-commerce existant sous prestashop-REPUBLICATION
Budget : 5 000€
Recherche Infogerance Serveur Debian Linux
Budget : 1 800€
Creation d-un site vitrine avec MagentO
Budget : 2 000€

Logiciels

sDEVIS-FACTURES vlPRO (8.1.0.3)
SDEVIS-FACTURES VLPRO (8.1.0.3)

sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa...

Cliquez pour télécharger sDEVIS-FACTURES vlPRO
974 Application Server (12.2.4.6)
974 APPLICATION SERVER (12.2.4.6)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP