įvedimas

Viskas prasidėjo nuo trumpo scenarijaus, kuris turėjo sujungti adreso informaciją elektroninis paštas darbuotojai, gauti iš adresų sąrašo vartotojų sąrašo, o darbuotojų pareigos gautos iš personalo skyriaus duomenų bazės. Abu sąrašai buvo eksportuoti į Unicode tekstinius failus UTF-8 ir išsaugotas su Unix eilučių pabaiga.

Turinys paštas.txt

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

Turinys buhg.txt

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

Norėdami sujungti, failai buvo surūšiuoti naudojant Unix komandą sort ir pateikiami Unix programos įvedimui prisijungti, kuris netikėtai nepavyko dėl klaidos:

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

Pažiūrėjus akimis rūšiavimo rezultatą paaiškėjo, kad iš esmės rūšiavimas yra teisingas, tačiau sutapus vyriškoms ir moteriškoms pavardėms, moteriškos yra prieš vyriškas:

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

Atrodo kaip rūšiavimo triktis Unicode arba kaip feminizmo apraiška rūšiavimo algoritme. Pirmasis, žinoma, yra labiau tikėtinas.

Kol kas tai atidėkime prisijungti ir sutelkti dėmesį į sort. Pabandykime išspręsti problemą naudodamiesi moksliniais pokštais. Pirmiausia pakeiskime lokalę iš lt apie ru_RU. Norint rūšiuoti, pakaktų nustatyti aplinkos kintamąjį LC_COLLATE, bet negaiškime laiko smulkmenoms:

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

Niekas nepasikeitė.

Pabandykime perkoduoti failus į vieno baito koduotę:

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

Vėl niekas nepasikeitė.

Nieko nepadarysi, sprendimo teks ieškoti internete. Tiesiogiai apie rusiškas pavardes nieko nėra, bet kyla klausimų dėl kitų rūšiavimo keistenybių. Pavyzdžiui, čia yra problema: „Unix sort“ traktuoja „-“ (brūkšnelio) simbolius kaip nematomus. Trumpai tariant, eilutės „a-b“, „aa“, „ac“ rūšiuojamos kaip „aa“, „a-b“, „ac“.

Atsakymas visur standartinis: naudokite programuotojo lokalę "C" ir tu būsi laimingas. Pabandykime:

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

Kažkas pasikeitė. Ivanovai išsirikiavo teisinga tvarka, nors Yolkina kažkur paslydo. Grįžkime prie pradinės problemos:

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

Veikė be klaidų, kaip žadėjo internetas. Ir tai nepaisant Yolkinos pirmoje eilutėje.

Atrodo, kad problema išspręsta, bet tik tuo atveju pabandykime kitą rusišką kodavimą - „Windows“. CP1251:

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

Rūšiavimo rezultatas, kaip bebūtų keista, sutaps su lokale "C", ir visas pavyzdys, atitinkamai, veikia be klaidų. Kažkokia mistika.

Nemėgstu programavimo mistikos, nes ji dažniausiai užmaskuoja klaidas. Turėsime rimtai išnagrinėti, kaip tai veikia. sort ir ką tai įtakoja? LC_COLLATE .

Pabaigoje pabandysiu atsakyti į klausimus:

kodėl moterų pavardės buvo surūšiuotos neteisingai?
kodėl LANG=ru_RU.CP1251 pasirodė lygiavertis LANG=C
Kodėl sort и prisijungti įvairių idėjų apie surūšiuotų eilučių tvarką
kodėl visuose mano pavyzdžiuose yra klaidų?
pagaliau kaip surūšiuoti eilutes pagal savo skonį

Rūšiavimas Unicode

Pirmoji stotelė bus techninė ataskaita Nr. 10 pavadinimu Unicode lyginimo algoritmas interneto unicode.org. Ataskaitoje yra daug techninių detalių, todėl leiskite trumpai apibendrinti pagrindines idėjas.

Lyginimas — eilučių „lyginimas“ yra bet kokio rūšiavimo algoritmo pagrindas. Patys algoritmai gali skirtis („burbulas“, „sujungti“, „greitai“), tačiau visi jie naudos eilučių poros palyginimą, kad nustatytų jų pasirodymo tvarką.

Eilučių rūšiavimas natūralia kalba yra gana sudėtinga problema. Net ir paprasčiausiose vieno baito koduotėse raidžių tvarka abėcėlėje, net ir tam tikru būdu besiskirianti nuo anglų lotyniškos abėcėlės, nebesutaps su skaitinių reikšmių, kuriomis šios raidės yra užkoduotos, tvarka. Taigi vokiečių abėcėlėje raidė Ö stovi tarp О и P, ir koduotėje CP850 ji patenka tarp ÿ и Ü.

Galite pabandyti abstrahuotis nuo konkrečios kodavimo ir apsvarstyti „idealias“ raides, kurios yra išdėstytos tam tikra tvarka, kaip tai daroma Unicode. Kodavimai UTF8, UTF16 arba vieno baito KOI8-R (jei reikalingas ribotas Unikodo poaibis) pateiks skirtingus skaitinius raidžių vaizdus, tačiau nurodys tuos pačius pagrindinės lentelės elementus.

Pasirodo, net jei simbolių lentelę sukursime nuo nulio, negalėsime jai priskirti universalios simbolių tvarkos. Skirtingose nacionalinėse abėcėlėse, kuriose naudojamos tos pačios raidės, šių raidžių tvarka gali skirtis. Pavyzdžiui, prancūziškai Æ bus laikomi ligatūra ir surūšiuoti kaip eilutė AE. Norvegų kalba Æ bus atskira raidė, kuri yra po Z. Beje, be ligatūros kaip Æ Yra raidės, parašytos keliais simboliais. Taigi čekų abėcėlėje yra raidė Ch, kuris stovi tarp H и I.

Be abėcėlės skirtumų, yra ir kitų nacionalinių tradicijų, turinčių įtakos rūšiavimui. Visų pirma kyla klausimas: kokia tvarka žodyne turėtų būti žodžiai, sudaryti iš didžiųjų ir mažųjų raidžių? Rūšiavimui taip pat gali turėti įtakos skyrybos ženklų naudojimas. Ispanų kalboje apverstas klaustukas naudojamas klausiamo sakinio pradžioje (Ar jums patinka muzika?). Šiuo atveju akivaizdu, kad klausiamieji sakiniai neturėtų būti grupuojami į atskirą klasterį už abėcėlės ribų, bet kaip surūšiuoti eilutes su kitais skyrybos ženklais?

Aš nesigilinsiu ties eilučių rūšiavimu kalbomis, kurios labai skiriasi nuo europietiškų. Atkreipkite dėmesį, kad kalbose, kurių rašymo kryptis iš dešinės į kairę arba iš viršaus į apačią, eilučių simboliai greičiausiai išsaugomi skaitymo tvarka, ir net neabėcėlės rašymo sistemos turi savo būdus, kaip eilutes rūšiuoti po simbolio. . Pavyzdžiui, hieroglifus galima rūšiuoti pagal stilių (Kinų rašmenų klavišai) arba tarimu. Tiesą sakant, neįsivaizduoju, kaip jaustukai turėtų būti išdėstyti, bet jūs taip pat galite sugalvoti ką nors jiems.

Remiantis aukščiau išvardintomis ypatybėmis, buvo suformuluoti pagrindiniai eilučių, pagrįstų Unicode lentelėmis, palyginimo reikalavimai:

eilučių palyginimas nepriklauso nuo simbolių padėties kodų lentelėje;
simbolių sekos, sudarančios vieną simbolį, sumažinamos iki kanoninės formos (A + viršutinis apskritimas yra toks pat kaip Å);
Lyginant eilutes, simbolis nagrinėjamas eilutės kontekste ir, jei reikia, sujungiamas su kaimynais į vieną palyginimo vienetą (Ch čekų kalba) arba yra padalintas į keletą (Æ Prancūzų);
visos nacionalinės ypatybės (abėcėlė, didžiosios/mažosios raidės, skyryba, rašymo tipų tvarka) turi būti sukonfigūruotos iki rankinio eilės priskyrimo (jaustukų);
palyginimas svarbus ne tik rūšiuojant, bet ir daugelyje kitų vietų, pavyzdžiui, nurodant eilučių diapazonus (pakeičiant {A... z} bash);
palyginimas turėtų būti atliktas gana greitai.

Be to, ataskaitos autoriai suformulavo palyginimo savybes, kuriomis algoritmų kūrėjai neturėtų pasikliauti:

palyginimo algoritmas neturėtų reikalauti atskiro simbolių rinkinio kiekvienai kalbai (rusų ir ukrainiečių kalboms būdinga dauguma kirilicos simbolių);
palyginimas neturėtų remtis simbolių tvarka Unikodo lentelėse;
eilutės svoris neturėtų būti eilutės atributas, nes ta pati eilutė skirtinguose kultūriniuose kontekstuose gali turėti skirtingą svorį;
eilučių svoris gali keistis sujungiant arba skaidant (nuo x < y to neseka xz < yz);
skirtingos eilutės, turinčios vienodą svorį, rūšiavimo algoritmo požiūriu laikomos lygiomis. Galimas papildomas tokių eilučių išdėstymas, tačiau tai gali pabloginti veikimą;
Pakartotinio rūšiavimo metu gali būti sukeistos vienodo svorio eilutės. Tvirtumas yra konkretaus rūšiavimo algoritmo, o ne eilučių palyginimo algoritmo savybė (žr. ankstesnę pastraipą);
Rūšiavimo taisyklės laikui bėgant gali keistis, nes kultūros tradicijos tobulėja / keičiasi.

Taip pat numatyta, kad palyginimo algoritmas nieko nežino apie apdorojamų eilučių semantiką. Taigi eilutės, susidedančios tik iš skaitmenų, neturėtų būti lyginamos kaip skaičiai, o angliškų pavadinimų sąrašuose straipsnis (Beatles, The).

Siekiant patenkinti visus šiuos reikalavimus, siūlomas kelių lygių (faktiškai keturių lygių) lentelių rūšiavimo algoritmas.

Anksčiau simboliai eilutėje buvo sumažinti iki kanoninės formos ir sugrupuoti į palyginimo vienetus. Kiekvienam palyginimo vienetui priskiriami keli svoriai, atitinkantys kelis palyginimo lygius. Palyginimo vienetų svoriai yra sutvarkytų aibių elementai (šiuo atveju sveikieji skaičiai), kuriuos galima palyginti daugiau ar mažiau. Ypatinga prasmė IGNORUOTA (0x0) reiškia, kad atitinkamame palyginimo lygyje šis vienetas nėra įtrauktas į palyginimą. Stygų palyginimas gali būti kartojamas kelis kartus, naudojant atitinkamų lygių svarmenis. Kiekviename lygyje dviejų eilučių palyginimo vienetų svoriai lyginami vienas su kitu.

Skirtinguose skirtingų nacionalinių tradicijų algoritmo įgyvendinimuose koeficientų reikšmės gali skirtis, tačiau „Unicode“ standartas apima pagrindinę svorių lentelę - „Numatytoji Unicode rūšiavimo elementų lentelė“ (DUCET). Norėčiau pažymėti, kad nustatant kintamąjį LC_COLLATE iš tikrųjų rodo svorio lentelės pasirinkimą eilučių palyginimo funkcijoje.

Svorio koeficientai DUCET išdėstyta taip:

pirmame lygyje visos raidės sumažinamos iki tos pačios raidės, atsisakoma diakritinių ženklų, nepaisoma skyrybos ženklų (ne visų);
antrame lygyje atsižvelgiama tik į diakritinius ženklus;
trečiajame lygyje atsižvelgiama tik į atvejį;
ketvirtame lygyje atsižvelgiama tik į skyrybos ženklus.

Lyginimas vyksta keliais ėjimais: pirmiausia lyginami pirmojo lygio koeficientai; jei svoriai sutampa, atliekamas pakartotinis palyginimas su antrojo lygio svoriais; tada galbūt trečią ir ketvirtą.

Palyginimas baigiamas, kai eilutėse yra atitinkantys palyginimo vienetai su skirtingais svoriais. Eilutės, turinčios vienodą svorį visuose keturiuose lygiuose, laikomos lygiomis viena kitai.

Šis algoritmas (su krūva papildomų techninių detalių) davė pavadinimą ataskaitai Nr. 10 - "Unicode Collation Algorithm" (ACU).

Štai čia mūsų pavyzdžio rūšiavimo elgesys tampa šiek tiek aiškesnis. Būtų malonu palyginti jį su Unicode standartu.

Norėdami išbandyti įgyvendinimus ACU yra specialus testas, naudojant svorio failą, įgyvendinant DUCET. Svarstyklių faile galite rasti įvairiausių juokingų dalykų. Pavyzdžiui, yra mažongo ir europietiško domino tvarka, taip pat kostiumų tvarka kortų kaladėje (simbolis 1F000 ir toliau). Kortų kostiumai dedami pagal bridžo – PCBT taisykles, o kortos kostiume yra iš eilės T, 2,3, XNUMX... K.

Rankiniu būdu tikrinama, ar eilutės surūšiuotos teisingai pagal DUCET būtų gana varginantis, bet, mūsų laimei, yra pavyzdinis bibliotekos įgyvendinimas darbui su Unicode - "Tarptautiniai Unicode komponentai"(ICU).

Šios bibliotekos svetainėje, sukurta m IBM, yra demonstracinių puslapių, įskaitant eilučių palyginimo algoritmo puslapis. Mes įvedame į savo bandymo eilutes su numatytaisiais nustatymais ir, štai, gauname tobulą rusišką rūšiavimą.

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

Beje, svetainė ICU Apdorojant skyrybos ženklus galite rasti palyginimo algoritmo paaiškinimą. Pavyzdžiuose Surinkimo DUK apostrofas ir brūkšnelis ignoruojami.

Unikodas mums padėjo, bet ieškokite keisto elgesio priežasčių sort в Linux teks važiuoti kitur.

Rūšiavimas glibc

Greitas paslaugų šaltinio kodų vaizdas sort iš GNU Core Utils parodė, kad pačiame įrankyje lokalizavimas yra susijęs su dabartinės kintamojo reikšmės spausdinimu LC_COLLATE kai veikia derinimo režimu:

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

Stygų palyginimai atliekami naudojant standartinę funkciją strcoll, o tai reiškia, kad viskas, kas įdomu, yra bibliotekoje glibc.

Apie wiki projektas glibc skirta stygų palyginimui viena pastraipa. Iš šios pastraipos galima suprasti, kad in glibc rūšiavimas pagrįstas mums jau žinomu algoritmu ACU (Unicode lyginimo algoritmas) ir (arba) jam artimu standartu ISO 14651 (Tarptautinis eilučių užsakymas ir palyginimas). Kalbant apie naujausią standartą, reikėtų pažymėti, kad svetainėje standards.iso.org ISO 14651 oficialiai paskelbtas viešai prieinamu, tačiau atitinkama nuoroda nukreipia į neegzistuojantį puslapį. Google grąžina kelis puslapius su nuorodomis į oficialias svetaines, kuriose siūloma įsigyti elektroninę standarto kopiją už šimtą eurų, tačiau trečiame ar ketvirtame paieškos rezultatų puslapyje yra ir tiesioginės nuorodos į PDF. Apskritai standartas praktiškai nesiskiria nuo ACU, bet nuobodesnis skaityti, nes jame nėra aiškių nacionalinių eilučių rūšiavimo ypatybių pavyzdžių.

Įdomiausia informacija apie wiki buvo nuoroda į klaidų sekiklis su diskusija apie eilučių palyginimo įgyvendinimą glibc. Iš diskusijos galima sužinoti, kad glibc naudojamas stygoms palyginti ISOasmeninis stalas Bendra šablonų lentelė (CTT), kurio adresą rasite paraiškoje A standartinis ISO 14651. 2000–2015 m. ši lentelė glibc neturėjo prižiūrėtojo ir gerokai skyrėsi (bent jau išoriškai) nuo dabartinės standarto versijos. Nuo 2015 m. iki 2018 m. vyko adaptacija prie naujos lentelės versijos, o dabar jūs turite galimybę realiai susipažinti su nauja lentelės versija (8 Centos), ir senas (7 Centos).

Dabar, kai turime visą informaciją apie algoritmą ir pagalbines lenteles, galime grįžti prie pradinės problemos ir suprasti, kaip teisingai rūšiuoti eilutes rusiškoje lokalėje.

ISO 14651 / 14652

Mus dominančios lentelės šaltinio kodas CTT daugumoje platinimų Linux yra kataloge /usr/share/i18n/locales/. Pati lentelė yra faile iso14651_t1_common. Tada tai yra failo direktyva kopijuoti iso14651_t1_common įtrauktas į failą iso14651_t1, kuris, savo ruožtu, yra įtrauktas į nacionalines bylas, įskaitant lt и ru_RU. Daugumoje platinimų Linux visi šaltinio failai yra įtraukti į pagrindinį diegimą, tačiau jei jų nėra, turėsite įdiegti papildomą paketą iš platinimo.

Failo struktūra iso14651_t1 gali atrodyti siaubingai daugžodžiai, su neakivaizdžiais vardų darymo taisyklėmis, bet pažiūrėjus viskas gana paprasta. Struktūra aprašyta standarte ISO 14652, kurio kopiją galima atsisiųsti iš svetainės open-std.org. Galima perskaityti kitą failo formato aprašymą specifikacijas POSIX nuo OpenGroup. Kaip alternatyvą standarto skaitymui galite ištirti funkcijos šaltinio kodą lyginti_skaityti в glibc/locale/programs/ld-collate.c.

Failo struktūra atrodo taip:

Pagal numatytuosius nustatymus simbolis naudojamas kaip pabėgimo simbolis, o eilutės pabaiga po simbolio # yra komentaras. Abu simboliai gali būti apibrėžti iš naujo, o tai daroma naujoje lentelės versijoje:

escape_char /
comment_char %

Faile bus tokio formato žetonai arba (Kur x - šešioliktainis skaitmuo). Tai šešioliktainis Unicode kodo taškų kodavimas UCS-4 (UTF-32). Visi kiti elementai kampiniuose skliaustuose (įskaitant , <2> ir panašiai) yra laikomos paprastomis stygų konstantomis, kurios turi mažai reikšmės už konteksto ribų.

Linija LC_COLLATE nurodo, kad toliau prasideda duomenys, apibūdinantys eilučių palyginimą.

Pirma, palyginimo lentelėje nurodomi svorių pavadinimai ir simbolių derinių pavadinimai. Paprastai tariant, dviejų tipų pavadinimai priklauso dviem skirtingiems objektams, tačiau faktiniame faile jie yra sumaišyti. Svorių pavadinimai nurodomi raktiniu žodžiu lyginimo simbolis (palyginimo simbolis), nes lyginant Unikodo simboliai, turintys vienodą svorį, bus laikomi lygiaverčiais simboliais.

Bendras dabartinės failo versijos skyriaus ilgis yra apie 900 eilučių. Iš kelių vietų parsivežiau pavyzdžius, kad parodyčiau pavadinimų savavališkumą ir kelių tipų sintaksę.

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

lyginimo simbolis surašo eilutę OSMANYA svarstyklių pavadinimų lentelėje
lyginimo simbolis .. registruoja vardų seką, susidedančią iš priešdėlio S ir šešioliktainė skaitinė priesaga iš 1D000 į 1D35F.
Ffff в lyginimo simbolis atrodo kaip didelis beženklis sveikasis skaičius šešioliktaine, bet tai tik pavadinimas, kuris gali atrodyti
pavadinimas reiškia kodo tašką koduotėje UCS-4
lyginamasis elementas iš " “ užregistruoja naują pavadinimą Unicode taškų porai.

Kai apibrėžiami svorių pavadinimai, nurodomi tikrieji svoriai. Kadangi palyginimui svarbūs tik santykiai didesni už mažiau, svoriai nustatomi pagal paprastą sąrašo pavadinimų seką. Pirmiausia pateikiami „lengvesni“ svoriai, tada „sunkesni“. Leiskite jums priminti, kad kiekvienam Unicode simboliui priskiriami keturi skirtingi svoriai. Čia jie sujungiami į vieną užsakytą seką. Teoriškai bet koks simbolinis pavadinimas gali būti naudojamas bet kuriame iš keturių lygių, tačiau komentarai rodo, kad kūrėjai mintyse suskirsto pavadinimus į lygius.

% 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

Galiausiai faktinio svorio lentelė.

Svorių skyrius yra įtrauktas į raktinių žodžių eilutes order_start и order_end. Papildomos parinktys order_start nustatyti, kuria kryptimi nuskaitomos eilutės kiekviename palyginimo lygyje. Numatytasis nustatymas yra pirmyn. Skyriaus tekstą sudaro eilutės, kuriose yra simbolio kodas ir keturi jo svarmenys. Simbolio kodas gali būti vaizduojamas pačiu simboliu, kodo tašku arba anksčiau apibrėžtu simboliniu pavadinimu. Svoriai taip pat gali būti suteikiami simboliniams pavadinimams, kodo taškams ar patiems simboliams. Jei naudojami kodo taškai arba simboliai, jų svoris yra toks pat kaip kodo taško skaitinė reikšmė (padėtis Unicode lentelėje). Aiškiai nenurodyti simboliai (kaip suprantu) laikomi priskirtais lentelei su pirminiu svoriu, atitinkančiu poziciją Unicode lentelėje. Ypatinga svorio vertė IGNORĖ reiškia, kad simbolis yra ignoruojamas atitinkamu palyginimo lygiu.

Norėdami parodyti svarstyklių struktūrą, pasirinkau tris gana akivaizdžius fragmentus:

simboliai, kurie visiškai ignoruojami
simboliai, lygiaverčiai skaičiui trys pirmuose dviejuose lygiuose
kirilicos abėcėlės pradžia, kurioje nėra diakritinių ženklų, todėl ji rūšiuojama daugiausia pagal pirmąjį ir trečiąjį lygius.

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

Dabar galite grįžti prie pavyzdžių rūšiavimo nuo straipsnio pradžios. Pasala slypi šioje svorio lentelės dalyje:

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

Matyti, kad šioje lentelėje skyrybos ženklai iš lentelės ASCII (įskaitant tarpą) beveik visada ignoruojamas lyginant eilutes. Vienintelės išimtys yra eilutės, kurios atitinka viską, išskyrus skyrybos ženklus, esančius atitinkamose vietose. Mano pavyzdžio eilutės (po rūšiavimo) palyginimo algoritmui atrodo taip:

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

Atsižvelgiant į tai, kad svarstyklių lentelėje didžiosios raidės rusų kalba yra po mažųjų raidžių (trečiame lygyje sunkesnis nei ), rūšiavimas atrodo visiškai teisingas.

Nustatydami kintamąjį LC_COLLATE=C įkeliama speciali lentelė, kuri nurodo baitų palyginimą

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

Kadangi Unicode kodo taškas Ё yra prieš A, eilutės rūšiuojamos atitinkamai.

Tekstinės ir dvejetainės lentelės

Akivaizdu, kad eilučių palyginimas yra labai dažna operacija ir lentelės analizavimas CTT gana brangi procedūra. Siekiant optimizuoti prieigą prie lentelės, ji sukompiliuojama į dvejetainę formą su komanda localdef.

Komanda localdef kaip parametrus priima failą su nacionalinių charakteristikų lentele (parinktis -i), kuriame visi simboliai pavaizduoti unikodo taškais, ir Unicode taškų bei konkrečios koduotės simbolių atitikimo failas (parinktis -f). Atlikus darbą, lokalei sukuriami dvejetainiai failai, kurių pavadinimas nurodytas paskutiniame parametre.

glibc palaiko du dvejetainius failų formatus: "tradicinį" ir "modernų".

Tradicinis formatas reiškia, kad lokalės pavadinimas yra pakatalogio pavadinimas /usr/lib/locale/. Šiame pakatalogyje saugomi dvejetainiai failai LC_COLLATE, LC_CTYPE, LC_TIME ir taip toliau. Failas LC_IDENTIFICATION yra oficialus lokalės pavadinimas (kuris gali skirtis nuo katalogo pavadinimo) ir komentarai.

Šiuolaikinis formatas apima visų lokalių saugojimą viename archyve /usr/lib/locale/locale-archive, kuris susietas su visų naudojamų procesų virtualiąja atmintimi glibc. Šiuolaikinio formato lokalės pavadinimas yra šiek tiek kanonizuotas - kodavimo pavadinimuose lieka tik skaičiai ir raidės, sumažintos iki mažųjų raidžių. Taigi ru_RU.KOI8-R, bus išsaugotas kaip ru_RU.koi8r.

Įvesties failų ieškoma esamame kataloge, taip pat kataloguose /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ failams CTT ir kodavimo failus, atitinkamai.

Pavyzdžiui, komanda

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

sukompiliuos failą /usr/share/i18n/locales/ru_RU naudojant kodavimo failą /usr/share/i18n/charmaps/MAC-CYRILLIC.gz ir išsaugokite rezultatą /usr/lib/locale/locale-archive po pavadinimu ru_RU.maccyrillic

Jei nustatote kintamąjį LANG = en_US.UTF-8 kad glibc ieškos lokalių dvejetainių failų šioje failų ir katalogų sekoje:

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

Jei lokalė pasitaiko ir tradiciniame, ir šiuolaikiniame formate, pirmenybė teikiama šiuolaikiniam.

Sudarytų lokalių sąrašą galite peržiūrėti naudodami komandą locale -a.

Palyginimo lentelės paruošimas

Dabar, apsiginklavę žiniomis, galite sukurti savo idealią eilučių palyginimo lentelę. Šioje lentelėje reikia teisingai palyginti rusiškas raides, įskaitant raidę Ё, ir tuo pačiu atsižvelgti į skyrybos ženklus pagal lentelę ASCII.

Savos rūšiavimo lentelės paruošimo procesas susideda iš dviejų etapų: svorių lentelės redagavimas ir jos sudarymas dvejetaine forma su komanda localdef.

Kad palyginimo lentelė būtų koreguojama su minimaliomis redagavimo išlaidomis, formatu ISO 14652 Pateikiamos jau esančio stalo svorių reguliavimo skyriai. Skyrius prasideda raktiniu žodžiu pertvarkyti-po ir nurodant poziciją, po kurios atliekamas pakeitimas. Skyrius baigiasi linija pertvarkymo pabaiga. Jei reikia taisyti keletą lentelės skilčių, tada kiekvienai tokiai skyriui sukuriamas skyrius.

Nukopijavau naujas failų versijas iso14651_t1_common и ru_RU iš saugyklos glibc į mano namų katalogą ~/.local/share/i18n/locales/ ir šiek tiek redagavau skyrių LC_COLLATE в ru_RU. Naujos failų versijos visiškai suderinamos su mano versija glibc. Jei norite naudoti senesnes failų versijas, lentelėje turėsite pakeisti simbolinius pavadinimus ir pakeitimo pradžios vietą.

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

Tiesą sakant, reikėtų pakeisti laukus LC_IDENTIFICATION kad jie nurodytų lokalę ru_MY, bet mano pavyzdyje to nereikėjo, nes neįtraukiau archyvo į lokalių paiešką lokalė-archyvas.

Kad localdef dirbo su failais mano aplanke per kintamąjį I18NPATH Galite pridėti papildomą katalogą įvesties failų paieškai, o dvejetainių failų išsaugojimo katalogą galima nurodyti kaip kelią su pasviraisiais brūkšniais:

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

POSIX daro prielaidą, kad in KALBA galite rašyti absoliučius kelius į katalogus su lokalės failais, pradedant pasviruoju brūkšniu, bet glibc в Linux visi keliai skaičiuojami iš bazinio katalogo, kurį galima nepaisyti naudojant kintamąjį LOCPATH. Po įdiegimo LOCPATH=~/.local/lib/locale/ visų su lokalizavimu susijusių failų bus ieškoma tik mano aplanke. Lokalių archyvas su kintamųjų rinkiniu LOCPATH ignoruojamas.

Štai lemiamas testas:

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

Sveika! Mes tai padarėme!

Kai kurios klaidos

Į pradžioje pateiktus klausimus apie eilučių rūšiavimą jau atsakiau, tačiau dar yra pora klausimų apie klaidas – matomas ir nematomas.

Grįžkime prie pradinės problemos.

Ir programa sort ir programa prisijungti naudokite tas pačias eilučių palyginimo funkcijas iš glibc. Kaip tai atsitiko prisijungti davė rūšiavimo klaidą eilutėse, surūšiuotose pagal komandą sort vietovėje lt_US.UTF-8? Atsakymas paprastas: sort lygina visą eilutę ir prisijungti lygina tik raktą, kuris pagal numatytuosius nustatymus yra eilutės pradžia iki pirmojo tarpo simbolio. Mano pavyzdyje tai sukėlė klaidos pranešimą, nes pirmųjų žodžių rūšiavimas eilutėse neatitiko visų eilučių rūšiavimo.

Lokalė "C" garantuoja, kad surūšiuotose eilutėse pradinės eilutės iki pirmosios tarpo taip pat bus surūšiuotos, tačiau tai tik užmaskuoja klaidą. Galima pasirinkti duomenis (žmones su tomis pačiomis pavardėmis, bet skirtingais vardais), kurie be klaidos pranešimo duotų neteisingą failų sujungimo rezultatą. Jei norime prisijungti sujungtos failo eilutės visu pavadinimu, tada teisingas būdas būtų aiškiai nurodyti lauko skyriklį ir rūšiuoti pagal rakto lauką, o ne pagal visą eilutę. Tokiu atveju sujungimas vyks teisingai ir jokioje lokalėje nebus klaidų:

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

Sėkmingai įvykdytas kodavimo pavyzdys CP1251 yra kita klaida. Faktas yra tas, kad visuose man žinomuose platinimuose Linux paketams trūksta sukompiliuotos lokalės ru_RU.CP1251. Jei sukompiliuota lokalė nerasta, tada sort tyliai naudoja baitų palyginimą, ką mes pastebėjome.

Beje, yra dar vienas nedidelis nesklandumas, susijęs su kompiliuotų lokalių neprieinamumu. Komanda LOCPATH=/tmp lokalė -a pateiks visų vietovių sąrašą lokalė-archyvas, bet su kintamųjų rinkiniu LOCPATH visoms programoms (įskaitant daugumą vieta) šios vietos nebus pasiekiamos.

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

išvada

Jei esate programuotojas, įpratęs manyti, kad eilutės yra baitų rinkinys, tada jūsų pasirinkimas LC_COLLATE=C.

Jei esate kalbininkas arba žodyno sudarytojas, geriau kompiliuokite savo vietovėje.

Jei esate paprastas vartotojas, jums tiesiog reikia priprasti prie to, kad komanda ls -a išveda failus, prasidedančius tašku, sumaišytą su failais, prasidedančiais raide ir Vidurnakčio vadas, kuri naudoja vidines funkcijas pavadinimams rūšiuoti, sąrašo pradžioje pateikia failus, prasidedančius tašku.