Introducere

Totul a început cu un script scurt care ar fi trebuit să unească informațiile despre adrese e-mail angajaților, obținute din lista de utilizatori ai buletinului informativ, cu funcțiile angajaților, obținute din baza de date a departamentului de resurse umane. Ambele liste au fost exportate în fișiere text în codificarea Unicode UTF-8 și salvate cu terminatori de linie Unix.

Conținut mail.txt

Ivanov Andrei;ia@example.com

Conținut buhg.txt

Ivanova Alla;malear
Yelkina Ella;macaraș
Ivanov Andrei;instalator
Abakanov Mihail;malear

Pentru a le uni, fișierele au fost sortate cu comanda Unix sort și trimise ca intrare către programul Unix join, care s-a încheiat brusc cu o eroare:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nu este sortat: Ivanov Andrei;instalator

Vizionarea rezultatului sortării a arătat că, în general, sortarea este corectă, dar în cazul în care există corespondente între numele masculine și feminine, numele feminine apar înaintea celor masculine:

$> sort buhg.txt
Abakanov Mihail;malear
Yelkina Ella;macaraș
Ivanova Alla;malear
Ivanov Andrei;instalator

Pare a fi un bug în sortarea Unicode sau o manifestare a feminismului în algoritmul de sortare. Prima variantă este, desigur, mai plauzibilă.

Să lăsăm deoparte join și să ne concentrăm pe sort. Să încercăm să rezolvăm problema prin încercări și erori. Pentru început, să schimbăm localitatea de la en_US pe ru_RU. Pentru sortare ar fi fost suficient să setăm variabila de mediu LC_COLLATE, dar nu ne vom mulțumi cu puțin:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;malear
Yelkina Ella;macaraș
Ivanova Alla;malear
Ivanov Andrei;instalator

Nimic nu s-a schimbat.

Să încercăm să recodificăm fișierele în codificarea pe un singur byte:

$> iconv -f UTF-8 -t KOI8-R buhg.txt 
 | LANG=ru_RU.KOI8-R sort 
 | iconv -f KOI8-R -t UTF8

Din nou, nimic nu s-a schimbat.

Nu avem încotro, va trebui să căutăm o soluție pe internet. Nu există informații exact despre numele rusești, dar există întrebări despre alte ciudățenii ale sortării. Iată, de exemplu, o problemă: sortarea Unix tratează caracterele ‘-‘ (linie) ca fiind invizibile. Pe scurt, liniile "a-b", "aa", "ac" sunt sortate ca "aa", "a-b", "ac".

Răspunsul este standard peste tot: folosește localitatea de programare "C" și va fi bine. Să încercăm:

$> LANG=C sort buhg.txt
Yelkina Ella;macaraș
Abakanov Mihail;malear
Ivanov Andrei;instalator
Ivanova Alla;avocat

S-a schimbat ceva. Ivanovii s-au aranjat în ordinea corectă, dar Iolkina a dispărut undeva. Revenim la sarcina inițială:

$> LANG=C sort buhg.txt > buhg.srt
$> LANG=C sort mail.txt > mail.srt
$> LANG=C join buhg.srt mail.srt > result

A funcționat fără erori, așa cum a promis internetul. Și asta în ciuda lui Iolkina în prima linie.

Problema pare să fie rezolvată, dar pentru orice eventualitate vom încerca încă o codare rusă - cea de Windows CP1251:

$> iconv -f UTF-8 -t CP1251 buhg.txt 
 | LANG=ro_RO.CP1251 sort 
 | iconv -f CP1251 -t UTF8

Rezultatul sortării, ciudat, va coincide cu localele "C", și întreaga demonstrație, în consecință, trece fără erori. E o adevărată minune.

Nu-mi place minunile în programare, deoarece, de obicei, ele maschează erorile. Va trebui să mă ocup serios de întrebarea cum funcționează sort și la ce influențează LC_COLLATE .

În final, voi încerca să răspund la întrebările:

de ce nu erau sortate corect numele de femei
de ce LANG=ro_RO.CP1251 s-a dovedit a fi echivalent LANG=C
de ce au sort și join reprezentări diferite despre ordinea liniilor sortate
de ce în toate exemplele mele sunt erori
în fine, cum să sortezi liniile după bunul tău plac

Sortarea în Unicode

Prima oprire va fi raportul tehnic nr. 10 intitulat algoritmul de collation Unicode site-ul nostru unicode.org. Raportul conține multe detalii tehnice, așa că îmi permit să ofer un rezumat al ideilor principale.

Collation — "compararea" liniilor — baza oricărui algoritm de sortare. Algoritmii în sine pot varia ("bubble", "merge", "quick"), dar toți vor folosi compararea unui set de linii pentru a determina ordinea acestora.

Sortarea liniilor în limbile naturale este o problemă destul de complexă. Chiar și în cele mai simple codificări pe un byte, ordinea literelor din alfabet, orice ar fi diferit de alfabetul englez, nu va coincide cu ordinea valorilor numerice cu care sunt codificate aceste litere. Astfel, în alfabetul german, litera Ö se află între O și P, iar în codarea CP850 se află între ÿ și Ü.

Poți încerca să te abstrezi de codarea specifică și să consideri „literele ideale” care sunt așezate într-o anumită ordine, așa cum este cazul în Unicode. Codările UTF8, UTF16 sau un byte KOI8-R (dacă este necesar un subset limitat de Unicode) vor oferi reprezentări numerice diferite ale literelor, dar se vor referi la aceleași elemente din tabela de bază.

Se pare că chiar și construind o tabelă de caractere de la zero, nu vom putea stabili un ordonare universală a caracterelor. În diferite alfabeturi naționale care folosesc aceleași litere, ordinea acestor litere poate diferi. De exemplu, în limba franceză Æ va fi considerată o ligatură și sortată ca un șir AE. În limba norvegiană Æ va fi o literă separată, care se plasează după Z. Apropo, pe lângă ligaturi de tipul Æ există litere care sunt scrise cu mai multe caractere. De exemplu, în alfabetul ceh există litera Ch, care se află între H și I.

. Pe lângă diferențele dintre alfabete, există și alte tradiții naționale care influențează ordonarea. În special, apare întrebarea: în ce ordine ar trebui să urmeze în dicționar cuvintele formate din litere mari și litere mici? De asemenea, ordonarea poate fi influențată de particularitățile utilizării semnelor de punctuație. În limba spaniolă, la începutul unei propoziții interogative se pune semnul întrebării întors (¿Te gusta la música?). În acest caz, este evident că propozițiile interogative nu ar trebui să fie grupate într-un cluster separat din afara alfabetului, iar cum să sortăm șirurile cu alte semne de punctuație?

Nu voi insista asupra ordonării șirurilor în limbi care diferă semnificativ de limbile europene. Voi sublinia că în limbile cu direcția de scriere de la dreapta la stânga sau de sus în jos, caracterele din șiruri sunt, cel mai probabil, stocate în ordinea lecturii, iar chiar și în scrierile non-alfabetice există propriile metode de ordonare pe caractere. De exemplu, hieroglifurile pot fi ordonate după formă (cheile hieroglifelor chinezești) sau după pronunție. Cum ar trebui ordonate emoji-urile, sincer să fiu, nu îmi dau seama, dar pentru ele se poate inventa ceva.

Pe baza caracteristicilor enumerate mai sus, au fost formulate cerințele de bază pentru compararea șirurilor, bazate pe tabele Unicode:

compararea șirurilor nu depinde de poziția caracterelor în tabela de coduri;
secvențele de caractere care formează un singur caracter sunt aduse la forma canonică (A + cerculețul de sus este același cu Å);
în compararea șirurilor, caracterul este considerat în contextul șirului și, dacă este necesar, este combinat cu vecinii într-o singură unitate de comparație (Ch în cehă) sau este împărțit în mai multe (Æ în franceză);
toate caracteristicile naționale (alfabet, litere mari/mici, semne de punctuație, ordinea tipurilor de scriere) trebuie să fie configurate până la o asignare manuală a ordinii (emoji);
comparația este importantă nu doar pentru sortare, ci și în multe alte locuri, de exemplu pentru a defini intervalele de rânduri (substituirea {A… я} în bash);
comparația trebuie să se realizeze suficient de repede.

În plus, autorii raportului au formulat proprietăți ale comparației pe care dezvoltatorii de algoritmi nu ar trebui să se bazeze:

algoritmul de comparație nu ar trebui să necesite un set separat de caractere pentru fiecare limbă (limbile rusă și ucraineană folosesc împreună majoritatea caracterelor chirilice);
comparația nu ar trebui să se bazeze pe ordinea caracterelor din tabelele Unicode;
greutatea unui șir nu ar trebui să fie un atribut al șirului, deoarece același șir în diferite contexte culturale poate avea greutăți diferite;
greutățile șirurilor pot varia la fuziune sau la divizare (din x < Stabiliți o parolă și păstrați-o în siguranță! nu înseamnă că xz < yz);
șiruri diferite, care au aceeași greutate, sunt considerate egale din perspectiva algoritmului de sortare. Introducerea unui ordin suplimentar pentru astfel de șiruri este posibilă, dar poate reduce performanța;
la sortările repetate, șirurile cu aceeași greutate se pot schimba între ele. Stabilitatea este o proprietate specifică a unui algoritm de sortare, nu a algoritmului de comparație a șirurilor (vezi punctul anterior);
regulile de sortare se pot schimba în timp pe măsură ce tradițiile culturale sunt clarificate/alterate.

De asemenea, se stipulează că algoritmul de comparație nu are cunoștințe despre semantica șirurilor procesate. Astfel, șirurile formate doar din cifre nu ar trebui să fie comparate ca numere, iar în listele de denumiri în engleză, articolul nu ar trebui omis (Beatles, The).

Pentru a satisface toate cerințele menționate, a fost propus un algoritm de sortare în mai multe niveluri (de fapt, patru niveluri).

În prealabil, caracterele din șir sunt aduse la forma canonică și grupate în unități de comparație. Fiecărei unități de comparație i se atribuie mai multe greutăți, corespunzătoare mai multor niveluri de comparație. Greutățile unităților de comparație sunt elemente ale mulțimilor ordonate (în acest caz numere întregi), care pot fi comparate ca fiind mai mari sau mai mici. Valoarea specială IGNORED (0x0) înseamnă că la nivelul corespunzător comparației, această unitate nu participă la comparație. Comparația stringurilor poate fi repetată de mai multe ori, folosind greutăți corespunzătoare nivelurilor. La fiecare nivel, greutățile unităților de comparație ale celor două stringuri sunt comparate una cu cealaltă.

În diferite implementări ale algoritmului pentru tradiții naționale diferite, valorile coeficientului pot varia, dar standardul Unicode include o tabelă de greutăți de bază — "Default Unicode Collation Element Table" (DUCET). Vreau să menționez că setarea variabilei LC_COLLATE constituie de fapt o indicație pentru alegerea tabelei de greutăți în funcția de comparație a stringurilor.

Coeficientii de greutate DUCET sunt structurați astfel:

la primul nivel, toate literele sunt aduse la același registru, semnele diacritice sunt eliminate, iar semnele de punctuație (nu toate) sunt ignorate;
la al doilea nivel, se iau în considerare numai semnele diacritice;
la al treilea nivel, se ia în considerare numai registrul;
la al patrulea nivel, se iau în considerare doar semnele de punctuație.

Comparația se desfășoară în mai multe treceri: mai întâi se compară coeficientii de la primul nivel; dacă greutățile coincid, se face o comparație repetată cu greutățile celui de-al doilea nivel; apoi, posibil, al treilea și al patrulea.

Comparația se încheie atunci când în stringuri se găsesc unități de comparație corespunzătoare cu greutăți diferite. Stringurile care au greutăți egale la toate cele patru niveluri sunt considerate egale între ele.

Acest algoritm (cu o mulțime de detalii tehnice suplimentare) a dat denumirea raportului nr. 10 — "Unicode Collation Algorithm" (UCA).

În acest loc, comportamentul sortării din exemplul nostru devine puțin mai clar. Ar fi bine să-l comparăm cu standardul Unicode.

Pentru testarea implementărilor UCA există un test, care utilizează fișierul de greutăți, implementând DUCET. În fișierul de greutăți pot fi găsite diverse curiozități. De exemplu, există ordinea pieselor de mahjong și a domino-ului european, precum și ordinea simbolurilor în pachetul de cărți (simbolul 1F000 și așa mai departe). Mastrele cărților sunt aranjate conform regulilor de bridge — PCHBT, iar cărțile dintr-o suită — în ordinea T,2,3… K.

Verificarea manuală a corectitudinii sortării stringurilor conform DUCET ar fi fost destul de obositoare, dar, din fericire pentru noi, există o implementare exemplară a bibliotecii pentru lucrul cu Unicode – "Componente Internaționale pentru Unicode" (ICU).

Pe site-ul acestei biblioteci, dezvoltată în IBM, există pagini de demonstrație, inclusiv pagina algoritmului de comparare a stringurilor. Introducem stringurile noastre de testare cu setările implicite și, oh, minune, obținem o sortare perfectă în rusă.

Abakanov Mihail; zugrav
Elkina Ella; macaragiu
Ivanov Andrei; instalator
Ivanova Alla; avocat

Apropo, pe site-ul ICU poți găsi clarificări despre modul de funcționare al algoritmului de comparare în cazul procesării semnelor de punctuație. În exemplele Întrebări frecvente despre Collation se ignoră apostroful și cratima.

Unicode ne-a ajutat, dar va trebui să căutăm motivele comportamentului ciudat sort în Linux în altă parte.

Sortare în glibc

O privire rapidă asupra codului sursă al utilitarului sort din GNU Core Utils a arătat că localizarea în utilitar se reduce la afișarea valorii curente a variabilei LC_COLLATE la pornirea în modul de depanare:

$ sort --debug buhg.txt > buhg.srt
sort: folosind regulile de sortare 'en_US.UTF8'

Compararea stringurilor se face cu funcția standard strcoll, ceea ce înseamnă că tot ce este interesant se află în biblioteca glibc.

Pe wiki proiectului glibc care este consacrată comparării stringurilor unui paragraf. Din acest paragraf putem înțelege că în glibc sortarea se bazează pe algoritmul deja cunoscut UCA (Algoritmul de collation Unicode) și/sau pe un standard apropiat ISO 14651 (Ordinea și compararea stringurilor internaționale). Despre acest ultim standard trebuie remarcat faptul că pe site-ul standards.iso.org ISO 14651 este declarat oficial accesibil publicului, dar linkul corespunzător duce la o pagină inexistentă. Google oferă câteva pagini cu linkuri către site-uri oficiale care oferă cumpărarea unei copii electronice a standardului pentru o sută de euro, dar pe a treia sau a patra pagină din rezultatele căutării se pot găsi și linkuri directe către PDF. În general, standardul nu se deosebește foarte mult de UCA, dar este mai puțin captivant, deoarece nu conține exemple vii ale particularităților naționale ale sortării stringurilor.

Cea mai interesantă informație de pe wiki s-a dovedit a fi un link către bug tracker cu discuții despre implementarea comparării stringurilor în glibc. Din discuție putem învăța că în glibc pentru compararea stringurilor se folosește ISOtabelul Tabela Comună de Șabloane (CTT), adresa căruia poate fi găsită în anexa A standardului ISO 14651. Între anii 2000 și 2015, acest tabel în glibc nu avea un menținător și se deosebea destul de mult (cel puțin exterior) de versiunea actuală a standardului. Între 2015 și 2018 a avut loc adaptarea la noua versiune a tabelului și în prezent aveți șansa să întâlniți în viața reală atât varianta nouă a tabelului (CentOS 8), cât și cea veche (CentOS 7).

Acum, când avem toată informația despre algoritm și tabelele auxiliare, putem reveni la problema inițială și înțelege cum să sortăm corect șirurile în localizarea rusă.

ISO 14651/14652

Codul sursă al tabelului care ne interesează CTT în majoritatea distribuțiilor Linux se află în directorul /usr/share/i18n/locales/. Tabelul însuși se află în fișierul iso14651_t1_common. Apoi, acest fișier cu directiva copy iso14651_t1_common este inclus în fișierul iso14651_t1, care, la rândul său, este inclus în fișierele naționale, inclusiv în en_US și ru_RU. În majoritatea distribuțiilor Linux toate fișierele sursă sunt incluse în instalația de bază, dar dacă nu sunt disponibile, va trebui să instalați un pachet suplimentar din distribuție.

Structura fișierului iso14651_t1 poate părea extrem de detaliată, cu reguli de denumire neclare, dar dacă analizați, totul este destul de simplu. Structura este descrisă în standardul ISO 14652, o copie a căruia poate fi descărcată de pe site-ul open-std.org. O altă descriere a formatului fișierului poate fi citită în specificații POSIX de la OpenGroup. Ca alternativă la citirea standardului, puteți studia codul sursă al funcției collate_read în glibc/locale/programs/ld-collate.c.

Structura fișierului arată astfel:

În mod implicit, simbolul este folosit ca simbol de escape, iar sfârșitul liniei după simbolul # este un comentariu. Ambele simboluri pot fi redefine, ceea ce a fost realizat în noua versiune a tabelului:

escape_char /
comment_char %

În fișier vor apărea tokeni în formatul <Uxxxx> sau <Uxxxxxxxx> (unde x — este o cifră hexadecimală). Aceasta reprezintă reprezentarea hexadecimală a pozițiilor de cod Unicode în codificarea UCS-4 (UTF-32). Toate celelalte elemente din paranteze unghiulare (inclusiv <Uxxxx_xxxx>, <2> și similare), sunt considerate constante de șiruri simple, fără un sens special în afara contextului.

Șirul LC_COLLATE ne spune că datele care urmează descriu comparația șirurilor.

Mai întâi se stabilesc numele pentru greutăți în tabelul de comparație și numele pentru combinațiile de simboluri. În general, cele două tipuri de nume aparțin unor entități diferite, dar în fișierul real sunt amestecate. Numele greutăților sunt definite prin cuvântul cheie collating-symbol (simbol de comparare), deoarece atunci când se compară simbolurile Unicode cu greutăți identice, acestea vor fi considerate simboluri echivalente.

Lungimea totală a secțiunii în revizia curentă a fișierului este de aproximativ 900 de linii. Am extras exemple din mai multe locuri pentru a ilustra arbitraritatea numelui și câteva tipuri de sintaxă.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Valoarea garantată cea mai mare a simbolului. Mantenere la sfârșitul acestei liste
...
collating-element  from ""
collating-element  from ""

collating-symbol înregistrează un șir OSMANYA în tabelul de nume ale greutăților
collating-symbol .. înregistrează o secvență de nume formată dintr-un prefix S și un sufix numeric hexazecimal din 1D000 la 1D35F.
FFFF în collating-symbol arată ca un întreg nesemnat mare în sistemul de numerotare hexazecimală, dar <SFFFF> este doar un nume care ar putea arăta ca <VERYBIGVAL>
nume <U0413> reprezintă un punct de cod în codificare UCS-4
collating-element from "" înregistrează un nou nume pentru o pereche de puncte Unicode.

Odată ce numele greutăților sunt definite, se stabilesc propriile greutăți. Deoarece în comparație contează doar relațiile mai-mult/mai puțin, greutățile sunt definite printr-o secvență simplă de enumerare a numelui. Mai întâi se enumeră greutățile "mai ușoare", apoi cele "mai grele". Vreau să reamintesc că fiecărui simbol Unicode îi sunt atribuite patru greutăți diferite. Aici acestea sunt consolidate într-o secvență ordonată unică. Teoretic, orice nume simbolic poate fi folosit pe oricare dintre cele patru niveluri, dar comentariile sugerează că dezvoltatorii împart mental numele pe niveluri.

% Alocările de greutate simbolică

% Alocările de greutate de nivelul 3




...
% Alocările de greutate de nivelul 2

 % LINIE DE COMBINARE JOASĂ
 % VIRGULĂ DEASUPRA
 % VIRGULĂ ÎNREVERZATĂ DEASUPRA
...
% Alocările de greutate de nivelul 1
 % TABULARE ORIZONTALĂ
 % ÎNCHEIERE LINIE
 % TABULARE VERTICALĂ
...
 % LITERA MICĂ CYRILICĂ DE
 % LITERA MICĂ CYRILICĂ KOMI DE
 % LITERA MICĂ CYRILICĂ DJE
 % LITERA MICĂ CYRILICĂ KOMI DJE
 % LITERA MICĂ CYRILICĂ GJE
 % LITERA MICĂ CYRILICĂ ZE CU DESCENS
 % LITERA MICĂ CYRILICĂ IE
 % LITERA MICĂ CYRILICĂ IE CU BREVE
 % LITERA MICĂ CYRILICĂ IE UCRAINEANĂ
 % LITERA MICĂ CYRILICĂ ZHE

În cele din urmă, tabelul greutăților propriu-zis.

Secțiunea greutăților este închisă în rânduri cu cuvinte cheie order_start și order_end. Parametrii suplimentari order_start stabilește în ce direcție sunt examinate rândurile la fiecare nivel de comparație. Prin default, se folosește parametrul forward. Corpul secțiunii constă din rânduri care conțin codul simbolului și cele patru greutăți ale acestuia. Codul simbolului poate fi reprezentat de simbolul însuși, de punctul de cod sau de numele simbolic definit anterior. Greutățile pot fi, de asemenea, specificate prin nume simbolice, puncte de cod sau simboluri în sine. Dacă se folosesc puncte de cod sau simboluri, atunci greutatea lor coincide cu valoarea numerică a punctului de cod (poziția în tabelul Unicode). Simbolurile care nu sunt specificate explicit (așa cum îmi dă impresia) sunt considerate a fi atribuite în tabel cu o greutate primară, care coincide cu poziția în tabelul Unicode. Valoarea specială a greutății IGNORE semnifică faptul că la nivelul respectiv de comparație, acest simbol este ignorat.

Pentru a demonstra structura greutăților, am ales trei fragmente destul de evidente:

simboluri care sunt complet ignorate
simboluri echivalente cu cifra trei la primele două niveluri
începutul alfabetului chirilic, care nu conține semne diacritice și, prin urmare, este sortat în principal pe baza primului și al treilea nivel.

ordine_start forward;forward;forward;forward,pozitie
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % ÎNCEPUTUL ANTETULUI (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % ÎNCEPUTUL TEXTULUI (in 6429)
...
 ;;; % CIFRA TREI
 ;;; % CIFRA TREI ÎN PLIN
 ;;; % CIFRA TREI ÎN PARANTEZE
 ;;; % CIFRA TREI PUNCT
 ;;; % CIFRA TREI BOLD MATEMATIC
...
 ;;; % LITERA MICĂ CYRILICĂ A
 ;;; % LITERA MARE CYRILICĂ A
 ;;; % LITERA MICĂ CYRILICĂ A CU BREVI
 ;;; % LITERA MICĂ CYRILICĂ A CU BREVI
...
 ;;; % LITERA MICĂ CYRILICĂ BE
 ;;; % LITERA MARE CYRILICĂ BE
 ;;; % LITERA MICĂ CYRILICĂ VE
 ;;; % LITERA MARE CYRILICĂ VE
...
ordine_end

Acum putem reveni la sortarea exemplelor din începutul articolului. Problema este în această parte a tabelului greutăților:

IGNORE;IGNORE;IGNORE; % SPAȚIU
 IGNORE;IGNORE;IGNORE; % SEMN DE EXCLAMARE
 IGNORE;IGNORE;IGNORE; % SEMN DE ÎNTREBARE
...

Se observă că în acest tabel semnele de punctuație din tabelul ASCII (inclusiv spațiul) sunt practic întotdeauna ignorate la compararea șirurilor. Excepția o constituie doar șirurile care coincid în totalitate, cu excepția semnelor de punctuație care apar în poziții corespunzătoare. Șirurile din exemplul meu (după sortare) pentru algoritmul de comparare arată astfel:

Abakanov Mihail Malar
Elkina Ella Crănoastră
Ivanova Alla Malar
Ivanov Andrei Tăietor

Având în vedere că în tabelul greutăților literele mari din limba rusă vin după cele mici (la nivelul trei <CAP> mai greu decât <MIN>), sortarea arată absolut corect.

La setarea variabilei LC_COLLATE=C se încarcă un tabel special care stabilește compararea pe octeți

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* tabelul de primul nivel */
  6 * sizeof (uint32_t),
  /* tabelul de al doilea nivel */
  7 * sizeof (uint32_t),
  /* tabelul de al treilea nivel */
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'fe', L'xff'
};

Deoarece în Unicode punctul de cod pentru Ё este înaintea lui A, șirurile sunt sortate corespunzător.

Tabele text și binare

Este evident că compararea șirurilor este o operațiune extrem de frecventă, iar analiza tabelului CTT o procedură destul de costisitoare. Pentru a optimiza accesul la tabel, ea este compilată într-o formă binară cu ajutorul comenzii localedef.

Comanda localedef primește ca parametri un fișier cu tabelul caracteristicilor naționale (opțiunea -i), în care toate simbolurile sunt reprezentate prin puncte Unicode, și un fișier de corespondență între punctele Unicode și simbolurile unei anumite codificări (opțiunea -f). Ca rezultat al execuției, se creează fișiere binare pentru locală, cu numele specificat în ultimul parametru.

Glibc suportă două formate de fișiere binare: "tradițional" și "modern".

Formatul tradițional presupune că numele locală este numele unui subdirector în /usr/lib/locale/. În acest subdirector sunt stocate fișierele binare LC_COLLATE, LC_CTYPE, LC_TIME etc. Fișierul LC_IDENTIFICATION conține numele formal al localității (care poate diferi de numele directorului) și comentarii.

Formatul modern presupune stocarea tuturor localelor într-un singur arhivă /usr/lib/locale/locale-archive, care este mapată în memoria virtuală a tuturor proceselor ce utilizează glibc. Numele localei în formatul modern este supus unei canonizări — în denumirile codificărilor rămân doar cifrele și literele, aduse la litere mici. Astfel ru_RU.KOI8-R, va fi salvat ca ru_RU.koi8r.

Fișierele de intrare sunt căutate în directorul curent, precum și în directoarele /usr/share/i18n/locales/ și /usr/share/i18n/charmaps/ pentru fișiere CTT și fișiere de codificare, respectiv.

De exemplu, comanda

localedef -i ru_RU -f MAC-CYRILLIC ru_RU.MAC-CYRILLIC

va compila fișierul /usr/share/i18n/locales/ru_RU folosind fișierul de codificare /usr/share/i18n/charmaps/MAC-CYRILLIC.gz și va salva rezultatul în /usr/lib/locale/locale-archive cu numele ru_RU.maccyrillic

Dacă se setează variabila LANG=en_US.UTF-8 atunci glibc va căuta fișierele binare ale localelor în următoarea succesiune de fișiere și directoare:

/usr/lib/locale/locale-archive
/usr/lib/locale/en_US.UTF-8/
/usr/lib/locale/en_US/
/usr/lib/locale/enUTF-8/
/usr/lib/locale/en/

Dacă locală apare atât în formate tradiționale, cât și în cele moderne, prioritatea este dată formatului modern.

Pentru a vizualiza lista localelor compilate, se poate folosi comanda locale -a.

Pregătirea propriei tabele de comparare

Acum, dispunând de cunoștințe, se poate crea propria tabelă ideală de comparare a șirurilor. Această tabelă trebuie să compare corect literele rusești, inclusiv litera Ё, și să țină cont de semnele de punctuație conform tabelei ASCII.

Procesul de pregătire a propriei tabele de ordonare constă în două etape: editarea tabelei de greutăți și compilarea acesteia în formă binară cu comanda localedef.

Pentru a ajusta tabela de comparare cu costuri minime pentru editare, în formatul ISO 14652 se preconizează secțiuni de ajustare a greutăților pentru tabelul existent. Secțiunea începe cu cuvântul cheie reorder-after și indicarea poziției după care se efectuează înlocuirea. Secțiunea se finalizează cu linia reorder-end. Dacă trebuie să corectez mai multe porțiuni ale tabelului, se creează câte o secțiune pentru fiecare porțiune.

Am copiat noile versiuni ale fișierelor iso14651_t1_common și ru_RU din depozit glibc în directorul meu personal ~/.local/share/i18n/locales/ și am editat ușor secțiunea LC_COLLATE în ru_RU. Noile versiuni ale fișierelor sunt complet compatibile cu versiunea mea glibc. Dacă dorești să folosești versiunile vechi ale fișierelor, va trebui să schimbi numele simbolice și locul de unde începe înlocuirea în tabel.

LC_COLLATE
% Copiați șablonul din ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPAȚIU
 ;;; % SEMN EXCLAMARE
 ;;; % SEMN CITARE
...
 ;;; % PARANTEZĂ ÎNCHEIATĂ ÎN DREAPTA
 ;;; % TILDĂ
reorder-end
END LC_COLLATE

De fapt, ar fi trebuit să schimb câmpurile în LC_IDENTIFICATION astfel încât să indice pe localitatea ru_MY, dar în exemplul meu acest lucru nu a fost necesar, deoarece am exclus din căutare arhiva localizărilor locale-archive.

Pentru a localedef am lucrat cu fișiere în directorul meu prin variabila I18NPATH se poate adăuga un director suplimentar pentru căutarea fișierelor de intrare, iar directorul pentru salvarea fișierelor binare poate fi specificat sub formă de cale cu slash-uri:

$> I18NPATH=~/.local/share/i18n localedef -i ru_RU -f UTF-8 ~/.local/lib/locale/ru_MY.UTF-8

POSIX presupune că LANG poate scrie căi absolute către directoarele cu fișierele localizărilor, începând cu slash-ul direct, dar glibc în Linux toate căile sunt considerate a fi de la directorul de bază, care poate fi redefinit prin variabila LOCPATH. După setarea LOCPATH=~/.local/lib/locale/ toate fișierele legate de localizare vor fi căutate doar în directorul meu. Arhiva localizărilor cu variabila setată LOCPATH este ignorată.

Iată testul decisiv:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mihail;vopsitor
Elkina Ella;crainică
Ivanov Andrei;instalator
Ivanova Alla;avocat

Ura! Am reușit!

Lucru la erori

Am răspuns deja întrebărilor despre sortarea rândurilor, ridicate la început, dar mai există câteva întrebări despre erori – vizibile și invizibile.

Să ne întoarcem la sarcina originală.

Și programul sort și programul join folosesc aceleași funcții de comparare a rândurilor din glibc. Cum a fost posibil că join a returnat o eroare de sortare pe liniile sortate de comanda sort în locală en_US.UTF-8? Ответ прост: sort compara întreaga linie, în timp ce join compara doar cheia, care în mod implicit este începutul liniei până la primul caracter de spațiu. În exemplul meu, acest lucru a dus la un mesaj de eroare, deoarece sortarea primelor cuvinte din linii nu s-a potrivit cu sortarea liniilor complete.

Locale "C" garantează că subșirurile inițiale până la primul spațiu din liniile sortate vor fi de asemenea sortate, dar acest lucru doar maschează eroarea. Se pot alege date de tipul (persoane cu aceeași prenume, dar nume diferite), care fără mesaj de eroare ar da un rezultat greșit la fuziunea fișierelor. Dacă dorim ca join să combine liniile fișierelor după nume și prenume, atunci cea mai bună metodă este să specificăm despartitorul de câmpuri și să sortăm după câmpul cheie, nu după întreaga linie. În acest fel, fuziunea va decurge corect și nu vor exista erori în nicio locală:

$> sort -t ; -k 1 buhg.txt > buhg.srt
$> sort -t ; -k 1 mail.txt > mail.srt
$> join -t ; buhg.srt mail.srt > result

Un exemplu de succes în codificare CP1251 conține o altă eroare. Este vorba că în toate distribuțiile pe care le cunosc Linux pachetele nu conțin localul compilat ru_RU.CP1251. Dacă locația compilată nu este găsită, atunci sort folosește în tăcere o comparație pe byte, ceea ce am observat.

Apropo, există o altă mică eroare legată de inaccesibilitatea localurilor compilate. Comanda LOCPATH=/tmp locale -a va returna o listă cu toate localurile din locale-archive, dar cu variabila setată LOCPATH pentru toate programele (inclusiv pentru sinele locale) aceste localuri vor fi inaccesibile.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: using ‘en_US.UTF-8’ sorting rules

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: using simple byte comparison

Concluzie

Dacă ești un programator care este obișnuit să considere că liniile sunt un set de byte, atunci alegerea ta LC_COLLATE=C.

Dacă ești un lingvist sau un compilator de dicționare, atunci cel mai bine este să compilezi propria ta locală.

Dacă ești un utilizator obișnuit, atunci este suficient să te obișnuiești cu faptul că comanda ls -a returnează fișierele care încep cu punct, amestecate cu fișierele care încep cu literă, iar Midnight Commander, care utilizează funcțiile interne pentru a sorta numele, mută fișierele care încep cu punct, la începutul listei.