Uvod

Sve je počelo s kratkim skriptom koja je trebala spojiti informacije o adresama e-mail zaposlenika, dobivenih iz popisa korisnika mailing liste, s pozicijama zaposlenika, dobivenim iz baze podataka ljudskih resursa. Oba popisa su eksportirana u tekstualne datoteke u Unicode kodiranju UTF-8 i pohranjena s unixovskim završecima redaka.

Sadržaj mail.txt

Ivanov Andrej;ia@example.com

Sadržaj buhg.txt

Ivanova Alla;maljar
Jolkina Ella;kranovčica
Ivanov Andrej;slavolikar
Abakanov Mihail;maljar

Za spajanje, datoteke su sortirane unixovskom komandom sort i predane na ulaz unix programu join, koji je naglo završio s greškom:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nije sortirano: Ivanov Andrej;slavolikar

Pogled na rezultat sortiranja pokazao je da je u cjelini sortiranje ispravno, ali u slučaju podudaranja muških i ženskih prezimena, ženska se prezimena pojavljuju ispred muških:

$> sort buhg.txt
Abakanov Mihail;maljar
Jolkina Ella;kranovčica
Ivanova Alla;maljar
Ivanov Andrej;slavolikar

Izgleda kao greška sortiranja u Unicodeu ili kao manifestacija feminizma u algoritmu sortiranja. Prvo je, naravno, vjerodostojnije.

Ostavimo to za sada join i usmjerimo se na sort. Pokušajmo riješiti zadatak metodom pokušaja i pogreške. Za početak, promijenimo lokalitet s en_US na ru_RU. Za sortiranje bilo bi dovoljno postaviti varijablu okruženja LC_COLLATE, ali nećemo baš sitničariti:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;maljar
Jolkina Ella;kranovčica
Ivanova Alla;maljar
Ivanov Andrej;slavolikar

NIšta se nije promijenilo.

Pokušajmo prekodirati datoteke u jednogluk kodiranje:

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

Opet nije bilo promjena.

Ne možemo ništa napamet, moramo tražiti rješenje na internetu. Iako o ruskim prezimenima nema ničega, postoje pitanja o drugim čudnim ponašanjima sortiranja. Na primjer, postoji takav problem: unix sort treats ‘-‘ (dash) characters as invisible. Ukratko, redovi "a-b", "aa", "ac" sortiraju se kao "aa", "a-b", "ac".

Odgovor je svugdje standardan: koristite programski lokalitet "C" i bit ćete sretni. Pokušajmo:

$> LANG=C sort buhg.txt
Jolkina Ella;kranovčica
Abakanov Mihail;maljar
Ivanov Andrej;slavolikar
Ivanova Alla;advokat

Nešto se promijenilo. Ivanovi su se postavili u pravilan red, ali Jolkina je nekako ispala. Vraćamo se na izvorni zadatak:

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

Radilo je bez grešaka, kao što je internet obećao. I to unatoč Junču u prvom redu.

Izgleda da je problem rešen, ali za svaki slučaj isprobaćemo još jedan ruski kod — Windowsov. CP1251:

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

Rezultat sortiranja, koliko god čudno bilo, poklapaće se s lokalitetom "C", i ceo primer, shodno tome, prolazi bez grešaka. Neka vrsta mistike.

Ne volim mistiku u programiranju, pošto obično maskira greške. Moraću ozbiljno da se pozabavim pitanjem kako to funkcioniše sort i na šta utiče LC_COLLATE .

Na kraju ću pokušati da odgovorim na pitanja:

zašto nisu ispravno sortirana ženska prezimena
zašto LANG=hr_HR.CP1251 je ispalo ekvivalentno LANG=C
zašto imaju sort i join različite prikaze o redu sortiranih redova
zašto u svim mojim primerima ima grešaka
na kraju, kako sortira redove prema svojoj želji

Sortiranje u Unicode-u

Prva stanica je tehnički izveštaj br. 10 pod nazivom Unicode collation algorithm na stranici unicode.org. Izveštaj sadrži mnogo tehničkih detalja, pa ću si dozvoliti da navedem kratak pregled osnovnih ideja.

Collation — "upoređivanje" redova — osnova svakog algoritma sortiranja. Sami algoritmi mogu se razlikovati ("bubble", "merge", "quick"), ali svi će koristiti upoređivanje parova redova, kako bi odredili redosled njihovog sleđenja.

Sortiranje redova na prirodnom jeziku je prilično složen problem. Čak i u najjednostavnijim jednoumjernim kodiranjima redosled slova u alfabetskoj listi, barem u nečemu što se razlikuje od engleske latinice, neće se poklapati s redosledom numeričkih vrednosti kojima se ti karakteri kodiraju. Tako u nemačkom alfabetu slovo Ö se nalazi između o i P, a u kodiranju CP850 to spada između ÿ i Ü.

Može se pokušati apstrahovati od konkretne kodiranja i razmatrati "idealna" slova koja su postavljena u određenom redosledu, kao što je učinjeno u Unicode-u. Kodiranja UTF8, UTF16 ili jednoumjerno KOI8-R (ako je potrebno ograničeno podskup Unicode-a) će davati različite numeričke represente slova, ali će se istovremeno pozivati na iste elemente osnovne tabele.

Ispostavlja se da čak i kada izgradimo tablicu znakova od nule, ne možemo dodijeliti univerzalni redoslijed znakova. U različitim nacionalnim alfabetima koji koriste iste slova, redoslijed tih slova može se razlikovati. Na primjer, u francuskom jeziku Æ će se smatrati ligaturom i sortirati kao niz AE. U norveškom jeziku Æ bit će zasebno slovo koje se nalazi nakon Z. Usput, osim ligatura poput Æ postoje slova koja se zapisuju s više znakova. Tako u češkom alfabetu postoji slovo Ch, koje se nalazi između H i I.

. Osim razlika u alfabetima, postoje i druge nacionalne tradicije koje utječu na sortiranje. Konkretno, postavlja se pitanje: kojim redoslijedom trebaju slijediti u rječniku riječi koje se sastoje od velikih i malih slova? Također, na sortiranje mogu utjecati posebnosti korištenja interpunkcijskih znakova. U španjolskom jeziku na početku upitne rečenice stavlja se obrnuti upitni znak (¿Te gusta la música?). U tom slučaju je očigledno da upitne rečenice ne bi trebale biti grupirane u zaseban klaster izvan alfabeta, a kako sortirati nizove s drugim interpunkcijskim znakovima?

Neću se zadržavati na sortiranju nizova u jezicima koji se znatno razlikuju od europskih. Istaknut ću da u jezicima s pravcem pisanja s desna na lijevo ili odozgo prema dolje, znakovi u nizovima vjerojatno se čuvaju u redu slijeda čitanja, a čak iu nealfabetskim pismenostima postoje načini za sortiranje nizova po znakovima. Na primjer, hijeroglifi se mogu sortirati prema obliku (ključevima kineskih hijeroglifa) ili prema izgovoru. Kako bi se trebali sortirati emojiji, iskreno, nemam predstavu, ali se može smisliti nešto i za njih.

Na temelju gore navedenih značajki formulirane su osnovne zahtjeve za usporedbu nizova, temeljenih na Unicode tablicama:

usporedba nizova ne ovisi o položaju znakova u kodnoj tablici;
sekvencije znakova koje čine jedan znak dovode se u kanonički oblik (A + gornji krug točno je ono što je Å);
prilikom usporedbe nizova znak se razmatra u kontekstu niza i, po potrebi, spaja s susjedima u jednu jedinicu usporedbe (Ch u češkom) ili se razbija na više (Æ u francuskom);
svi nacionalni specifičnosti (alfabet, velika/mala slova, interpunkcija, redoslijed vrsta pisanja) trebaju se prilagoditi sve do ručnog dodjeljivanja redoslijeda (emoji);
usporedba je važna ne samo za sortiranje, već i na mnogim drugim mjestima, primjerice za postavljanje raspona redaka (zamjena {A… z} u bash);
usporedba se mora izvršavati dovoljno brzo.

Osim toga, autori izvješća su formulirali svojstva usporedbe na koja programeri algoritma ne smiju oslanjati:

algoritam usporedbe ne smije zahtijevati poseban skup znakova za svaki jezik (ruski i ukrajinski jezici zajednički koriste većinu znakova ćirilice);
usporedba se ne smije oslanjati na redoslijed znakova u Unicode tablicama;
težina niza ne smije biti atribut niza, jer isti niz u različitim kulturnim kontekstima može imati različite težine;
težine nizova mogu se mijenjati prilikom spajanja ili razdvajanja (iz x < y ne implicira da xz < yz);
različiti nizovi koji imaju iste težine smatraju se jednakima s gledišta algoritma sortiranja. Uvođenje dodatnog redoslijeda za takve nizove je moguće, ali može pogoršati performanse;
pri ponovnim sortiranjem, nizovi koji imaju iste težine mogu mijenjati mjesta. Stabilnost je svojstvo određenog algoritma sortiranja, a ne svojstvo algoritma usporedbe nizova (vidi prethodnu točku);
pravila sortiranja mogu se mijenjati s vremenom kako se kulturne tradicije preciziraju/mijene.

Također je navedeno da algoritam usporedbe ne zna ništa o semantici obrađenih nizova. Tako, nizovi koji se sastoje samo od brojeva ne smiju se uspoređivati kao brojevi, a u popisima engleskih naziva ne smije se uklanjati članak (Beatles, The).

Kako bi se zadovoljili svi navedeni zahtjevi, predložen je višerazinski (zapravo četverorazinski) tablični algoritam sortiranja.

Prethodno, znakovi u nizu se dovode u kanonički oblik i grupiraju u jedinice usporedbe. Svakoj jedinici usporedbe dodjeljuju se nekoliko težina, koje odgovaraju nekoliko razina usporedbe. Težine jedinica usporedbe su elementi uređenih skupova (u ovom slučaju cijeli brojevi), koji se mogu uspoređivati kao veći-manji. Posebna vrijednost IGNORED (0x0) znači da se na odgovarajućoj razini usporedbe ta jedinica ne sudjeluje u usporedbi. Usporedba nizova može se ponavljati nekoliko puta, koristeći težine odgovarajućih razina. Na svakoj od razina težine jedinica usporedbe dvaju nizova se postupno uspoređuju međusobno.

U različitim realizacijama algoritma za različite nacionalne tradicije veličine koeficijenata mogu se razlikovati, ali u sastavnicu standarda Unicode uključena je osnovna tablica težina — "Default Unicode Collation Element Table" (DUCET). Želim napomenuti da je postavljanje varijable LC_COLLATE u biti pokazatelj odabira tablice težina u funkciji usporedbe niza.

Težinski koeficijenti DUCET organizirani su na sljedeći način:

na prvoj razini sva slova se dovode u jedan oblik, dijakritički znakovi se odbacuju, interpunkcijski znakovi (ne svi) se ignoriraju;
na drugoj razini uzimaju se u obzir samo dijakritički znakovi;
na trećoj razini uzima se u obzir samo oblik slova;
na četvrtoj razini uzimaju se u obzir samo interpunkcijski znakovi.

Usporedba se odvija u nekoliko prolaza: prvo se uspoređuju koeficijenti prve razine; ako su težine iste, prolazi se ponovna usporedba s težinama druge razine; zatim, moguće, treće i četvrte.

Usporedba završava kada se u nizovima nalaze odgovarajuće jedinice usporedbe s različitim težinama. Nizovi koji imaju jednake težine na svim četirima razinama smatraju se jednakima.

Ovaj algoritam (s mnoštvom dodatnih tehničkih detalja) dao je naziv izvještaju br. 10 — "Unicode Collation Algorithm" (UCA).

Na ovom mjestu ponašanje sortiranja iz našeg primjera postaje pomalo jasnije. Dobro bi bilo usporediti ga sa standardom Unicode.

Za testiranje realizacija UCA postoji posebni test, koji koristi datoteku težina, koji implementira DUCET. U datoteci težina možete pronaći različite zanimljivosti. Na primjer, tamo je redoslijed kostiju mahjonga i europskog domina, kao i redoslijed boja u špilu karata (simbol 1F000 i dalje). Boje karata su poredane prema pravilima bridža — PČBТ, a karte u boji — u redoslijedu T,2,3… K.

Ručno provjeravanje ispravnosti sortiranja nizova prema DUCET bilo bi prilično umarajuće, ali, srećom za nas, postoji uzorna implementacija biblioteke za rad s Unicodeom — "Međunarodne komponente za Unicode" (ICU).

Na web stranici ove biblioteke, razvijene u IBM, postoje demonstracijske stranice, uključujući i stranicu algoritma usporedbe nizova. Unosimo naše testne nizove s zadanim postavkama i, oh čudo, dobivamo savršeno hrvatsko sortiranje.

Abakanov Mihail;maler
Jolkina Ella;kranovka
Ivanov Andrej;bravar
Ivanova Alla;advokat

Usput, na web stranici ICU možete pronaći pojašnjenje rada algoritma usporedbe pri obradi interpunkcijskih znakova. U primjerima Česta pitanja o sortiranju ignoriraju se apostrof i crtica.

Unicode nam je pomogao, ali morat ćemo tražiti razloge čudnog ponašanja sort u Linux negdje drugdje.

Sortiranje u glibc

Brzi pregled izvornog koda alata sort iz GNU Core Utils pokazuje da se u samom alatu lokalizacija svodi na ispis trenutne vrijednosti varijable LC_COLLATE prilikom pokretanja u načinu otklanjanja pogrešaka:

$ sort --debug buhg.txt > buhg.srt
sort: koristi ‘en_US.UTF8’ pravila sortiranja

Usporedba nizova provodi se standardnom funkcijom strcoll, a to znači da se sve zanimljivo nalazi u biblioteci glibc.

Na wiki projekta glibc usporedbi nizova posvećen jedan odlomak. Iz ovog odlomka možemo shvatiti da u glibc sortiranje se temelji na već poznatom algoritmu UCA (The Unicode collation algorithm) i/ili na sličnom standardu ISO 14651 (Međunarodno poredak i usporedba nizova). Što se tiče posljednjeg standarda, treba napomenuti da je na web stranici standards.iso.org ISO 14651 službeno objavljen javnosti, ali odgovarajući link vodi na nepostojeću stranicu. Google prikazuje nekoliko stranica s vezama na službene stranice koje nude kupnju elektroničke kopije standarda za stotinu eura, ali na trećoj-četvrtoj stranici rezultata pretraživanja može se pronaći i izravne veze na PDF. U cjelini, standard se praktički ne razlikuje od UCA, ali se čita dosadnije, budući da ne sadrži slikovite primjere nacionalnih osobitosti sortiranja nizova.

Najzanimljivija informacija na wiki bila je veza na bug tracker s raspravom o implementaciji usporedbe nizova u glibc. Iz rasprave možete saznati da u glibc za usporedbu nizova koristi ISOtablicu tipa The Common Template Table (CTT), čija se adresa može pronaći u dodatku A standardu ISO 14651. Između 2000. i 2015. godine, ova tablica u glibc nije imala maintainer i značajno se razlikovala (barem izvana) od trenutne verzije standarda. Od 2015. do 2018. godine odvijala se prilagodba novoj verziji tablice i trenutno imate priliku susresti u stvarnom životu kako novi varijantu tablice (CentOS 8), tako i staru (CentOS 7).

Sada kada imamo sve informacije o algoritmu i pomoćnim tablicama, možemo se vratiti na izvorni problem i razumjeti kako ispravno sortirati redove u ruskoj lokalizaciji.

ISO 14651/14652

Izvorni kod tablice koja nas zanima CTT u većini distribucija Linux nalazi se u katalogu /usr/share/i18n/locales/. Sama tablica se nalazi u datoteci iso14651_t1_common. Zatim, ta datoteka s direktivom copy iso14651_t1_common uključuje se u datoteku iso14651_t1, koja se zauzvrat uključuje u nacionalne datoteke, uključujući i en_US i ru_RU. U većini distribucija Linux sve izvorne datoteke uključene su u osnovnu instalaciju, ali ako ih nema, morat ćete instalirati dodatni paket iz distribucije.

Struktura datoteke iso14651_t1 može se činiti užasno opširnom, s nejasnim pravilima za izgradnju imena, ali ako se razumije, sve je prilično jednostavno. Struktura je opisana u standardu ISO 14652, kopiju možete preuzeti s web stranice open-std.org. Još jedan opis formata datoteke možete pročitati u specifikacijama POSIX od OpenGroup. Kao alternativu čitanju standarda, možete proučiti izvorne tekstove funkcije collate_read u glibc/locale/programs/ld-collate.c.

Struktura datoteke izgleda ovako:

Po defaultu, simbol se koristi kao simbol za escape, a kraj retka nakon simbola # je komentar. Oba simbola moguće je redefinirati, što je učinjeno u novoj verziji tablice:

escape_char /
comment_char %

U datoteci će se nalaziti tokeni u formatu <Uxxxx> ili <Uxxxxxxxx> (gdje x — hexadecimal digit). To je heksadecimalna reprezentacija kodnih točaka Unicodea u kodiranju UCS-4 (UTF-32). Svi ostali elementi u kutnim zagradama (uključujući <Uxxxx_xxxx>, <2> i slične), smatraju se običnim string konstantama bez posebnog značenja izvan konteksta.

Retak LC_COLLATE nam govori da nakon toga počinju podaci koji opisuju usporedbu stringova.

Prvo se postavljaju imena za težine u tablici usporedbe i imena za kombinacije simbola. Općenito, dva tipa imena pripadaju dvjema različitim entitetima, ali u stvarnoj datoteci su pomiješani. Imena težina postavljaju se ključnom riječi simbol za sortiranje (simbol usporedbe), jer će kod usporedbe Unicode znakovi koji imaju jednake težine biti smatrani ekvivalentnim znakovima.

Ukupna duljina sekcije u trenutnoj reviziji datoteke je oko 900 redaka. Uzeo sam primjere iz nekoliko mjesta kako bih pokazao proizvoljnost imena i nekoliko vrsta sintakse.

LC_COLLATE

simbol za sortiranje <RES-1>
simbol za sortiranje <BLK>
simbol za sortiranje <MIN>
simbol za sortiranje <WIDE>
...
simbol za sortiranje <ARABIC>
simbol za sortiranje <ETHPC>
simbol za sortiranje <OSMANYA>
...
simbol za sortiranje <S1D000>..<S1D35F>
simbol za sortiranje <SFFFF> % Jamčena najveća vrijednost simbola. Držite na kraju ovog popisa
...
element za sortiranje <U0413_0301> iz "<U0413><U0301>"
element za sortiranje <U0413_0341> iz "<U0413><U0341>"

simbol za sortiranje <OSMANYA> registrira niz OSMANYA u tablici težina imena
simbol za sortiranje <S1D000>..<S1D35F> registrira niz imena koja se sastoje od prefiksa S i šesnaestog digit njime od 1D000 do 1D35F.
FFFF u simbol za sortiranje <SFFFF> izgleda kao veliko bezznakovno cijelo u šesnaestom sustavu, ali <SFFFF> to je samo ime koje bi moglo izgledati kao <VERYBIGVAL>
ime <U0413> označava kodnu točku u kodiranju UCS-4
element za sortiranje <U0413_0301> iz "<U0413><U0301>" registrira novo ime za par Unicode točaka.

Kada su težine imena definirane, postavljaju se same težine. Budući da pri usporedbi ima značaj samo odnos veće-manje, težine se definiraju jednostavnom sekvencijom navođenja imena. Prvo se navode "lakše" težine, zatim "teže". Podsjećam da se svakom Unicode znaku dodjeljuju četiri različite težine. Ovdje su one svedene u jedinstvenu uređenu sekvencu. Teoretski, bilo koje simbolično ime može se koristiti na bilo kojoj od četiri razine, no komentari ukazuju da se programeri mentalno dijele imena po razinama.

% Dodjela simboličnih težina

% Dodjele težina treće razine
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Dodjele težina druge razine
<BASE>
<LOWLINE> % SPROVEDENO NISKO
<PSILI> % SPROVEDENA ZAREZ GORE
<DASIA> % SPROVEDENA OBRNUTA ZAREZ GORE
...
% Dodjele težina prve razine
<S0009> % HORIZONTALNA TABULACIJA
<S000A> % REDNA POSLIJEDICA
<S000B> % VERTIKALNA TABULACIJA
...
<S0434> % MALO SLUČAJNO PISMO DE
<S0501> % MALO SLUČAJNO PISMO KOMI DE
<S0452> % MALO SLUČAJNO PISMO DJE
<S0503> % MALO SLUČAJNO PISMO KOMI DJE
<S0453> % MALO SLUČAJNO PISMO GJE
<S0499> % MALO SLUČAJNO PISMO ZE SA SPUSTENIM
<S0435> % MALO SLUČAJNO PISMO IE
<S04D7> % MALO SLUČAJNO PISMO IE S BREVE
<S0454> % MALO SLUČAJNO PISMO UKRAJINSKI IE
<S0436> % MALO SLUČAJNO PISMO ZHE

Na kraju, vlastita tabela težina.

Sekcija težina zaključena je u redovima s ključnim riječima order_start i order_end. Dodatni parametri order_start određuju smjer u kojem se redovi pregledavaju na svakoj razini usporedbe. Zadani parametar je forward. Tijelo sekcije sastoji se od redova koji sadrže kod simbola i četiri njegove težine. Kod simbola može biti predstavljen samim simbolom, kodnom točkom ili simboličnim imenom definiranim ranije. Težine se također mogu definirati simboličnim imenima, kodnim točkama ili samim simbolima. Ako se koriste kodne točke ili simboli, njihova težina odgovara numeričkoj vrijednosti kodne točke (pozicija u Unicode tablici). Simboli koji nisu izričito navedeni (kako ja razumijem) smatraju se dodanima u tablicu s primarnom težinom koja odgovara poziciji u Unicode tablici. Specijalna vrijednost težine IGNORE znači da se na odgovarajućoj razini usporedbe taj simbol ignorira.

Za demonstraciju strukture težina odabrao sam tri dovoljno očita segmenta:

simboli koji se potpuno ignoriraju
simboli ekvivalentni broju tri na prvih dvjema razinama
početak ćirilice, koja ne sadrži dijakritičke znakove, a stoga se sortira, uglavnom, prema prvoj i trećoj razini.

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

Sada se možemo ponovno vratiti na sortiranje primjera s početka članka. Zamka je u ovom dijelu tabele težina:

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

Vidljivo je da u ovoj tablici postoje interpunkcijske znakove iz tablice ASCII (uključujući razmak) pri usporedbi nizova gotovo uvijek se ignorira. Izuzetak čine samo nizovi koji se u potpunosti podudaraju osim po interpunkcijskim znakovima koji se nalaze na istim pozicijama. Nizovi iz mog primjera (nakon sortiranja) za algoritam usporedbe izgledaju ovako:

AbakanovMihailMajstor
JolkinaElakranovčica
IvanovaAllaMajstor
IvanovAndrejZidar

S obzirom na to da u tablici težina velika slova u ruskom jeziku dolaze nakon malih (na trećoj razini <CAP> teže od <MIN>), sortiranje izgleda potpuno ispravno.

Pri postavljanju varijable LC_COLLATE=C učitava se posebna tablica koja postavlja usporedbu bajt po bajt

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

Budući da u Unicodeu kodna točka Ё dolazi prije A, tako se i nizovi sortiraju u skladu s tim.

Tekstualne i binarne tablice

Očigledno je da je usporedba nizova iznimno česta operacija, a analiza tablice CTT prilično je skupa procedura. Za optimizaciju pristupa tablici, ona se kompajlira u binarni oblik pomoću naredbe localedef.

Komanda localedef prima kao parametre datoteku s tablicom nacionalnih značajki (opcija -i), u kojoj su svi simboli predstavljeni Unicode točkama, i datoteku koja odgovara točkama Unicode simbolima određene kodirane (opcija -f). Kao rezultat rada stvaraju se binarne datoteke za lokalitet, s imenom navedenim u posljednjem parametru.

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

Tradicionalni format podrazumijeva da je ime lokaliteta, ime poddirektorija u /usr/lib/locale/. U ovom poddirektoriju se pohranjuju binarne datoteke LC_COLLATE, LC_CTYPE, LC_TIME i slično. Datoteka LC_IDENTIFICATION sadrži formalno ime lokaliteta (koje može biti različito od imena direktorija) i komentare.

Moderni format podrazumijeva pohranu svih lokaliteta u jedinstvenom arhivu /usr/lib/locale/locale-archive, koji se prikazuje u virtualnu memoriju svih procesa koji koriste glibcIme lokalizacije u suvremenom formatu podliježe određenoj kanonizaciji — u nazivima kodiranja ostaju samo brojevi i slova, svedeni na mala slova. Tako hr_HR.KOI8-R, će biti sačuvano kao hr_HR.koi8r.

Ulazne datoteke traže se u trenutnom katalogu, kao i u katalogima /usr/share/i18n/locales/ i /usr/share/i18n/charmaps/ za datoteke CTT i datoteke kodiranja sukladno tome.

Na primjer, naredba

localedef -i hr_HR -f MAC-CYRILLIC hr_HR.MAC-CYRILLIC

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

Ako postavite varijablu LANG=en_US.UTF-8 onda glibc će tražiti binarne datoteke lokalizacije u sljedećem redoslijedu 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 lokalizacija pojavljuje i u tradicionalnom i u suvremenom formatu, prioritet se daje suvremenom.

Popis kompajliranih lokalizacija možete pregledati naredbom locale -a.

Priprema vlastite tablice usporedbe

Sada, s znanjem na raspolaganju, možete stvoriti vlastitu idealnu tablicu usporedbe nizova. Ova tablica mora ispravno uspoređivati ruska slova, uključujući slovo Ё, i pritom uzimati u obzir interpunkcijske znakove prema tablici ASCII.

Proces pripreme vlastite tablice sortiranja sastoji se od dva koraka: uređivanja tablice težina i kompilacije u binarni oblik naredbom localedef.

Kako bi se tablica usporedbe mogla prilagođavati s minimalnim troškovima uređivanja, u formatu ISO 14652 predviđene su sekcije korekcije težina već postojeće tablice. Sekcija počinje ključnom riječi reorder-after i naznakom pozicije nakon koje se provodi zamjena. Sekciju završava redak reorder-end. Ako je potrebno ispraviti nekoliko dijelova tablice, stvara se po sekciji za svaki takav dio.

Kopirao sam nove verzije datoteka iso14651_t1_common i ru_RU iz repozitorija glibc u svoj domaći katalog ~/.local/share/i18n/locales/ i malo uredio odjeljak LC_COLLATE u ru_RU. Nove verzije datoteka u potpunosti su kompatibilne s mojom verzijom glibc. Ako želite koristiti stare verzije datoteka, morat ćete promijeniti simboličke nazive i mjesto s kojeg počinje zamjena u tablici.

LC_COLLATE
% Kopirajte predložak iz ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % EXCLAMATION MARK
 ;;; % QUOTATION MARK
...
 ;;; % RIGHT CURLY BRACKET
 ;;; % TILDE
reorder-end
END LC_COLLATE

U stvari, trebalo bi promijeniti polja u LC_IDENTIFICATION tako da upućuju na lokalizaciju hr_MY, ali u mom primjeru to nije bilo potrebno, jer sam iz pretraživanja lokalizacija isključio arhivu locale-archive.

Da localedef radio s datotekama u svojoj mapi preko varijable I18NPATH možeš dodati dodatni katalog za pretraživanje ulaznih datoteka, a katalog za spremanje binarnih datoteka možeš odrediti kao putanju sa kosim crticama:

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

POSIX podrazumijeva da u LANG možeš pisati apsolutne putanje do katalogâ s datotekama lokalizacije, počinjući s kosom crticom, ali glibc u Linux svi putevi se računaju od osnovnog kataloga, koji se može predefinirati preko varijable LOCPATH. Nakon postavljanja LOCPATH=~/.local/lib/locale/ sve datoteke povezane s lokalizacijom bit će tražene samo u mojoj mapi. Arhiva lokalizacija uz postavljenu varijablu LOCPATH se ignorira.

Evo odlučujućeg testa:

$> LANG=hr_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mihail;slikar
Jolkina Ella;operater
Ivanov Andrij;bravar
Ivanova Alla;advokat

Ura! Uspjeli smo!

Rad na greškama

Već sam odgovorio na pitanja o sortiranju redaka postavljenim na početku, ali još su ostala neka pitanja o greškama — vidljivim i nevidljivim.

Vratimo se izvornoj zadaći.

I program sort i program join koriste iste funkcije za usporedbu redaka iz glibc. Kako se dogodilo da join je prijavljivao grešku sortiranja na redovima, sortiranim komandom sort u lokalizaciji en_US.UTF-8? Ответ прост: sort uspoređuje cijeli redak, dok join uspoređuje samo ključ, koji je prema zadanim postavkama početak retka do prvog razmaknog simbola. U mom primjeru to je dovelo do poruke o grešci jer sortiranje prvih riječi u redovima nije odgovaralo sortiranju cijelih redova.

Lokalizacija "C" jamči da će u sortiranim redovima početne podnizovi do prvog razmaka također biti sortirani, ali to samo prikriva grešku. Mogu se odabrati podaci (ljudi sa istim prezimenima, ali različitim imenima), koji bez poruke o grešci mogu dati pogrešan rezultat spajanja datoteka. Ako želimo da join spaja redove datoteka po imenu i prezimenu, ispravan način bi bio eksplicitno odrediti razdjelnik polja i sortirati po ključnom polju, a ne po cijelom redu. U tom slučaju će i spajanje proći ispravno i u nijednoj lokalizaciji neće biti grešaka:

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

Primjer uspješno izvršen u kodiranju CP1251 sadrži još jednu grešku. Naime, u svim meni poznatim distribucijama Linux nedostaje iskompilirana lokalizacija u paketima ru_RU.CP1251. Ako iskompilirana lokalizacija nije pronađena, tada sort tiho koristi byte-by-byte usporedbu, što smo i primijetili.

Usput, postoji još jedan mali bug vezan za nedostupnost iskompiliranih lokalizacija. Komanda LOCPATH=/tmp locale -a izdaje popis svih lokalizacija u locale-archive, ali uz postavljenu varijablu LOCPATH za sve programe (uključujući i samu locale) ove lokalizacije će biti nedostupne.

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

Ako ste programer koji smatra da su stringovi skupovi bajtova, tada je vaš izbor LC_COLLATE=C.

Ako ste lingvist ili sastavljač rječnika, bolje bi bilo da iskompilirate svoju lokalizaciju.

Ako ste obični korisnik, dovoljno je da se naviknete na to da komanda ls -a izdaje datoteke koje počinju točkom, zajedno s datotekama koje počinju slovom, a Midnight Commander, koji koristi svoje unutarnje funkcije za sortiranje imena, izdvaja datoteke koje počinju točkom na početak popisa.