Uvod

Vse se je začelo s kratkim skriptom, ki naj bi združil informacije o naslovih e-pošta zaposlenih, pridobljenih s seznama uporabnikov poštnega seznama, z nazivom zaposlenih, pridobljenim iz baze kadrovske službe. Obe seznama sta bila eksportirana v besedilne datoteke v kodiranju Unicode UTF-8 in shranjena z unixovskimi konci vrstic.

Sadržaj mail.txt

Ivanov Andrej;ia@example.com

Sadržaj buhg.txt

Ivanova Alla;ometa
Jelkinja Ella;žerjavistka
Ivanov Andrej;mehanik
Abakanov Mihail;ometa

Za združitev sta bili datoteki sortirani z unixovskim ukazom sort in podani v unixovski program pridružite se, ki je nepričakovano končal z napako:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: ni sortiran: Ivanov Andrej;mehanik

Pogled na rezultat sortiranja je pokazal, da je sortiranje na splošno pravilno, toda v primeru ujemanja moških in ženskih priimkov, ženski priimki gredo pred moške:

$> sort buhg.txt
Abakanov Mihail;ometa
Jelkinja Ella;žerjavistka
Ivanova Alla;ometa
Ivanov Andrej;mehanik

Zdi se, da gre za napako sortiranja v Unicode-u ali za izraz feminizma v algoritmu sortiranja. Prvo seveda bolj verjetno.

Pustimo za zdaj pridružite se in se osredotočimo na sort. Poskusimo rešiti nalogo s poskusno metodo. Za začetek spremenimo lokalno okolje iz en_US na ru_RU. Za sortiranje bi bilo dovolj nastaviti okoljsko spremenljivko LC_COLLATE, a ne bomo bili tako skopi:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;ometa
Jelkinja Ella;žerjavistka
Ivanova Alla;ometa
Ivanov Andrej;mehanik

Nič se ni spremenilo.

Poskusimo prekodirati datoteke v enobitno kodiranje:

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

Spet se ni nič spremenilo.

Ni druge, treba bo iskati rešitev na internetu. O ruskih priimkih ni kaj dosti, a so vprašanja o drugih čudnostih sortiranja. Na primer, takšen problem: unix sort obravnava ‘-‘ (pomišljaj) kot nevidne znake. Na kratko, vrstice "a-b", "aa", "ac" so sortirane kot "aa", "a-b", "ac".

Odgovor je povsod standarden: uporabite programersko lokalno okolje "C" in sreča vas bo spremljala. Poskušamo:

$> LANG=C sort buhg.txt
Jelkinja Ella;žerjavistka
Abakanov Mihail;ometa
Ivanov Andrej;mehanik
Ivanova Alla;odvetnica

Nekaj se je spremenilo. Ivanovi so se postavili v pravi vrstni red, toda Jelkinja je nekam splezala. Vrnimo se k izvorni nalogi:

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

Работало без ошибок, как и обещано интернетом. И это несмотря на Ёлкину в первой строке.

Проблема вроде решена, но на всякий случай попробуем еще одну русскую кодировку — виндоусовскую. CP1251:

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

Результат сортировки, как ни странно, совпадает с локалью. "C", и весь пример, соответственно, проходит без ошибок. Какая-то мистическая ситуация.

Я не люблю мистику в программировании, поскольку обычно она маскирует ошибки. Придётся всерьёз заняться вопросом, как работает sort и на что влияет LC_COLLATE .

В конце я попытаюсь ответить на вопросы:

почему неправильно сортировались женские фамилии
je merjeni predmet prav te dolžine, kot jo je pokazal. Ravnil bo samo pokazal njegovo velikost in nič več. Ni filozofski kamen, temveč zgolj lesena deska, s katero merimo. LANG=ru_RU.CP1251 оказался эквивалентом LANG=C
почему у sort in pridružite se разные представления о порядке отсортированных строк
почему во всех моих примерах есть ошибки
наконец, как сортировать строки по своему вкусу

Сортировка в Юникоде

Первой остановкой будет технический отчёт № 10 под названием Unicode collation algorithm na spletnem mestu unicode.org. Отчёт содержит много технических деталей, так что я позволю себе привести краткое изложение основных идей.

Collation — "сравнение" строк — основа любого алгоритма сортировки. Сами алгоритмы могут отличаться ("пузырьком", "слиянием", "быстрый"), но все они будут использовать сравнение пары строк, для определения порядка их следования.

Сортировка строк на естественном языке — это довольно сложная проблема. Даже в простейших однобайтовых кодировках порядок букв в алфавите, хоть в чём-то отличающемся от английской латиницы, уже не будет совпадать с порядком числовых значений, которыми эти буквы кодируются. Так в немецком алфавите буква Ö стоит между O in P, а в кодировке CP850 она попадает между ÿ in Ü.

Можно попытаться абстрагироваться от конкретной кодировки и рассматривать "идеальные" буквы, которые расположены в некотором порядке, как это сделано в Юникоде. Кодировки UTF8, UTF16 или однобайтовая KOI8-R (если нужно ограниченное подмножество Юникода) будут давать разные числовые представления букв, но ссылаться при этом на одни и те же элементы базовой таблицы.

Izkaže se, da celo z ustvarjanjem tabele znakov od začetka ne moremo določiti univerzalnega reda znakov. V različnih nacionalnih abecedah, ki uporabljajo iste črke, se lahko red teh črk razlikuje. Na primer, v francoščini Æ bodo obravnavane kot ligatura in sortirane kot niz AE. V norveščini pa Æ bo ločena črka, ki se nahaja za Z. Mimogrede, poleg ligatur, kot je Æ so tudi črke, zapisane z več simboli. Tako ima češka abeceda črko Ch, ki se nahaja med H in I.

Poleg razlik v abecedah obstajajo tudi druge nacionalne tradicije, ki vplivajo na razvrščanje. Zlasti se postavi vprašanje: v kakšnem redu naj v slovarju sledijo besede, sestavljene iz velikih in malih črk? Na razvrščanje lahko vplivajo tudi posebnosti uporabe ločil. V španščini se na začetku vprašalne povedi postavi obrnjen vprašaj (¿Te gusta la música?). V tem primeru je očitno, da vprašalne povedi ne bi smele biti razvrščene v ločen kluster zunaj abecede, ampak kako razvrstiti nize z drugimi ločili?

Ne bom se ustavljal pri razvrščanju nizi v jezikih, ki se močno razlikujejo od evropskih. Ugotavljam, da se v jezikih s smerjo pisanja od desne proti levi ali od zgoraj navzdol znaki v nizih verjetno hranijo v vrstnem redu branja, in celo v neabecednih pismenih sistemih obstajajo lastni načini za razvrščanje nizov znak za znakom. Na primer, hieroglifi se lahko razvrščajo po oblikovanju (ključev kitajskih hieroglifov) ali po izgovorjavi. Kako naj se razvrščajo emojiji, iskreno rečeno, si ne predstavljam, vendar se tudi zanje lahko nekaj izmisli.

Na podlagi zgoraj naštetih značilnosti so bila oblikovana osnovna načela za primerjavo nizov, ki temeljijo na Unicode tabelah:

primerjava nizov ni odvisna od položaja znakov v kodni tabeli;
zaporedja znakov, ki tvorijo enotne znake, se privedejo v kanonično obliko (A + zgornji krogec je enako kot Å);
pri primerjavi nizov se znak obravnava v kontekstu niza in se, če je potrebno, združi s sosedi v enoto primerjanja (Ch v češčini) ali se razdeli na več (Æ v francoščini);
Vse nacionalne posebnosti (alfabet, velike/male črke, ločila, vrstni red vrst pisanja) morajo biti nastavljive, vse do ročnega določitve vrstnega reda (emojiji);
Primerjava je pomembna ne le za razvrščanje, temveč tudi na mnogih drugih mestih, na primer za določanje razponov vrstic (podstavitev {A…j} v bash);
Primerjava mora potekati dovolj hitro.

Poleg tega so avtorji poročila opredelili lastnosti primerjave, na katere se razvijalci algoritmov ne bi smeli zanašati:

Algoritem primerjave ne sme zahtevati ločenega nabora znakov za vsak jezik (ruski in ukrajinski jeziki skupaj uporabljajo večino znakov cirilice);
Primerjava ne sme temeljiti na vrstnem redu znakov v Unicode tabelah;
Teža niza ne bi smela biti atribut niza, saj ima isti niz v različnih kulturnih kontekstih lahko različne teže;
Teže nizov se lahko spreminjajo med združevanjem ali razdelitvijo (iz x < y to ne pomeni, da xz < yz);
Različni nizi, ki imajo enake teže, se obravnavajo kot enaki glede na algoritem razvrščanja. Uvedba dodatnega urejanja takih nizov je mogoča, vendar lahko poslabša zmogljivost;
Pri ponovnih razvrstitvah se nizi, ki imajo enake teže, lahko zamenjajo. Stabilnost je lastnost določenega algoritma razvrščanja, ne pa lastnost algoritma primerjave nizov (glej prejšnjo točko);
Pravila razvrščanja se lahko s časom spreminjajo, saj se kulturne tradicije natančneje opredeljujejo/spremenijo.

prav tako je navedeno, da algoritem primerjave ne ve ničesar o semantiki obdelanih nizov. Tako se nizi, ki vsebujejo samo številke, ne smejo primerjati kot števila, in v seznamih angleških imen ne sme biti odstranjena členka (Beatles, The).

Da bi zadostili vsem navedenim zahtevam, je bil predlagan večstopenjski (dejansko štiristopenjski) tabelarni algoritem razvrščanja.

Vnaprej se znaki v nizu pripeljejo v kanonično obliko in razvrstijo v enote primerjave. Vsaki enoti primerjave se dodeli več teže, ki ustrezajo več ravnem primerjave. Teže enot primerjave so elementi urejenih množic (v tem primeru cela števila), ki jih je mogoče primerjati na večje-manje. Posebna vrednost IGNORED (0x0) pomeni, da ta enota pri primerjavi na ustrezni ravni ne sodeluje. Primerjava nizov se lahko večkrat ponovi, pri čemer se uporabljajo uteži ustreznih ravni. Na vsaki ravni se uteži enot primerjave dveh nizov zaporedno med seboj primerjajo.

V različnih različicah algoritma za različne nacionalne tradicije se lahko vrednosti koeficientov razlikujejo, vendar standard Unicode vključuje osnovno tabelo uteži — "Default Unicode Collation Element Table" (DUCET). Rad bi opozoril, da nastavitev spremenljivke LC_COLLATE v bistvu nakazuje izbiro tabele uteži v funkciji primerjave nizov.

Utežne koeficente DUCET so zasnovane na naslednji način:

na prvem nivoju se vse črke pretvorijo v enak način pisanja, diakritični znaki se odstranijo, ločila (ne vsa) se prezrejo;
na drugem nivoju se upoštevajo samo diakritični znaki;
na tretjem nivoju se upošteva samo način pisanja;
na četrtem nivoju se upoštevajo samo ločila.

Primerjava poteka v več korakih: najprej se primerjajo koeficienti prvega nivoja; če se uteži ujemajo, se izvede ponovna primerjava z utežmi drugega nivoja; nato, po potrebi, tretjega in četrtega.

Primerjava se konča, ko v nizih najdemo ustrezne enote primerjave z različnimi utežmi. Nizi, ki imajo enake uteži na vseh štirih nivojih, se štejejo za enake.

Ta algoritem (s številnimi dodatnimi tehničnimi podrobnostmi) je dal ime poročilu št. 10 — "Unicode Collation Algorithm" (UCA).

Na tem mestu se vedenje sortiranja iz našega primera nekoliko bolje razume. Dobro bi ga bilo primerjati s standardom Unicode.

Za testiranje izvedb UCA obstaja poseben test, ki uporablja datoteko uteži, koji implementira DUCET. V datoteki uteži lahko najdete različne zanimivosti. Na primer, tam je vrstni red ploščic mahjonga in evropskega domin, pa tudi vrstni red barv v igralni karti (simbol 1F000 in naprej). Igralne barve so razporejene v skladu s pravili bridža — PČB, karte v barvi pa v zaporedju T, 2, 3… K.

Ročna preverba pravilnosti sortiranja nizov v skladu z DUCET bi bila precej naporna, a na srečo za nas obstaja odlična implementacija knjižnice za delo z Unicode — "Mednarodne komponente za Unicode" (ICU).

Na spletni strani te knjižnice, razvite v IBM, so demonstracijske strani, vključno z stranjo algoritma za primerjanje nizov. Vnesemo naše testne nize s privzetimi nastavitvami in, o čudež, dobimo popolno rusko sortiranje.

Abakanov Mihail; slikopleskar
Jolkina Ella; žerjavistka
Ivanov Andrej; ključavničar
Ivanova Alla; odvetnica

Še več, na spletni strani ICU lahko najdete pojasnilo delovanja algoritma za primerjanje ob obdelavi ločil. V primerih FAQ o sortiranju se apostrof in pomišljaj prezreta.

Unicode nam je pomagal, vendar bo treba iskati vzroke za nenavadno vedenje sort u Linux kjer drugje.

Sortiranje v glibc

Hiter pregled izvorne kode orodja sort iz GNU Core Utils je pokazal, da se v samem orodju lokalizacija zmanjša na tiskanje trenutne vrednosti spremenljivke LC_COLLATE ob zagonu v togo načinu:

$ sort --debug buhg.txt > buhg.srt
sort: uporablja pravila za sortiranje ‘en_US.UTF8’

Primerjanje nizov se izvaja s standardno funkcijo strcoll, kar pomeni, da je vse zanimivo v knjižnici glibc.

Na wiki projekta glibc Primerjanje nizov ima posvečen en odstavek. Iz tega odstavka lahko razumemo, da je v glibc sortiranje zasnovano na že znanem algoritmu UCA (Unicode collation algorithm) in/ali na sorodni standardu ISO 14651 (Mednarodno uravnavanje in primerjanje nizov). Glede zadnjega standarda je treba omeniti, da je na spletni strani standards.iso.org ISO 14651 uradno razglašen za javno dostopnega, vendar ustrezna povezava vodi na neobstoječo stran. Google prikazuje več strani s povezavami na uradne strani, ki ponujajo nakup elektronske kopije standarda za sto evrov, vendar na tretji ali četrti strani rezultatov iskanja najdemo tudi neposredne povezave do PDF. Splošno gledano, standard se praktično ne razlikuje od UCA, vendar je branje dolgočasnejše, ker ne vsebuje živahnih primerov nacionalnih posebnosti pri sortiranju nizov.

Najzanimivejša informacija na wiki se je izkazala za povezavo do sistem za poročanje napak s razpravo o izvedbi primerjanja nizov v glibc. Iz razprave lahko izvemo, da v glibc za primerjanje nizov uporabljajo ISOtabelo The Common Template Table (CTT), katere naslov lahko najdete v Prilogi A standarda ISO 14651. Med leti 2000 in 2015 je ta tabela v glibc ni imela vzdrževalca in se je precej razlikovala (vsaj zunaj) od trenutne različice standarda. Od leta 2015 do 2018 je potekala prilagoditev novi različici tabele in trenutno imate priložnost srečati v resničnem svetu tako novo različico tabele (CentOS 8), kot tudi staro (CentOS 7).

Zdaj, ko imamo vse informacije o algoritmu in pomožnih tabelah, se lahko vrnemo k izhodiščnemu vprašanju in razumemo, kako pravilno razvrstiti vrstice v ruski lokalizaciji.

ISO 14651/14652

Izvorna koda tabele, ki nas zanima CTT v večini distribucij Linux se nahaja v imeniku /usr/share/i18n/locales/. Sama tabela se nahaja v datoteki iso14651_t1_common. Nato se ta datoteka vključuje v datoteko copy iso14651_t1_common v datoteko iso14651_t1, ki se nato vključuje v nacionalne datoteke, vključno z en_US in ru_RU. V večini distribucij Linux vse izvorne datoteke vključene v osnovno namestitev, vendar če jih ni, bo treba namestiti dodatni paket iz distribucije.

Struktura datoteke iso14651_t1 se lahko zdi strašno obsežna, z nejasnimi pravili oblikovanja imen, vendar če se poglobite, je vse dovolj preprosto. Struktura je opisana v standardu ISO 14652, kopijo katerega lahko prenesete s spletne strani open-std.org. Še en opis formata datoteke lahko preberete v specifikacijah POSIX od OpenGroup. Kot alternativo branju standarda lahko preučite izvorne kode funkcije collate_read u glibc/locale/programs/ld-collate.c.

Struktura datoteke izgleda takole:

Privzeto se simbol uporablja kot zaščitni simbol, konec vrstice po simbolu # pa je komentar. Obe simboli lahko prekoračita, kar je bilo storjeno v novi različici tabele:

escape_char /\ncomment_char %

V datoteki se bodo pojavili tokni v formatu <Uxxxx> ili <Uxxxxxxxx> (gdje x — številska cifra). To je številska predstavitev kodnih točk Unikoda v kodiranju UCS-4 (UTF-32). Vsi ostali elementi v oglatih oklepajih (vključno z <Uxxxx_xxxx>, <2> in podobno) se obravnavajo kot navadne verižne konstante, ki nimajo posebnega pomena zunaj konteksta.

Vrstica LC_COLLATE nam pove, da se začenjajo podatki, ki opisujejo primerjavo nizov.

Najprej se določijo imena za teže v tabeli primerjave in imena za kombinacije simbolov. Na splošno sta dva tipa imen povezana z dvema različnima entitetama, vendar so v resnični datoteki pomešana. Imena teže so določena s ključnimi besedami collating-symbol (comparing symbol), because when comparing Unicode characters with equal weights, they will be considered equivalent characters.

The total length of the section in the current revision of the file is about 900 lines. I extracted examples from several places to demonstrate the arbitrariness of names and various syntax types.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Guaranteed largest symbol value. Keep at end of this list
...
collating-element  from ""
collating-element  from ""

collating-symbol registers the string OSMANYA in the weight names table
collating-symbol .. registers a sequence of names consisting of a prefix S and a hexadecimal numeric suffix of 1D000 do 1D35F.
FFFF u collating-symbol appears as a large unsigned integer in hexadecimal, but <SFFFF> is just a name that could look like <VERYBIGVAL>
имя <U0413> means a code point in the encoding UCS-4
collating-element from "" registers a new name for a pair of Unicode points.

When weight names are defined, actual weights are assigned. Since only greater-lesser relationships matter in comparison, weights are determined by a simple sequence of enumerating names. Lighter weights are listed first, followed by heavier ones. I remind you that each Unicode character is assigned four different weights. Here, they are consolidated into a single ordered sequence. Theoretically, any symbolic name can be used at any of the four levels, but comments indicate that developers mentally categorize names by levels.

% Symbolic weight assignments

% Third-level weight assignments




...
% Second-level weight assignments

 % COMBINING LOW LINE
 % COMBINING COMMA ABOVE
 % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
 % HORIZONTAL TABULATION 
 % LINE FEED
 % VERTICAL TABULATION
...
 % CYRILLIC SMALL LETTER DE
 % CYRILLIC SMALL LETTER KOMI DE
 % CYRILLIC SMALL LETTER DJE
 % CYRILLIC SMALL LETTER KOMI DJE
 % CYRILLIC SMALL LETTER GJE
 % CYRILLIC SMALL LETTER ZE WITH DESCENDER
 % CYRILLIC SMALL LETTER IE
 % CYRILLIC SMALL LETTER IE WITH BREVE
 % CYRILLIC SMALL LETTER UKRAINIAN IE
 % CYRILLIC SMALL LETTER ZHE

Končno, dejanska tabela teže.

Sekcija teže je vključena v vrstice s ključnimi besedami order_start in order_end. Dodatni parametri order_start določajo, v katero smer se pregledujejo vrstice na vsaki ravni primerjave. Privzeto se uporablja parameter forward. Telo sekcije je sestavljeno iz vrstic, ki vsebujejo kodo znaka in štiri njegove teže. Koda znaka je lahko predstavljena kot sam znak, kodna točka ali simbolno ime, že prej določeno. Teže se lahko določijo tudi s simbolnimi imeni, kodnimi točkami ali samimi znaki. Če se uporabljajo kodne točke ali znaki, potem njihova teža ustreza numerični vrednosti kodne točke (poziciji v tabeli Unicode). Znakovi, ki niso izrecno navedeni (kolikor razumem) se štejejo kot dodani v tabelo s primarno težo, ki ustreza poziciji v tabeli Unicode. Posebna vrednost teže IGNORE pomeni, da se na ustrezni ravni primerjave ta znak ignorira.

Za prikaz strukture teže sem izbral tri kar očitne dele:

znaki, ki se popolnoma ignorirajo
znaki, ekvivalentni številu tri na prvih dveh ravneh
začetek cirilice, ki ne vsebuje diakritičnih znakov, zato se razvršča predvsem po prvi in tretji ravni.

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

Zdaj se lahko spet vrnemo k razvrščanju primerov na začetku članka. Zanka se skriva v tem delu tabele teže:

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

Iz te tabele je očigledno da su interpunkcijski znakovi iz tabele ASCII (uključujući razmak) pri poređenju stringova praktično uvek se ignorišu. Izuzetak čine samo stringovi koji se podudaraju u svemu osim interpunkcijskih znakova na odgovarajućim mestima. Stringovi iz mog primera (posle sortiranja) za algoritam poređenja izgledaju ovako:

AbakanovMihailMalar
JolkinaElliKranovščica
IvanovaAllaMalar
IvanovAndrejLesar

Imajući u vidu da u tabeli težina velika slova u ruskom jeziku dolaze posle malih (na trećem nivou <CAP> teže nego <MIN>), sortiranje izgleda apsolutno ispravno.

Pri postavljanju varijable LC_COLLATE=C učitava se posebna tabela koja definiše bajt po bajt upoređivanje

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

Pošto u Unikodu tačka kodiranja Ё prethodi A, tako se i stringovi sortiraju odgovarajuće.

Tekstualne i binarne tabele

Očigledno je da je poređenje stringova izuzetno često korišćena operacija, a analiza tabele CTT prilično skupa procedura. Da bi se optimizovao pristup tabeli, ona se kompajlira u binarni oblik pomoću komande localedef.

Komanda localedef koja prima kao parametre datoteku sa tabelom nacionalnih osobina (opcija -i), u kojoj su svi simboli predstavljeni Unikod tačkama, i datoteku usklađivanja tačaka Unikoda sa određenim kodiranjem (opcija -f). Kao rezultat rada kreiraju se binarne datoteke za lokalitet, sa imenom navedenim u poslednjem parametru.

Glibc podržava dva formata binarnih datoteka: "tradicionalni" i "savremeni".

Tradicionalni format podrazumeva da ime lokaliteta bude ime poddirektorijuma u /usr/lib/locale/. U ovom poddirektorijumu se čuvaju binarne datoteke LC_COLLATE, LC_CTYPE, LC_TIME itd. Datoteka LC_IDENTIFICATION sadrži formalno ime lokaliteta (koje može biti različito od imena direktorijuma) i komentare.

Savremeni format podrazumeva čuvanje svih lokaliteta u jednom arhivu /usr/lib/locale/locale-archive, koji se mapira u virtuelnu memoriju svih procesa koji koriste glibcIme lokaliteta u modernom formatu podložan je određenoj kanonizaciji — u nazivima kodiranja ostaju samo cifre i slova, dovede se u mala slova. Tako sl_SI.KOI8-R, biće sačuvano kao sl_SI.koi8r.

Ulazne datoteke se pretražuju u trenutnom katalogu, kao i u katalogama /usr/share/i18n/locales/ in /usr/share/i18n/charmaps/ za datoteke CTT i datoteke kodiranja u skladu s tim.

Na primer, komanda

localedef -i sl_SI -f MAC-CYRILLIC sl_SI.MAC-CYRILLIC

kompiliše datoteku /usr/share/i18n/locales/ru_RU koristeći datoteku kodiranja /usr/share/i18n/charmaps/MAC-CYRILLIC.gz i sačuvaće rezultat u /usr/lib/locale/locale-archive pod imenom sl_SI.maccyrillic

Ako se postavi promenljiva LANG=en_US.UTF-8 onda glibc će tražiti binarne datoteke lokaliteta u sledećem redosledu datoteka i katalogâ:

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

Ako se lokalitet pojavljuje i u tradicionalnom i u modernom formatu, prioritet se daje modernom.

Pregledate listu kompilanih lokaliteta možete komandom locale -a.

Priprema svoje tabele upoređivanja

Sada, naoružani znanjem, možemo kreirati sopstvenu idealnu tabelu za upoređivanje. Ova tabela treba da ispravno upoređuje ruska slova, uključujući slovo Ё, i pritom uzima u obzir interpunkcijske znakove u skladu sa tabelom ASCII.

Proces pripreme sopstvene tabele sortiranja sastoji se iz dva koraka: uređivanja tabele težina i kompajliranja u binarni oblik komandom localedef.

Kako bi se tabela upoređivanja mogla prilagoditi uz minimalne troškove uređivanja, u formatu ISO 14652 predviđene su sekcije za korekciju težina već postojećih tabela. Sekcija počinje ključnom rečju reorder-after i naznakom pozicije posle koje se vrši zamena. Sekciju završava linija reorder-end. Ako je potrebno ispraviti više delova tabele, onda se kreira po jedna sekcija za svaki takav deo.

Kopirao sam nove verzije datoteka iso14651_t1_common in ru_RU iz repozitorijuma glibc u svoju domaću mapu ~/local/share/i18n/locales/ i malo uredio odeljak LC_COLLATE u ru_RU. Nove verzije datoteka su potpuno kompatibilne sa mojom verzijom glibc. Ako odlučite da koristite stare verzije datoteka, moraćete da promenite simbolička imena i mesto odakle počinje zamena u tabeli.

LC_COLLATE
% Kopirajte šablon iz ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;; % PROSTOR
 ;; % UZVIK
 ;; % CITAAT
...
 ;; % DESNI VITIČASTI ZAVRŠETAK
 ;; % TILDA
reorder-end
KRAJ LC_COLLATE

Na resnični način bi bilo treba spremeniti polja v LC_IDENTIFICATION da bi kazala na lokalno okolje sl_MY, vendar v mojem primeru to ni bilo potrebno, saj sem iz iskanja lokalizacij izključil arhiv locale-archive.

Da localedef je deloval s datotekami v moji mapi prek spremenljivke I18NPATH lahko dodamo dodatni imenik za iskanje vhodnih datotek, imenik za shranjevanje binarnih datotek pa lahko navedemo v obliki poti z poševnicami:

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

POSIX predpostavlja, da lahko v LANG napišemo absolutne poti do imenikov z lokalnimi datotekami, ki se začnejo s poševnico, toda glibc u Linux vse poti se štejejo od osnovnega imenika, ki ga lahko prepišemo s spremenljivko LOCPATH. Po nastavitvi LOCPATH=~/local/lib/locale/ se bodo vse datoteke, povezane z lokalizacijo, iskale samo v moji mapi. Arhiv lokalizacij z nastavljeno spremenljivko LOCPATH je prezrta.

Tukaj je odločilni test:

$> LANG=sl_MY.UTF-8 LOCPATH=~/local/lib/locale/ sort buhg.txt
Abakanov Mihail;barve
Jelkin Ela;kranovka
Ivanov Andrej;tesar
Ivanova Alla;odvetnica

Hura! Uspelo nam je!

Rad na greškama

Že sem odgovoril na vprašanja o razvrščanju vrstic, postavljena na začetku, toda še vedno sta ostali dve vprašanji glede napak — vidnih in nevidnih.

Vrnimo se k izvorni nalogi.

In program sort in program pridružite se uporabljata iste funkcije za primerjavo nizov iz glibc. Kako se je to zgodilo, da pridružite se je prikazal napako pri razvrščanju vrstic, razvrščenih z ukazom sort v lokalnem okolju en_US.UTF-8? Ответ прост: sort primerja celoten niz, medtem ko pridružite se primerja samo ključe, ki so po privzetku začetni del niza do prvega presledka. V mojem primeru je to privedlo do napake, saj razvrščanje prvih besed v nizih ni bilo skladno z razvrščanjem celotnih nizov.

Lokalno okolje "C" zagotavlja, da bodo začetni podnizi do prvega presledka tudi razvrščeni, vendar to le prikriva napako. Mogoče je izbrati takšne podatke (ljudi z enakimi priimki, a različnimi imeni), ki bi brez napake privedli do napačnega rezultata pri združevanju datotek. Če želimo, da pridružite se združi vrstice datotek po F, I in O, bo pravilen način jasna navedba ločila za polja in razvrščanje po ključnem polju, ne po celotnem nizu. V tem primeru bo tudi združevanje pravilno potekalo in v nobenem lokalnem okolju ne bo napak:

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

Успешно выполненный пример в кодировке CP1251 содержит еще одну ошибку. Дело в том, что во всех известных мне дистрибутивах Linux в пакетах отсутствует скомпилированная локаль ru_RU.CP1251. Если скомпилированная локаль не найдена, то sort молча использует побайтовое сравнение, что мы и наблюдали.

Кстати, есть еще один маленький глюк, связанный с недоступностью скомпилированных локалей. Команда LOCPATH=/tmp locale -a выдаст список всех локалей в locale-archive, но при установленной переменной LOCPATH для всех программ (в том числе и для самой locale) эти локали будут недоступны.

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

Zaključek

Если вы программист, который привык считать, что строки — это набор байтов, то ваш выбор LC_COLLATE=C.

Если вы лингвист или составитель словарей, то вам лучше скомпилировать свою локаль.

Если вы простой пользователь, то вам достаточно привыкнуть к тому, что команда ls -a выдаёт файлы, начинающиеся с точки, вперемешку с файлами, начинающимися с буквы, а Midnight Commander, который использует свои внутренние функции для сортировки имён, выносит файлы, начинающиеся с точки, в начало списка.