Úvod

Všetko sa začalo s krátkym skriptom, ktorý mal spojiť informácie o adresách e-mail zamestnancov, získaných zo zoznamu používateľov e-mailového rozosielania, s pozíciami zamestnancov, získanými z databázy oddelenia ľudských zdrojov. Oba zoznamy boli exportované do textových súborov v kódovaní Unicode UTF-8 a uložené s unixovými koncami riadkov.

Obsah mail.txt

Ivanov Andrej;ia@example.com

Obsah buhg.txt

Ivanová Alla;malár
Jelkina Ella;žeriavnik
Ivanov Andrej;sporák
Abakanov Michal;malár

Pre zlúčenie boli súbory zoradené unixovým príkazom sort a zadané do vstupu unixového programu join, ktorý náhle skončil s chybou:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nie je zoradené: Ivanov Andrej;sporák

Náhľad výsledku triedenia ukázal, že celkové triedenie je správne, ale v prípade zhodných mužských a ženských priezvisk, ženské priezviská sú pred mužskými:

$> sort buhg.txt
Abakanov Michal;malár
Jelkina Ella;žeriavnik
Ivanová Alla;malár
Ivanov Andrej;sporák

Vyzerá to ako chyba triedenia v Unicode alebo ako prejav feministického prístupu v algoritme triedenia. Prvé, samozrejme, znie pravdepodobnejšie.

Zatiaľ to nechajme tak join a sústreďme sa na sort. Skúsime vyriešiť úlohu metódou pokus-omyl. Na začiatok zmeníme lokalitu na en_US na ru_RU. Na triedenie by stačilo nastaviť premennú prostredia LC_COLLATE, ale nebudeme sa zaoberať maličkosťami:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Michal;malár
Jelkina Ella;žeriavnik
Ivanová Alla;malár
Ivanov Andrej;sporák

Nič sa nezmenilo.

Skúsime prekódovať súbory do jednoubytového kódovania:

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

Opäť sa nič nezmenilo.

Nič sa nedá robiť, budeme musieť nájsť riešenie na internete. Priame informácie o ruských priezviskách nie sú, ale existujú otázky o iných zvláštnostiach triedenia. Napríklad takýto problém: unix sort považuje znaky „-“ (pomlčka) za neviditeľné. Stručne povedané, reťazce "a-b", "aa", "ac" sa triedia ako "aa", "a-b", "ac".

Odpoveď je všade štandardná: použite programátorskú lokalitu "C" a budete šťastní. Skúšame:

$> LANG=C sort buhg.txt
Jelkina Ella;žeriavnik
Abakanov Michal;malár
Ivanov Andrej;sporák
Ivanová Alla;advokát

Niečo sa zmenilo. Ivanovci sa zoradili do správneho poradia, pravda Jelkina niekam ušla. Vraciame sa k pôvodnej úlohe:

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

Fungoval bez chýb, ako sľúbil internet. A to aj napriek Jolkina v prvej rade.

Problém sa zdá byť vyriešený, ale pre každú náhodu vyskúšame ešte jedno ruské kódovanie — windowsové. CP1251:

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

Výsledok triedenia, ako je divné, bude zhodný s lokalitou. "C", a celý príklad preto prechádza bez chýb. Nejaká mystika.

Nemám rád mystiku v programovaní, pretože obvykle zakrýva chyby. Budem musieť vážne sa zaoberať otázkou, ako to funguje. sort a na čo to vplýva. LC_COLLATE .

Na konci sa pokúsim odpovedať na otázky:

prečo sa nesprávne triedili ženské priezviská.
prečo LANG=ru_RU.CP1251 sa ukázal ako ekvivalent. LANG=C
prečo majú sort a join rôzne predstavy o poradí triedených riadkov.
prečo vo všetkých mojich príkladoch sú chyby.
a nakoniec, ako triediť riadky podľa vlastného vkusu.

Triedenie v Unicode.

Prvou zastávkou bude technická správa č. 10 s názvom. Unicode collation algorithm. na stránke unicode.org.. Správa obsahuje množstvo technických podrobností, takže si dovoľujem uviesť stručný prehľad hlavných myšlienok.

Triedenie — "porovnávanie" riadkov — základ každého algoritmu triedenia. Samotné algoritmy sa môžu líšiť ("bubline", "zlučovanie", "rýchle"), ale všetky budú používať porovnávanie dvojíc riadkov na určenie poradia ich nasledujúceho poradia.

Triedenie riadkov v prirodzenom jazyku je dosť zložitý problém. Aj v najjednoduchších jednobytných kódovaniach poradie písmen v abecede, aspoň v niečom odlišnom od anglickej latinky, už nebude zodpovedať poradiu číselných hodnôt, ktorými sú tieto písmená kódované. Tak v nemeckej abecede písmeno. Ö stojí medzi O a P, a v kódovaní. CP850 sa dostáva medzi ÿ a Ü..

Môžete sa pokúsiť abstrahovať od konkrétneho kódovania a považovať "ideálne" písmená, ktoré sú usporiadané v určitom poradí, ako je to v Unicode. Kódovania. UTF8, UTF16 alebo jednobyte. KOI8-R (ak potrebujete obmedzené podmnožstvo Unicode) budú poskytovať rôzne číselné reprezentácie písmen, ale odkazujú zároveň na tie isté prvky základnej tabuľky.

Zjavuje sa, že aj keď si vytvoríme tabuľku znakov odznova, nebudeme schopní určiť univerzálny poriadok znakov. V rôznych národných abecedách, ktoré používajú rovnaké písmená, sa poradie týchto písmen môže líšiť. Napríklad vo francúzskom jazyku Æ bude považované za ligatúru a triedené ako reťazec AE. V nórskom jazyku Æ bude samostatným písmenom, ktoré sa nachádza po Z. Mimochodom, okrem ligatúr ako Æ existujú písmená, ktoré sú zapisované niekoľkými znakmi. Tak v českej abecede existuje písmeno Ch, ktoré sa nachádza medzi H a I.

. Okrem rozdielov v abecedách existujú aj iné národné tradície ovplyvňujúce triedenie. Vzniká otázka: v akom poradí by mali nasledovať v slovníku slová pozostávajúce z veľkých a malých písmen? Na triedenie môžu tiež vplývať špeciálne pravidlá používania interpunkčných znamienok. V španielskom jazyku sa na začiatku otázkového vety vkladá obrátené otáznik (¿Te gusta la música?). V tomto prípade je zrejmé, že otázkové vety by nemali byť zaradené do samostatného klastru mimo abecedy, a ako by sa mali triediť reťazce s inými interpunkčnými znakmi?

Nebudem sa zastavovať na triedení reťazcov v jazykoch, ktoré sa výrazne líšia od európskych. Upozorňujem, že v jazykoch s pravorukým alebo zvislým smerom písania sa znaky v reťazcoch pravdepodobne uchovávajú v poradí čítania, a dokonca aj v neabecedných písomnostiach existujú svoje spôsoby znakového radenia reťazcov. Napríklad, hieroglyfy môžu byť radené podľa vzhľadu (kľúče čínskych hieroglyfov) alebo podľa výslovnosti. Ako by mali byť radené emoji, úprimne povedané, si neviem predstaviť, ale aj pre ne by sa mohlo niečo vymyslieť.

Na základe uvedených zvláštností boli formulované základné požiadavky na porovnávanie reťazcov, založené na tabuľkách Unicode:

porovnanie reťazcov nezávisí od umiestnenia znakov v kó movej tabuľke;
sekvencie znakov, ktoré tvoria jeden znak, sú prevedené do kanonického tvaru (A + horný kruh to isté, čo a Å);
pri porovnávaní reťazcov sa znak posudzuje v kontexte reťazca a, ak je to potrebné, spája sa so susedmi do jednej porovnávacej jednotky (Ch v českom) alebo sa rozdelí na niekoľko (Æ vo francúzskom);
Všetky národné špecifiká (abeceda, veľké/malé písmená, interpunkcia, poradie druhov písania) musia byť nastaviteľné až na manuálne určenie poradia (emodži);
Porovnanie je dôležité nielen pre triedenie, ale aj na mnohých iných miestach, napríklad na určenie rozsahov riadkov (zástupca {A… я} v bash);
Porovnanie by sa malo vykonávať dostatočne rýchlo.

Okrem toho autori správy formulovali vlastnosti porovnania, na ktoré sa vývojári algoritmu nemajú spoliehať:

Algoritmus porovania by nemal vyžadovať samostatnú sadu znakov pre každý jazyk (ruština a ukrajinčina spoločne používajú väčšinu znakov cyriliky);
Porovnanie by nemalo byť založené na poradí znakov v tabuľkách Unicode;
Hmotnosť reťazca by nemala byť atribútom reťazca, pretože ten istý reťazec v rôznych kultúrnych kontextoch môže mať rôzne hmotnosti;
Hmotnosti reťazcov sa môžu meniť pri zlúčení alebo rozdelení (z x < y to neznamená, že xz < yz);
Rôzne reťazce, ktoré majú rovnaké hmotnosti, sú považované za rovnaké z hľadiska algoritmu triedenia. Zavedenie dodatočného usporiadania takýchto reťazcov je možné, ale môže zhoršiť výkon;
Pri opakovaných triedeniach sa reťazce s rovnakými hmotnosťami môžu meniť. Stabilita je vlastnosť konkrétneho algoritmu triedenia, nie vlastnosť algoritmu porovnávania reťazcov (pozri predchádzajúci bod);
Pravidlá triedenia sa môžu v priebehu času meniť v súlade s upresnením/změnou kultúrnych tradícií.

Tiež je uvedené, že algoritmus porovnávania nevie nič o sémantike spracovávaných reťazcov. Reťazce pozostávajúce iba z číslic by sa nemali porovnávať ako čísla a v zoznamoch anglických názvov by sa nemal odstraňovať článok (Beatles, The).

Aby bolo možné splniť všetky uvedené požiadavky, bol navrhnutý viacúrovňový (v skutočnosti štyrochúrovňový) tabuľkový algoritmus triedenia.

Predtým sa znaky v reťazci prevádzajú na kanonický tvar a skupinujú sa do jednotiek porovnávania. Každej jednotke porovnávania sú priradené niekoľko hmotností, ktoré zodpovedajú niekoľkým úrovniam porovnávania. Hmotnosti jednotiek porovnávania sú prvky usporiadaných množín (v tomto prípade celé čísla), ktoré je možné porovnávať na viac-menej. Špeciálna hodnota IGNORED (0x0) znamená, že na príslušnej úrovni porovnania sa daná jednotka na porovnaní nezúčastňuje. Porovnávanie reťazcov môže prebiehať viackrát, pričom sa používajú váhy príslušných úrovní. Na každej úrovni sa váhy porovnávacích jednotiek dvoch reťazcov postupne porovnávajú medzi sebou.

V rôznych realizáciách algoritmu pre rôzne národné tradície sa hodnoty koeficientov môžu líšiť, ale do zloženia štandardu Unicode patrí základná tabuľka váh — "Default Unicode Collation Element Table" (DUCET). Chcem poznamenať, že nastavenie premennej LC_COLLATE fakticky predstavuje určenie výberu tabuľky váh vo funkcii porovnávania reťazcov.

Váhové koeficienty DUCET sú usporiadané nasledovne:

na prvej úrovni sa všetky písmená uvádzajú do jedného písmena, diakritické znamienka sa ignorujú, interpunkcia (nie všetka) sa ignoruje;
na druhej úrovni sa zohľadňujú iba diakritické znamienka;
na tretej úrovni sa zohľadňuje iba písmeno;
na štvrtej úrovni sa zohľadňujú iba interpunkčné znamienka.

Porovnávanie prebieha v niekoľkých prechodoch: najprv sa porovnávajú koeficienty prvej úrovne; ak sa váhy zhodujú, prebieha opätovné porovnanie s váhami druhej úrovne; potom možno aj tretej a štvrtej.

Porovnávanie sa končí, keď sa v reťazcoch nachádzajú zodpovedajúce si jednotky porovnania s rôznymi váhami. Reťazce, ktoré majú rovnaké váhy na všetkých štyroch úrovniach, sa považujú za rovnaké.

Tento algoritmus (s množstvom dodatočných technických podrobností) dal názov správe č. 10 — "Unicode Collation Algorithm" (UCA).

V tomto mieste sa správanie triedenia z nášho príkladu stáva o niečo zrozumiteľnejším. Bolo by dobré porovnať ho so štandardom Unicode.

Na testovanie realizácií UCA existuje špeciálny test, ktorý používa súbor váh, implementujúci DUCET. V súbore váh môžete nájsť rôzne zaujímavosti. Napríklad tam je poradie domina a európskeho domína, ako aj poradie farieb v balíčku kariet (symbol 1F000 a ďalej). Kartové farby sú usporiadané podľa pravidiel bridžu — PČBT, a karty v farbe — v poradí T,2,3… K.

Ručná kontrola správnosti triedenia reťazcov v súlade s DUCET by bola dosť únavná, ale našťastie pre nás existuje ukážková implementácia knižnice na prácu s Unicode - "International Components for Unicode" (ICU).

Na stránke tejto knižnice, vyvinutej v IBM, sú demonštračné stránky, vrátane stránky algoritmu porovnávania reťazcov. Zadáme naše testovacie reťazce s predvolenými nastaveniami a, ó zázrak, dostaneme dokonalú slovenskú triedu.

Abakanov Michal;malíř
Jolkina Ella;kranovnica
Ivanov Andrej;zvárač
Ivanova Alla;advokát

Mimochodom, na stránke ICU môžete nájsť objasnenie fungovania algoritmu porovnávania pri spracovaní interpunkčných znamienok. V príkladoch Collation FAQ sa ignorujú apostrof a pomlčka.

Unicode nám pomohol, ale hľadať príčiny zvláštneho správania sort v Linux budeme musieť niekde inde.

Triedenie v glibc

Rýchly prehľad zdrojových kódov nástroja sort z GNU Core Utils ukázal, že v samotnom nástroji sa lokalizácia zjednodušuje na tlač aktuálnej hodnoty premennej LC_COLLATE pri spustení v ladicoms režime:

$ sort --debug buhg.txt > buhg.srt
sort: using 'sk_SK.UTF8' sorting rules

Porovnávanie reťazcov sa vykonáva štandardnou funkciou strcoll, takže všetko zaujímavé sa nachádza v knižnici glibc.

Na wiki projektu glibc porovnávaniu reťazcov je zasvätený jeden odsek. Z tohto odseku sa dá pochopiť, že v glibc triedenie je založené na už známom algoritme UCA (The Unicode collation algorithm) a/alebo na blízkom štandarde ISO 14651 (Medzinárodné usporiadanie a porovnávanie reťazcov). O poslednom štandarde treba poznamenať, že na stránke standards.iso.org ISO 14651 je oficiálne vyhlásený za verejný, ale príslušný odkaz vedie na neexistujúcu stránku. Google vracia niekoľko stránok s odkazmi na oficiálne stránky, ktoré ponúkajú zakúpiť elektronickú kópiu štandardu za sto eur, ale na tretej-štvrtej stránke výsledkov vyhľadávania nájdete aj priame odkazy na PDF. Celkovo sa štandard prakticky nelíši od UCA, ale číta sa nudnejšie, pretože neobsahuje živé príklady národných zvláštností triedenia reťazcov.

Najzaujímavejšou informáciou na wiki bola linka na bugtracker s diskusiou o implementácii porovnávania reťazcov v glibc. Z diskusie sa dozvieme, že v glibc na porovnávanie reťazcov sa používa ISOspoločná tabuľka The Common Template Table (CTT), ktorej adresu nájdete v prílohe A štandardu ISO 14651. Medzi rokmi 2000 a 2015 sa táto tabuľka v glibc nemala údržbára a dosť sa líšila (aspoň na pohľad) od súčasnej verzie štandardu. Od roku 2015 do 2018 prebiehala adaptácia na novú verziu tabuľky a v súčasnosti máte šancu stretnúť v reálnom živote ako nový variant tabuľky (CentOS 8), tak aj starý (CentOS 7).

Teraz, keď máme všetky informácie o algoritme a pomocných tabuľkách, môžeme sa vrátiť k pôvodnému problému a pochopiť, ako správne triediť riadky v ruskej lokalite.

ISO 14651/14652

Zdrojový kód zaujímavej tabuľky CTT vo väčšine distribúcií Linux sa nachádza v adresári /usr/share/i18n/locales/. Samotná tabuľka sa nachádza v súbore iso14651_t1_common. Potom sa tento súbor pomocou príkazu copy iso14651_t1_common zahrnie do súboru iso14651_t1, ktorý sa zase zahrnie do národných súborov, vrátane en_US a ru_RU. Vo väčšine distribúcií Linux sú všetky zdrojové súbory zahrnuté v základnej inštalácii, ale ak tam nie sú, budete musieť nainštalovať dodatočný balík z distribúcie.

Štruktúra súboru iso14651_t1 sa môže zdať hrozne zložitá, s nejasnými pravidlami pre vytváranie názvov, ale ak sa do toho pohrabete, všetko je dosť jednoduché. Štruktúra je opísaná v štandarde ISO 14652, kópiu ktorého si môžete stiahnuť z webu open-std.org. Ďalší opis formátu súboru si môžete prečítať v špecifikáciách POSIX od OpenGroup. Alternatívou k čítaniu štandardu je preskúmanie zdrojových textov funkcie collate_read v glibc/locale/programs/ld-collate.c.

Štruktúra súboru vyzerá nasledovne:

Symbol sa predvoleně používa ako únikový symbol a koniec riadku po symbole # je komentárom. Obe symboly je možné predefinovať, čo sa aj stalo v novej verzii tabuľky:

escape_char /
comment_char %

V súbore sa vyskytujú tokeny vo formáte <Uxxxx> alebo <Uxxxxxxxx> (kde x — hexadecimálna číslica). Toto je hexadecimálne zobrazenie kódových bodov Unicode vo kódovaní UCS-4 (UTF-32). Všetky ostatné prvky v uhľových zátvorkách (vrátane <Uxxxx_xxxx>, <2> a jemu podobné), sa považujú za jednoduché reťazcové konštanty, ktoré nemajú žiadny špeciálny význam mimo kontextu.

Riadok LC_COLLATE nám hovorí, že ďalej nasledujú údaje popisujúce porovnávanie reťazcov.

Najskôr sa určujú názvy pre váhy v tabuľke porovnávania a názvy pre kombinácie symbolov. V podstate patrí dva typy názvov dvom rôznym entitám, ale v reálnom súbore sú pomiešané. Názvy váh sú určené kľúčovým slovom collating-symbol (porovnávací symbol), pretože pri porovnávaní Unicode znaky s rovnakou váhou budú považované za ekvivalentné znaky.

Celková dĺžka sekcie v aktuálnej revízii súboru je približne 900 riadkov. Vybral som príklady z viacerých miest, aby som demonštroval variabilitu názvov a niekoľko typov syntaxe.

LC_COLLATE

collating-symbol \ncollating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Zaručená najväčšia hodnota symbolu. Udržujte na konci tohto zoznamu
...
collating-element  from ""
collating-element  from ""

collating-symbol registruje reťazec OSMANYA v tabuľke mien váh
collating-symbol .. registruje sekvenciu mien pozostávajúcich z predponu S a hexadecimálneho číselného suffixu z 1D000 do 1D35F.
FFFF v collating-symbol vyzerá ako veľké nezáporné celé číslo v hexadecimálnom systéme číslovania, ale <SFFFF> to je len názov, ktorý by mohol vyzerať ako <VERYBIGVAL>
názov <U0413> znamená kódový bod v kódovaní UCS-4
collating-element from "" registruje nové meno pre pár Unicode bodov.

Keď sú váhy mien definované, sú nastavené vlastné váhy. Pretože pri porovnávaní záleží iba na vzťahoch väčšie-menej, váhy sú určené jednoduchou sekvenciou výpisu mien. Najprv sú vymenované "ľahšie" váhy a potom "ťažšie". Pripomínam, že každému Unicode symbolu je priradených štyri rôzne váhy. Tu sú zjednotené do jedinej usporiadanej sekvencie. Teoreticky môže byť akékoľvek symbolické meno použité na akomkoľvek z troch úrovní, ale komentáre naznačujú, že vývojári psychicky rozdeľujú mená podľa úrovní.

% Symbolické priradenia váh

% Priradenia váh tretej úrovne




...
% Priradenia váh druhej úrovne

 % KOMBINAČNÁ NÍZKA ČIARA
 % KOMBINAČNÝ ČÍR NAD
 % KOMBINAČNÝ OPAČNÝ ČÍR NAD
...
% Priradenia váh prvej úrovne
 % HORIZONTÁLNE TABULOVANIE 
 % RIADKOVÝ PRENOS
 % VERTIKÁLNE TABULOVANIE
...
 % CYRILICKE MALÉ PÍSMENKO DE
 % CYRILICKE MALÉ PÍSMENKO KOMI DE
 % CYRILICKE MALÉ PÍSMENKO DJE
 % CYRILICKE MALÉ PÍSMENKO KOMI DJE
 % CYRILICKE MALÉ PÍSMENKO GJE
 % CYRILICKE MALÉ PÍSMENKO ZE S DESCENDEROM
 % CYRILICKE MALÉ PÍSMENKO IE
 % CYRILICKE MALÉ PÍSMENKO IE S BREVIEROM
 % CYRILICKE MALÉ PÍSMENKO UKRAJINSKEJ IE
 % CYRILICKE MALÉ PÍSMENKO ZHE

Nakoniec, samotná tabuľka váh.

Sekcia váh je uzavretá v radoch s kľúčovými slovami order_start a order_end. Doplnkové parametre order_start určujú, v akom smere sa porovnávajú riadky na každej úrovni porovnávania. Predvolene sa používa parameter forward. Telo sekcie pozostáva z riadkov, ktoré obsahujú kód znaku a štyri jeho váhy. Kód znaku môže byť predstavený samotným znakom, kódovou bodkou alebo symbolickým menom definovaným skôr. Váhy môžu byť tiež definované symbolickými menami, kódovými bodkami alebo samotnými znakmi. Ak sa používajú kódové bodky alebo znaky, ich váha sa zhoduje s číselnou hodnotou kódovej bodky (pozíciou v tabuľke Unicode). Znakmi, ktoré nie sú explicitne uvedené (ako rozumiem), sa považujú za pridané do tabuľky s primárnou váhou, ktorá sa zhoduje s pozíciou v tabuľke Unicode. Špeciálna hodnota váhy IGNORE znamená, že na zodpovedajúcej úrovni porovnávania sa tento znak ignoruje.

Na demonštrovanie štruktúry váh som vybral tri pomerne zrejmé fragmenty:

znaky, ktoré sú úplne ignorované
znaky ekvivalentné číslu tri na prvých dvoch úrovniach
začiatok cyrilského abecedy, ktorá neobsahuje diakritické znaky, a preto sa usporadúva predovšetkým podľa prvej a tretej úrovne.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (v 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (v 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (v 6429)
...
 ;;; % DIGIT THREE
 ;;; % FULLWIDTH DIGIT THREE
 ;;; % PARENTHESIZED DIGIT THREE
 ;;; % DIGIT THREE FULL STOP
 ;;; % MATHEMATICAL BOLD DIGIT THREE
...
 ;;; % CYRILLIC SMALL LETTER A
 ;;; % CYRILLIC CAPITAL LETTER A
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
...
 ;;; % CYRILLIC SMALL LETTER BE
 ;;; % CYRILLIC CAPITAL LETTER BE
 ;;; % CYRILLIC SMALL LETTER VE
 ;;; % CYRILLIC CAPITAL LETTER VE
...
order_end

Teraz sa môžeme znova vrátiť k triedeniu príkladov z začiatku článku. Zrada spočíva v tejto časti tabuľky váh:

IGNORE;IGNORE;IGNORE; % SPACE
 IGNORE;IGNORE;IGNORE; % EXCLAMATION MARK
 IGNORE;IGNORE;IGNORE; % QUOTATION MARK
...

Je vidno, že v tejto tabuľke sú interpunkčné znaky z tabuľky ASCII (vrátane medzery) pri porovnávaní riadkov sa takmer vždy ignoruje. Výnimku tvoria len riadky, ktoré sa zhodujú vo všetkom, okrem interpunkčných znakov, ktoré sa nachádzajú na zhodných pozíciách. Riadky z môjho príkladu (po triedení) pre algoritmus porovnávania vyzerajú takto:

AbakanovMichalmalír
JolkinováElakranovčička
IvanováAllamalír
IvanovAndrejlesár

Vzhľadom na to, že v tabuľke váh sa veľké písmená v ruštine nachádzajú po malých (na tretej úrovni <CAP> ťažšie ako <MIN>), triedenie vyzerá absolútne správne.

Pri nastavovaní premennej LC_COLLATE=C sa načíta špeciálna tabuľka, ktorá určuje porovnanie po bajtoch

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'
};

Keďže v Unicode sa kódová bodka Ё nachádza pred A, aj riadky sú triedené zodpovedajúcim spôsobom.

Textové a binárne tabuľky

Je zrejmé, že porovnávanie riadkov je mimoriadne často vykonávaná operácia, a analýza tabuľky CTT je pomerne nákladný proces. Na optimalizáciu prístupu k tabuľke sa kompiluje do binárnej formy príkazom localedef.

Tím localedef akceptuje ako parametre súbor s tabuľkou národných špecifík (voľba -i), v ktorom sú všetky symboly uvedené ako body Unicode, a súbor zodpovednosti bodov Unicode pre konkrétnu kódovanie (voľba -f). V dôsledku práce vznikajú binárne súbory pre lokalitu, s menom uvedeným v poslednom parametri.

Glibc podporuje dva formáty binárnych súborov: "tradičný" a "moderný".

Tradičný formát predpokladá, že meno lokality je názov podpriečinka v /usr/lib/locale/. V tomto podpriečinku sú uložené binárne súbory LC_COLLATE, LC_CTYPE, LC_TIME a pod. Súbor LC_IDENTIFICATION obsahuje formálne meno lokality (ktoré sa môže líšiť od názvu priečinka) a komentáre.

Moderný formát predpokladá uloženie všetkých lokalít v jedinom archíve /usr/lib/locale/locale-archive, ktorý sa zobrazuje v virtuálnej pamäti všetkých procesov, ktoré ho používajú glibc. Meno locale v modernom formáte prechádza určitou kanonizáciou – v názvoch kódovania zostávajú iba číslice a písmená uvedené malými písmenami. Tak ru_RU.KOI8-R, bude uložené ako ru_RU.koi8r.

Vstupné súbory sa hľadajú v aktuálnom adresári, ako aj v adresároch /usr/share/i18n/locales/ a /usr/share/i18n/charmaps/ pre súbory CTT a súbory kódovania zodpovedajúco.

Napríklad príkaz

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

skompiluje súbor /usr/share/i18n/locales/ru_RU s použitím súboru kódovania /usr/share/i18n/charmaps/MAC-CYRILLIC.gz a uloží výsledok do /usr/lib/locale/locale-archive pod názvom ru_RU.maccyrillic

Ak nastavíte premennú LANG=en_US.UTF-8 , glibc bude hľadať binárne súbory locale v nasledujúcej sekvencii súborov a adresárov:

/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/

Ak sa locale vyskytuje v tradičnom aj v modernom formáte, má prioritu moderný.

Zoznam skompilovaných lokalít si môžete pozrieť príkazom locale -a.

Príprava vlastnej tabuľky porovnávania

Teraz, s vybavením znalosťami, môžete vytvoriť svoju vlastnú ideálnu tabuľku porovnávania reťazcov. Táto tabuľka by mala správne porovnávať ruské písmená, vrátane písmena Ё, pričom zohľadňuje interpunkčné znamienka v súlade s tabuľkou ASCII.

Proces prípravy vlastnej triediacej tabuľky sa skladá z dvoch fáz: úpravy tabuľky váh a kompilácie do binárnej formy príkazom localedef.

Aby sa tabuľka porovnávania dala prispôsobiť s minimálnymi nákladmi na úpravu, formát ISO 14652 predpokladá sekcie úpravy váh už existujúcej tabuľky. Sekcia začína kľúčovým slovom reorder-after a určením pozície, po ktorej sa vykonáva zmena. Sekcia končí riadkom reorder-end. Ak je potrebné opraviť niekoľko častí tabuľky, vytvorí sa sekcia pre každú z týchto častí.

Nahradil som nové verzie súborov iso14651_t1_common a ru_RU z repozitára glibc do svojho domáceho adresára ~/.local/share/i18n/locales/ a mierne som upravil sekciu LC_COLLATE v ru_RU. Nové verzie súborov sú úplne kompatibilné s mojou verziou glibc. Ak chcete použiť staré verzie súborov, budete musieť zmeniť symbolické mená a miesto, odkiaľ začína zmena v tabuľke.

LC_COLLATE
% Skopírujte šablónu z ISO/IEC 14651
skopírujte "iso14651_t1"
preusporiadajte-po <U000D>
<U0020> <S0020>;<ZÁKLAD>;<MIN>;<U0020> % PRIESTOR
<U0021> <S0021>;<ZÁKLAD>;<MIN>;<U0021> % VÝKRIČNÍK
<U0022> <S0022>;<ZÁKLAD>;<MIN>;<U0022> % ÚLOHA
...
<U007D> <S007D>;<ZÁKLAD>;<MIN>;<U007D> % PRAVÝ ZÁVORKA
<U007E> <S007E>;<ZÁKLAD>;<MIN>;<U007E> % TILDA
preusporiadajte-koniec
KONIEC LC_COLLATE

V skutočnosti by bolo potrebné zmeniť polia v LC_IDENTIFICATION tak, aby odkazovali na lokalitu sk_MY, ale v mojom príklade to nebolo potrebné, pretože som vylúčil z vyhľadávania lokality archív locale-archive.

Aby localedef pracoval so súbormi vo mojej zložke cez premennú I18NPATH môžete pridať dodatočný adresár na vyhľadávanie vstupných súborov, a adresár na uloženie binárnych súborov môžete určiť ako cestu so slashmi:

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

POSIX predpokladá, že v LANG je možné písať absolútne cesty k adresárom so súbormi lokalít, ktoré začínajú priamym slashom, ale glibc v Linux všetky cesty sa považujú od základného adresára, ktorý je možné prepísať pomocou premennej LOCPATH. Po nastavení LOCPATH=~/.local/lib/locale/ budú všetky súbory súvisiace s lokalizáciou hľadané iba v mojej zložke. Archiv lokalít pri nastavenej premennej LOCPATH sa ignoruje.

Tu je rozhodujúci test:

$> LANG=sk_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Michal;malíř
Jelkinová Ella;kranovnica
Ivanov Andrej;tesár
Ivanová Alla;advokát

Hurá! Podarilo sa nám to!

Práca na chybách

Na otázky o triedení reťazcov, ktoré boli položené na začiatku, som už odpovedal, ale zostáva ešte niekoľko otázok o chybách — viditeľných a neviditeľných.

Vráťme sa k pôvodnej úlohe.

A program sort a program join používajú rovnaké funkcie porovnávania reťazcov z glibc. Ako sa teda stalo, že join vykazoval chybu triedenia na reťazcoch, ktoré boli triedené príkazom sort v lokalite en_US.UTF-8? Ответ прост: sort porovnáva celý reťazec, zatiaľ čo join porovnáva iba kľúč, ktorým je predvolene začiatok reťazca pred prvým medzerným symbolom. V mojom príklade to viedlo k hláseniu o chybe, pretože triedenie prvých slov v reťazcoch sa neshodovalo s triedením plných reťazcov.

Lokalita "C" zaručuje, že v zoradených riadkoch budú aj počiatočné podreťazce až po prvý medzery tiež usporiadané, ale to len maskuje chybu. Môžete vybrať také dáta (ľudia s rovnakými priezviskami, ale rôznymi menami), ktoré by bez hlásenia o chybe poskytli nesprávny výsledok pri zlúčení súborov. Ak chceme, aby join zhromaždil riadky súborov podľa Meno a priezvisko, správny spôsob bude jasne uviesť oddeľovač polí a zoradiť podľa kľúčového poľa, a nie podľa celej strany. V tomto prípade bude zlúčenie prebiehať správne a v žiadnej lokalite nebudú chyby:

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

Úspešne vykonaný príklad v kódovaní CP1251 obsahuje ešte jednu chybu. Problém je v tom, že vo všetkých známych distribúciách Linux v balíčkoch chýba skompilovaná lokalita sk_SK.CP1251. Ak skompilovaná lokalita nie je nájdená, sort potichu používa porovnávanie byte po byte, čo sme aj pozorovali.

Navyše, existuje ešte jedna malá chyba týkajúca sa neavailability skompilovaných lokalít. Príkaz LOCPATH=/tmp locale -a vydá zoznam všetkých lokalít v locale-archive, ale pri nastavenej premennej LOCPATH pre všetky programy (vrátane samotnej locale) budú tieto lokality nedostupné.

$> 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

Záver

Ak ste programátor, ktorý je zvyknutý považovať reťazce za množinu bytov, vaša voľba LC_COLLATE=C.

Ak ste lingvista alebo zostavovateľ slovníka, bolo by lepšie skompilovať vašu lokalitu.

Ak ste bežný používateľ, stačí si zvyknúť na to, že príkaz ls -a vydáva súbory, začínajúce bodkou, v zmiešanom režime so súbormi, ktoré začínajú písmenom, a Midnight Commander, ktorý používa svoje interné funkcie na triedenie mien, vynechá súbory, ktoré začínajú bodkou, na začiatku zoznamu.