{"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 altro esempio: memorizziamo le stringhe Unicode in modo 30-60% pi\u00f9 compatto rispetto a UTF-8","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

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

Di seguito, propongo di esaminare il mio tentativo di fornire una risposta a questa domanda e una realizzazione di un algoritmo relativamente semplice che permette di memorizzare stringhe nella maggior parte delle lingue del mondo, senza aggiungere l'eccesso di dati presente in UTF-8.<\/a><\/noindex><\/p>\n

Dichiarazione di non responsabilit\u00e0.<\/i> Far\u00f2 subito alcune importanti precisazioni: la soluzione descritta non \u00e8 proposta come un sostituto universale di UTF-8.<\/strong>, si adatta solo a un elenco ristretto di casi (di cui parler\u00f2 dopo), e non deve mai essere utilizzato per interagire con API esterne (di cui non sanno nemmeno nulla). Pi\u00f9 frequentemente, per la memorizzazione compatta di grandi volumi di dati testuali, si adattano algoritmi di compressione generali (come deflate). Inoltre, gi\u00e0 nella fase di creazione della mia soluzione, ho trovato uno standard esistente nello stesso Unicode, che risolve lo stesso problema \u2014 \u00e8 un po' pi\u00f9 complesso (e spesso meno efficace), ma rimane uno standard accettato, anzich\u00e9 qualcosa creato frettolosamente. Di questo parler\u00f2 anche.<\/p>\n

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

\nPer cominciare, alcune parole su cosa sia in generale 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 caratteri possono essere numerati con i numeri da 0 a 255, e i numeri da 0 a 255 sono ovviamente rappresentabili in un byte. Se torniamo alle origini, la codifica ASCII \u00e8 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 \u00e8 compatibile con essa (si differenziano solo nella parte 'superiore', dove il bit pi\u00f9 significativo \u00e8 uno).<\/p>\n

Cosa differenzia Unicode da quelle codifiche e perch\u00e9 con esso sono associate molte rappresentazioni specifiche \u2014 UTF-8, UTF-16 (BE e LE), UTF-32? Analizziamo per ordine.<\/p>\n

Lo standard principale di Unicode descrive solo la corrispondenza tra i caratteri (e in alcuni casi \u2014 singoli componenti dei caratteri) e i loro numeri. E i numeri possibili in questo standard sono moltissimi \u2014 da 0x00<\/b><\/code> fino a 0x10FFFF<\/b><\/code> (1 114 112 pezzi). Se volessimo memorizzare un numero in questo intervallo in una variabile, n\u00e9 1 n\u00e9 2 byte sarebbero sufficienti. E poich\u00e9 i nostri processori non sono progettati per lavorare con numeri a tre byte, saremmo costretti a utilizzare ben 4 byte per ogni simbolo! Questo \u00e8 UTF-32, ma proprio a causa di questa \"sprecatezza\" questo formato non \u00e8 molto popolare.<\/p>\n

Fortunatamente, i simboli all'interno di Unicode non sono ordinati a caso. La loro moltitudine \u00e8 suddivisa in 17 \"piani<\/em>\", ognuno dei quali contiene 65536 (0x10000<\/b><\/code>) \u00abpunti codice<\/em>\"). Il concetto di \"punto codice\" qui \u00e8 semplicemente il numero di simbolo<\/em>, assegnato a lui da Unicode. Ma, come gi\u00e0 detto, in Unicode non sono numerati solo i singoli simboli, ma anche i loro componenti e i segni di controllo (e a volte non corrispondono affatto a un numero \u2014 forse fino a un certo punto, ma per noi questo non \u00e8 cos\u00ec importante), quindi \u00e8 pi\u00f9 corretto parlare sempre del numero stesso dei numeri, piuttosto che dei simboli. Tuttavia, per brevit\u00e0, in seguito user\u00f2 spesso la parola \"simbolo\", riferendomi al termine \"punto codice\".<\/p>\n

\"Un
\nPiani di Unicode. Come si pu\u00f2 vedere, la maggior parte (i piani da 4 a 13) non \u00e8 ancora utilizzata.<\/i><\/p>\n

La cosa pi\u00f9 sorprendente \u00e8 che tutta la sostanza fondamentale si trova nel piano zero, chiamato "Piano Multilingue di Base<\/em>". Se una riga contiene testo in una delle lingue moderne (compreso il cinese), non potrai uscire da questo piano. Ma non si pu\u00f2 nemmeno escludere il resto dello 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 funziona cos\u00ec: tutti i caratteri che rientrano in Piano Multilingue di Base<\/em>, vengono codificati \u00abcos\u00ec come sono\u00bb, con il corrispondente numero a due byte. Tuttavia, alcuni numeri in questo intervallo non rappresentano affatto caratteri specifici, ma indicano che dopo questa coppia di byte deve essere considerata un'altra \u2014 combinando i valori di questi quattro byte insieme, otteniamo un numero che copre l'intero intervallo consentito di Unicode. Questa rappresentazione \u00e8 chiamata \u00abcoppie surrogative\u00bb \u2014 forse ne hai sentito parlare.<\/p>\n

In questo modo, UTF-16 richiede due o (in rari casi) quattro byte per un singolo \"punto di codice\". Questo \u00e8 meglio che utilizzare costantemente quattro byte, ma l'ASCII (e altri caratteri ASCII) in questa codifica consumano met\u00e0 dello spazio utilizzato per gli zeri. UTF-8 intende correggere questo: in esso, l'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'ASCII sta meglio: \u00e8 tornata la compatibilit\u00e0 con ASCII, e la distribuzione \u00e8 pi\u00f9 uniformemente \"distribuita\" da 1 a 4 byte. Ma gli alfabeti diversi da quello latino, ahim\u00e8, non guadagnano affatto rispetto a UTF-16, e molti richiedono addirittura tre byte invece di due \u2014 l'intervallo coperto dalla registrazione a due byte si \u00e8 ristretto di 32 volte, da 0xFFFF<\/b><\/code> fino a 0x7FF<\/b><\/code>, e non include pi\u00f9 n\u00e9 il cinese n\u00e9, per esempio, il georgiano. L'alfabeto cirillico e altri cinque alfabeti \u2013\u00a0evviva \u2013\u00a0hanno avuto fortuna, 2 byte per simbolo.<\/p>\n

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

\u00c8 davvero un problema? In realt\u00e0, non molto. Da un lato, se ci preoccupiamo molto dello spazio occupato, abbiamo algoritmi di compressione che possono facilmente eliminare tutta l'entropia e la ridondanza superflue. 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 affidata a un codice che prima lavorava solo con ASCII, senza temere che possa incontrare un carattere dell'intervallo ASCII che in realt\u00e0 non \u00e8 presente (poich\u00e9 in UTF-8 tutti i byte che iniziano con il bit zero sono proprio ASCII). E se vogliamo improvvisamente tagliare una piccola parte da una grande stringa, senza decodificarla dall'inizio (o recuperare parte delle informazioni dopo un'area danneggiata), non \u00e8 difficile trovare l'offset dove inizia un certo carattere (\u00e8 sufficiente saltare i byte che hanno un prefisso di bit) 10<\/b><\/code>).<\/p>\n

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

\nD'altra parte, ci sono rare situazioni in cui algoritmi di compressione come deflate sono poco applicabili, ma si desidera comunque ottenere una memorizzazione compatta delle stringhe. Personalmente, mi sono trovato di fronte a una tale sfida mentre riflettevo sulla costruzione di un albero dei prefissi compresso<\/a><\/noindex> per un ampio vocabolario che include parole in lingue arbitrarie. Da un lato, ogni parola \u00e8 molto breve, quindi comprimerla sarebbe inefficace. Dall'altro, l'implementazione dell'albero che ho considerato era progettata affinch\u00e9 ogni byte della stringa archiviata generasse un nodo dell'albero separato, quindi era molto utile minimizzare il loro numero. Nella mia libreria Az.js<\/a><\/noindex> (come in pymorphy2<\/a><\/noindex>, su cui si basa) un problema simile viene risolto semplicemente: le stringhe imballate in DAWG<\/a><\/noindex>-dizionari sono memorizzate l\u00ec in vecchia cara CP1251<\/a><\/noindex>. Ma, come \u00e8 facile capire, questo funziona bene solo per un alfabeto limitato \u2014 una stringa in cinese non pu\u00f2 essere inserita in un tale dizionario.<\/p>\n

Segnalo anche un altro spiacevole inconveniente che si presenta quando si utilizza UTF-8 in una tale struttura dati. Nell'immagine sopra si pu\u00f2 vedere che, quando un carattere viene scritto come due byte, i bit relativi al suo numero non sono contigui, ma interrotti da un paio di bit 10<\/b><\/code> in mezzo: 110xxxxx 10xxxxxx<\/b><\/code>. A causa di ci\u00f2, quando nei codici dei caratteri si sovraccaricano i 6 bit inferiori del secondo byte (ossia si verifica un passaggio 10111111<\/b><\/code> \u2192 10000000<\/b><\/code>), cambia anche il primo byte. Risultando nel fatto che la lettera \u00ab\u043f\u00bb \u00e8 rappresentata dai byte 0xD0 0xBF<\/b><\/code>, e la successiva \u00ab\u0440\u00bb \u00e8 gi\u00e0 0xD1 0x80<\/b><\/code>. Nell'albero dei prefissi, questo porta a una divisione del nodo genitore in due: uno per il prefisso 0xD0<\/b><\/code>, e l'altro per 0xD1<\/b><\/code> (anche se tutta la scrittura in cirillico potrebbe essere codificata solo con il secondo byte).<\/p>\n

Cosa ho ottenuto<\/h2>\n

\nAffrontando questo compito, ho deciso di esercitarmi con i giochi di bit, e allo stesso tempo conoscere meglio la struttura del Unicode in generale. Il risultato \u00e8 stato il formato di codifica UTF-C (\u00abC\u00bb sta per compatto<\/em>), che non spende pi\u00f9 di 3 byte per un singolo punto di codice, e molto spesso permette di utilizzare solo un byte extra per l'intera riga codificata<\/strong>. Questo porta al fatto che per molti alfabeti non ASCII, tale codifica risulta 30-60% pi\u00f9 compatta di UTF-8<\/strong>.<\/p>\n

Ho presentato esempi di implementazione degli algoritmi di codifica e decodifica sotto forma di librerie in JavaScript e Go<\/a><\/noindex>, potete usarle liberamente nel vostro codice. Ma sottolineo comunque che in un certo senso questo formato rimane un \u00abbici\u00bb, e non lo consiglio di utilizzare senza essere consapevoli di ci\u00f2 che vi serve<\/strong>. Si tratta pi\u00f9 di un esperimento che di un serio \"miglioramento di UTF-8\". Tuttavia, il codice \u00e8 scritto in modo ordinato, conciso, con un gran numero di commenti e coperto da test.<\/p>\n

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

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

Eliminazione dei bit ridondanti<\/h2>\n

\nHo preso, naturalmente, UTF-8 come base. La prima e pi\u00f9 ovvia cosa che si pu\u00f2 cambiare \u00e8 ridurre il numero di bit di controllo 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> con 1<\/b><\/code>, e nei byte successivi eliminiamo del tutto 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

Aspetta, dov'\u00e8 la registrazione a quattro byte? Non \u00e8 pi\u00f9 necessaria \u2014 con la registrazione 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 rilevazione dei confini dei caratteri da una posizione arbitraria del buffer. Non possiamo colpire un byte arbitrario e trovare l'inizio del carattere successivo. Questa \u00e8 una limitazione del nostro formato, ma nella pratica la necessit\u00e0 di farlo non si presenta spesso. Di solito possiamo scorrere il buffer dall'inizio (soprattutto quando si tratta di stringhe brevi).<\/p>\n

La situazione con la copertura delle lingue a 2 byte \u00e8 anche migliorata: ora il formato a due byte offre un intervallo di 14 bit, che corrisponde a codici fino a 0x3FFF<\/b><\/code>. Ai cinesi non va bene (i loro ideogrammi sono principalmente nel range da 0x4E00<\/b><\/code> fino a 0x9FFF<\/b><\/code>), ma ai georgiani e a molte altre nazioni va meglio: le loro lingue rientrano anch'esse in 2 byte per carattere.<\/p>\n

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

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

Come detto sopra, Unicode \u00e8 diviso in piani<\/em> per 65536 codici ciascuna. Ma questa suddivisione non \u00e8 molto utile (come gi\u00e0 detto, ci troviamo pi\u00f9 spesso nel piano zero). Pi\u00f9 interessante \u00e8 la suddivisione in blocchi.<\/em> Questi intervalli non hanno pi\u00f9 una lunghezza fissa e hanno pi\u00f9 significato \u2014 di solito, ciascuno riunisce simboli di un unico alfabeto.<\/p>\n

\"Un
\nBlocco contenente i caratteri dell'alfabeto bengalese. Purtroppo, per ragioni storiche, questo \u00e8 un esempio di imballaggio non molto denso \u2014 96 caratteri sono sparsi casualmente su 128 punti di codice del blocco.<\/i><\/p>\n

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

    \n
  1. Due byte 10yyyyyy yxxxxxxx<\/b><\/code> non solo indicano un simbolo con il numero yyyyyy yxxxxxxx<\/b><\/code>, ma cambiano l'alfabeto corrente<\/em> con yyyyyy y0000000<\/b><\/code> (cio\u00e8 ricordiamo tutti i bit tranne i meno significativi 7 bit<\/strong>);<\/li>\n
  2. Un byte 0xxxxxxx<\/b><\/code> questo \u00e8 il simbolo dell'alfabeto attuale. Deve essere semplicemente sommato con lo spostamento che abbiamo memorizzato al passo 1. Poich\u00e9 non abbiamo cambiato l'alfabeto, lo spostamento \u00e8 pari a zero, quindi manteniamo la compatibilit\u00e0 con ASCII.<\/li>\n<\/ol>\n

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

      \n
    1. Tre byte 110yyyyy yxxxxxxx xxxxxxxx<\/b><\/code> designano il simbolo con il numero yyyyyy yxxxxxxx xxxxxxxx<\/b><\/code>, cambiano l'alfabeto corrente<\/em> con yyyyyy y0000000 00000000<\/b><\/code> (abbiamo memorizzato tutto tranne i bit inferiori 15 bit<\/strong>), e impostano un flag che ora siamo in modalit\u00e0<\/em> lunga (al cambio dell'alfabeto di nuovo in quello a due byte, questo flag lo resetteremo);<\/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 dal passo 1. L'unica differenza \u00e8 che ora leggiamo due byte (perch\u00e9 siamo passati a questa modalit\u00e0).<\/li>\n<\/ol>\n

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

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

      Cosa \u00e8 peggiorato? Innanzitutto, abbiamo uno stato, ovvero lo spostamento dell'alfabeto attuale<\/em> e il flag in modalit\u00e0 lunga<\/em>. Questo ci limita ulteriormente: ora gli stessi caratteri possono essere codificati in modo diverso a seconda dei contesti. La ricerca di sottostringhe, ad esempio, dovr\u00e0 tenerne conto, e non basarsi solo sul confronto dei byte. In secondo luogo, una volta cambiato l'alfabeto, ci sono stati problemi con la codifica dei caratteri ASCII (e questo non include solo l'alfabeto latino, ma anche la punteggiatura di base, spazi inclusi) \u2014 richiedono un cambio dell'alfabeto in 0, cio\u00e8 un altro byte sovrfluo (e poi un altro per tornare al nostro principale).<\/p>\n

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

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

      0xxxxxxx<\/b><\/code> \u2014 1 byte in modalit\u00e0 normale, 2 in quella 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
      \n
      \nOra, nella registrazione a due byte, \u00e8 disponibile un bit in meno \u2014 possono essere contenuti punti di codice fino a 0x1FFF<\/b><\/code>, e non 0x3FFF<\/b><\/code>. Tuttavia, \u00e8 ancora chiaramente di pi\u00f9 rispetto ai codici a due byte UTF-8, nella maggior parte dei linguaggi comuni ci si fa ancora spazio, la perdita pi\u00f9 evidente \u00e8 stata       hiragana<\/a><\/noindex> e katakana<\/a><\/noindex>, i giapponesi sono tristi.<\/p>\n

      Cos'\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 (auxiliary<\/em>) alfabetico. Quando cambiamo l'alfabeto attuale, un pezzo del vecchio alfabeto diventa ausiliario. Ad esempio, se passiamo da ASCII al cirillico, nel 'ripostiglio' ci sono ora 64 caratteri che contengono latino, numeri, spazio e virgola<\/strong> (le inserzioni pi\u00f9 comuni nei testi non-ASCII). Se torniamo di nuovo a ASCII, la parte principale del cirillico diventa l'alfabeto ausiliario.<\/p>\n

      Grazie all'accesso a due alfabeti, possiamo gestire un numero maggiore di testi, con costi minimi per il cambio di alfabeto (la punteggiatura porter\u00e0 pi\u00f9 frequentemente a tornare in ASCII, ma dopo molti caratteri non-ASCII li estrarremo gi\u00e0 dall'alfabeto aggiuntivo, senza riattivare il cambio).<\/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 compatibilit\u00e0 parziale 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, sorge una difficolt\u00e0: come ottenere un alfabeto ausiliario dall'alfabeto principale? Si pu\u00f2 mantenere lo stesso offset, ma \u2014 ahim\u00e8 \u2014 qui la struttura Unicode gioca gi\u00e0 contro di noi. Spesso, la parte principale dell\u2019alfabeto non si trova all\u2019inizio del blocco (ad esempio, la maiuscola russa \u00ab\u0410\u00bb ha il codice 0x0410<\/b><\/code>, mentre il blocco cirillico inizia con 0x0400<\/b><\/code>). Pertanto, prendendo in \u00abriserva\u00bb i primi 64 caratteri, potremmo perdere l'accesso alla parte finale dell'alfabeto.<\/p>\n

      Per risolvere questo problema, ho manualmente esaminato alcuni blocchi corrispondenti a vari linguaggi, e ho indicato per loro l'offset dell'alfabeto ausiliario all'interno di quello principale. Ho riorganizzato l'alfabeto latino, in via eccezionale, come fosse base64.<\/p>\n

      \"Un<\/p>\n

      Ultimi ritocchi<\/h2>\n

      \nInfine, pensiamo a dove possiamo ancora migliorare qualcosa.<\/p>\n

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

      Pertanto, scegliamo alcuni intervalli selezionati, corrispondenti a emoji, hiragana e katakana, li rinumera in un'unica lista continua e li codifichiamo in due byte anzich\u00e9 tre:<\/p>\n

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

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

      Cerchiamo di risolvere un altro problema. Come sappiamo, l'alfabeto principale \u00e8 essenzialmente i 6 bit superiori<\/strong>, che teniamo a mente e attacchiamo al codice di ciascun simbolo decodificato. Nel caso dei caratteri cinesi, che si trovano nel blocco 0x4E00<\/b><\/code> \u2013 0x9FFF<\/b><\/code>, si tratta di bit 0 o 1. Questo non \u00e8 molto pratico: dovremo costantemente cambiare l'alfabeto tra questi due valori (ossia, spendere tre byte). Ma notiamo che in modalit\u00e0 lunga possiamo sottrarre dal codice il numero di simboli che codifichiamo usando la modalit\u00e0 corta (dopo tutte le astuzie sopra descritte, questo \u00e8 10240) \u2014 allora l'intervallo dei caratteri cinesi si sposter\u00e0 a 0x2600<\/b><\/code> \u2013 0x77FF<\/b><\/code>, e in tal caso, in tutto questo intervallo, i 6 bit superiori (su 21) saranno pari a 0. Pertanto, le sequenze di caratteri utilizzeranno due byte per carattere (il che \u00e8 ottimale per un intervallo cos\u00ec ampio), senza richiedere cambiamenti di alfabeto. <\/p>\n

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

      \nGli esperti di Unicode, gi\u00e0 leggendo 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 quello descritto nell'articolo.<\/p>\n

      Ammetto onestamente: ho saputo della sua esistenza solo dopo essermi immerso profondamente nella scrittura della mia soluzione. Se ne fossi stato a conoscenza fin dall'inizio, probabilmente avrei provato a scrivere la sua implementazione invece di inventare il mio approccio.<\/p>\n

      Curiosamente, SCSU utilizza idee molto simili a quelle a cui sono arrivato autonomamente (invece del concetto di \u201calfabeti\u201d, vengono utilizzate \u201cfinestre\u201d, e ce ne sono pi\u00f9 di quante ne avessi io). Allo stesso tempo, questo formato ha anche dei difetti: \u00e8 un po' pi\u00f9 vicino agli algoritmi di compressione piuttosto che di codifica. In particolare, lo standard fornisce numerosi modi di rappresentazione, ma non spiega come scegliere quella ottimale \u2014 a questo scopo, l'encoder deve applicare alcune euristiche. Pertanto, un encoder SCSU che produce un buon packaging sar\u00e0 pi\u00f9 complesso e ingombrante rispetto al mio algoritmo.<\/p>\n

      Per confronto, ho portato un'implementazione relativamente semplice di SCSU in JavaScript \u2014 in termini di quantit\u00e0 di codice, si \u00e8 rivelata comparabile con il mio UTF-C, ma in alcuni casi ha mostrato risultati peggiori di decine di punti percentuali (a volte pu\u00f2 anche superarlo, ma di poco). Ad esempio, i testi in ebraico e greco sono stati codificati in UTF-C addirittura con un miglioramento del 60% rispetto a SCSU<\/strong> (probabilmente a causa dei loro alfabeti compatti).<\/p>\n

      Aggiungo inoltre che oltre a SCSU esiste un altro metodo di rappresentazione compatta di Unicode \u2014 BOCU-1<\/a><\/noindex>, ma mira 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 che difficilmente possa essere superiore a SCSU.<\/p>\n

      Possibili miglioramenti<\/h2>\n

      \nL'algoritmo che ho presentato non \u00e8 universale per design (qui, probabilmente, le mie intenzioni divergono maggiormente da quelle del consorzio Unicode). Ho gi\u00e0 accennato al fatto che \u00e8 stato sviluppato principalmente per un compito specifico (memorizzazione di un dizionario multilingue in un albero di prefissi), e alcune delle sue caratteristiche potrebbero non adattarsi bene ad altri compiti. Ma il fatto che non sia uno standard pu\u00f2 essere anche un vantaggio \u2014 puoi facilmente modificarlo per le tue esigenze<\/strong>.<\/p>\n

      Ad esempio, \u00e8 ovvio che si pu\u00f2 eliminare la presenza di stato, rendere la codifica stateless \u2014 semplicemente non aggiornando le variabili sconti<\/b><\/code>, disattiva<\/b><\/code> e \u00e821Bit<\/b><\/code> nel codificatore e nel decodificatore. In tal caso, non sar\u00e0 possibile imballare efficacemente sequenze di caratteri di un singolo alfabeto, ma si avr\u00e0 la garanzia che ogni stesso carattere \u00e8 sempre codificato con gli stessi byte, indipendentemente dal contesto.<\/p>\n

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

      Un ulteriore svantaggio, menzionato in precedenza, \u00e8 che nel testo voluminoso codificato in UTF-C non c'\u00e8 un modo rapido per trovare il confine di un carattere vicino a un qualsiasi byte. Tagliando dal buffer codificato gli ultimi, diciamo, 100 byte, rischiate di ottenere spazzatura con cui non potete fare niente. La codifica non \u00e8 progettata per immagazzinare log di diversi gigabyte, ma in generale questo pu\u00f2 essere sistemato. Byte 0xBF<\/b><\/code> non dovrebbe mai apparire come primo byte (ma pu\u00f2 essere il secondo o il terzo). Pertanto, durante la codifica, \u00e8 possibile inserire una sequenza 0xBF 0xBF 0xBF<\/b><\/code> ogni, diciamo, 10 Kb \u2014 cos\u00ec, se necessario, trovare il confine sar\u00e0 sufficiente scansionare il pezzo selezionato finch\u00e9 non si trova un marcatore simile. Dopo l'ultimo 0xBF<\/b><\/code> ci sar\u00e0 garantito l'inizio di un carattere. (Durante la decodifica, questa sequenza di tre byte deve ovviamente essere ignorata.)<\/p>\n

      In sintesi<\/h2>\n

      \nSe siete arrivati fino a qui, congratulazioni! Spero che, come me, abbiate appreso qualcosa di nuovo (o rinfrescato un ricordo) sul funzionamento di Unicode.<\/p>\n

      \"Un
      \nPagina dimostrativa. Nell'esempio dell'ebraico sono visibili i vantaggi sia rispetto a UTF-8 che a SCSU.<\/i><\/p>\n

      Non considerare le ricerche sopra descritte come un'invasione degli standard. Tuttavia, sono complessivamente soddisfatto dei risultati delle mie scoperte e quindi felice di condividerli. condividere<\/a><\/noindex>: ad esempio, la libreria JS in forma minimizzata pesa solo 1710 byte (e non ha dipendenze, naturalmente). Come ho accennato prima, puoi vedere il suo funzionamento sulla pagina demo<\/a><\/noindex> (l\u00ec trovi anche un set di testi per confrontarla con UTF-8 e SCSU).<\/p>\n

      Infine, vorrei richiamare l'attenzione sui casi in cui usare UTF-C non vale la pena<\/b>:<\/p>\n

      Diamo un'occhiata ai blocchi Unicode che richiedono attualmente tre byte. Principalmente, come gi\u00e0 detto, si tratta di ideogrammi cinesi - ma \u00e8 difficile fare qualcosa con essi, sono 21.000. Inoltre, ci sono anche i caratteri hiragana e katakana - e questi sono gi\u00e0 meno, meno di duecento. E, dal momento che abbiamo menzionato i giapponesi, ci sono anche le emoji (in realt\u00e0 sono sparse in molte parti del Unicode, ma i blocchi principali sono nell'intervallo 0x1F300<\/b><\/code> \u2013 0x1FBFF<\/b><\/code>). Pensando al fatto che ora ci sono emoji composte da pi\u00f9 punti di codice (ad esempio, l'emoji \u200d\u200d\u200d\"Un<\/a><\/noindex> \u00e8 composta da ben 7 codici!), diventa davvero scioccante spendere per ognuna tre byte (7\u00d73 = 21 byte per un singolo simbolo, \u00e8 un incubo).<\/p>\n