{"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\/es\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Otro invento: almacenamos cadenas Unicode de un 30-60% m\u00e1s compactas que UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Otro
\n
\nSi eres desarrollador y tienes que elegir una codificaci\u00f3n, casi siempre la soluci\u00f3n correcta ser\u00e1 Unicode. La forma espec\u00edfica de representaci\u00f3n depende del contexto, pero a menudo tambi\u00e9n hay una respuesta universal: UTF-8. Es bueno porque permite usar todos los caracteres de Unicode sin gastar demasiado<\/em> byte en la mayor\u00eda de los casos. Sin embargo, para los idiomas que utilizan no solo el alfabeto latino, 'no demasiado' significa al menos dos bytes por car\u00e1cter<\/strong>. \u00bfSe puede hacer mejor, sin volver a codificaciones prehist\u00f3ricas que nos limitan a solo 256 s\u00edmbolos disponibles?<\/p>\n

A continuaci\u00f3n, le propongo conocer mi intento de responder a esta pregunta y la implementaci\u00f3n de un algoritmo relativamente simple que permite almacenar cadenas en la mayor\u00eda de los idiomas del mundo, sin a\u00f1adir la redundancia que existe en UTF-8.<\/a><\/noindex><\/p>\n

Descargo de responsabilidad.<\/i> Primero har\u00e9 unas importantes aclaraciones: la soluci\u00f3n descrita no se ofrece como un sustituto universal de UTF-8<\/strong>, solo es adecuada para un conjunto espec\u00edfico de casos (que se describen a continuaci\u00f3n), y de ning\u00fan modo debe utilizarse para la interacci\u00f3n con API externas (que no tienen conocimiento de ella). En la mayor\u00eda de los casos, los algoritmos de compresi\u00f3n de prop\u00f3sito general (como deflate) son adecuados para almacenar grandes vol\u00famenes de datos textuales de manera compacta. Adem\u00e1s, ya en el proceso de crear mi soluci\u00f3n, encontr\u00e9 un est\u00e1ndar existente en Unicode que resuelve el mismo problema: es un poco m\u00e1s complicado (y a menudo peor), pero sigue siendo un est\u00e1ndar aceptado y no algo hecho improvisadamente. Tambi\u00e9n hablar\u00e9 de eso.<\/p>\n

Sobre Unicode y UTF-8<\/h2>\n

\nPara empezar, unas palabras sobre qu\u00e9 es en general Unicode<\/strong> y UTF-8<\/strong>.<\/p>\n

Como es sabido, antes eran populares las codificaciones de 8 bits. Con ellas todo era simple: 256 s\u00edmbolos pueden numerarse con n\u00fameros del 0 al 255, y los n\u00fameros del 0 al 255 se pueden representar de manera obvia con un solo byte. Si retrocedemos a los or\u00edgenes, la codificaci\u00f3n ASCII est\u00e1 limitada a 7 bits, por lo que el bit m\u00e1s significativo en su representaci\u00f3n byte es cero, y la mayor\u00eda de las codificaciones de 8 bits son compatibles con ella (se diferencian solo en la parte 'superior', donde el bit m\u00e1s significativo es uno).<\/p>\n

\u00bfEn qu\u00e9 se diferencia Unicode de esas codificaciones y por qu\u00e9 est\u00e1 relacionado con tantas representaciones espec\u00edficas: UTF-8, UTF-16 (BE y LE), UTF-32? Vamos a desglosarlo.<\/p>\n

El est\u00e1ndar principal de Unicode describe solo la correspondencia entre los caracteres (y en algunos casos, componentes individuales de los caracteres) y sus n\u00fameros. Y hay muchos n\u00fameros posibles en este est\u00e1ndar: desde 0x00<\/b><\/code> hasta 0x10FFFF<\/b><\/code> (1 114 112 unidades). Si quisi\u00e9ramos almacenar un n\u00famero en ese rango en una variable, ni 1 ni 2 bytes ser\u00edan suficientes. Y dado que nuestros procesadores no est\u00e1n adaptados para trabajar con n\u00fameros de tres bytes, tendr\u00edamos que usar 4 bytes para un solo car\u00e1cter. Esto es UTF-32, pero precisamente debido a este 'desperdicio', este formato no es popular.<\/p>\n

Afortunadamente, los caracteres dentro de Unicode no est\u00e1n ordenados al azar. Su gran cantidad se divide en 17 'planos<\/em>', cada uno de los cuales contiene 65536 (0x10000<\/b><\/code>) \u00abpuntos de c\u00f3digo<\/em>). El t\u00e9rmino 'punto de c\u00f3digo' aqu\u00ed es simplemente el n\u00famero de car\u00e1cter<\/em>, asignado a \u00e9l por Unicode. Pero, como se mencion\u00f3 anteriormente, en Unicode no solo se numeran los caracteres individuales, sino tambi\u00e9n sus componentes y marcas de control (y a veces ni siquiera corresponde a un n\u00famero, posiblemente hasta cierto tiempo, pero eso no nos importa), por lo que es m\u00e1s correcto hablar siempre del n\u00famero de n\u00fameros en s\u00ed, y no de caracteres. Sin embargo, m\u00e1s adelante, por brevedad, a menudo utilizar\u00e9 la palabra 'car\u00e1cter', refiri\u00e9ndome al t\u00e9rmino 'punto de c\u00f3digo'.<\/p>\n

\"Otro
\nPlanos de Unicode. Como se puede ver, la mayor parte (los planos del 4 al 13) a\u00fan no se ha utilizado.<\/i><\/p>\n

Lo m\u00e1s notable es que toda la \"pulpa\" principal est\u00e1 en el plano cero, que se llama \"Plano Multiling\u00fce B\u00e1sico<\/em>\". Si la l\u00ednea contiene texto en uno de los idiomas modernos (incluyendo chino), no saldr\u00e1s de este plano. Pero tampoco se puede cortar el resto de Unicode: por ejemplo, los emojis se encuentran principalmente al final del siguiente plano, \"Plano Multiling\u00fce Suplementario<\/em>\" (se extiende desde 0x10000<\/b><\/code> hasta 0x1FFFF<\/b><\/code>). Por lo tanto, UTF-16 procede de esta manera: todos los caracteres que caen en Plano Multiling\u00fce B\u00e1sico<\/em>, se codifican 'tal cual', con el n\u00famero de dos bytes correspondiente. Sin embargo, algunos n\u00fameros en este rango no representan caracteres espec\u00edficos, sino que indican que hay que considerar otra pareja de bytes despu\u00e9s de esta; combinando los valores de estos cuatro bytes, obtendremos un n\u00famero que abarca todo el rango permitido de Unicode. Esta representaci\u00f3n se llama 'pares de sustituci\u00f3n' \u2014 tal vez ya hayas o\u00eddo hablar de ellos.<\/p>\n

Por lo tanto, UTF-16 requiere dos o (en muy raras ocasiones) cuatro bytes por cada \"punto de c\u00f3digo\". Esto es mejor que usar constantemente cuatro bytes, pero la lat\u00ednica (y otros caracteres ASCII) en esta codificaci\u00f3n consume la mitad del espacio en ceros. UTF-8 est\u00e1 dise\u00f1ado para corregir esto: en \u00e9l, ASCII ocupa, como antes, solo un byte; los c\u00f3digos de 0x80<\/b><\/code> hasta 0x7FF<\/b><\/code> \u2014 dos bytes; de 0x800<\/b><\/code> hasta 0xFFFF<\/b><\/code> \u2014 tres, y de 0x10000<\/b><\/code> hasta 0x10FFFF<\/b><\/code> \u2014 cuatro. Por un lado, la lat\u00ednica ha mejorado: ha regresado la compatibilidad con ASCII, y la distribuci\u00f3n est\u00e1 m\u00e1s uniformemente \"esparcida\" de 1 a 4 bytes. Pero los alfabetos distintos del latino, lamentablemente, no ganan nada en comparaci\u00f3n con UTF-16, y muchos ahora requieren tres bytes en lugar de dos: el rango cubierto por la codificaci\u00f3n de dos bytes se ha reducido 32 veces, desde 0xFFFF<\/b><\/code> hasta 0x7FF<\/b><\/code>, y en \u00e9l no entran ni el chino ni, por ejemplo, el georgiano. Al cir\u00edlico y a otros cinco alfabetos - \u00a1hurra! - les fue bien, 2 bytes por s\u00edmbolo.<\/p>\n

\u00bfPor qu\u00e9 sucede esto? Veamos c\u00f3mo UTF-8 representa los c\u00f3digos de los s\u00edmbolos:
\n\"Otro
\nDirectamente para representar n\u00fameros aqu\u00ed se utilizan bits que est\u00e1n etiquetados con el s\u00edmbolo x<\/b><\/code>. Se puede ver que en la codificaci\u00f3n de dos bytes hay solo 11 bits (de 16). Los bits principales aqu\u00ed solo cumplen una funci\u00f3n de servicio. En el caso de la codificaci\u00f3n de cuatro bytes, se asignan 21 bits de 32 para el n\u00famero del punto de c\u00f3digo\u2014 parec\u00eda que con tres bytes (que dan un total de 24 bits) ser\u00eda suficiente, pero los marcadores de servicio consumen demasiado.<\/p>\n

\u00bfEs esto malo? En realidad, no mucho. Por un lado, si nos importa mucho el espacio ocupado, tenemos algoritmos de compresi\u00f3n que pueden eliminar f\u00e1cilmente toda la entrop\u00eda y redundancia innecesarias. Por otro lado, el objetivo de Unicode era proporcionar una codificaci\u00f3n lo m\u00e1s universal posible. Por ejemplo, una cadena codificada en UTF-8 se puede confiar a un c\u00f3digo que antes solo trabajaba con ASCII, y no temer que vea un s\u00edmbolo del rango ASCII que en realidad no est\u00e1 all\u00ed (porque en UTF-8, todos los bytes que comienzan con un bit cero son precisamente ASCII). Y si de repente queremos cortar una peque\u00f1a cola de una gran cadena, sin decodificarla desde el principio (o restaurar parte de la informaci\u00f3n despu\u00e9s de un \u00e1rea da\u00f1ada) \u2014 no es dif\u00edcil encontrar el desplazamiento donde comienza alg\u00fan s\u00edmbolo (basta con omitir los bytes que tienen un prefijo de bits 10<\/b><\/code>).<\/p>\n

\u00bfPor qu\u00e9 entonces inventar algo nuevo?<\/h2>\n

\nAl mismo tiempo, a veces hay situaciones en las que algoritmos de compresi\u00f3n como deflate son inaplicables, y se desea lograr un almacenamiento compacto de cadenas. Personalmente, me encontr\u00e9 con esta tarea al reflexionar sobre la construcci\u00f3n de un \u00e1rbol de prefijos comprimido<\/a><\/noindex> para un gran diccionario que incluye palabras en varios idiomas. Por un lado, cada palabra es muy corta, lo que hace que comprimirla sea inefectivo. Por otro lado, la implementaci\u00f3n del \u00e1rbol que estaba considerando estaba dise\u00f1ada para que cada byte de la cadena almacenada generara un nodo separado del \u00e1rbol, por lo que minimizar su cantidad era muy \u00fatil. En mi biblioteca Az.js<\/a><\/noindex> (al igual que en pymorphy2<\/a><\/noindex>, que es la base de esta) este problema se resuelve f\u00e1cilmente: las cadenas empacadas en el diccionario DAWG<\/a><\/noindex>se almacenan all\u00ed en el viejo y querido CP1251<\/a><\/noindex>. Sin embargo, como es f\u00e1cil de entender, esto solo funciona bien para un alfabeto limitado; una cadena en chino no se puede almacenar en tal diccionario.<\/p>\n

Me gustar\u00eda se\u00f1alar tambi\u00e9n un aspecto inc\u00f3modo que surge al usar UTF-8 en tal estructura de datos. En la imagen anterior, se puede ver que al escribir un car\u00e1cter en forma de dos bytes, los bits correspondientes a su n\u00famero no van en secuencia, sino que est\u00e1n interrumpidos por un par de bits 10<\/b><\/code> en el medio: 110xxxxx 10xxxxxx<\/b><\/code>. Debido a esto, cuando se desbordan los 6 bits menos significativos del segundo byte del c\u00f3digo del car\u00e1cter (es decir, se produce un desbordamiento 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), el primer byte tambi\u00e9n cambia. As\u00ed, la letra \u00ab\u043f\u00bb se representa con los bytes 0xD0 0xBF<\/b><\/code>, mientras que la siguiente \u00ab\u0440\u00bb ya es 0xD1 0x80<\/b><\/code>. En el \u00e1rbol de prefijos, esto conduce a la divisi\u00f3n del nodo padre en dos: uno para el prefijo 0xD0<\/b><\/code>, y otro para 0xD1<\/b><\/code> (aunque toda la escritura cir\u00edlica podr\u00eda codificarse solo con el segundo byte).<\/p>\n

Lo que logr\u00e9<\/h2>\n

\nEnfrentado a este reto, decid\u00ed practicar con juegos de bits y, de paso, conocer mejor la estructura de Unicode en general. El resultado fue un formato de codificaci\u00f3n llamado UTF-C (\u2018C\u2019 de compacto<\/em>), que no utiliza m\u00e1s de 3 bytes por cada punto de c\u00f3digo, y que a menudo permite utilizar solo un byte adicional para toda la cadena codificada<\/strong>. Esto resulta en que para muchos alfabetos no ASCII, tal codificaci\u00f3n es 30-60% m\u00e1s compacta que UTF-8<\/strong>.<\/p>\n

. He presentado ejemplos de implementaci\u00f3n de los algoritmos de codificaci\u00f3n y decodificaci\u00f3n en forma de bibliotecas en JavaScript y Go<\/a><\/noindex>, puede utilizarlos libremente en su c\u00f3digo. Sin embargo, subrayo que, en cierto modo, este formato sigue siendo una \u201cbicicleta\u201d y no lo recomiendo usar sin tener claro por qu\u00e9 lo necesita<\/strong>. Al fin y al cabo, es m\u00e1s un experimento que una verdadera \u201cmejora de UTF-8\u201d. Sin embargo, el c\u00f3digo est\u00e1 bien escrito, es conciso, con muchos comentarios y cobertura de pruebas.<\/p>\n

\"Otro
\nResultados de la ejecuci\u00f3n de pruebas y comparaci\u00f3n con UTF-8<\/i><\/p>\n

Tambi\u00e9n he creado una p\u00e1gina de demostraci\u00f3n<\/a><\/noindex>, donde puedes evaluar el funcionamiento del algoritmo, y m\u00e1s adelante contar\u00e9 m\u00e1s sobre sus principios y el proceso de desarrollo.<\/p>\n

Eliminando bits redundantes<\/h2>\n

\nComo base, tom\u00e9, por supuesto, UTF-8. Lo primero y m\u00e1s obvio que se puede cambiar es reducir el n\u00famero de bits de control en cada byte. Por ejemplo, el primer byte en UTF-8 siempre comienza con 0<\/b><\/code>, o con 11<\/b><\/code> \u2014 y el prefijo 10<\/b><\/code> solo est\u00e1 presente en los siguientes bytes. Cambiemos el prefijo 11<\/b><\/code> en 1<\/b><\/code>, y en los siguientes bytes eliminemos los prefijos por completo. \u00bfQu\u00e9 obtendremos?<\/p>\n

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

Espera, \u00bfy d\u00f3nde est\u00e1 el registro de cuatro bytes? Ya no es necesario \u2014 al usar tres bytes ahora tenemos disponible 21 bits y esto es m\u00e1s que suficiente para todos los n\u00fameros hasta 0x10FFFF<\/b><\/code>.<\/p>\n

\u00bfQu\u00e9 sacrificamos aqu\u00ed? Lo m\u00e1s importante es la detecci\u00f3n de los l\u00edmites de los caracteres desde cualquier parte del buffer. No podemos simplemente apuntar a un byte y desde ah\u00ed encontrar el inicio del siguiente car\u00e1cter. Esta es una limitaci\u00f3n de nuestro formato, pero en la pr\u00e1ctica no suele ser necesario. Normalmente, podemos recorrer el buffer desde el principio (especialmente cuando se trata de cadenas cortas).<\/p>\n

La situaci\u00f3n con la representaci\u00f3n de idiomas con 2 bytes tambi\u00e9n ha mejorado: ahora el formato de dos bytes proporciona un rango de 14 bits, lo que equivale a c\u00f3digos hasta 0x3FFF<\/b><\/code>. Los chinos no tienen suerte (sus caracteres principalmente est\u00e1n en el rango de 0x4E00<\/b><\/code> hasta 0x9FFF<\/b><\/code>), pero los georgianos y muchos otros pueblos se alegran \u2014 sus idiomas tambi\u00e9n se ajustan a 2 bytes por car\u00e1cter.<\/p>\n

Introduciendo el estado del codificador<\/h2>\n

\nAhora pensemos en las propiedades de las cadenas mismas. En el diccionario, a menudo hay palabras escritas con caracteres de un solo alfabeto, y esto tambi\u00e9n es cierto para muchos otros textos. Ser\u00eda bueno indicar este alfabeto una vez y luego solo mencionar el n\u00famero de la letra dentro de \u00e9l. Veamos si la ubicaci\u00f3n de los caracteres en la tabla de Unicode nos ayuda.<\/p>\n

Como se mencion\u00f3 anteriormente, Unicode se divide en plano<\/em> por 65536 c\u00f3digos cada uno. Sin embargo, esta divisi\u00f3n no es muy \u00fatil (como ya se ha mencionado, la mayor\u00eda de las veces estamos en el plano cero). Una divisi\u00f3n m\u00e1s interesante es la de bloques.<\/em> Estos rangos ya no tienen una longitud fija y tienen m\u00e1s sentido; por lo general, cada uno agrupa s\u00edmbolos de un mismo alfabeto.<\/p>\n

\"Otro
\nBloque que contiene s\u00edmbolos del alfabeto bengal\u00ed. Desafortunadamente, por razones hist\u00f3ricas, este es un ejemplo de empaquetado no muy denso: 96 s\u00edmbolos est\u00e1n distribuidos ca\u00f3ticamente en 128 puntos de c\u00f3digo del bloque.<\/i><\/p>\n

Los inicios de los bloques y sus tama\u00f1os siempre son m\u00faltiplos de 16, lo que se hace simplemente por conveniencia. Adem\u00e1s, muchos bloques comienzan y terminan en valores que son m\u00faltiplos de 128 o incluso de 256; por ejemplo, el alfabeto cir\u00edlico b\u00e1sico ocupa 256 bytes desde 0x0400<\/b><\/code> hasta 0x04FF<\/b><\/code>. Esto es bastante conveniente: si una vez guardamos el prefijo 0x04<\/b><\/code>, entonces cualquier s\u00edmbolo cir\u00edlico se puede representar con un solo byte. Sin embargo, as\u00ed perdemos la posibilidad de volver a ASCII (y a cualquier otro s\u00edmbolo en general). Por lo tanto, hacemos lo siguiente:<\/p>\n

    \n
  1. Dos bytes 10yyyyyy yxxxxxxx<\/b><\/code> no solo representan el s\u00edmbolo con el n\u00famero yyyyyy yxxxxxxx<\/b><\/code>, sino que tambi\u00e9n cambian el alfabeto actual<\/em> en yyyyyy y0000000<\/b><\/code> es decir, recordamos todos los bits, excepto los menos significativos. 7 bits<\/strong>);<\/li>\n
  2. Un byte 0xxxxxxx<\/b><\/code> es un s\u00edmbolo del alfabeto actual. Simplemente hay que sumarlo al desplazamiento que hemos recordado en el paso 1. Mientras no hayamos cambiado el alfabeto, el desplazamiento es cero, as\u00ed que hemos mantenido la compatibilidad con ASCII.<\/li>\n<\/ol>\n

    \nDe manera similar para los c\u00f3digos que requieren 3 bytes:<\/p>\n

      \n
    1. Tres bytes 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> representan el s\u00edmbolo con el n\u00famero yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, cambian el alfabeto actual<\/em> en yyyyyy y0000000 00000000<\/b><\/code> (recordamos todo, excepto los menos significativos 15 bits<\/strong>), y ponen una bandera de que ahora estamos en modo largo<\/em> en modo largo, este es un s\u00edmbolo del alfabeto actual. De manera similar, lo sumamos al desplazamiento del paso 1. La \u00fanica diferencia es que ahora leemos dos bytes (porque hemos cambiado a ese modo).<\/li>\n
    2. Dos bytes 0xxxxxxx xxxxxxxx<\/b><\/code> Suena bien: ahora, mientras necesitemos codificar s\u00edmbolos de un mismo rango de 7 bits de Unicode, gastamos 1 byte extra al principio y solo un byte por cada s\u00edmbolo.<\/li>\n<\/ol>\n

      \nTrabajo de una de las primeras versiones. Ya supera a UTF-8 con frecuencia, pero a\u00fan hay mucho que mejorar.<\/p>\n

      \"Otro
      \n\u00bfQu\u00e9 ha empeorado? En primer lugar, tenemos un estado, a saber,<\/i><\/p>\n

      el desplazamiento del alfabeto actual y la bandera<\/em> de modo largo. modo largo<\/em>Esto nos limita adicionalmente: ahora los mismos caracteres pueden estar codificados de diferentes maneras en diferentes contextos. La b\u00fasqueda de subcadenas, por ejemplo, tendr\u00e1 que hacerse teniendo esto en cuenta, y no simplemente comparando bytes. En segundo lugar, tan pronto como cambiamos el alfabeto, hubo problemas con la codificaci\u00f3n de caracteres ASCII (y esto no solo incluye caracteres latinos, sino tambi\u00e9n puntuaci\u00f3n b\u00e1sica, incluidos los espacios) \u2014 requieren un nuevo cambio de alfabeto en 0, es decir, de nuevo un byte adicional (y luego otro para volver a nuestro alfabeto principal).<\/p>\n

      Un alfabeto est\u00e1 bien, dos \u2014 mejor<\/h2>\n

      \nIntentemos cambiar un poco nuestros prefijos de bits, a\u00f1adiendo uno m\u00e1s a los tres descritos anteriormente:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 byte en modo normal, 2 en modo extendido
      \n11xxxxxx<\/b><\/code> \u2014 1 byte
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 bytes
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 bytes<\/p>\n

      \"Otro
      \n
      \nAhora en la codificaci\u00f3n de dos bytes hay un bit menos disponible \u2014 se pueden codificar puntos hasta 0x1FFF<\/b><\/code>, y no 0x3FFF<\/b><\/code>. Sin embargo, sigue siendo notablemente m\u00e1s que en los c\u00f3digos de dos bytes de UTF-8, la mayor parte de los idiomas comunes todav\u00eda cabe, la p\u00e9rdida m\u00e1s notable \u2014 se cay\u00f3       hiragana<\/a><\/noindex> y katakana<\/a><\/noindex>, los japoneses est\u00e1n tristes.<\/p>\n

      \u00bfCu\u00e1l es el nuevo c\u00f3digo 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 (auxiliary<\/em>) del alfabeto. Cuando cambiamos el alfabeto actual, un fragmento del alfabeto antiguo se convierte en auxiliar. Por ejemplo, cambiamos de ASCII a cir\u00edlico \u2014 ahora hay 64 caracteres en el 'almac\u00e9n' que contienen caracteres latinos, n\u00fameros, espacios y una coma<\/strong> (las inserciones m\u00e1s comunes en textos no ASCII). Si cambiamos de nuevo a ASCII \u2014 el alfabeto auxiliar se convertir\u00e1 en la parte principal del cir\u00edlico.<\/p>\n

      Gracias al acceso a dos alfabetos, podemos manejar una mayor cantidad de textos con un costo m\u00ednimo de cambio de alfabetos (la puntuaci\u00f3n generalmente llevar\u00e1 a regresar a ASCII, pero despu\u00e9s de eso, muchos caracteres no ASCII los obtendremos del alfabeto adicional, sin necesidad de un cambio adicional).<\/p>\n

      Bonus: al designar el alfabeto adicional con un prefijo 11xxxxxx<\/b><\/code> y elegir su desplazamiento inicial igual a 0xC0<\/b><\/code>, obtenemos compatibilidad parcial con CP1252. En otras palabras, muchos (pero no todos) los textos de Europa occidental codificados en CP1252 se ver\u00e1n igual en UTF-C.<\/p>\n

      Aqu\u00ed, sin embargo, surge una dificultad: \u00bfc\u00f3mo obtener el auxiliar del alfabeto principal? Se puede dejar el mismo desplazamiento, pero \u2014 desafortunadamente \u2014 aqu\u00ed la estructura de Unicode ya juega en nuestra contra. Muy a menudo la parte principal del alfabeto no est\u00e1 al inicio del bloque (por ejemplo, la 'A' may\u00fascula rusa tiene c\u00f3digo 0x0410<\/b><\/code>, aunque el bloque cir\u00edlico comienza con 0x0400<\/b><\/code>). Por lo tanto, al tomar en 'cach\u00e9' los primeros 64 caracteres, es posible que perdamos acceso a la parte final del alfabeto.<\/p>\n

      Para resolver este problema, revis\u00e9 manualmente algunos bloques correspondientes a diferentes idiomas y se\u00f1al\u00e9 el desplazamiento del alfabeto auxiliar dentro del principal. En el caso del alfabeto latino, por excepci\u00f3n, lo reorden\u00e9 completamente al estilo de base64.<\/p>\n

      \"Otro<\/p>\n

      Los toques finales<\/h2>\n

      \nPensemos por \u00faltimo d\u00f3nde m\u00e1s podr\u00edamos mejorar algo.<\/p>\n

      Notemos que el formato 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> permite codificar n\u00fameros hasta 0x1FFFFF<\/b><\/code>, mientras que Unicode termina antes, en 0x10FFFF<\/b><\/code>. En otras palabras, el \u00faltimo punto de c\u00f3digo se representar\u00e1 como 10110000 11111111 11111111<\/b><\/code>. Por lo tanto, podemos decir que si el primer byte tiene la forma 1011xxxx<\/b><\/code> (donde xxxx<\/b><\/code> es mayor que 0), significa algo m\u00e1s. Por ejemplo, se pueden a\u00f1adir otros 15 caracteres, siempre disponibles para codificaci\u00f3n en un byte, pero decid\u00ed proceder de otra manera.<\/p>\n

      Por lo tanto, elegimos algunos rangos seleccionados que corresponden a emojis, hiragana y katakana, los renumeramos en una sola lista continua y los codificamos en forma de dos bytes en lugar de tres:<\/p>\n

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

      Genial: el mencionado emoji \u200d\u200d\u200d\"Otro<\/a><\/noindex>, que consiste en 7 puntos de c\u00f3digo, en UTF-8 ocupa 25 bytes, y nosotros lo hemos comprimido en 14<\/strong> (exactamente dos bytes para cada punto de c\u00f3digo). A prop\u00f3sito, Habr se neg\u00f3 a procesarlo (tanto en el antiguo como en el nuevo editor), as\u00ed que tuve que insertarlo como imagen.<\/p>\n

      Intentemos corregir otro problema. Como recordamos, el alfabeto principal es, en esencia, los 6 bits m\u00e1s significativos<\/strong>, que mantenemos en mente y adjuntamos al c\u00f3digo de cada s\u00edmbolo decodificado subsiguiente. En el caso de los caracteres chinos que est\u00e1n en el bloque 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, es un bit 0 o 1. No es muy conveniente: tendremos que alternar constantemente entre estos dos valores (es decir, gastar tres bytes cada vez). Sin embargo, notemos que en el modo largo podemos restar del propio c\u00f3digo el n\u00famero de caracteres que estamos codificando mediante el modo corto (despu\u00e9s de todas las astucias descritas anteriormente, esto son 10240) \u2014 as\u00ed el rango de los caracteres se trasladar\u00e1 a 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, y en este caso, en todo este rango, los 6 bits superiores (de 21) ser\u00e1n iguales a 0. As\u00ed, las secuencias de caracteres utilizar\u00e1n dos bytes por car\u00e1cter (lo que es \u00f3ptimo para un rango tan grande), sin requerir cambios de alfabeto. <\/p>\n

      Soluciones alternativas: SCSU, BOCU-1<\/h2>\n

      \nLos conocedores de Unicode, al leer el t\u00edtulo del art\u00edculo, probablemente se apresuren a recordar que dentro de los est\u00e1ndares de Unicode hay Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU), que describe un m\u00e9todo de codificaci\u00f3n bastante similar al que se menciona en el art\u00edculo.<\/p>\n

      Confieso sinceramente: su existencia solo la descubr\u00ed despu\u00e9s de haberme sumergido profundamente en la escritura de mi propia soluci\u00f3n. Si hubiera sabido de \u00e9l desde el principio, probablemente habr\u00eda intentado escribir su implementaci\u00f3n en lugar de idear mi propio enfoque.<\/p>\n

      Curiosamente, SCSU utiliza ideas muy parecidas a las que desarroll\u00e9 por mi cuenta (en lugar del concepto de \u00abalfabetos\u00bb, se utilizan \u00abventanas\u00bb, y hay m\u00e1s disponibles que los m\u00edos). Al mismo tiempo, este formato tambi\u00e9n tiene desventajas: est\u00e1 un poco m\u00e1s cerca de los algoritmos de compresi\u00f3n que de la codificaci\u00f3n. En particular, el est\u00e1ndar ofrece m\u00faltiples formas de representaci\u00f3n, pero no indica c\u00f3mo elegir la \u00f3ptima: para esto, el codificador debe aplicar ciertas heur\u00edsticas. Por lo tanto, un codificador SCSU que brinde una buena compresi\u00f3n ser\u00e1 m\u00e1s complicado y voluminoso que mi algoritmo.<\/p>\n

      Para comparar, traslad\u00e9 una implementaci\u00f3n relativamente simple de SCSU a JavaScript \u2014 en cuanto a volumen de c\u00f3digo fue comparable a mi UTF-C, pero en varios casos mostr\u00f3 resultados decenas de por ciento inferiores (en ocasiones puede superarlo, pero no mucho). Por ejemplo, textos en hebreo y griego fueron codificados en UTF-C un 60% mejor que SCSU<\/strong> (probablemente debido a sus compactos alfabetos).<\/p>\n

      Adem\u00e1s, a\u00f1adir\u00e9 que, adem\u00e1s de SCSU, tambi\u00e9n existe otro m\u00e9todo de representaci\u00f3n compacta de Unicode \u2014 BOCU-1<\/a><\/noindex>, pero tiene como objetivo la compatibilidad con MIME (lo cual no necesitaba), y utiliza un enfoque ligeramente diferente para la codificaci\u00f3n. No he evaluado su eficacia, pero me parece que no ser\u00e1 mayor que la de SCSU.<\/p>\n

      Posibles mejoras<\/h2>\n

      \nEl algoritmo que he presentado no es universal por dise\u00f1o (en esto, probablemente, mis objetivos divergen m\u00e1s de los del consorcio Unicode). Ya mencion\u00e9 que fue desarrollado principalmente para una tarea (almacenamiento de un diccionario multiling\u00fce en un \u00e1rbol de prefijo), y algunas de sus caracter\u00edsticas pueden no ser adecuadas para otras tareas. Pero el hecho de que no sea un est\u00e1ndar puede ser tambi\u00e9n una ventaja \u2014 puedes adaptarlo f\u00e1cilmente a tus necesidades<\/strong>.<\/p>\n

      Por ejemplo, de manera obvia se puede eliminar la necesidad de estado, haciendo la codificaci\u00f3n sin estado: simplemente no actualizar las variables ofertas<\/b><\/code>, auxOffs<\/b><\/code> y is21Bit<\/b><\/code> en el codificador y el decodificador. En ese caso, no podr\u00e1s empaquetar de manera eficiente secuencias de caracteres de un mismo alfabeto, pero garantizas que el mismo car\u00e1cter siempre se codifica con los mismos bytes, independientemente del contexto.<\/p>\n

      Adem\u00e1s, se puede afinar el codificador para un idioma espec\u00edfico, cambiando el estado por defecto \u2014 por ejemplo, orient\u00e1ndose hacia textos en ruso, configurando al principio del codificador y del decodificador offs = 0x0400<\/b><\/code> y auxOffs = 0<\/b><\/code>. Esto tiene sentido especialmente en el caso del modo sin estado. En general, esto ser\u00e1 similar al uso de codificaci\u00f3n de ocho bits antigua, solo que no limita la posibilidad de insertar caracteres de todo Unicode seg\u00fan sea necesario.<\/p>\n

      Otra desventaja, mencionada anteriormente, es que en un texto voluminoso codificado en UTF-C no hay una forma r\u00e1pida de encontrar el l\u00edmite de un car\u00e1cter cercano a un byte arbitrario. Si cortas del buffer codificado los \u00faltimos, digamos, 100 bytes, corres el riesgo de obtener basura, con la que no se puede hacer nada. La codificaci\u00f3n no est\u00e1 dise\u00f1ada para almacenar logs de varios gigabytes, pero en general esto se puede corregir. El byte 0xBF<\/b><\/code> nunca debe encontrarse como primer byte (pero puede ser el segundo o tercero). Por lo tanto, al codificar se puede insertar una secuencia 0xBF 0xBF 0xBF<\/b><\/code> cada, digamos, 10 Kb \u2014 as\u00ed que cuando sea necesario, para encontrar el l\u00edmite ser\u00e1 suficiente escanear el trozo seleccionado hasta que se encuentre un marcador similar. Tras el \u00faltimo 0xBF<\/b><\/code> garantizado ser\u00e1 el inicio de un car\u00e1cter. (Al decodificar, esta secuencia de tres bytes, por supuesto, debe ser ignorada.)<\/p>\n

      Resumiendo<\/h2>\n

      \nSi has llegado hasta aqu\u00ed, \u00a1felicitaciones! Espero que t\u00fa, al igual que yo, hayas aprendido algo nuevo (o refrescado lo antiguo) sobre la tecnolog\u00eda Unicode.<\/p>\n

      \"Otro
      \nP\u00e1gina de demostraci\u00f3n. A trav\u00e9s del hebreo se pueden ver las ventajas tanto frente a UTF-8 como ante SCSU.<\/i><\/p>\n

      No se deben considerar las investigaciones anteriores como una invasi\u00f3n a los est\u00e1ndares. Sin embargo, en general estoy satisfecho con los resultados de mi trabajo y por eso estoy feliz de compartir<\/a><\/noindex>: por ejemplo, la biblioteca JS en su versi\u00f3n minimizada ocupa solo 1710 bytes (y, por supuesto, no tiene dependencias). Como mencion\u00e9 anteriormente, se puede ver su funcionamiento en la p\u00e1gina de demostraci\u00f3n<\/a><\/noindex> (all\u00ed tambi\u00e9n hay un conjunto de textos para compararla con UTF-8 y SCSU).<\/p>\n

      Por \u00faltimo, me gustar\u00eda volver a llamar la atenci\u00f3n sobre los casos en los que usar UTF-C no vale la pena<\/b>:<\/p>\n

      Veamos aquellos bloques de Unicode que requieren tres bytes actualmente. En su mayor\u00eda, como ya se mencion\u00f3, son caracteres chinos, pero es dif\u00edcil hacer algo al respecto, hay 21 mil. Sin embargo, tambi\u00e9n se incluyen hiragana y katakana, que son menos de doscientos. Y, dado que hemos mencionado a los japoneses, all\u00ed tambi\u00e9n est\u00e1n los emojis (en realidad est\u00e1n esparcidos en muchas partes de Unicode, pero los bloques principales est\u00e1n en el rango 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Si pensamos en el hecho de que ahora existen emojis que se componen de varios puntos de c\u00f3digo (por ejemplo, el emoji \u200d\u200d\u200d\"Otro<\/a><\/noindex> se compone de hasta 7 c\u00f3digos), resulta muy desafortunado gastar tres bytes en cada uno (7\u00d73 = 21 bytes por un solo s\u00edmbolo, es un verdadero desastre).<\/p>\n