Sissejuhatus

Kõik algas lühikesest skriptist, mis pidi ühendama teabe töötajate e-posti aadresside kohta, e-mail mis saadud e-posti loendi kasutajate nimekirjast, koos töötajate ametikohtadega, mis saadi personaliosakonna andmebaasist. Mõlemad nimekirjad eksporditi tekstifailidesse Unicode kodeeringuga, UTF-8 ja salvestati Unix'i ridade lõppudega.

Sisu mail.txt

Ivanov Andrei;ia@example.com

Sisu buhg.txt

Ivanova Alla;maaler
Jolkina Ella;kraanajuhiks
Ivanov Andrei;torumees
Abakanov Mihhail;maaler

Failide ühendamiseks sorteeriti need Unix'i käsuga sort ja edastati Unix'i programmile, liitu, mis lõpetas ootamatult vea 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 Andrei;torumees

Sorteerimise tulemuse visuaalne kontroll näitas, et üldiselt on sorteerimine õige, kuid meessoost ja naissoost perekonnanimede kattumiste korral on naised enne mehi:

$> sort buhg.txt
Abakanov Mihhail;maaler
Jolkina Ella;kraanajuhiks
Ivanova Alla;maaler
Ivanov Andrei;torumees

Tundub nagu Unicode sorteerimise viga või nagu feminism sorteerimisalgoritmis. Esimene, muidugi, on usutavam.

Jätame praegu kõrvale liitu ja keskendume sort. Proovime ülesannet lahendada katsetamise meetodil. Alguseks muutkem kohaleks en_US järgnevaga et_RU. Sorteerimiseks piisaks keskkonnamuutuja seadmisest LC_COLLATE, aga me ei jää selliste väikeste asjadega vaeva:

$> LANG=et_RU.UTF-8 sort buhg.txt
Abakanov Mihhail;värvija
Jolkina Ella;kraanajuhataja
Ivanova Alla;värvija
Ivanov Andrei;torumees

Midagi ei ole muutunud.

Proovime faile ühebaidise kodeeringuga ümber kodeerida:

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

Taaskord ei ole midagi muutunud.

Midagi ei ole teha, tuleb leida lahendus internetist. Otseses mõttes venekeelsete perekonnanimede kohta pole midagi, aga on küsimusi teiste sorteerimise eriskummaliste asjade kohta. Näiteks selline probleem: unix sort käsitleb ‘-‘ (kriipsu) märke nähtamatutena. Lühidalt öeldes, read "a-b", "aa", "ac" sorteeritakse nagu "aa", "a-b", "ac".

Vastus on igal pool standardne: kasutage programmeerija kohalikke seadeid "C" ja siis on teil õnn. Proovime:

$> LANG=C sort buhg.txt
Jolkina Ella;kraanajuhataja
Abakanov Mihhail;värvija
Ivanov Andrei;torumees
Ivanova Alla;advokaat

Midagi on muutunud. Ivanov’id on õiges järjekorras, kuid Jolkina on kuhugi kadunud. Naaseme algsele ülesandele:

$> 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 on vaatamata Ёlkini esimesele reale.

Probleem näib olevat lahendatud, kuid igaks juhuks proovime veel üht 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, nagu imelik see ka ei oleks, vastab lokaadile "C", ja kogu näide seega läbib ilma vigadeta. Milline müstika.

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

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

• miks sorteeriti valejärjekorras naissoost perekonnanimesid
• miks LANG=ru_RU.CP1251 osutus ekvivalendiks LANG=C
• miks on sort ja liitu erinevad arusaamad sorteeritud ridade järjekorrast
• miks kõigis mu näidetes on vigu
• lõpuks, kuidas sorteerida ridu oma maitse järgi

Sorteerimine Unicode'is

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

Sorteerimine — "string comparison" on the basis of any sorting algorithm. The algorithms can differ ("bubble", "merge", "quick"), but they all rely on comparing pairs of strings to establish their order.

Sorting strings in natural language is quite a complex issue. Even in the simplest single-byte encodings, the order of letters in an alphabet that differs from the English Latin alphabet won't match the numerical values by which these letters are encoded. For example, in the German alphabet, the letter Ö is positioned between Umbes ja P, while in the encoding CP850 it falls between ÿ ja Ü.

One could try to abstract from a specific encoding and consider "ideal" letters arranged in a certain order, as done in Unicode. Encodings UTF8, UTF16 or single-byte KOI8-R (if a limited subset of Unicode is needed) will provide different numerical representations of letters but will refer to the same elements in the basic table.

Selgub, et isegi sümbolite tabeli nullist koostamisel ei suuda me sellele määrata universaalset sümbolite järjestust. Erinevates rahvuslikes tähestikes, mis kasutavad samu tähti, võib nende tähede järjestus erineda. Näiteks prantsuse keeles Æ peetakse ligatuuriks ja seda sorteeritakse kui stringi. AETaas, norski keeles Æ on see eraldi täht, mis paikneb pärast Z. Muide, lisaks ligatuuridele nagu Æ on olemas tähed, mis on kirjutatud mitme sümboliga. Nii on Tšehhi tähestikus täht Ch, mis asub nende vahel H ja I.

Lisaks tähestike erinevustele on olemas ka teised rahvuslikud traditsioonid, mis mõjutavad sorteerimist. Eriti tõstatub küsimus: millises järjekorras peaksid sõnaraamatutes esinduma suurtähed ja väiketähed? Samuti võivad sorteerimist mõjutada erimärgid. Hispaania keeles asetatakse küsimuse algusesse pööratud küsimärgi märk (¿Te gusta la música?). Sel juhul on ilmne, et küsimustikud ei peaks olema eraldi rühmitatud väljaspool tähestikku, vaid kuidas järjestada ridu koos teiste kirjavahemärgiga?

Ma ei kavatse peatuda ridade järjestamisele keeltes, mis erinevad tugevasti Euroopa keeltest. Märgin, et paremale või ülespoole kirjutamise suunaga keeltes hoitakse sümboleid ridades tõenäoliselt lugemisjärjestuses, ning ka mitte-täheline kirjutamine omab oma viise ridade sümbolite järjekorra seadmiseks. Näiteks võivad hieroglüfid olla järjestatud vastavalt kirjutusviisile (hiina hieroglüfide võtmed) või hääldusele. Kuidas emojid peaksid olema järjestatud, ma ausalt öeldes ei tea, kuid ka nende jaoks võiks midagi välja mõelda.

Ülaltoodud omaduste põhjal on välja töötatud peamised nõuded ridade võrdlemiseks, mis põhinevad Unicode tabelitel:

• ridade võrdlemine ei sõltu sümbolite asukohast kooditabelis;
• sümbolite järjestused, mis moodustavad ühe sümboli, viiakse kanonilisse vormi (A + ülemine ring see on sama mis Å);
• stringide võrdlemisel võetakse sümbol arvesse kontekstis ja vajadusel ühendatakse see naabersümbolitega üheks võrdlemiseüksuseks (Ch tšehhi keeles) või jagatakse mitmeks (Æ prantsuse keeles);
• kõik rahvuslikud omadused (tähestik, suure-/väikese tähtede erinevus, kirjavahemärgid, kirjutamise viiside järjekord) peavad olema seadistatavad kuni käsitsi määratud järjekorrani (emoji);
• võrdlemine on oluline mitte ainult sortimise jaoks, vaid ka paljude teiste kohtade jaoks, näiteks stringide vahemike määramiseks (asendus {A… я} in bash);
• võrdlemine peab toimuma piisavalt kiiresti.

Lisaks on aruande autorid formuleerinud võrdlemise omadused, millele algoritmi arendajad ei peaks tuginema:

• võrdlemise algoritm ei tohiks nõuda iga keele jaoks eraldi sümbolite kogumit (vene ja ukraina keel kasutavad suuresti samu kirillitsa sümboleid);
• võrdlemine ei tohiks tugineda sümbolite järjekorrale Unicode tabelites;
• stringi kaal ei tohiks olla stringi atribuut, kuna sama string erinevates kultuurilistes kontekstides võib omada erinevat kaalu;
• tekstide kaalud võivad muutuda sulandumisel või jagunemisel (näiteks x < y ei tähenda, et xz < yz);
• erinevad tekstid, millel on samad kaalud, loetakse sortimisalgoritmi seisukohalt võrdsed. Täiendava järjestuse kehtestamine nende tekstide vahel on võimalik, kuid see võib halvendada jõudlust;
• korduvate sortimiste puhul võivad võrdselt kaalutud tekstid omavahel kohtasid vahetada. Stabiilsus on konkreetse sortimisalgoritmi omadus, mitte tekstide võrdlemise algoritmi omadus (vt eelmist punkti);
• sortimisreeglid võivad aja jooksul muutuda kultuuriliste traditsioonide täpsustamise/muutmise tõttu.

Samuti on sätestatud, et võrdlemisalgoritm ei tea midagi võrreldavate tekstide semantikast. Seega ei tohiks numbritest koosnevaid tekstid võrrelda numbritena ning ingliskeelsetes nimedes ei tohi artiklit välja jätta (Beatles, The).

Kõikide tõstatatud nõuete rahuldamiseks on välja töötatud mitmetasandiline (tegelikult neljatase) tabeli sortimisalgoritm.

Eelnevalt tuuakse stringi sümbolid kanoniliseks ja rühmitatakse võrdlemiseks ühikuteks. Iga võrdlusühikule omistatakse mitu kaalu vastavalt erinevatele võrdlustasanditele. Võrdlusüksuste kaalud on järjestatud hulkade elemendid (antud juhul täisarvud), mida saab võrrelda suurem-vähem suhtega. Eriline väärtus IGNORED (0x0) tähendab, et vastaval võrdlustasandil antud üksus ei osale võrdluses. Stringide võrdlemine võib toimuda korduvalt, kasutades vastavate tasemete kaalu. Iga taseme võrdlusühikute kaalu võrreldakse järjestikku omavahel.

Erinevates algoritmi rakendustes eri rahvuslike traditsioonide jaoks võivad koefitsientide suurused erineda, kuid Unicode'i standardisse kuulub põhikaalu tabel — "Default Unicode Collation Element Table" (DUCET). Tahan märkida, et muutuja seadistamine LC_COLLATE on tegelikult viide kaalutabeli valimisele stringide võrdluse funktsioonis.

Kaalukoefitsiendid DUCET on organiseeritud järgmiselt:

• esimese taseme puhul muudetakse kõik tähed ühte soovitud suurusesse, diakriitilised märgid jäetakse välja, kirjavahemärgid (kuid mitte kõik) ignoreeritakse;
• teise taseme puhul arvestatakse ainult diakriitilisi märke;
• kolmanda taseme puhul arvestatakse ainult tähte suurust;
• neljanda taseme puhul arvestatakse ainult kirjavahemärke.

Võrdlemine toimub mitmes etapis: kõigepealt võrreldakse esimesel tasemel koefitsiente; kui kaalud kokkusobivad, järgneb uuesti võrreldes teisel tasemel; seejärel võib läbi viia ka kolmanda ja neljanda taseme.

Võrdlemine lõpeb, kui ridades leidub vastanduvad võrdlemise üksused erinevate kaalu järgi. Ridu, millel on kõikidel neljal tasemel võrdne kaal, peetakse üksteisega võrdsed.

See algoritm (koos paljude lisatehniliste detailidega) andis aruande nr 10 nime — "Unicode Collation Algorithm" (UCA).

Selles kohas muutub meie näite sortimis käitumine natuke arusaadavamaks. Oleks hea võrrelda seda Unicode'i standardiga.

Teostuste testimiseks UCA on olemas spetsiaalne test, kasutades kaalu faili, mis rakendab DUCET. Kaalu failis on erinevaid huvitavaid asju. Näiteks on seal mänge mahjongi ja Euroopa domino joonestus ning kaardikomplekti mastide järjestus (sümbol 1F000 ja edasi). Kaardimastid on paigutatud vastavalt bridži reeglitele — PCHBT, ning mastidesse kuuluvad kaardid on järjestatud järjehoidjate järgi T, 2, 3… K.

Reaalse ridade sortimise õiguse kontrollimine vastavalt DUCET oleks üsna kurnav, kuid õnneks meie jaoks on olemas suurepärane rakendus Unikoodi raamatukogu jaoks — "International Components for Unicode" (ICU).

Selle raamatukogu veebisaidil, mis on loodud IBM, on demonstreerivad lehed, sealhulgas stringide võrdlemise algoritmi leht. Sisestame meie testitavad stringid vaikeseadistustega ja, oh imet, saame ideaalse vene sortimise.

Abakanov Mihhail;värvimees
Jolkina Ella;kraanaoperaator
Ivanov Andre;torumees
Ivanova Alla;advokaat

Muide, saidilt ICU võib leida täpsustusi võrdlemise algoritmi töö kohta kirjavahemärkide käsitlemisel. Näiteks Collation FAQ ignoreeritakse apostroof ja sidekriips.

Unikood aitas meid, kuid kummalise käitumise põhjuseid sort ühes Linux peab otsima mujalt.

Sortimine glibc

Kiire ülevaade tööriista lähtekoodidest sort kohast GNU Core Utils näitas, et tööriist ise lokaliseerimine piirneb praeguse muutuja väärtuse prindimisega LC_COLLATE käivitamisel silumisrežiimis:

$ sort --debug buhg.txt > buhg.srt
sort: kasutab ‘en_US.UTF8’ sorteeringureegleid

Stringide võrdlemine toimub standardse funktsiooni strcoll, seega on kõik huvitav juba raamatukogus glibc.

VDS-l on võimalik installida: wiki projekt glibc stringide võrdlemisega tegeleb üks lõik. Sellest lõigust võib järeldada, et glibc sorteerimine põhineb juba tuttaval algoritmil UCA (The Unicode collation algorithm) ja/või sarnasel standardil ISO 14651 (Rahvusvaheline stringide järjestamine ja võrdlemine). Mis puudutab viimast standardit, siis tuleks märkida, et saidil standards.iso.org ISO 14651 on ametlikult kuulutatud avalikuks, kuid vastav link viib olematusse lehte. Google annab mitu lehte, kus on lingid ametlikele saitidele, mis pakuvad standardi elektroonilise koopia ostmist sada eurot, kuid kolmanda-neljanda lehe otsingutulemustes leiab ka otse lingid PDF. Üldiselt ei erine standard praktiliselt UCA, kuid loetakse igavamalt, kuna see ei sisalda silmapaistvaid näiteid riiklike eripärade sorteerimisel.

Kõige huvitavam teave oli wiki link vea jälgimise süsteemile stringide võrdlemise rakendamise arutamiseks glibc. Arutelust selgub, et glibc stringide võrdlemiseks kasutatakse ISOüht tabelit Common Template Table (CTT), mille aadressi leiate rakendusest A standardist ISO 14651. Aastatel 2000 kuni 2015 ei olnud sellel tabelil hooldajat ja see erineb märgatavalt (vähemalt visuaalselt) praegusest standardi versioonist. Aastatel 2015 kuni 2018 toimus kohandamine uue versiooni tabeliga ja hetkel on teil võimalus kohtuda reaalses elus nii uue versiooniga ( glibc ) kui ka vanaga (CentOS 8Nüüd, kui kogu teave algoritmi ja abitablettide kohta on olemas, saame naasta algse probleemi juurde ja mõista, kuidas õigesti järjestada stringe vene lokaalis.CentOS 7).

ISO 14651/14652

Meid huvitava tabeli lähtekood

enamikus distributsioonides CTT asub kataloogis Linux . Ainult tabel asub failis /usr/share/i18n/locales/iso14651_t1_common . Seejärel kaasatakse see fail direktiivigacopy iso14651_t1_common faili iso14651_t1 , mis omakorda on kaasatud riiklikele failidele, sealhulgas. Enamikus distributsioonides en_US ja et_RU. Enamikus jaotustes Linux kõik algfailid on lisatud põhivaru, kuid kui neid pole, peate installima täiendava paketi jaotusest.

Faili struktuur , mis omakorda on kaasatud riiklikele failidele, sealhulgas see võib tunduda kohutavalt sõnakas, ebamugavate nimevormingureeglitega, kuid kui vaadata, on see piisavalt lihtne. Struktuur on kirjeldatud standardis ISO 14652, mida saab alla laadida veebisaidilt open-std.org. Veel üht faili formaadi kirjelduse saab lugeda spetsifikatsioonides POSIX alates OpenGroup. Standardi lugemise alternatiivina saab uurida funktsiooni allikaid collate_read ühes glibc/locale/programs/ld-collate.c.

Faili struktuur näeb välja järgmine:

Vaikimisi kasutatakse sümbolit kui maskeerimissümbolit ning reavahetus sümbolist # on kommentaar. Mõlemat sümbolit saab üle kirjutada, nagu on tehtud uues tabeli versioonis:

escape_char /
comment_char %

Failis võivad esineda tokenid formaadis <Uxxxx> või <Uxxxxxxxx> (kus x — kuusnurkne number). See on kuusnurkne esitus Unicode'i koodipunktide UCS-4 (UTF-32). Kõik ülejäänud elemendid nurgasulgudes (sealhulgas <Uxxxx_xxxx>, <2> ja sarnased) on peetud lihtsakste stringikonspektideks, millel ei ole konteksti väljaspool erilist tähendust.

String LC_COLLATE ütleb meile, et edasi algavad andmed, mis kirjeldavad stringide võrdlemist.

Esiteks määratakse kaalu nimed võrdlustabelis ning tähemärkide kombinatsioonide nimed. Üldiselt kuuluvad kaks tüüpi nimesid kahele erinevale entiteedile, kuid tegelikus failis on need segamini. Kaalu nimed määratakse märksõnaga collating-symbol (võrdlemise sümbol), kuna Unicode'i sümbolid, millel on samad kaalud, peetakse ekvivalentseteks sümboliteks.

Jooksva faili versiooni sektsiooni kogupikkus on umbes 900 rida. Olen võtnud näiteid mitmest kohast, et näidata nimede meelevaldsust ja mitut tüüpi süntaksit.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % garantii suurim sümboliväärtus. Hoidke selle nimekirja lõpus
...
collating-element  from ""
collating-element  from ""

• collating-symbol registreerib stringi OSMANYA kaalu nimede tabelis
• collating-symbol .. registreerib nimejärjestuse, mis koosneb eesliitest S ja kuuekümnendkümnendast numbrilisest sufiksist alates 1D000 kuni 1D35F.
• FFFF ühes collating-symbol näeb välja nagu suur märkidevaheline täisarv kuuekümnendkümnendises süsteemis, kuid <SFFFF> on lihtsalt nimi, mis võiks välja näha nagu <VERYBIGVAL>
• nimi <U0413> tähendab koodpunkti kodeeringus UCS-4
• collating-element from "" registreerib uue nime kahele Unicode'i punktile.

Kui kaalud on määratud, määratakse tegelikud kaalud. Kuna võrdlemisel on oluline ainult suuremate-väiksemate suhted, määratakse kaalud lihtsa nime loetelu järgi. Esiteks loetletakse "kergemad" kaalud, seejärel "raskaamad". Pean meenutama, et igale Unicode'i sümbolile antakse neli erinevat kaalu. Need on koondatud ühte järjestatud järjestusse. Teoreetiliselt võib iga sümboolne nimi olla kasutatud mis tahes neljal tasemel, kuid kommentaarides märgitakse, et arendajad mõtlevad nimed tasemetena.

% Sümbolite kaalude määramine

% Kolmanda taseme kaalude määramine




...
% Teise taseme kaalude määramine

 % ÜHENDAMINE MADALALINNA
 % ÜHENDAMINE KOMA ÜLE
 % ÜHENDAMINE PÖÖRDKOMA ÜLE
...
% Esimese taseme kaalude määramine
 % HORIZONTAL TABULATSIOON
 % RIDA KATKESTUS
 % VERTIKAALNE TABULATSIOON
...
 % KÜRILI KERGE TÄHE DE
 % KÜRILI KERGE TÄHE KOMI DE
 % KÜRILI KERGE TÄHE DJE
 % KÜRILI KERGE TÄHE KOMI DJE
 % KÜRILI KERGE TÄHE GJE
 % KÜRILI KERGE TÄHE ZE KAEGA
 % KÜRILI KERGE TÄHE IE
 % KÜRILI KERGE TÄHE IE BREVEGA
 % KÜRILI KERGE TÄHE UKRAINLAINE IE
 % KÜRILI KERGE TÄHE ZHE

Lõpuks on ise kaalu tabel.

Kaalude sektsioon on raamis koos märksõnadega order_start ja order_end. Täiendavad parameetrid order_start määravad, millises suunas ridasid igal võrreldava tasemel vaadataks. Vaikesätetena kasutatakse parameetrit forward. Sektsiooni sisu koosneb ridadest, mis sisaldavad sümbolikoodi ja nelja selle kaalu. Sümbolikood võib olla esindatud sümbol ise, koodipunkt või varasemalt määratletud sümboolne nimi. Kaaled saab samuti määrata sümboolsete nimede, koodipunktide või ise sümbolite kaudu. Kui kasutatakse koodipunkte või sümboleid, on nende kaal kooskõlas koodipunkti numbrilise väärtusega (positsioonis Unicode tabelis). Ekslikult mitteüles märgitud sümbolid (nagu ma aru saan) loetakse tabelis, mille esmane kaal vastab nende positsioonile Unicode tabelis. Eriline kaal väärtus IGNORE tähendab, et vastaval võrdlustasemel antud sümbolit ignoreeritakse.

Kaalustruktuuri demonstreerimiseks valisin kolm piisavalt selget fragmenti:

• sümbolid, mida ignoreeritakse täielikult
• sümbolid, mis on ekvivalentne numbriga kolm esimesel kahel tasemel
• vene tähestiku algus, mis ei sisalda diakriitilisi märke ja seetõttu sorteeritakse peamiselt esimese ja kolmanda taseme järgi.

tellimus_algus edasi;edasi;edasi;edasi,positsioon
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % PEALKIRJA ALGUS (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % TEKSTI ALGUS (in 6429)
...
 ;; ;  % KOLMOND DIGIT 
 ;; ;  % TÄIESTI KOLME FULLWIDTH 
 ;; ;  % KOLMNEDA PÄRA KOLM 
 ;; ;  % KOLME KOLME PUNKT 
 ;; ;  % MATEMAACOLILLA BOLD DIGIT KOLM
...
 ;; ;  % KIRILL SILMINE A 
 ;; ;  % KIRILL SUUR A 
 ;; ;  % KIRILL SILMINE A KÄRGIK 
 ;; ;  % KIRILL SILMINE A KÄRGIK
...
 ;; ;  % KIRILL SILMINE BE 
 ;; ;  % KIRILL SUUR BE 
 ;; ;  % KIRILL SILMINE VE 
 ;; ;  % KIRILL SUUR VE
...
tellimus_lõpp

Nüüd on taas võimalik naasta artikli alguses esitatud näidete järjestusse. Probleem peitub selles osas kaalu tabelis:

IGNORE;IGNORE;IGNORE; % RUUM 
 IGNORE;IGNORE;IGNORE; % KÜSIMUSMÄRK 
 IGNORE;IGNORE;IGNORE; % TSITAAT
...

On märgata, et selles tabelis ignoreeritakse interpunktsiooni tavaliselt, ASCII (sealhulgas tühik) stringide võrdlemisel. Eranditeks on vaid stringid, mis on täielikult identsed, välja arvatud vastavates positsioonides esinevad interpunktsioonimärgid. Minu näite stringid (pärast sorteerimist) näevad välja järgmiselt:

AbakanovMikhailPainters
YolkinaElenaScreenwriter
IvanovaAllaPainter
IvanovAndreyJoiner

Arvestades, et kaalutabelis on vene keeles suured tähed väikeste tähtede järel (kolmandal tasemel <CAP> kõvemad kui <MIN>), siis näeb sorteerimine välja täiesti korrektne.

Muutes muutuja LC_COLLATE=C laaditakse eriline tabel, mis määrab byte-taseme 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 asub koodipunkt Ё koha järjekorras A ees, järjestatakse ka stringid vastavalt.

Teksti- ja binaartabelid

On selge, et stringide võrdlemine on äärmiselt sage toiming, samas kui tabeli analüüs CTT on üsna kulukas protseduur. Tabeli juurdepääsu optimeerimiseks kompileeritakse see kahekordsesse vormingusse käsuga localedef.

Meeskond localedef millele antakse parameetritena fail, mis sisaldab riiklike eripärade tabelit (valik -i), milles kõik sümbolid on esitatud Unicode'i punktidena, ja fail, mis seob Unicode'i punkte konkreetse kodeeringu sümbolitega (valik -f). Töö tulemusena luuakse kohalikuks kaksikfailid, mille nimi on määratud viimasena antud parameetris.

Glibc toetab kaht tüüpi kahekordse faili formaate: "traditsiooniline" ja "modernne".

Traditsiooniline formaat eeldab, et lokaali nimi on alamkausta nimi /usr/lib/locale/. Selles alamkaustas hoitakse kaksikfailid LC_COLLATE, LC_CTYPE, LC_TIME ja nii edasi. Fail LC_IDENTIFICATION sisaldab lokaali formaalset nime (mis võib erineda kausta nimest) ja kommentaare.

Kaasaegne formaat eeldab, et kõik lokaalid on salvestatud ühte arhiivi /usr/lib/locale/locale-archive, mis on kaardistatud kõigi protsesside virtuaalsesse mälu, mis seda kasutavad. glibc. Keelja on kaasaegses formaadis läbi teinud teatud kanoniseerimise – kodeeringu nimedes jäävad alles vaid numbrid ja tähed, mis on muudetud väiketähtedeks. Nii ru_RU.KOI8-R, salvestatakse järgmiselt ru_RU.koi8r.

Sisendfailid otsitakse praegusest kataloogist ning ka kataloogidest /usr/share/i18n/locales/ ja /usr/share/i18n/charmaps/ failide CTT ja kodeerimisfailide jaoks 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 nimega ru_RU.maccyrillic

Kui seadistada muutujaks LANG=en_US.UTF-8 siis glibc otsitakse lokaali binaarfailide jaoks järgmises failide ja kataloogide järjestuses:

/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 traditsioonilises kui ka kaasaegses formaadis, antakse eelis kaasaegsele.

Kompileeritud lokaalide loendit saab vaadata käsuga locale -a.

Oma võrdlustabeli koostamine

Nüüd, relvastatuna teadmistega, on võimalik luua oma ideaalne stringide võrdlustabel. See tabel peab õigesti võrdlema vene tähti, sealhulgas tähti Ё, ning arvestama loetlemismärke vastavalt tabeliga ASCII.

Oma sortimistabeli ettevalmistamise protsess koosneb kahest etapist: kaalutabeli redigeerimisest ja selle kompileerimisest binaarvormis käsuga localedef.

Et võrdlustabelit oleks võimalik kohandada minimaalse redigeerimiskuluga, on formaadis ISO 14652 ette nähtud juba olemasoleva tabeli kaalude kohandamise sektsioonid. Sektsioon algab võtmesõnast reorder-after ja positsiooni näitamisest, mille järel toimub asendamine. Sektsiooni lõpetab rida reorder-end. Kui on vaja korrigeerida mitu tabeli osa, luuakse iga sellise osa jaoks oma sektsioon.

Kopeerisin uued versioonid failidest . Seejärel kaasatakse see fail direktiiviga ja et_RU hoidlast glibc oma kodukatalooge ~/.local/share/i18n/locales/ ja muutsin veidi jaotust LC_COLLATE ühes et_RU. Uued faili versioonid on täielikult ühilduvad minu versiooniga glibc. Kui soovite kasutada vanu faili versioone, peate muutma sümboolseid nimesid ja kohta, kust asendamine tabelis algab.

LC_COLLATE
% Kopeeri mall ISO/IEC 14651
kopeerida "iso14651_t1"
järjesta-pärast 
 ;;; % Tühi ruum
 ;;; % Üksik märk
 ;;; % Tsiteerimismärk
...
 ;;; % Parem kurv
 ;;; % Tilde
järjesta-lõpp
LÕPP LC_COLLATE

Tegelikult oleks pidanud muutma väljad LC_IDENTIFICATION niimoodi, et need viitaksid lokaalile ru_MY, kuid minu näites ei olnud see vajalik, kuna ma välistasin otsingust lokaliseerimise arhiivi locale-archive.

Et localedef töötasin failidega oma kaustas läbi muutuja I18NPATH võib lisada täiendava katalooge sisendfailide otsimiseks, ja katalooge binaarfailide salvestamiseks võib määrata teena, mis sisaldab kaldkriipse:

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

POSIX eeldab, et LANG võib kirjutada absoluutsete teedena kataloogidele, kus asuvad lokaalid, mis algavad otsekaldkriipsuga, kuid glibc ühes Linux kõik teed arvestatakse baas-kataloogist, mille võib ületada muutuja LOCPATH. Pärast seadistamist LOCPATH=~/.local/lib/locale/ otsitakse kõiki lokaliseerimisega seotud faile ainult minu kaustast. Lokaalide arhiiv, kui muutuja on seadistatud. LOCPATH ei arvestata.

See test on:

$> LANG=et_EE.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mihhail;värvija
Jolkina Ella;kraanajuht
Ivanov Andrei;sepp
Ivanova Alla;advokaat

Hurraa! Me tegime selle ära!

Vigade parandamine

Olen juba vastanud alguses esitatud stringi sortimise küsimustele, kuid veel on mõned küsimused nähtavatest ja nähtamatutest vigadest.

Naaseme algse ülesande juurde.

Ja programm sort ja programm liitu kasutavad samu stringi võrdlemise funktsioone glibc. Kuidas juhtus, et liitu andis sortimisvea stringidele, mis sorteeriti käsuga sort järgi lokaalis et_US.UTF-8? Ответ прост: sort võrdleb stringi tervikuna, samas kui liitu võrdleb ainult võtit, mis vaikimisi on stringi algus kuni esimese tühikuni. Minu näites viis see veateadeni, kuna lause algusede sortimine ei kattunud täielike stringide sortimisega.

Lokaal "C" garanteerib, et sorteeritud ridade algusosad kuni esimese tühikuni on samuti sorteeritud, kuid see varjab viga. On võimalik leida selliseid andmeid (inimesed, kellel on sama perekonnanimi, kuid erinevad eesnimed), mis ilma veateateta tooksid vale tulemuse failide ühinemisel. Kui soovime, et liitu ühendaks failide ridu FIO järgi, siis õige viis on selgelt määratleda väljade eraldaja ja sorteerida võtmevälja järgi, mitte kogu rida järgi. Sel juhul toimub ühinemine õigesti ja ei esine vigu üheski lokaadis:

$> 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äbi viidud näide kodeeringus CP1251 sisaldab veel ühte viga. Asi on selles, et kõigis tuntud distributsioonides Linux puuduvad pakettides kompileeritud lokaalid ru_RU.CP1251. Kui kompileeritud lokaali ei leita, siis sort kasutab vaikselt byte-per-byte võrdlemist, mida me ka jälgisime.

Muide, on veel üks väike viga, mis on seotud kompileeritud lokaalide kättesaamatusega. Käsk LOCPATH=/tmp locale -a väljastab kõik lokaalid locale-archive, kuid eeldusel, et muutujat on seadistatud LOCPATH kõikidele programmidele (ka kõigele locale) need lokaalid ei ole 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 on harjunud arvama, et stringid on baitide kogum, siis on see sinu valik. LC_COLLATE=C.

Kui oled lingvist või sõnaraamatute koostaja, siis oleks parem, kui compileeriksid oma lokaali.

Kui oled lihtsalt kasutaja, siis piisab, kui harjuda, et käsk ls -a väljastab faile, mis algavad punktiga, segatuna failidega, mis algavad tähega, ning Midnight Commander, mis kasutab oma sisemisi funktsioone nimede sortimiseks, toob failid, mis algavad punktiga, nimekirja algusesse.

Lingid

Aruanne nr 10 Unicode kollektsiooni algoritm

Tähtede kaaluudised unicode.org

ICU — IBM-i Unicode'i töötlusraamatukogu rakendus.

Sortimise test ICU

Tähtede kaalud ISO 14651

Failivormingu kirjeldus kaaludega ISO 14652

Arutelu stringide võrdlemise üle glibc

Allikas: habr.com