{"id":95911,"date":"2020-10-05T01:42:09","date_gmt":"2020-10-04T23:42:09","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8"},"modified":"2020-10-05T01:42:09","modified_gmt":"2020-10-04T23:42:09","slug":"eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","status":"publish","type":"post","link":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Un autre v\u00e9lo : nous stockons des cha\u00eenes Unicode 30-60 % plus compactes que UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Un
\n
\nSi vous \u00eates d\u00e9veloppeur et que vous devez choisir une encodage, la solution presque toujours correcte sera Unicode. Le mode de repr\u00e9sentation sp\u00e9cifique d\u00e9pend du contexte, mais le plus souvent, il y a aussi une r\u00e9ponse universelle \u2014 UTF-8. Il est avantageux car il permet d'utiliser tous les caract\u00e8res Unicode sans gaspiller trop<\/em> de bytes dans la plupart des cas. Cependant, pour les langues qui n'utilisent pas seulement l'alphabet latin, \u00ab pas trop \u00bb signifie au moins deux bytes par caract\u00e8re<\/strong>. Peut-on faire mieux, sans revenir \u00e0 des encodages pr\u00e9historiques qui nous limitent \u00e0 seulement 256 caract\u00e8res disponibles ?<\/p>\n

Je vous pr\u00e9sente ci-dessous ma tentative de r\u00e9pondre \u00e0 cette question et une mise en \u0153uvre d'un algorithme relativement simple, permettant de stocker des cha\u00eenes dans la plupart des langues du monde, sans ajouter la redondance pr\u00e9sente dans UTF-8.<\/a><\/noindex><\/p>\n

Avertissement.<\/i> Je vais d'abord faire quelques importantes r\u00e9serves : la solution d\u00e9crite n'est pas propos\u00e9e comme un remplacement universel de l'UTF-8<\/strong>, elle convient uniquement dans un nombre restreint de cas (qui seront abord\u00e9s ci-dessous), et ne doit en aucun cas \u00eatre utilis\u00e9e pour interagir avec des API externes (qui ne la connaissent pas non plus). Le plus souvent, pour le stockage compact de grandes quantit\u00e9s de donn\u00e9es textuelles, des algorithmes de compression g\u00e9n\u00e9riques (par exemple, deflate) seront appropri\u00e9s. De plus, tout en cr\u00e9ant ma solution, j'ai d\u00e9couvert un standard existant dans Unicode lui-m\u00eame, qui r\u00e9sout le m\u00eame probl\u00e8me \u2014 il est un peu plus complexe (et souvent moins performant), mais reste un standard accept\u00e9, et non une solution bricol\u00e9e. Je vais \u00e9galement en parler.<\/p>\n

\u00c0 propos de Unicode et UTF-8<\/h2>\n

\nPour commencer \u2014 quelques mots sur ce qu'est au juste Unicode<\/strong> et UTF-8<\/strong>.<\/p>\n

Comme on le sait, les encodages 8 bits \u00e9taient autrefois populaires. C'\u00e9tait simple : 256 caract\u00e8res peuvent \u00eatre num\u00e9rot\u00e9s avec les nombres de 0 \u00e0 255, et les nombres de 0 \u00e0 255 peuvent \u00e9videmment \u00eatre repr\u00e9sent\u00e9s par un seul byte. Si nous revenons aux origines, l'encodage ASCII est m\u00eame limit\u00e9 \u00e0 7 bits, ce qui signifie que le bit le plus significatif de sa repr\u00e9sentation byte est \u00e9gal \u00e0 z\u00e9ro, et la plupart des encodages 8 bits sont compatibles avec lui (ils ne diff\u00e8rent que dans la \u00ab partie sup\u00e9rieure \u00bb, o\u00f9 le bit le plus significatif est un).<\/p>\n

En quoi Unicode se distingue-t-il de ces encodages et pourquoi est-il associ\u00e9 \u00e0 plusieurs repr\u00e9sentations concr\u00e8tes \u2014 UTF-8, UTF-16 (BE et LE), UTF-32 ? Examinons cela dans l'ordre.<\/p>\n

Le standard Unicode principal d\u00e9crit uniquement la correspondance entre les caract\u00e8res (et dans certains cas, les composants individuels des caract\u00e8res) et leurs num\u00e9ros. Et le nombre possible de num\u00e9ros dans ce standard est tr\u00e8s \u00e9lev\u00e9 - jusqu'\u00e0 0x00<\/b><\/code> \u00e0 0x10FFFF<\/b><\/code> (1 114 112 unit\u00e9s). Si nous souhaitions stocker un nombre dans cette plage dans une variable, ni 1 ni 2 octets ne suffiraient. Et comme nos processeurs ne sont pas vraiment con\u00e7us pour traiter des nombres en trois octets, nous serions contraints d'utiliser 4 octets pour un seul caract\u00e8re ! C'est ce qu'on appelle l'UTF-32, mais justement \u00e0 cause de cette \u00ab gaspillage \u00bb, ce format n'est pas populaire.<\/p>\n

Heureusement, les caract\u00e8res \u00e0 l'int\u00e9rieur de Unicode ne sont pas ordonn\u00e9s au hasard. Leur multitude est divis\u00e9e en 17 \u00abplans<\/em>\u00bb, chacun contenant 65 536 (0x10000<\/b><\/code>) \u00abpoints de code<\/em>. La notion de \u00ab point de code \u00bb ici est simplement un num\u00e9ro de caract\u00e8re<\/em>, qui lui a \u00e9t\u00e9 attribu\u00e9 par Unicode. Mais, comme mentionn\u00e9 pr\u00e9c\u00e9demment, dans Unicode, non seulement des caract\u00e8res individuels sont num\u00e9rot\u00e9s, mais \u00e9galement leurs composants et les annotations techniques (et parfois, le num\u00e9ro ne correspond m\u00eame \u00e0 rien - peut-\u00eatre pour un certain temps, mais cela n'est pas notre principal souci), il est donc plus correct de toujours parler du nombre de num\u00e9ros, et non de caract\u00e8res. Cependant, pour des raisons de concision, j'utiliserai souvent le terme \u00ab caract\u00e8re \u00bb, en me r\u00e9f\u00e9rant au terme \u00ab point de code \u00bb.<\/p>\n

\"Un
\nPlans de Unicode. Comme on peut le voir, la majeure partie (les plans 4 \u00e0 13) est encore inutilis\u00e9e.<\/i><\/p>\n

\u0427\u0442\u043e \u0441\u0430\u043c\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u2014 \u0432\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u00ab\u043c\u044f\u043a\u043e\u0442\u043a\u0430\u00bb \u043b\u0435\u0436\u0438\u0442 \u0432 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u043e\u043d\u0430 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f "Plan multilingue de base<\/em>". \u0415\u0441\u043b\u0438 \u0441\u0442\u0440\u043e\u0447\u043a\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u0435\u043a\u0441\u0442 \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u0438\u0437 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u043e\u0432 (\u0432\u043a\u043b\u044e\u0447\u0430\u044f \u043a\u0438\u0442\u0430\u0439\u0441\u043a\u0438\u0439), \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u044d\u0442\u043e\u0439 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438 \u0432\u044b \u043d\u0435 \u0432\u044b\u0439\u0434\u0435\u0442\u0435. \u041d\u043e \u043e\u0442\u0441\u0435\u043a\u0430\u0442\u044c \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u042e\u043d\u0438\u043a\u043e\u0434\u0430 \u0442\u043e\u0436\u0435 \u043d\u0435\u043b\u044c\u0437\u044f \u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u044d\u043c\u043e\u0434\u0437\u0438 \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043f\u043e \u0441\u0447\u0451\u0442\u0443 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, "Plan multilingue suppl\u00e9mentaire<\/em>" (\u043e\u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043e\u0442 0x10000<\/b><\/code> \u00e0 0x1FFFF<\/b><\/code>). Ainsi, UTF-16 proc\u00e8de comme suit : tous les caract\u00e8res appartenant \u00e0 Plan multilingue de base<\/em>, sont cod\u00e9s \u00ab tels quels \u00bb, avec leur nombre en deux octets correspondant. Cependant, une partie des nombres dans cette plage ne d\u00e9signe pas de caract\u00e8res sp\u00e9cifiques, mais indique qu'apr\u00e8s cette paire d'octets, il faut examiner une autre paire - en combinant les valeurs de ces quatre octets ensemble, nous obtiendrons un nombre qui couvre toute la plage autoris\u00e9e de Unicode. Cette repr\u00e9sentation est appel\u00e9e \u00ab paires de substitution \u00bb - peut-\u00eatre en avez-vous entendu parler.<\/p>\n

Ainsi, UTF-16 n\u00e9cessite deux ou (dans de tr\u00e8s rares cas) quatre octets par \u00ab point de code \u00bb. C'est mieux que d'utiliser constamment quatre octets, mais la latin (et d'autres symboles ASCII) consomment ici la moiti\u00e9 de l'espace occup\u00e9 par des z\u00e9ros. UTF-8 a \u00e9t\u00e9 con\u00e7u pour corriger cela : l'ASCII y occupe, comme auparavant, un octet ; les codes de 0x80<\/b><\/code> \u00e0 0x7FF<\/b><\/code> \u2014 deux octets ; de 0x800<\/b><\/code> \u00e0 0xFFFF<\/b><\/code> \u2014 trois, et de 0x10000<\/b><\/code> \u00e0 0x10FFFF<\/b><\/code> \u2014 quatre. D'une part, la latin s'en sort bien : la compatibilit\u00e9 avec l'ASCII est revenue, et la r\u00e9partition est plus uniform\u00e9ment \u00ab \u00e9tal\u00e9e \u00bb de 1 \u00e0 4 octets. Mais les alphabets autres que le latin, h\u00e9las, ne s'am\u00e9liorent pas par rapport \u00e0 UTF-16, et beaucoup n\u00e9cessitent maintenant trois octets au lieu de deux \u2014 la plage couverte par l'enregistrement en deux octets a \u00e9t\u00e9 r\u00e9duite de 32 fois, de 0xFFFF<\/b><\/code> \u00e0 0x7FF<\/b><\/code>, \u0438 \u0432 \u043d\u0435\u0433\u043e \u043d\u0435 \u043f\u043e\u043f\u0430\u0434\u0430\u0435\u0442 \u0443\u0436\u0435 \u043d\u0438 \u043a\u0438\u0442\u0430\u0439\u0441\u043a\u0438\u0439, \u043d\u0438, \u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u0433\u0440\u0443\u0437\u0438\u043d\u0441\u043a\u0438\u0439. \u041a\u0438\u0440\u0438\u043b\u043b\u0438\u0446\u0435 \u0438 \u0435\u0449\u0451 \u043f\u044f\u0442\u0438 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430\u043c \u2014 \u0443\u0440\u0430 \u2014 \u043f\u043e\u0432\u0435\u0437\u043b\u043e, 2 \u0431\u0430\u0439\u0442\u0430 \u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b.<\/p>\n

Pourquoi cela se produit-il ? Voyons comment UTF-8 repr\u00e9sente les codes de caract\u00e8res :
\n\"Un
\nDirectement pour la repr\u00e9sentation des nombres, des bits sont utilis\u00e9s ici, marqu\u00e9s par le symbole x<\/b><\/code>. On voit que dans l'enregistrement en deux octets, il n'y a que 11 bits (sur 16). Les bits de t\u00eate ont ici seulement une fonction de service. Dans le cas de l'enregistrement en quatre octets, 21 bits sur 32 sont allou\u00e9s au num\u00e9ro du point de code \u2014 il semblerait qu'il aurait suffi de trois octets (qui fournissent au total 24 bits), mais les marqueurs de service consomment trop.<\/p>\n

Est-ce mauvais ? En r\u00e9alit\u00e9, pas vraiment. D'une part \u2014 si nous sommes tr\u00e8s soucieux de l'espace occup\u00e9, nous avons des algorithmes de compression qui \u00e9limineront facilement toute l'entropie et la redondance. D'autre part \u2014 l'objectif de l'Unicode \u00e9tait de fournir un codage aussi universel que possible. Par exemple, une cha\u00eene cod\u00e9e en UTF-8 peut \u00eatre confi\u00e9e \u00e0 un code qui fonctionnait auparavant uniquement avec l'ASCII, sans craindre qu'il y voie un symbole du domaine ASCII qui n'y est pas r\u00e9ellement pr\u00e9sent (car, dans UTF-8, tous les octets commen\u00e7ant par un bit nul sont effectivement de l'ASCII). Et si nous voulons soudainement couper une petite queue d'une grande cha\u00eene, sans la d\u00e9coder depuis le d\u00e9but (ou restaurer une partie des informations apr\u00e8s un segment endommag\u00e9) \u2014 il n'est pas difficile de trouver le d\u00e9calage o\u00f9 commence un symbole donn\u00e9 (il suffit de sauter les octets ayant un pr\u00e9fixe binaire 10<\/b><\/code>).<\/p>\n

Pourquoi alors inventer quelque chose de nouveau ?<\/h2>\n

\nCependant, il arrive parfois que des algorithmes de compression comme deflate soient mal adapt\u00e9s, et qu'on souhaite obtenir un stockage compact des cha\u00eenes. Personnellement, j'ai \u00e9t\u00e9 confront\u00e9 \u00e0 ce d\u00e9fi en r\u00e9fl\u00e9chissant \u00e0 la construction d'un arbre de pr\u00e9fixes compress\u00e9<\/a><\/noindex> pour un grand dictionnaire incluant des mots de diverses langues. D'une part, chaque mot est tr\u00e8s court, donc le compresser serait peu efficace. D'autre part, l'impl\u00e9mentation de l'arbre que j'envisageais \u00e9tait con\u00e7ue de mani\u00e8re \u00e0 ce que chaque octet de la cha\u00eene stock\u00e9e g\u00e9n\u00e8re un sommet distinct de l'arbre, donc minimiser leur nombre \u00e9tait tr\u00e8s utile. Dans ma biblioth\u00e8que Az.js<\/a><\/noindex> (tout comme dans pymorphy2<\/a><\/noindex>, sur laquelle elle est bas\u00e9e) un tel probl\u00e8me se r\u00e9sout simplement : les cha\u00eenes, emball\u00e9es dans un dictionnaire DAWG<\/a><\/noindex>, y sont stock\u00e9es en fid\u00e8le CP1251<\/a><\/noindex>. Mais, comme il n'est pas difficile de le comprendre, cela fonctionne bien seulement pour un alphabet limit\u00e9 : on ne peut d\u00e9j\u00e0 plus int\u00e9grer une cha\u00eene en chinois dans un tel dictionnaire.<\/p>\n

Je tiens \u00e9galement \u00e0 souligner un autre d\u00e9sagr\u00e9ment qui survient lors de l'utilisation de l'UTF-8 dans une telle structure de donn\u00e9es. Sur l'image ci-dessus, on voit que lors de l'enregistrement d'un caract\u00e8re sous forme de deux octets, les bits correspondant \u00e0 son num\u00e9ro ne sont pas en continu, mais interrompus par une paire de bits 10<\/b><\/code> au milieu : 110xxxxx 10xxxxxx<\/b><\/code>. \u00c0 cause de cela, lorsque les 6 bits de poids faible du second octet d\u00e9bordent (c'est-\u00e0-dire qu'il y a un d\u00e9passement 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), le premier octet change \u00e9galement. Ainsi, la lettre \u00ab \u043f \u00bb est repr\u00e9sent\u00e9e par les octets 0xD0 0xBF<\/b><\/code>, et la lettre suivante \u00ab \u0440 \u00bb \u2014 d\u00e9j\u00e0 par 0xD1 0x80<\/b><\/code>. Dans l'arbre de pr\u00e9fixes, cela entra\u00eene la division du sommet parent en deux \u2013 un pour le pr\u00e9fixe 0xD0<\/b><\/code>, et l'autre pour 0xD1<\/b><\/code> (bien que tout le cyrillique pourrait \u00eatre cod\u00e9 seulement avec le second octet).<\/p>\n

Ce que j'ai obtenu<\/h2>\n

\nConfront\u00e9 \u00e0 ce d\u00e9fi, j'ai d\u00e9cid\u00e9 de m'exercer \u00e0 manipuler des bits, tout en me familiarisant un peu mieux avec la structure du Unicode en g\u00e9n\u00e9ral. Le r\u00e9sultat a \u00e9t\u00e9 un format de codage UTF-C (\u00ab C \u00bb pour compact<\/em>), qui ne consomme pas plus de 3 octets par point de code, et permet tr\u00e8s souvent de n'utiliser qu'un seul octet suppl\u00e9mentaire pour toute la cha\u00eene cod\u00e9e<\/strong>. Cela entra\u00eene le fait que sur de nombreux alphabets non ASCII, ce codage s'av\u00e8re 30 \u00e0 60 % plus compact que l'UTF-8<\/strong>.<\/p>\n

J'ai format\u00e9 des exemples d'impl\u00e9mentation des algorithmes de codage et de d\u00e9codage sous forme de biblioth\u00e8ques en JavaScript et Go<\/a><\/noindex>, vous pouvez les utiliser librement dans votre code. Mais je tiens \u00e0 souligner qu'en un certain sens, ce format reste un \u00ab v\u00e9lo \u00bb, et je ne vous recommande pas de l'utiliser sans comprendre pourquoi vous en avez besoin<\/strong>. C'est plus une exp\u00e9rience qu'une v\u00e9ritable \u00ab am\u00e9lioration de l'UTF-8 \u00bb. N\u00e9anmoins, le code est \u00e9crit de mani\u00e8re soign\u00e9e, concise, avec de nombreux commentaires et une couverture de tests.<\/p>\n

\"Un
\nR\u00e9sultat des tests et comparaison avec l'UTF-8<\/i><\/p>\n

J'ai \u00e9galement cr\u00e9\u00e9 une page de d\u00e9monstration<\/a><\/noindex>, o\u00f9 vous pouvez appr\u00e9cier le fonctionnement de l'algorithme, et par la suite, je vous expliquerai plus en d\u00e9tail ses principes et son processus de d\u00e9veloppement.<\/p>\n

\u00c9liminons les bits redondants<\/h2>\n

\nJ'ai pris comme base, bien s\u00fbr, l'UTF-8. La premi\u00e8re et la plus \u00e9vidente chose que nous pouvons changer est de r\u00e9duire le nombre de bits de contr\u00f4le dans chaque octet. Par exemple, le premier octet dans l'UTF-8 commence toujours par 0<\/b><\/code>, ou par 11<\/b><\/code> \u2014 et le pr\u00e9fixe 10<\/b><\/code> n'appara\u00eet que dans les octets suivants. Rempla\u00e7ons le pr\u00e9fixe 11<\/b><\/code> sur 1<\/b><\/code>, et nous supprimerons compl\u00e8tement les pr\u00e9fixes dans les octets suivants. Que va-t-il se passer?<\/p>\n

0xxxxxxx<\/b><\/code> \u2014 1 octet
\n10xxxxxx xxxxxxxx<\/b><\/code> \u2014 2 octets
\n110xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 octets<\/p>\n

Attendez, et o\u00f9 est l'enregistrement de quatre octets? Eh bien, cela n'est plus n\u00e9cessaire \u2014 avec trois octets, nous avons maintenant acc\u00e8s \u00e0 21 bits, ce qui est largement suffisant pour tous les nombres jusqu'\u00e0 0x10FFFF<\/b><\/code>.<\/p>\n

Qu'est-ce que nous avons sacrifi\u00e9 ici? La chose la plus importante est la d\u00e9tection des limites des caract\u00e8res \u00e0 partir d'un emplacement al\u00e9atoire dans le tampon. Nous ne pouvons pas pointer sur un octet al\u00e9atoire et trouver le d\u00e9but du caract\u00e8re suivant. C'est une limitation de notre format, mais en pratique, ce besoin ne se pr\u00e9sente pas souvent. En g\u00e9n\u00e9ral, nous sommes capables de parcourir le tampon depuis le d\u00e9but (surtout lorsqu'il s'agit de courtes cha\u00eenes).<\/p>\n

La situation avec la couverture des langues de 2 octets s'est \u00e9galement am\u00e9lior\u00e9e : maintenant, le format \u00e0 deux octets offre une plage de 14 bits, soit des codes jusqu'\u00e0 0x3FFF<\/b><\/code>. Les Chinois ne sont pas chanceux (leurs id\u00e9ogrammes sont principalement situ\u00e9s dans la plage de 0x4E00<\/b><\/code> \u00e0 0x9FFF<\/b><\/code>), mais les G\u00e9orgiens et de nombreux autres peuples ont eu un peu plus de chance \u2014 leurs langues peuvent \u00e9galement \u00eatre repr\u00e9sent\u00e9es en 2 octets par caract\u00e8re.<\/p>\n

Introduisons l'\u00e9tat de l'encodeur<\/h2>\n

\nR\u00e9fl\u00e9chissons maintenant aux caract\u00e9ristiques des cha\u00eenes elles-m\u00eames. Dans un dictionnaire, les mots sont souvent \u00e9crits avec des caract\u00e8res d'un m\u00eame alphabet, et cela est \u00e9galement vrai pour de nombreux autres textes. Il serait bon d'indiquer un alphabet une fois, puis de n'indiquer que le num\u00e9ro de la lettre \u00e0 l'int\u00e9rieur. Voyons si la disposition des caract\u00e8res dans la table Unicode peut nous aider.<\/p>\n

Comme mentionn\u00e9 ci-dessus, Unicode est divis\u00e9 en plans<\/em> par 65536 codes chacun. Mais cette division n'est pas tr\u00e8s utile (comme d\u00e9j\u00e0 mentionn\u00e9, nous sommes le plus souvent dans le plan z\u00e9ro). Une division plus int\u00e9ressante est celle en blocs.<\/em> Ces plages n'ont d\u00e9j\u00e0 plus de longueur fixe, et ont plus de sens \u2014 g\u00e9n\u00e9ralement, chacune regroupe des caract\u00e8res d'un m\u00eame alphabet.<\/p>\n

\"Un
\nBloc contenant des caract\u00e8res de l'alphabet bengali. Malheureusement, pour des raisons historiques, c'est un exemple de conditionnement peu dense \u2014 96 caract\u00e8res sont dispers\u00e9s de mani\u00e8re chaotique sur 128 points de code du bloc.<\/i><\/p>\n

Le d\u00e9but des blocs et leur taille sont toujours multiples de 16 \u2014 c'est simplement fait pour des raisons de commodit\u00e9. De plus, de nombreux blocs commencent et se terminent par des valeurs multiples de 128 ou m\u00eame de 256 \u2014 par exemple, le cyrillique de base occupe 256 octets \u00e0 partir de 0x0400<\/b><\/code> \u00e0 0x04FF<\/b><\/code>. C'est plut\u00f4t pratique : si nous enregistrons une fois le pr\u00e9fixe 0x04<\/b><\/code>, alors n'importe quel caract\u00e8re cyrillique peut \u00eatre \u00e9crit en un octet. Cependant, nous perdons ainsi la possibilit\u00e9 de revenir \u00e0 l'ASCII (et \u00e0 tout autre caract\u00e8re en g\u00e9n\u00e9ral). Donc, nous proc\u00e9dons comme suit :<\/p>\n

    \n
  1. Deux octets 10yyyyyy yxxxxxxx<\/b><\/code> non seulement d\u00e9signent le caract\u00e8re num\u00e9rot\u00e9 yyyyyy yxxxxxxx<\/b><\/code>, mais changent l'alphabet courant<\/em> sur yyyyyy y0000000<\/b><\/code> c'est-\u00e0-dire que nous m\u00e9morisons tous les bits, sauf les moins significatifs 7 bits<\/strong>);<\/li>\n
  2. Un octet 0xxxxxxx<\/b><\/code> est un caract\u00e8re de l'alphabet courant. Il faut simplement l'ajouter au d\u00e9calage que nous avons m\u00e9moris\u00e9 \u00e0 l'\u00e9tape 1. Tant que nous n'avons pas chang\u00e9 d'alphabet, le d\u00e9calage est \u00e9gal \u00e0 z\u00e9ro, donc nous avons conserv\u00e9 la compatibilit\u00e9 avec l'ASCII.<\/li>\n<\/ol>\n

    \nDe m\u00eame pour les codes n\u00e9cessitant 3 octets :<\/p>\n

      \n
    1. Trois octets 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> d\u00e9signent le caract\u00e8re num\u00e9rot\u00e9 yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, changent l'alphabet courant<\/em> sur yyyyyy y0000000 00000000<\/b><\/code> (nous avons m\u00e9moris\u00e9 tout, sauf les moins significatifs 15 bits<\/strong>), et mettent un drapeau que nous sommes maintenant en mode long<\/em> lorsque nous changeons d'alphabet pour revenir \u00e0 un mode \u00e0 deux octets, nous r\u00e9initialiserons ce drapeau);<\/li>\n
    2. Deux octets 0xxxxxxx xxxxxxxx<\/b><\/code> en mode long, c'est le caract\u00e8re de l'alphabet courant. De m\u00eame, nous l'ajoutons au d\u00e9calage de l'\u00e9tape 1. La seule diff\u00e9rence est que maintenant, nous lisons deux octets (car nous avons bascul\u00e9 dans ce mode).<\/li>\n<\/ol>\n

      \nCela semble plut\u00f4t bon : tant que nous avons besoin d'encoder des caract\u00e8res d'une m\u00eame plage Unicode de 7 bits, nous d\u00e9pensons 1 octet suppl\u00e9mentaire au d\u00e9but et un octet pour chaque caract\u00e8re.<\/p>\n

      \"Un
      \nTravail d'une des premi\u00e8res versions. Elle d\u00e9passe d\u00e9j\u00e0 souvent UTF-8, mais il reste encore des am\u00e9liorations \u00e0 apporter.<\/i><\/p>\n

      Qu'est-ce qui s'est d\u00e9t\u00e9rior\u00e9 ? Tout d'abord, nous avons introduit un \u00e9tat, \u00e0 savoir le d\u00e9calage de l'alphabet courant<\/em> et un drapeau mode long<\/em>. Cela nous impose des limitations suppl\u00e9mentaires : maintenant, les m\u00eames caract\u00e8res peuvent \u00eatre cod\u00e9s diff\u00e9remment selon les contextes. La recherche de sous-cha\u00eenes, par exemple, devra d\u00e9sormais tenir compte de cela au lieu de simplement comparer des octets. Deuxi\u00e8mement, une fois que nous avons chang\u00e9 d'alphabet, le codage des caract\u00e8res ASCII a mal tourn\u00e9 (et cela ne concerne pas seulement l'alphabet latin, mais aussi la ponctuation de base, y compris les espaces) \u2014 ils n\u00e9cessitent un changement d'alphabet en 0, c'est-\u00e0-dire un octet suppl\u00e9mentaire (et encore un autre pour revenir \u00e0 notre base).<\/p>\n

      Un alphabet c'est bien, deux c'est mieux<\/h2>\n

      \nEssayons de modifier l\u00e9g\u00e8rement nos pr\u00e9fixes de bits en ajoutant un troisi\u00e8me aux trois d\u00e9crits ci-dessus :<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 octet en mode normal, 2 en mode long
      \n11xxxxxx<\/b><\/code> \u2014 1 octet
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 octets
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 octets<\/p>\n

      \"Un
      \n
      \nMaintenant, dans l'enregistrement sur deux octets, il y a un bit disponible de moins \u2014 les points de code allant jusqu'\u00e0 0x1FFF<\/b><\/code>, pas 0x3FFF<\/b><\/code>. Cependant, c'est encore nettement plus que dans les codes \u00e0 deux octets de UTF-8, la plupart des langues courantes peuvent encore y tenir, la perte la plus notable \u2014 a disparu       hiragana<\/a><\/noindex> et katakana<\/a><\/noindex>, les Japonais sont tristes.<\/p>\n

      Quel est donc ce nouveau code 11xxxxxx<\/b><\/code>? \u042d\u0442\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u00ab\u0437\u0430\u0433\u0430\u0448\u043d\u0438\u043a\u00bb \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0432 64 \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043e\u043d \u0434\u043e\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043d\u0430\u0448 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0430\u043b\u0444\u0430\u0432\u0438\u0442, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043d\u0430\u0437\u0432\u0430\u043b \u0435\u0433\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c (auxiliaire<\/em>) alphabet. Lorsque nous changeons l'alphabet actuel, une partie de l'ancien alphabet devient auxiliaire. Par exemple, si nous avons chang\u00e9 de l'ASCII au cyrillique \u2014 dans le \u00ab stock \u00bb il y a maintenant 64 caract\u00e8res, contenant l'alphabet latin, les chiffres, les espaces et la virgule<\/strong> (les insertions les plus fr\u00e9quentes dans les textes non-ASCII). Si nous revenons \u00e0 l'ASCII \u2014 l'alphabet auxiliaire deviendra la majeure partie du cyrillique.<\/p>\n

      Gr\u00e2ce \u00e0 l'acc\u00e8s \u00e0 deux alphabets, nous pouvons traiter un grand nombre de textes, en ayant des co\u00fbts minimaux pour le changement d'alphabets (la ponctuation nous ram\u00e8nera souvent \u00e0 l'ASCII, mais apr\u00e8s cela, nous extrairons de nombreux caract\u00e8res non-ASCII d\u00e9j\u00e0 de l'alphabet suppl\u00e9mentaire, sans changement suppl\u00e9mentaire).<\/p>\n

      Bonus : en d\u00e9signant l'alphabet suppl\u00e9mentaire par un pr\u00e9fixe 11xxxxxx<\/b><\/code> et en choisissant son d\u00e9calage initial comme 0xC0<\/b><\/code>, nous obtenons une compatibilit\u00e9 partielle avec CP1252. En d'autres termes, de nombreux (mais pas tous) textes d'Europe de l'Ouest cod\u00e9s en CP1252 appara\u00eetront de la m\u00eame mani\u00e8re en UTF-C.<\/p>\n

      Cela soul\u00e8ve, cependant, une difficult\u00e9 : comment obtenir l'alphabet auxiliaire \u00e0 partir de l'alphabet principal ? On peut laisser le m\u00eame d\u00e9calage, mais \u2014 h\u00e9las \u2014 ici la structure de Unicode joue d\u00e9j\u00e0 contre nous. Tr\u00e8s souvent, la majeure partie de l'alphabet ne se trouve pas au d\u00e9but du bloc (par exemple, la lettre majuscule russe \u00ab \u0410 \u00bb a le code 0x0410<\/b><\/code>, bien que le bloc cyrillique commence par 0x0400<\/b><\/code>). Ainsi, en prenant les 64 premiers caract\u00e8res dans notre \u00ab bo\u00eete de rangement \u00bb, nous pourrions \u00e9ventuellement perdre l'acc\u00e8s \u00e0 la partie terminale de l'alphabet.<\/p>\n

      Pour r\u00e9soudre ce probl\u00e8me, j'ai manuellement parcouru certains blocs correspondant \u00e0 diff\u00e9rentes langues et j'ai indiqu\u00e9 pour eux le d\u00e9calage de l'alphabet auxiliaire \u00e0 l'int\u00e9rieur du principal. J'ai m\u00eame r\u00e9organis\u00e9 par exception les caract\u00e8res latins comme en base64.<\/p>\n

      \"Un<\/p>\n

      Derni\u00e8res retouches<\/h2>\n

      \nR\u00e9fl\u00e9chissons enfin \u00e0 o\u00f9 nous pourrions encore am\u00e9liorer quelque chose.<\/p>\n

      Notons que le format 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> permet de coder des nombres allant jusqu'\u00e0 0x1FFFFF<\/b><\/code>, tandis que l'Unicode se termine plus t\u00f4t, \u00e0 0x10FFFF<\/b><\/code>. En d'autres termes, le dernier point de code sera repr\u00e9sent\u00e9 comme 10110000 11111111 11111111<\/b><\/code>. Ainsi, nous pouvons dire que si le premier octet a la forme 1011xxxx<\/b><\/code> UCS-4 xxxx<\/b><\/code> plus de 0), il d\u00e9signe autre chose. Par exemple, nous pourrions y ajouter encore 15 caract\u00e8res, toujours disponibles pour \u00eatre cod\u00e9s en un octet, mais j'ai d\u00e9cid\u00e9 de proc\u00e9der autrement.<\/p>\n

      C'est pourquoi nous choisissons quelques plages s\u00e9lectionn\u00e9es correspondant aux emojis, \u00e0 l'hiragana et au katakana, nous les renum\u00e9rotant dans une liste continue et les codant sous forme de deux octets au lieu de trois :<\/p>\n

      1011xxxx xxxxxxxx<\/b><\/code> <\/p>\n

      G\u00e9nial : l'emoji mentionn\u00e9 ci-dessus \u200d\u200d\u200d\"Un<\/a><\/noindex>, compos\u00e9 de 7 points de code, occupe 25 octets en UTF-8, et nous l'avons int\u00e9gr\u00e9 dans 14<\/strong> (exactement deux octets par point de code). Au fait, Habr a refus\u00e9 de le traiter (dans l'\u00e9diteur ancien et nouveau), donc j'ai d\u00fb l'ins\u00e9rer en tant qu'image.<\/p>\n

      Essayons encore de corriger un autre probl\u00e8me. Comme nous le savons, l'alphabet principal est essentiellement les 6 bits sup\u00e9rieurs<\/strong>, que nous gardons \u00e0 l'esprit, et nous les collons au code de chaque symbole d\u00e9chiffr\u00e9 suivant. Pour ce qui est des caract\u00e8res chinois, qui se trouvent dans le bloc 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, c'est soit un bit 0, soit un bit 1. Ce n'est pas tr\u00e8s pratique : nous devrons constamment changer d'alphabet entre ces deux valeurs (c'est-\u00e0-dire d\u00e9penser trois octets). Mais remarquons que dans le mode long, nous pouvons soustraire du code le nombre de caract\u00e8res que nous codons avec le mode court (apr\u00e8s tous les subtilit\u00e9s mentionn\u00e9es ci-dessus, cela fait 10240) \u2014 alors la plage des id\u00e9ogrammes sera d\u00e9cal\u00e9e \u00e0 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, et dans ce cas, dans toute cette plage, les 6 bits les plus significatifs (sur 21) seront \u00e9gaux \u00e0 0. Ainsi, les s\u00e9quences d'id\u00e9ogrammes utiliseront deux octets par id\u00e9ogramme (ce qui est optimal pour une si grande plage), sans provoquer de changements d'alphabet. <\/p>\n

      Solutions alternatives : SCSU, BOCU-1<\/h2>\n

      \nLes connaisseurs de Unicode, apr\u00e8s avoir lu le titre de l'article, sont probablement impatients de rappeler qu'il existe directement parmi les normes Unicode Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU), qui d\u00e9crit une m\u00e9thode de codage tr\u00e8s similaire \u00e0 celle d\u00e9crite dans cet article.<\/p>\n

      J'avoue honn\u00eatement : j'ai d\u00e9couvert son existence seulement apr\u00e8s m'\u00eatre profond\u00e9ment plong\u00e9 dans l'\u00e9criture de ma solution. Si je l'avais su d\u00e8s le d\u00e9part, j'aurais probablement essay\u00e9 d'\u00e9crire son impl\u00e9mentation au lieu de concevoir ma propre approche.<\/p>\n

      Ce qui est int\u00e9ressant, c'est que SCSU utilise des id\u00e9es tr\u00e8s similaires \u00e0 celles auxquelles je suis arriv\u00e9 moi-m\u00eame (au lieu du concept \u00ab d'alphabets \u00bb, il utilise des \u00ab fen\u00eatres \u00bb, et il y en a plus que je n'en ai). En m\u00eame temps, ce format a aussi des inconv\u00e9nients : il est un peu plus proche des algorithmes de compression que du codage. En particulier, la norme propose plusieurs fa\u00e7ons de repr\u00e9sentation, mais ne dit pas comment choisir l'optimale \u2014 pour cela, l'encodeur doit appliquer certaines heuristiques. Ainsi, un encodeur SCSU qui donne un bon conditionnement sera plus complexe et plus encombrant que mon algorithme.<\/p>\n

      Pour la comparaison, j'ai transf\u00e9r\u00e9 une impl\u00e9mentation relativement simple de SCSU en JavaScript \u2014 en termes de code, elle s'est r\u00e9v\u00e9l\u00e9e comparable \u00e0 mon UTF-C, mais dans certains cas, elle a montr\u00e9 des r\u00e9sultats de plusieurs dizaines de pourcentages pires (elle peut parfois le surpasser, mais pas de beaucoup). Par exemple, les textes en h\u00e9breu et en grec UTF-C ont \u00e9t\u00e9 cod\u00e9s jusqu'\u00e0 60% mieux que SCSU<\/strong> (probablement en raison de leurs alphabets compacts).<\/p>\n

      Je rajoute que, en plus de SCSU, il existe \u00e9galement une autre m\u00e9thode de repr\u00e9sentation compacte de l'Unicode \u2014 BOCU-1<\/a><\/noindex>, mais il vise la compatibilit\u00e9 avec MIME (ce qui n'\u00e9tait pas n\u00e9cessaire pour moi) et utilise une approche l\u00e9g\u00e8rement diff\u00e9rente pour le codage. Je n'ai pas \u00e9valu\u00e9 son efficacit\u00e9, mais je pense qu'elle ne sera gu\u00e8re sup\u00e9rieure \u00e0 celle de SCSU.<\/p>\n

      Am\u00e9liorations possibles<\/h2>\n

      \nL'algorithme que j'ai propos\u00e9 n'est pas universel par conception (c'est probablement dans ce sens que mes objectifs divergent le plus de ceux du consortium Unicode). J'ai d\u00e9j\u00e0 mentionn\u00e9 qu'il a \u00e9t\u00e9 principalement con\u00e7u pour une t\u00e2che sp\u00e9cifique (le stockage d'un dictionnaire multilingue dans un arbre pr\u00e9fixe), et certaines de ses caract\u00e9ristiques peuvent mal convenir \u00e0 d'autres t\u00e2ches. Mais le fait qu'il ne soit pas standard peut aussi \u00eatre un avantage \u2014 vous pouvez facilement l'adapter \u00e0 vos besoins<\/strong>.<\/p>\n

      Par exemple, on peut facilement se d\u00e9barrasser de l'\u00e9tat, rendant le codage stateless \u2014 il suffit de ne pas mettre \u00e0 jour les variables offres<\/b><\/code>, auxOffs<\/b><\/code> et est21Bit<\/b><\/code> dans l'encodeur et le d\u00e9codeur. Dans ce cas, il ne sera pas possible d'emballer efficacement des s\u00e9quences de caract\u00e8res d'un m\u00eame alphabet, mais il y aura la garantie qu'un m\u00eame caract\u00e8re est toujours cod\u00e9 avec les m\u00eames octets, ind\u00e9pendamment du contexte.<\/p>\n

      De plus, il est possible de personnaliser le codeur pour une langue sp\u00e9cifique, en modifiant l'\u00e9tat par d\u00e9faut \u2014 par exemple, en se basant sur des textes russes, il serait judicieux de d\u00e9finir au d\u00e9but de l'encodeur et du d\u00e9codeur offs = 0x0400<\/b><\/code> et auxOffs = 0<\/b><\/code>. En particulier, cela a du sens dans le mode stateless. Dans l'ensemble, cela ressemblera \u00e0 l'utilisation d'un ancien code \u00e0 huit bits, tout en permettant d'incorporer des caract\u00e8res de tout le Unicode si n\u00e9cessaire.<\/p>\n

      Un autre inconv\u00e9nient, mentionn\u00e9 pr\u00e9c\u00e9demment \u2014 dans un texte volumineux encod\u00e9 en UTF-C, il n'existe pas de moyen rapide de trouver la limite d'un caract\u00e8re proche d'un octet arbitraire. Si vous coupez les 100 derniers octets d'un tampon cod\u00e9, vous risquez d'obtenir des donn\u00e9es corrompues, avec lesquelles il n'y a rien \u00e0 faire. Le codage n'est pas con\u00e7u pour conserver des logs de plusieurs gigaoctets, mais cela peut \u00eatre corrig\u00e9 dans l'ensemble. Un octet 0xBF<\/b><\/code> ne doit jamais appara\u00eetre comme premier octet (mais peut \u00eatre second ou troisi\u00e8me). Ainsi, lors du codage, il est possible d'ins\u00e9rer une s\u00e9quence 0xBF 0xBF 0xBF<\/b><\/code> tous les, disons, 10 Ko \u2014 alors, en cas de besoin, il suffira de scanner la section choisie jusqu'\u00e0 ce qu'un tel marqueur soit trouv\u00e9. Apr\u00e8s le dernier 0xBF<\/b><\/code> le d\u00e9but d'un caract\u00e8re sera garanti. (Lors du d\u00e9codage, il faudra bien s\u00fbr ignorer cette s\u00e9quence de trois octets.)<\/p>\n

      En r\u00e9sum\u00e9<\/h2>\n

      \nSi vous \u00eates arriv\u00e9 ici, f\u00e9licitations ! J'esp\u00e8re que vous, comme moi, avez appris quelque chose de nouveau (ou raffra\u00eechi votre m\u00e9moire) sur le fonctionnement de l'Unicode.<\/p>\n

      \"Un
      \nPage de d\u00e9monstration. L'exemple de l'h\u00e9breu montre les avantages tant par rapport \u00e0 l'UTF-8 qu'\u00e0 SCSU.<\/i><\/p>\n

      Il ne faut pas consid\u00e9rer les recherches d\u00e9crites ci-dessus comme une atteinte aux normes. Cependant, je suis globalement satisfait des r\u00e9sultats de mes travaux, donc je suis heureux de les partager<\/a><\/noindex>: par exemple, la biblioth\u00e8que JS en version minifi\u00e9e ne p\u00e8se que 1710 octets (et n'a bien s\u00fbr pas de d\u00e9pendances). Comme je l'ai mentionn\u00e9 pr\u00e9c\u00e9demment, son fonctionnement peut \u00eatre consult\u00e9 sur la page de d\u00e9monstration<\/a><\/noindex> (o\u00f9 il y a aussi un ensemble de textes avec lesquels elle peut \u00eatre compar\u00e9e \u00e0 UTF-8 et SCSU).<\/p>\n

      Enfin, je voudrais souligner \u00e0 nouveau les cas o\u00f9 il ne faut pas utiliser UTF-C peut-\u00eatre<\/b>:<\/p>\n

      Regardons les blocs Unicode qui n\u00e9cessitent actuellement trois octets. Principalement, comme mentionn\u00e9, ce sont des caract\u00e8res chinois \u2014 mais il est difficile d\u2019agir sur ceux-ci, il y en a 21 000. Mais il y a aussi l'hiragana et le katakana \u2014 et ceux-ci sont d\u00e9j\u00e0 moins nombreux, moins de deux cents. Et puisque nous avons \u00e9voqu\u00e9 les Japonais \u2014 il y a aussi des emojis (en r\u00e9alit\u00e9, ils sont \u00e9parpill\u00e9s dans Unicode, mais les blocs principaux sont dans la plage 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Si l'on consid\u00e8re qu'il existe maintenant des emojis qui se composent de plusieurs points de code (par exemple, l'emoji \u200d\u200d\u200d\"Un<\/a><\/noindex> se compose de pas moins de 7 codes !), alors il est vraiment dommage de gaspiller trois octets pour chacun d'eux (7\u00d73 = 21 octets pour un seul symbole, c'est un cauchemar).<\/p>\n