Uvod

Sve je počelo kratkom skriptom koja je trebala objediniti podatke o adresi e-mail zaposlenici dobiveni iz popisa korisnika mailing liste, s pozicijama zaposlenika dobivenim iz baze HR odjela. Oba popisa su izvezena u Unicode tekstualne datoteke UTF-8 i spremljeni s Unix završecima redaka.

sadržaj mail.txt

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

sadržaj buhg.txt

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

Za spajanje, datoteke su sortirane Unix naredbom vrsta i predaje na ulaz Unix programa pridruži, koji neočekivano nije uspio s pogreškom:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

Gledajući rezultat razvrstavanja vlastitim očima, pokazalo se da je, općenito gledano, razvrstavanje ispravno, ali u slučaju podudarnosti muških i ženskih prezimena, ženska su ispred muških:

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

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

Odgodimo to za sada pridruži i usredotočite se na vrsta. Pokušajmo riješiti problem znanstvenim pokingom. Prvo, promijenimo lokalizaciju iz hr 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 ponovno kodirati 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, morat ćete potražiti rješenje na internetu. Ne postoji ništa izravno o ruskim prezimenima, ali postoje pitanja o drugim neobičnostima sortiranja. Na primjer, evo problema: unix sortiranje znakove '-' (crtica) tretira kao nevidljive. Ukratko, nizovi "a-b", "aa", "ac" sortirani su kao "aa", "a-b", "ac".

Odgovor je svugdje standardan: koristite lokalizaciju programera "C" i bit ćeš sretan. Pokušajmo:

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

Nešto se promijenilo. Ivanovci su se redali pravilnim redom, iako se Yolkina negdje okliznula. Vratimo 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 > result

Radilo je bez grešaka, kao što je Internet obećao. I to unatoč Yolkinoj 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, čudno, podudarat će se s lokalitetom "C", te cijeli primjer, sukladno tome, radi bez grešaka. Nekakav misticizam.

Ne volim mistiku u programiranju jer ona obično prikriva greške. Morat ćemo ozbiljno ispitati kako to funkcionira. vrsta i na što utječe? LC_COLLATE .

Na kraju ću pokušati odgovoriti na pitanja:

zašto su ženska prezimena pogrešno razvrstana?
zašto LANG=ru_RU.CP1251 pokazalo se ekvivalentnim JEZIK=C
zašto vrsta и pridruži različite ideje o redoslijedu sortiranih nizova
zašto postoje greške u svim mojim primjerima?
konačno kako sortirati nizove po svom ukusu

Sortiranje u Unicodeu

Prva stanica bit će tehničko izvješće br. 10 pod naslovom Unicode algoritam za uspoređivanje Online unicode.org. Izvješće sadrži puno tehničkih detalja, pa mi dopustite da dam kratak sažetak glavnih ideja.

Sravnjivanje — “uspoređivanje” nizova je osnova svakog algoritma sortiranja. Sami algoritmi mogu se razlikovati ("bubble", "merge", "fast"), ali svi će koristiti usporedbu para nizova kako bi odredili redoslijed u kojem se pojavljuju.

Sortiranje nizova u prirodnom jeziku je prilično složen problem. Čak i u najjednostavnijem jednobajtnom kodiranju, 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 s kojima su ta slova kodirana. Dakle, u njemačkoj abecedi slovo Ö stoji između О и P, i u kodiranju CP850 ona dobiva između ÿ и Ü.

Možete se pokušati apstrahirati od određenog kodiranja i razmotriti "idealna" slova koja su poredana nekim redoslijedom, kao što je učinjeno u Unicodeu. Kodiranja UTF8, UTF16 ili jednobajtni KOI8-R (ako je potreban ograničeni podskup Unicodea) će dati različite numeričke prikaze slova, ali se odnose na iste elemente osnovne tablice.

Ispada da čak i ako tablicu simbola izgradimo od nule, nećemo joj moći dodijeliti univerzalni redoslijed simbola. U različitim nacionalnim abecedama koje koriste ista slova, redoslijed tih slova može se razlikovati. Na primjer, na francuskom Æ smatrat će se ligaturom i sortirati kao niz AE. Na norveškom Æ bit će zasebno slovo, koje se nalazi nakon Z. Usput, osim ligatura poput Æ Postoje slova napisana s nekoliko simbola. Dakle, u češkoj abecedi postoji slovo Ch, koji stoji između H и I.

Osim razlika u abecedi, postoje i druge nacionalne tradicije koje utječu na sortiranje. Posebno se postavlja pitanje kojim bi se redom u rječniku trebale pojavljivati riječi koje se sastoje od velikih i malih slova? Na razvrstavanje također može utjecati korištenje interpunkcijskih znakova. U španjolskom se na početku upitne rečenice koristi obrnuti upitnik (Voliš li glazbu?). U ovom slučaju očito je da upitne rečenice ne treba grupirati u zasebnu skupinu izvan abecede, ali kako poredati retke s drugim interpunkcijskim znakovima?

Neću se zadržavati na razvrstavanju nizova na jezicima koji su vrlo različiti od europskih. Imajte na umu da su u jezicima sa smjerom pisanja zdesna nalijevo ili odozgo prema dolje, znakovi u recima najvjerojatnije pohranjeni redoslijedom čitanja, a čak i neabecedni sustavi pisanja imaju vlastite načine sređivanja redaka znak po znak . Na primjer, hijeroglifi se mogu poredati po stilu (Tipke s kineskim znakovima) ili po izgovoru. Da budem iskren, nemam pojma kako bi emojiji trebali biti raspoređeni, ali možete smisliti nešto i za njih.

Na temelju gore navedenih značajki, formulirani su osnovni zahtjevi za usporedbu nizova na temelju Unicode tablica:

usporedba nizova ne ovisi o položaju znakova u kodnoj tablici;
nizovi znakova koji tvore jedan znak svode se na kanonski oblik (A + gornji krug je isti kao Å);
Kada se uspoređuju nizovi, znak se razmatra u kontekstu niza i, ako je potrebno, kombinira se sa svojim susjedima u jednu jedinicu usporedbe (Ch na češkom) ili je podijeljen na nekoliko (Æ na francuskom);
sve nacionalne značajke (abeceda, velika/mala slova, interpunkcija, redoslijed vrsta pisanja) moraju biti konfigurirane do ručnog dodjeljivanja redoslijeda (emoji);
usporedba je važna ne samo za sortiranje, već i na mnogim drugim mjestima, na primjer za određivanje raspona redaka (zamjena {A... z} u udariti);
usporedbu treba obaviti prilično brzo.

Osim toga, autori izvješća formulirali su svojstva usporedbe na koja se razvijači algoritama ne bi trebali oslanjati:

algoritam za usporedbu ne bi trebao zahtijevati poseban skup znakova za svaki jezik (ruski i ukrajinski jezici dijele većinu ćiriličnih znakova);
usporedba se ne bi trebala oslanjati na redoslijed znakova u Unicode tablicama;
težina niza ne bi trebala biti atribut niza, budući da isti niz u različitim kulturnim kontekstima može imati različite težine;
težine redaka mogu se promijeniti prilikom spajanja ili dijeljenja (od x < y to ne prati to xz < yz);
različiti nizovi s istim težinama smatraju se jednakima sa stajališta algoritma za sortiranje. Uvođenje dodatnog redoslijeda takvih nizova je moguće, ali može pogoršati performanse;
Tijekom ponovljenog sortiranja, retci s istim težinama mogu se zamijeniti. Robusnost je svojstvo specifičnog algoritma za sortiranje, a ne svojstvo algoritma za usporedbu nizova (pogledajte prethodni paragraf);
Pravila razvrstavanja mogu se mijenjati tijekom vremena kako se kulturne tradicije usavršavaju/mijenjaju.

Također je propisano da algoritam za usporedbu ne zna ništa o semantici nizova koji se obrađuju. Stoga se nizovi koji se sastoje samo od znamenki ne smiju uspoređivati kao brojevi, au popisima engleskih naziva članak (Beatlesi, The).

Kako bi se zadovoljili svi navedeni zahtjevi, predlaže se višerazinski (zapravo četverorazinski) algoritam za sortiranje tablica.

Prethodno su znakovi u nizu reducirani u kanonski oblik i grupirani u jedinice za usporedbu. Svakoj jedinici usporedbe dodijeljeno je nekoliko težina koje odgovaraju nekoliko razina usporedbe. Težine usporednih jedinica su elementi uređenih skupova (u ovom slučaju cijelih brojeva) koji se mogu uspoređivati više ili manje. Posebno značenje IGNORIRANO (0x0) znači da na odgovarajućoj razini usporedbe ova jedinica nije uključena u usporedbu. Usporedba nizova može se ponoviti nekoliko puta, koristeći težine odgovarajućih razina. Na svakoj razini, težine usporednih jedinica u dva retka međusobno se uzastopno uspoređuju.

U različitim implementacijama algoritma za različite nacionalne tradicije, vrijednosti koeficijenata mogu se razlikovati, ali Unicode standard uključuje osnovnu tablicu težina - "Tablica zadanih Unicode kolacionih elemenata" (DUCET). Želio bih napomenuti da postavljanje varijable LC_COLLATE zapravo je pokazatelj odabira tablice težine u funkciji usporedbe nizova.

Težinski koeficijenti DUCET raspoređeni na sljedeći način:

na prvoj razini sva su slova reducirana na ista velika i mala slova, dijakritički znakovi se odbacuju, interpunkcijski znakovi (ne svi) se zanemaruju;
na drugoj razini uzimaju se u obzir samo dijakritički znakovi;
na trećoj razini uzimaju se u obzir samo slučajevi;
na četvrtoj razini uzimaju se u obzir samo interpunkcijski znakovi.

Usporedba se odvija u nekoliko prolaza: prvo se uspoređuju koeficijenti prve razine; ako se težine podudaraju, provodi se ponovljena usporedba s težinama druge razine; zatim možda treći i četvrti.

Usporedba završava kada reci sadrže podudarne jedinice usporedbe s različitim težinama. Redovi koji imaju jednake težine na sve četiri razine smatraju se međusobno jednakima.

Ovaj algoritam (uz hrpu dodatnih tehničkih detalja) dao je ime izvješću br. 10 - "Unicode Collation Algorithm" (ACU).

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

Za testiranje implementacija ACU postoji poseban test, koristeći datoteka s utezima, provedba DUCET. U datoteci s vagama možete pronaći svakakve smiješne stvari. Na primjer, postoji redoslijed mahjonga i europskih domina, kao i redoslijed boja u špilu karata (simbol 1F000 i dalje). Boje karata se postavljaju prema pravilima bridža - PCBT, a karte u boji su u nizu T, 2,3, XNUMX... K.

Ručna provjera jesu li redovi pravilno sortirani prema DUCET bilo bi prilično zamorno, ali, na našu sreću, postoji uzorna implementacija biblioteke za rad s Unicodeom - "Međunarodne komponente za Unicode"(JIL).

Na web stranici ove knjižnice, razvijenoj u IBM, postoje demo stranice, uključujući stranica algoritma za usporedbu nizova. Unesemo svoje testne retke sa zadanim postavkama i, gle čuda, dobivamo savršeno rusko sortiranje.

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

Usput, web stranica JIL Možete pronaći pojašnjenje algoritma za usporedbu prilikom obrade interpunkcijskih znakova. U primjerima Uspoređivanje FAQ apostrof i crtica se zanemaruju.

Unicode nam je pomogao, ali potražite razloge čudnog ponašanja vrsta в Linux morat će otići negdje drugdje.

Razvrstavanje u glibc

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

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

Usporedbe nizova izvode se pomoću standardne funkcije strcoll, što znači da je sve zanimljivo u knjižnici glibc.

Na wiki projekt glibc posvećen usporedbi nizova jedan paragraf. Iz ovog stavka može se razumjeti da je u glibc sortiranje se temelji na nama već poznatom algoritmu ACU (Unicode algoritam za uspoređivanje) i/ili na njemu bliskom standardu ISO 14651 (Međunarodno sređivanje nizova i usporedba). Što se tiče najnovijeg standarda, valja napomenuti da na web mjestu standardi.iso.org ISO 14651 službeno proglašen javno dostupnim, ali odgovarajući link vodi na nepostojeću stranicu. Google vraća nekoliko stranica s poveznicama na službene stranice koje nude kupnju elektroničke kopije standarda za stotinjak eura, no na trećoj ili četvrtoj stranici rezultata pretraživanja nalaze se i izravne poveznice na PDF. Općenito, standard se praktički ne razlikuje od ACU, ali je dosadniji za čitanje jer ne sadrži jasne primjere nacionalnih značajki sortiranja nizova.

Najzanimljivije informacije o wiki postojala je poveznica na tragač bugova s raspravom o implementaciji usporedbe nizova u glibc. Iz rasprave se može saznati da glibc koristi se za usporedbu nizova ISOosobni stol Tablica zajedničkog predloška (CTT), čiju adresu možete pronaći u prijavi A standard ISO 14651. Između 2000. i 2015. ova tablica u glibc nije imao održavatelja i bio je dosta drugačiji (barem izvana) od trenutne verzije standarda. Od 2015. do 2018. odvijala se prilagodba na novu verziju tablice, a sada imate priliku u stvarnom životu upoznati novu verziju tablice (8 CentOS), i stari (7 CentOS).

Sada kada imamo sve informacije o algoritmu i pomoćnim tablicama, možemo se vratiti izvornom problemu i razumjeti kako pravilno sortirati nizove u ruskom jeziku.

ISO 14651/14652

Izvorni kod tablice koja nas zanima CTT na većini distribucija Linux nalazi se u katalogu /usr/share/i18n/locales/. Sama tablica je u datoteci iso14651_t1_uobičajeno. Onda je ovo direktiva datoteke kopija iso14651_t1_common uključen u datoteku iso14651_t1, koji je, pak, uključen u nacionalne datoteke, uključujući hr и ru_ru. Na 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 izgledati užasno opširno, s neočitim pravilima za konstruiranje imena, ali ako pogledate, sve je prilično jednostavno. Struktura je opisana u standardu ISO 14652čiju kopiju možete preuzeti s web stranice open-std.org. Još jedan opis formata datoteke može se pročitati u tehnički podaci POSIX iz OpenGroup. Kao alternativu čitanju standarda, možete proučiti izvorni kod funkcije usporedi_čitaj в glibc/locale/programs/ld-collate.c.

Struktura datoteke izgleda ovako:

Prema zadanim postavkama, znak se koristi kao izlazni znak, a kraj retka nakon znaka # je komentar. Oba simbola je moguće redefinirati, što je i učinjeno u novoj verziji tablice:

escape_char /
comment_char %

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

red LC_COLLATE govori nam da sljedeći počinju podaci koji opisuju usporedbu nizova.

Prvo se specificiraju nazivi za težine u usporednoj tablici i nazivi za kombinacije simbola. Općenito govoreći, dvije vrste naziva pripadaju dvjema različitim entitetima, ali u stvarnoj su datoteci pomiješane. Imena težina određena su ključnom riječi slaganje-simbol (znak za usporedbu) jer će se pri usporedbi Unicode znakovi koji imaju iste težine smatrati ekvivalentnim znakovima.

Ukupna duljina odjeljka u trenutnoj reviziji datoteke je oko 900 redaka. Izvukao sam primjere s nekoliko mjesta kako bih pokazao proizvoljnost imena i nekoliko vrsta 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>"

simbol za uspoređivanje zapisuje niz OSMANIJA u tablici naziva ljestvica
simbol za uspoređivanje .. registrira niz imena koji se sastoji od prefiksa S i heksadecimalni numerički sufiks iz 1D000 na 1D35F.
FFFF в simbol za uspoređivanje izgleda kao veliki heksadecimalni cijeli broj bez predznaka, ali to je samo ime koje bi moglo izgledati
Naziv znači kodna točka u kodiranju UCS-4
element za uspoređivanje iz "" registrira novo ime za par Unicode točaka.

Nakon što su definirani nazivi utega, specificiraju se stvarni utezi. Budući da su u usporedbi važni samo odnosi veće-ne-manje, težine se određuju jednostavnim slijedom popisa imena. Prvo su navedene "lakše" težine, a zatim one "teže". Dopustite mi da vas podsjetim da su svakom Unicode znaku dodijeljene četiri različite težine. Ovdje su kombinirani u jedan uređen niz. U teoriji, bilo koje simbolično ime može se koristiti na bilo kojoj od četiri razine, ali komentari pokazuju da programeri mentalno razdvajaju imena na razine.

% 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

Na kraju, stvarna tablica težine.

Odjeljak s težinama zatvoren je u recima s ključnim riječima red_start и kraj_narudžbe. Dodatne mogućnosti red_start odrediti u kojem se smjeru retci skeniraju na svakoj razini usporedbe. Zadana postavka je naprijed. Tijelo odjeljka sastoji se od redaka koji sadrže kod simbola i njegove četiri težine. Šifra znaka može biti predstavljena samim znakom, kodnom točkom ili prethodno definiranim simboličkim imenom. Težine se također mogu dati simboličkim nazivima, kodnim točkama ili samim simbolima. Ako se koriste kodne točke ili znakovi, njihova težina je jednaka numeričkoj vrijednosti kodne točke (pozicija u Unicode tablici). Znakovi koji nisu eksplicitno navedeni (koliko ja razumijem) smatraju se dodijeljenima tablici s primarnom težinom koja odgovara poziciji u Unicode tablici. Posebna vrijednost težine ZANEMARITI znači da se simbol zanemaruje na odgovarajućoj razini usporedbe.

Kako bih pokazao strukturu ljestvice, odabrao sam tri prilično očita fragmenta:

likovi koji su potpuno zanemareni
simboli ekvivalentni broju tri u prve dvije razine
početak ćirilice, koji ne sadrži dijakritičke znakove, pa je razvrstan uglavnom po prvoj i trećoj razini.

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 leži u ovom dijelu tablice 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 tablici interpunkcijski znakovi iz tab ASCII (uključujući razmak) se gotovo uvijek zanemaruje kada se uspoređuju nizovi. Jedina iznimka su retci koji se podudaraju u svemu osim interpunkcijskih znakova koji se nalaze na odgovarajućim pozicijama. Linije iz mog primjera (nakon sortiranja) za algoritam usporedbe izgledaju ovako:

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

S obzirom da u tablici ljestvica velika slova u ruskom dolaze nakon malih slova (na trećoj razini teži od ), sortiranje izgleda potpuno ispravno.

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

Budući da u Unicodeu kodna točka Ë dolazi ispred A, nizovi su sortirani u skladu s tim.

Tekst i binarne tablice

Očito je usporedba nizova vrlo uobičajena operacija i raščlanjivanje tablice CTT prilično skup postupak. Kako bi se optimizirao pristup tablici, ona se naredbom prevodi u binarni oblik lokalna def.

Momčad lokalna def prihvaća kao parametre datoteku s tablicom nacionalnih obilježja (opcija -i), u kojoj su svi znakovi predstavljeni Unicode točkama, i datoteka korespondencije između Unicode točaka i znakova određenog kodiranja (opcija -f). Kao rezultat rada, stvorene su binarne datoteke za lokalizaciju s nazivom navedenim u posljednjem parametru.

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

Tradicionalni format znači da je naziv lokalizacije naziv poddirektorija u /usr/lib/locale/. Ovaj poddirektorij pohranjuje binarne datoteke LC_COLLATE, LC_CTYPE, LC_TIME i tako dalje. Datoteka LC_IDENTIFIKACIJA sadrži službeni naziv lokalizacije (koji se može razlikovati od naziva direktorija) i komentare.

Moderni format uključuje pohranjivanje svih lokaliteta u jednu arhivu /usr/lib/locale/locale-archive, koji je preslikan u virtualnu memoriju svih procesa koji koriste glibc. Naziv lokaliteta u modernom formatu podliježe određenoj kanonizaciji - samo brojevi i slova smanjeni na mala slova ostaju u nazivima kodiranja. Tako ru_RU.KOI8-R, bit će spremljeno kao ru_RU.koi8r.

Ulazne datoteke pretražuju se u trenutnom direktoriju, kao iu direktorijima /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ za datoteke CTT odnosno datoteke za kodiranje.

Na primjer, naredba

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

će kompajlirati datoteku /usr/share/i18n/locales/ru_RU pomoću datoteke za kodiranje /usr/share/i18n/charmaps/MAC-CYRILLIC.gz i spremite rezultat u /usr/lib/locale/locale-archive pod imenom ru_RU.maccyrillic

Ako postavite varijablu Lang = en_US.UTF-8 da glibc tražit će binarne datoteke lokalizacije 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 lokalizacija pojavljuje iu tradicionalnom iu modernom formatu, tada se prednost daje modernom formatu.

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

Priprema vaše usporedne tablice

Sada, naoružani znanjem, možete izraditi vlastitu idealnu tablicu za usporedbu nizova. Ova tablica treba ispravno usporediti ruska slova, uključujući slovo Ë, i istovremeno uzeti u obzir interpunkcijske znakove u skladu s tablicom ASCII.

Proces pripreme vlastite tablice sortiranja sastoji se od dvije faze: uređivanje tablice težine i njezino sastavljanje u binarni oblik pomoću naredbe lokalna def.

Kako bi se usporedna tablica prilagodila uz minimalne troškove uređivanja, u formatu ISO 14652 Predviđeni su dijelovi za podešavanje težine postojećeg stola. Odjeljak počinje ključnom riječi reorder-after i označavanje pozicije nakon koje se vrši zamjena. Dio završava linijom reorder-end. Ako je potrebno ispraviti nekoliko odjeljaka tablice, tada se za svaki takav odjeljak stvara odjeljak.

Kopirao sam nove verzije datoteka iso14651_t1_uobičajeno и ru_ru iz spremišta glibc u moj matični direktorij ~/.local/share/i18n/locales/ i malo uredio odjeljak LC_COLLATE в ru_ru. Nove verzije datoteka potpuno su kompatibilne s mojom verzijom glibc. Ako želite koristiti starije verzije datoteka, morat ćete promijeniti simbolička imena i mjesto početka zamjene u tablici.

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

Zapravo, bilo bi potrebno promijeniti polja u LC_IDENTIFIKACIJA tako da ukazuju na lokalitet ru_MY, ali u mom primjeru to nije bilo potrebno jer sam isključio arhivu iz pretraživanja lokaliteta lokalizacija-arhiva.

Da lokalna def radio s datotekama u mojoj mapi putem varijable I18NPATH Možete dodati dodatni direktorij za traženje ulaznih datoteka, a direktorij za spremanje binarnih datoteka može se navesti kao staza s kosim crtama:

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

POSIX sugerira da u JEZIK možete napisati apsolutne staze do direktorija s lokalnim datotekama, počevši s kosom crtom, ali glibc в Linux sve se staze broje iz osnovnog direktorija, koji se može nadjačati kroz varijablu LOCPATH. Nakon instalacije LOCPATH=~/.local/lib/locale/ sve datoteke povezane s lokalizacijom bit će pretraživane samo u mojoj mapi. Arhiva lokaliteta sa skupom varijabli LOCPATH ignorirani.

Evo odlučujućeg testa:

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

hura! Uspjeli smo!

Neke pogreške

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

Vratimo se na izvorni problem.

I program vrsta i program pridruži koristiti iste funkcije usporedbe nizova iz glibc. Kako se dogodilo da pridruži dao je pogrešku pri sortiranju redaka sortiranih naredbom vrsta na lokalitetu en_US.UTF-8? Odgovor je jednostavan: vrsta uspoređuje cijeli niz i pridruži uspoređuje samo ključ, koji je prema zadanim postavkama početak niza do prvog razmaka. U mom primjeru, to je rezultiralo porukom o pogrešci jer sortiranje prvih riječi u redovima nije odgovaralo sortiranju cijelih redaka.

Lokalitet "C" jamči da će u sortiranim nizovima početni podnizovi do prvog razmaka također biti sortirani, ali to samo maskira pogrešku. Moguće je odabrati podatke (osobe s istim prezimenom, ali različitim imenima) koji bi bez poruke o pogrešci dali netočan rezultat spajanja datoteka. Ako želimo pridruži spojene retke datoteke punim imenom, tada bi ispravan način bio eksplicitno navesti razdjelnik polja i sortirati po ključnom polju, a ne po cijelom retku. U ovom slučaju, spajanje će se odvijati ispravno i neće biti pogrešaka ni u jednom mjestu:

$> 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 kodiranja CP1251 sadrži još jednu grešku. Činjenica je da u svim meni poznatim distribucijama Linux paketima nedostaje kompilirana lokalizacija ru_RU.CP1251. Ako kompajlirana lokalizacija nije pronađena, tada vrsta tiho koristi usporedbu bajt po bajt, što smo primijetili.

Usput, postoji još jedan mali kvar vezan uz nedostupnost kompiliranih lokaliteta. Tim LOCPATH=/tmp lokalizacija -a dat će popis svih lokaliteta u lokalizacija-arhiva, ali sa skupom varijabli LOCPATH za sve programe (uključujući većinu mjesto) ove postavke 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 misliti da su nizovi skup bajtova, onda je vaš izbor LC_COLLATE=C.

Ako ste lingvist ili sastavljač rječnika, bolje je da sastavljate na svom jeziku.

Ako ste jednostavan korisnik, onda se samo trebate naviknuti na činjenicu da naredba ls -a ispisuje datoteke koje počinju točkom pomiješane s datotekama koje počinju slovom i Ponoćni zapovjednik, koji koristi svoje unutarnje funkcije za razvrstavanje imena, stavlja datoteke koje počinju s točkom na početak popisa.