Unicode

Posted in Stand-up philosophy on September 19th, 2012 by Mihnea

De ce pula mea ai vrea sa poti scrie nume de fisiere in telugu? Ok, stramosii tai n-au fost in stare sa realizeze ca 20 si ceva de semne sint suficiente pentru a reprezenta pe foaie sunetele care le ies pe gura, dar s-au prins altii intre timp. Cum cacat sa insisti sa scrii cu viermisori si iatagane dupa ce ai vazut alfabetul latin? Si, mai rau, cum sa-ti vina ideea sa aduci haosul asta in software, in loc sa le faci un bine inapoiatilor si sa le spui ca daca vor tehnica de virf pentru vazut porn, trebuie sa se invete si cu tehnica de virf pentru scris si citit? الجهاد!

Faptul ca lumea civilizata i-a bagat in seama p-astia a fost prima greseala. A doua greseala a fost formarea unui Comitet responsabil cu recensamintul alfabetului si incartiruirea mazgaliturilor intr-un Standard International. Acest Comitet ar fi putut sa adune literele latine, chirilice, kana si eventual grecesti (cu perversiunile lor gen ăâöé etc.), sa le puna intr-o tabela si sa termine treaba (ignorind ostentativ ideogramele si jihadistii), dar nu asa functioneaza comitetele. Cind ti se confera puterea de a Gindi O Solutie, trebuie sa faci ceva complicat, ca sa le arati celorlalti ca esti destept. Orice prost poate sa puna citeva sute de caractere intr-o tabela, dar tu esti un erudit patrunzator si vezi imaginea de ansamblu, asa ca tabela ta va contine hieroglifele egiptene, caracterele ugaritice, cartile de joc, emoticoane, piesele de domino si mahjong etc. Si privind tu asa la cele un milion de semne adunate, simti ca tot nu-i destul si tot se vor gasi diversi sa conteste valoarea ta, valoarea ta, asa ca adaugi si scrijeliturile de pe discul din Phaistos (caracterele 0x101D0 – 0x101FF), care nu a fost descifrat inca. CINE-I CEL MAI ERUDIT ACUM?

Si nu te opresti aici. Nefiind prost si tinind cu tarie sa arati lumii asta, te apuci sa incurajezi creativitatea in exprimare prin intermediul semnelor diacritice. Desi ai bagat in tabela toate formele de A cu cerculet, accente, sedila, puncte si combinatii, faci caractere separate pentru toate aceste semne, ca sa poata omul sa scrie A cu trema fie ca Ä, fie ca A urmat de ¨.

Astfel s-a nascut Unicode, un standard menit sa ingreuneze pe cit posibil reprezentarea digitala a textului. Unicode se asigura ca orice operatiune de bun simt pe care ai vrea s-o faci pe un string devine imposibila. De exemplu, daca ai avut ghinionul sa inveti ca un string e o insiruire de caractere, imperialistul dornic de globalizare din tine va avea pretentia ca al 5-lea caracter dintr-un string sa fie la pozitia 5. In termeni stiintifici, vei dori ca accesul la caractere sa fie in timp O(1). Ei bine, Unicode se pisa pe pretentia ta din multiple directii.

In primul rind, cea mai folosita encodare pentru Unicode este UTF-8, care e un cod cu lungime variabila. Asta s-a intimplat din cauza ca, desi sint vreo 1.1 milioane de caractere in Unicode, oamenii normali folosesc cam 100 din ele, deci s-a simtit nevoia unei reprezentari compacte. Astfel, un caracter poate avea intre 1 si 4 bytes, deci textu’ e mic, dar ca sa ajungi la un caracter trebuie ori sa treci prin toate caracterele de dinainte, adica O(N), ori sa tii si sa actualizezi o tabela de index impreuna cu string-ul, care ar fi mai mare decit spatiul cistigat prin encodarea cu lungime variabila.

Minerii se vor grabi sa observe ca Microsoft au rezolvat demult problema asta prin intermediul string-urilor wide, unde un caracter e tinut pe 16 biti. Minerii sint prosti si nu realizeaza faptul ca 1.1 milioane de caractere nu incap in 16 biti. String-urile wide din Windows folosesc de fapt UTF-16, care este tot un cod cu lungime variabila si are aceleasi probleme ca UTF-8, plus ca ocupa de doua ori mai mult spatiu pentru textul de oameni normali, trebuie convertit la UTF-8 pentru a discuta cu restul lumii si e endian-dependent, asa ca inainte sa te exprimi pe limba lui trebuie sa semnalezi ce endianness preferi cu un cacat numit byte order mark.

Sigur, 1.1 milioane de caractere pot fi reprezentate pe 32 de biti. Se pare ca problemele noastre se rezolva daca folosim UTF-32 si acceptam ca 75% din text sa fie 0, ca memoria si discurile sint ieftine in zilele noastre. Ei bine, gratie diacriticelor separate (sau “combining marks” cum se numesc ele oficial) se rezolva o pula. Daca pentru codul tau “un caracter” inseamna “o litera” si nu “o litera sau un semn de cacat care face parte din litera anterioara”, tot trebuie sa parcurgi string-ul ca sa ajungi la o anumita pozitie si ca bonus trebuie sa si stii care sint semnele alea ca sa tii cont de ele cind numeri. Evident, celelalte reprezentari au si ele problema asta.

Sa facem un efort de imaginatie: un miner-arhitect este insarcinat sa toarne fundatia unui cod ce va folosi UTF-8. Sesizind problema indexarii, dinsul infaptuieste o functie numita CharacterAt() care parcurge string-ul in cautarea pozitiei date, tinind cont de lungime variabila, diactritice separate si alte mui. In urma sa trudeste minerul-programator ce este insarcinat sa caute slash-urile dintr-un string. Miinile lui negre iti vor intinde o floare asemanatoare cu codul ce urmeaza:

for(size_t i = 0; i < Length(str); ++i)
{
    if(CharacterAt(str, i) == '/')
    {
        // ceva
    }
}

Am incercat aici sa cuprind cit mai bine mentalitatea de miner, folosind size_t pentru variabila i, ca asa a auzit ca-i bine, dar chemind Length() la fiecare iteratie, deoarece minerii nu inteleg ce face de fapt functia aia. Oricum, chiar daca minerul muta apelul catre Length() in afara buclei, cautarea asta e tot O(N^2). Cam ca atoi-ul Minerului Suprem, mai tineti minte?

Apropo, Length() ala trebuie sa aplice aceleasi principii de convietuire globala ca CharacterAt() ca sa afle cite caractere sint de fapt in sir, nu merge sa cauti primul 0.

Exista diversi mintosi care sustin ca accesul aleatoriu la caractere este necesar foarte rar. De obicei cauti ceva printr-un string, deci oricum iei la rind toate caracterele, asa ca ai nevoie doar de niste facilitati de iteratie care sa stie de regulile pulii. Chiar daca le dam dreptate, ramine comparatia, un alt detaliu prin care Unicode da muie programatorilor din lumea intreaga.

Un om sanatos s-ar astepta sa poata compara doua string-uri byte cu byte: cind gasesti valori diferite la aceeasi pozitie, string-urile difera. Asta ar fi prea simplu, asa ca din nou diacriticele separate salveaza situatia. Ca sa compari doua string-uri trebuie intii sa le normalizezi, o operatiune cit se poate de simpla si naturala cu o descriere concisa, de doar 27 de pagini. Pentru a stimula si mai tare creativitatea, exista de fapt 4 moduri de normalizare, numite intuitiv D, C, KD si KC. Pe linga disclaimer-ul ala despre OOP ce insoteste codul Java din descriere, supun amuzamentului dumneavoastra si metoda recomandata de utilizare a implementarii din WINAPI: deoarece nu poti sti cit de mare o sa fie string-ul normalizat, chemi functia aia intr-o bucla pina cind o nimereste.

Dupa ce reusesti sa normalizezi string-ul ala trebuie sa incepi cu intrebarile filosofice: este sau nu string-ul ’10’ echivalent cu ‘Ⅹ’, ‘Δ’ sau ‘١٠’? Apropo, Ⅹ ala nu e X, este 0x2169, “Roman Numeral Ten” si in UTF-8 se scrie pe 3 bytes: 0xE2 0x85 0xA9. Ce ne faceam daca nu aveam in Unicode numerele romane de la 1 la 12? UNDE MAI ERA ERUDITIA NOASTRA?!

Deci muie Unicode, muie alfabet!

Tags: , , , , , , , , , , ,