{"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\/it\/blog\/administrirovanie\/eshhyo-odin-velosiped-hranim-yunikodnye-stroki-na-30-60-kompaktnee-chem-utf-8","title":{"rendered":"Un'altra bicicletta: memorizziamo le stringhe Unicode da 30-60% pi\u00f9 compatte rispetto a UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Un'altra
\n
\nSe sei uno sviluppatore e hai il compito di scegliere una codifica, quasi sempre la scelta giusta sar\u00e0 Unicode. Il modo specifico di rappresentazione dipende dal contesto, ma pi\u00f9 spesso c'\u00e8 anche una risposta universale: UTF-8. \u00c8 utile perch\u00e9 consente di utilizzare tutti i caratteri di Unicode, senza sprecare troppi<\/em> byte nella maggior parte dei casi. Tuttavia, per le lingue che utilizzano non solo l'alfabeto latino, \"non troppi\" significa almeno due byte per carattere<\/strong>. \u00c8 possibile fare di meglio, senza tornare a codifiche preistoriche che ci limitano a sole 256 simboli disponibili?<\/p>\n

Di seguito, ti propongo di conoscere il mio tentativo di rispondere a questa domanda e implementare un algoritmo relativamente semplice che consente di memorizzare stringhe nella maggior parte delle lingue del mondo, senza aggiungere quel ridondanza che \u00e8 presente in UTF-8.<\/a><\/noindex><\/p>\n

Disclaimer.<\/i> Innanzitutto, far\u00f2 alcune importanti precisazioni: la soluzione descritta non \u00e8 proposta come una sostituzione universale di UTF-8<\/strong>, si adatta solo a un elenco ristretto di casi (di cui parler\u00f2 pi\u00f9 avanti), e non deve in alcun modo essere utilizzata per interagire con API esterne (che non ne sanno nulla). Spesso, per un'archiviazione compatta di grandi volumi di dati testuali, sono adatti algoritmi di compressione generali (per esempio, deflate). Inoltre, gi\u00e0 durante la creazione della mia soluzione, ho trovato uno standard esistente all'interno di Unicode, che risolve lo stesso problema: \u00e8 un po' pi\u00f9 complesso (e spesso peggiore), ma comunque \u00e8 uno standard accettato e non assemblato alla rinfusa. Di questo parler\u00f2 anch'io.<\/p>\n

Su Unicode e UTF-8<\/h2>\n

\nPer iniziare, alcune parole su cos'\u00e8 Unicode<\/strong> e UTF-8<\/strong>.<\/p>\n

Come \u00e8 noto, in passato erano popolari le codifiche a 8 bit. Con esse era tutto semplice: 256 simboli possono essere numerati da 0 a 255, e i numeri da 0 a 255 sono evidentemente rappresentabili in un byte. Se torniamo alle origini, la codifica ASCII \u00e8 addirittura limitata a 7 bit, quindi il bit pi\u00f9 significativo nella sua rappresentazione byte \u00e8 zero, e la maggior parte delle codifiche a 8 bit sono compatibili con essa (si differenziano solo nella parte \"superiore\", dove il bit pi\u00f9 significativo \u00e8 uno).<\/p>\n

Qual \u00e8 la differenza tra Unicode e quelle codifiche e perch\u00e9 con esso sono associate numerose rappresentazioni specifiche \u2014 UTF-8, UTF-16 (BE e LE), UTF-32? Procediamo con ordine.<\/p>\n

Lo standard principale di Unicode descrive solo la corrispondenza tra i caratteri (e in alcuni casi \u2014 le singole componenti dei caratteri) e i loro numeri. E i numeri possibili in questo standard sono davvero tanti \u2014 da 0x00<\/b><\/code> fino a 0x10FFFF<\/b><\/code> (1.114.112). Se volessimo memorizzare un numero in un intervallo simile in una variabile, n\u00e9 1 n\u00e9 2 byte sarebbero sufficienti. E poich\u00e9 i nostri processori non sono particolarmente predisposti a gestire numeri a tre byte, saremmo costretti a utilizzare ben 4 byte per ogni simbolo! Questo \u00e8 UTF-32, ma proprio a causa di questa \u00abspreco\u00bb questo formato non \u00e8 molto popolare.<\/p>\n

Fortunatamente, i caratteri all'interno di Unicode non sono ordinati a caso. Tutti quelli presenti sono divisi in 17 \u00abpiani<\/em>\u00bb, ognuno dei quali contiene 65.536 (0x10000<\/b><\/code>) \u00abpunti di codice<\/em>\u00bb. Il concetto di \u00abpunto di codice\u00bb qui \u00e8 semplicemente il numero del carattere<\/em>, assegnato a esso da Unicode. Ma, come detto prima, in Unicode non sono numerati solo i singoli caratteri, ma anche le loro componenti e le note di servizio (e a volte non corrisponde nemmeno a un numero \u2014 forse, per un certo periodo, ma per noi non \u00e8 cos\u00ec importante), quindi \u00e8 pi\u00f9 corretto parlare sempre del numero totale dei numeri, piuttosto che dei caratteri. Tuttavia, per brevit\u00e0, in seguito utilizzer\u00f2 spesso la parola \u00abcarattere\u00bb, riferendomi al termine \u00abpunto di codice\u00bb.<\/p>\n

\"Un'altra
\nPiani di Unicode. Come si pu\u00f2 notare, la maggior parte (i piani dal 4 al 13) sono ancora inutilizzati.<\/i><\/p>\n

Cosa c'\u00e8 di pi\u00f9 interessante \u00e8 che tutta la \"polpa\" principale si trova nel piano zero, chiamato \"Piano Multilingue di Base<\/em>\". Se la riga contiene testo in una delle lingue moderne (compreso il cinese), non supererai questo piano. Ma non puoi escludere il resto di Unicode - per esempio, le emoji si trovano principalmente alla fine del piano successivo, \"Piano Multilingue Supplementare<\/em>\" (che si estende da 0x10000<\/b><\/code> fino a 0x1FFFF<\/b><\/code>). Pertanto, UTF-16 si comporta cos\u00ec: tutti i caratteri che rientrano in Piano Multilingue di Base<\/em>, codificati \u00abcos\u00ec come sono\u00bb, con il corrispondente numero a due byte. Tuttavia, parte dei numeri in questo intervallo non rappresenta affatto caratteri specifici, ma indica che dopo questa coppia di byte \u00e8 necessario considerare un'altra \u2014 combinando i valori di questi quattro byte insieme, si ottiene un numero che copre l'intero intervallo consentito di Unicode. Questa rappresentazione \u00e8 chiamata \u00abcoppie surrogate\u00bb \u2014 potreste averne sentito parlare.<\/p>\n

Pertanto, UTF-16 richiede due o (in rari casi) quattro byte per un singolo \u00abpunto di codice\u00bb. \u00c8 meglio che usare costantemente quattro byte, ma l'alfabeto latino (e altri caratteri ASCII) in questa codifica occupa met\u00e0 dello spazio disponibile in zeri. UTF-8 \u00e8 stato progettato per risolvere questo problema: ASCII occupa, come prima, solo un byte; i codici da 0x80<\/b><\/code> fino a 0x7FF<\/b><\/code> \u2014 due byte; da 0x800<\/b><\/code> fino a 0xFFFF<\/b><\/code> \u2014 tre, e da 0x10000<\/b><\/code> fino a 0x10FFFF<\/b><\/code> \u2014 quattro. Da un lato, l'alfabeto latino ne trae giovamento: \u00e8 tornata la compatibilit\u00e0 con ASCII, e la distribuzione \u00e8 pi\u00f9 uniformemente \u00abspalmata\u00bb da 1 a 4 byte. Ma gli alfabeti diversi da quello latino, purtroppo, non traggono vantaggio rispetto a UTF-16, e molti richiedono addirittura tre byte invece di due \u2014 l'intervallo coperto dalla registrazione a due byte si \u00e8 ridotto di 32 volte, da 0xFFFF<\/b><\/code> fino a 0x7FF<\/b><\/code>, e non include n\u00e9 il cinese n\u00e9, ad esempio, il georgiano. Alla cirillicae ad altri cinque alfabeti - evviva - va bene, 2 byte per simbolo.<\/p>\n

Perch\u00e9 succede questo? Vediamo come UTF-8 rappresenta i codici dei caratteri:
\n\"Un'altra
\nDirettamente per la rappresentazione dei numeri qui sono stati utilizzati i bit, contrassegnati dal simbolo x<\/b><\/code>. \u00c8 evidente che nella registrazione a due byte ci sono solo 11 bit (su 16). I bit pi\u00f9 significativi hanno solo una funzione di servizio. Nel caso della registrazione a quattro byte, addirittura 21 bit su 32 sono riservati al numero del punto di codice \u2014 sembrerebbe che tre byte (che danno un totale di 24 bit) sarebbero sufficienti, ma i marcatori di servizio consumano troppi.<\/p>\n

\u00c8 un male? In realt\u00e0, non molto. Da un lato, se ci preoccupiamo molto dello spazio occupato, abbiamo algoritmi di compressione che eliminano facilmente tutta l'entropia e la ridondanza in eccesso. Dall'altro, l'obiettivo di Unicode era fornire una codifica il pi\u00f9 universale possibile. Ad esempio, una stringa codificata in UTF-8 pu\u00f2 essere gestita da un codice che prima lavorava solo con ASCII, senza temere che possa imbattersi in un simbolo dell'intervallo ASCII che in realt\u00e0 non esiste (perch\u00e9 in UTF-8 tutti i byte che iniziano con il bit zero sono proprio ASCII). E se volessimo improvvisamente tagliare una piccola coda da una grande stringa, senza decodificarla dall'inizio (o ripristinare parte delle informazioni dopo un'area danneggiata) - non \u00e8 difficile trovare l'offset dove inizia un simbolo (\u00e8 sufficiente saltare i byte che hanno un prefisso di bit. 10<\/b><\/code>).<\/p>\n

Perch\u00e9 allora inventare qualcosa di nuovo?<\/h2>\n

\nAllo stesso tempo, ci sono occasioni in cui algoritmi di compressione come il deflate sono mal applicabili, ma si desidera ottenere una memorizzazione compatta delle stringhe. Personalmente, mi sono trovato ad affrontare tale compito, riflettendo sulla costruzione di un albero dei prefissi compresso<\/a><\/noindex> per un grande dizionario che includa parole in lingue arbitrarie. Da un lato, ogni parola \u00e8 molto corta, quindi comprimerla non sarebbe efficace. Dall'altro, l'implementazione dell'albero che stavo considerando era progettata affinch\u00e9 ogni byte della stringa memorizzata generasse un nodo separato dell'albero, quindi minimizzare il loro numero sarebbe stato molto utile. Nella mia libreria Az.js<\/a><\/noindex> (cos\u00ec come in pymorphy2<\/a><\/noindex>, su cui si basa) un problema simile viene risolto in modo semplice: le stringhe imballate in un dizionario DAWG<\/a><\/noindex>vengono memorizzate l\u00ec in buon vecchio CP1251<\/a><\/noindex>. Ma, come \u00e8 facile capire, funziona bene solo per un alfabeto limitato: una stringa in cinese non pu\u00f2 essere inserita in tale dizionario.<\/p>\n

Sottolineo anche un altro fastidioso aspetto che si verifica quando si utilizza UTF-8 in una tale struttura dati. Nella figura sopra si pu\u00f2 vedere che, quando il simbolo viene scritto come due byte, i bit che si riferiscono al suo numero non sono contigui, ma sono interrotti da un paio di bit 10<\/b><\/code> nel mezzo: 110xxxxx 10xxxxxx<\/b><\/code>. Di conseguenza, quando nel codice del simbolo si sovraccaricano i 6 bit inferiori del secondo byte (cio\u00e8 si verifica un passaggio 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), anche il primo byte cambia. Risultato, la lettera \u00ab\u043f\u00bb \u00e8 rappresentata dai byte 0xD0 0xBF<\/b><\/code>, e la successiva \u00abr\u00bb \u2014 gi\u00e0 0xD1 0x80<\/b><\/code>. Nell'albero dei prefissi ci\u00f2 porta alla separazione del nodo genitore in due: uno per il prefisso 0xD0<\/b><\/code>, e l'altro per 0xD1<\/b><\/code> (anche se tutto il cirillico potrebbe essere codificato solo con il secondo byte).<\/p>\n

Cosa ho ottenuto<\/h2>\n

\nAffrontando questa sfida, ho deciso di esercitarmi con i giochi di bit, e nel contempo di conoscere meglio la struttura di Unicode in generale. Il risultato \u00e8 stato il formato di codifica UTF-C (\u00abC\u00bb da compatto<\/em>), che utilizza al massimo 3 byte per ogni punto di codice, e molto spesso consente di utilizzare solo un byte extra per l'intera stringa codificata<\/strong>. Questo porta al fatto che in molti alfabeti non ASCII tale codifica risulta dal 30 al 60% pi\u00f9 compatta rispetto a UTF-8<\/strong>.<\/p>\n

Ho preparato esempi di implementazione degli algoritmi di codifica e decodifica sotto forma di librerie in JavaScript e Go<\/a><\/noindex>, puoi usarle liberamente nel tuo codice. Tuttavia, sottolineo che in un certo senso questo formato rimane un \u00abmarchio\u00bb, e non consiglio di usarlo senza renderti conto di cosa ti serve veramente<\/strong>. Si tratta comunque di pi\u00f9 un esperimento che un serio \u00abmiglioramento di UTF-8\u00bb. Tuttavia, il codice \u00e8 scritto in modo ordinato, conciso, con un gran numero di commenti e copertura di test.<\/p>\n

\"Un'altra
\nRisultato dell'esecuzione dei test e confronto con UTF-8<\/i><\/p>\n

Inoltre, ho creato una pagina demo<\/a><\/noindex>, dove puoi valutare il funzionamento dell'algoritmo, e poi parler\u00f2 pi\u00f9 dettagliatamente dei suoi principi e del processo di sviluppo.<\/p>\n

Eliminare i bit ridondanti<\/h2>\n

\nCome base ho utilizzato, ovviamente, UTF-8. La prima e pi\u00f9 ovvia cosa che si pu\u00f2 cambiare \u00e8 ridurre il numero di bit di servizio in ogni byte. Ad esempio, il primo byte in UTF-8 inizia sempre o con 0<\/b><\/code>, o con 11<\/b><\/code> \u2014 e il prefisso 10<\/b><\/code> \u00e8 presente solo nei byte successivi. Sostituiamo il prefisso 11<\/b><\/code> in 1<\/b><\/code>, e per i byte successivi eliminiamo completamente i prefissi. Cosa otteniamo?<\/p>\n

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

Fermati un attimo, e dov'\u00e8 la codifica a quattro byte? Non \u00e8 pi\u00f9 necessaria: con la codifica di tre byte abbiamo ora accesso a 21 bit e questo \u00e8 pi\u00f9 che sufficiente per tutti i numeri fino a 0x10FFFF<\/b><\/code>.<\/p>\n

Cosa abbiamo sacrificato qui? La cosa pi\u00f9 importante \u00e8 la scoperta dei confini dei simboli da un punto qualsiasi del buffer. Non possiamo fare clic su un byte casuale e da l\u00ec trovare l'inizio del simbolo successivo. Questa \u00e8 una limitazione del nostro formato, ma nella pratica la necessit\u00e0 di questo non si presenta spesso. Di solito siamo in grado di scorrere il buffer dall'inizio (soprattutto quando si parla di stringhe corte).<\/p>\n

La situazione riguardante la copertura dei linguaggi con 2 byte \u00e8 migliorata: ora il formato a due byte offre un intervallo di 14 bit, il che corrisponde ai codici fino a 0x3FFF<\/b><\/code>. Ai cinesi non va bene (i loro ideogrammi si trovano principalmente nell'intervallo da 0x4E00<\/b><\/code> fino a 0x9FFF<\/b><\/code>), ma ai georgiani e a molti altri popoli \u00e8 andata meglio: le loro lingue si adattano anch'esse a 2 byte per simbolo.<\/p>\n

Introduciamo lo stato dell'encoder<\/h2>\n

\nOra pensiamo alle propriet\u00e0 delle righe stesse. Nel dizionario ci sono per lo pi\u00f9 parole scritte con simboli di un solo alfabeto, e questo \u00e8 vero anche per molti altri testi. Sarebbe utile indicare una sola volta questo alfabeto e poi indicare solo il numero della lettera al suo interno. Vediamo se la disposizione dei simboli nella tabella Unicode ci aiuta.<\/p>\n

Come gi\u00e0 detto, l'Unicode \u00e8 suddiviso in piani<\/em> di 65536 codici ciascuno. Ma questa suddivisione non \u00e8 molto utile (come gi\u00e0 detto, di solito ci troviamo nel piano zero). \u00c8 molto pi\u00f9 interessante la suddivisione in blocchi.<\/em> Questi intervalli non hanno gi\u00e0 lunghezze fisse e portano un significato maggiore: di solito, ognuno riunisce simboli di un alfabeto.<\/p>\n

\"Un'altra
\nBlocco che contiene simboli dell'alfabeto bengalese. Sfortunatamente, per ragioni storiche, questo \u00e8 un esempio di imballaggio non molto denso: 96 simboli sono sparsi in modo caotico su 128 punti di codice del blocco.<\/i><\/p>\n

L'inizio dei blocchi e le loro dimensioni sono sempre un multiplo di 16: questo \u00e8 stato fatto semplicemente per comodit\u00e0. Inoltre, molti blocchi iniziano e finiscono con valori multipli di 128 o addirittura 256; ad esempio, la principale scrittura in cirillico occupa 256 byte da 0x0400<\/b><\/code> fino a 0x04FF<\/b><\/code>. \u00c8 piuttosto comodo: se una volta memorizziamo il prefisso 0x04<\/b><\/code>, allora in seguito qualsiasi simbolo cirillico pu\u00f2 essere registrato in un byte. Tuttavia, in questo modo perderemo la possibilit\u00e0 di tornare all'ASCII (e a qualsiasi altro simbolo in generale). Quindi procediamo cos\u00ec:<\/p>\n

    \n
  1. Due byte 10yyyyyy yxxxxxxx<\/b><\/code> non solo rappresentano un simbolo con numero yyyyyy yxxxxxxx<\/b><\/code>, ma cambiano l'alfabeto corrente<\/em> in yyyyyy y0000000<\/b><\/code> (ossia memorizziamo tutti i bit tranne i pi\u00f9 bassi 7 bit<\/strong>);<\/li>\n
  2. Un byte 0xxxxxxx<\/b><\/code> \u00e8 il simbolo dell'alfabeto corrente. Deve semplicemente essere sommato a quell'offset che abbiamo memorizzato nel passo 1. Finch\u00e9 non abbiamo cambiato alfabeto, l'offset \u00e8 zero, quindi abbiamo mantenuto la compatibilit\u00e0 con l'ASCII.<\/li>\n<\/ol>\n

    \nAnalogamente per i codici che richiedono 3 byte:<\/p>\n

      \n
    1. Tre byte 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> rappresentano un simbolo con numero yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, cambiano l'alfabeto corrente<\/em> in yyyyyy y0000000 00000000<\/b><\/code> (memorizziamo tutto, tranne i pi\u00f9 bassi 15 bit<\/strong>), e pongono un flag, che ora siamo in lungo<\/em> modalit\u00e0 (quando cambiamo nuovamente l'alfabeto su questo flag lo ripristineremo);<\/li>\n
    2. Due byte 0xxxxxxx xxxxxxxx<\/b><\/code> in modalit\u00e0 lunga questo \u00e8 il simbolo dell'alfabeto attuale. Analogamente, lo sommiamo con lo spostamento del passo 1. L'unica differenza \u00e8 che ora leggiamo due byte (perch\u00e9 ci siamo switchati in tale modalit\u00e0).<\/li>\n<\/ol>\n

      \nSuona bene: ora, finch\u00e9 dobbiamo codificare simboli dello stesso intervallo Unicode a 7 bit, spendiamo 1 byte extra all'inizio e solo 1 byte per ogni simbolo.<\/p>\n

      \"Un'altra
      \nFunziona una delle prime versioni. Gi\u00e0 spesso supera UTF-8, ma c'\u00e8 ancora margine di miglioramento.<\/i><\/p>\n

      Cosa \u00e8 peggiorato? In primo luogo, abbiamo uno stato, ovvero lo spostamento dell'alfabeto attuale<\/em> e il flag di modalit\u00e0 lunga<\/em>. Questo ci limita ulteriormente: ora gli stessi simboli possono essere codificati in modo diverso in contesti differenti. La ricerca di sottostringhe, ad esempio, dovr\u00e0 tenerne conto, invece di confrontare semplicemente i byte. In secondo luogo, non appena abbiamo cambiato l'alfabeto, \u00e8 diventato difficile codificare i simboli ASCII (e questo non riguarda solo l'alfabeto latino, ma anche la punteggiatura di base, inclusi gli spazi) \u2014 richiedono un cambio di alfabeto a 0, cio\u00e8 ancora un byte extra (e poi un altro per tornare al nostro principale).<\/p>\n

      Un alfabeto \u00e8 buono, due sono meglio<\/h2>\n

      \nProviamo a cambiare un po' i nostri prefissi bit, inserendo un altro ai tre sopra descritti:<\/p>\n

      0xxxxxxx<\/b><\/code> \u2014 1 byte in modalit\u00e0 normale, 2 in modalit\u00e0 lunga
      \n11xxxxxx<\/b><\/code> \u2014 1 byte
      \n100xxxxx xxxxxxxx<\/b><\/code> \u2014 2 byte
      \n101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> \u2014 3 byte<\/p>\n

      \"Un'altra
      \n
      \nOra nella codifica a due byte \u00e8 diventato disponibile un byte in meno \u2014 si possono includere punti di codice fino a 0x1FFF<\/b><\/code>, e non 0x3FFF<\/b><\/code>. Tuttavia, \u00e8 ancora sensibilmente pi\u00f9 dell'UTF-8 a due byte, la maggior parte delle lingue comuni ci sta ancora, la perdita pi\u00f9 evidente \u00e8 stata       hiragana<\/a><\/noindex> e katakana<\/a><\/noindex>, i giapponesi sono tristi.<\/p>\n

      Qual \u00e8 il nuovo codice 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 (ausiliario<\/em>) alfabeto. Quando cambiamo l'alfabeto attuale, un pezzo del vecchio alfabeto diventa ausiliario. Ad esempio, se passiamo da ASCII a cirillico \u2014 ora abbiamo 64 simboli in serbatoio, contenenti alfabeto latino, numeri, spazio e virgola<\/strong> (le inserzioni pi\u00f9 comuni nei testi non-ASCII). Se torniamo su ASCII \u2014 l'alfabeto ausiliario diventa la parte principale del cirillico.<\/p>\n

      Grazie all'accesso a due alfabeti, possiamo gestire un gran numero di testi, avendo costi minimi per il passaggio tra alfabeti (la punteggiatura porter\u00e0 pi\u00f9 spesso a tornare all'ASCII, ma dopo di ci\u00f2 molti simboli non ASCII verranno gi\u00e0 estratti dall'alfabeto supplementare, senza un nuovo passaggio).<\/p>\n

      Bonus: designando l'alfabeto supplementare con un prefisso 11xxxxxx<\/b><\/code> e scegliendo il suo offset iniziale uguale a 0xC0<\/b><\/code>, otteniamo una parziale compatibilit\u00e0 con CP1252. In altre parole, molti (ma non tutti) i testi dell'Europa occidentale codificati in CP1252 appariranno allo stesso modo anche in UTF-C.<\/p>\n

      Qui, in effetti, si presenta una difficolt\u00e0: come ottenere l'alfabeto ausiliario dall'alfabeto principale? Possiamo mantenere lo stesso offset, ma\u2014ahim\u00e8\u2014qui la struttura di Unicode gioca contro di noi. Molto spesso, la parte principale dell'alfabeto non si trova all'inizio del blocco (ad esempio, la maiuscola russa \"A\" ha il codice 0x0410<\/b><\/code>, mentre il blocco cirillico inizia con 0x0400<\/b><\/code>). Cos\u00ec, prendendo in prestito i primi 64 simboli, potremmo perdere l'accesso alla parte finale dell'alfabeto.<\/p>\n

      Per risolvere questo problema, ho esaminato manualmente alcuni blocchi corrispondenti a diverse lingue e ho specificato per essi l'offset dell'alfabeto ausiliario all'interno dell'alfabeto principale. Ho riordinato l'alfabeto latino, in via eccezionale, come se fosse base64.<\/p>\n

      \"Un'altra<\/p>\n

      Finiture finali<\/h2>\n

      \nInfine, riflettiamo su dove possiamo apportare ulteriori miglioramenti.<\/p>\n

      Notiamo che il formato 101xxxxx xxxxxxxx xxxxxxxx<\/b><\/code> permette di codificare numeri fino a 0x1FFFFF<\/b><\/code>, mentre Unicode termina prima, a 0x10FFFF<\/b><\/code>. In altre parole, l'ultimo punto di codice sar\u00e0 rappresentato come 10110000 11111111 11111111<\/b><\/code>. Pertanto, possiamo dire che se il primo byte ha l'aspetto 1011xxxx<\/b><\/code> (dove xxxx<\/b><\/code> maggiore di 0), allora significa qualcos'altro. Ad esempio, possiamo aggiungere altri 15 simboli, costantemente disponibili per la codifica in un byte, ma ho deciso di procedere diversamente.<\/p>\n

      Perci\u00f2, scegliamo alcuni intervalli selezionati, corrispondenti a emoji, hiragana e katakana, li rinumeriamo in un'unica lista continua e li codifichiamo in due byte invece di tre:<\/p>\n

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

      Ottimo: l'emoji sopra citato \u200d\u200d\u200d\"Un'altra<\/a><\/noindex>, che consiste in 7 punti di codice, in UTF-8 occupa 25 byte, mentre noi lo abbiamo ridotto a 14<\/strong> (proprio due byte per ogni punto di codice). A proposito, Habr ha rifiutato di elaborarlo (sia nella vecchia che nella nuova editor), quindi abbiamo dovuto inserirlo come immagine.<\/p>\n

      Proviamo a risolvere un'altra questione. Come ricordiamo, l'alfabeto principale \u00e8 essenzialmente i 6 bit superiori<\/strong>, che teniamo a mente, e li applichiamo al codice di ogni simbolo decodificato. Nel caso dei caratteri cinesi, che si trovano nel blocco 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, questo corrisponde a 0 o 1. Non \u00e8 molto comodo: ci toccher\u00e0 continuamente cambiare l'alfabeto tra questi due valori (ossia utilizzare tre byte). Ma notiamo che nella modalit\u00e0 lunga possiamo sottrarre dal codice il numero di simboli che stiamo codificando con la modalit\u00e0 corta (dopo tutti i trucchi sopracitati, sono 10240) \u2014 in quel caso, l'intervallo dei caratteri si sposter\u00e0 a 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, e in questo caso in tutto questo intervallo i 6 bit superiori (su 21) saranno uguali a 0. In questo modo, le sequenze di caratteri utilizzeranno due byte per carattere (che \u00e8 ottimale per un intervallo cos\u00ec ampio), senza richiedere cambi di alfabeto. <\/p>\n

      Soluzioni alternative: SCSU, BOCU-1<\/h2>\n

      \nGli esperti di Unicode, appena leggono il titolo dell'articolo, probabilmente si affretteranno a ricordare che tra gli standard Unicode c'\u00e8 Standard Compression Scheme for Unicode<\/a><\/noindex> (SCSU), che descrive un modo di codifica molto simile a quanto descritto nell'articolo.<\/p>\n

      Confesso francamente: ho scoperto la sua esistenza solo dopo essermi immerso completamente nella scrittura della mia soluzione. Se l'avessi conosciuto fin dall'inizio, probabilmente avrei provato a scrivere la sua implementazione invece di inventare il mio approccio.<\/p>\n

      Ci\u00f2 che \u00e8 interessante, SCSU utilizza idee molto simili a quelle a cui sono arrivato autonomamente (anzich\u00e9 il concetto di \"alfabeti\", usano \"finestre\", e ne hanno pi\u00f9 di quante ne abbia io). Allo stesso tempo, questo formato ha anche dei difetti: \u00e8 un po' pi\u00f9 vicino agli algoritmi di compressione piuttosto che alla codifica. In particolare, lo standard offre moltissimi modi di rappresentazione, ma non detto come scegliere il migliore \u2014 per questo, l'encoder deve applicare alcune euristiche. In questo modo, l'encoder SCSU, che fornisce un buon imballaggio, sar\u00e0 pi\u00f9 complesso e ingombrante rispetto al mio algoritmo.<\/p>\n

      A titolo di confronto, ho trasferito una realizzazione relativamente semplice di SCSU in JavaScript \u2014 per quantit\u00e0 di codice \u00e8 risultata comparabile al mio UTF-C, ma in alcuni casi ha mostrato risultati peggiori di decine di punti percentuali (a volte pu\u00f2 anche eccederlo, ma non di molto). Ad esempio, i testi in ebraico e greco sono stati codificati da UTF-C il 60% meglio rispetto a SCSU<\/strong> (probabilmente a causa dei loro alfabeti compatti).<\/p>\n

      Aggiungo separatamente che, oltre a SCSU, c'\u00e8 anche un altro modo di rappresentare in modo compatto Unicode \u2014 BOCU-1<\/a><\/noindex>, ma questo \u00e8 mirato alla compatibilit\u00e0 con MIME (cosa di cui non avevo bisogno), e utilizza un approccio di codifica leggermente diverso. Non ho valutato la sua efficacia, ma mi sembra improbabile che sia migliore di SCSU.<\/p>\n

      Possibili miglioramenti<\/h2>\n

      \nL'algoritmo che ho presentato non \u00e8 universale per progetto (qui, probabilmente, i miei obiettivi divergono di pi\u00f9 da quelli del consorzio Unicode). Ho gi\u00e0 menzionato che \u00e8 stato sviluppato principalmente per un compito (memorizzare un dizionario multilingue in un albero di prefissi), e alcune delle sue caratteristiche potrebbero non adattarsi bene ad altre esigenze. Tuttavia, il fatto che non sia uno standard pu\u00f2 essere un vantaggio \u2014 puoi facilmente adattarlo alle tue necessit\u00e0<\/strong>.<\/p>\n

      Ad esempio, \u00e8 ovvio che \u00e8 possibile eliminare lo stato, rendere la codifica stateless \u2014 semplicemente non aggiornando le variabili fuori<\/b><\/code>, ausOffs<\/b><\/code> e is21Bit<\/b><\/code> nell'encoder e nel decoder. In questo caso, non sar\u00e0 possibile imballare in modo efficiente sequenze di caratteri dello stesso alfabeto, ma ci sar\u00e0 la garanzia che lo stesso carattere sar\u00e0 sempre codificato con gli stessi byte, indipendentemente dal contesto.<\/p>\n

      Inoltre, \u00e8 possibile affinare l'encoder per una lingua specifica, cambiando lo stato predefinito \u2014 ad esempio, orientandosi su testi russi, impostare all'inizio dell'encoder e del decoder. offset = 0x0400<\/b><\/code> e auxOffs = 0<\/b><\/code>. In particolare, questo ha senso nel caso della modalit\u00e0 stateless. In generale, sar\u00e0 simile all'uso di una vecchia codifica a otto bit, ma non priva della possibilit\u00e0 di inserire caratteri da tutto il Unicode secondo necessit\u00e0.<\/p>\n

      Un altro svantaggio, menzionato in precedenza, \u00e8 che nel testo voluminoso codificato in UTF-C non esiste un modo veloce per trovare il confine del carattere pi\u00f9 vicino a un byte arbitrario. Tagliando dal buffer codificato gli ultimi, diciamo, 100 byte, \u00e8 possibile ottenere spazzatura con cui non si pu\u00f2 fare nulla. La codifica non \u00e8 progettata per memorizzare log di diversi gigabyte, ma in generale questo pu\u00f2 essere corretto. Un byte 0xBF<\/b><\/code> non dovrebbe mai apparire come primo byte (ma pu\u00f2 essere secondo o terzo). Pertanto, durante la codifica, \u00e8 possibile inserire una sequenza 0xBF 0xBF 0xBF<\/b><\/code> ogni, ad esempio, 10 Kb: allora, se necessario, sar\u00e0 sufficiente scansionare il pezzo selezionato fino a quando non viene trovato un simile marcatore. Dopo l'ultimo 0xBF<\/b><\/code> ci sar\u00e0 garantito l'inizio di un carattere. (Durante la decodifica, questa sequenza di tre byte, ovviamente, dovr\u00e0 essere ignorata.)<\/p>\n

      In sintesi<\/h2>\n

      \nSe sei arrivato fin qui, congratulazioni! Spero che, come me, tu abbia imparato qualcosa di nuovo (o rinfrescato la memoria su qualcosa di vecchio) sul funzionamento di Unicode.<\/p>\n

      \"Un'altra
      \nPagina dimostrativa. L'esempio dell'ebraico mostra i vantaggi sia rispetto all'UTF-8 che all'SCSU.<\/i><\/p>\n

      Non bisogna considerare le ricerche sopra descritte come un attacco agli standard. Tuttavia, sono complessivamente soddisfatto dei risultati del mio lavoro, quindi sono felice di condividerli<\/a><\/noindex>: ad esempio, la libreria JS in forma minificata pesa solo 1710 byte (e non ha dipendenze, ovviamente). Come ho accennato prima, \u00e8 possibile familiarizzare con il suo funzionamento sulla pagina demo<\/a><\/noindex> (l\u00e0 puoi trovare anche un insieme di testi con cui confrontarla con UTF-8 e SCSU).<\/p>\n

      Infine, vorrei richiamare ancora l'attenzione sui casi in cui utilizzare UTF-C non \u00e8 conveniente<\/b>:<\/p>\n

      Guardiamo ai blocchi di Unicode che richiedono tre byte ora. In massima parte, come gi\u00e0 detto, sono ideogrammi cinesi\u2014ma con essi \u00e8 difficile fare qualcosa, sono 21 mila. Ma ci sono anche hiragana e katakana\u2014e sono gi\u00e0 meno di duecento. E, visto che abbiamo menzionato i giapponesi\u2014l\u00ec ci sono anche le emoji (in realt\u00e0 sono sparse in molte parti di Unicode, ma i blocchi principali sono nell'intervallo 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Se ci pensiamo, ci sono emoji che sono composte da pi\u00f9 punti di codice (ad esempio, emoji \u200d\u200d\u200d\"Un'altra<\/a><\/noindex> che consistono in 7 codici!), ci viene davvero da piangere a pensare di sprecare tre byte per ognuna (7\u00d73 = 21 byte per un singolo simbolo, \u00e8 un incubo).<\/p>\n