Overblog Suivre ce blog
Administration Créer mon blog
16 octobre 2010 6 16 /10 /octobre /2010 14:06

 

J'ai brièvement expliqué dans mon précédent billet l'intérêt des rvalue references de C++11 et nous avons pu voir que les améliorations de performances dans les programmes génériques justifiaient amplement leur inclusion dans la nouvelle norme. Néanmoins, je tiens à rappeler que cet ajout se fera aux dépens d'une complexité accrue du langage. Le programmeur débutant devra maitriser les concepts de déplacement et de copie, ainsi que les temporaires anonymes, avant de pouvoir tirer avantage de cette fonctionnalité.

Le langage D se voulant être un C++ plus simple, il se devait de résoudre ce problème de manière plus élégante.

Classes et structures

 

Premier constat, une classe D n'a pas grand-chose en commun avec son homologue C++. D a choisi la même approche que C#, en séparant clairement les structures et les classes, alors que ces deux types correspondent plus ou moins à la même chose en C++.

En D, une classe est toujours instanciée sur le tas, au moyen de l'opérateur new et est toujours manipulée par référence. De cette manière, aucune copie accidentelle d'objet classe n'aura lieu tant que le programmeur l'aura expressément demandé (appel à une méthode clone, par exemple). Il n'est pas possible de surcharger l'opérateur d'affectation pour les classes.

 

Mais D propose aussi un type structure, qui est proche des structures/classes C++ et se manipule aussi par valeur ; avec quelques différences cependant. Les structures D ont notamment une contrainte supplémentaire : elles doivent être déplaçables. C'est-à-dire que l'état de l'objet doit être indépendant de sa position en mémoire. En pratique, cela signifie qu'une structure ne peut contenir de pointeur vers ses propres membres. Le code suivant est donc incorrect en D :

 struct S
{
private:
int i;
int* pi;

public:
this(int value)
{
i = value;
pi = &i;
}
}

 

En pratique, cela ne pose pas de problème, car cette technique n'est jamais indispensable. Le fait d'avoir des objets déplaçables présente des avantages d'optimisation pour le compilateur ou l'environnement d'exécution, comme le ramasse-miettes.

Le constructeur postblit

 

Contrairement au langage C++, le langage D ne propose pas de constructeur de copie pour les structures. Le constructeur de copie est un mécanisme du C++ dans lequel une méthode spécifique est appelée lorsqu'un objet doit être copié. Si le programmeur ne définit par de constructeur de copie, le compilateur C++ en générera un automatiquement. Le constructeur de copie généré se bornera à faire une copie brute (memcpy) des données de l'objet. Cela peut suffire pour les types simples (appelés POD, pour Plain Old Data), mais est clairement insuffisant pour un objet complexe, possédant des pointeurs vers des données externes. C'est précisément la raison pour laquelle C++ permet au programmeur d'écrire son propre constructeur de copie.

 

Comme je l'ai dit, le langage D ne propose pas de constructeur de copie. En D, toutes les copies de structures seront toujours assurées par le langage, qui fera toujours un memcpy des données de la structure. Comme cette technique est insuffisante pour les types complexes, D propose un autre mécanisme appelé le constructeur postblit. C'est en fait une méthode optionnelle qui sera appelée après une copie de structure. J'insiste bien sur le fait que ce n'est pas un constructeur de copie car il ne remplace pas le mécanisme de copie de la structure, il est appelé après la copie brute des champs de la structure.

Dans un constructeur postblit, le programmeur insèrera généralement du code qui dupliquera les objets manipulés par référence. On a donc une copie en deux étapes :

  • Le langage copie la source via memcpy, la copie possède des champs qui pointent vers les mêmes données que la source.

  • Le constructeur postblit duplique les données références.

 struct T
{
private:
int[] pi;
public:
/// Constructeur
this(size_t n)
{
pi = new int[n];
}

/// Constructeur postblit
this(this)
{
// duplique le tableau pointe par pi
pi = pi.dup;
}
}

Pourquoi un constructeur postblit ?

 

À ce stade-là, vous vous demanderez peut-être quel peut être l'intérêt du postblit constructeur par rapport à ce bon vieux constructeur de copie C++. C'est simple. Avec la contrainte que les objets doivent être déplaçables, une copie d'objets devient strictement équivalente à un déplacement + un appel à un hook défini par l'utilisateur (ici le postblit). Bon d'accord, le ramasse-miettes simplifie aussi un peu les choses.

Lorsque le compilateur détecte qu'il peut remplacer une copie par un déplacement, il est libre de ne pas insérer d'appel au constructeur postblit. En somme, D remplace la définition de 2 constructeurs (copie et déplacement) par la définition d'une seule méthode (postblit) qui ne sera pas appelée s'il n'y en a pas besoin.

Repost 0
Published by Olivier - dans Programmation
commenter cet article
14 octobre 2010 4 14 /10 /octobre /2010 17:20

Déplacement contre copie

La nouvelle norme du langage C++ introduit une nouveauté de taille, les rvalue references, destinées à réduire le nombre de copies d'objets en privilégiant le déplacement d'un objet plutôt que sa copie lorsque cela est possible. Une rvalue reference est une référence vers un objet anonyme temporaire et s'écrit au moyen de deux symboles & au lieu d'un seul.

En gros, la forme canonique d'une classe T en C++ 11 ressemblera à ça :

 class T
{
int* pi;
public:
T() : pi(new int[100000]) { }
~T() { delete[] pi; }

// Sémantique de copie
T(const T& t) : pi(new int[100000]) { memcpy(pi, t.pi,
100000 * sizeof(int)); }
T& operator=(const T& t) {memcpy(pi, t.pi, 100000 * sizeof(int));}

// Sémantique de déplacement
T(T&& t) : pi(t.pi) {t.pi = nullptr; }
T& operator=(T&& t) {std::swap(pi, t.pi); return *this; }
};

 

Avec en dernier, les deux nouvelles méthodes à implémenter, destinées à être utilisées lorsque l'objet sera déplacé plutôt que copié. On peut noter que le paramètre de ces méthodes n'est pas constant, puisque celui-ci est destiné à être invalidé par le déplacement.

 

Le constructeur de déplacement sera utilisé par le compilateur lorsqu'on affectera un temporaire anonyme, par exemple avec le code suivant :

 

 T creerGrosObjet()
{
T obj1;
return obj1;
}

int main(int argc, char** argv)
{
T obj2 = creerGrosObjet(); // On ne copie pas, on déplace.
return 0;
}

 

 

Dans cet exemple, un compilateur C++ 11 détectera que l'objet affecté à la variable obj2 est un temporaire destiné à être détruit immédiatement et fera donc appel au constructeur de déplacement pour que ob2.pi pointe sur les mêmes données que obj1.pi (qui lui se verra affecter null, sans cela, l'appel au destructeur de obj1 aurait de fâcheuses conséquences).

Comme un petit dessin vaut mieux qu'un long discours, voici une illustration destinée à mettre en évidence la différence entre un déplacement et une copie d'objets.

:

 

  copyvsmove

 

Pour plus d'informations sur les rvalue references, vous pouvez vous référer à http://www.artima.com/cppsource/rvalue.html

Premier benchmark

 

Un premier benchmark de la STL tirant parti de cette optimisation a été posté sur le net et le résultat est plutôt sympathique puisqu'on a presque un facteur 14 de performances entre le test utilisant la copie et celui utilisant le déplacement.

 

http://cpp-next.com/archive/2010/10/howards-stl-move-semantics-benchmark/

 

On peut donc s'attendre à avoir un gain appréciable de performances des programmes C++, dès lors que le commun des mortels aura compris comment les rvalue references fonctionnent.

Car c'est bien là le coeur du problème : les rvalues references viennent complexifier un langage qui n'en avait pas vraiment besoin.

Repost 0
Published by Olivier - dans Programmation
commenter cet article
5 octobre 2010 2 05 /10 /octobre /2010 16:06

 

As my relatives may know, I am fond of Digital Mars D programming language. It allies both C++ power and modern languages ease of use, like Java or C#.

When you read a criticism of the D programming language, one of the flaws that come the most often is related to the toolchain. OPTLINK, the Windows linker comes to my mind immediately (thank God DMD UNIX version use the GCC linker instead of this one). But the most problematic issue is certainly the lack of a good IDE. 

Of course, a lot of good text editors do have a D mode by now, but you often still have to compile and debug your application in a seperate terminal window. If GDB last version now supports D, there was a long way to a integration in a good IDE.

Rainer Schuetze may be our messiah, having written a Visual Studio plugin called, you had guessed it, Visual D.

 

 

screenshot

 

Let's have a look how to install it correctly on Windows.

 

 

First step, download the compiler.

 

Visual D do not provies a D compiler by itself, it only launches it and communicates with it. So you have to download the official Digital Mars compiler, DMD. Last version is 2.049 by now. It comes as a zip archive that you just have to decompress in a folder. For the need of this article, I have chosen the C:\dmd2 folder.

 

 

Second step, Visual Studio

 

If you are the happy owner of a non Express Visual Studio version, please make sure it is installed correctly and skip the following lines.

If Visual Studio Express versions are free of charge, they do not include plugin support, so you cannot use them to host the Visual D plugin. You have to download and install something called Visual Studio 2010 Shell instead. It is in fact the Visual Studio standard edition IDE, without any language support. It is not meant to be used directly, but as a plugin platform. We are going to use it as a Visual D host. It is provided by Microsoft for free. Once you have downloaded and installed it, you can go to the next section.

 

Visual, at last

 

Now download and install Visual D. At the time these lines are written, version 0.3.17 has just came out of the bake. This is the version I use.

If you have several Visual Studio versions installed on your computer, be sure to choose the 2010 version during the installation process. When you will be asked to, indicate the folder where you had DMD unzipped at step one (c:\dmd2 if you did the way I did).

Now you can start Visual Studio 2010 from your Start menu. If everything went right, you will  see D project templates on the "File / new project "dialog. Just try to create a "hello world"  console application to ensure you installation is correct.

 

projects

Don't worry about this ".Net Framework 4" thiing on the top of the screen, DMD will only generate 100% native code !

Cannot add symbols to module, probably msobj100.dll missing

 

Whenever I was trying to compile and run an application in the IDE, I got this error message. It seems that the missing msobj100.dll file is not provided by Visual Studio 2010 Shell. Fortunately, it comes with Visual C++ 2010. I was able to resolve the issue by downloading and installing Visual C++ 2010 Express and now everything works correctly for me. 

Repost 0
Published by Olivier - dans Programmation
commenter cet article
4 octobre 2010 1 04 /10 /octobre /2010 17:15

 

Ceux qui me connaissent le savent bien, je suis un adepte du langage D de Digital Mars. Ce langage a le mérite d'allier la puissance du C++ à la facilité d'utilisation d'un langage plus moderne tels Java ou C#.

Un des gros points noirs qui est souvent cité lorsqu'on élabore une critique du langage est la faiblesse des utilitaires officiels. Je pense bien évidement à OPTLINK, l'éditeur de liens sous Windows (les versions UNIX de DMD ont la chance d'utiliser celui de GCC), mais aussi et surtout au manque d'environnement de développement intégré. Certes de nombreux éditeurs de texte possèdent un mode D, mais il faut encore souvent se payer la compilation et le débogage de son application dans un terminal séparé. Si GDB supporte maintenant officiellement le langage, il restait encore pas mal de chemin vers une intégration à un IDE.

La lumière vient de nous être apportée par Rainer Schuetze et son plugin pour Visual Studio, logiquement nommé Visual D.

 

screenshot

 

Nous allons voir comment installer cet environnement de développement gratuit sous Windows.

 

 

Première étape, Télécharger le compilateur.

 

Visual D ne contient pas en lui même le compilateur D. Il ne fait que l'appeler et communiquer avec lui. Vous devez donc télécharger le compilateur officiel de Digital Mars, DMD. À l'heure où j'écris ces lignes, il est en version 2.049. Téléchargez donc l'archive contenant le compilateur et décompressez-le. J'ai pour ma part opté pour le dossier C:\dmd2.

 

Deuxième étape, Visual Studio

 

Si vous êtes l'heureux propriétaire d'une version payante de Visual D, assurez-vous de l'avoir bien installée et passez au prochain paragraphe.Sinon, lisez la suite.

Les versions Express de Visual Studio ont beau être gratuites, elles ne supportent pas l'installation de plugins et vous ne pouvez donc pas les utiliser comme hôte pour Visual D. Vous devez donc télécharger et installer le Visual Studio 2010 Shell, lui aussi disponible gratuitement. Le Shell correspond à l'IDE version standard, dépouillé de tout support de langage. On ne peut donc pas s'en servir directement. C'est juste une plateforme à plugins. Nous allons l'utiliser comme hôte pour Visual D.

 

Enfin, Visual D

 

Téléchargez maintenant Visual D. Au moment où j'écris ces lignes, la version 0.3.17 vient tout juste de sortir (c'est celle que j'utilise). Si vous avez plusieurs versions de Visual Studio, choisissez d'installer Visual D dans Visual Studio 2010. Indiquez-lui en outre le répertoire racine de l'installation de DMD (dans mon cas, C:\dmd2).

Vous pouvez lancer Visual Studio depuis le menu démarrer. Si Visual D est correctement installé, vous aurez alors des modèles de projets D dans la liste de nouveaux projets. Créez une application console et vérifiez qu'elle s'exécute bien.

 

projects

Ne prêtez pas attention à la mention .Net Framework 4 en haut de l'écran. DMD ne va générer que du code natif !

Cannot add symbols to module, probably msobj100.dll missing

 

J'avais cette erreur qui m'empêchait d'exécuter ou de déboguer toute application au sein de l'environnement de développement. En effet la version gratuite du Shell ne fournit pas cette bibliothèque. Elle est cependant fournie par Visual C++. J'ai résolu ce problème en installant la version Express de Visual C++.

Repost 0
Published by Olivier - dans Programmation
commenter cet article
3 octobre 2010 7 03 /10 /octobre /2010 13:31

Voici billet plutôt court pour signaler la sortie de ComiqueBouc en version 1.1.



ComiqueBouc est — comme son nom peut l'indiquer pour un francophone ayant quelques notions de la langue de Shakespeare et un bon coup dans le nez — un lecteur de bandes dessinées numériques.

Cette version est la première publiée officiellement sur Internet, sous licence GPL. C'est avec une certaine satisfaction personnelle que je franchis le cap en publiant à la fois ses sources et des binaires prêts à l'emploi.

Pourquoi ce projet ?

Je suis un utilisateur convaincu de CDisplay sous Windows depuis plusieurs années. Malheureusement, le développement de ce dernier semble s'être arrêté depuis quelque temps et il lui manque certaines fonctionnalités modernes. Il n'est par exemple pas possible d'ouvrir des documents compressés avec l'algorithme de 7zip. J'ai donc pris sur moi de développer rapidement un équivalent à CDisplay qui serait en mesure de répondre à ce besoin.

Prérequis

Un système Windows moderne avec .net version 3.5 ou supérieur installé. C'est la version livrée de base avec Windows 7. Je suppose qu'il doit être possible de l'exécuter également avec Mono, mais je n'ai pas essayé.

Pour le développement, les sources contiennent un projet Visual C# 2010 prêt à l'emploi. Deux DLLs supplémentaires (livrées dans les binaires) sont en outre nécessaires exécuter le projet.

Nouveautés

Cette version apporte l'affichage/navigation par aperçus de vignettes. On peut sélectionner une page et l'atteindre en double-cliquant sur la vignette correspondante. Comme une illustration vaut mieux qu'un long discours, voici une capture d'écran illustrant cette fonctionnalité.


screenshot-cb-1.1

Téléchargement

Vous pouvez télécharger ComiqueBouc et/ou ses sources sur la page SourceForge du projet.

Repost 0
Published by Olivier - dans Projets personnels
commenter cet article
27 septembre 2010 1 27 /09 /septembre /2010 13:00

Bonjour à tous,

 

Voici un petit article d'introduction à la programmation d'applications sur iPhone/iPod Touch/iPad. Si vous avez des notions de programmation sur les plateformes Mac ou NextStep, vous verrez que cela n'est pas très différent. Question équipement, vous aurez besoin d'un Mac sous OS X 10.5 minimum.Vous aurez besoin d'avoir installé les outils de développement présents sur le DVD d'installation de Mac OS et le SDK iPhone/iPad disponible sur http://developer.apple.com

 

Niveau connaissances, des notions de programmation orientée objet sont indispensables. Il faut connaître le motif de conception MVC (Modèle Vue Contrôleur), qui est très utilsé par Cocoa. Connaître Objective C, ou au moins Java est très utile.

Création d'un nouveau projet

Ouvrez XCode, choisissez de créer un nouveau projet. Dans l'assistant de nouveau projet, choisissez une cible "iPhone OS Application", et "View-based Application" dans la liste de gauche :

 

helloworld1

 

Choisissez un nom pour le projet (ici, j'ai mis HelloWord). L'assistant vous crée toute une liste de fichiers nécessaires à votre application :

 

helloworld2

 

Quelques remarques sur les fichiers importants :

  • La classe HelloWorldAppDelegate est le délégué à la classe NSApplication. Elle contient les méthodes de spécialisation de la logique de votre application.Contrairement à Java, on dérive très peu avec Objective-C et Cocoa, on délègue.
  • La classe HelloWorldViewController est le contrôleur lié à la fenêtre principale de votre application. C'est dans celle-ci que vous gérerez les évènements lié à l'interface.
  • Le fichier HelloWorldViewController.xib est un fichier Interface Builder, l'application qui permet de gérer l'interface de votre application de manière graphique.

Gestion de l'interface graphique

Notre interface sera constituée d'une vue unique avec un bouton. Lors du clic sur celui-ci, le message "Hello, World" s'affichera sur l'écran. Ouvrez le fichier HelloWorldViewController.h, il contient l'interface du contrôleur de notre vue. Nous avons besoin de la personnaliser afin qu'elle référence un champ texte (label) et ajouter la méthode d'évènement du clic sur le bouton. Complétez la classe de cette manière :

 

helloworld3

 

IBOutlet et IBAction sont utilisés par Interface Builder pour reconnaître des types qu'il doit prendre en compte. IBOutlet désigne un élément de l'interface (bouton, champ texte, liste, etc.) et IBAction un gestionnaire d'évenement. Une IBAction prend toujours un paramètre sender de type id, qui est un pointeur vers l'objet à l'origine de l'évenement. En pratique IBOutlet est une macro préprocesseur vide et IBAction un typedef vers void.

 

Dans le fichier HelloWorldViewController.m, nous allons rajouter l'implémentation de la méthode onButtonClick :

 

helloworld4

 

Rien de bien compliqué, on envoie le message setText à l'objet pointé par lblHello, afin de lui faire afficher la phrase "Hello, world". N'oubliez pas l'arobase devant les guillemets, celà indique que la chaîne est un objet NSString codé en UTF-16, plutôt qu'un tableau de caractères terminé par un 0, comme en C.

 

Personnalisation de l'interface graphique

Double-cliquez maintenant sur le fichier HelloWorldViewController.xib. Cela va lancer Interface Builder, l'application dédiée à la création d'interfaces. Le fichier contient trois objets : Une référence vers le contrôleur que nous venons de modifier sous l'appellation "File's Owner", une autre référence (inutile dans notre cas) et une vue (la fenêtre de notre application) :

 

helloworld5

 

Ouvrez la vue, et glissez-déposez un label et un bouton sur votre vue. J'ai mis "Say hello" comme titre de mon bouton :

 

helloworld6

 

Selectionnez maintenant l'objet "File's owner". Maintenez le bouton Ctrl : le curseur de votre souris vous permet de tracer une ligne. Cela permet d'indiquer les objets vers lequels les pointeurs à l'intérieur de votre contrôleur vont pointer. Reliez le "File's owner" au label : une bulle s'ouvre, listant tous les pointeurs vers des UILabel de votre contrôleur. Il n'y en a qu'un seul : le champ lblHello. Selectionnez-le. À l'exécution, le champ lblHello pointera alors vers le label à l'intérieur de la vue.

 

helloworld7

 

Maintenant recommencez l'opération, en partant du bouton et en le reliant à votre File's owner. Cette fois, vous avez le choix de la méthodé à déclencher lors du clic sur le bouton. Sélectionnez la méthode onButtonClick.Cette méthode sera maintenant déclenchée lors du clic sur le bouton.

 

helloworld8

 

Selectionnez à nouveau le UILabel et effacez son texte, afin qu'il ne soit pas visible au démarrage de l'application. Sauvegardez le fichier .xib via le menu File/Save. Vous pouvez maintenant quitter Interface Builder et revenir à la fenêtre XCode. Cliquez sur le bouton "Build and Run" en haut de la fenêtre de votre projet. Vous verrez alors votre application se lancer dans le simulateur iPhone :

 

helloworld9

 

Conclusion

Nous avons vu aujourd'hui les bases de la programmation d'applications sur iPhone/iPod Touch/iPad. Vous avez appris à créer un projet, vous avez vu les composants de base d'une application : la vue et le contrôleur. Vous avez appris à écrire des gestionnaires d'évènements et à lier des éléments d'interface à votre code afin de les manipuler depuis celui-ci. Vous pouvez maintenant vous entraîner à rajouter des contrôles et autres éléments d'interface et à réagir à leur évènements.

 

Merci de votre attention.

Repost 0
Published by Olivier - dans Programmation
commenter cet article
26 septembre 2010 7 26 /09 /septembre /2010 16:45

 

Bonjour à tous,

Nous avons vu l'autre jour que l'algorithme LZW était très simple à implémenter en Python : une quinzaine de lignes suffit pour coder la fonction de compression et la décompression n'est pas plus longue. Pour autant, nous nous sommes arrêtés à produire un tableau d'entiers de 32 bits en sortie de notre fonction de compression. Il s'agit maintenant de stocker ces entiers de manière à ce qu'ils tiennent le moins de place possible en mémoire.

Nous allons utiliser un codage très simple. L'algorithme LZW utilise un compteur qui s'incrémente pour identifier les combinaisons d'octets rencontrées. C'est la variable n des fonctions compress et uncompress. Cette valeur ne fait qu'augmenter au fur et à mesure. Les premiers nombres, de 256 à 511, ne nécessitent que 9 bits pour être représentés. Une fois qu'on aura dépassé cette limite, les nombres de 512 à 1023 nécessiteront 10bits, et ainsi de suite. On commence à 8 bits et chaque fois que l'on franchit une nouvelle limite, on double la quantité de nombres représentables en ajoutant un bit.

 

Codage

Nous allons coder n'importe quel nombre N par la valeur N+1. Ainsi, on s'assure qu'on ne pourra jamais rencontrer la valeur 0 dans la séquence codée. Le zéro sera utilisé pour signifier que l'on ajoute un bit supplémentaire pour représenter les nombres suivants. C'est ce que fait la fonction « pack » :

 def pack(seq):
nbits = 8 # nombre de bits par nombre
bits = array.array('B') # tableau de bits
output = array.array('B') # sortie codée

# convertit les entiers en liste de 0 ou 1
for n in seq:
if n+1 > 2**nbits-1: # si on dépasse la limite
b = _int_to_bits(0, nbits) # ajoute 0
bits.extend(b)
nbits += 1 # on utilise un bit de plus
b = _int_to_bits(n+1, nbits) # ajoute n+1
bits.extend(b)

# allonge la séquence sur un multiple de 8
while len(bits) % 8:
bits.append(0)

# code les bits 8 par 8 dans des octets.
index = 0
size = len(bits)
while index < size:
byte = _int_from_bits(bits[index:index+8])
output.append(byte)
index += 8
return output



Entiers et séquences de bits

La fonction pack fait appel à deux fonctions utilitaires pour convertir des nombres en suites de bits et vice et versa. Voici leur codes. Tout d'abord la fonction « _int_to_bits » :

 def _int_to_bits(num, nbits):
output = array.array('B')
for bit_index in range(nbits-1, -1, -1):
mask = 1 << bit_index
if num & mask:
output.append(1)
else:
output.append(0)
return output

 

Le paramètre « num » indique le nombre à convertir, le paramètre « nbits » est le nombre de bits à utiliser en sortie. La fonction inverse, ne prend qu'un seul paramètre, une séquence de bits dont on connait nécessairement la taille :

 def _int_from_bits(seq):
output = 0
nbits = len(seq)
for bit_index in range(nbits):
if seq[(nbits-1) - bit_index] == 1:
output |= 1 << bit_index
return output

 

Décodage

La fonction de décodage n'est pas plus compliquée que la fonction de codage :

 def unpack(seq):
bits = array.array('B')
output = [] # sortie décodée

# convertir les octets en suite de bits
for n in seq:
b = _int_to_bits(n, 8)
bits.extend(b)

index = 0
nbits = 8 # nombre de bits par nombre
size = len(bits)

# convertir les bits en entiers
while index < size:
limit = min(index+nbits, size)
i = _int_from_bits(bits[index:limit]) # bits -> nombre
if i == 0:
nbits += 1 # code les nombres sur un bit de plus
else:
output.append(i-1) # N -> N-1
index += limit-index
return output

Utilisation 

Pour tester le résultat de notre petite séance de codage, je vais utiliser le fameux faux texte latin Lorem ipsum  dans sa version populaire. Le tout se passe dans un shell Python interactif :

 >>> import lzw
>>> s = "Lorem ipsum [...] amet." # Je vous épargne les détails
>>> len(s)
2054 # la taille de la chaine non compressée
>>> sc = lzw.pack(lzw.compress(s)) # compresse et code le texte dans sc
>>> len(sc)
1197 # La version compressée par LZW tient presque deux fois moins de place :)
>>> s2 = lzw.uncompress(lzw.unpack(sc)) # décompression
>>> s2 == s
True # La preuve que tout marche bien ! Ouf !

Voilà nous avons fait le tour de l'algorithme, il est assez simple et fonctionne remarquablement bien sur du texte. J'ai testé celui-ci avec Python 2.6.5 sur Linux, mais il devrait marcher sans trop de modifications avec Python 3.

Merci de votre attention !

Repost 0
Published by Olivier - dans Programmation
commenter cet article
24 septembre 2010 5 24 /09 /septembre /2010 13:26

Bonjour à tous,

Dans le cadre de ce blog, j'inaugure une section programmation. Je vais parler aujourd'hui de l'algorithme de compression de données LZW. C'est un algorithme très simple, ce qui me permettra de toucher un large public. La compression de données, tout le monde a une idée de ce à quoi ça sert : réduire la place occupée par des données. LZW est un algorithme de compression non destructeur, c'est-à-dire que les données compressées puis décompressées sont strictement identiques à l'original. Compresser avec LZW « n'abime pas » les données (contrairement au JPEG pour les images, ou au MP3 pour l'audio, par exemple). Cet algorithme est très célèbre, car il est au coeur du format d'image GIF, qui a secoué le web au début des années 2000. La société qui possédait le brevet sur cet algorithme s'est mise à menacer tous les éditeurs de navigateurs et de logiciels d'édition d'images pour non-paiement de royalties. C'est d'ailleurs ce qui a poussé à l'élaboration du format d'image PNG, qui est plus riche en fonctionnalités que le GIF et qui n'utilise pas LZW. Depuis 2004, ce brevet est tombé dans le domaine public, on peut donc utiliser LZW sans souci partout dans le monde.

 

Je ne vais pas détailler ici l'algorithme complet, la page Wikipédia qui y est consacrée serait de toute manière bien plus pédagogique que ma modeste prose. Je vais me contenter de fournir une implémentation de l'algorithme en Python en respectant les noms et les conventions qui sont utilisés sur Wikipédia. Ça permettra au lecteur de faire la correspondance entre le code et la description de l'algorithme plus facilement. Le choix d'un langage de haut niveau comme Python facilite la traduction de certaines opérations comme « ajouter au dictionnaire », puisque le langage possède un type dictionnaire intégré.

 

Compression

Voyons tout d'abord la compression des données. C'est le propos de la fonction « compress » :

 def compress(data):

dic = dict([[chr(i), i] for i in range(256)]) #Crée le dictionnaire initial

output = array.array('I') #liste de nombres en sortie

n = 256 #code de la prochaine combinaison

w = ""

for c in data:

wc = w + c

if wc in dic:

w = wc

else:

dic[wc] = n

n += 1

output.append(dic[w])

w = c

output.append(dic[w])

return output

 

C'est tout ? Oui. Le terrible algorithme qui a fait trembler le web au début des années 2000 peut être implémenté en 15 lignes de Python... Je vous laisse juges de savoir s'il était utile de faire tout un pataquès pour si peu. En tout cas, il est pratique, car il est suffisamment simple et concis pour être abordé dans le cadre d'un blog. :) Magie du typage dynamique, le paramètre data peut être une chaîne de caractères 8 bits, un objet array ou une liste d'octets. Pour des raisons d'efficacité mémoire, je préfère renvoyer un array plutôt qu'une liste. Voyons maintenant la décompression...

Décompression

Sans surprise, la décompression est tout aussi simple :

 def uncompress(data):

dic = dict([i, chr(i)] for i in range(256))

output = [dic[data[0]]]

n = 256

w = data[0]

for c in data[1:]:

try:

entry = dic[c]

except KeyError:

entry = dic[w]

entry += entry[0]

output.append(entry)

dic[n] = dic[w] + entry[0]

n += 1

w = c

return "".join(output)

 

Conclusion

L'implémentation présentée ici n'est pas complète. En effet je me suis intéressé ici à l'implémentation théorique de l'algorithme, qui renvoie comme résultat une liste d'entiers. Chacun de ces entiers va prendre une place fixe non optimale en mémoire (généralement 32 bits). Or un nombre comme 260 (par exemple) n'a besoin que de 9 bits pour être exprimé. La prochaine étape consistera donc à réduire leur volume en utilisant un codage à nombre de bits variable. Ce sera le sujet d'un prochain billet. Je proposerai alors le code source complet (et directement utilisable) de mon module LZW.

Merci de votre attention.

 

Repost 0
Published by Olivier Pisano - dans Programmation
commenter cet article

Présentation

Recherche

Liens