| ★ CODING ★ DECOMPRESSION DE DONNEES ★ |
| Bidouilles ACPC n°42 - La decompression |
Comme nous l'avions vu dans les dernières bidouilles, la compression de données peut être simple en aperçu. Les choses se gâtent lorsqu'on s'approche un peu du fond du sujet. La réalisation de ce type de programme nécessite un volume prodigieux de matière grise. Encore faut-il ensuite qu'il soit réellement efficace. M'enfin, cette discipline met plus d'un programmeur aux fraises. Nous allons donc essayer de nous approcher plus encore de l'algorithme idéal, histoire de ne pas se mettre dedans au niveau des performances. Attention aux maux de tête...Les quelques documents portant sur la compression de données que j'ai pu compulser sont assez vagues et il n'en est pas deux qui racontent la même histoire. Dans ce cas, il faut faire la part des choses. Je vous propose donc une version qui me semble une des plus efficaces. La dernière fois, nous avons vu que la compression Lempel passait par la création d'un dictionnaire dynamique. Ce dictionnaire était en quelque sorte constitué de sous-chaînes significatives et représentatives du fichier initial. En clair, je te le prends, je te le découpe en petits morceaux auxquels je donne un petit nom, et je n'ai qu'à envoyer les petits noms au lieu des gros paquets de données. Après l'algorithme de compression, voici celui de décompression.
Oh! la belle prise de tête... Cela paraît très simple à programmer vu sous cet angle, mais vous allez vite vous apercevoir que tout n'est pas si simple. En effet, une seule et unique chose n'apparaît pas dans cet algorithme : la place mémoire utilisée par le dictionnaire. Pour chaque caractère reçu, il est simple de calculer que deux caractères sont stockés dans le dictionnaire. Mon Dieu ! que de contraintes lors de la gestion de nos 32 petits Ko de mémoire centrale. Comment faire pour que toutes ces données, ce programme et le reste tienne dans ce si petit carré libre ? Là encore, des dieux de la programmation ont frappé ! LA CHAINE AFIN Les inventeurs de cette technique de compression ont analysé la progression des caractères et se sont aperçu que toutes les chaînes générées ont en fait la même base, En clair, les phrases à stocker sont souvent construites à partir d'une phrase préalablement connue. Simple alors de dresser des maillons pointant sur le caractères précédents de la chaîne, ceci jusqu'au premier. En fait, de la place est perdue par caractère car ce stockage implique la perte d'un octet pour la valeur Ascii plus un mot pour l'adresse du caractère précédent, Cela dit, si une même chaîne de base longue de 30 signes est répétée 50 fois, cela fait d'autant plus de mémoire occupée. Si on perd de la place au départ, on finit par en gagner plus qu'on en espérait. Mais voilà, ce type de stockage, s'il est plus qu'économe en mémoire, se révèle d'une lenteur insupportable lors des traitements, imaginez les galipettes qu'il faut opérer pour reconstituer une chaîne qui sera en fin de compte inutilisable, ne correspondant pas à celle à compresser. Pour la décompression, ce type de problème ne gène pas, puisqu'il suffit d'accéder aux données selon un ordre prescrit. En revanche, pour l'opération inverse, toutes les chaînes doivent être passées en revue, ceci 'pour coder le mieux possible la phrase en cours de traitement, Qu'est-ce qu'on teste, qu'est-ce que ça bosse, qu'est-ce qu'on attend, qu'est-ce qu'on se fait ch... Pour ceux qui n'ont pas envie de développer le programme, cette étape est suffisante. Je vous promets de longues siestes derrière le CPC mais cela fonctionnera (si vous avez la patience d'attendre et si l'alimentation du moniteur ne fond pas entre-temps). Cette solution est donc juste bonne à vérifier l'algorithme, mais pas utilisable tous les jours. C'est ici que les génies de l'informatique ont encore frappé (Aïe!). LES STOCKAGES Pour faire fort, ils ont fait fort. Ce n'est pas si simple de trouver des astuces permettant d'accélérer de manière réelle des algorithmes de recherche. Surtout lorsqu'il s'agit de chaînes de caractères. Reprenons en Cœur les différents types de recherches existantes, avec quelques méthodes de gestion des données. La dichotomie : c'est l'art de gérer un tableau de chaînes triées, Simple d'utilisation, puisqu'il suffit de taper au milieu du tableau et de comparer. Si on est trop grand, on est trop haut, dans le cas contraire on est trop bas. Il suffit donc de scanner dans la partie qui nous intéresse, de l'attaquer par le milieu, de comparer et de recommencer jusqu'à ce que la taille de la partie à comparer soit de 1. Si on est égal à cet objet, on dit trouvé, sinon, perdu ! Le nombre de comparaisons est alors supercompressé, car il équivaut à l'inverse de la puissance de deux de la taille initiale. Pour être concret, un tableau de 256 octets sera parcouru en huit tests. Qu'en dites-vous ? Les tableaux simples : ils impliquent le rangement des éléments de manière linéaire et séquentielle. Cela prend de la place et, pour chaque insertion ou chaque destruction, tout le tableau à réorganiser ! Que de déplacements mémoires pour tenir ce type d'engin à jour. De plus, une chaîne de deux caractères prendra autant de place qu'une de la taille maximale prévue. A rejeter à tout prix, trop gourmand en mémoire. Les tableaux codés ; ils rangent toujours les éléments de manière séquentielle mais codent leur longueur. Pas de place de perdue, mais, malheureusement, perte du bénéfice de l'accès direct aux informations. A rejeter itou. Les tableaux d'index sont encore la meilleure technique envisageable à ce jour si on ne veut pas trop s'embêter. Elle consiste à stocker les chaînes de caractères sous forme de tableaux codés, et des pointeurs sur celles-ci par la méthode simple. Facile ainsi d'intercaler un index ou pointeur codé sur un mot et d'aligner les chaînes de caractères au bon plaisir de leurs arrivées. Le tableau est facile à trier, facile à compulser et tout aussi facile à utiliser avec la méthode dichotomique, Pour tout élément à trouver, il suffit de prendre son index à la position connue dans le tableau, d'aller chercher la chaîne à utiliser à l'adresse pointée et de continuer si besoin est. Petite perte de temps machine pour un joli gain de mémoire. Les programmeurs fous se sont là, encore lancé, des définis insensés. Hé ! con, pourquoi faire deux recherches dans un tableau alors qu'une seule pourrait suffire ? 100 GRAMMES DE HAS-CODING ? Le problème des tableaux linéaires, c'est qu'ils ont besoin d'indices, mais les indices ne sont pas représentatifs des variables sur lesquelles ils pointent... et là est tout le secret. Il suffisait de se dire cela pour inventer le Hascoding. Pour ranger une chaîne dans un tableau (ou plutôt son pointeur car c'est plus efficace) il faut déterminer un indice. Au lieu de fixer celui-ci par une bête insertion par ordre alphabétique, pratique mais lour-dingue, il suffit de le générer en fonction de la chaîne traitée. Une moulinet-te travaillant sur tout les caractères de la chaîne peut générer un indice unique directement et parfaitement représentatif de la phrase. A priori, même deux phrases différentes engendreront deux indices tout aussi différents par le biais de la moulinette. Essayez cela avec de simples additions et décalages et vous vous apercevrez que cela n'est pas si bête. Malheureusement, et comme partout, une chose bien ne vient pas seule. Voici les contraintes d'utilisation. Pour ne pas que deux chaînes très ou peu différentes utilisent la même clef, il faut une moulinette relativement scabreuse. Ne vous méprenez pas, il existe des techniques palliatives dans le cas ou des doublons se glisseraient tout de même dans cet algorithme. La taille du tableau doit être la plus grande possible pour ne pas que le tableau puisse être totalement plein, ce qui ruinerait son exploitation. Et enfin et plus grave, lors de la gestion de doublons, il n'est pas possible de supprimer un élément du tableau sans risquer de perdre des données si chères. A TES SOUHAITS Maintenant que nous disposons de tous les éléments cruciaux, nous pouvons attaquer de plein fouet la structuration et la programmation de notre compresseur-décompresseur. Comment va ta sœur de données ? Malheureusement, la place vient à me manquer et la suite sera si belle que vous n'en croirez pas vos yeux... la prochaine fois. Ach, Sined, ACPC n°42
|
