Uvod
Sve je počelo s kratkim skriptom koji je trebao spojiti informacije o adresama e-mail zaposlenika, dobijenih s liste korisnika mailing liste, s radnim mestima zaposlenika, dobijenim iz evidencije ljudskih resursa. Oba spiska su eksportovana u tekstualne datoteke u Unicode kodiranju UTF-8 i sačuvana s unix završenicama redova.
Sadržaj mail.txt
Ivanov Andrej;ia@example.comSadržaj buhg.txt
Ivanova Alla;maljar
Jelkina Ella;kranovčica
Ivanov Andrej;tesar
Abakanov Mihail;maljarZa spajanje, datoteke su sortirane unix komandama sort i prosleđene unix programu join, koji je iznenada 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: is not sorted: Ivanov Andrej;tesarPogled na rezultat sortiranja pokazao je da je u celini sortiranje ispravno, ali u slučaju poklapanja muških i ženskih prezimena, ženska idu pre muških:
$> sort buhg.txt
Abakanov Mihail;maljar
Jelkina Ella;kranovčica
Ivanova Alla;maljar
Ivanov Andrej;tesarIzgleda kao greška u sortiranju u Unicode-u ili kao manifestacija feminizma u algoritmu sortiranja. Prvo je, naravno, verovatnije.
Ostavimo za sada join i fokusirajmo se na sort. Pokušajmo da rešimo problem metodom pokušaja i greške. Za početak, promenimo lokalizaciju s en_US na ru_RU. Za sortiranje bi bilo dovoljno postaviti varijablu okruženja LC_COLLATE, ali nećemo se ograničavati:
$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;maljar
Jelkina Ella;kranovčica
Ivanova Alla;maljar
Ivanov Andrej;tesarNije se ništa promenilo.
Pokušajmo da prekodiramo datoteke u jednonitnu kodiranje:
$> iconv -f UTF-8 -t KOI8-R buhg.txt
| LANG=ru_RU.KOI8-R sort
| iconv -f KOI8-R -t UTF8Opet se ništa nije promenilo.
Ne može se ništa, moraćemo da tražimo rešenje na internetu. Direkno o ruskim prezimenima nema ništa, ali postoje pitanja o drugim čudnim stvarima u sortiranju. Na primer, takav problem: . Ukratko, redovi "a-b", "aa", "ac" se sortiraju kao "aa", "a-b", "ac".
Odgovor svuda standardan: koristite programersku lokalnost "C" i biće vam sreće. Pokušajmo:
$> LANG=C sort buhg.txt
Jelkina Ella;kranovčica
Abakanov Mihail;maljar
Ivanov Andrej;tesar
Ivanova Alla;advokatNeki su se redovi promenili. Ivanovi su se posložili u pravilan redosled, ali Jelkina je nekako nestala. Vraćamo se na izvorni problem:
$> LANG=C sort buhg.txt > buhg.srt
$> LANG=C sort mail.txt > mail.srt
$> LANG=C join buhg.srt mail.srt > resultRadilo je bes grešaka, kao što je internet obećao. I to uprkos Ēolkinu u prvom redu.
Izgleda da je problem rešen, ali za svaki slučaj pokušajmo još jednu rusku kodiranje — windows kodiranje CP1251:
$> iconv -f UTF-8 -t CP1251 buhg.txt
| LANG=ru_RU.CP1251 sort
| iconv -f CP1251 -t UTF8 Rezultat sortiranja će, zanimljivo, odgovarati lokalnoj postavci "C", i ceo primer, prema tome, prolazi bez grešaka. Neka mistika.
Ne volim mistiku u programiranju, jer obično prikriva greške. Moraću ozbiljno da proučim kako funkcioniše sort i na šta utiče LC_COLLATE .
Na kraju ću pokušati da odgovorim na pitanja:
- zašto su ženska prezimena bila sortirana pogrešno
- zašto LANG=ru_RU.CP1251 se ispostavio ekvivalentom LANG=C
- zašto su sort i join različita predstava o redosledu sortiranih redova
- zašto u svim mojim primerima postoje greške
- konačno, kako sortirati redove po svom ukusu
Sortiranje u Unicode-u
Prva stanica biće tehnički izveštaj br. 10 pod nazivom sajtu . Izveštaj sadrži mnogo tehničkih detalja, pa ću prilikom sebi dozvoliti da navedem kratak pregled osnovnih ideja.
Klasifikacija — "upoređivanje" redova — osnova svakog algoritma sortiranja. Sami algoritmi mogu se razlikovati ("bubljanje", "spajanje", "brzo"), ali svi će koristiti upoređivanje parova redova da odrede redosled.
Sortiranje redova na prirodnom jeziku je prilično složen problem. Čak i u najjednostavnijim jednonitnim kodiranjima, redosled slova u abecedi, u nečem što se razlikuje od engleskog latiničnog pisma, neće se poklapati sa redosledom numeričkih vrednosti kojima su ta slova kodirana. Tako, u nemačkoj abecedi slovo Ö stoji između O i P, a u kodiranju CP850 pada 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 to učinjeno u Unicode-u. Kodiranja UTF8, UTF16 ili jednonitna KOI8-R (ako je potrebna ograničena podskupina Unicode-a) daće različite numeričke prikaze slova, ali će se odnositi na iste elemente osnovne tabele.
Ispostavlja se da čak i kada izgradimo tabelu karaktera od nule, ne možemo dodeliti univerzalni redosled tim karakterima. U različitim nacionalnim alfabetima koji koriste iste slova, redosled tih slova može se razlikovati. Na primer, u francuskom jeziku Æ će se smatrati ligaturom i sortiraće se kao niz AE. U norveškom jeziku Æ će biti posebno slovo koje se nalazi posle Z. Usput, osim ligatura kao što su Æ postoje slova koja se zapisuju sa više simbola. Tako u češkom alfabetu postoji slovo Ch, koje se nalazi između H i I.
Osim razlike u alfabetima postoje i druge nacionalne tradicije koje utiču na sortiranje. Konkretno, postavlja se pitanje: kojim redosledom bi trebalo da slede u rečniku reči koje se sastoje od velikih i malih slova? Takođe, na sortiranje mogu uticati posebnosti korišćenja interpunkcijskih znakova. U španskom 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 trebalo grupisati u poseban klaster van alfabeta, a kako sortirati nizove sa drugim interpunkcijskim znacima?
Neću se zadržavati na sortiranju nizova u jezicima koji se značajno razlikuju od evropskih. Istaknuću da se u jezicima sa pravcem pisanja s desna na levo ili odozgo prema dole, simboli u nizovima verovatno čuvaju u redosledu čitanja, a čak i u nealfabetskim pismima postoje načini za redosled simbola. Na primer, hijeroglifi se mogu redoslediti prema obliku () ili prema izgovoru. Na koji način bi trebalo redoslediti emodžije, iskreno, ne mogu da zamislim, ali i za njih se može smisliti nešto.
Na osnovu gore navedenih osobina formulisani su osnovni zahtevi za poređenje nizova baziranih na Unicode tabelama:
- poređenje nizova ne zavisi od pozicije simbola u kodnoj tabeli;
- sekvencije simbola koji čine jedinstveni simbol dovode se u kanonički oblik (A + gornji krug je isto što i Å);
- prilikom poređenja nizova, simbol se razmatra u kontekstu niza i, po potrebi, okuplja se sa susedima u jednu jedinicu poređenja (Ch na češkom) ili se deli na više (Æ na francuskom);
- Sve nacionalne karakteristike (abeceda, velika/mala slova, interpunkcija, redoslijed vrsta pisanja) trebaju se prilagođavati, uključujući mogućnost ručnog određivanja redoslijeda (emojis);
- Uporedba je važna ne samo za sortiranje, već i na mnogim drugim mestima, na primer za određivanje intervala redova (zamena {A… ja} u bash);
- Uporedba mora biti dovoljno brza.
Pored toga, autori izveštaja su formulisali osobine uporedbe na koje programeri algoritma ne bi trebali da se oslanjaju:
- Algoritam za upoređivanje ne sme zahtevati poseban skup simbola za svaki jezik (ruski i ukrajinski jezici zajednički koriste većinu simbola ćirilice);
- Uporedba ne bi trebala biti zasnovana na redosledu simbola u Unicode tabelama;
- Težina niza ne bi trebala biti atribut niza, jer isti niz može imati različite težine u različitim kulturnim kontekstima;
- Težine nizova se mogu promeniti prilikom spajanja ili deljenja (iz x < y ne znači da xz < yz);
- Različiti nizovi koji imaju jednake težine smatraju se jednakim u smislu algoritma sortiranja. Uvođenje dodatnog redoslednog kriterijuma za takve nizove je moguće, ali može poboljšati performanse;
- Prilikom ponovnih sortiranja, nizovi koji imaju jednake težine mogu menjati mesta. Stabilnost je osobina specifičnog algoritma sortiranja, a ne osobina algoritma za upoređivanje nizova (vidi prethodnu tačku);
- Pravila sortiranja se mogu menjati tokom vremena kako se kulturne tradicije preciziraju/menjaju.
Takođe je navedeno da algoritam za upoređivanje ne zna ništa o semantici obrađenih nizova. Na primer, nizovi koji se sastoje isključivo od cifara ne bi trebalo da se upoređuju kao brojevi, a u listama engleskih naziva član ne bi trebao biti uklonjen (Beatles, The).
Da bi se zadovoljili svi navedeni zahtevi, predložen je višerazinski (zapravo četverorazinski) tabelarni algoritam sortiranja.
Pre toga, simboli u nizu se dovode do kanonskog oblika i grupišu u jedinice upoređivanja. Svakoj jedinici upoređivanja dodeljuju se nekoliko težina, u skladu sa više nivoa upoređivanja. Težine jedinica upoređivanja su elementi uređenih skupova (u ovom slučaju cela brojevi) koje se mogu upoređivati kao veći/manji. Specijalna vrednost IGNORED (0x0) označava da na odgovarajućem nivou poređenja, ova jedinica nije uključena u poređenje. Poređenja stringova mogu se ponavljati više puta, koristeći težine odgovarajućih nivoa. Na svakom od nivoa, težine jedinica poređenja dva stringa se uzastopno upoređuju.
U različitim implementacijama algoritma za različite nacionalne tradicije, vrednosti koeficijenata mogu se razlikovati, ali u sastavnu strukturu standarda Unikoda uključena je osnovna tabela težina — "Default Unicode Collation Element Table" (DUCET). Želim napomenuti da postavljanje promenljive LC_COLLATE u suštini predstavlja izbor tabele težina u funkciji poređenja stringova.
Težinski koeficijenti DUCET su strukturirani na sledeći način:
- na prvom nivou se sve slova dovode u jedan isti oblik, dijakritički znakovi se ignoriraju, a interpunkcijski znakovi (ne svi) se zanemaruju;
- na drugom nivou se uzimaju u obzir samo dijakritički znakovi;
- na trećem nivou se uzima u obzir samo oblik slova;
- na četvrtom nivou se uzimaju u obzir samo interpunkcijski znakovi.
Poređenje se vrši u nekoliko prolaza: prvo se upoređuju koeficijenti prvog nivoa; ako se težine poklapaju, zatim se ponovo upoređuju težine drugog nivoa; potom, moguće je i trećeg i četvrtog.
Poređenje se završava kada se u stringovima nalaze odgovarajuće jedinice poređenja sa različitim težinama. Stringovi koji imaju jednake težine na svih četiri nivoa smatraju se jednakim među sobom.
Ovaj algoritam (sa mnoštvom dodatnih tehničkih detalja) je dao naziv izveštaju br. 10 — "Unicode Collation Algorithm" (UCA).
U ovom delu ponašanje sortiranja iz našeg primera postaje pomalo jasnije. Dobro bi bilo uporediti ga sa standardom Unikoda.
Za testiranje implementacija UCA postoje posebni , koristeći , koja implementira DUCET. U datoteci težina možete pronaći razne zanimljivosti. Na primer, tamo je redosled pločica mahjonga i evropskog dominosa, kao i redosled boja u špilu karata (simbol 1F000 i dalje). Boje karata su raspoređene prema pravilima bridža — PČBТ, a karte unutar boje — u redosledu T,2,3… K.
Ručno proveravanje tačnosti sortiranja stringova u skladu s DUCET bila bi prilično iscrpljujuća, ali na sreću za nas, postoji uzorna implementacija biblioteke za rad sa Unicode-om — "" (ICU).
Na sajtu ove biblioteke, razvijene u IBM, postoje demonstracione stranice, uključujući i . Unosimo naše testne nizove sa podešavanjima po default-u i, o čudo, dobijamo savršeno srpsko sortiranje.
Abakanov Mihail;maler
Jolkina Ella;kranovka
Ivanov Andrej;majstor
Ivanova Alla;advokatUsput, na sajtu ICU možete pronaći pojašnjenje rada algoritma upoređivanja prilikom obrade znakova interpunkcije. U primerima se ignorišu apostrof i crtica.
Unicode nam je pomogao, ali ćemo morati da potražimo uzroke čudnog ponašanja sort u Linux negde drugde.
Sortiranje u glibc
Brzi pregled izvornog koda alata sort iz GNU Core Utils je pokazao da se u samom alatu lokalizacija svodi na štampanje trenutne vrednosti promenljive LC_COLLATE prilikom pokretanja u režimu debagovanja:
$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rulesUpoređivanje nizova se vrši standardnom funkcijom strcoll, a to znači da se sve zanimljivo nalazi u biblioteci glibc.
Na wiki projekat glibc upoređivanju nizova posvećen . Iz ovog pasusa se može shvatiti da u glibc sortiranje se bazira na već poznatom algoritmu UCA (The Unicode collation algorithm) i/ili na srodnom standardu ISO 14651 (International string ordering and comparison). U vezi sa poslednjim standardom treba primetiti da je na sajtu ISO 14651 službeno objavljen kao javno dostupan, ali odgovarajući link vodi na nepostojeću stranicu. Google prikazuje nekoliko stranica sa linkovima na zvanične sajtove koji nude kupovinu elektronske kopije standarda za stotinu evra, ali na trećoj-četvrtoj strani pretrage naći će se i direktni linkovi na PDF. U celini, standard se praktično ne razlikuje od UCA, ali se čita dosadnije, pošto ne sadrži upečatljive primere nacionalnih osobenosti sortiranja nizova.
Najzanimljivija informacija na wiki bila je poveznica na sa raspravom o implementaciji upoređivanja nizova u glibc. Iz rasprave se može saznati da se u glibc za upoređivanje nizova koristi ISOtabela (CTT), čija se adresa može naći u dodatku A standardu ISO 14651. Između 2000. i 2015. godine ova tabela u glibc nije imala mjerača i prilično se razlikovala (barem izvana) od trenutne verzije standarda. Od 2015. do 2018. godine prilagođavana je novoj verziji tabele i trenutno imate priliku susresti u stvarnom životu i novu verziju tabele (CentOS 8), kao i staru (CentOS 7).
Sada kada imamo sve informacije o algoritmu i pomoćnim tabelama, možemo se vratiti izvornoj problematici i shvatiti kako ispravno sortirati redove u ruskoj lokalizaciji.
ISO 14651/14652
Izvorni kod tabele koja nas zanima CTT u većini distribucija Linux nalazi se u katalogu /usr/share/i18n/locales/. Sama tabela se nalazi u datoteci iso14651_t1_common. Potom se ova datoteka direktivom copy iso14651_t1_common uključuje 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 su uključene u osnovnu instalaciju, ali ako ih nema, moraćete instalirati dodatni paket iz distribucije.
Struktura datoteke iso14651_t1 može delovati strašno opširno, sa nejasnim pravilima za izgradnju imena, ali kada se razumete, sve je prilično jednostavno. Struktura je opisana u standardu ISO 14652, čiju kopiju možete preuzeti sa sajta . Još jedan opis formata datoteke može se pročitati u POSIX od OpenGroup. Kao alternativu čitanju standarda, možete istražiti izvorne tekstove funkcije collate_read u glibc/locale/programs/ld-collate.c.
Struktura datoteke izgleda ovako:
Podrazumevano, simbol se koristi kao eskapni simbol, a kraj reda posle simbola # predstavlja komentar. Ova dva simbola se mogu redefinisati, što je i učinjeno u novoj verziji tabele:
escape_char /
comment_char %U datoteci će se susretati tokeni u formatu <Uxxxx> ili <Uxxxxxxxx> (gde x — heksadecimalna cifra). Ovo heksadecimalno predstavljanje kodnih tačaka Unikoda u kodiranju UCS-4 (UTF-32). Svi ostali elementi u uglastim zagradama (uključujući <Uxxxx_xxxx>, <2> i slične), smatraju se prostim string konstantama, koje nemaju posebnog smisla van konteksta.
String LC_COLLATE nam govori da će uskoro početi podaci koji opisuju poređenje stringova.
Prvo se postavljaju imena za težine u tabeli poređenja i imena za kombinacije simbola. Uopšteno govoreći, dva tipa imena pripadaju dvema različitim entitetima, ali u stvarnoj datoteci su pomešana. Imena težina se postavljaju ključnom rečju collating-symbol (symbol za usporedbu), jer se prilikom usporedbe Unicode znakovi s istim težinama smatraju ekvivalentnim znakovima.
Ukupna dužina sekcije u trenutnoj reviziji datoteke je oko 900 redaka. Izvadio sam primjere iz nekoliko mjesta kako bih pokazao proizvoljnost imena i nekoliko vrsta sintakse.
LC_COLLATE
collating-symbol
collating-symbol
collating-symbol
collating-symbol
...
collating-symbol
collating-symbol
collating-symbol
...
collating-symbol ..
collating-symbol % Jamčena najveća vrijednost simbola. Držite na kraju ove liste
...
collating-element from ""
collating-element from ""- collating-symbol registrira redak OSMANYA u tablici imena težina
- collating-symbol .. registrira niz imenâ, koji se sastoji od prefiksa S i heksadecimalnog numeričkog sufiksa iz 1D000 do 1D35F.
- FFFF u collating-symbol izgleda kao veliko bezuslovno cijelo u heksadecimalnom brojevnom sistemu, ali <SFFFF> to je samo ime, koje bi moglo izgledati kao <VERYBIGVAL>
- ime <U0413> znači kodnu tačku u kodiranju UCS-4
- collating-element from "" registrira novo ime za par Unicode tačaka.
Kada su imena težina definirana, postavljaju se same težine. Budući da su u usporedbi važni samo odnosi više-manje, težine se postavljaju jednostavnom sekvencom nabrajanja imena. Prvo se nabraja "lakše" težine, a zatim "teže". Podsjećam da se svakom Unicode znaku dodjeljuju četiri različite težine. Ovdje su svedene u jedinstvenu sortiranu sekvencu. Teoretski, bilo koje simboličko ime može se koristiti na bilo kojem od četiri nivoa, ali komentari sugeriraju da programeri su mentalno podijelili imena po nivoima.
% Simbolički dodjela težina
% Dodjela težina treće razine
...
% Dodjela težina druge razine
% KOMBINE RAČUN <
% KOMBINE ZAREZ IZNAD
% KOMBINE OBRNUTI ZAREZ IZNAD
...
% Dodjela težina prve razine
% HORIZONTALNA TABULACIJA
% NOVI RED
% VERTIKALNA TABULACIJA
...
% MALO SLOVO DE NA ĆIRILICI
% MALO SLOVO KOMI DE NA ĆIRILICI
% MALO SLOVO DJE NA ĆIRILICI
% MALO SLOVO KOMI DJE NA ĆIRILICI
% MALO SLOVO GJE NA ĆIRILICI
% MALO SLOVO ZE SA SLOŽENOM NA ĆIRILICI
% MALO SLOVO IE NA ĆIRILICI
% MALO SLOVO IE SA BREVE NA ĆIRILICI
% MALO SLOVO UKRAJINSKO IE NA ĆIRILICI
% MALO SLOVO ZHE NA ĆIRILICINaposlije, sama tabela težina.
Sekcija težina je zatvorena u redove sa ključnim riječima order_start i order_end. Dodatni parametri order_start određuju u kojem pravcu se pregleda redove na svakom nivou poređenja. Po defaultu se koristi parametar forward. Telo sekcije se sastoji od redova koji sadrže kod znaka i četiri njegove težine. Kod znaka može biti predstavljen samim znakom, kodnom tačkom ili simboličkim imenom koje je prethodno definirano. Težine takođe mogu biti određene simboličkim imenima, kodnim tačkama ili samim znakovima. Ako se koriste kodne tačke ili znakovi, njihova težina odgovara numeričkoj vrednosti kodne tačke (poziciji u Unicode tabeli). Znakovi koji nisu eksplicitno navedeni (kako ja razumem) smatraju se pridruženima u tabeli sa primarnom težinom koja odgovara poziciji u Unicode tabeli. Posebna vrednost težine IGNORE znači da se na odgovarajućem nivou poređenja ovaj znak ignoriše.
Za demonstraciju strukture težina odabrao sam tri prilično očigledna fragmenta:
- znakovi koji se potpuno ignorišu
- znakovi ekvivalentni broju tri na prva dva nivoa
- početak ćiriličnog alfabeta, koji ne sadrži dijakritičke znakove, a stoga se sortira, uglavnom, po prvom i trećem nivou.
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_endSada se možemo ponovo vratiti na sortiranje primera iz početka članka. Nevolja se krije upravo u ovom delu tabele težina:
IGNORE;IGNORE;IGNORE % SPACE
IGNORE;IGNORE;IGNORE % EXCLAMATION MARK
IGNORE;IGNORE;IGNORE % QUOTATION MARK
...Jasno je da u ovoj tabeli znakovi interpunkcije dolaze iz tabele ASCII (uključujući razmak) pri poređenju stringova se praktično uvek ignoriše. Izuzetak čine samo stringovi koji se poklapaju u svemu osim u znakovima interpunkcije koji se pojavljuju na istim pozicijama. Stringovi iz mog primera (nakon sortiranja) za algoritam poređenja izgledaju ovako:
Abakanov Mihail maljar
Jolkina Ellakranovščica
Ivanova Alla maljar
Ivanov Andrej sestričUzimajući u obzir da u tabeli težina velika slova u ruskom jeziku dolaze posle malih (na trećem nivou <CAP> teži nego <MIN>), sortiranje izgleda apsolutno ispravno.
Pri postavljanju promenljive LC_COLLATE=C učitava se posebna tabela koja definiše bajt-po-bajt poređenje
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'
};Pošto u Unicode-u kodna tačka Ё dolazi pre А, tako se i stringovi sortiraju u skladu sa tim.
Tekstualne i binarne tabele
Očigledno je da je poređenje stringova veoma česta operacija, a analiza tabele CTT je prilično skupa procedura. Da bi se optimizovao pristup tabeli, ona se kompajlira u binarni oblik pomoću komande localedef.
Tim localedef primi kao parametre datoteku sa tabelom nacionalnih osobina (opciju -i), u kojoj su svi simboli predstavljeni Unicode tačkama, i datoteku usklađenja tačaka Unicode sa simbolima specifične kodiranja (opciju -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 je ime lokaliteta ime podfoldera u /usr/lib/locale/. U ovom podfolderu se čuvaju binarne datoteke LC_COLLATE, LC_CTYPE, LC_TIME itd. Datoteka LC_IDENTIFICATION sadrži formalno ime lokaliteta (koje može da se razlikuje od imena foldera) i komentare.
Savremeni format podrazumeva čuvanje svih lokaliteta u jedinstvenom arhivu /usr/lib/locale/locale-archive, koji se mapira u virtuelnu memoriju svih procesa koji ga koriste glibcIme lokaliteta u savremenom formatu podliježe određenoj kanonizaciji — u nazivima kodiranja ostaju samo cifre i slova, koja su prebačena u mala slova. Tako ru_RU.KOI8-R, biće sačuvano kao ru_RU.koi8r.
Ulazne datoteke se traže u trenutnom katalogu, kao i u katalozima /usr/share/i18n/locales/ i /usr/share/i18n/charmaps/ za datoteke CTT i datoteke kodiranja u skladu s tim.
Na primjer, komandna
localedef -i ru_RU -f MAC-CYRILLIC ru_RU.MAC-CYRILLICkompiliš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 ru_RU.maccyrillic
Ako se postavi promenljiva LANG=en_US.UTF-8 onda glibc će tražiti binarne datoteke lokaliteta u sledećem redosledu datoteka i kataloga:
/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 savremenom formatu, prioritet se daje savremenom.
Popis skompilovanih lokaliteta može se pregledati komandnom locale -a.
Priprema svoje tabele poređenja
Sada, opremljeni znanjem, možete stvoriti svoju idealnu tabelu poređenja stringova. Ova tabela bi trebala ispravno da poredi ruska slova, uključujući slovo Ё, i pritom uzimajući u obzir interpunkcijske znakove u skladu s tabelom ASCII.
Proces pripreme vlastite tabele sortiranja sastoji se od dva koraka: uređivanje tabele težina i kompajliranje u binarni oblik komandom localedef.
Da bi se tabela poređenja mogla prilagoditi uz minimalne troškove uredničkog rada, u formatu ISO 14652 predviđene su sekcije prilagođavanja težina već postojeće tabele. Sekcija počinje ključnom riječi reorder-after i označavanjem pozicije, nakon koje se izvršava zamjena. Sekciju završava red reorder-end. Ako je potrebno ispraviti više delova tabele, kreira se po jedna sekcija za svaki takav deo.
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 deo LC_COLLATE u ru_RU. Nove verzije datoteka su potpuno kompatibilne s mojom verzijom glibc. Ako želite koristiti stare verzije datoteka, biće potrebno da promenite simbolička imena i mesto od kojeg počinje zamena u tabeli.
LC_COLLATE
% Kopirajte šablon iz ISO/IEC 14651
kopiraj "iso14651_t1"
preuredi-nakon
;;; % PROSTOR
;;; % UZVIK
;;; % NAVODNIK
...
;;; % DESNI ZAVRŠNI ZAVRŠETAK
;;; % TILDA
preuredi-kraj
KRAJ LC_COLLATEZapravo, trebali bismo promijeniti polja u LC_IDENTIFICATION tako da upućuju na lokalitet bs_BA, ali u mom primjeru to nije bilo potrebno, jer sam isključio with pretragu lokaliteta arhiva locale-archive.
Kako bi localedef radio sam s datotekama u svom direktoriju putem varijable I18NPATH možete dodati dodatni direktorij za pretraživanje ulaznih datoteka, a direktorij za spremanje binarnih datoteka možete navesti kao putanju sa kose crte:
$> I18NPATH=~/.local/share/i18n localedef -i bs_BA -f UTF-8 ~/.local/lib/locale/bs_BA.UTF-8POSIX podrazumijeva da LANG možete pisati apsolutne putanje do direktorija s datotekama lokaliteta, počinjući od kose crte, ali glibc u Linux sve putanje se smatraju od osnovnog direktorija, koji se može predefinirati putem varijable LOCPATH. Nakon postavljanja LOCPATH=~/.local/lib/locale/ sve datoteke koje se odnose na lokalizaciju će se tražiti samo u mom direktoriju. Arhiv lokaliteta pri postavljenoj varijabli LOCPATH se ignoriše.
Evo ga, odlučujući test:
$> LANG=bs_BA.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mihail;farbač
Jelkinan Ella;crnač
Ivanov Andrej;bravar
Ivanova Alla;advokatUra! Uspjeli smo!
Rad na greškama
Već sam odgovorio na pitanja o sortiranju nizova postavljenim na početku, ali ostalo je još nekoliko pitanja o greškama — vidljivim i nevidljivim.
Vratimo se izvornoj zadatku.
I program sort i program join koriste iste funkcije za usporedbu nizova iz glibc. Kako je to moguće da join javila grešku pri sortiranju nizova, sortir anim komandnom sort u lokalitetu en_US.UTF-8? Ответ прост: sort uspoređuje cijeli niz, dok join uspoređuje samo ključ, koji je po defaultu početak niza do prvog razmaknog simbol.
Lokalitet "C" garantira da će u sortiranim nizovima inicijalne podnizove do prvog razmaka također biti sortirani, ali to samo prikriva grešku. Možemo pronaći takve podatke (ljudi s istim prezimenima, ali različitim imenima), koji bez poruke o grešci bi dali pogrešan rezultat pri spajanju datoteka. Ako želimo da join Kada se spajaju redovi datoteka prema FIO, ispravan način bi bio da se jasno odredi separator polja i sortira prema ključnom polju, a ne prema cijelom redu. U tom slučaju će spajanje proći ispravno, a u nijednoj lokalnoj verziji 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 > resultPrimjer uspješnog izvršavanja u kodiranju CP1251 sadrži još jednu grešku. Naime, u svim poznatim distribucijama Linux nedostaje kompajlirana lokalizacija ru_RU.CP1251. Ako kompajlirana lokalizacija nije pronađena, tada sort nečujno koristi bajtno poređenje, što smo i primijetili.
Usput, postoji još jedan mali bug vezan uz nedostupnost kompajliranih lokalizacija. Komanda LOCPATH=/tmp locale -a dati će popis svih lokalizacija u locale-archive, ali uz postavljenu varijablu LOCPATH za sve programe (uključujući i sam locale) te 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 comparisonZaključak
Ako ste programer koji je navikao da smatra da su redovi skup bajtova, onda je vaš izbor LC_COLLATE=C.
Ako ste lingvista ili sastavljač rečnika, bolje je da kompajlirate svoju lokalizaciju.
Ako ste običan korisnik, dovoljno je da se naviknete na to da komanda ls -a daje datoteke koje počinju tačkom, pomešane sa datotekama koje počinju slovom, dok Midnight Commander, koji koristi svoje unutrašnje funkcije za sortiranje imena, stavlja datoteke koje počinju tačkom na početak spiska.
Linkovi
Izvor: habr.com
