Binary Ordered Compression for Unicode

Le BOCU-1 est un schéma de transformation du texte, compatible avec le répertoire universel d’Unicode et ISO/CEI 10646, en séquences d’octets. Il tire son nom de l’acronyme anglais de Binary Ordered Compression for Unicode (« compression ordonnée binairement pour Unicode »), qui décrit une méthode brevetée de codage plus générale, et dont BOCU-1 est une des variantes possibles ; cette variante est standardisée de façon très stricte (de façon bien plus limitative que la méthode de codage BOCU qui a d’autres applications que le seul codage du texte) et réutilisable sous cette forme dans des applications libres (sous certaines réserves concernant certaines modifications qui restent interdites sans l’obtention préalable d’une autorisation et d’une licence spécifiques si ces modifications ne sont pas strictement conformes à la spécification de cette seule variante).

Comme UTF-8, BOCU-1 est compatible avec MIME et les formats de fichiers texte usuels, car il laisse les codes de contrôle C0 essentiels (utilisés comme séparateurs de ligne ou de page) ainsi que les blancs (espaces normales et tabulations) codés sous forme d’octets simples qui ne servent pas non plus à représenter d’autres caractères multi-octets. Et comme UTF-8 (mais pas UTF-16 ou SCSU), il conserve au niveau binaire l’ordre de tri des valeurs scalaires des points de code. Cependant BOCU-1 n’est pas utilisable tel quel pour coder les noms de documents et dossiers (dans les systèmes de fichiers), ni dans les URL.

Intérêts

Son intérêt par rapport à UTF-8 (dans son utilisation pour MIME) réside dans la meilleure compression de données qu’il permet sans nécessiter d’algorithme compliqué de traitement : il offre un taux de compression comparable à UTF-8 pour les langues latines (anglais, français, allemand, roumain, suédois, tchèque, etc.). Il offre des taux de compression comparables à UTF-16 (et bien meilleur qu’UTF-8) pour les langues à écriture idéographique (notamment le chinois, le japonais) ainsi que pour le coréen (dans l‘écriture alphasyllabure hangul).

Comme UTF-8, UTF-16BE, UTF-16LE, UTF-32BE, UTF-32LE (mais à l’inverse de SCSU, ou même UTF-16 et UTF-32 qui sont dépendants de l’ordonnancement des octets dans les unités de codage sur 16 ou 32 bits et de la présence ou non d’un code « BOM », de l‘anglais Byte Order Mark, en tête de texte), il est totalement prédictif (il n’existe qu’une seule façon de coder en séquences d’octets une même séquence de points de code composant un texte).

Mais par rapport à UTF-8 et UTF-16, il améliore la compression du coréen transcrit seulement dans l’alphabet jamo de base.

Il offre un meilleur taux de compression (comparable à celui offert par SCSU) qu’UTF-8 et bien meilleur qu’UTF-16 pour les langues utilisant d’autres écritures qui utilisent la plupart du temps un nombre réduit de caractères, pris soit dans un même bloc de 128 points de code, soit parmi les codes de contrôles C0 et l’espace standard, en obtenant des taux également comparables aux codes des pages de codes et jeux de caractères 8 bits ou multioctets qui ont été développés dans le passé pour certaines langues ou familles de langues, tout en permettant d’être compatible avec la totalité du répertoire universel de l’UCS. C’est le cas de toutes les écritures alphabétiques simples, notamment l’écriture grecque (pour la transcription du grec moderne monotonique ou l’ancien grec classique, mais aussi pour le grec polytonique), cyrillique (pour la transcription du russe, bulgare, ukrainien, etc.), ou les abjads sémitiques (arabe, hébreu), et la plupart des abugidas brahmiques (comme la dévanagari pour la transcription de l’hindi ou du sanscrit, l’écriture tamoule, les écritures thaïe, khmère, lao, les écritures philippines, etc.)

Principes de codage

Le codage BOCU-1 est contextuel et orienté vers le codage en suite d’octets indivisible. Il n’utilise qu’une seule variable d’état entière (contenant la valeur scalaire d’un point de code unique dépendant seulement d’un seul point de code précédemment encodé, donc limité à 21 bits).

Il ne doit être utilisé que pour coder sous la forme de séquences d’octets des suites de points de code standards dotés d’une valeur scalaire dans les normes ISO/CEI 10646 et Unicode (donc uniquement dans U+0000 à U+D7FF, ou U+E000 à U+10FFFF). Comme les autres schémas de transformations conformes à Unicode (tels que UTF-8), il autorise le codage des non-caractères (tels que U+FFFE..U+FFFF) et uniquement ceux-ci (contrairement au codage GB-18030 utilisé en République populaire de Chine, et qui permet de coder aussi la totalité des points de code standards de l‘UCS, mais qui contient aussi des extensions permettant, temporairement, de représenter des caractères non encore normalisés dans l’UCS au niveau international au moyen d’un nombre plus important de positions d’usage privé dans leur mappage possible vers l’UCS, mais réservées dans un registre permanent au sein de cette norme nationale).

La variable d’état

La variable d’état prend une valeur initiale fixe, qui est restaurée après chaque occurrence d’un caractère de contrôle C0 dans le texte (U+0000 à U+001F) et qui correspond au milieu de la colonne des 128 caractères de l’US-ASCII : U+0040.

L’encodage BOCU d’un nouveau point de code dépend de celui-ci :

1. Si ce nouveau point de code est le caractère d’une espace normale, U+0020, l’octet 0x20 est émis, mais la variable d’état n’est pas modifiée.
2. Si ce nouveau point de code est celui d’un des trente-deux caractères de contrôle C0 (U+0000 à U+001F), l’octet de même valeur scalaire est émis, et la variable d’état prend la valeur U+0040 (au milieu du bloc latin de base) : cela permet une resynchronisation du flux sur les sauts de lignes.
3. Sinon, ce nouveau point de code est codé avec une longueur variable sur un à quatre octets (mais sans utiliser aucun des douze octets invariants réservés pour MIME, ni l’octet 0x20 représentant l’espace U+0020), calculés selon la différence delta entre les valeurs scalaires de ce nouveau point de code et de celui stocké dans la variable d’état.

La variable d’état n’est pas modifiée après le codage d’une espace (U+0020), afin de ne pas briser le taux de compression dans les textes non latins les plus courants (ce n’était pas le cas dans la version initiale appelée simplement « BOCU » par ses concepteurs, et que la version BOCU-1 référencée par la note technique UTN#6 d’Unicode a améliorée sur ce point).

Dans tous les autres cas, la variable d’état prend la valeur d’un point de code au milieu du bloc dans lequel se situe le dernier caractère qui a été encodé. Des exceptions sont faites pour les écritures nécessitant des blocs plus larges ou non alignés sur des multiples de 128 points de code :

1. après le codage d'un caractère du bloc hiragana (U+3040 à U+309F), la variable d’état prend la valeur du point de code au milieu de ce bloc (U+3070).
2. après le codage d’un caractère sinographique du bloc CJK Unihan (U+4E00 à U+9FA5), la variable d’état prend la valeur du point de code au milieu de ce bloc (U+76D2).
3. après le codage d’un caractère du bloc des syllabes hangul précomposées (U+AC00 à U+D7A3), la variable d’état prend la valeur du point de code au milieu de ce bloc (U+C1D1).
4. dans les autres cas, la variable d’état prend la valeur du dernier point de code, arrondie au multiple de 128 inférieur puis auquel on ajoute 64.

Points de codes codés de façon invariante et synchronisation

Les douze caractères de contrôle invariants pour MIME, et qui sont toujours codés avec le même octet quelle que soit leur position dans le texte sont :

• U+0000, codé 0x00 dans BOCU-1 : le caractère de bourrage (null, abrégé NUL) ;
• U+0007, codé 0x07 dans BOCU-1 : le caractère d’alarme (bell, abrégé BEL) ;
• U+0008, codé 0x08 dans BOCU-1 : l’espace de correction arrière (backspace, abrégé BS) ;
• U+0009, codé 0x09 dans BOCU-1 : la tabulation horizontale (tabulation, abrégé TAB) ;
• U+000A, codé 0x0A dans BOCU-1 : le saut de ligne (line feed, abrégé LF) ;
• U+000B, codé 0x0B dans BOCU-1 : la tabulation verticale (vertical tabulation, abrégé VT) ;
• U+000C, codé 0x0C dans BOCU-1 : le saut de page (form feed, abrégé FF) ;
• U+000D, codé 0x0D dans BOCU-1 : le retour chariot (carriage return, abrégé CR) ;
• U+000E, codé 0x0E dans BOCU-1 : le contrôle de sortie hors-code (shift out, abrégé SO) ;
• U+000F, codé 0x0F dans BOCU-1 : le contrôle de retour en-code (shift in, abrégé SI) ;
• U+001A, codé 0x1A dans BOCU-1 : le contrôle de substitution (substitute, abrégé SUB), également utilisé dans les fichiers textes compatibles DOS et CPM comme marqueur de fin de fichier ;
• U+001B, codé 0x1B dans BOCU-1 : le contrôle d’échappement (escape, abrégé ESC) ;

(Ces douze caractères de contrôle s’ajoutent à l’espace normale U+0020 codée 0x20 et décrite ci-dessus, qui est aussi invariante mais ne déclenche pas de réinitialisation de la variable d’état et ne peut donc pas servir à la resynchronisation du flux).

Les 20 autres caractères de contrôle C0, bien que codés aussi eux-mêmes en utilisant un seul octet de valeur scalaire identique (afin de préserver l’ordre de tri binaire), sont aussi utilisés comme octets suffixe dans la représentation différentielle des autres caractères.

On peut noter que certains protocoles de transport ou protocoles de liaison pour le transport de données (y compris le texte) utilisent d’autres caractères de contrôle pour l’encapsulation de données dans des trames (notamment U+0002 [STX] et U+0003 [ETX] et U+0016 [SYN]), le contrôle de flux (notamment U+0011 [DC1/XON] et U+0014 [DC4/XOFF]), l’acquittement (hors-bande) de commandes (notamment U+0006 [ACK] et U+0015 [NAK]), le bourrage (notamment U+007F [DEL]), l’annulation anticipée d’une séquence ou commande en cours non acquittée (U+0018 [CAN]), et la transparence des données encapsulées (notamment avec U+0010 [DLE]).

Ces contrôles ne sont pas préservés (mais réencodés différemment à l’aide des valeurs deltas décrites ci-dessous) dans BOCU-1 qui sera incompatible avec ces protocoles (qui disposent parfois de dispositifs d’échappement permettant de transporter ces caractères de façon transparente, mais nécessitant l’emploi d’un des contrôles susmentionnés). La plupart de ces protocoles sont aujourd’hui désuets et remplacés par des protocoles assurant une totale transparence des données encapsulées à l’aide de codages binaires plus efficaces (par exemple les protocoles de transport TCP/IP de l’Internet ou les trames compatibles Ethernet des normes IEEE 802).

À ces valeurs d’octets fixes s’ajoute une valeur réservée qui ne représente elle-même aucun point de code et ne peut figurer non plus comme premier octet du séquence multi-octet représentant un point de code :

• la valeur d’octet 0xFF est réservée comme code reset spécial pour la resynchronisation (il ne sera codé que pour forcer la variable d’état à sa valeur initiale U+0040 : cela brise effectivement l’ordonnancement binaire des points de code (cet octet ne représentera donc pas un caractère) ;
• il peut être utilisé comme terminateur de texte ou comme séparateur de clés de tri textuelles puisqu’il est supérieur à tous les autres octets utilisés pour le codage des points de code, mais il ne pourra pas être utilisé comme octet préfixe au milieu d’un texte codé BOCU sans briser le tri binaire) ;
• mais cette valeur pourra être utilisée aussi pour les octets suffixes servant à coder les grandes valeurs de deltas sur plusieurs octets (voir ci-dessous).

Codage différentiel des autres points de code

Le codage différentiel des autres points de code dotés d’une valeur scalaire (caractères ou non-caractères) doit permettre de coder distinctement des différences positives ou négatives entre tout point de code possible et celui contenu dans la variable d’état : les petites différences (valeurs de delta positives ou négatives) nécessitent moins d’octets que les grandes différences.

Parmi ces différences, celles dans l’intervalle delta de -64 à +63 ne nécessitent qu’un seul octet, alors que les différences plus grandes sont représentées par un octet préfixe discriminant, indiquant la longueur de la séquence totale, suivi de un ou plusieurs octets de suffixe.

Table résumée de codage des deltas (en hexadécimal)

Delta minimum	Delta maximum	Séquence d’octets minimum	Séquence d’octets maximum
-10FF9F	-2DD0D	21 F0 5A D9	21 FF FF FF
-2DD0C	-2912	22 01 01	24 FF FF
-2911	-41	25 01	4F FF
-40	+3F	50	CF
+40	+2910	D0 01	FA FF
+2911	+2DD0B	FB 01 01	FD FF FF
+2DD0C	+10FFBF	FE 01 01 01	FE 19 B4 54

Dans la table ci-dessus, les premiers octets d’une séquence (octets de préfixe discriminants) sont indiqués en gras comme dans le reste de cet article. Les octets de suffixe varient de 0x01 à 0xFF mais ne peuvent pas prendre toutes les valeurs possibles : les 13 valeurs d’octet réservées aux caractères de contrôle invariants et à l’espace sont exclues de ce codage (qui utilise un système numéral de base 243 avant de mapper les chiffres de ce système sur les valeurs d’octets autorisées).

Le détail de ce codage, sur la façon dont il a été déterminé et finalement utilisé, est expliqué dans les sous-sections qui suivent.

Représentation des petits deltas sur un seul octet

Sachant que tous les caractères de contrôle C0 (U+0000 à U+001F) et l’espace U+0020 sont codés aussi par un octet unique, et qu’un octet est réservé pour la fonction de synchronisation ou de marque de fin de texte, cela laisse 222 valeurs d’octets possibles dans un intervalle continu (de 0x21 à 0xFE) pour coder les petits deltas avec un octet unique, et pour coder les octets de préfixe discriminants des plus grands deltas.

La valeur d’octet médiane de cet intervalle est 0x90, qui sera utilisée pour coder un delta nul (c’est-à-dire pour encoder un point de code égal à celui dans la variable d’état).

Les petits deltas de -64 à +63 seront codés relativement à cette valeur d’octet, donc avec les valeurs d’octet entre 0x50 et 0xCF.

Autres valeurs de delta possibles codées sur plusieurs octets, et octets utilisables

Dans BOCU-1, les valeurs d’octets suffixes ne sont pas séparées des valeurs d’octets préfixes, mais les deux types excluent les douze valeurs d’octets réservées aux caractères de contrôle invariants et à l’espace (U+0020).

Sachant que les douze caractères de contrôle C0 invariants (U+0000, U+0007 à U+000F, U+001A et U+001B) et l’espace U+0020 ne sont jamais utilisés non plus comme octets de suffixe (pour préserver la compatibilité MIME), cela laisse 243 valeurs possibles (de 0x01 à 0x06, de 0x10 à 0x19, et de 0x1C à 0x1F et de 0x21 à 0xFF) pour le (ou les) octet(s) de suffixe utilisés (après un premier octet de préfixe discriminant) pour coder les valeurs plus grandes (négatives ou positives) de deltas sur plusieurs octets.

Les valeurs de deltas sont codées de sorte que les octets uniques et les octets de préfixe sont ordonnées de la valeur des deltas négatifs la plus grande en valeur absolue à la valeur des deltas positifs les plus grands.

• Ces valeurs de delta n’étant pas utilisées pour coder les points de code U+0000 à U+0020, les deltas ne sont utilisés que pour coder les points de code U+0021 à U+10FFFF (sauf le petit segment U+D800 à U+DFFF des demi-codets qui n'ont pas de valeur scalaire et dont le codage est interdit pour la conformité à Unicode).
• Les valeurs possibles de la variable d’état ne peuvent être comprises qu’entre U+0040 (valeur initiale ou de resynchronisation après le codage d’un des douze caractères de contrôle C0 invariants) et U+10FFC0.
• Les valeurs possibles de delta codés sur plusieurs octets ne peuvent donc être comprises que :
  • entre (0x21 - 0x10FFC0) = -0x10FF9F = −1 114 015 et -65 (soit 1 113 951 valeurs négatives) ; ou bien
  • entre +64 et (0x40 - 0x10FFFF-0x40) = +0x10FFBF = 1 114 047 (soit 1 113 984 valeurs positives).

Pour coder ces grands deltas sur plusieurs octets, on utilisera un octet de préfixe discriminant parmi :

• les 47 valeurs d’octets entre 0x21 et 0x4F (pour les deltas négatifs inférieurs à -64, du plus grand négatif au moins négatif)
• les 47 valeurs d’octets entre 0xD0 et 0xFE (pour les deltas positifs supérieurs à +63, du moins positif au plus grand positif)

et un ou plusieurs octets de suffixe parmi :

• les 20 valeurs d’octets non invariants dans les codes de contrôles C0 : de 0x01 à 0x06, de 0x10 à 0x19, de 0x1C à 0x1F.
• les autres 223 valeurs d’octets de 0x21 à 0xFF.

Répartition des octets de préfixe

Indépendamment du signe des deltas, on a 47 valeurs d’octets de préfixe disponibles et 243 valeurs d’octets de suffixe, pour coder jusqu’à 1 113 823 valeurs négatives et 1 113 984 valeurs positives de delta.

• Les séquences codées sur 2 octets permettent donc de coder 243 valeurs de deltas par octet de préfixe utilisé
• Les séquences codées sur 3 octets permettent de coder 243² = 59 049 valeurs de delta par octet de préfixe utilisé
• Les séquences codées sur 4 octets permettent de coder jusqu’à 243³ = 14 348 907 valeurs de delta (bien plus que nécessaire pour la totalité).

Pour obtenir la compression maximale, on a intérêt à maximiser les codes les plus courts en utilisant le plus possible de séquences sur 2 octets pour les valeurs de deltas les plus faibles et les plus probables :

• 43 des 47 valeurs d’octets préfixes(entre 0x25 et 0x4F) pour les delta négatifs permettent de coder 43 * 243 = 10 449 valeurs (entre −10 513 et -65) ;
• 43 des 47 valeurs d’octets préfixes (entre 0xD0 et 0xFA) pour les delta positifs permettent de coder 43 * 243 = 10 449 valeurs (entre +64 et 10 512).

Les séquences codées sur 3 octets utilisent :

• 3 des 47 valeurs d’octets préfixes (entre 0x22 et 0x24) pour les delta négatifs permettent de coder 3 * 243² = 177 147 valeurs (entre −187 660 et −10 514) ;
• 3 des 47 valeurs d’octets préfixes (entre 0xFB et 0xFD) pour les delta positifs permettent de coder 3 * 243² = 177 147 valeurs (entre 10 513 et 187 659).

Les séquences codées sur 4 octets utilisent :

• 1 des 47 valeurs d’octets préfixes (0x21) pour les delta négatifs permettent de coder toutes les autres (entre −1 114 015 et −187 661) ;
• 1 des 47 valeurs d’octets préfixes (0xFE) pour les delta négatifs permettent de coder toutes les autres (entre 187 660 et 1 114 047) ;

La totalité des points de code ayant une valeur scalaire dans l’UCS peut donc être encodé sous cette forme compressée tout en conservant leur ordre binaire relatif.

Notes

Environ 6,46 % seulement de toutes les séquences possibles sur 4 octets (243³ = 14 348 907) sont utilisées (les dernières possibles pour les valeurs de delta négatives, et les premières possibles pour les valeurs de delta positives), pour chacune des deux valeurs d’octet préfixe 0x21 et 0xFF.

1. De même que la séquence spéciale de synchronisation forcée, codée par l’octet unique 0xFF, aurait pu être codée parmi les valeurs de delta résiduelles sous forme d’une séquence multi-octets parmi celles inutilisées à la fin de la plage positive, et cette valeur d’octet 0xFF aurait alors pu être utilisée aussi comme octet préfixe discriminant pour des séquences plus courtes permettant d’étendre certaines plages de valeurs de delta codées sur des séquences plus courtes.
   • Mais cela n’aurait pas suffi à éviter des séquences de 4 octets qui sont nécessaires pour coder les plus de 900 000 deltas positifs et presque autant de deltas négatifs nécessaires.
   • Toutefois, cela aurait permis de coder deux points de code supplémentaires (de façon semblable à l’espace) sur un seul octet d’autres caractères de contrôle C0 à garder invariant, par exemple [DEL] U+007F pour une compatibilité améliorée avec les protocoles qui l'interprètent comme un caractère de bourrage).
2. Pour disposer d’une représentation de longueur variable sur au maximum 4 octets de toutes les valeurs de delta nécessaires à la représentation de la totalité de l’UCS, il suffit en effet de disposer de seulement 104 valeurs d’octets suffixes (au lieu des 243 utilisées dans BOCU-1), non utilisées par les caractères codés sur un seul octet invariant. Le choix de 243 valeurs d’octets variables permet de maximiser la compression uniquement en fonction de l’objectif de compatibilité avec MIME uniquement (compatible avec les jeux sur 8 bits) mais pas avec tous les protocoles (et notamment pas les protocoles sur 7 bits, ni ceux qui demandent la préservation du codage US-ASCII).
   • Une représentation totalement compatible avec ISO/CEI 8859 (préservant le codage de l’US-ASCII et aussi les contrôles C1) n’aurait laissé que 96 valeurs d’octets pour coder les séquences de longueurs variable, et il aurait fallu soit étendre les séquences de delta en les autorisant à atteindre jusqu'à 5 octets de code (et utiliser alors une base d’au minimum 33 valeurs d’octets, parmi ces 96, pour les octets suffixes) ; pour limiter les séquences à 4 octets maximum, il est nécessaire d’autoriser les séquences variables représentant les valeurs deltas à réutiliser 104 des 160 valeurs d’octets de l’ISO 8859, mais uniquement comme valeurs de codes suffixes (et non de codes préfixes ou codes uniques) : parmi ces 104 il faudrait nécessairement inclure au minimum 8 des valeurs d’octets codant les contrôles C1.
   • IBM a ainsi développé des adaptations du codage plus général BOCU (différent de la variante BOCU-1 présentée ici) pour la compatibilité avec EBCDIC (en préservant les contrôles C0 et l’espace U+0020, codé 0x40 dans EBCDIC, ainsi que la plupart des contrôles C1) : pour cela, la base de 243 octets variables a été réduite.
3. Parmi les séquences de 4 octets utilisées dans BOCU-1, celles servant à coder les plus grandes valeurs négatives possibles de delta ne peuvent servir qu’à encoder des points de code du jeu US-ASCII (U+0000 à U+007F), et seulement quand la variable d’état est à sa valeur maximale (U+10FFC0, après l’encodage d'un point de code du 17^e et dernier plan d’usage privé). Ces séquences sont toujours codées sur 4 octets, et commencent toujours par l’octet préfixe 0x21, qui est suivi du premier octet suffixe constant 0xF0, du second octet suffixe valant seulement 0x5A ou 0x5B, et d’un troisième octet suffixe.
   • Le remplacement de ces séquences par l’allocation d'un intervalle de valeurs d’octets pour le premier octet suffixe (après l’octet préfixe 0x21) aurait permis de conserver un codage sur 2 octets d’une partie significative du jeu US-ASCII (par exemple tous les contrôles C0, les ponctuations et les 10 chiffres, parmi les points de code inférieurs à U+0040) voire la totalité de ce jeu, quelle que soit la valeur de la variable d'état (alors qu’un codage sur 2 octets de ces points de code ne sera possible que si la variable d’état ne contient pas un point de code trop grand).
   • Sachant que 13 caractères de l’US-ASCII sont déjà codés par leur valeur scalaire sur 1 octet, il aurait suffi de coder directement les autres caractères de ce jeu simplement en les préfixant par l’octet préfixe 0x21 (chaque fois que la valeur de delta est inférieure à -64 ou supérieure à +63, c’est-à-dire quand ils ne peuvent pas être codés sur un seul octet de delta entre 0x50 et 0xCF), sans que cela n’entre en collision avec les autres deltas négatifs (Cela aurait même pu être utilisé pour tous les caractères de l’ISO 8859-1 inférieurs à U+00F0, y compris donc les caractères de contrôle C1).
   • Il aurait même pu être possible de faire que, dans ce cas-là, la variable d’état ne soit pas synchronisée et conserve sa valeur (afin d’éviter d’avoir à coder ensuite sur plus de 2 octets une grande valeur positive de delta, pour revenir au bloc qui contenait le dernier caractère encodé avant ces caractères de l’US-ASCII), comme le fait déjà le codage (sur un seul octet) de l’espace U+0020.
   • Ces possibilités de compression supplémentaires n’ont pas été retenues dans BOCU-1 (alors qu’elles auraient été utiles pour les écritures asiatiques dans des documents HTML et XML où l’utilisation mixte des caractères syntaxiques de l’US-ASCII et des caractères asiatiques est fréquente).

Calcul, mappage et ordonnancement des octets de suffixe

Les deltas sont ajustés en valeur absolue en retranchant la valeur absolue minimale de chaque intervalle auxquels ils appartiennent, puis ils sont exprimés dans la base numérique 243 (par divisions euclidiennes successives de la valeur absolue du delta ajusté dans chaque intervalle de codage) afin obtenir une suite de chiffres entre 0 et 242 dans cette base. Le signe est alors rétabli sur ce décalage (par une opération de complément à 243 pour les deltas négatifs), et chaque chiffre de cette base qui est alors mappé sur les 243 valeurs possibles d'octets de suffixe décrits ci-dessus.

L'ordre croissant de mappage des 243 décalages signés calculés suit la progression binaire croissante des 243 valeurs d’octets de suffixe utilisés (de 0x01 à 0x06, de 0x10 à 0x19, et de 0x1C à 0x1F et de 0x21 à 0xFF), lesquels sont codés dans l’ordre du chiffre de poids fort (dans la base 243) vers le chiffre unitaire de poids faible, ce qui assure que la compression finale produira aussi un code ordonné dans l’ordre binaire.

Utilisation

Il est aussi destiné à être utilisé pour la compression de textes courts (par exemple pour le stockage de champs dans une base de données), pour lesquels il est aussi souhaitable de pouvoir effectuer de la recherche en texte plein. À l’inverse des codages UTF-8/16/32, il n’offre pas une possibilité de resynchronisation depuis une position aléatoire dans un texte. Mais des possibilités limitées de resynchronisation existent dans les textes contenant des phrases et paragraphes (et non des mots isolés), par le fait que les espaces, tabulations et séparateurs de ligne sont laissés inchangés (ces possibilités peuvent ne pas exister dans les textes idéographiques écrits sans espace).

Ce schéma de compression est seulement adapté au stockage ou à la transmission de textes conformes à Unicode ou l’ISO/CEI 10646, il n’est pas conçu pour fonctionner correctement avec les données binaires pour lesquels les formats de compression de fichiers quelconques (comme deflate ou compress utilisés dans MIME, ou les formats d’archive zip, gzip, bzip2) sont mieux adaptés. Ces formats de compression peuvent être utilisés en complément pour améliorer encore les textes codés avec BOCU-1.

Son implémentation est très simple à mettre en œuvre et à certifier, contrairement aux algorithmes génériques de compression de données binaires qui nécessitent souvent la gestion d’un nombre élevé de variables d’état et de tampons de taille souvent variable, ou qui travaille sur des entités aussi petites que le bit : les performances seront donc souvent bien meilleures pour un traitement local au sein d’un même processus ou entre processus d’un même système hôte, qu’avec les algorithmes de compression génériques (qui en revanche pourront s’avérer parfois meilleurs dans le cas de données très volumineuses ou accédées depuis un médium lent ou via un réseau, au prix d’une charge processeur bien supérieure).

Problèmes

Propriété intellectuelle : brevet et licences

Ce schéma de codage, qui ne fait pas partie du standard Unicode mais y est mentionné dans une note technique optionnelle, est le seul qui soit restreint dans son utilisation par le fait qu’il est couvert par un brevet décrivant un algorithme plus général (brevet détenu actuellement par IBM car il a été créé et publié par des personnes qui étaient alors employées par lui).

Cependant IBM a accepté d’en offrir des licences gratuites (sans paiement de redevance ou royalties) à tous les développeurs qui en feraient la demande en produisant une version pleinement conforme à la documentation fournie par IBM (ce qu’IBM peut vérifier, mais ce qui en interdit toute modification, amélioration ou adaptation à des algorithmes dérivés, sans obtention d’une licence). Le brevet couvre notamment la méthode et les principes de codage utilisés.

BOCU-1 est une version particulière (libérée des contraintes de royalties) de l’algorithme de codage plus général BOCU (qui est, lui, soumis à l’obtention d’un accord de licence) et qui permet de réserver d’autres valeurs d’octets invariants ou interdits pour le codage des caractères de l’UCS mais nécessaires à d’autres fonctions ou données dans certains protocoles (par exemple pour le codage complet de l’UCS dans un code barre restreint à 47 valeurs d’octets utilisables, ou encore dans le système de noms de domaines DNS restreint à 37 valeurs d’octets utilisables).

IBM a mis en œuvre (dans sa bibliothèque ICU, fournie sous la licence libre X modifiée pour ICU et signée par IBM) une variante de cet algorithme plus général BOCU pour la compression des clés de collation générées pour l’algorithme de tri normalisé UCA Unicode, afin de compresser les poids de collation de chaque niveau, en évitant d’utiliser certaines valeurs d’octets réservés (par exemple l’octet nul) ce qui permet de stocker les clés de collation dans des chaînes de caractères C où le caractère nul est réservé, et un code est réservé au séparateur de clés de tri multiniveaux.

Compatibilité insuffisante

La variante libre BOCU-1 de l’algorithme BOCU souffre de plusieurs problèmes :

• Parmi les 243 valeurs d’octets utilisées dans des codes variables, figurent 19 codes de contrôles C0 et le caractère de contrôle DEL (U+007F) parfois utilisé comme caractère de bourrage dans certains protocoles. BOCU-1 n’est donc pas compatible avec les applications qui dépendent de l’ISO/CEI 646.
• Les valeurs d’octets caractères de contrôle C1 (U+0080 à U+009F) sont utilisés aussi de façon variable et perdent leur fonction de contrôle (il reste possible de les encoder mais sous la forme de deltas mono-octets ou multioctets), mais c’est un problème mineur (UTF-8 réencode aussi ces contrôles additionnels sous forme de séquences multi-octets).
• Les possibilités de synchronisation pour une recherche depuis une position aléatoire sont insuffisantes.
  • Elle ne sépare pas les octets de préfixe ou octets de code unique des octets de suffixe utilisés pour les points de code codés sur plusieurs octets. La lecture ne peut être qu’unidirectionnelle pour les points de code représentés sous forme de séquences multi-octets codés sous forme de deltas.
  • Le codage, même s’il est prédictif et ne permet qu’un seul codage du même texte (contrairement à SCSU où diverses stratégies de compression sont possibles), ne produit pas toujours la même séquence d’octets pour les mêmes points de code (comme le permet UTF-8) puisque les points de code sont représentés le plus souvent par une différence avec un point de code de référence dépendant du point de code précédent.
  • BOCU-1 ne peut donc pas être utilisé avec les algorithmes de recherche rapide comme l’algorithme de Boyer-Moore qui peut trouver de fausses occurrences positives. Ce codage est donc très mal adapté comme codage en mémoire pour le travail des éditeurs de texte et algorithmes de traitement de chaînes demandant des recherches-substitutions rapides (en revanche il parait idéal si le texte est constitué de petits enregistrements séparés par des sauts de ligne, par exemple dans des tables de données à trier, fichiers journaux, lexiques...
• Trop peu de valeurs d’octets sont réservées pour la synchronisation, qui ne peut avoir lieu que sur les espaces normales (U+0020) et sauts de lignes codés dans l’US-ASCII.

Compression simple mais non optimale

La partition des points de code en grands-sous-ensembles présuppose que les points de code présents dans un texte seront majoritairement dans des blocs de cette taille. L’algorithme n’a pas été revu pour prendre en compte les écritures dont les points de code utilisés sont distribuées sur plusieurs blocs distincts.

• De nouveaux syllabaires (codés dans Unicode et ISO/CEI 10646 dans des blocs plus grands que 128 points de code) ne font pas partie des exceptions retenues à la taille par défaut de bloc de 128 points de code. Il est impossible de modifier cette liste sans rendre l’implémentation non conforme (et donc soumise à un accord de licence non libre en vertu du brevet mentionné ci-dessus).
• Les seuls points de code hors du bloc optimal qui ne conduisent pas à coder de grandes valeurs de delta sur plusieurs octets puis à nouveau une valeur de delta de signe opposé pour revenir dans le bloc de base sont les seuls codes de contrôle C0 et l’espace normale (U+0020). Toutes les autres ponctuations, ou même les points de code des diacritiques génériques (qui sont utilisés dans l’écriture latine, comme aussi les écritures grecques et cyrilliques), ainsi que les ponctuations générales du bloc latin de base quand elles sont utilisées dans d'autres écritures, nécessitent de grandes valeurs de delta, donc un codage multioctet de ces caractères et du caractère qui le suit: dans ce cas, BOCU-1 sera donc un peu moins efficace en compression que les jeux de caractères 8 bits spécialisés pour certaines langues.
• Il n’est pas possible de définir d’autres tailles de blocs optimales pour la détermination du meilleur point de code au centre d’un bloc qui sera celui conservé dans la variable d’état (La compression SCSU utilise une stratégie plus fine).
• Il n’est pas possible d’utiliser plus d’une variable d’état, chacune portant par exemple sur des blocs distincts mais de plus petite taille (par exemple deux variables contenant un point de code dans des blocs de 64, et un encodage des deltas prenant en compte le bloc le plus proche et la différence de probabilité entre les deltas de signes opposés entre ces deux blocs).
• Même avec une seule variable d’état, l’algorithme n’est pas complètement optimal car il n’y a pas le même nombre (ni la même fréquence dans les textes) de points de code avant et après le bloc dans lequel la variable d’état est positionnée :
  • lorsque la variable d’état est à sa valeur initiale (U+0040) ou juste après le codage d’un code de contrôle C0 (ou du code spécial reset 0xFF) qui réinitialise cette valeur, aucune valeur de delta négative ne peut être codée sur plusieurs octets : la moitié des possibilités de codage multioctets est inutilisée (on ne trouvera donc jamais aucun des 47 octets de préfixe réservés au codage multi-octets des valeurs de delta négatives inférieures à -64).
  • l’algorithme a omis d’égaliser les valeurs possibles de deltas entre les valeurs négatives et positives, alors qu’il pouvait le faire simplement en traitant l’ensemble complet des points de code représentables (entre U+0000 et U+10FFFF, dont on peut aussi exclure l’intervalle U+D800 à U+DFFF des demi-codets par décalage pour compacifier un peu plus cet espace) comme des positions sur un cercle de périmètre 0x110000 (ou 0x10F800 si l’on compacte les demi-codets) qui peut être parcouru dans les deux directions de façon cyclique. Dans des textes usuels, le bloc le plus fréquemment utilisé sera plus près du début de l’espace des points de code, et donc les valeurs de delta codées sur plusieurs octets utiliseront très majoritairement des valeurs positives pour sortir de ce bloc, lequel sera immédiatement suivi très majoritairement valeur de delta de signe opposé et codée sur plusieurs octets pour revenir au bloc initial. Comme les deux ensembles ne sont pas de taille égale, l’algorithme peut utiliser parfois plus de séquences codées sur 3 octets que nécessaire, là ou 2 octets auraient pu suffire.
• L’algorithme ne réordonne pas non plus les blocs de points de code possibles en fonction du bloc actuel, avant de calculer les valeurs de delta selon cet ordre, afin de prendre en compte certains blocs alternatifs nettement plus fréquents que d’autres : par exemple le bloc des diacritiques combinants n’est pas rapproché du bloc courant quand c’est le bloc latin de base ou le bloc grec ou cyrillique de base, et ne rapproche pas non plus le bloc latin contenant les ponctuations générales quand le bloc courant n’est pas le bloc latin de base : trop de valeurs de delta codées sur plusieurs octets nécessitent 3 octets au lieu de 2 seulement.
• Il n’a pas non plus tenu compte de la distribution des blocs de points de code référencés par les encodages 8 bits qui ont été normalisés depuis longtemps, et qui étaient pourtant de bons indicateurs de la fréquence d’usage des blocs alternatifs, et qui restent meilleurs le plus souvent pour le codage d’HTML ou XML où les excursions du bloc de l’écriture courante (pour le texte littéral du document) vers le bloc latin de base (contenant les symboles de ponctuations syntaxiques et les noms de balises et attributs HTML standards) sont très fréquentes. Même UTF-8 s’avère plus efficace dans ce dernier cas.
• L’algorithme n’est pas autoadaptatif : dans toute paire de points de code à représenter, le second sera toujours représenté par la même valeur de delta, et donc toujours codé avec le même nombre d’octets, quelle que soit sa fréquence dans le texte. Les algorithmes de compression génériques (à base de dictionnaires enregistrant les paires les plus probables selon leur distribution statistique déjà constatée) donnent de bien meilleurs résultats (et peuvent aussi coder ces paires fréquentes en réduisant même le nombre de bits par unité à coder, lesquelles peuvent être même de longueur plus longues, en utilisant des fractions d’octets dans le codage final).

Voir aussi

Articles connexes

• International Components for Unicode (ICU), ensemble de bibliothèques (développées en source ouvert et distribuées librement sous licence X version ICU) pour l’intégration en C/C++ ou Java du support des normes Unicode/ISO/CEI 10646 et l’internationalistion des logiciels, capables de convertir des textes conformes à Unicode, entre BOCU-1 et divers encodages nationaux ou internationaux (standards ou normalisés).

  Les bibliothèques ICU, très modulaires et réputées (pour leur qualité, leur stabilité, leur conformité stricte aux standards et normes qu’elles implémentent, ainsi que pour leur performance et la quasi-exhaustivité des fonctionnalités, écritures, langues et jeux de caractères codés qu’elles supportent) ont également été intégrées partiellement ou totalement à de nombreux autres langages de programmation ou sous-systèmes à l’aide de modules interfaces spécifiques pour ces langages (PHP, Perl, C#/J#/VB, etc.) ou sous-systèmes et ateliers écrits dans ces langages.

Références externes

• Unicode Technical Note #6 BOCU-1: MIME Compatible Unicode Compression