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