Compression LZW en Actionscript 2
Par -Alexandre LEGOUT aka LAlex- le vendredi, mai 21 2004, 17:48 - Liens - Lien permanent
ShoeBox nous gratifie sur son blog d'une implémentation en AS2 de l'algorithme de compression LZW. Voici qui peut être bien pratique pour réduire les transferts de données, pour peu que le serveur qui receptionne ou envoie les données implémente lui aussi cet algo.
Au passage, j'en profite pour signaler ce blog à ceux qui ne le connaissent pas encore. ShoeBox tournait avant sur un blog en Flash trés bien conçu, qui devrait faire son retour un de ces jours !!! ![]()
Commentaires
Vraiment bien tout cela, et en attendant son retour en FLASH, j'aime beaucoup sa charte graphique en tout cas.
Par contre pour ce qui est des classes.. je suis en train de voir à les reprendre car je les trouve pas super optimisées... je posterai sur son blog quand j'aurai fini mes petites transformations

bye
Non éffectivement les classes ne sont pas encore super optimisées... c'était un premier jet pour pouvoir exposer le principe
mais je vais prochainement reposter une nouvelles version, optimisée et utilisant de facon plus utile la syntaxe AS2. Il faut également implémenter l'overflood du dictionnaire ascii, j'avai préparée la chose en n'utilsant pas les valeur 256 et 257 pour les transformer en caractére de réinitialisation dictionnaire et d'EOF 
Sinon un conseil.. si je peux me permettre

Entre tes variables locales temporaires dans tes fonction en les déclarant non pas au début de ta classe mais en local dans les méthodes. Je ne pense pas que cela soit utile de tout garder sous forme de propriété...
Bon

je met le code ici car lalex a mi les balises AS sur son blog, cela sera peut être un peu plus clair pour la relecture
/* ------------------- LZW v 0.0.1
Name : LZW
Package : com.eka.compression
Version : 0.0.1
Date : 2004-05-22
Author : ekameleon
URL : <a href="http://www.ekameleon.net" rel="nofollow">http://www.ekameleon.net</a>
Mail : <a href="mailto:contact@ekameleon.net" rel="nofollow">contact@ekameleon.net</a>
DESCRIPTION
La classe LZW (Lempel Ziv Welch) permet de compresser ou de décompresser une chaine de caractère.
Les méthodes sont utilisables sans constructeur.
UTILISATION
import com.eka.compression.LZW ;
var txt:String = "L'intérêt de cette méthode réside dans le fait qu'un indice est transféré sur 12 bits." ;
var c:String = LZW.compress (txt) ; // compression
var d:String = LZW.decompress (c) ; // décompression
trace(txt + "
Taille avant la compression : " + txt.length ) ;
trace ("------- compression") ;
trace (c + "
Taille après la compression : " + c.length ) ;
trace ("------- décompression") ;
trace(d + "
Taille après la décompression : " + d.length ) ;
PUBLIC METHODS
- compress ( str:String)
# paramètre : une chaine de caractère que l'on souhaite compresser.
# renvoi : une chaine de caractère
- decompress ( str:String)
# paramètre : une chaine de caractère compressée avec l'algorithme LZW que l'on souhaite décompresser
# renvoi : une chaine de caractère
REMERCIEMENTS :
shoebox : <a href="http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw" rel="nofollow">http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw</a>
lalex : <a href="http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments" rel="nofollow">http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments</a>
------------------------- */
class com.eka.compression.LZW {
//----o Constructor
private function LZW() {}
//----o Publics Methodes
static public function compress ( str : String ) : String {
var dico:Array = new Array() ;
for ( var i=0 ; i<256 ; i++) dico[ String.fromCharCode (i) ] = i ;
var result:String = "";
var txt2encode:String = str ;
var splitStr:Array = txt2encode.split("") ;
var length:Number = splitStr.length ;
var nbChar:Number = 257 ; // Nombres de caractères courant dans le dictionnaire
var buffer:String = "" ; // initialisation du tampon buffer
for (var i:Number=0 ; i <= length ; i++) {
var current = splitStr[i] ;
if ( dico[ buffer + current ] !== undefined ) {
buffer += current ;
} else {
result += String.fromCharCode ( dico[buffer] ) ;
dico [buffer + current] = nbChar ;
nbChar ++ ;
buffer = current ;
}
}
return result ;
}
static public function decompress ( str:String ) : String {
var dico:Array = new Array() ;
for ( var i:Number=0 ; i<256 ; i++) {
var c:String = String.fromCharCode (i) ;
dico[c] = c ;
}
var txt2encode:String = str ;
var splitStr:Array = txt2encode.split("") ;
var length:Number = splitStr.length ;
var nbChar:Number = 257; // nombre de caractère courant dans le dictionnaire
var buffer:String = "" ; // initialisation du tampon mémoire
var chaine:String = "" ; // chaine temporaire
var result:String = "" ; // chaine retournée à la fin de la décompression
for ( var i:Number = 0 ; i < length ; i++) {
var current:String = splitStr [i] ;
var code:Number = txt2encode.charCodeAt(i) ;
if (buffer == "") {
buffer = current ;
result += current ;
} else {
if ( code <= 256 ) {
result += current ;
chaine = buffer + current ;
dico [ nbChar ] = chaine ;
nbChar ++ ;
buffer = current ;
} else {
chaine = dico [ code ] ;
result += chaine ;
dico [nbChar] = buffer + chaine.slice (0, 1);
nbChar ++ ;
buffer = chaine ;
}
}
}
return result;
}
}
Pour le moment j'ai repris un peu ton code car j'avais une erreur avec le tiens sur un caractère de fin style une virgule ou un point qui apparaissait pas à la décompression ...
J'ai repris aussi ton algo en 1 seule classe avec des méthodes statiques.
Le plus important je pense c'était de bien faire en sorte de ne pas conserver le dictionnaire en mémoire, c'est justement l'intérêt de cet algorithme à ce que j'ai cru comprendre.
bye
ah ! ... des problèmes sur certains caractères au dessus dans les balises AS...
les < n'ont pas l'air de bien passer convenablement, ils ont été remplacé par <
oui éffectivement mais il n'y a aucun dictionnaire, il est reconstitué pendant les phases de compression et de décompression. J'avai mis à la suite les deux phases pour montrer que le code fonctionnait correctement
Par contre, il faudrai que j'implémente aussi un parseur de code dans mon blog ca sera plus propre et lisiblle
shoebox > J'ai fait un colorisateur de code en PHP si tu veux : http://www.lalex.com/dsplay/
++ ^^
_global.LZW = function (){
implémentation en AS1 pour les viellards ... une question pour nos experts : dans un fla je code :trace("LZW");
}
_global.LZW.prototype.compress = function ( str ) {
var dico= new Array() ;
for ( var i=0 ; i<256 ; i++) dico[ String.fromCharCode (i) ] = i ;
var result = "";
var txt2encode = str ;
var splitStr = txt2encode.split("") ;
var length = splitStr.length ;
var nbChar= 257 ; // Nombres de caractères courant dans le dictionnaire
var buffer = "" ; // initialisation du tampon buffer
for (var i=0 ; i <= length ; i++) {
var current = splitStr[i] ;
if ( dico[ buffer + current ] !== undefined ) {
buffer += current ;
} else {
result += String.fromCharCode ( dico[buffer] ) ;
dico [buffer + current] = nbChar ;
nbChar ++ ;
buffer = current ;
}
}
return result ;
}
_global.LZW.prototype.decompress = function ( str ) {
var dico = new Array() ;
for ( var i=0 ; i<256 ; i++) {
var c = String.fromCharCode (i) ;
dico[c] = c ;
}
var txt2encode = str ;
var splitStr = txt2encode.split("") ;
var length = splitStr.length ;
var nbChar = 257; // nombre de caractère courant dans le dictionnaire
var buffer = "" ; // initialisation du tampon mémoire
var chaine = "" ; // chaine temporaire
var result = "" ; // chaine retournée à la fin de la décompression
for ( var i = 0 ; i < length ; i++) {
var current = splitStr [i] ;
var code = txt2encode.charCodeAt(i) ;
if (buffer == "") {
buffer = current ;
result += current ;
} else {
if ( code <= 256 ) {
result += current ;
chaine = buffer + current ;
dico [ nbChar ] = chaine ;
nbChar ++ ;
buffer = current ;
} else {
chaine = dico [ code ] ;
result += chaine ;
dico [nbChar] = buffer + chaine.slice (0, 1);
nbChar ++ ;
buffer = chaine ;
}
}
}
return result;
}
#include "LZW.as"Lzw_compressor = new LZW();
var txt = "Question How can I pass long string between Flash and email without using DB? Problem I'm currently sending a long string from Flash MX to PHP email compiler, that sends this string as an URL within the email. Person should click on this URL and be brought back to Flash that takes the string. The problem is URL length limit";
var c = Lzw_compressor.decompress(txt);// compression
var d = Lzw_compressor.decompress(c);
// décompression
trace(txt+"
Taille avant la compression : "+txt.length);
trace("------- compression");
trace(c+"
Taille après la compression : "+c.length);
trace("------- décompression");
trace(d+"
Taille après la décompression : "+d.length);
output //--->
Question How can I pass long string between Flash and email without using DB? Problem I'm currently sending a long string from Flash MX to PHP email compiler, that sends this string as an URL within the email. Person should click on this URL and be brought back to Flash that takes the string. The problem is URL length limit
Taille avant la compression : 325
------- compression
question how caCi pass lcg ArinEbetweeCflEh dd email witCut usGEdb?EroblI i'mcurrHtlyeHd?Ieeetgg fNoII mx toEhpii?comp?er,UhaLsrE?iEGrEICoJK?C?eU?l.EŸsceLlIclick ??E??Ig bNughLbaOUUtsi?ŽUakaZ??g??nnno?lrJng?eim
Taille après la compression : 210
------- décompression
question how can i pass long string between flash and email without using db? problem i'm currently sending a long string from flash mx to php email compiler, that sends this string as an url within the email. person should click on this url and be brought back to flash that takes the string. the problem is url length lim
Taille après la décompression : 323
--------------------------------------------------------------------------
la compression ne gère donc pas la casse et il y a un bug sur le mot limit (il manque 2 charatères)
Tiens .. faut que je vois cela
est-ce une faute de frappe ou bien tu essais de décompresser du texte non-compressé?
on dirait bien ... car sur mes tests cela marche bien mon algo au dessus
Il est éffectivement assez suspect que tu décompresse un texte non compressé ce qui peut expliquer les érreurs pedant la création du dictionnaire. Mais sinon cet algo gére trés bien la casse et les caractères spéciaux
LZW rulez ! et c'est tout free maintenant (fin de brevet)
oui
)
pour le decompress c'est une faute de frappe
en revanche ma classe AS1 ne gère pas la casse ...
et ça marche avec ta version, Eka.
j'ai surement glissé quelques bugs
enfin bravo pour l'implémentation.
une question pensez vous que ce sois intéressant de compresser un XML dans la class WDDX
( as1 ou as2
A+
/* ------------------- LZW v 0.0.1
* AS1 Class.
Name : LZW
AS1 Package : org.kiwispirit.LZW
Version : 0.0.1
Date : 2004/6/3
Author : clement hussenot
URL : <a href="http://www.1stfloorlab.com" rel="nofollow">http://www.1stfloorlab.com</a>
Mail : <a href="mailto:clement@hussenot.com" rel="nofollow">clement@hussenot.com</a>
DESCRIPTION
La classe LZW (Lempel Ziv Welch) permet de compresser ou de décompresser une chaine de caractère.
Les méthodes sont utilisables sans constructeur.
UTILISATION
#include "LZW.as"
cLZW = new _global.org.kiwispirit.LZW();
//var txt = "L'intérêt de cette méthode réside dans le fait qu'un indice est transféré sur 12 bits.";
var c = cLZW.compress(txt);
// compression
var d = cLZW.decompress(c);
// décompression
trace(txt+"
Taille avant la compression : "+txt.length);
trace("------- compression");
trace(c+"
Taille après la compression : "+c.length);
trace("------- décompression");
trace(d+"
Taille après la décompression : "+d.length);
PUBLIC METHODS
- compress ( str)
# paramètre : une chaine de caractère que l'on souhaite compresser.
# renvoi : une chaine de caractère
- decompress ( str)
# paramètre : une chaine de caractère compressée avec l'algorithme LZW que l'on souhaite décompresser
# renvoi : une chaine de caractère
REMERCIEMENTS :
shoebox : <a href="http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw" rel="nofollow">http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw</a>
lalex : <a href="http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments" rel="nofollow">http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments</a>
ekamelon : <a href="http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comm1257" rel="nofollow">http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comm1257</a>
------------------------- */
if (_global.org == undefined) _global.org = new Object();
if (_global.org.kiwispirit == undefined) _global.org.kiwispirit = new Object();
//----o Constructor
_global.org.kiwispirit.LZW = function() {
}
//----o Publics Methodes
_global.org.kiwispirit.LZW.prototype.compress = function ( str ) {
var dico = new Array() ;
for ( var i=0 ; i<256 ; i++) dico[ String.fromCharCode (i) ] = i ;
var result = "";
var txt2encode = str ;
var splitStr = txt2encode.split("") ;
var length = splitStr.length ;
var nbChar = 257 ; // Nombres de caractères courant dans le dictionnaire
var buffer = "" ; // initialisation du tampon buffer
for (var i=0 ; i <= length ; i++) {
var current = splitStr[i] ;
if ( dico[ buffer + current ] !== undefined ) {
buffer += current ;
} else {
result += String.fromCharCode ( dico[buffer] ) ;
dico [buffer + current] = nbChar ;
nbChar ++ ;
buffer = current ;
}
}
return result ;
}
_global.org.kiwispirit.LZW.prototype.decompress = function ( str ) {
var dico = new Array() ;
for ( var i=0 ; i<256 ; i++) {
var c = String.fromCharCode (i) ;
dico[c] = c ;
}
var txt2encode = str ;
var splitStr = txt2encode.split("") ;
var length = splitStr.length ;
var nbChar = 257; // nombre de caractère courant dans le dictionnaire
var buffer = "" ; // initialisation du tampon mémoire
var chaine = "" ; // chaine temporaire
var result = "" ; // chaine retournée à la fin de la décompression
for ( var i = 0 ; i < length ; i++) {
var current = splitStr [i] ;
var code = txt2encode.charCodeAt(i) ;
if (buffer == "") {
buffer = current ;
result += current ;
} else {
if ( code <= 256 ) {
result += current ;
chaine = buffer + current ;
dico [ nbChar ] = chaine ;
nbChar ++ ;
buffer = current ;
} else {
chaine = dico [ code ] ;
result += chaine ;
dico [nbChar] = buffer + chaine.slice (0, 1);
nbChar ++ ;
buffer = chaine ;
}
}
}
return result;
}
Pour créer tes packages en AS1 utilise la fonction écrite par Moock :
if (typeof _global.AsSetupPackage == "undefined") {Utilisation :_global.AsSetupPackage = function (path) {
var a = path.split('.');
var o = _global ;
for (var i = 0; i < a.length; i++) {
var name = a[i];
if (o[name] == undefined) o[name] = new Object( ) ;
o = o[name] ;
}
}
}
#include "com/eka/library/AsSetupPackage.as"
// ---------o import library
AsSetupPackage("com.eka.tools") ;
var p = com.eka.tools ; // p comme package
// ----o constructeur
p.MaClasse = function () {
// mon constructeur
}
// ici contenu de la classe
// ----o Encapsulation
ASSetPropFlags(p.MaClasse.prototype, null, 1);
delete p ;
bye
merci
je cherchais un truc dans le genre
Salut,
au sujet de l'erreur de la version en AS1 qui oublie un ou plusieurs caracteres,
suffi de rajouter un ch'tit ligne de code dans la fonction de compression
result += String.fromCharCode(dico[buffer]);return result;
c'est étrange quand même, que ca chie en AS1
choooiinnggg
Malheureusement, l'algo est bugué. Il ne rend pas les mêmes donnés à tout coup. J'essaie de compresser une serie de chiffres et il ne me retourne pas les mêmes coordonnées à tous les coups. Dommage. Si vous avez une autre solution contactez moi svp.
Quel algo ??
AS1 ou AS2 ? tu peux préciser et montrer ce que tu fais ? 
Je vais à peu prés te fournir la meme réponse que celle que j'ai donné sur mon blog: j'ai fait des test avec des chaines chiffrées et cela fonctionne parfaitement.
Mais bien sur je n'ai testé que mon adaptation AS2 de LZW, et je n'ai jamais eu l'occassion de voir si la version AS1 fonctionne...
Le problème c'est que tous ceux qui nous parlent de bug.. ne montrent pas leur code et ce qu'ils font... du coup on va pas aller très loin là
Pour finir ...
Cette version AS1 fonctionne parfaitement chez moi
http://code.1stfloorlab.com/LZH.htm
en revanche si quelqu'un trouve une implémentation PHP
je suis super preneur A+
clem.
clement > En ayant l'implémentation AS2, la traduction vers PHP devrait pas être trop difficile !
Certainement mais j'ai encore du mal avec les class pour php...
j'essaye
c'est les mêmes... un peu plus lourd avec les this-> mais bon
C'est dingue ce que LZW déchaine les passions

Je suis en train de terminer Huffman, donc suite au prochain épisode
cette algo ne renvois pas les meme valeur si plus de 2 caracteres se succedent ou plus:
222 revois 2
cococo co etc...
an unicode extension
/* ------------------- LZW v 0.0.1Name : LZW
Package : com.eka.compression
Version : 0.0.1
Date : 2004-05-22
Author : ekameleon
URL : <a href="http://www.ekameleon.net" rel="nofollow">http://www.ekameleon.net</a>
Mail : <a href="mailto:contact@ekameleon.net" rel="nofollow">contact@ekameleon.net</a>
DESCRIPTION
La classe LZW (Lempel Ziv Welch) permet de compresser ou de décompresser une chaine de caractère.
Les méthodes sont utilisables sans constructeur.
UTILISATION
import com.eka.compression.LZW ;
var txt:String = "L'intérêt de cette méthode réside dans le fait qu'un indice est transféré sur 12 bits." ;
var c:String = LZW.compress (txt) ; // compression
var d:String = LZW.decompress (c) ; // décompression
trace(txt + "
Taille avant la compression : " + txt.length ) ;
trace ("------- compression") ;
trace (c + "
Taille après la compression : " + c.length ) ;
trace ("------- décompression") ;
trace(d + "
Taille après la décompression : " + d.length ) ;
PUBLIC METHODS
- compress ( str:String)
# paramètre : une chaine de caractère que l'on souhaite compresser.
# renvoi : une chaine de caractère
- decompress ( str:String)
# paramètre : une chaine de caractère compressée avec l'algorithme LZW que l'on souhaite décompresser
# renvoi : une chaine de caractère
REMERCIEMENTS :
shoebox : <a href="http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw" rel="nofollow">http://www.shoe-box.org/blog/index.php/2004/05/05/13-CompressionLzw</a>
lalex : <a href="http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments" rel="nofollow">http://www.lalex.com/blog/comments/200405/164-compression-lzw-actionscript-2.html#comments</a>
------------------------- */
class LZW {
//----o Constructor
static var numToVal = 65000;
private function LZW() {
}
//----o Publics Methodes
public static function compress(str:String):String {
var dictionary:Array = new Array();
for (var i = 0; i<numToVal; i++) {
dictionary[String.fromCharCode(i)] = i;
}
var result:String = "";
var txt2encode:String = str;
var splitStr:Array = txt2encode.split("");
var length:Number = splitStr.length;
var nbChar:Number = numToVal+1;
// Nombres de caractères courant dans le dictionnaire
var buffer:String = "";
// initialisation du tampon buffer
for (var i = 0; i<=length; i++) {
var current = splitStr[i];
if (dictionary[buffer+current] !== undefined) {
buffer += current;
} else {
result += String.fromCharCode(dictionary[buffer]);
dictionary[buffer+current] = nbChar;
nbChar++;
buffer = current;
}
}
return result;
}
//------------------------------
public static function decompress(str:String):String {
var dictionary:Array = new Array();
for (var i = 0; i<numToVal; i++) {
var c:String = String.fromCharCode(i);
dictionary[c] = c;
}
var txt2encode:String = str;
var splitStr:Array = txt2encode.split("");
var length:Number = splitStr.length;
var nbChar:Number = numToVal+1;
// nombre de caractère courant dans le dictionnaire
var buffer:String = "";
// initialisation du tampon mémoire
var chaine:String = "";
// chaine temporaire
var result:String = "";
// chaine retournée à la fin de la décompression
for (var i = 0; i<length; i++) {
var current:String = splitStr[i];
var code:Number = txt2encode.charCodeAt(i);
if (buffer == "") {
buffer = current;
result += current;
} else {
if (code<=numToVal) {
result += current;
chaine = buffer+current;
dictionary[nbChar] = chaine;
nbChar++;
buffer = current;
} else {
chaine = dictionary[code];
result += chaine;
dictionary[nbChar] = buffer+chaine.slice(0, 1);
nbChar++;
buffer = chaine;
}
}
}
return result;
}
}
I don't speak french sorry.
The compress methods on this page don't work when exporting to flash player 6, because variable names are case insensitive. I've included my conversion of the compress method below that works when exported to fp6.
public static function compress_fp6(str:String):String{
var dico:Array = new Array();
for (var i = 0; i < 256; i++)
{
dico[String(i)] = i;
}
var res:String = "";
var txt2encode:String = str;
var splitStr:Array = txt2encode.split("");
var len:Number = splitStr.length;
var nbChar:Number = 257;
var buffer:Array = new Array();
for (var i = 0; i <= len; i++)
{
var current = splitStr[i];
if (buffer.length == 0)
var xstr = String(current.charCodeAt(0));
else
var xstr = buffer.join("-") + "-" + String(current.charCodeAt(0));
if (dico[xstr] !== undefined)
{
buffer.push(current.charCodeAt(0));
}
else
{
res += String.fromCharCode(dico[buffer.join("-")]);
dico[xstr] = nbChar;
nbChar++;
delete buffer;
buffer = new Array();
buffer.push(current.charCodeAt(0));
}
}
return res;
}
I don't speak french either, sorry. If you have multiple same character in a row
(for example www.mydomain.com), the decompress method returns an invalid string.
Any ideas to fix it? It also could work also with flash 6..
Example (exported for Flash 7):
ORGINAL STRING: www.mydomain.com
COMPRESSED: wa.mydomain.cc (chars don't display correcly here)
DECOMPRESSED: wundefined.mydomain.com
Thanks in advance.
Meychi: I've already fixed this.. I will post soon! (no time atm)
http://www.razorberry.com/blog/archives/2004/08/22/lzw-compression-methods-in-as2/
Beau travail
Merci 
Geez, thanks Ash. Great work.
Good work
Boudiou, ce post à complétement "squatté" la découverte de ShoeBox ...
Bravo amis anglophones ! (i.e. Congratulations !)
Bé euh
moi aussi j'avais corrigé ça, il n'a même pas implémenté la limite des 1024 charactères
qui à mérité pas mal d'améliorations 
Enfin voila, je crois que cela ferme ce petit sujet
Prochaine étape, il faut qu'une ame volontaire se devoue pour porter l'algorythme en PHP