Úvod

Všetko to začalo krátkym skriptom, ktorý mal kombinovať informácie o adrese e-mail zamestnancov získaných zo zoznamu užívateľov mailing listu, pričom pozície zamestnancov boli získané z databázy HR oddelenia. Oba zoznamy boli exportované do textových súborov Unicode UTF-8 a uložené s koncovkami riadkov Unix.

obsah mail.txt

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

obsah buhg.txt

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

Na zlúčenie boli súbory zoradené podľa príkazu Unix druh a odoslaný na vstup unixového programu spojiť, ktorý neočakávane zlyhal s chybou:

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

Pohľad na výsledok triedenia očami ukázal, že vo všeobecnosti je triedenie správne, ale v prípade zhody mužských a ženských priezvisk sú ženské pred mužskými:

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

Vyzerá to ako chyba triedenia v Unicode alebo ako prejav feminizmu v triediacom algoritme. Prvá je, samozrejme, vierohodnejšia.

Nateraz to odložme spojiť a sústrediť sa na druh. Pokúsme sa problém vyriešiť pomocou vedeckého popichovania. Najprv zmeňme miestne nastavenie sk na ru_RU. Na triedenie by stačilo nastaviť premennú prostredia LC_COLLATE, ale nebudeme strácať čas maličkosťami:

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

Nič sa nezmenilo.

Skúsme prekódovať súbory do jednobajtové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.

Nedá sa nič robiť, riešenie budete musieť hľadať na internete. Priamo o ruských priezviskách nie je nič, ale sú tu otázky o iných triediacich zvláštnostiach. Napríklad tu je problém: Unix sort považuje znaky „-“ (pomlčka) za neviditeľné. Stručne povedané, reťazce "a-b", "aa", "ac" sú zoradené ako "aa", "a-b", "ac".

Ответ везде стандартный: используйте программистскую локаль "C" a budeš šťastný. Vyskúšajme:

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

Niečo sa zmenilo. Ivanovci sa zoradili v správnom poradí, hoci Yolkina sa niekde pošmykla. Vráťme sa k pôvodnému problému:

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

Fungovalo to bez chýb, ako internet sľuboval. A to aj napriek Yolkine v prvej línii.

Zdá sa, že problém je vyriešený, ale pre každý prípad skúsme iné ruské kódovanie - Windows CP1251:

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

Výsledok triedenia sa napodiv bude zhodovať s miestnym nastavením "C"a celý príklad podľa toho beží bez chýb. Nejaký druh mystiky.

Nemám rád mystiku v programovaní, pretože väčšinou maskuje chyby. Budeme musieť vážne preskúmať, ako to funguje. druh a čo to ovplyvňuje? LC_COLLATE .

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

почему неправильно сортировались женские фамилии
prečo LANG=ru_RU.CP1251 sa ukázalo ako rovnocenné JAZYK=C
почему у druh и spojiť rôzne predstavy o poradí triedených reťazcov
prečo sú vo všetkých mojich príkladoch chyby?
konečne ako si zoradiť reťazce podľa svojich predstáv

Triedenie v Unicode

Prvou zastávkou bude technická správa č.10 s názvom Unicode porovnávací algoritmus on-line unicode.org. Správa obsahuje veľa technických podrobností, dovoľte mi preto uviesť krátke zhrnutie hlavných myšlienok.

Porovnanie — „porovnávanie“ reťazcov je základom každého triediaceho algoritmu. Samotné algoritmy sa môžu líšiť ("bublina", "zlúčiť", "rýchle"), ale všetky použijú porovnanie dvojice reťazcov na určenie poradia, v ktorom sa objavia.

Сортировка строк на естественном языке — это довольно сложная проблема. Даже в простейших однобайтовых кодировках порядок букв в алфавите, хоть в чём-то отличающемся от английской латиницы, уже не будет совпадать с порядком числовых значений, которыми эти буквы кодируются. Так в немецком алфавите буква Ö стоит между О и Pa v kódovaní CP850 dostane sa medzi ÿ и Ü.

Môžete sa pokúsiť abstrahovať od konkrétneho kódovania a zvážiť „ideálne“ písmená, ktoré sú usporiadané v určitom poradí, ako sa to robí v Unicode. Kódovania UTF8, UTF16 alebo jednobajtový KOI8-R (ak je potrebná obmedzená podmnožina Unicode) poskytne rôzne číselné reprezentácie písmen, ale odkazuje na rovnaké prvky základnej tabuľky.

Ukazuje sa, že aj keď zostavíme tabuľku symbolov od začiatku, nebudeme jej môcť priradiť univerzálne poradie symbolov. V rôznych národných abecedách, ktoré používajú rovnaké písmená, sa môže poradie týchto písmen líšiť. Napríklad vo francúzštine Æ bude považovaný za ligatúru a zoradený ako reťazec AE. v nórčine Æ bude samostatný list, ktorý sa nachádza za Z. Mimochodom, okrem ligatúr ako Æ Existujú písmená napísané niekoľkými symbolmi. Takže v českej abecede je písmeno Ch, ktorý stojí medzi H и I.

Okrem rozdielov v abecedách existujú aj iné národné tradície, ktoré ovplyvňujú triedenie. Predovšetkým vyvstáva otázka: v akom poradí by sa v slovníku mali objaviť slová pozostávajúce z veľkých a malých písmen? Triedenie môže byť ovplyvnené aj použitím interpunkčných znamienok. V španielčine sa na začiatku opytovacej vety používa obrátený otáznik (Máš rád hudbu?). V tomto prípade je zrejmé, že opytovacie vety by sa nemali zoskupovať do samostatného zhluku mimo abecedy, ale ako triediť riadky s inými interpunkčnými znamienkami?

Nebudem sa zaoberať triedením reťazcov v jazykoch veľmi odlišných od európskych. Všimnite si, že v jazykoch so smerom písania sprava doľava alebo zhora nadol sú znaky v riadkoch s najväčšou pravdepodobnosťou uložené v poradí čítania a dokonca aj neabecedné systémy písania majú svoje vlastné spôsoby usporiadania riadkov znak po znaku. . Napríklad hieroglyfy môžu byť usporiadané podľa štýlu (Klávesy čínskych znakov) alebo podľa výslovnosti. Úprimne povedané, netuším, ako by mali byť emotikony usporiadané, ale aj pre nich môžete niečo vymyslieť.

Na základe vyššie uvedených funkcií boli formulované základné požiadavky na porovnávanie reťazcov na základe tabuliek Unicode:

porovnávanie reťazcov nezávisí od pozície znakov v kódovej tabuľke;
sekvencie znakov tvoriace jeden znak sú redukované na kanonickú formu (A + horný kruh je rovnaký ako Å);
Pri porovnávaní reťazcov sa znak berie do úvahy v kontexte reťazca a ak je to potrebné, kombinuje sa so svojimi susedmi do jednej porovnávacej jednotky (Ch v češtine) alebo sa delí na niekoľko (Æ francuzsky);
všetky národné znaky (abeceda, veľké/malé písmená, interpunkcia, poradie typov písania) musia byť nakonfigurované až po manuálne priradenie poradia (emoji);
porovnanie je dôležité nielen pri triedení, ale aj na mnohých iných miestach, napríklad pri špecifikovaní rozsahov riadkov (nahradením {A... z} v tresnúť);
porovnanie by malo byť vykonané pomerne rýchlo.

Okrem toho autori správy sformulovali porovnávacie vlastnosti, na ktoré by sa vývojári algoritmov nemali spoliehať:

porovnávací algoritmus by nemal vyžadovať samostatnú sadu znakov pre každý jazyk (ruské a ukrajinské jazyky zdieľajú väčšinu znakov cyriliky);
porovnanie by sa nemalo spoliehať na poradie znakov v tabuľkách Unicode;
váha 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ôznu váhu;
hmotnosti riadkov sa môžu zmeniť pri zlúčení alebo rozdelení (od x < y z toho nevyplýva xz < yz);
rôzne reťazce s rovnakými váhami sa považujú za rovnaké z hľadiska triediaceho algoritmu. Zavedenie dodatočného objednávania takýchto reťazcov je možné, ale môže to znížiť výkon;
Pri opakovanom triedení môžu byť riadky s rovnakou hmotnosťou zamenené. Robustnosť je vlastnosťou konkrétneho triediaceho algoritmu a nie vlastnosťou algoritmu porovnávania reťazcov (pozri predchádzajúci odsek);
Pravidlá triedenia sa môžu časom meniť tak, ako sa zdokonaľujú/menia kultúrne tradície.

Je tiež stanovené, že porovnávací algoritmus nevie nič o sémantike spracovávaných reťazcov. Reťazce pozostávajúce iba z číslic by sa teda nemali porovnávať ako čísla a v zoznamoch anglických názvov by článok (Beatles, The).

Na splnenie všetkých špecifikovaných požiadaviek je navrhnutý viacúrovňový (vlastne štvorúrovňový) algoritmus triedenia tabuliek.

Predtým boli znaky v reťazci zredukované na kanonickú formu a zoskupené do porovnávacích jednotiek. Každá jednotka porovnávania má priradených niekoľko váh zodpovedajúcich niekoľkým úrovniam porovnávania. Váhy porovnávacích jednotiek sú prvky usporiadaných množín (v tomto prípade celé čísla), ktoré možno porovnávať za viac alebo menej. Zvláštny význam IGNOROVANÝ (0x0) znamená, že na zodpovedajúcej úrovni porovnávania táto jednotka nie je zapojená do porovnávania. Porovnanie reťazcov je možné niekoľkokrát opakovať s použitím váh zodpovedajúcich úrovní. Na každej úrovni sa váhy porovnávacích jednotiek dvoch riadkov postupne navzájom porovnávajú.

V rôznych implementáciách algoritmu pre rôzne národné tradície sa hodnoty koeficientov môžu líšiť, ale štandard Unicode obsahuje základnú tabuľku váh - "Predvolená tabuľka prvkov zoradenia Unicode" (DUCET). Chcel by som poznamenať, že nastavenie premennej LC_COLLATE je vlastne indikáciou výberu váhovej tabuľky vo funkcii porovnávania reťazcov.

Váhové koeficienty DUCET usporiadané takto:

na prvej úrovni sú všetky písmená zmenšené na rovnaké veľké a malé písmená, diakritika sa vynecháva, interpunkčné znamienka (nie všetky) sa ignorujú;
na druhej úrovni sa berie do úvahy iba diakritika;
na tretej úrovni sa berie do úvahy iba prípad;
na štvrtej úrovni sa berú do úvahy iba interpunkčné znamienka.

Porovnanie prebieha v niekoľkých prechodoch: najprv sa porovnajú koeficienty prvej úrovne; ak sa váhy zhodujú, potom sa vykoná opakované porovnanie s váhami druhej úrovne; potom možno tretí a štvrtý.

Porovnanie sa skončí, keď riadky obsahujú zhodné jednotky porovnania s rôznymi váhami. Riadky, ktoré majú rovnakú váhu na všetkých štyroch úrovniach, sa považujú za rovnaké.

Tento algoritmus (s množstvom ďalších technických detailov) dal názov správe č. 10 - "Unicode Collation Algorithm" (ACU).

Tu je správanie triedenia z nášho príkladu trochu jasnejšie. Bolo by pekné porovnať to so štandardom Unicode.

Na testovanie implementácií ACU existuje špeciálna test, použitím súbor váh, implementácia DUCET. V súbore váhy nájdete najrôznejšie vtipné veci. Napríklad existuje poradie mahjongu a európskych domino, ako aj poradie farieb v balíčku kariet (symbol 1F000 a ďalej). Obleky kariet sú umiestnené podľa pravidiel bridžu - PCBT a karty vo farbe sú v poradí T, 2,3, XNUMX... K.

Manuálna kontrola, či sú riadky správne zoradené podľa DUCET by to bolo dosť únavné, ale našťastie pre nás existuje príkladná implementácia knižnice pre prácu s Unicode - "Medzinárodné komponenty pre Unicode"(ICU).

Na webovej stránke tejto knižnice, vyvinutej v r IBM, tam sú ukážkové stránky, vrátane stránka s porovnávacím algoritmom reťazcov. Vstúpime do našich testovacích liniek s predvolenými nastaveniami a hľa, dostaneme dokonalé ruské triedenie.

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

Mimochodom, webová stránka ICU Objasnenie porovnávacieho algoritmu nájdete pri spracovaní interpunkčných znamienok. V príkladoch Časté otázky o zoraďovaní apostrof a spojovník sa ignorujú.

Unicode nám pomohol, ale hľadajte dôvody pre zvláštne správanie druh в Linux bude musieť ísť niekam inam.

Triedenie v glibc

Rýchly prehľad zdrojových kódov pomôcky druh z GNU Core Utils ukázali, že v samotnom nástroji sa lokalizácia znižuje na tlač aktuálnej hodnoty premennej LC_COLLATE pri spustení v režime ladenia:

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

Porovnania reťazcov sa vykonávajú pomocou štandardnej funkcie strcoll, čo znamená, že všetko zaujímavé je v knižnici glibc.

Na wiki projekt glibc venovaný porovnávaniu reťazcov jeden odsek. Z tohto odseku možno pochopiť, že v glibc triedenie je založené na nám už známom algoritme ACU (Algoritmus porovnávania Unicode) a/alebo v norme, ktorá je jej blízka ISO 14651 (Medzinárodné usporiadanie reťazcov a porovnávanie). Čo sa týka najnovšieho štandardu, treba poznamenať, že na stránke standardy.iso.org ISO 14651 oficiálne vyhlásené za verejne dostupné, 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ú kúpu elektronickej kópie normy za sto eur, no na tretej či štvrtej stránke výsledkov vyhľadávania sú aj priame odkazy na PDF. Vo všeobecnosti sa štandard prakticky nelíši od ACU, ale je nudnejšie čítať, pretože neobsahuje jasné príklady národných znakov triedenia reťazcov.

Najzaujímavejšie informácie o wiki bol tam odkaz na sledovač chýb s diskusiou o implementácii porovnávania reťazcov v glibc. Z diskusie sa to dá dozvedieť glibc používa sa na porovnávanie reťazcov ISOosobný stôl Tabuľka spoločných šablón (CTT), ktorej adresu nájdete v prihláške A štandardná ISO 14651. V rokoch 2000 až 2015 táto tabuľka v glibc nemal správcu a bol celkom odlišný (aspoň externe) od súčasnej verzie štandardu. Od roku 2015 do roku 2018 prebiehala adaptácia na novú verziu tabuľky a teraz máte možnosť stretnúť sa v reálnom živote s novou verziou tabuľky (8 CentOS) a starý (7 CentOS).

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ť reťazce v ruskom prostredí.

ISO 14651 / 14652

Zdrojový kód tabuľky, ktorá nás zaujíma CTT na väčšine distribúcií Linux je v katalógu /usr/share/i18n/locales/. Samotná tabuľka je v súbore iso14651_t1_common. Potom je to súborová direktíva skopírujte iso14651_t1_common zahrnuté v súbore iso14651_t1, ktorý je zase zahrnutý do vnútroštátnych súborov vrátane sk и ru_RU. Vo väčšine distribúcií Linux Všetky zdrojové súbory sú zahrnuté v základnej inštalácii, ale ak nie sú prítomné, budete si musieť nainštalovať ďalší balík z distribúcie.

Štruktúra súboru iso14651_t1 может показаться ужасно многословной, с неочевидными правилами построения имён, но если разобраться, то всё достаточно просто. Структура описана в стандарте ISO 14652, ktorého kópiu si môžete stiahnuť z webovej stránky open-std.org. Môžete si prečítať ďalší popis formátu súboru technické údaje POSIX od OpenGroup. Ako alternatívu k čítaniu štandardu si môžete preštudovať zdrojový kód funkcie Collate_read в glibc/locale/programs/ld-collate.c.

Štruktúra súboru vyzerá takto:

Štandardne sa znak používa ako únikový znak a koniec riadku za znakom # je komentár. Oba symboly je možné predefinovať, čo sa robí v novej verzii tabuľky:

escape_char /
comment_char %

Súbor bude obsahovať tokeny vo formáte alebo (kde x - hexadecimálna číslica). Toto je hexadecimálna reprezentácia bodov kódu Unicode v kódovaní UCS-4 (UTF-32). Všetky ostatné prvky v uhlových zátvorkách (vrátane , <2> a podobne) sa považujú za jednoduché reťazcové konštanty, ktoré majú malý význam mimo kontextu.

Riadok LC_COLLATE nám hovorí, že ďalej začína údaj popisujúci porovnanie reťazcov.

Najprv sú špecifikované názvy pre váhy v porovnávacej tabuľke a názvy pre kombinácie symbolov. Vo všeobecnosti tieto dva typy mien patria dvom rôznym entitám, ale v skutočnom súbore sú zmiešané. Názvy váh sú špecifikované kľúčovým slovom porovnanie-symbol (porovnávací znak), pretože pri porovnávaní budú znaky Unicode, ktoré majú rovnakú váhu, považované za ekvivalentné znaky.

Celková dĺžka sekcie v aktuálnej revízii súboru je asi 900 riadkov. Vytiahol som príklady z viacerých miest, aby som ukázal svojvoľnosť mien a niekoľko typov syntaxe.

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

Collating-symbol prihlási reťazec OSMANYA v tabuľke názvov váh
porovnávací-symbol .. registruje postupnosť mien pozostávajúcu z predpony S a hexadecimálna číselná prípona od 1D000 na 1D35F.
FFFF в Collating-symbol vyzerá ako veľké celé číslo bez znamienka v šestnástkovej sústave, ale je to len meno, ktoré môže vyzerať
meno znamená kódový bod v kódovaní UCS-4
porovnávací prvok z "" zaregistruje nový názov pre dvojicu bodiek Unicode.

Po zadefinovaní názvov hmotností sa špecifikujú skutočné hmotnosti. Keďže v porovnaní záleží len na vzťahoch väčší ako menší, váhy sú určené jednoduchou sekvenciou mien v zozname. Najprv sú uvedené „ľahšie“ hmotnosti, potom „ťažšie“. Dovoľte mi pripomenúť, že každý znak Unicode má priradené štyri rôzne váhy. Tu sú spojené do jednej usporiadanej sekvencie. Teoreticky by sa na ktorejkoľvek zo štyroch úrovní dalo použiť akékoľvek symbolické meno, ale komentáre naznačujú, že vývojári mentálne rozdeľujú mená do úrovní.

% 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

Nakoniec skutočná tabuľka hmotnosti.

Sekcia váh je uzavretá v riadkoch kľúčových slov order_start и order_end. Extra možnosti order_start určiť, ktorým smerom sa na každej úrovni porovnávania skenujú riadky. Predvolené nastavenie je vpred. Telo sekcie pozostáva z riadkov, ktoré obsahujú kód symbolu a jeho štyri váhy. Kód znaku môže byť reprezentovaný znakom samotným, bodom kódu alebo symbolickým názvom definovaným predtým. Váhy možno priradiť aj symbolickým menám, kódovým bodom alebo samotným symbolom. Ak sú použité kódové body alebo znaky, ich váha je rovnaká ako číselná hodnota kódového bodu (pozícia v tabuľke Unicode). Znaky, ktoré nie sú výslovne špecifikované (ako som pochopil), sa považujú za priradené k tabuľke s primárnou váhou, ktorá zodpovedá pozícii v tabuľke Unicode. Špeciálna hodnota hmotnosti ignorovať znamená, že symbol je na príslušnej úrovni porovnania ignorovaný.

Aby som demonštroval štruktúru váh, vybral som tri celkom zrejmé fragmenty:

символы, которые игнорируются полностью
symboly ekvivalentné číslu tri v prvých dvoch úrovniach
začiatok azbuky, ktorá neobsahuje diakritiku, a preto je triedená najmä podľa prvej a tretej úrovne.

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

Teraz sa môžete vrátiť k triedeniu príkladov zo začiatku článku. Prepad leží v tejto časti tabuľky váh:

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

Je vidieť, že v tejto tabuľke sú interpunkčné znamienka z tabuľky ASCII (vrátane medzery) sa pri porovnávaní reťazcov takmer vždy ignoruje. Jedinou výnimkou sú riadky, ktoré sa zhodujú vo všetkom okrem interpunkčných znamienok nájdených na zodpovedajúcich pozíciách. Riadky z môjho príkladu (po zoradení) pre porovnávací algoritmus vyzerajú takto:

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

Vzhľadom na to, že v tabuľke mierok sú veľké písmená v ruštine za malými písmenami (na tretej úrovni ťažšie ako <MIN>), сортировка выглядит абсолютно правильной.

Pri nastavovaní premennej LC_COLLATE=C načíta sa špeciálna tabuľka, ktorá špecifikuje porovnanie bajtu po byte

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 je bod kódu Ё pred A, reťazce sú zoradené podľa toho.

Textové a binárne tabuľky

Je zrejmé, že porovnávanie reťazcov je mimoriadne bežnou operáciou a analýzou tabuľky CTT dosť nákladný postup. Pre optimalizáciu prístupu k tabuľke je skompilovaná do binárnej podoby pomocou príkazu localdef.

Tím localdef akceptuje ako parametre súbor s tabuľkou národných charakteristík (voliteľné -i), v ktorom sú všetky znaky reprezentované bodkami Unicode a súborom korešpondencie medzi bodkami Unicode a znakmi špecifického kódovania (možnosť -f). В результате работы создаются двоичные файлы для локали, с именем указанным в последнем параметре.

glibc podporuje dva binárne formáty súborov: „tradičný“ a „moderný“.

Tradičný formát znamená, že názov miestneho nastavenia je názvom podadresára v /usr/lib/locale/. V tomto podadresári sú uložené binárne súbory LC_COLLATE, LC_CTYPE, LC_TIME a tak ďalej. Súbor LC_IDENTIFICATION obsahuje formálny názov lokality (ktorý sa môže líšiť od názvu adresára) a komentáre.

Современный формат предполагает хранение всех локалей в едином архиве /usr/lib/locale/locale-archive, ktorý je namapovaný na virtuálnu pamäť všetkých procesov, ktoré používajú glibc. Názov miestneho nastavenia v modernom formáte podlieha určitej kanonizácii – v kódovacích názvoch zostávajú iba čísla a písmená zmenšené na malé písmená. Takže ru_RU.KOI8-R, bude uložený ako ru_RU.koi8r.

Vstupné súbory sa vyhľadávajú v aktuálnom adresári, ako aj v adresároch /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ pre súbory CTT a kódovanie súborov, resp.

Napríklad príkaz

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

skompiluje súbor /usr/share/i18n/locales/ru_RU pomocou kódovacieho súboru /usr/share/i18n/charmaps/MAC-CYRILLIC.gz a uložte výsledok do /usr/lib/locale/locale-archive pod menom ru_RU.maccyrillic

Ak nastavíte premennú LANG = en_US.UTF-8 potom glibc bude hľadať lokálne binárne súbory v nasledujúcom poradí 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 miestne nastavenie vyskytuje v tradičnom aj modernom formáte, prednosť má moderný.

Pomocou príkazu môžete zobraziť zoznam skompilovaných miestnych nastavení locale -a.

Príprava porovnávacej tabuľky

Teraz, vyzbrojení znalosťami, si 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 Ё a zároveň brať do úvahy interpunkčné znamienka v súlade s tabuľkou ASCII.

Процесс подготовки своей таблицы сортировки состоит из двух этапов: редактирования таблицы весов и компиляции её в двоичную форму командой localdef.

Aby sa porovnávacia tabuľka dala upraviť s minimálnymi nákladmi na úpravu, vo formáte ISO 14652 K dispozícii sú sekcie na úpravu hmotnosti existujúceho stola. Sekcia začína kľúčovým slovom doobjednať-po a označenie polohy, po ktorej sa uskutoční výmena. Úsek končí čiarou reorder-end. Ak je potrebné opraviť niekoľko častí tabuľky, potom sa pre každú takúto časť vytvorí časť.

Skopíroval som nové verzie súborov iso14651_t1_common и ru_RU z úložiska glibc do môjho domovského adresára ~/.local/share/i18n/locales/ a mierne som upravil sekciu LC_COLLATE в ru_RU. Nové verzie súborov sú plne kompatibilné s mojou verziou glibc. Ak chcete použiť staršie verzie súborov, budete musieť zmeniť symbolické názvy a miesto, kde začína nahradzovanie v tabuľke.

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

V skutočnosti by bolo potrebné zmeniť polia v LC_IDENTIFICATION tak, aby ukazovali na miestne nastavenie ru_MY, ale v mojom príklade to nebolo potrebné, pretože som vylúčil archív z vyhľadávania miestnych nastavení locale-archív.

Že localdef pracoval so súbormi v mojom priečinku prostredníctvom premennej I18NPATH Môžete pridať ďalší adresár na vyhľadávanie vstupných súborov a adresár na uloženie binárnych súborov možno zadať ako cestu s lomkami:

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

POSIX naznačuje, že v JAZYK môžete písať absolútne cesty k adresárom so súbormi miestnych nastavení, počnúc lomkou, ale glibc в Linux všetky cesty sa počítajú zo základného adresára, ktorý je možné prepísať pomocou premennej LOCPATH. Po inštalácii LOCPATH=~/.local/lib/locale/ všetky súbory súvisiace s lokalizáciou sa budú hľadať iba v mojom priečinku. Archív miestnych nastavení s nastavenou premennou LOCPATH ignoroval.

Tu je rozhodujúci test:

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

Hurá! Zvládli sme to!

Niektoré chyby

Na otázky o triedení reťazcov som už odpovedal na začiatku, ale stále existuje niekoľko otázok o chybách - viditeľných a neviditeľných.

Vráťme sa k pôvodnému problému.

A program druh a program spojiť použiť rovnaké funkcie na porovnanie reťazcov glibc. Ako sa to stalo spojiť dal chybu zoradenia v riadkoch zoradených príkazom druh v miestnych nastaveniach sk_US.UTF-8? Odpoveď je jednoduchá: druh porovnáva celý reťazec a spojiť porovnáva iba kľúč, ktorý je štandardne začiatkom reťazca až po prvý znak medzery. V mojom príklade to viedlo k chybovému hláseniu, pretože zoradenie prvých slov v riadkoch nezodpovedalo zoradeniu celých riadkov.

Miestne nastavenie "C" zaručuje, že v zoradených reťazcoch budú zoradené aj počiatočné podreťazce až po prvú medzeru, ale tým sa chyba iba maskuje. Je možné vybrať údaje (ľudí s rovnakými priezviskami, ale odlišnými krstnými menami), ktoré by bez chybového hlásenia viedli k nesprávnemu výsledku zlúčenia súborov. Ak chceme spojiť zlúčené riadky súboru podľa celého názvu, správnym spôsobom by bolo explicitne špecifikovať oddeľovač polí a triediť podľa poľa kľúča a nie podľa celého riadku. V tomto prípade bude zlúčenie pokračovať správne a v žiadnom miestnom nastavení nebudú žiadne 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 inú chybu. Faktom je, že vo všetkých mne známych distribúciách Linux v balíčkoch chýba skompilované miestne nastavenie ru_RU.CP1251. Ak sa kompilované miestne nastavenie nenájde, potom druh ticho používa porovnanie bajtu po byte, čo sme pozorovali.

Mimochodom, je tu ešte jedna malá závada súvisiaca s neprístupnosťou skompilovaných lokálov. Tím LOCPATH=/tmp locale -a zobrazí zoznam všetkých miestnych nastavení locale-archív, ale s premennou množinou LOCPATH pre všetky programy (vrátane väčšiny národné) tieto miestne nastavenia nebudú k dispozícii.

$> 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ý si zvykne myslieť, že reťazce sú množinou bajtov, potom je vaša voľba LC_COLLATE=C.

Ak ste lingvista alebo kompilátor slovníka, radšej kompilujte vo svojom lokálnom prostredí.

Ak ste jednoduchý používateľ, musíte si len zvyknúť na to, že príkaz ls -a vypíše súbory začínajúce bodkou zmiešané so súbormi začínajúcimi písmenom a Veliteľ polnoci, ktorý používa svoje interné funkcie na triedenie názvov, umiestňuje súbory začínajúce bodkou na začiatok zoznamu.