Uvod

Sve je počelo sa kratkom skriptom koja je trebala da kombinuje informacije o adresi i-mejl zaposleni dobijeni sa liste korisnika mailing liste, sa pozicijama zaposlenih iz baze podataka HR odjela. Obje liste su izvezene u Unicode tekstualne datoteke UTF-8 i sačuvan sa završetcima Unix linija.

Sadržaj mail.txt

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

Sadržaj buhg.txt

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

Da bi se spojili, fajlovi su sortirani Unix komandom sudbina i predati na ulaz Unix programa Pridruži se, koji neočekivano nije uspio 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: Иванов Андрей;слесарь

Gledanje rezultata sortiranja očima pokazalo je da je, generalno gledano, sortiranje ispravno, ali u slučaju podudarnosti muških i ženskih prezimena, ženska dolaze ispred muških:

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

Izgleda kao greška u sortiranju u Unicode-u ili kao manifestacija feminizma u algoritmu sortiranja. Prvi je, naravno, uvjerljiviji.

Odložimo to za sada Pridruži se i fokusirati se na sudbina. Pokušajmo riješiti problem pomoću naučnog bockanja. Prvo, promijenimo lokalizaciju iz en_US na ru_RU. Za sortiranje bi bilo dovoljno postaviti varijablu okruženja LC_COLLATE, ali nećemo gubiti vrijeme na sitnice:

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

Ništa se nije promijenilo.

Pokušajmo prekodirati datoteke u jednobajtno kodiranje:

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

Opet se ništa nije promijenilo.

Ne možete ništa da uradite, moraćete da tražite rešenje na internetu. Ne postoji ništa direktno o ruskim prezimenima, ali postoje pitanja o drugim neobičnostima sortiranja. Na primjer, evo problema: unix sortiranje tretira '-' (crticu) znakove kao nevidljive. Ukratko, nizovi "a-b", "aa", "ac" su sortirani kao "aa", "a-b", "ac".

Odgovor je svuda standardan: koristite lokalizaciju programera "C" i bićeš srećna. Pokusajmo:

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

Nešto se promijenilo. Ivanovci su se postrojili u ispravnom redosledu, iako je Yolkina negde okliznula. Vratimo se originalnom problemu:

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

Radio je bez grešaka, kao što je internet obećavao. I to uprkos Yolkini u prvoj liniji.

Čini se da je problem riješen, ali za svaki slučaj, pokušajmo s drugim ruskim kodiranjem - Windows CP1251:

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

Rezultat sortiranja, začudo, poklopit će se s lokalitetom "C", i cijeli primjer, shodno tome, radi bez grešaka. Neka vrsta misticizma.

Ne volim misticizam u programiranju jer obično maskira greške. Moraćemo ozbiljno da ispitamo kako to funkcioniše. sudbina i na šta utiče? LC_COLLATE .

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

zašto su ženska prezimena pogrešno sortirana?
zašto LANG=ru_RU.CP1251 ispostavilo se kao ekvivalentno LANG=C
zašto u sudbina и Pridruži se različite ideje o redoslijedu sortiranih nizova
zašto u svim mojim primjerima ima grešaka?
konačno kako sortirati nizove po svom ukusu

Sortiranje u Unicode-u

Prva stanica će biti tehnički izvještaj br. 10 pod naslovom Unicode algoritam za usporedbu online unicode.org. Izvještaj sadrži mnogo tehničkih detalja, pa mi dozvolite da dam kratak sažetak glavnih ideja.

sravnjivanje — „upoređivanje“ stringova je osnova svakog algoritma za sortiranje. Sami algoritmi se mogu razlikovati ("bubble", "spajanje", "brzo"), ali svi će koristiti poređenje para nizova da bi odredili redoslijed u kojem se pojavljuju.

Sortiranje nizova na prirodnom jeziku je prilično složen problem. Čak i kod najjednostavnijih jednobajtnih kodiranja, redoslijed slova u abecedi, čak i na neki način različit od engleske latinice, više se neće podudarati s redoslijedom numeričkih vrijednosti kojima su ova slova kodirana. Dakle, u njemačkom alfabetu slovo Ö stoji između О и P, i u kodiranju CP850 ona je između ÿ и Ü.

Možete pokušati da se apstrahujete od određenog kodiranja i razmotrite “idealna” slova koja su raspoređena nekim redosledom, kao što je to učinjeno u Unicode-u. Kodiranja UTF8, UTF16 ili jednobajt KOI8-R (ako je potreban ograničeni podskup Unicodea) će dati različite numeričke prikaze slova, ali će se odnositi na iste elemente osnovne tabele.

Ispostavilo se da čak i ako napravimo tabelu simbola od nule, nećemo moći da joj dodelimo univerzalni redosled simbola. U različitim nacionalnim alfabetima koji koriste ista slova, redoslijed ovih slova može se razlikovati. Na primjer, na francuskom Æ će se smatrati ligaturom i sortirati kao niz AE. Na norveškom Æ će biti posebno slovo, koje se nalazi iza Z. Inače, pored ligatura poput Æ Postoje slova ispisana sa nekoliko simbola. Dakle, u češkoj abecedi postoji slovo Ch, koji stoji između H и I.

Osim razlika u alfabetima, postoje i druge nacionalne tradicije koje utječu na sortiranje. Posebno se postavlja pitanje: kojim bi se redom riječi koje se sastoje od velikih i malih slova trebale pojaviti u rječniku? Na sortiranje može uticati i upotreba znakova interpunkcije. Na španskom se obrnuti upitnik koristi na početku upitne rečenice (Volite li muziku?). U ovom slučaju je očigledno da upitne rečenice ne treba grupirati u poseban niz izvan abecede, već kako razvrstati redove sa drugim znacima interpunkcije?

Neću se zadržavati na sortiranju nizova na jezicima koji se jako razlikuju od evropskih. Imajte na umu da se u jezicima sa smjerom pisanja zdesna nalijevo ili odozgo prema dolje, znakovi u redovima najvjerovatnije pohranjuju u redoslijedu čitanja, a čak i neabecedni sistemi pisanja imaju svoje načine redanja redova znak po znak . Na primjer, hijeroglifi se mogu poredati po stilu (Tasteri kineskih znakova) ili izgovorom. Da budem iskren, nemam pojma kako bi emotikoni trebali biti raspoređeni, ali možete smisliti nešto i za njih.

Na osnovu gore navedenih karakteristika, formulisani su osnovni zahtevi za poređenje nizova na osnovu Unicode tabela:

poređenje stringova ne zavisi od položaja znakova u tablici kodova;
nizovi znakova koji formiraju jedan znak svode se na kanonski oblik (A + gornji krug je isti kao Å);
Kada se porede nizovi, karakter se razmatra u kontekstu niza i, ako je potrebno, kombinuje se sa svojim susjedima u jednu jedinicu poređenja (Ch na češkom) ili je podijeljen na nekoliko (Æ na francuskom);
sve nacionalne karakteristike (abeceda, velika/mala slova, interpunkcija, redoslijed pisanja) moraju biti konfigurisane do ručnog dodjeljivanja redoslijeda (emoji);
poređenje je važno ne samo za sortiranje, već i na mnogim drugim mjestima, na primjer za određivanje raspona redova (zamjena {A... z} u bash);
poređenje treba obaviti prilično brzo.

Osim toga, autori izvještaja formulirali su svojstva usporedbe na koja se programeri algoritama ne bi trebali oslanjati:

algoritam poređenja ne bi trebao zahtijevati poseban skup znakova za svaki jezik (ruski i ukrajinski jezici dijele većinu ćiriličnih znakova);
poređenje ne treba da se oslanja na redosled znakova u Unicode tabelama;
težina stringa ne bi trebala biti atribut stringa, budući da isti niz u različitim kulturnim kontekstima može imati različite težine;
težine redova se mogu promijeniti prilikom spajanja ili razdvajanja (od x < y to ne sledi xz < yz);
različiti nizovi koji imaju iste težine smatraju se jednakim sa stanovišta algoritma za sortiranje. Uvođenje dodatnog reda takvih nizova je moguće, ali to može pogoršati performanse;
Tokom ponovljenog sortiranja, redovi sa istim težinama mogu se zamijeniti. Robusnost je svojstvo specifičnog algoritma za sortiranje, a ne svojstvo algoritma poređenja nizova (pogledajte prethodni pasus);
Pravila sortiranja se mogu promijeniti tokom vremena kako se kulturna tradicija usavršava/mijenja.

Takođe je propisano da algoritam poređenja ne zna ništa o semantici nizova koji se obrađuju. Dakle, nizove koji se sastoje samo od cifara ne treba porediti kao brojeve, a u listama engleskih naziva članak (Beatles, The).

Kako bi se zadovoljili svi ovi zahtjevi, predlaže se algoritam za sortiranje tablica na više nivoa (zapravo na četiri nivoa).

Prethodno su znakovi u nizu svedeni na kanonski oblik i grupirani u jedinice poređenja. Svakoj jedinici poređenja je dodijeljeno nekoliko pondera koji odgovaraju nekoliko nivoa poređenja. Težine jedinica poređenja su elementi uređenih skupova (u ovom slučaju cijeli brojevi) koji se mogu porediti za više ili manje. Posebno značenje IGNORED (0x0) znači da na odgovarajućem nivou poređenja ova jedinica nije uključena u poređenje. Poređenje nizova se može ponoviti nekoliko puta, koristeći pondere odgovarajućih nivoa. Na svakom nivou, težine jedinica poređenja dva reda se uzastopno porede jedna s drugom.

U različitim implementacijama algoritma za različite nacionalne tradicije, vrijednosti koeficijenata mogu se razlikovati, ali Unicode standard uključuje osnovnu tablicu težina - "Zadana tablica Unicode Collation Element" (DUCET). Želio bih napomenuti da postavljanje varijable LC_COLLATE je zapravo indikacija odabira tabele težine u funkciji poređenja nizova.

Ponderi koeficijenti DUCET raspoređeni na sljedeći način:

na prvom nivou, sva slova se svode na isto slovo, dijakritici se odbacuju, znaci interpunkcije (ne svi) se zanemaruju;
na drugom nivou uzimaju se u obzir samo dijakritici;
na trećem nivou uzima se u obzir samo slučaj;
na četvrtom nivou uzimaju se u obzir samo znaci interpunkcije.

Poređenje se odvija u nekoliko prolaza: prvo se upoređuju koeficijenti prvog nivoa; ako se ponderi poklapaju, onda se vrši ponovljeno poređenje sa ponderima drugog nivoa; onda možda treći i četvrti.

Poređenje se završava kada redovi sadrže odgovarajuće jedinice poređenja s različitim težinama. Redovi koji imaju jednaku težinu na sva četiri nivoa smatraju se jednakim jedni drugima.

Ovaj algoritam (sa gomilom dodatnih tehničkih detalja) dao je naziv izvještaju br. 10 - "Unicode Collation Algoritam" (ACU).

Ovdje ponašanje sortiranja iz našeg primjera postaje malo jasnije. Bilo bi lijepo uporediti ga sa Unicode standardom.

Za testiranje implementacija ACU postoji poseban kviz, koristeći težina fajla, implementacija DUCET. Možete pronaći razne smiješne stvari u datoteci vage. Na primjer, postoji redoslijed mahjonga i evropskih domina, kao i red odijela u špilu karata (simbol 1F000 i dalje). Boje karata su postavljene prema pravilima bridža - PCBT, a karte u boji su u nizu T, 2,3, XNUMX... K.

Ručna provjera da li su redovi pravilno sortirani prema DUCET bilo bi prilično zamorno, ali, na našu sreću, postoji primjerna implementacija biblioteke za rad sa Unicode-om - "Međunarodne komponente za Unicode"(\ TICU).

Na web stranici ove biblioteke, razvijenoj god IBM, postoje demo stranice, uključujući stranica algoritma za poređenje nizova. Ulazimo u naše testne linije sa zadanim postavkama i, eto, dobijamo savršeno rusko sortiranje.

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

Usput, web stranica ICU Možete pronaći pojašnjenje algoritma poređenja prilikom obrade znakova interpunkcije. U primjerima Često postavljana pitanja o slaganju apostrof i crtica se zanemaruju.

Unicode nam je pomogao, ali potražite razloge za čudno ponašanje sudbina в Linux moraće da ode negde drugde.

Sortiranje u glibc

Brzi pregled izvornih kodova uslužnih programa sudbina из GNU Core Utils pokazao da se u samom uslužnom programu lokalizacija svodi na ispis trenutne vrijednosti varijable LC_COLLATE kada radi u načinu za otklanjanje grešaka:

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

Poređenja nizova se izvode pomoću standardne funkcije strcoll, što znači da se sve zanimljivo nalazi u biblioteci glibc.

U Wiki projekat glibc posvećeno poređenju stringova jedan pasus. Iz ovog pasusa se može shvatiti da u glibc sortiranje se zasniva na algoritmu koji nam je već poznat ACU (Unicode algoritam za usporedbu) i/ili na standardu koji mu je blizak ISO 14651 (Međunarodni poredak i poređenje nizova). Što se tiče najnovijeg standarda, treba napomenuti da na sajtu standards.iso.org ISO 14651 zvanično proglašen javno dostupnim, ali odgovarajući link vodi na nepostojeću stranicu. Gugl vraća nekoliko stranica sa linkovima ka zvaničnim sajtovima koji nude kupovinu elektronske kopije standarda za sto evra, ali na trećoj ili četvrtoj stranici rezultata pretrage nalaze se i direktni linkovi na PDF. Općenito, standard se praktički ne razlikuje od ACU, ali je dosadniji za čitanje jer ne sadrži jasne primjere nacionalnih karakteristika sortiranja nizova.

Najzanimljivije informacije o Wiki postojala je veza za bug tracker uz raspravu o implementaciji poređenja nizova u glibc. Iz diskusije se to može saznati glibc koristi se za poređenje nizova ISOlični sto Zajednička tablica predložaka (CTT), čija se adresa može pronaći u prijavi A standard ISO 14651. Između 2000. i 2015. godine ova tabela u glibc nije imao održavaoca i bio je prilično drugačiji (barem eksterno) od trenutne verzije standarda. Od 2015. do 2018. odvijala se adaptacija na novu verziju tablice, a sada imate priliku upoznati u stvarnom životu novu verziju tablice (CentOS 8), i stari (CentOS 7).

Sada kada imamo sve informacije o algoritmu i pomoćnim tabelama, možemo se vratiti na izvorni problem i razumjeti kako pravilno sortirati nizove u ruskom lokalu.

ISO 14651 / 14652

Izvorni kod tabele koja nas zanima CTT na većini distribucija Linux nalazi se u katalogu /usr/share/i18n/locales/. Sama tabela je u datoteci iso14651_t1_common. Onda je ovo direktiva datoteke kopija iso14651_t1_common uključeno u fajl iso14651_t1, koji je zauzvrat uključen u nacionalne datoteke, uključujući en_US и ru_RU. Na većini distribucija Linux svi izvorni fajlovi su uključeni u osnovnu instalaciju, ali ako nisu prisutni, moraćete da instalirate dodatni paket iz distribucije.

Struktura fajla iso14651_t1 može izgledati strašno opširno, s neočiglednim pravilima za građenje imena, ali ako pogledate, sve je prilično jednostavno. Struktura je opisana u standardu ISO 14652, čija se kopija može preuzeti sa web stranice open-std.org. Drugi opis formata datoteke može se pročitati specifikacije POSIX iz OpenGroup. Kao alternativu čitanju standarda, možete proučiti izvorni kod funkcije collate_read в glibc/locale/programs/ld-collate.c.

Struktura fajla izgleda ovako:

Podrazumevano, znak se koristi kao izlazni znak, a kraj reda nakon znaka # je komentar. Oba simbola se mogu redefinisati, što je i urađeno u novoj verziji tabele:

escape_char /
comment_char %

Datoteka će sadržavati tokene u formatu ili (Gdje x - heksadecimalna cifra). Ovo je heksadecimalni prikaz Unicode kodnih tačaka u kodiranju UCS-4 (UTF-32). Svi ostali elementi u ugaonim zagradama (uključujući , <2> i slično) se smatraju jednostavnim string konstantama koje imaju malo značenja izvan konteksta.

Gudački LC_COLLATE govori nam da slijedeći počinju podaci koji opisuju poređenje nizova.

Prvo, nazivi su specificirani za težine u tabeli poređenja i imena za kombinacije simbola. Uopšteno govoreći, dvije vrste imena pripadaju dva različita entiteta, ali u stvarnom fajlu su pomiješane. Imena težina su specificirana ključnom riječi sporedni simbol (znak za poređenje) jer će se prilikom poređenja Unicode znakovi koji imaju iste težine smatrati ekvivalentnim znakovima.

Ukupna dužina sekcije u trenutnoj reviziji fajla je oko 900 redova. Izvukao sam primjere sa nekoliko mjesta da pokažem proizvoljnost imena i nekoliko tipova sintakse.

LC_COLLATE

collating-symbol <RES-1>
collating-symbol <BLK>
collating-symbol <MIN>
collating-symbol <WIDE>
...
collating-symbol <ARABIC>
collating-symbol <ETHPC>
collating-symbol <OSMANYA>
...
collating-symbol <S1D000>..<S1D35F>
collating-symbol <SFFFF> % Guaranteed largest symbol value. Keep at end of this list
...
collating-element <U0413_0301> from "<U0413><U0301>"
collating-element <U0413_0341> from "<U0413><U0341>"

sporedni-simbol evidentira string OSMANYA u tabeli naziva skala
sporedni-simbol .. registruje niz imena koji se sastoji od prefiksa S i heksadecimalni numerički nastavak iz 1D000 do 1D35F.
FFFF в sporedni-simbol izgleda kao veliki neoznačeni cijeli broj u heksadecimalnom, ali to je samo ime koje bi moglo izgledati
Ime znači kodnu tačku u kodiranju UCS-4
element za slaganje iz "" registruje novo ime za par Unicode tačaka.

Kada se definišu nazivi pondera, specificiraju se stvarne težine. Budući da su samo relacije veće od manje bitne u poređenju, težine se određuju jednostavnim nizom imena na listi. Prvo su navedene “lakše” težine, a zatim one “teže”. Dozvolite mi da vas podsjetim da su svakom Unicode znaku dodijeljene četiri različite težine. Ovdje se kombinuju u jedan uređeni niz. U teoriji, bilo koje simbolično ime može se koristiti na bilo kojem od četiri nivoa, ali komentari ukazuju na to da programeri mentalno razdvajaju imena u nivoe.

% Symbolic weight assignments

% Third-level weight assignments
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Second-level weight assignments
<BASE>
<LOWLINE> % COMBINING LOW LINE
<PSILI> % COMBINING COMMA ABOVE
<DASIA> % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
<S0009> % HORIZONTAL TABULATION 
<S000A> % LINE FEED
<S000B> % VERTICAL TABULATION
...
<S0434> % CYRILLIC SMALL LETTER DE
<S0501> % CYRILLIC SMALL LETTER KOMI DE
<S0452> % CYRILLIC SMALL LETTER DJE
<S0503> % CYRILLIC SMALL LETTER KOMI DJE
<S0453> % CYRILLIC SMALL LETTER GJE
<S0499> % CYRILLIC SMALL LETTER ZE WITH DESCENDER
<S0435> % CYRILLIC SMALL LETTER IE
<S04D7> % CYRILLIC SMALL LETTER IE WITH BREVE
<S0454> % CYRILLIC SMALL LETTER UKRAINIAN IE
<S0436> % CYRILLIC SMALL LETTER ZHE

Konačno, tabela stvarne težine.

Odjeljak težine je zatvoren u redovima ključnih riječi order_start и order_end. Dodatne opcije order_start odrediti u kom smjeru se redovi skeniraju na svakom nivou poređenja. Podrazumevana postavka je napred. Tijelo odjeljka se sastoji od redova koji sadrže kod simbola i njegove četiri težine. Šifra karaktera može biti predstavljena samim znakom, kodnom točkom ili simboličkim imenom koje je prethodno definirano. Težine se također mogu dati simboličkim imenima, kodnim tačkama ili samim simbolima. Ako se koriste kodne tačke ili znakovi, njihova težina je ista kao i numerička vrijednost kodne točke (pozicija u Unicode tabeli). Znakovi koji nisu eksplicitno specificirani (kako ja razumijem) smatraju se dodijeljenim tablici s primarnom težinom koja odgovara poziciji u Unicode tablici. Posebna vrijednost težine IGNORED znači da se simbol zanemaruje na odgovarajućem nivou poređenja.

Da bih demonstrirao strukturu vage, odabrao sam tri prilično očigledna fragmenta:

znakova koji se potpuno zanemaruju
simboli ekvivalentni broju tri u prva dva nivoa
početak ćirilice, koja ne sadrži dijakritičke znakove, pa je raspoređena uglavnom po prvom i trećem nivou.

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

Sada se možete vratiti na sortiranje primjera s početka članka. Zasjeda se nalazi u ovom dijelu tabele utega:

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

Vidi se da su u ovoj tabeli znakovi interpunkcije iz tabele ASCII (uključujući razmak) se gotovo uvijek zanemaruje prilikom upoređivanja stringova. Jedini izuzetak su redovi koji se podudaraju u svemu osim u znakovima interpunkcije koji se nalaze na podudarnim pozicijama. Redovi iz mog primjera (nakon sortiranja) za algoritam poređenja izgledaju ovako:

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

S obzirom da u tabeli skala velika slova u ruskom dolaze iza malih slova (na trećem nivou teže od ), sortiranje izgleda potpuno ispravno.

Prilikom postavljanja varijable LC_COLLATE=C učitava se posebna tabela koja specificira poređenje 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'xfe', L'xff'
};

Pošto u Unicode-u kodna tačka Ë dolazi ispred A, nizovi se sortiraju u skladu sa tim.

Tekstualne i binarne tabele

Očigledno, poređenje stringova je izuzetno uobičajena operacija i raščlanjivanje tablice CTT prilično skupa procedura. Da bi se optimizirao pristup tabeli, ona se kompajlira u binarni oblik pomoću naredbe localdef.

tim localdef prihvata kao parametre datoteku sa tabelom nacionalnih karakteristika (opcija -i), u kojem su svi znakovi predstavljeni Unicode točkama, i datoteka korespondencije između Unicode tačaka i znakova određenog kodiranja (opcija -f). Kao rezultat rada, kreiraju se binarne datoteke za lokalizaciju s imenom navedenim u posljednjem parametru.

glibc podržava dva binarna formata datoteka: "tradicionalni" i "moderni".

Tradicionalni format znači da je naziv lokalizacije ime poddirektorija u /usr/lib/locale/. Ovaj poddirektorij pohranjuje binarne datoteke LC_COLLATE, LC_CTYPE, LC_TIME i tako dalje. File LC_IDENTIFICATION sadrži formalni naziv lokaliteta (koji se može razlikovati od imena direktorija) i komentare.

Moderni format uključuje pohranjivanje svih lokacija u jednu arhivu /usr/lib/locale/locale-archive, koji je mapiran u virtuelnu memoriju svih procesa koji koriste glibc. Naziv lokaliteta u modernom formatu podliježe određenoj kanonizaciji - u nazivima kodiranja ostaju samo brojevi i slova svedena na mala slova. Dakle ru_RU.KOI8-R, biće sačuvan kao ru_RU.koi8r.

Ulazni fajlovi se traže u trenutnom direktorijumu, kao iu direktorijumima /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ za fajlove CTT i datoteke za kodiranje, respektivno.

Na primjer, naredba

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

će kompajlirati fajl /usr/share/i18n/locales/ru_RU koristeći datoteku za kodiranje /usr/share/i18n/charmaps/MAC-CYRILLIC.gz i sačuvaj rezultat u /usr/lib/locale/locale-archive pod imenom ru_RU.maccyrillic

Ako postavite varijablu LANG = hr_US.UTF-8 onda glibc će tražiti binarne standarde u sljedećem nizu datoteka i direktorija:

/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 lokalna lokacija pojavljuje iu tradicionalnom iu modernom formatu, prioritet se daje modernom.

Možete pogledati listu kompajliranih lokalizacija pomoću naredbe locale -a.

Priprema vaše uporedne tabele

Sada, naoružani znanjem, možete kreirati svoju vlastitu idealnu tablicu za poređenje žica. Ova tabela treba pravilno uporediti ruska slova, uključujući slovo Ë, i istovremeno uzeti u obzir znakove interpunkcije u skladu s tablicom ASCII.

Proces pripreme vlastite tablice za sortiranje sastoji se od dvije faze: uređivanje tabele težina i prevođenje u binarni oblik pomoću naredbe localdef.

Kako bi se uporedna tabela prilagodila uz minimalne troškove uređivanja, u formatu ISO 14652 Predviđene su sekcije za podešavanje težine postojećeg stola. Odjeljak počinje ključnom riječi reorder-after i označavajući položaj nakon kojeg se vrši zamjena. Odjeljak se završava linijom reorder-end. Ako je potrebno ispraviti nekoliko sekcija tabele, onda se kreira odeljak za svaki takav odeljak.

Kopirao sam nove verzije fajlova iso14651_t1_common и ru_RU iz spremišta glibc u moj početni direktorij ~/.local/share/i18n/locales/ i malo uredio odjeljak LC_COLLATE в ru_RU. Nove verzije datoteka su potpuno kompatibilne s mojom verzijom glibc. Ako želite koristiti starije verzije datoteka, morat ćete promijeniti simbolička imena i mjesto gdje počinje zamjena u tabeli.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

U stvari, bilo bi potrebno promijeniti polja u LC_IDENTIFICATION tako da ukazuju na lokaciju ru_MY, ali u mom primjeru to nije bilo potrebno, budući da sam arhivu isključio iz pretraživanja lokaliteta locale-archive.

da localdef radio sa fajlovima u mom folderu preko varijable I18NPATH Možete dodati dodatni direktorij za traženje ulaznih datoteka, a direktorij za spremanje binarnih datoteka može se navesti kao staza sa kosim crtama:

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

POSIX pretpostavlja da u JEZIK možete pisati apsolutne putanje do direktorija s datotekama lokalizacije, počevši s kosom crtom naprijed, ali glibc в Linux sve staze se broje iz osnovnog direktorija, koji se može nadjačati kroz varijablu LOCPATH... Nakon instalacije LOCPATH=~/.local/lib/locale/ sve datoteke vezane za lokalizaciju će se pretraživati samo u mom folderu. Arhiva lokalizacija sa skupom varijabli LOCPATH se ignorira.

Evo odlučujućeg testa:

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

Ura! Uspjeli smo!

Radite na greškama

Već sam odgovorio na pitanja o sortiranju stringova postavljena na početku, ali ima još par pitanja o greškama - vidljivim i nevidljivim.

Vratimo se originalnom problemu.

I program sudbina i program Pridruži se koristite iste funkcije za usporedbu nizova iz glibc. Kako se to dogodilo Pridruži se dao grešku u sortiranju redova sortiranih naredbom sudbina in locale sr_US.UTF-8? Odgovor je jednostavan: sudbina uspoređuje cijeli niz, i Pridruži se upoređuje samo ključ, koji je po defaultu početak niza do prvog znaka razmaka. U mom primjeru, ovo je rezultiralo porukom o grešci jer sortiranje prvih riječi u redovima nije odgovaralo sortiranju kompletnih redova.

Locale "C" garantuje da će u sortiranim stringovima i početni podnizovi do prvog razmaka takođe biti sortirani, ali ovo samo maskira grešku. Moguće je odabrati podatke (osobe sa istim prezimenima, ali različitim imenima) koji bi bez poruke o grešci dali pogrešan rezultat spajanja fajlova. Ako želimo Pridruži se spojene linije datoteke punim imenom, tada bi ispravan način bio da se eksplicitno navede separator polja i sortira po ključnom polju, a ne po cijelom redu. U ovom slučaju, spajanje će se nastaviti ispravno i neće biti grešaka ni na jednom lokalitetu:

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

Uspješno izveden primjer u kodiranju CP1251 sadrži još jednu grešku. Činjenica je da u svim meni poznatim distribucijama Linux paketima nedostaje prevedena lokalizacija ru_RU.CP1251. Ako kompajlirana lokalizacija nije pronađena, onda sudbina tiho koristi poređenje bajt po bajt, što smo i primijetili.

Usput, postoji još jedna mala greška koja se odnosi na nedostupnost kompajliranih lokalizacija. Tim LOCPATH=/tmp lokalizacija -a će dati listu svih lokacija u locale-archive, ali sa skupom varijabli LOCPATH za sve programe (uključujući većinu locale) ove lokacije neće biti dostupne.

$> 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 je navikao da misli da su stringovi skup bajtova, onda je vaš izbor LC_COLLATE=C.

Ako ste lingvist ili prevodilac rječnika, onda je bolje da kompajlirate u svom lokalu.

Ako ste jednostavan korisnik, samo se trebate naviknuti na činjenicu da je komanda ls -a ispisuje datoteke koje počinju s tačkom pomiješane s datotekama koje počinju slovom, i Ponoćni zapovjednik, koji koristi svoje interne funkcije za sortiranje imena, stavlja datoteke koje počinju tačkom na početak liste.