Introducere

Totul a început cu un scurt script care trebuia să combine informații despre adresă e-mail angajați obținuți din lista utilizatorilor listei de corespondență, cu posturi de angajați obținute din baza de date a departamentului HR. Ambele liste au fost exportate în fișiere text Unicode UTF-8 și salvat cu terminații de linie Unix.

conținut mail.txt

Иванов Андрей;[email protected]

conținut buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

Pentru a fuziona, fișierele au fost sortate prin comanda Unix fel și trimis la intrarea programului Unix alătura, care a eșuat în mod neașteptat cu o eroare:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

Privind rezultatul sortării cu ochii tăi a arătat că, în general, sortarea este corectă, dar în cazul coincidențelor numelor de familie masculin și feminin, cele feminine vin înaintea celor masculine:

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

Arată ca o eroare de sortare în Unicode sau ca o manifestare a feminismului în algoritmul de sortare. Prima este, desigur, mai plauzibilă.

Să amânăm deocamdată alătura și concentrează-te pe fel. Să încercăm să rezolvăm problema folosindu-i științific. Mai întâi, să schimbăm localitatea de la ro_ pe ru_ru. Pentru a sorta, ar fi suficient să setați variabila de mediu LC_COLLATE, dar nu vom pierde timpul cu fleacuri:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

Nimic nu s-a schimbat.

Să încercăm să recodificăm fișierele într-o codificare pe un singur octet:

$> 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 poți face nimic, va trebui să cauți o soluție pe internet. Nu există nimic direct despre numele de familie rusești, dar există întrebări despre alte ciudățenii de sortare. De exemplu, aici este o problemă: sortarea unix tratează caracterele „-” (liniuță) ca fiind invizibile. Pe scurt, șirurile „ab”, „aa”, „ac” sunt sortate ca „aa”, „ab”, „ac”.

Răspunsul este standard peste tot: utilizați localitatea programatorului "C" si vei fi fericit. Sa incercam:

$> LANG=C sort buhg.txt
Ёлкина Элла;крановщица
Абаканов Михаил;маляр
Иванов Андрей;слесарь
Иванова Алла;адвокат

Ceva sa schimbat. Ivanovii s-au aliniat în ordinea corectă, deși Yolkina a alunecat undeva. Să revenim la problema 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 Yolkina în prima linie.

Problema pare a fi rezolvată, dar pentru orice eventualitate, să încercăm o altă codificare rusă - Windows CP1251:

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

Rezultatul sortării, destul de ciudat, va coincide cu locația "C", iar întregul exemplu, în consecință, rulează fără erori. Un fel de misticism.

Nu-mi place misticismul în programare pentru că de obicei maschează greșelile. Va trebui să ne uităm serios cum funcționează. fel si ce afecteaza? LC_COLLATE .

La final voi încerca să răspund la întrebări:

de ce au fost sortate greșit numele de familie ale femeilor?
de ce LANG=ru_RU.CP1251 s-a dovedit a fi echivalent LANG=C
de ce face fel и alătura idei diferite despre ordinea șirurilor sortate
de ce sunt erori în toate exemplele mele?
în sfârșit, cum să sortați șirurile după bunul plac

Sortare în Unicode

Prima oprire va fi raportul tehnic nr.10 intitulat Algoritmul de colare Unicode on-line unicode.org. Raportul conține multe detalii tehnice, așa că permiteți-mi să fac un scurt rezumat al ideilor principale.

Colaționare — „compararea” șirurilor este baza oricărui algoritm de sortare. Algoritmii înșiși pot diferi („bubble”, „merge”, „rapid”), dar toți vor folosi o comparație a unei perechi de șiruri pentru a determina ordinea în care apar.

Sortarea șirurilor în limbaj natural este o problemă destul de complexă. Chiar și în cele mai simple codificări pe un singur octet, ordinea literelor din alfabet, chiar diferită într-un fel de alfabetul latin englez, nu va mai coincide cu ordinea valorilor numerice cu care sunt codificate aceste litere. Deci, în alfabetul german litera Ö stă între О и P, și în codificare CP850 ea se pune între ÿ и Ü.

Puteți încerca să faceți abstracție dintr-o codificare specifică și să luați în considerare literele „ideale” care sunt aranjate într-o anumită ordine, așa cum se face în Unicode. Codificări UTF8, UTF16 sau de un octet KOI8-R (dacă este necesar un subset limitat de Unicode) va oferi reprezentări numerice diferite ale literelor, dar se referă la aceleași elemente ale tabelului de bază.

Se pare că, chiar dacă construim un tabel de simboluri de la zero, nu vom putea să-i atribuim o ordine universală a simbolurilor. În diferite alfabete naționale care folosesc aceleași litere, ordinea acestor litere poate diferi. De exemplu, în franceză Æ va fi considerată o ligatură și sortată ca șir AE. În norvegiană Æ va fi o scrisoare separată, care se află după Z. Apropo, pe lângă ligaturi ca Æ Există litere scrise cu mai multe simboluri. Deci, în alfabetul ceh există o literă Ch, care se află între H и I.

Pe lângă diferențele de alfabet, există și alte tradiții naționale care influențează sortarea. În special, se pune întrebarea: în ce ordine ar trebui să apară în dicționar cuvintele formate din litere mari și mici? Sortarea poate fi, de asemenea, afectată de utilizarea semnelor de punctuație. În spaniolă, un semn de întrebare inversat este folosit la începutul unei propoziții interogative (Îți place muzica?). În acest caz, este evident că propozițiile interogative nu trebuie grupate într-un grup separat în afara alfabetului, dar cum să sortăm liniile cu alte semne de punctuație?

Nu mă voi opri asupra sortării șirurilor în limbi foarte diferite de cele europene. Rețineți că în limbile cu o direcție de scriere de la dreapta la stânga sau de sus în jos, caracterele din rânduri sunt cel mai probabil stocate în ordine de citire și chiar și sistemele de scriere non-alfabetice au propriile moduri de a ordona liniile caracter cu caracter . De exemplu, hieroglifele pot fi ordonate după stil (Taste cu caractere chinezești) sau prin pronunție. Sincer să fiu, nu am idee cum ar trebui aranjate emoji-urile, dar poți găsi ceva și pentru ele.

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

compararea șirurilor de caractere nu depinde de poziția caracterelor în tabelul de coduri;
secvențele de caractere care formează un singur caracter sunt reduse la formă canonică (A + cercul de sus este același cu Å);
La compararea șirurilor, un caracter este considerat în contextul șirului și, dacă este necesar, combinat cu vecinii săi într-o unitate de comparație (Ch în cehă) sau este împărțit în mai multe (Æ in franceza);
toate caracteristicile naționale (alfabet, majuscule/minuscule, punctuație, ordinea tipurilor de scriere) trebuie configurate până la atribuirea manuală a ordinii (emoji);
comparația este importantă nu numai pentru sortare, ci și în multe alte locuri, de exemplu pentru specificarea intervalelor de rânduri (înlocuind {A... z} în pocni);
comparația ar trebui făcută destul de repede.

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

algoritmul de comparare nu ar trebui să necesite un set separat de caractere pentru fiecare limbă (limbile rusă și ucraineană au cele mai multe caractere chirilice);
comparația nu trebuie să se bazeze pe ordinea caracterelor din tabelele Unicode;
greutatea șirului nu ar trebui să fie un atribut al șirului, deoarece același șir în contexte culturale diferite poate avea ponderi diferite;
Greutățile rândurilor se pot schimba la îmbinare sau împărțire (de la x < y nu rezulta asta xz < yz);
șiruri diferite având aceleași ponderi sunt considerate egale din punctul de vedere al algoritmului de sortare. Este posibilă introducerea unei ordonări suplimentare a unor astfel de șiruri, dar poate degrada performanța;
În timpul sortării repetate, rândurile cu aceleași greutăți pot fi schimbate. Robustitatea este o proprietate a unui anumit algoritm de sortare, și nu o proprietate a unui algoritm de comparare a șirurilor (vezi paragraful anterior);
Regulile de sortare se pot schimba în timp pe măsură ce tradițiile culturale se rafinează/se schimbă.

De asemenea, se prevede că algoritmul de comparație nu știe nimic despre semantica șirurilor care sunt procesate. Astfel, șirurile care constau numai din cifre nu trebuie comparate ca numere, iar în listele de nume englezești articolul (Beatles, The).

Pentru a satisface toate aceste cerințe, se propune un algoritm de sortare a tabelelor pe mai multe niveluri (de fapt, cu patru niveluri).

Anterior, caracterele din șir sunt reduse la formă canonică și grupate în unități de comparație. Fiecărei unități de comparație i se atribuie mai multe ponderi 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 pentru mai mult sau mai puțin. Înțeles special IGNORAT (0x0) înseamnă că la nivelul de comparație corespunzător această unitate nu este implicată în comparație. Comparația șirurilor poate fi repetată de mai multe ori, folosind greutățile nivelurilor corespunzătoare. La fiecare nivel, ponderile unităților de comparare a două rânduri sunt comparate secvenţial între ele.

În diferite implementări ale algoritmului pentru diferite tradiții naționale, valorile coeficienților pot diferi, dar standardul Unicode include un tabel de bază de ponderi - „Tabelul de elemente de colaţionare Unicode implicit” (DUCET). Aș dori să remarc faptul că setarea variabilei LC_COLLATE este de fapt o indicație a selecției tabelului de greutate în funcția de comparare a șirurilor.

Coeficienți de ponderare DUCET dispuse astfel:

la primul nivel, toate literele sunt reduse la aceeași literă, semnele diacritice sunt eliminate, semnele de punctuație (nu toate) sunt ignorate;
la al doilea nivel sunt luate în considerare doar diacritice;
la al treilea nivel se ia în considerare numai cazul;
la al patrulea nivel se iau în considerare doar semnele de punctuație.

Comparația are loc în mai multe treceri: mai întâi se compară coeficienții primului nivel; dacă greutățile coincid, atunci se efectuează o comparație repetată cu greutățile de al doilea nivel; apoi poate un al treilea și al patrulea.

Comparația se termină atunci când rândurile conțin unități de comparație care se potrivesc cu greutăți diferite. Rândurile care au greutăți egale la toate cele patru niveluri sunt considerate egale între ele.

Acest algoritm (cu o grămadă de detalii tehnice suplimentare) a dat numele raportului nr. 10 - „Algoritmul de colare Unicode” (ACU).

Aici devine puțin mai clar comportamentul de sortare din exemplul nostru. Ar fi bine să-l comparăm cu standardul Unicode.

Pentru a testa implementările ACU există o specială test, folosind dosar de greutăți, implementând DUCET. Puteți găsi tot felul de lucruri amuzante în fișierul cântarilor. De exemplu, există ordinea mahjong-ului și a jocurilor de domino europene, precum și ordinea costumelor într-un pachet de cărți (simbol 1F000 și mai departe). Trusele de cărți sunt așezate conform regulilor de bridge - PCBT, iar cărțile din costum sunt în secvența T, 2,3, XNUMX... K.

Verificați manual dacă rândurile sunt sortate corect în funcție de DUCET ar fi destul de plictisitor, dar, din fericire pentru noi, există o implementare exemplară a bibliotecii pentru lucrul cu Unicode - "Componente internaționale pentru Unicode"(ATI).

Pe site-ul acestei biblioteci, dezvoltat în IBM, există pagini demo, inclusiv pagina de algoritm de comparare a șirurilor. Intrăm în liniile noastre de testare cu setări implicite și, iată, obținem o sortare perfectă în limba rusă.

Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

Apropo, site-ul ATI Puteți găsi o clarificare a algoritmului de comparație atunci când procesați semnele de punctuație. În exemple Întrebări frecvente privind colaționarea apostroful și cratima sunt ignorate.

Unicode ne-a ajutat, dar căutați motive pentru comportament ciudat fel в Linux va trebui să meargă în altă parte.

Sortare în glibc

Vedere rapidă a codurilor sursă de utilitate fel de GNU Core Utils a arătat că în utilitatea în sine, localizarea se reduce la imprimarea valorii curente a variabilei LC_COLLATE când rulați în modul de depanare:

$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rules

Comparațiile de șiruri sunt efectuate folosind funcția standard strcoll, ceea ce înseamnă că totul este interesant în bibliotecă glibc.

Pe Wiki proiect glibc dedicat comparării șirurilor un paragraf. Din acest paragraf se poate înțelege că în glibc sortarea se bazează pe un algoritm deja cunoscut de noi ACU (Algoritmul de colare Unicode) și/sau la un standard apropiat de acesta ISO 14651 (Comandarea și compararea șirurilor internaționale). În ceea ce privește ultimul standard, trebuie menționat că pe site standarde.iso.org ISO 14651 declarat oficial disponibil public, dar linkul corespunzător duce la o pagină inexistentă. Google returnează mai multe pagini cu link-uri către site-uri oficiale care oferă să cumpere o copie electronică a standardului pentru o sută de euro, dar pe a treia sau a patra pagină a rezultatelor căutării există și link-uri directe către PDF. În general, standardul nu este practic diferit de ACU, dar este mai plictisitor de citit deoarece nu conține exemple clare de caracteristici naționale ale sortării șirurilor.

Cele mai interesante informații despre Wiki a existat un link către bug tracker cu o discuție despre implementarea comparației șirurilor în glibc. Din discuție se poate învăța că glibc folosit pentru a compara șiruri ISOmasa personala Tabelul șablon comun (CTT), a cărui adresă se regăsește în cerere A standard ISO 14651. Între 2000 și 2015 acest tabel în glibc nu avea un întreținător și era destul de diferit (cel puțin extern) de versiunea actuală a standardului. Din 2015 până în 2018, a avut loc adaptarea la noua versiune a mesei, iar acum aveți șansa de a întâlni în viața reală o nouă versiune a mesei (CentOS 8), și vechi (CentOS 7).

Acum că avem toate informațiile despre algoritm și tabelele auxiliare, putem reveni la problema inițială și putem înțelege cum să sortăm corect șirurile în localitatea rusă.

ISO 14651/14652

Codul sursă al tabelului care ne interesează CTT pe majoritatea distribuțiilor Linux este in catalog /usr/share/i18n/locales/. Tabelul în sine este în fișier iso14651_t1_common. Atunci aceasta este directiva de fișiere copiați iso14651_t1_common incluse în dosar iso14651_t1, care, la rândul său, este inclusă în dosarele naționale, inclusiv ro_ и ru_ru. Pe majoritatea distribuțiilor Linux toate fișierele sursă sunt incluse în instalarea de bază, dar dacă nu sunt prezente, va trebui să instalați un pachet suplimentar din distribuție.

Structura fișierului iso14651_t1 poate părea teribil de verbos, cu reguli neevidente pentru construirea numelor, dar dacă te uiți la asta, totul este destul de simplu. Structura este descrisă în standard ISO 14652, a cărui copie poate fi descărcată de pe site open-std.org. O altă descriere a formatului de fișier poate fi citită în specificații POSIX din OpenGroup. Ca alternativă la citirea standardului, puteți studia codul sursă al funcției colate_read в glibc/locale/programs/ld-collate.c.

Structura fișierului arată astfel:

În mod implicit, caracterul este folosit ca caracter de escape, iar sfârșitul liniei după caracterul # este un comentariu. Ambele simboluri pot fi redefinite, ceea ce se face în noua versiune a tabelului:

escape_char /
comment_char %

Fișierul va conține token-uri în format sau (Unde x - cifra hexazecimală). Aceasta este reprezentarea hexazecimală a punctelor de cod Unicode din codificare UCS-4 (UTF-32). Toate celelalte elemente din paranteze unghiulare (inclusiv , <2> și altele asemenea) sunt considerate simple constante de șir care au puțină semnificație în afara contextului.

rând LC_COLLATE ne spune că în continuare încep datele care descriu comparația șirurilor.

Mai întâi, sunt specificate nume pentru greutăți în tabelul de comparație și nume pentru combinațiile de simboluri. În general, cele două tipuri de nume aparțin a două entități diferite, dar în fișierul propriu-zis sunt amestecate. Numele greutăților sunt specificate de cuvântul cheie colating-simbol (caracter de comparație) deoarece la comparare, caracterele Unicode care au aceleași greutăți vor fi considerate caractere echivalente.

Lungimea totală a secțiunii în versiunea curentă a fișierului este de aproximativ 900 de linii. Am extras exemple din mai multe locuri pentru a arăta arbitraritatea numelor și mai multe tipuri de sintaxă.

LC_COLLATE

collating-symbol <RES-1>
collating-symbol <BLK>
collating-symbol <MIN>
collating-symbol <WIDE>
...
collating-symbol <ARABIC>
collating-symbol <ETHPC>
collating-symbol <OSMANYA>
...
collating-symbol <S1D000>..<S1D35F>
collating-symbol <SFFFF> % Guaranteed largest symbol value. Keep at end of this list
...
collating-element <U0413_0301> from "<U0413><U0301>"
collating-element <U0413_0341> from "<U0413><U0341>"

colating-simbol înregistrează un șir OSMANYA în tabelul numelor de cântare
colating-simbol .. înregistrează o succesiune de nume formată dintr-un prefix S și sufix numeric hexazecimal din 1D000 la 1D35F.
FFFF в colating-simbol arată ca un întreg mare fără semn în hexazecimal, dar este doar un nume care ar putea arăta
nume înseamnă punct de cod în codificare UCS-4
element-colating din " " înregistrează un nume nou pentru o pereche de puncte Unicode.

Odată ce denumirile ponderilor sunt definite, ponderile reale sunt specificate. Deoarece doar relațiile mai mari decât mai puțin contează în comparație, ponderile sunt determinate de o simplă succesiune de nume de listare. Greutățile „mai ușoare” sunt enumerate mai întâi, apoi cele „mai grele”. Permiteți-mi să vă reamintesc că fiecărui caracter Unicode i se atribuie patru greutăți diferite. Aici ele sunt combinate într-o singură secvență ordonată. În teorie, orice nume simbolic ar putea fi folosit la oricare dintre cele patru niveluri, dar comentariile indică faptul că dezvoltatorii separă mental numele în niveluri.

% Symbolic weight assignments

% Third-level weight assignments
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Second-level weight assignments
<BASE>
<LOWLINE> % COMBINING LOW LINE
<PSILI> % COMBINING COMMA ABOVE
<DASIA> % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
<S0009> % HORIZONTAL TABULATION 
<S000A> % LINE FEED
<S000B> % VERTICAL TABULATION
...
<S0434> % CYRILLIC SMALL LETTER DE
<S0501> % CYRILLIC SMALL LETTER KOMI DE
<S0452> % CYRILLIC SMALL LETTER DJE
<S0503> % CYRILLIC SMALL LETTER KOMI DJE
<S0453> % CYRILLIC SMALL LETTER GJE
<S0499> % CYRILLIC SMALL LETTER ZE WITH DESCENDER
<S0435> % CYRILLIC SMALL LETTER IE
<S04D7> % CYRILLIC SMALL LETTER IE WITH BREVE
<S0454> % CYRILLIC SMALL LETTER UKRAINIAN IE
<S0436> % CYRILLIC SMALL LETTER ZHE

În sfârșit, tabelul de greutate reală.

Secțiunea de ponderi este inclusă în rânduri de cuvinte cheie order_start и order_end. Opțiuni suplimentare order_start determinați în ce direcție sunt scanate rândurile la fiecare nivel de comparație. Setarea implicită este înainte. Corpul secțiunii este format din linii care conțin codul simbolului și cele patru greutăți ale sale. Codul caracterului poate fi reprezentat de caracterul însuși, un punct de cod sau un nume simbolic definit anterior. Greutățile pot fi date și numelor simbolice, punctelor de cod sau simbolurilor în sine. Dacă sunt utilizate puncte de cod sau caractere, greutatea lor este aceeași cu valoarea numerică a punctului de cod (poziție în tabelul Unicode). Caracterele care nu sunt specificate în mod explicit (după cum am înțeles) sunt considerate atribuite tabelului cu o pondere primară care se potrivește cu poziția din tabelul Unicode. Valoare specială de greutate IGNORA înseamnă că simbolul este ignorat la nivelul corespunzător de comparație.

Pentru a demonstra structura scalelor, am ales trei fragmente destul de evidente:

personaje care sunt complet ignorate
simboluri echivalente cu numărul trei din primele două niveluri
începutul alfabetului chirilic, care nu conține semne diacritice și, prin urmare, este sortat în principal după primul și al treilea nivel.

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

Acum puteți reveni la sortarea exemplelor de la începutul articolului. Ambuscada se află în această parte a tabelului cu greutăți:

<U0020> IGNORE;IGNORE;IGNORE;<U0020> % SPACE
<U0021> IGNORE;IGNORE;IGNORE;<U0021> % EXCLAMATION MARK
<U0022> IGNORE;IGNORE;IGNORE;<U0022> % QUOTATION MARK
...

Se poate observa că în acest tabel semnele de punctuație din tabel ASCII (inclusiv spațiul) este aproape întotdeauna ignorat la compararea șirurilor. Singurele excepții sunt liniile care se potrivesc în orice, cu excepția semnelor de punctuație găsite în pozițiile care se potrivesc. Liniile din exemplul meu (după sortare) pentru algoritmul de comparare arată astfel:

АбакановМихаилмаляр
ЁлкинаЭллакрановщица
ИвановаАлламаляр
ИвановАндрейслесарь

Având în vedere că în tabelul scalelor, majusculele în limba rusă vin după litere mici (la al treilea nivel mai greu decat ), sortarea pare absolut corectă.

La setarea unei variabile LC_COLLATE=C este încărcat un tabel special care specifică o comparație octet cu octet

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* 1st-level table */
  6 * sizeof (uint32_t),
  /* 2nd-level table */
  7 * sizeof (uint32_t),
  /* 3rd-level table */
  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'xfe', L'xff'
};

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

Text și tabele binare

Evident, compararea șirurilor este o operație extrem de comună și analizarea tabelelor CTT o procedură destul de costisitoare. Pentru a optimiza accesul la tabel, acesta este compilat în formă binară cu comanda localdef.

Echipă localdef acceptă ca parametri un fișier cu un tabel de caracteristici naționale (opțiune -i), în care toate caracterele sunt reprezentate prin puncte Unicode și un fișier de corespondență între punctele Unicode și caracterele unei anumite codificări (opțiune -f). Ca rezultat al lucrării, fișierele binare sunt create pentru local cu numele specificat în ultimul parametru.

glibc acceptă două formate de fișiere binare: „tradițional” și „modern”.

Formatul tradițional înseamnă că numele localității este numele subdirectorului în /usr/lib/locale/. Acest subdirector stochează fișiere binare LC_COLLATE, LC_CTYPE, LC_TIME și așa mai departe. Fişier LC_IDENTIFICARE conține numele formal al localizării (care poate fi diferit de numele directorului) și comentarii.

Formatul modern implică stocarea tuturor localităților într-o singură arhivă /usr/lib/locale/locale-archive, care este mapat la memoria virtuală a tuturor proceselor care utilizează glibc. Numele local în formatul modern este supus unei anumite canonizări - în numele de codificare rămân doar numerele și literele reduse la litere mici. Asa de ru_RU.KOI8-R, va fi salvat ca ru_RU.koi8r.

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

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 salvați rezultatul în /usr/lib/locale/locale-archive sub nume ru_RU.maccyrillic

Dacă setați variabila LANG = ro_US.UTF-8 că glibc va căuta binare locale în următoarea secvență 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ă o locație apare atât în format tradițional, cât și în format modern, atunci prioritate este dată celui modern.

Puteți vizualiza lista de localități compilate cu comanda locale -a.

Pregătirea tabelului de comparație

Acum, înarmat cu cunoștințele, vă puteți crea propriul tabel ideal de comparare a șirurilor. Acest tabel ar trebui să compare corect literele rusești, inclusiv litera Ё și, în același timp, să ia în considerare semnele de punctuație în conformitate cu tabelul ASCII.

Procesul de pregătire a propriului tabel de sortare constă în două etape: editarea tabelului de ponderi și compilarea lui în formă binară cu comanda localdef.

Pentru ca tabelul de comparație să fie ajustat cu costuri minime de editare, în format ISO 14652 Sunt furnizate secțiuni pentru ajustarea greutăților unui tabel existent. Secțiunea începe cu un cuvânt cheie reordonare-după şi indicarea poziţiei după care se efectuează înlocuirea. Secțiunea se termină cu linia reordonare-sfârşit. Dacă este necesară corectarea mai multor secțiuni ale tabelului, atunci se creează o secțiune pentru fiecare astfel de secțiune.

Am copiat versiuni noi ale fișierelor iso14651_t1_common и ru_ru din depozit glibc în directorul meu de acasă ~/.local/share/i18n/locales/ și am editat ușor secțiunea LC_COLLATE в ru_ru. Noile versiuni de fișiere sunt pe deplin compatibile cu versiunea mea glibc. Dacă doriți să utilizați versiuni mai vechi de fișiere, va trebui să schimbați numele simbolice și locul de unde începe înlocuirea în tabel.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

De fapt, ar fi necesar să se schimbe câmpurile în LC_IDENTIFICARE astfel încât să indice localul ru_MY, dar în exemplul meu acest lucru nu a fost necesar, deoarece am exclus arhiva din căutarea localităților local-arhivă.

Că localdef a lucrat cu fișierele din folderul meu printr-o variabilă I18NPATH Puteți adăuga un director suplimentar pentru a căuta fișiere de intrare, iar directorul pentru salvarea fișierelor binare poate fi specificat ca o cale cu bare oblice:

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

POSIX presupune că în LIMBA puteți scrie căi absolute către directoare cu fișiere locale, începând cu o bară oblică, dar glibc в Linux toate căile sunt numărate din directorul de bază, care poate fi suprascris printr-o variabilă LOCPATH. După instalare LOCPATH=~/.local/lib/locale/ toate fișierele legate de localizare vor fi căutate numai în folderul meu. Arhiva localităților cu setul de variabile LOCPATH ignorat.

Iată testul decisiv:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

Ura! Am reusit!

Unele erori

Am răspuns deja la întrebările despre sortarea șirurilor puse la început, dar există încă câteva întrebări despre erori - vizibile și invizibile.

Să revenim la problema inițială.

Și programul fel și programează alătura utilizați aceleași funcții de comparare a șirurilor de la glibc. Cum sa întâmplat asta alătura a dat o eroare de sortare pe rândurile sortate după comandă fel în local ro_US.UTF-8? Raspunsul este simplu: fel compară întregul șir și alătura compară doar cheia, care este implicit începutul șirului până la primul caracter de spațiu alb. În exemplul meu, acest lucru a dus la un mesaj de eroare deoarece sortarea primelor cuvinte din rânduri nu se potrivea cu sortarea liniilor complete.

Locale "C" garantează că în șirurile sortate vor fi sortate și subșirurile inițiale până la primul spațiu, dar asta doar maschează eroarea. Este posibil să selectați date (persoane cu aceleași nume de familie, dar prenume diferite) care, fără mesajul de eroare, ar da un rezultat incorect de îmbinare a fișierelor. Dacă vrem alătura linii de fișier îmbinate după numele complet, atunci modalitatea corectă ar fi să specificați în mod explicit separatorul de câmpuri și să sortați după câmpul cheie, și nu după întreaga linie. În acest caz, îmbinarea se va desfășura corect și nu vor exista erori în nicio locație:

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

Exemplu executat cu succes în codificare CP1251 conține o altă eroare. Cert este că în toate distribuțiile cunoscute de mine Linux pachetelor lipsesc localitatea compilată ru_RU.CP1251. Dacă localul compilat nu este găsit, atunci fel folosește în tăcere o comparație octet cu octet, ceea ce am observat.

Apropo, există o altă mică eroare legată de inaccesibilitatea localizărilor compilate. Echipă LOCPATH=/tmp local -a va oferi o listă cu toate localitățile din local-arhivă, dar cu variabila setată LOCPATH pentru toate programele (inclusiv cele mai multe localizare) aceste localizări nu vor fi disponibile.

$> 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ă creadă că șirurile sunt un set de octeți, atunci alegerea ta LC_COLLATE=C.

Dacă sunteți lingvist sau compilator de dicționar, atunci mai bine compilați în localitatea dvs.

Dacă sunteți un utilizator simplu, atunci trebuie doar să vă obișnuiți cu faptul că comanda Este-a scoate fișiere care încep cu un punct amestecate cu fișiere care încep cu o literă și Comandantul nopții, care își folosește funcțiile interne pentru a sorta numele, plasează fișierele care încep cu un punct la începutul listei.