Sissejuhatus

Kõik algas lühikesest skriptist, mis pidi ühendama teavet aadresside e-mail töötajatest, mis saadud meililisti kasutajate loendist, koos töötajate ametikohtadega, mis saadud personaliosakonna andmebaasist. Mõlemad loendid eksportiti tekstifailidena Unicode'i kodeeringus UTF-8 ja salvestati unixi lõppudega.

Sisu mail.txt

Ivanov Andre;ia@example.com

Sisu buhg.txt

Ivanova Alla;maaler
Jolkin Ella;kraanajuht
Ivanov Andre;torumees
Abakanov Mihail;maaler

Failide ühendamiseks sortsiti failid unixi käsu abil sort ja edastati unixi programmile join, mis lõpetas ootamatult tõrke tõttu:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: pole sorteeritud: Ivanov Andre;torumees

Sorteerimise tulemus nägi silmaga vaadates välja õige, kuid meeste ja naiste perekonnanimede kokkulangemisel on naised enne mehi:

$> sort buhg.txt
Abakanov Mihail;maaler
Jolkin Ella;kraanajuht
Ivanova Alla;maaler
Ivanov Andre;torumees

Tundub, et see on unicode'i sortimise viga või naiste õiguste manifestatsioon sortimise algoritmis. Esimene tundub muidugi usutavam.

Jätame hetkel kõrvale join ja keskendume sort. Proovime lahendada ülesande teadlikult eksitades. Alustuseks muudame lokaali en_US . Tundub, et ru_RU. Sorteerimiseks piisaks keskkonnamuutuja seadmisest LC_COLLATE, aga me ei hakka pisiasju ajama:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;maaler
Jolkin Ella;kraanajuht
Ivanova Alla;maaler
Ivanov Andre;torumees

Miski ei muutunud.

Proovime faile ühekordse kodeeringusse edastada:

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

Taaskord ei muutunud miski.

Mitte midagi teha, tuleb otsida lahendust internetist. Otse vene perekonnanimede kohta ei ole midagi, kuid on küsimusi teiste sorteerimise veidrustega. Näiteks selline probleem: unix sort käsitleb ‘-’ (miinus) märke nähtamatutena. Kui lühidalt, siis stringid "a-b", "aa", "ac" sorteeritakse kui "aa", "a-b", "ac".

Vastus on kõikjal standardne: kasutage programmeerija lokaali "C" ja teil on õnne. Proovime:

$> LANG=C sort buhg.txt
Jolkin Ella;kraanajuht
Abakanov Mihail;maaler
Ivanov Andre;torumees
Ivanova Alla;advokaat

Midagi on muutunud. Ivanovid on õiges järjekorras, tõepoolest on Jolkin kuhugi kadunud. Naaseme algse ülesande juurde:

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

See toimis ilma vigadeta, nagu lubas internet. Ja see kõik vaatamata Ёlkina esimeses reas.

Probleem näib olevat lahendatud, kuid igaks juhuks proovime veel ühte vene kodeeringut — Windowsi kodeeringut CP1251:

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

Sorteerimise tulemus, ootamatult, vastab lokaalile "C", ja kogu näide, vastavalt, läbib veatut. Miski müstiline.

Ma ei armasta müstikat programmeerimises, kuna tavaliselt varjab see vigu. Pean tõsiselt tegelema küsimusega, kuidas see töötab sort ja millele see mõjutab LC_COLLATE .

Lõpus püüan vastata küsimustele:

• miks naiste perekonnanimesid sorteeriti valesti
• miks LANG=ru_RU.CP1251 osutus ekvivalentseks LANG=C
• miks on sort ja join erinevad arusaamad sorteeritud ridade järjestusest
• miks on kõigis minu näidetes vead
• lõpuks, kuidas sorteerida ridu oma maitse järgi

Sorteerimine UTF-8 formaadis

Esimene peatus on tehniline aruanne nr 10 pealkirjaga Unicode collation algorithm veebisaidil unicode.org. Aruanne sisaldab palju tehnilisi detaile, nii et luban endale tuua lühikese ülevaate põhiteesidest.

Võrdlemine — "võrdlus" ridade vahel — on iga sorteerimisalgoritmi aluseks. Igal algoritmil võivad olla erinevused ("mull", "ühendamine", "kiire"), kuid kõik need kasutavad ridade paaride võrdlemist, et määrata nende järjestus.

Ridade sorteerimine loomulikus keeles on üsna keeruline probleem. Isegi kõige lihtsamates ühebaidistes kodeeringutes ei vasta tähtede järjekord tähestikus, mis on mingil määral erinev ingliskeelsest, juba numbrilistele väärtustele, millega need tähed kodeeritakse. Nii on saksa tähestikus täht Ö paikneb kui O ja P, ja kodeeringus CP850 sattub see vahele ÿ ja Ü.

Saame proovida abstraktiseerida konkreetse kodeeringu ja vaadata "ideaalseid" tähti, mis asuvad mingis järjestuses, nagu see on tehtud UTF-8. Kodeeringud UTF8, UTF16 või ühebaidine KOI8-R (kui on vaja piiratud alamsüsteemi UTF-8-st) annavad erinevad numbrilised esitlused tähtedele, kuid viitavad samadele elementidele põhitaabelis.

Selgub, et isegi nullist sümbolite tabeli koostamine ei võimalda meil määrata universaalset sümbolite järjekorda. Erinevates rahvuslikes tähestikes, mis kasutavad samu tähti, võib nende tähtede järjekord erineda. Näiteks prantsuse keeles Æ loetakse ligatuuriks ja sorteeritakse nagu string AE. Norra keeles Æ loetakse eraldi tähiseks, mis asub pärast Z. Muide, lisaks ligatuuride tüüpidele Æ on olemas ka tähed, mis on kirjutatud mitme sümboliga. Tshehhi tähestikus on täht Ch, mis asub kahe vahel H ja I.

Lisaks tähestike erinevusele on olemas ka muid rahvuslikke traditsioone, mis mõjutavad sortimist. Eelkõige tekib küsimus: millises järjekorras peaksid sõnaraamatus olema sõnad, mis koosnevad suurtest ja väikestest tähtedest? Samuti võivad sortimist mõjutada kirjavahemärgi kasutamise eripärad. Hispaania keeles asetatakse küsimuse ette pööratud küsimärk (¿Te gusta la música?). Sel juhul on selge, et küsimused ei tohiks rühmituda eraldi klastrisse väljaspool tähestikku, vaid kuidas sorteerida stringe koos teiste kirjavahemärkidega?

Ma ei hakka peatuma stringide sortimisel keeltes, mis oluliselt erinevad Euroopa keeltest. Tahan märkida, et keeltes, kus kirjutamise suund on paremalt vasakule või ülalti alla, hoitakse tõenäoliselt stringide sümboleid lugemise järjekorras ning isegi mitte-tähestikulistes kirjutistes on oma meetodid stringide sümbolite järjekorda seadmiseks. Näiteks võivad hieroglüüfid olla järjestatud nende joonistuse järgi (hiina hieroglüüfide võtmed) või häälduse järgi. Kuidas peaksid emoji sorteerima, ei oska ma ausalt öelda, kuid ka nende jaoks saab midagi välja mõelda.

Tulenevalt eespool mainitud omadustest on välja töötatud peamised nõuded stringide võrdlemiseks, mis põhinevad Unicode tabelitel:

• stringide võrdlemine ei sõltu sümbolite asukohast kooditabelis;
• sümbolite järjestused, mis moodustavad ühe sümboli, viiakse kanonilisse vormi (A + ülemine ring on sama, mis Å);
• stringide võrdlemisel käsitletakse sümbolit kontekstis ja vajadusel ühendatakse see naabritega ühe võrdlusüksusena (Ch tshehhi keeles) või jagatakse mitmeks (Æ prantsuse keeles);
• kõik rahvuslikud omadused (alfabeet, suur/kirjas, kirjavahemärgid, kirjutamisviiside järjekord) peavad olema seadistatavad kuni käsitsi määramiseni (emodžid);
• võrdlemine on oluline mitte ainult sortimise jaoks, vaid ka paljude muude kohtade jaoks, näiteks ridade vahemike määramisel (asendus {A… я} sisse bash);
• võrdlemine peab toimuma piisavalt kiiresti.

Lisaks on raporti autorid formuleerinud võrdlemise omadused, millele algoritmi arendajad ei peaks toetuma:

• võrdlemise algoritm ei tohi nõuda iga keele jaoks eraldi sümbolite komplekti (vene ja ukraina keel kasutavad enamikku kirillitsast ühiselt);
• võrdlemine ei tohi toetuda sümbolite järjekorrale Unicode tabelites;
• stringi kaal ei tohi olla stringi atribuut, kuna sama string erinevates kultuurilistes kontekstides võib omada erinevaid kaalu;
• stringide kaalud võivad muutuda liitmise või jagamise käigus (välja x < y ei tähenda, et xz < yz);
• erinevad stringid, millel on samad kaalud, loetakse sortimisalgoritmi seisukohalt võrdseks. Selliste stringide täiendava järjekorda seadmise võimalus on olemas, kuid see võib halvendada jõudlust;
• korrastatud sortimisel võivad samade kaaludega stringid omavahel vahetuda. Stabiilsus on konkreetse sortimisalgoritmi omadus, mitte stringide võrdlemise algoritmi omadus (vt eelmist punkti);
• sortimisreeglid võivad aja jooksul muutuda, kui kultuurilised traditsioonid täienevad/muudavad.

Samuti on märgitud, et võrdlemise algoritm ei tea midagi võrreldavate stringide semantikast. Seega ei tohi ainult numbritest koosnevaid stringe võrrelda kui arvusid, ja ingliskeelsete nimetuste loendites ei tohi artikkel eemalduda (Beatles, The).

Käideldes kõiki nõutud tingimusi, on ette nähtud mitmeastmeline (praktiliselt neljast astmest koosnev) tabelialgoritm.

Eelnevalt viidatakse, et stringi sümbolid tuuakse kanoniliselt ja rühmitatakse võrdlemise üksusteks. Iga võrdlemise üksusele määratakse mitu kaalu, mis vastavad mitmele võrdlemise tasemele. Võrdlemise üksuste kaalud on järjestatud hulkade elemendid (antud juhul täisarvud), mida saab võrrelda suurem-vähem. Eriline väärtus IGNORED (0x0) tähendab, et vastava võrdluse tasemel ei osale antud üksus võrreldes. Stringide võrdlemine võib korduda mitu korda, kasutades vastavate tasandite kaalu. Igal tasemel võrreldakse järjestikku kahe stringi võrdlemise kaalude üksusi.

Erinevates algoritmi rakendustes eri rahvuste traditsioonide jaoks võivad tegurite suurused erineda, kuid Unicode'i standardisse kuulub põhikaalude tabel — "Default Unicode Collation Element Table" (DUCET). Tahan märkida, et muutuja seadmine LC_COLLATE on tegelikult viide kaalu tabeli valimisele stringide võrdlemise funktsioonis.

Kaalu koefitsiendid DUCET on üles ehitatud järgmiselt:

• esimesel tasemel muudetakse kõik tähed ühte suurust, diakriitilised märgid jäetakse välja, kirjavahemärgid (mitte kõik) ignoreeritakse;
• teisel tasemel arvestatakse ainult diakriitilisi märke;
• kolmandal tasemel arvestatakse ainult suurust;
• neljandal tasemel arvestatakse ainult kirjavahemärke.

Võrdlemine toimub mitmete läbikäikude käigus: esiteks võrreldakse esimese taseme koefitsiente; kui kaalud on väärtustes võrdsed, toimub uus võrdlemine teise taseme kaaludega; seejärel võimalikult kolmanda ja neljanda tasemega.

Võrdlemine lõpeb, kui stringides on vastavad üksteisele võrreldavad üksused erinevate kaaludega. Stringid, mis omavad võrdsed kaalu kõigil neljal tasemel, peetakse omavahel võrdsed.

Just see algoritm (paljude täiendavate tehniliste detailidega) andis nime aruandele nr 10 — "Unicode Collation Algorithm" (UCA).

Siin muutub sorteerimise käitumine meie näites mõnevõrra selgemaks. Oleks hea seda võrrelda Unicode'i standardiga.

Rakenduste testimiseks UCA on olemas spetsiaalne test, mis kasutab kaalude faili, mis rakendab DUCET. Kaalude failis võib leida erinevaid huvitavaid asju. Näiteks on seal mahjongi ja Euroopa domino täringute järjestus ning kaardipakkides mastide järjestus (sümbol 1F000 ja edasi). Kaardimastid on paigutatud vastavalt bridži reeglitele — PCHBT, ja kaardid mastis — järjestuses T, 2, 3… K.

Stringide sortimise õigsuse käsitsi kontrollimine vastavalt DUCET oleks üsna väsitav, kuid õnneks meie jaoks on olemas silmapaistev teostus Unicode'iga töötamiseks — "Rahvusvahelised komponente Unicode'i jaoks" (ICU).

Selle raamatukogu veebisaidil, mis on välja töötatud IBM, on demonstreerimise leheküljed, sealhulgas stringide võrdlemise algoritmi leht. Sisestame meie teststringid vaike seadistustega ja, oh imet, saame ideaalse eesti sorteeringu.

Abakanov Mihhail;maalija
Jolkina Ella;kraanaoperaator
Ivanov Andrei;torumees
Ivanova Alla;advokaad

Muide, veebisaidilt ICU leiate täpsustusi võrdlemise algoritmi toimimise kohta, kui käsitletakse kirjavahemärke. Näidetes Collation FAQ ignoreeritakse apostroofe ja sidekriipse.

Unicode aitas meid, kuid peame leidma imelike käitumise põhjused sort ja Linux kusagil mujal.

Sorteerimine glibc-s

Kiire ülevaade GNU Core Utilsi sort API-s allikakoodist näitas, et utiliidi lokaliseerimine piirdub muutujate praeguse väärtuse väljatrükiga käivitamise ajal tõrkeotsingurežiimis: LC_COLLATE $ sort --debug buhg.txt > buhg.srt sort: kasutab ‘en_US.UTF8’ sorteeri reegleid

Stringide võrdlemine toimub standardse funktsiooni

strcoll , seega on kõik huvitav osa raamatukoguststringide võrdlemisele pühendatud glibc.

Pealehe wiki projekti glibc üks lõik . Sellest lõigust on võimalik aru saada, etsorteerimine põhineb juba meile tuntud algoritmil glibc The Unicode collation algorithm UCA () ja/või sellele sarnasel standardilISO 14651 Rahvusvaheline stringide järjestamise ja võrdlemise (). Seoses viimase standardiga tuleb märkida, et veebisaidilstandards.iso.org on ametlikult kuulutatud avalikuks, kuid vastav link viib mitteeksisteerivale lehele. Google annab mitmeid lehti viidete kohta ametlikele saitidele, mis pakuvad ostmiseks elektroonilist koopiat standardist sajandi euro eest, kuid otsingu kolmandal-neljandal lehel leiate ka otse lingid Rahvusvaheline stringide järjestamise ja võrdlemise . Üldiselt ei erine standard praktiliselt PDF, kuid on igavamat lugeda, kuna ei sisalda eredate näidete riiklikke omadusi stringide sorteerimisel. UCASellel veebisaidil leidis kõige huvitavam teave

oli link wiki veaküllastusse stringide võrdlemise rakenduse arutelu . Arutelust võib teada saada, et glibcstringide võrdlemiseks kasutatakse glibc Common Template Table'i ISOCTT ), mille aadressi leiate standardi (lisast. Aastatel 2000 ja 2015 oli see tabel A tavaliselt stabiilne. Rahvusvaheline stringide järjestamise ja võrdlemise. Aastatel 2000 kuni 2015 ilmus see tabel glibc ei omanud hooldajat ja erines üsna tugevalt (vähemalt välimuselt) praegusest standardi versioonist. Aastatel 2015 kuni 2018 toimus kohandamine uue tabeliversiooniga ja hetkel on teil võimalus reaalses elus kohtuda nii uue tabeliversiooniga (CentOS 8), kui ka vana (CentOS 7).

Nüüd, kui kogu teave algoritmi ja abite tabelite kohta on olemas, saame naasta algse probleemi juurde ja mõista, kuidas õigesti sorteerida read Vene lokaliseerimise kontekstis.

ISO 14651/14652

Meid huvitava tabeli lähtekood lisast enamikes jaotustes Linux asub kataloogis /usr/share/i18n/locales/. Ise tabel asub failis iso14651_t1_common. Siis see fail direktiiviga copy iso14651_t1_common sisaldub failis iso14651_t1, mis omakorda sisaldub riiklikes failides, sealhulgas en_US ja ru_RU. Enamikes jaotustes Linux on kõik lähtefailid osa põhinstallatsioonist, kuid kui neid ei ole, tuleb installida täiendav paket jaotusest.

Faili struktuur iso14651_t1 võib tunduda kohutavalt sõnaline, mitte selgete reeglitega nimede koostamisel, kuid kui süveneda, on kõik piisavalt lihtne. Struktuur on kirjeldatud standardis ISO 14652, mille koopia on saadaval laadimiseks veebilehelt open-std.org. Veel ühe faili formaadi kirjeldamise leiate spetsifikatsioonidest POSIX-i alates OpenGroup. Alternatiivina standardi lugemisele võite uurida funktsiooni lähtekode collate_read ja glibc/locale/programs/ld-collate.c.

Faili struktuur on järgmine:

Vaikimisi kasutatakse sümbolit kui ekraanitsümbolit ja rea lõpp pärast sümbolit # on kommentaar. Mõlemat sümbolit saab ümber määrata, mis ka toimus uue tabeliversiooniga:

escape_char /
comment_char %

Failis võib esineda tokenid formaadis <Uxxxx> või <Uxxxxxxxx> kui x — kuusnurkne number). See on Unicode koodpunktide kuusnurkne esituskodeeringus UCS-4 (UTF-32). Kõik muud elemendid nurksulgudes (sealhulgas <Uxxxx_xxxx>, <2> ja sarnased), peetakse lihtsateks stringi konstantideks, millel ei ole eriliselt tähendust konteksti väljaspool.

Rida LC_COLLATE ütleb meile, et järgmised andmed kirjeldavad stringide võrdlemist.

Esialgu määratakse kaaludele nimed võrdlustabelis ja sümbolite kombinatsioonidele. Üldiselt kuuluvad kaks tüüpi nimesid kahte erinevasse üksusesse, kuid reaalses failis on need segamini. Kaalude nimed määratakse võtmesõnaga collating-symbol (võrdlussümbol), kuna Unicode'i sümbolid, millel on samad kaalud, arvestatakse ekvivalentseteks sümboliteks.

Praeguse faili versiooni sektsiooni kogupikkus on umbes 900 rida. Olen näiteks välja lõiganud mitmest kohast, et näidata nimede juhuslikkust ja eri tüüpi süntaksit.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantiide suurim sümboli väärtus. Hoida loendi lõpus
...
collating-element  from ""
collating-element  from ""

• collating-symbol registreerib rea OSMANYA kaalude nimede tabelis
• collating-symbol .. registreerib nimede jada, mis koosneb eesliitest S ja heksadetsimaalsest numbrilisest sufiksist, mis on 1D000 kuni 1D35F.
• FFFF ja collating-symbol näib olevat suur positiivne täisarv heksadetsimaalses süsteemis, kuid <SFFFF> on lihtsalt nimi, mis võiks välja näha nagu <VERYBIGVAL>
• nimi <U0413> tähendab koodipunkti kodeeringus UCS-4
• collating-element from "" registreerib uue nime kahele Unicode'i punktile.

Kui kaalude nimed on määratud, määratakse tegelikud kaalud. Kuna võrdlemisel on oluline ainult suhete määr ehitamiseks, siis määratakse kaalud lihtsa nimede loetelu jada kaudu. Esmalt loetletakse "kergemad" kaalud, seejärel "raskemad". Tuletan meelde, et iga Unicode'i sümbolile antakse neli erinevat kaalu. Siin on need koondatud ühte järjestatud jadasse. Teoreetiliselt võib iga sümboolne nimi olla kasutusel igal neljal tasemel, kuid kommentaarid osutavad, et arendajad jagavad nimed tasemete kaupa.

% Sümboolsete kaalude määramised

% Kolmanda taseme kaalude määramised




...
% Teise taseme kaalude määramised

 % KOMBINERIV ALAJÕM
 % KOMBINERIV KOMMA ÜLE
 % KOMBINERIV PÖÖRDUMINE KUMMA ÜLE
...
% Esimese taseme kaalude määramised
 % HORIZONTAALNE TABULATSIOON
 % REAASTIMINE
 % VERTIKAALNE TABULATSIOON
...
 % KÜRILI KEELE VÄIKE KIRI DE
 % KÜRILI KEELE VÄIKE KIRI KOMI DE
 % KÜRILI KEELE VÄIKE KIRI DJE
 % KÜRILI KEELE VÄIKE KIRI KOMI DJE
 % KÜRILI KEELE VÄIKE KIRI GJE
 % KÜRILI KEELE VÄIKE KIRI ZE, MILLEL ON ALLA MINEK
 % KÜRILI KEELE VÄIKE KIRI IE
 % KÜRILI KEELE VÄIKE KIRI IE, MILLEL ON BREVI
 % KÜRILI KEELE VÄIKE KIRI UKRAINIAN IE
 % KÜRILI KEELE VÄIKE KIRI ZHE

Lõpuks, tabel koos kaaludega.

Kaalude sektsioon on joontega, mis sisaldavad võtmesõnu order_start ja order_end. Täiendavad parameetrid order_start määravad, millises suunas read igal võrdlemise tasemel vaadatakse. Vaikimisi kasutatakse parameetrit forward. Sektsiooni keha koosneb ridadest, mis sisaldavad sümboli koodi ja nelja selle kaalu. Sümboli kood võib olla esindatud kas sümbol ise, koodipunkt või sümboolne nimi, mis on varem määratletud. Kaalu saab samuti määrata sümboolsete nimede, koodipunktide või sümbolite kaudu. Kui kasutatakse koodipunkte või sümboleid, siis nende kaal on samasugune kui koodipunkti numbriline väärtus (positsioon Unicode tabelis). Sümbolid, mida ei ole selgelt määratletud (nii nagu ma aru saan), arvestatakse tabelisse peamise kaaluga, mis vastab positsioonile Unicode tabelis. Eriline kaalu väärtus IGNORE tähendab, et vastaval võrdlemise tasemel seda sümbolit ei arvestata.

Kaalude struktuuri demonstreerimiseks valisin kolm piisavalt ilmselget fragmenti:

• sümbolid, mida täielikult ignoreeritakse
• sümbolid, mis on ekvivalentne numbrile kolm esimesel kahel tasemel
• kiri kyrillises alfabeedis, mis ei sisalda diakriitilisi märke ja seetõttu sorteeritakse peamiselt esimesel ja kolmandal tasemel.

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

Nüüd saab jälle naasta artikli alguse näidete sortimise juurde. Probleem peitub tabeli kaalu selles osas:

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

On näha, et selles tabelis on kirjavahemärgid tabelist Pobitine või pobaita rasteriseerimine (sealhulgas tühik) stringide võrdlemisel praktiliselt alati ignoreeritakse. Eranditeks on vaid read, mis kattuvad täielikult, välja arvatud kirjavahemärgid, mis esinevad kattuvates positsioonides. Minu näite read (pärast sortimist) näevad välja järgmised:

AbakanovMihhailvärvija
JolkinaElakraanioperaator
IvanovaAllavärvija
IvanovAndrei puusepp

Arvestades, et kaalu tabelis käivad vene keeles suurtähed pärast väiketähti (kolmandal tasemel <CAP> raske kui <MIN>), sortimine näib täiesti korrektne.

Muutes muutuja LC_COLLATE=C laaditakse eriline tabel, mis määrab baitide võrdlemise

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

Kuna Unicode'is on tähemärk Ё enne A, sorteeritakse read vastavalt.

Tekstilised ja binaarsed tabelid

On ilmne, et stringide võrreldamine on äärmiselt sagedane operatsioon ja tabeli analüüs lisast mõnevõrra kulukas protseduur. Tabeli juurdepääsu optimeerimiseks kompileeritakse see binaarfaili kujule käsu localedef.

Meeskond localedef mis võtab parameetritena faili riiklike eripärade tabeliga (valik -i), milles kõik sümbolid on esitatud Unicode'i punktidena, ja faili, mis seondab Unicode'i punktid konkreetses kodeeringus sümbolitega (valik -f). Töö tulemusena luuakse binaarfailid lokaali jaoks, mille nimi on määratud viimases parameetris.

Glibc toetab kahte tüüpi binaarfailide formaate: "traditsiooniline" ja "kaasaegne".

Traditsiooniline formaat tähendab, et lokaali nimi on nimekiri alla kaustas /usr/lib/locale/. Sellel alamkaustal hoitakse binaarfailide LC_COLLATE, LC_CTYPE, LC_TIME jne. Fail LC_IDENTIFICATION sisaldab lokaali formaalset nime (mis võib erineda kausta nimest) ja kommentaare.

Kaasaegne formaat eeldab, et kõik lokaalid hoitakse ühes arhiivis /usr/lib/locale/locale-archive, mis kaardistatakse virtuaalsesse mällu kõigile protsessidele, mis seda kasutavad glibc. Kaasaegses formaadis nimetatakse lokaali nime teatud kanoniseerimisele — kodeeringu nimedes jäävad ainult numbrid ja tähed, mis on muudetud väikesteks tähtedeks. Nii ru_RU.KOI8-R, salvestatakse kui ru_RU.koi8r.

Sisendfailid otsitakse jooksva kausta ning kaustade /usr/share/i18n/locales/ ja /usr/share/i18n/charmaps/ failide lisast ja kodeeringute failide vastavalt.

Näiteks käsk

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

kompileerib faili /usr/share/i18n/locales/ru_RU kasutades kodeerimisfaili /usr/share/i18n/charmaps/MAC-CYRILLIC.gz ja salvestab tulemuse /usr/lib/locale/locale-archive koos nimega ru_RU.maccyrillic

Kui keskkonnamuutuja LANG=en_US.UTF-8 siis glibc otsib lokaali binaarfailide järgmist järgnevate failide ja kaustade järjekorras:

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

Kui lokaal esineb nii traditsioonilistes kui ka kaasaegsetes formaatides, antakse eelnev kaal kaasaegsele.

Koostatud lokaalide nimekirja saab vaadata käsuga locale -a.

Oma võrdlustabeli ettevalmistamine

Nüüd, varustatud teadlike teadmistega, saab luua oma ideaalse stringide võrdlustabeli. See tabel peab õigesti võrreldama vene tähti, sealhulgas tähti Ё, arvestades samas ka kirjavahemärke vastavalt tabelile Pobitine või pobaita rasteriseerimine.

Oma sortimisse tabeli ettevalmistamise protsess koosneb kahest etapist: kaalutabeli redigeerimisest ja selle binaarfailiks kompileerimisest käsuga localedef.

Kuna võrreldava tabeli kohandamine minimaalse redigeerimise kuludega on võimalik, on formaadis ISO 14652 on olemas olemasoleva tabeli kaalu kohandamise sektsioonid. Sektsioon algab võtmesõnast reorder-after ja positsiooni näitamisest, mille järel asendamine toimub. Sektsiooni lõpetab rida reorder-end. Kui tabeli mitmeid osi tuleb kohandada, luuakse iga sellise osa jaoks oma sektsioon.

Ma kopeerisin uued faili versioonid iso14651_t1_common ja ru_RU repositooriumist glibc oma kodukatalooge ~/.local/share/i18n/locales/ ja redigeerisin osakonda natuke. LC_COLLATE ja ru_RU. Uued faili versioonid on täielikult ühilduvad minu versiooniga glibc. Kui soovite kasutada vanemaid faili versioone, peate muutma sümboolseid nimesid ja asukohta, kust asendamine algab tabelis.

LC_COLLATE
% Kopeerige mall ISO/IEC 14651-st
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % EXCLAMATION MARK
 ;;; % QUOTATION MARK
...
 ;;; % RIGHT CURLY BRACKET
 ;;; % TILDE
reorder-end
END LC_COLLATE

Tegelikult oleks pidanud väljad muutma LC_IDENTIFICATION nii, et need viitavad lokaali ru_MY, kuid minu näites ei olnud seda vaja, kuna ma jätsin välja lokaalisalad locale-archive.

Et localedef töötas failidega minu kaustas läbi muutuja I18NPATH võib lisada lisakausta sisendfailide otsimiseks, ja binaarfailide salvestamise katalooge saab määrata tee kaudu, mis on släshidega:

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

POSIX-i eeldab, et LANG võib kirjutada absoluutteed failide kataloogide jaoks, mis algavad sirgest släshist, kuid glibc ja Linux kõik teed loetakse aluskataloogist, mille saab üle määrata muutuja LOCPATH. Pärast seadistamist LOCPATH=~/.local/lib/locale/ kõik lokaliseerimisega seotud failid otsitakse ainult minu kaustast. Lokaali arhiiv seadistatud muutuja korral LOCPATH ignored.

Siin on otsustav test:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mihhail;maalija
Jolkina Ella;kraanajuht
Ivanov Andre;torulukksepp
Ivanova Alla;advokaat

Hurraa! Me tegime selle ära!

Töötamine vigade kallal

Olen juba vastanud alguses esitatud ridade sortimise küsimustele, kuid on veel paar küsimust vigade kohta - nähtavad ja nähtamatud.

Naaseme algse ülesande juurde.

Ja programm sort ja programm join kasutavad samu stringide võrdlemise funktsioone glibc. Kuidas see juhtus, et join näitas sorteerimise viga ridade puhul, mis olid sorteeritud käsuga sort kohalikus en_US.UTF-8? Ответ прост: sort võrdleb rida täielikult, kuid join võrdleb ainult märksõna, milleks on vaikimisi rida kuni esimese tühiku sümbolini. Minu näites põhjustas see veateate, kuna ridade esimeste sõnade sorteerimine ei klappinud täisridade sorteerimisega.

Kohalik "C" tagab, et sorteeritud ridades on algsed alampead sõnad kuni esimese tühiku sümbolini samuti sorteeritud, kuid see varjab vaid viga. Võib leida selliseid andmeid (inimesed, kellel on samad perekonnanimed, kuid erinevad eesnimed), mis annavad vale faili ühendamise tulemuse ilma veateateta. Kui soovime, et join ühendaks failide ridu perekonna- ja eesnime järgi, siis õige viis oleks eraldaja määramine ja nende sorteerimine märksõna järgi, mitte kogu rea järgi. Sel juhul toimub ka ühendamine õigesti ja mingis kohalikus ei esine vigu:

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

Edukalt lõpetatud näide kodeeringus CP1251 kätkeb veel üht viga. Nimelt on kõigis minu teadaolevates distributsioonides Linux pakettides puuduv kompileeritud kohalik ru_RU.CP1251. Kui kompileeritud kohalikku ei leita, siis sort kasutatakse vaikselt byte-tasemel võrdlemist, mida me olime ka näinud.

Muide, on ka veel üks väike tõrge, mis on seotud kompileeritud lokalite puudumisega. Käsk LOCPATH=/tmp locale -a annab välja kõigi lokalite loendi locale-archive, kuid seatud muutuja LOCPATH kõikide programmide (sealhulgas locale) jaoks ei ole need kohalikud saadaval.

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

Kokkuvõte

Kui oled programmeerija, kes harjunud arvama, et read on byte'ide kogum, siis on sinu valik LC_COLLATE=C.

Kui oled lingvist või sõnaraamatute koostaja, siis on sul parem oma kohalik kompileerida.

Kui oled tavaline kasutaja, siis piisab, kui harjuda sellega, et käsk ls -a annab välja faile, mis algavad punktiga, koos failidega, mis algavad tähega, ja Midnight Commander, mis kasutab oma sisemisi funktsioone nimede sortimiseks, viib failid, mille nimi algab punktiga, loendi ette.

Viidatud lingid

Aruanne nr 10 Unicode sortimisalgoritmi kohta

Sümbolite kaalud unicode.org-is

ICU — teostus IBM-i Unicode'i töötlemise raamatukogust.

Sorteerimistest ICU

Sümbolite kaalud Rahvusvaheline stringide järjestamise ja võrdlemise

Faili formaadi kirjeldus kaaludega ISO 14652

Kettide võrdlemise arutelu glibc

Allikas: habr.com