Informationswissenschaft - Theorie, Methode und Praxis / Sciences de l'information - théorie, méthode et pratique

— «algorithme» arrive en 2415 èmeposition dans ce dictionnaire;

— «compression» arrive en 10 324 èmeposition;

— «de» arrive en 11 112 èmeposition;

— «dictionnaire» arrive en 12 956 èmeposition;

— «un» arrive en 74 454 èmeposition.

Dans ce cas, la phrase

«L’algorithme de compression LZW utilise un dictionnaire.» peut être codée de la manière suivante:

«L’*2’415*11 112*10 324*LZW*utilise*74 454*12 956*.», car «L’», «LZW», «utilise» et «.» ne se trouvent pas dans le dictionnaire considéré.

Examinons l’efficacité de cet algorithme. La phrase qu’il faut coder est constituée de 56 caractères. En utilisant le code ASCII, on constate que 448 bits sont requis pour coder ce texte. Calculons maintenant le nombre de bits nécessaires lorsque l’on profite du dictionnaire. Comme il faut 17 bits 12pour coder les nombres jusqu’à 100 000, on doit utiliser 18 bits pour coder les mots qui se trouvent dans le dictionnaire. En effet, il faut 1 bit supplémentaire pour indiquer si ce qui suit correspond à un index ou à un mot codé en ASCII. Les mots présents dans le dictionnaire étant au nombre de 5, cela nous donne 90 bits. De plus, les quatre chaînes de caractères codées en ASCII nécessitent respectivement 22,30,62 et 14 bits, puisqu’il faut 1 bit pour indiquer que ce qui suit est codé en ASCII, 5 bits pour indiquer la longueur du code ASCII, puis le code ASCII. On arrive à un total de 218 bits. On constate qu’il a effectivement été possible de compresser efficacement la phrase proposée.

Ci-dessus, c’est un dictionnaire traditionnel qui a été utilisé. Pour augmenter l’efficacité de l’algorithme, les dictionnaires utilisés contiennent en réalité des chaînes de caractères 13qui n’ont pas nécessairement de signification. De plus, la conception à l’avance d’un dictionnaire peut être irréalisable lorsque les données ne sont pas des données textuelles. C’est typiquement le cas des images. Il n’est pas évident qu’il soit possible de trouver des arrangements de couleurs qui reviennent régulièrement dans toutes les images. Pour cette raison, il est nécessaire de définir des algorithmes capables de construire un dictionnaire différent pour chaque image. Pour éviter la transmission du dictionnaire entre le codeur et le décodeur de l’image, il s’agit de le construire selon une procédure permettant au décodeur de reconstruire le dictionnaire au fil du décodage.

Par exemple, le codeur peut démarrer avec un dictionnaire vide ou par défaut (constitué des lettres de l’alphabet par exemple). Ensuite, en cours de codage, le codeur cherche dans le dictionnaire le mot le plus long qui correspond à la chaîne de caractères qu’il doit coder. Supposons que la prochaine chaîne de caractères à coder soit «couleurs» mais que seul le mot «coule» soit déjà présent dans le dictionnaire. Dans ce cas, le codeur code uniquement le début, à savoir «coule», du mot «couleur», et le codeur précise que la lettre suivante est le u. Ensuite il ajoute le mot «couleu» au dictionnaire, et il s’attaque à la prochaine chaîne de caractères à coder. Dans notre cas, il s’agit de «rs» et de ce qui suit. Ainsi, le dictionnaire est en constante évolution, en fonction des redondances qui apparaissent.

Parmi les algorithmes faisant appel à une procédure de ce genre, on trouve les algorithmes précurseurs LZ77 et LZ78, publiés par A. Lempel et J. Ziv en 1977 et 1978 respectivement. Par la suite, une variante de ces algorithmes a été publiée en 1984 par T. Welch. Cet algorithme est connu sous le nom de LZW et est probablement le plus fameux des algorithmes de la famille LZ, qui regroupe les variantes de LZ77 et de LZ78.

Plutôt qu’une efficacité ciblée sur un type de donnée très particulier, les algorithmes de la famille LZ ont tendance à être efficaces sur des données de tout type. Cette caractéristique en fait un algorithme «tout-terrain», très utile lorsqu’il s’agit de compresser différents types de données ensemble. Toutefois, lorsqu’il s’agit de compresser un type de données bien précis, il existe souvent un algorithme plus efficace.

Les méthodes de compression JPEG (pour les images en couleur; compression avec perte), JPEG 2000 (pour les images en couleur, compression sans ou avec perte) et JBIG2 (pour les images noir/blanc, compression sans ou avec perte) font appel à des mathématiques avancées, et ne peuvent donc être résumes dans le cadre du présent article. Ces algorithmes bénéficient de techniques récentes et sont particulièrement efficaces.

Pour certaines utilisations, les couleurs des images ne sont pas très importantes, voire superflues. Ainsi, la fidélité exacte des couleurs est sans valeur pour le lecteur intéressé uniquement par le texte d’un document. Pour ce genre d’usages, il peut même être avantageux de ne pas prendre en compte la couleur et de se contenter d’une numérisation en noir/blanc. Le poids des images numérisées en noir/blanc, nettement inférieur au poids des mêmes images numérisées en couleur, est un atout important. Dans le même genre de cas, l’impression est également une fonction pour laquelle une numérisation sans couleur peut être profitable. Par exemple, cela permet de réduire l’utilisation du toner des imprimantes.

Mais les bibliothèques et les archives peuvent tout à fait être confrontées à des situations dans lesquelles le respect des couleurs originales est important. Cela peut être le cas lorsqu’un utilisateur publie des images de documents. Par exemple, des images peuvent être publiées dans un catalogue d’exposition. Il peut aussi arriver que quelqu’un ait comme projet la création d’un fac-similé qui soit le plus fidèle possible au document original. Et si la numérisation a comme but de créer une copie pouvant remplacer le document original, alors la fidélité de la reproduction est primordiale. En effet, une institution patrimoniale peut estimer que certains originaux sont dans un tel état que la création d’une copie est nécessaire pour assurer la pérennité de l’information. Pour ces situations, il est nécessaire de savoir comment les formats d’images gèrent les couleurs.

Aujourd’hui, de nombreux appareils gèrent des couleurs. Les imprimantes, les écrans, les appareils photographiques et les scanners sont dans ce cas. Dans le but de transmettre fidèlement les couleurs entre ces appareils, différents standards ont été émis par les organismes compétents. En l’occurrence, il s’agit de la Commission Internationale de l’Eclairage (CIE) et de l’International Color Consortium (ICC).

Le concept d’espace de couleurs est important. Un espace de couleurs est une correspondance définie entre un ensemble de couleurs et un ensemble de nombres. Cette correspondance permet de coder les couleurs avec des nombres. Plus précisément, il s’agit de faire correspondre un triple 14de nombres à chaque couleur. Par exemple, l’espace RVB (RGB en anglais) décompose une couleur C en un rouge R, un vert V et un bleu B. A la couleur C est associé le triple (r, v, b) où r est le nombre associé à la couleur R, v est le nombre correspondant à la couleur V et b est le nombre décrivant la couleur B. Concrètement, (255,0,0) correspond au rouge primaire alors que (110,11,20) décrit la couleur grenat. 15Il est toutefois nécessaire d’être très prudent: il existe un grand nombre d’espaces RVB. Parmi les espaces de ce type qui sont souvent utilisés se trouvent sRGB et Adobe RGB (1998).

Cela veut dire qu’un même triple peut très bien correspondre à des couleurs différentes en fonction de l’espace de couleurs considéré. De plus, deux espaces différents ne couvrent pas nécessairement le même gamut. 16Par exemple, l’espace de couleurs sRGB a un gamut plus petit que l’espace Adobe RGB (1998), ce qui veut dire qu’il existe des couleurs que l’on peut décrire dans l’espace Adobe RGB (1998) alors qu’elles ne peuvent pas être décrites par l’espace sRGB.