Úvod

Vše začalo krátkým skriptem, který měl sloučit informace o adresách e-mail zaměstnanců, získaných ze seznamu uživatelů e-mailového zpravodaje, s pozicemi zaměstnanců, které byly získány z databáze personálního oddělení. Obě seznamy byly exportovány do textových souborů v kódování Unicode UTF-8 a uloženy s unixovými konci řádků.

Obsah mail.txt

Ivanov Andrej;ia@example.com

Obsah buhg.txt

Ivanova Alla;malíř
Jolkina Ella;jeřábnice
Ivanov Andrej;zedník
Abakanov Michail;malíř

Pro sloučení byly soubory seřazeny unixovým příkazem sort a předány do unixového programu připojit, který 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: není seřazeno: Ivanov Andrej;zedník

Náhled výsledku třídění ukázal, že celkově je třídění správné, ale v případě shody mužských a ženských příjmení, ženská příjmení jsou před mužskými:

$>> sort buhg.txt
Abakanov Michail;malíř
Jolkina Ella;jeřábnice
Ivanova Alla;malíř
Ivanov Andrej;zedník

Vypadá to jako chyba třídění v Unicode nebo jako projev feminismu v algoritmu třídění. První možnost je samozřejmě pravděpodobnější.

Na chvíli to odložíme připojit a soustředíme se na sort. Zkusíme vyřešit problém metodou pokus-omyl. Pro začátek změníme lokalitu z en_US na ru_RU. Pro třídění by stačilo nastavit proměnnou prostředí LC_COLLATE, ale nebudeme se šetřit:

$>> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Michail;malíř
Jolkina Ella;jeřábnice
Ivanova Alla;malíř
Ivanov Andrej;zedník

Nic se nezměnilo.

Zkusíme překódovat soubory do jednovbajtového kódování:

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

Opět se nic nezměnilo.

Nezbývá než hledat řešení na internetu. O ruských příjmeních sice nic není, ale existují otázky ohledně jiných podivností v třídění. Například takový problém: unix sort považuje znaky ‚-‘ (pomlčka) za neviditelné. Zkrátka řečeno, řetězce "a-b", "aa", "ac" jsou tříděny jako "aa", "a-b", "ac".

Odpověď je všude standardní: použijte programátorskou lokalitu "C" a bude vám zle. Zkoušíme:

$>> LANG=C sort buhg.txt
Jolkina Ella;jeřábnice
Abakanov Michail;malíř
Ivanov Andrej;zedník
Ivanova Alla;advokát

Něco se změnilo. Ivanovovi se řadili ve správném pořadí, ale Jolkina někam zmizela. Vracíme se k původnímu úkolu:

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

Pracovalo to bez chyb, tak jak sliboval internet. A to i přes Jolkina v prvním řádku.

Problém se zdá být vyřešen, ale pro jistotu zkusíme ještě jedno ruské kódování — Windows. CP1251:

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

Výsledek třídění, jak se ukazuje, odpovídá lokalitě. "C", a celý příklad prochází bez chyb. Je to nějaká mystika.

Nemám rád mystiku v programování, protože obvykle maskuje chyby. Budu se muset vážně zabývat otázkou, jak to funguje sort a na co to má vliv. LC_COLLATE .

Na konci se pokusím odpovědět na otázky:

proč se nesprávně třídily ženské příjmení.
proč LANG=ru_RU.CP1251 se ukázalo jako ekvivalent. LANG=C
proč mají sort a připojit různé představy o pořadí seřazených řetězců.
proč jsou ve všech mých příkladech chyby.
nakonec, jak třídit řetězce podle svého vkusu.

Třídění v Unicode.

První zastávkou bude technická zpráva č. 10 s názvem Unicode collation algorithm. na webu unicode.org. Zpráva obsahuje mnoho technických detailů, takže si dovolím uvést shrnutí hlavních myšlenek.

Seřazení — "srovnání" řetězců — základ jakéhokoli algoritmu třídění. Samotné algoritmy se mohou lišit ("bublinkové", "slučovací", "rychlé"), ale všechny využívají srovnání dvojic řetězců pro určení pořadí jejich následování.

Třídění řetězců v přirozeném jazyce je docela složitý problém. Dokonce i v nejjednodušších jedno-bajtových kódováních se pořadí písmen v abecedě, které se alespoň trochu liší od anglického písma, už nebude shodovat s pořadím číselných hodnot, jimiž jsou tato písmena zakódována. Tak v německé abecedě písmeno Ö se nachází mezi O a redicted Frame), a v kódování CP850 se dostává mezi ÿ a Ü.

Můžeme se pokusit abstrahovat od konkrétního kódování a považovat "ideální" písmena, která jsou uspořádána v určitém pořadí, jak je to děláno v Unicode. Kódování UTF8, UTF16 nebo jedno-bajtová KOI8-R (pokud potřebujete omezené podmnožiny Unicode) budou poskytovat různá číselná zobrazení písmen, ale budou se odvolávat na stejné prvky základní tabulky.

Zdá se, že i když vytvoříme tabulku znaků od základů, nebudeme schopni přiřadit univerzální pořadí znaků. V různých národních abecedách, které používají stejné písmena, se pořadí těchto písmen může lišit. Například ve francouzštině Æ bude považováno za ligaturu a bude se řadit jako řetězec AE. V norském jazyce Æ bude samostatným písmenem, které se nachází za Z. Mimochodem, kromě ligatur typu Æ existují písmena, která jsou zapisována několika znaky. Tak v české abecedě existuje písmeno Ch, které je mezi H a I.

Kromě rozdílů v abecedách existují také jiné národní tradice, které ovlivňují řazení. Konkrétně se objevuje otázka: v jakém pořadí by měly následovat v slovníku slova skládající se z velkých a malých písmen? Na řazení mohou mít také vliv zvláštnosti používání interpunkčních znamének. Ve španělském jazyce se na začátku otázkového výroku používá obrácený otazník (¿Te gusta la música?). V tomto případě je zřejmé, že otázkové věty by neměly být seskupovány do samostatného klastru mimo abecedu, ale jak se mají řadit řetězce s jinými interpunkčními znaménky?

Nebudu se zabývat řazením řetězců v jazycích, které se výrazně liší od evropských. Upozorním, že v jazycích s písmem zprava doleva nebo shora dolů jsou znaky ve řetězcích pravděpodobně uloženy v pořadí čtení, a dokonce i v neabecedních písmech existují vlastní způsoby znakového uspořádání řetězců. Například, hieroglyfy mohou být řazeny podle tvaru (klíče čínských hieroglyfů) nebo podle výslovnosti. Jak by se měly řadit emoji, upřímně řečeno, si nedovedu představit, ale i pro ně je možné něco vymyslet.

Na základě výše uvedených zvláštností byla formulována základní kritéria pro porovnávání řetězců založených na tabulkách Unicode:

porovnání řetězců nezávisí na pozici znaků v kódové tabulce;
sekvence znaků, které tvoří jeden jediný znak, jsou převedeny na kanonickou podobu (A + horní kolečko je totéž jako Å);
při porovnávání řetězců se znak posuzuje v kontextu řetězce a v případě potřeby se spojuje s okolními do jedné jednotky porovnání (Ch v češtině) nebo se rozděluje na několik (Æ ve francouzštině);
Všechny národní specifika (abeceda, velká/malá písmena, interpunkce, pořadí druhů písma) musí být nastavena až na ruční určení pořadí (emojis);
Srovnání je důležité nejen pro třídění, ale také na mnoha jiných místech, například pro určení rozsahu řádků (zařazení {A…Я} v bash);
Srovnání by mělo být prováděno dostatečně rychle.

Kromě toho autoři zprávy formulovali vlastnosti srovnání, na které se vývojáři algoritmu nemohou spoléhat:

Algoritmus srovnání by neměl vyžadovat samostatnou sadu znaků pro každý jazyk (ruština a ukrajinština společně používají většinu znaků cyrilice);
Srovnání by nemělo záviset na pořadí znaků v tabulkách Unicode;
Váha řetězce by neměla být atributem řetězce, protože stejný řetězec v různých kulturních kontextech může mít různé váhy;
Váhy řetězců se mohou měnit při sloučení nebo rozdělení (z x < y to neznamená, že xz < yz);
Rozdílné řetězce, které mají stejné váhy, se považují za rovné z pohledu algoritmu třídění. Zavedení dodatečného uspořádání takových řetězců je možné, ale může snížit výkon;
Při opětovných tříděních se řetězce, které mají stejné váhy, mohou měnit místy. Stabilita je vlastnost konkrétního algoritmu třídění, nikoli vlastnost algoritmu srovnání řetězců (viz předchozí bod);
Pravidla třídění se mohou v průběhu času měnit, jak se upřesňují/změní kulturní tradice.

Také se uvádí, že algoritmus srovnání nic neví o sémantice zpracovávaných řetězců. Tak, řetězce složené pouze z číslic by neměly být srovnávány jako čísla, a v seznamech anglických názvů by neměl být odstraňován člen (Beatles, The).

Aby byla splněna všechna uvedená požadavky, byl navržen vícestupňový (v podstatě čtyřstupňový) tabulkový algoritmus třídění.

Nejprve jsou znaky v řetězci převedeny do kanonického tvaru a seskupeny do jednotek srovnání. Každé jednotce srovnání jsou přiřazeny různé váhy, které odpovídají několika úrovním srovnání. Váhy jednotek srovnání jsou prvky uspořádaných množin (v tomto případě celá čísla), která lze vzájemně porovnávat. Speciální hodnota IGNORED (0x0) znamená, že na odpovídající úrovni porovnání se tato jednotka v porovnání neúčastní. Porovnání řetězců se může opakovat několikrát, s použitím vah odpovídajících úrovní. Na každé z úrovní se váhy jednotek porovnání dvou řetězců postupně porovnávají mezi sebou.

V různých implementacích algoritmu pro různé národní tradice se velikosti koeficientů mohou lišit, ale součástí standardu Unicode je základní tabulka vah — "Default Unicode Collation Element Table" (DUCET). Rád bych podotkl, že nastavení proměnné LC_COLLATE fakticky představuje pokyn k výběru tabulky vah ve funkci porovnání řetězců.

Váhové koeficienty DUCET jsou uspořádány takto:

na první úrovni se všechny písmena převádějí na jeden registr, diakritická znaménka se odstraňují, interpunkční znaménka (ne všechna) se ignorují;
na druhé úrovni se berou v úvahu pouze diakritická znaménka;
na třetí úrovni se zohledňuje pouze registr;
na čtvrté úrovni se zohledňují pouze interpunkční znaménka.

Porovnání probíhá v několika průchodech: nejprve se porovnávají koeficienty první úrovně; pokud se váhy shodují, následuje opětovné porovnání s váhami druhé úrovně; poté, možná, třetí a čtvrté.

Porovnání končí, když v řetězcích jsou odpovídající si jednotky porovnání s různými váhami. Řetězce, které mají shodné váhy na všech čtyřech úrovních, se považují za rovnocenné.

Tento algoritmus (s množstvím dalších technických detailů) dal název zprávě č. 10 — "Unicode Collation Algorithm" (UCA).

V tomto okamžiku se chování třídění z našeho příkladu stává o něco jasnějším. Bylo by dobré je porovnat se standardem Unicode.

Pro testování implementací UCA existuje speciální test, který používá soubor vah, implementující DUCET. V souboru vah lze najít různé zajímavosti. Například tam je pořadí kostek mahjongu a evropského domina, stejně jako pořadí barev v balíčku karet (symbol 1F000 a tak dále). Karty jsou uspořádány podle pravidel bridže — PČBZT, a karty v barvě — v posloupnosti T,2,3… K.

Ruční kontrola správnosti třídění řetězců podle DUCET by byla poměrně únavná, ale k našemu štěstí existuje vzorová implementace knihovny pro práci s Unicode – "Mezinárodní komponenty pro Unicode" (ICU).

Na webu této knihovny, vyvinuté v IBM, jsou demonstrační stránka, včetně stránky algoritmu porovnávání řetězců. Zadáme naše testovací řetězce s výchozími nastaveními a, ó zázraku, dostaneme dokonalé ruské třídění.

Abakanov Michail;malíř
Jolkina Ella;jeřábnice
Ivanov Andrej;instalatér
Ivanova Alla;advokátka

Mimochodem, na webu ICU můžete najít upřesnění práce algoritmu porovnávání při zpracování interpunkčních znamének. V příkladech Collation FAQ jsou ignorovány apostrof a pomlčka.

Unicode nám pomohl, ale hledat příčiny podivného chování sort v Linux budeme muset někde jinde.

Třídění v glibc

Rychlý pohled na zdrojové kódy utility sort z GNU Core Utils ukázal, že v samotné utilitě je lokalizace omezena na tisk aktuální hodnoty proměnné LC_COLLATE při spuštění v ladicím režimu:

$ sort --debug buhg.txt > buhg.srt
sort: používá pravidla třídění ‘en_US.UTF8’

Porovnání řetězců se provádí standardní funkcí strcoll, což znamená, že vše zajímavé se nachází v knihovně glibc.

Na wiki projektem glibc srovnání řetězců se věnuje jeden odstavec. Z tohoto odstavce lze pochopit, že v glibc třídění je založeno na již známém algoritmu UCA (The Unicode collation algorithm) a/nebo na standardu, který mu je blízký ISO 14651 (Mezinárodní řazení a porovnávání řetězců). K poslednímu standardu je třeba poznamenat, že na webu standards.iso.org ISO 14651 je oficiálně oznámen jako veřejně přístupný, ale odpovídající odkaz vede na neexistující stránku. Google vydává několik stránek s odkazy na oficiální weby, které nabízejí zakoupit elektronickou kopii standardu za stovku euro, ale na třetí čtvrté stránce výsledků vyhledávání se najdou i přímé odkazy na PDF. Obecně se standard prakticky neliší od UCA, ale čte se nudněji, protože neobsahuje živé příklady národních zvláštností třídění řetězců.

Nejzajímavější informace na wiki se ukázala být odkazem na bug tracker s diskusí o implementaci porovnávání řetězců v glibc. Z diskuse lze zjistit, že v glibc pro porovnání řetězců se používá ISOtabulka The Common Template Table (CTT), jejíž adresu lze nalézt v příloze A standardu ISO 14651. Mezi lety 2000 a 2015 tato tabulka v glibc neměla maintainer a dost se lišila (alespoň z vnějšího pohledu) od současné verze standardu. Od roku 2015 do roku 2018 probíhala adaptace na novou verzi tabulky a nyní máte šanci potkat v reálném životě jak novou variantu tabulky (CentOS 8), tak i starou (CentOS 7).

Nyní, když máme všechny informace o algoritmu a pomocných tabulkách, můžeme se vrátit k původnímu problému a pochopit, jak správně seřadit řádky v ruské lokalizaci.

ISO 14651/14652

Zdrojový kód zajímající nás tabulky CTT ve většině distribucí Linux se nachází v katalogu /usr/share/i18n/locales/. Samotná tabulka je uložena v souboru iso14651_t1_common. Pak je tento soubor pomocí direktivy copy iso14651_t1_common začleněn do souboru iso14651_t1, který je zase zahrnut v národních souborech, včetně en_US a ru_RU. Ve většině distribucí Linux jsou všechny zdrojové soubory součástí základní instalace, ale pokud chybí, bude nutné nainstalovat další balíček z distribuce.

Struktura souboru iso14651_t1 může se zdát překvapivě rozsáhlá, s nejasnými pravidly pro tvorbu jmen, ale pokud se na to podíváte, zjistíte, že je to dost jednoduché. Struktura je popsána ve standardu ISO 14652, jehož kopii můžete stáhnout z webu open-std.org. Další popis formátu souboru si můžete přečíst na specifikacích POSIX od OpenGroup. Jako alternativu ke čtení standardu můžete prozkoumat zdrojové texty funkce collate_read v glibc/locale/programs/ld-collate.c.

Struktura souboru vypadá následovně:

Ve výchozím nastavení je znak použit jako únikový znak, a konec řádku po znaku # je komentářem. Oba znaky lze předefinovat, což bylo učiněno v nové verzi tabulky:

escape_char /
comment_char %

V souboru se budou objevovat tokeny ve formátu <Uxxxx> nebo <Uxxxxxxxx> (kde x — šestimístná hexadecimální číslice). Toto hexadecimální vyjádření kódových bodů Unicode je v kódování UCS-4 (UTF-32). Všechny ostatní prvky v ostrých závorkách (včetně <Uxxxx_xxxx>, <2> a podobné), se považují za jednoduché řetězcové konstanty, které nemají žádný zvláštní význam mimo kontext.

Řádek LC_COLLATE nám říká, že se dále nacházejí data popisující porovnávání řetězců.

Nejprve jsou zadána jména pro váhy v tabulce porovnávání a jména pro kombinace znaků. Obecně platí, že dva typy jmen patří dvěma různým entitám, ale v reálném souboru jsou zaměškané. Jména vah jsou zadána klíčovým slovem collating-symbol (srovnávací symbol), protože při porovnávání budou Unicode znaky s identickými váhami považovány za ekvivalentní symboly.

Celková délka sekce v aktuální revizi souboru je asi 900 řádků. Vzal jsem příklady z několika míst, abych ukázal libovůli názvů a několik druhů syntaxe.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Zaručená největší hodnota symbolu. Držte na konci tohoto seznamu
...
collating-element  z ""
collating-element  z ""

collating-symbol registruje řetězec OSMANYA v tabulce názvů váh
collating-symbol .. registruje sekvenci názvů, skládajících se z prefixu S a hexadecimální číselný sufix z 1D000 do 1D35F.
FFFF v collating-symbol vypadá jako velké nezáporné celé číslo v hexadecimální soustavě, ale <SFFFF> to je jen název, který by mohl vypadat jako <VERYBIGVAL>
název <U0413> znamená kódový bod v kódování UCS-4
collating-element z "" registruje nové jméno pro pár unicode bodů.

Jakmile jsou názvy vah definovány, stanovují se vlastně váhy. Protože při porovnávání má význam pouze vztah větší-menší, váhy se určují jednoduchou sekvencí výčtu názvů. Nejprve se uvádějí "lehčí" váhy, poté "těžší". Připomínám, že každému Unicode symbolu jsou přiřazeny čtyři různé váhy. Zde jsou shrnuty do jediné uspořádané sekvence. Teoreticky lze jakékoli symbolické jméno použít na kterékoliv ze čtyř úrovní, ale komentáře naznačují, že vývojáři mentálně dělí jména podle úrovní.

% Symbolické přiřazení vah

% Přiřazení vah třetí úrovně




...
% Přiřazení vah druhé úrovně

 % KOMBINUJÍCÍ NÍZKOU ČÁRU
 % KOMBINUJÍCÍ ČÁRKU NAD
 % KOMBINUJÍCÍ OPAČNOU ČÁRKU NAD
...
% Přiřazení vah první úrovně
 % HORIZONTÁLNÍ TABULACE 
 % ŘÁDKOVÝ ZLOM
 % VERTIKÁLNÍ TABULACE
...
 % KYRYLICE MALÉ PÍSMENO DE
 % KYRYLICE MALÉ PÍSMENO KOMI DE
 % KYRYLICE MALÉ PÍSMENO DJE
 % KYRYLICE MALÉ PÍSMENO KOMI DJE
 % KYRYLICE MALÉ PÍSMENO GJE
 % KYRYLICE MALÉ PÍSMENO ZE S KLESAJÍCÍM KOVEM
 % KYRYLICE MALÉ PÍSMENO IE
 % KYRYLICE MALÉ PÍSMENO IE S BREVIDEM
 % KYRYLICE MALÉ PÍSMENO UKRAJINSKÉ IE
 % KYRYLICE MALÉ PÍSMENO ZHE

Konečně, tabulka vah.

Sekce vah je uzavřena v řádcích s klíčovými slovy order_start a order_end. Další parametry order_start určují, v jakém směru jsou řádky procházeny na každé úrovni srovnání. Výchozí hodnota je forward. Tělo sekce se skládá z řádků, které obsahují kód znaku a čtyři jeho váhy. Kód znaku může být zastoupen samotným znakem, kódovou bodem nebo symbolickým názvem, které bylo dříve definováno. Váhy mohou být také definovány symbolickými názvy, kódovými body nebo samotnými znaky. Pokud jsou použity kódové body nebo znaky, pak se jejich váha shoduje s číselnou hodnotou kódové bodu (pozice v Unicode tabulce). Znaky, které nejsou výslovně uvedeny (jak chápu), jsou považovány za přidané do tabulky s primární váhou shodující se s pozicí v Unicode tabulce. Speciální hodnota váhy IGNORE znamená, že na odpovídající úrovni srovnání je tento znak ignorován.

Pro demonstraci struktury vah jsem vybral tři docela zřejmé fragmenty:

znaky, které jsou zcela ignorovány
znaky ekvivalentní číslici tři na prvních dvou úrovních
začátek cyrilice, která neobsahuje diakritická znamení, a proto je řazena převážně podle první a třetí úrovně.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 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

Nyní se mohu znovu vrátit k řazení příkladů na začátku článku. Skrytá past se nachází v této části tabulky vah:

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

Je zřejmé, že v této tabulce jsou interpunkční znaménka z tabulky ASCII (včetně mezery) při porovnávání řetězců se prakticky vždy ignoruje. Výjimku tvoří pouze řetězce, které se shodují ve všem, kromě interpunkce, která se nachází na shodných pozicích. Řetězce z mého příkladu (po seřazení) pro algoritmus porovnání vypadají takto:

AbakanovMichaelsmalíř
JelkinEllaKranovna
IvanovAlmaMalíř
IvanovAndrejzedníř

Vzhledem k tomu, že v tabulce vah velká písmena v ruštině následují po malých (na třetí úrovni <CAP> těžší než <MIN>), třídění vypadá naprosto správně.

Při nastavování proměnné LC_COLLATE=C se načítá zvláštní tabulka, která určuje bajtové porovnání

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'fe', L'xff'
};

Jelikož v Unicode bod kódu Ё, stojí před A, tak i řetězce jsou seřazeny odpovídajícím způsobem.

Textové a binární tabulky

Je zřejmé, že porovnání řetězců je nesmírně častá operace, zatímco rozbor tabulky CTT je poměrně náročná procedura. Pro optimalizaci přístupu k tabulce se kompiluje do binární formy příkazem localedef.

Tým localedef přijímá jako parametry soubor s tabulkou národních specifikací (možnost -i), ve kterém jsou všechny znaky zastoupeny jako Unicode body, a soubor shody Unicode bodů se symboly konkrétních kódování (možnost -f). V důsledku provedené práce se vytvářejí binární soubory pro lokalitu, s názvem uvedeným v posledním parametru.

Glibc podporuje dva formáty binárních souborů: "tradiční" a "moderní".

Tradiční formát předpokládá, že název lokality je název podadresáře v /usr/lib/locale/. V tomto podadresáři se nacházejí binární soubory LC_COLLATE, LC_CTYPE, LC_TIME a t.p. Soubory LC_IDENTIFICATION obsahují formální název lokality (který se může lišit od názvu adresáře) a komentáře.

Moderní formát předpokládá uchovávání všech lokalit v jediném archivu /usr/lib/locale/locale-archive, který se mapuje do virtuální paměti všech procesů, které jej používají glibc. Název lokality v moderním formátu podléhá určité kanonizaci – v názvech kódování zůstávají pouze číslice a písmena uvedená na malé písmeno. Tak ru_RU.KOI8-R, bude uloženo jako ru_RU.koi8r.

Vstupní soubory se hledají v aktuálním adresáři a také v adresářích /usr/share/i18n/locales/ a /usr/share/i18n/charmaps/ pro soubory CTT a soubory kódování odpovídajícím.

Například, příkaz

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

zkompiluje soubor /usr/share/i18n/locales/ru_RU s použitím souboru kódování /usr/share/i18n/charmaps/MAC-CYRILLIC.gz a uloží výsledek do /usr/lib/locale/locale-archive pod názvem ru_RU.maccyrillic

Pokud nastavíte proměnnou LANG=en_US.UTF-8 , pak glibc bude hledat binární soubory lokality v následující posloupnosti souborů a adresářů:

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

Pokud se lokalita vyskytuje jak v tradičním, tak v moderním formátu, dává se přednost modernímu.

Seznam zkompilovaných lokalit lze zobrazit příkazem locale -a.

Příprava vlastní tabulky porovnání

Nyní, obeznámeni se znalostmi, můžeme vytvořit vlastní ideální tabulku porovnání řetězců. Tato tabulka by měla správně porovnávat ruská písmena, včetně písmene Ё, a zároveň zohledňovat interpunkční znaménka podle tabulky ASCII.

Proces přípravy vlastní tabulky řazení se skládá ze dvou fází: úpravy tabulky váh a její kompilace do binární formy příkazem localedef.

Aby bylo možné tabulku porovnání přizpůsobit s minimálními náklady na úpravu, ve formátu ISO 14652 jsou připravovány sekce pro úpravu váh už existující tabulky. Sekce začíná klíčovým slovem reorder-after a uvedením pozice, za kterou následuje výměna. Sekci zakončuje řádek reorder-end. Pokud je třeba upravit několik částí tabulky, vytváří se sekce pro každou takovou část.

Zkopíroval jsem nové verze souborů iso14651_t1_common a ru_RU z repozitáře glibc do svého domácího adresáře ~/.local/share/i18n/locales/ a mírně upravil sekci LC_COLLATE v ru_RU. Nové verze souborů jsou plně kompatibilní s mou verzí glibc. Pokud se rozhodnete použít staré verze souborů, budete muset změnit symbolické názvy a místo, odkud začíná výměna v tabulce.

LC_COLLATE
% Zkopírujte šablonu z ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % MEZERA
 ;;; % VYŘČENÍ
 ;;; % UVOZOVKY
...
 ;;; % PRAVÁ OBRÁCENÁ SLOŽENÁ ZÁVORKA
 ;;; % TILDA
reorder-end
KONEC LC_COLLATE

Ve skutečnosti by bylo třeba změnit pole v LC_IDENTIFICATION tak, aby ukazovala na lokalitu ru_MY, ale v mém příkladu to nebylo potřeba, protože jsem vyloučil z vyhledávání lokality archiv locale-archive.

Aby localedef pracoval se soubory ve své složce prostřednictvím proměnné I18NPATH můžete přidat další adresář pro hledání vstupních souborů, a adresář pro ukládání binárních souborů můžete specifikovat jako cestu se zlomky:

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

POSIX předpokládá, že v LANG můžete psát absolutní cesty k adresářům se soubory lokalizace, které začínají přímo lomítkem, ale glibc v Linux všechny cesty se považují od základního adresáře, který lze předefinovat prostřednictvím proměnné LOCPATH. Po nastavení LOCPATH=~/local/lib/locale/ budou všechny soubory související s lokalizací hledány pouze ve své složce. Archiv lokalizací je při nastavené proměnné LOCPATH ignorován.

To je rozhodující test:

$> LANG=ru_MY.UTF-8 LOCPATH=~/local/lib/locale/ sort buhg.txt
Abakanov Michail;malíř
Jolkina Ella;jeřábnice
Ivanov Andrej;zedník
Ivanova Alla;advokát

Hurá! Udělali jsme to!

Práce na chybách

Již jsem odpověděl na otázky o třídění řetězců, položené na začátku, ale zbývá ještě pár otázek ohledně chyb — viditelných i neviditelných.

Vraťme se k původnímu úkolu.

A program sort a program připojit používají stejné funkce pro porovnávání řetězců z glibc. Jak se tedy stalo, že připojit vyvolával chybu třídění na řetězcích, seřazených příkazem sort v lokalitě en_US.UTF-8? Ответ прост: sort srovnává řetězec jako celek, zatímco připojit srovnává pouze klíč, kterým je ve výchozím nastavení začátek řetězce před prvním mezerou. V mém příkladu to vedlo k chybovému hlášení, protože třídění prvních slov v řetězcích se neshodovalo se tříděním celých řetězců.

Lokalita "C" zaručuje, že ve seřazených řetězcích budou počáteční podsoubory až k prvnímu mezeře také seřazeny, ale to pouze zakrývá chybu. Mohou být zvolena taková data (lidé se stejnými příjmeními, ale různými jmény), která bez chybového hlášení by vedla k nesprávnému výsledku sloučení souborů. Pokud chceme, aby připojit sloučil řádky souborů podle jména a příjmení, správným způsobem je výslovně uvést oddělovač polí a seřadit podle klíčového pole, nikoli podle celého řádku. V tomto případě bude sloučení probíhat správně a v žádné lokalizaci nebudou chyby:

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

Úspěšně provedený příklad v kódování CP1251 obsahuje ještě jednu chybu. Jde o to, že ve všech známých mých distribucích Linux není ve balíčcích zkompilovaná lokalizace ru_RU.CP1251. Pokud nebyla zkompilovaná lokalizace nalezena, sort potichu používá porovnání po bytech, což jsme pozorovali.

Mimochodem, existuje ještě jedna malá chyba spojená s nedostupností zkompilovaných lokalizací. Příkaz LOCPATH=/tmp locale -a vydá seznam všech lokalizací v locale-archive, ale s nastavenou proměnnou LOCPATH pro všechny programy (včetně samotného locale) budou tyto lokalizace 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ávěr

Pokud jste programátor, který je zvyklý myslet si, že řetězce jsou soubor bajtů, pak je váš výběr LC_COLLATE=C.

Pokud jste lingvista nebo autor slovníků, pak je lepší si zkompilovat svou lokalizaci.

Pokud jste běžný uživatel, pak si stačí zvyknout na to, že příkaz ls -a vydává soubory začínající tečkou, spolu s soubory začínajícími písmenem, a Midnight Commander, který používá své vlastní funkce pro třídění názvů, umisťuje soubory začínající tečkou na začátek seznamu.