ProHoster > Blogs > Administrācija > Kā Linux sistēmā sort tiek kārtotas rindas

Kā Linux sistēmā sort tiek kārtotas rindas

Ievads

Viss sākās ar īsu skriptu, kas bija paredzēts, lai apvienotu informāciju par adresēm e-pasts darbiniekiem, iegūtiem no pasta sūtījumu lietotāju saraksta, ar darbinieku amatiem, iegūtiem no personāla datubāzes. Abi saraksti tika eksportēti teksta failos Unicode kodējumā UTF-8 un saglabāti ar unix beigām rindām.

Saturs mail.txt

Ivanovs Andrejs;ia@example.com

Saturs buhg.txt

Ivanova Alla;krāvēja
Jolkina Ella;krāvēja
Ivanovs Andrejs;metālists
Abakanovs Mihails;krāvēja

Faili tika kārtoti ar unix komandu kārtoŔana un nodoti unix programmai join, kas negaidīti pabeidza darbu ar kļūdu:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nav kārtots: Ivanovs Andrejs;metālists

Pārskatot kārtoŔanas rezultātu, acīmredzami viss ir pareizi, taču gadījumos, kad ir atbilstoŔi vīrieŔu un sievieŔu uzvārdi, sievietes ir pirms vīrieŔiem:

$> sort buhg.txt
Abakanovs Mihails;krāvēja
Jolkina Ella;krāvēja
Ivanova Alla;krāvēja
Ivanovs Andrejs;metālists

Izskatās, ka tas ir sortÄ“Å”anas kļūda Unicode vai feminisma izpausme sortÄ“Å”anas algoritmā. Pirmais, protams, ir ticamāks.

Atliksim to pagaidām join un koncentrēsimies uz kārtoÅ”ana. Mēģināsim atrisināt uzdevumu ar eksperimentālu pieeju. Sāksim ar vietējās iestatÄ«Å”anas maiņu no en_US uz ru_RU. Lai kārtotu, pietiktu ar vides mainÄ«go iestatÄ«Å”anu LC_COLLATE, taču nesÄ«sim lietas lÄ«dz galam:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanovs Mihails;krāvēja
Jolkina Ella;krāvēja
Ivanova Alla;krāvēja
Ivanovs Andrejs;metālists

Nekas nav mainījies.

Mēģināsim pārcodināt failus vienbaitu kodējumā:

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

Atkal nekas nav mainījies.

Nekas cits neatliek, kā meklēt risinājumu internetā. TieÅ”i par krievu uzvārdiem nav nekā, bet ir jautājumi par citām dÄ«vainÄ«bām sortÄ“Å”anā. LÅ«k, piemēram, Ŕāda problēma: unix sort izturas pret ā€˜-ā€˜ (domuzÄ«me) simboliem kā pret neredzamajiem. ÄŖsi sakot, rindas "a-b", "aa", "ac" tiek kārtotas kā "aa", "a-b", "ac".

Atbilde visur ir standarta: izmantojiet programmētāju vietējo iestatījumu "C" un jums būs laime. Mēģinām:

$> LANG=C sort buhg.txt
Jolkina Ella;krāvēja
Abakanovs Mihails;krāvēja
Ivanovs Andrejs;metālists
Ivanova Alla;advokāts

Kaut kas ir mainījies. Ivanovi sakārtojās pareizā secībā, taču Jolkina kaut kur noslīdēja. Atgriežamies pie sākotnējā uzdevuma:

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

Tas darbojās bez kļūdām, kā solījās internets. Un tas, neskatoties uz Jolkina pirmajā rindā.

Problēma, Ŕķiet, ir atrisināta, bet katrā ziņā pamēģināsim vēl vienu krievu kodējumu ā€” Windows kodējumu. CP1251:

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

Sakārtojuma rezultāts, kā nevis dīvaini, sakritīs ar lokālo iestatījumu. "C", un viss piemērs, attiecīgi, iziet bez kļūdām. Kaut kas mistisks.

Es nemÄ«lu mistiku programmÄ“Å”anā, jo parasti tā apgriež kļūdas. Man bÅ«s nopietni jāpievērÅ”as jautājumam par to, kā tas darbojas. kārtoÅ”ana un uz ko tas ietekmē. LC_COLLATE .

Beigās es mēģināŔu atbildēt uz jautājumiem:

  • kāpēc nepareizi tika sakārtoti sievieÅ”u uzvārdi.
  • kāpēc. LANG=ru_RU.CP1251 izrādÄ«jās ekvivalents. LANG=C.
  • kāpēc kārtoÅ”ana un join atŔķirÄ«gi uzskati par sakārtoto rindu secÄ«bu.
  • kāpēc visos manos piemēros ir kļūdas.
  • visbeidzot, kā sakārtot rindas pēc savām vēlmēm.

SakārtoŔana Unicode.

Pirmais apstāklis bÅ«s tehniskā ziņojuma Nr. 10 ar nosaukumu. Unicode collation algorithm. vietnē unicode.org.. Ziņojums satur daudz tehnisku detaļu, tādēļ es atļauÅ”os sniegt Ä«su kopsavilkumu par pamata idejām.

SalÄ«dzināŔana ā€” "salÄ«dzināŔana" rindām ā€” ir jebkura sakārtoÅ”anas algoritma pamats. PaÅ”i algoritmi var atŔķirties ("burbuļa", "sadraudzÄ«bas", "ātrā"), bet tie visi izmantos salÄ«dzinājumu pāri rindām, lai noteiktu viņu secÄ«bu.

Rindu sakārtoÅ”ana dabiskajā valodā ir diezgan sarežģīts uzdevums. Pat visvienkārŔākajās vienbaita kodÄ“Å”anās gadÄ«jumos burti alfabētā, kas vismaz nedaudz atŔķiras no angļu alfabēta, vairs nesakritÄ«s ar numuru secÄ«bu, ar kuriem Å”ie burti tiek kodēti. Tā vācu alfabētā burts Ɩ atrodas starp O un P, bet kodÄ“Å”anā CP850 tas iekļūst starp Ćæ un Ɯ..

Mēģinot abstrahēties no konkrētās kodÄ“Å”anas, var skatÄ«t "ideālos" burtus, kuri ir sakārtoti kādā secÄ«bā, kā tas veikts Unicode. Kodējumi UTF8, UTF16 vai vienbaita KOI8-R (ja nepiecieÅ”ama ierobežota Unicode apakÅ”kopa) sniegs atŔķirÄ«gas numuriskas reprezentācijas burtiem, tomēr atsauksies uz tiem paÅ”iem pamatvirsmas elementiem.

Izrādās, ka pat izveidojot simbolu tabulu no nulles, mēs nevarēsim noteikt universālo simbolu secÄ«bu. Dažādās nacionālajās alfabētā, kas izmanto vienas un tās paÅ”as burtus, Å”o burtu secÄ«ba var atŔķirties. Piemēram, franču valodā Ɔ tiks uzskatÄ«ta par ligatÅ«ru un tiks kārtojama kā virkne. AESavukārt norvēģu valodā Ɔ tiks uzskatÄ«ta par atseviŔķu burtu, kas atrodas pēc Z. Starp citu, papildus ligatÅ«rām, piemēram, Ɔ pastāv burti, kuri tiek rakstÄ«ti ar vairākiem simboliem. Tādējādi čehu alfabētā ir burts Ch, kas atrodas starp H un I.

Papildus atŔķirÄ«bām alfabētā pastāv arÄ« citas nacionālās tradÄ«cijas, kas ietekmē kārtoÅ”anu. Proti, rodas jautājums: kādā secÄ«bā vārdā, kas sastāv no lielajiem un maziem burtiem, vajadzētu sekot vārdam vārdnÄ«cā? ArÄ« uz kārtoÅ”anu var ietekmēt pieturzÄ«mju lietoÅ”anas Ä«patnÄ«bas. Spāņu valodā jautājuma teikuma sākumā tiek ielikts apgriezts jautājuma zÄ«me (ĀæTe gusta la mĆŗsica?). Å ajā gadÄ«jumā ir acÄ«mredzams, ka jautājuma teikumi nedrÄ«kst grupēties atseviŔķā klasterÄ« ārpus alfabēta, bet kā kārtot virknes ar citām pieturzÄ«mēm?

Es nenodarbosÅ”os ar virkņu kārtoÅ”anu valodās, kas stipri atŔķiras no eiropieÅ”u valodām. Izceļu, ka valodās ar rakstÄ«Å”anas virzienu no labās uz kreiso vai no augÅ”as uz leju simboli virkni, visticamāk, tiek saglabāti lasÄ«Å”anas secÄ«bā, un pat nealfabētiskajās rakstÄ«bās ir savi veidi, kā simbolus kārtot virknes. Piemēram, hieroglifi var tikt kārtoti pēc rakstÄ«bas (Ä·Ä«nieÅ”u hieroglifus) vai pēc izrunas. Kā jākārto emocijas, godÄ«gi sakot, es nevaru iedomāties, bet arÄ« viņiem var izdomāt kādu risinājumu.

Balstoties uz iepriekÅ” minētajām iezÄ«mēm, tika izstrādāti galvenie prasÄ«bas virkņu salÄ«dzināŔanai, pamatojoties uz Unicode tabulām:

  • virkņu salÄ«dzināŔana nav atkarÄ«ga no simbolu pozÄ«cijas kodu tabulā;
  • simbolu secÄ«bas, kas veido vienu simbolu, tiek nodotas kanoniskajā formā (A + augŔējais aplis ir tas pats, kas ƅ);
  • salÄ«dzinot virknes, simbols tiek aplÅ«kots virknes kontekstā un, ja nepiecieÅ”ams, tiek apvienots ar blakus esoÅ”ajiem simboliem vienā salÄ«dzināŔanas vienÄ«bā (Ch čehu valodā) vai tiek sadalÄ«ts vairākos (Ɔ franču valodā);
  • Visām nacionālajām Ä«patnÄ«bām (alfabets, lielie/mazie burti, pieturzÄ«mes, rakstÄ«bas veidu kārtÄ«ba) ir jābÅ«t iestatāmām lÄ«dz pat manuālai kārtÄ«bas pieŔķirÅ”anai (emosmīļi);
  • SalÄ«dzināŔana ir svarÄ«ga ne tikai ŔķiroÅ”anai, bet arÄ« daudzās citās vietās, piemēram, rindu diapazonu noteikÅ”anai (aizvietojot {Aā€¦ я} ar bash);
  • SalÄ«dzināŔanai jānotiek pietiekami ātri.

Turklāt ziņojuma autori ir formulējuÅ”i salÄ«dzināŔanas Ä«paŔības, uz kurām algoritma izstrādātāji nedrÄ«kst paļauties:

  • SalÄ«dzināŔanas algoritmam nevajadzētu prasÄ«t atseviŔķu simbolu kopu katrai valodai (krievu un ukraiņu valodas kopÄ«gi izmanto lielāko daļu kirilicas simbolu);
  • SalÄ«dzināŔana nedrÄ«kst balstÄ«ties uz simbolu kārtÄ«bu Unicode tabulās;
  • Rindas svars nedrÄ«kst bÅ«t rindas atribÅ«ts, jo viena un tā pati rinda dažādos kultÅ«ras kontekstos var iegÅ«t dažādus svarus;
  • Rindu svari var mainÄ«ties apvienojot vai dalot (no x < y nenozÄ«mē, ka xz < yz);
  • Dažādas rindas, kurām ir vienādi svari, tiek uzskatÄ«tas par vienādām ŔķiroÅ”anas algoritma skatÄ«jumā. Papildu Ŕādu rindu kārtÄ«bas ievieÅ”ana ir iespējama, taču tā var pasliktināt veiktspēju;
  • Atkārtotās ŔķiroÅ”anās laikā rindas, kurām ir vienādi svari, var mainÄ«t vietām. UzticamÄ«ba ir konkrēta ŔķiroÅ”anas algoritma Ä«paŔība, bet ne rindu salÄ«dzināŔanas algoritma Ä«paŔība (sk. iepriekŔējo punktu);
  • Å Ä·iroÅ”anas noteikumi var mainÄ«ties laika gaitā, kamēr kultÅ«ras tradÄ«cijas tiek precizētas/vērtētas.

Tāpat ir noteikts, ka salÄ«dzināŔanas algoritmam nav nekādas zināŔanas par apstrādāto rindu semantiku. Tādējādi, rindas, kas sastāv tikai no cipariem, nedrÄ«kst tikt salÄ«dzinātas kā skaitļi, un angļu nosaukumu sarakstos nedrÄ«kst izņemt artikuli (Beatles, The).

Lai apmierinātu visus norādÄ«tos prasÄ«bas, tika piedāvāts daudzlÄ«meņu (faktiski četrlÄ«meņu) tabulas ŔķiroÅ”anas algoritms.

IepriekÅ” simboli rindā tiek pārvērsti kanoniskā formā un grupēti salÄ«dzināŔanas vienÄ«bās. Katrai salÄ«dzināŔanas vienÄ«bai tiek pieŔķirti vairāki svari, kas atbilst vairākiem salÄ«dzināŔanas lÄ«meņiem. SalÄ«dzināŔanas vienÄ«bu svari ir sakārtotas kopas elementi (Å”ajā gadÄ«jumā veseli skaitļi), kurus var salÄ«dzināt lielāks-mazāks. ÄŖpaŔā vērtÄ«ba IGNORED (0x0) nozÄ«mē, ka attiecÄ«gā salÄ«dzinājuma lÄ«menÄ« Ŕī viena nesanāk salÄ«dzināŔanai. Rindas salÄ«dzināŔana var atkārtoties vairākas reizes, izmantojot attiecÄ«go lÄ«meņu svarus. Katram no lÄ«meņiem divu rindu salÄ«dzināŔanas skalas secÄ«gi salÄ«dzina savā starpā.

Dažādās algoritma implementācijās, ņemot vērā dažādas nacionālās tradÄ«cijas, koeficientu vērtÄ«bas var atŔķirties, taču Unicode standarta sastāvā ietilpst pamata svaru tabula ā€” "Noklusējuma Unicode kolācijas elementu tabula" (DUCET). Vēlos atzÄ«mēt, ka mainÄ«gā iestatÄ«Å”ana LC_COLLATE faktiski ir norāde uz svaru tabulas izvēli rindas salÄ«dzināŔanas funkcijā.

Svara koeficienti DUCET ir veidoti Ŕādi:

  • pirmajā lÄ«menÄ« visas burti tiek pārvērsti vienā lietoÅ”anas režīmā, diakrÄ«tiskie zÄ«me tiek izslēgti, pieturzÄ«mes (ne visas) tiek ignorētas;
  • otrajā lÄ«menÄ« tiek ņemtas vērā tikai diakrÄ«tiskās zÄ«mes;
  • treÅ”ajā lÄ«menÄ« tiek ņemts vērā tikai reÄ£istrs;
  • ceturtajā lÄ«menÄ« tiek ņemti vērā tikai pieturzÄ«mes.

SalÄ«dzināŔana notiek vairākos pārejos: vispirms tiek salÄ«dzināti pirmā lÄ«meņa koeficienti; ja svari sakrÄ«t, tiek veikta atkārtota salÄ«dzināŔana ar otrā lÄ«meņa svariem; tad, iespējams, treÅ”ajā un ceturtajā.

SalÄ«dzināŔana beidzas, kad rindās atrodas attiecÄ«gi viena otrai salÄ«dzināŔanas vienÄ«bas ar atŔķirÄ«giem svariem. Rindas, kurām ir vienādi svari visos četros lÄ«meņos, tiek uzskatÄ«tas par lÄ«dzÄ«gām.

Å is algoritms (ar daudzām papildu tehniskām detaļām) deva nosaukumu pārskatam Nr. 10 ā€” "Unicode kolācijas algoritms" (UCA).

Å ajā vietā piemēra ŔķiroÅ”anas uzvedÄ«ba kļūst nedaudz vieglāk saprotama. BÅ«tu labi to salÄ«dzināt ar Unicode standartu.

Lai testētu implementācijas UCA ir pieejams speciāls tests, kas izmanto svara failu, kas ievieÅ” DUCET. Svara failā var atrast dažādas zināmas lietas. Piemēram, tur ir secÄ«ba mahjong kauliņu un Eiropas domino, kā arÄ« kārÅ”u mastu secÄ«ba (simbols 1F000 un tālāk). KārÅ”u masti tiek sakārtoti pēc bridža noteikumiem ā€” PČB, bet kartes masti ā€” secÄ«bā T, 2, 3ā€¦ K.

Rokas pārbaudÄ«Å”ana kārtoÅ”anas precizitāti saskaņā ar DUCET bÅ«tu diezgan nogurdinoÅ”a, taču, par laimi mums, ir izcila Unicode darbÄ«bas bibliotēkas realizācija ā€” "Starptautiskie Unicode komponenti" (ICU).

Å ajā bibliotēkas vietnē, kas izstrādāta IBM, ir demonstrācijas lapas, tostarp lapa ar virkņu salÄ«dzināŔanas algoritmu. Ievadām mÅ«su testÄ“Å”anas virknes ar noklusējuma iestatÄ«jumiem un, ak brÄ«nums, iegÅ«stam ideālu krievu ŔķiroÅ”anu.

Abakanovs Mihails;krāsotājs
Jolkina Ella;krāvējs
Ivanovs Andrejs;slēdzis
Ivanova Alla;advokāts

Starp citu, vietnē ICU var atrast precizējumu, kā darbojas virkņu salÄ«dzināŔanas algoritms, apstrādājot interpunkcijas zÄ«mes. Piemēros Collation FAQ tiek ignorēti apostrofi un defisi.

Unicode mums palÄ«dzēja, bet meklēt iemeslus dÄ«vainai uzvedÄ«bai kārtoÅ”ana par Linux bÅ«s jāmeklē vēl kaut kur citur.

Glasya ŔķiroŔana

Ātrā avota koda apskate utilÄ«tē kārtoÅ”ana no GNU Core Utils parādÄ«ja, ka paŔā utilÄ«tē lokalizācija ir saistÄ«ta ar paÅ”reizējās mainÄ«gā vērtÄ«bas drukāŔanu LC_COLLATE palaižot to atkļūdoÅ”anas režīmā:

$ sort --debug buhg.txt > buhg.srt
sort: izmanto ā€˜en_US.UTF8ā€™ ŔķiroÅ”anas noteikumus

Virkņu salÄ«dzināŔana tiek veikta ar standarta funkciju strcoll, tādējādi viss interesantais atrodas bibliotēkā glibc.

Uz wiki projekta glibc virkņu salÄ«dzināŔanai veltÄ«ts viens paragrāfs. No Ŕī paragrāfa var saprast, ka glibc ŔķiroÅ”ana pamatojas uz mums jau zināmo algoritmu UCA (Unicode ŔķiroÅ”anas algoritms) un/vai uz tam tuvu standartu ISO 14651 (Starptautiskā virkņu kārtoÅ”ana un salÄ«dzināŔana). Par pēdējo standartu jāatzÄ«mē, ka vietnē standards.iso.org ISO 14651 oficiāli paziņots par publiski pieejamu, bet attiecÄ«gā saite ved uz neeksistējoÅ”u lapu. Google sniedz vairākas lapas ar saitēm uz oficiālajām vietnēm, kas piedāvā iegādāties elektronisko kopiju par simtu eiro, bet treÅ”ajā-četurtajā lapā meklÄ“Å”anas rezultātā var atrast arÄ« tieŔās saites uz PDF. Kopumā, standarts praktiski neatŔķiras no UCA, bet ir garlaicÄ«gāk lasāms, jo nesatur spilgtus piemērus par nacionālajām ŔķiroÅ”anas Ä«paŔībām.

Interesantākā informācija vietnē wiki izrādÄ«jās saite uz kļūdu izsekotāju ar diskusijām par virkņu salÄ«dzināŔanas Ä«stenoÅ”anu glibc. No diskusijas var uzzināt, ka glibc virkņu salÄ«dzināŔanai tiek izmantota ISOtabula The Common Template Table (CTT), kuras adresi var atrast standarta A pielikumā ISO 14651. Starp 2000. un 2015. gadu Ŕī tabula glibc nepiederēja pie mÄ«tnes un diezgan ievērojami atŔķīrās (vismaz ārēji) no paÅ”reizējās standarta versijas. No 2015. lÄ«dz 2018. gadam notika pielāgoÅ”anās jaunajai tabulas versijai, un Å”obrÄ«d jums ir iespēja sastapt gan jauno tabulas variantu (CentOS 8), gan veco (CentOS 7).

Tagad, kad mums ir visa informācija par algoritmu un palīgtabulām, varam atgriezties pie sākotnējā jautājuma un saprast, kā pareizi sakārtot rindas krievu lokalizācijā.

ISO 14651/14652

InteresējoŔās tabulas avota kods CTT lielākajā daļā izplatÄ«jumu Linux atrodas katalogā /usr/share/i18n/locales/. Pati tabula atrodas failā iso14651_t1_common. Pēc tam Å”is fails ar direktÄ«vu copy iso14651_t1_common iekļaujas failā iso14651_t1, kas, savukārt, iekļaujas nacionālajos failos, tostarp en_US un ru_RU. Lielākajā daļā izplatÄ«jumu Linux visi avota faili ir iekļauti pamata instalācijā, bet, ja to nav, tad bÅ«s jāinstalē papildus pakotne no izplatÄ«juma.

Faila struktÅ«ra iso14651_t1 var Ŕķist drausmÄ«gi pārblÄ«vēta, ar neiedomājamiem nosaukumu veidoÅ”anas likumiem, bet, ja izprot, tad viss ir diezgan vienkārÅ”i. StruktÅ«ra ir aprakstÄ«ta standarts ISO 14652, tā kopiju var lejupielādēt no vietnes open-std.org. Vēl vienu faila formāta aprakstu var izlasÄ«t specifikācijās POSIX no OpenGroup. Kā alternatÄ«va standarta lasÄ«Å”anai, varat izpētÄ«t funkcijas avota kodus collate_read par glibc/locale/programs/ld-collate.c.

Faila struktūra izskatās Ŕādi:

Noklusējuma iestatÄ«jumos simbols tiek izmantots kā bēgÅ”anas simbols, un rindiņas beigas pēc simbols # ir komentārs. Abus simbolus var pārrakstÄ«t, kas arÄ« tika izdarÄ«ts jaunajā tabulas versijā:

escape_char /
comment_char %

Failā atradÄ«sies tokeni formātā <Uxxxx> vai <Uxxxxxxxx> (kur x ā€” seÅ”padsmito ciparu). Tā ir seÅ”padsmito attēloÅ”ana Unicode koda punktos kodējumā UCS-4 (UTF-32). Visi citi elementi stÅ«ros (ieskaitot <Uxxxx_xxxx>, <2> un tamlÄ«dzÄ«gi), tiek uzskatÄ«ti par vienkārŔām teksta konstantēm, kurām nav Ä«paÅ”as nozÄ«mes ārpus konteksta.

Rinda LC_COLLATE saka mums, ka turpmāk sāksies dati, kas apraksta rindas salīdzināŔanu.

Vispirms tabulā salÄ«dzināŔanai tiek noteikti svaru nosaukumi un simbolu kombināciju nosaukumi. VispārÄ«gi runājot, divi nosaukumu veidi pieder divām dažādām entitātēm, taču reālajā failā tie ir sajaukti. Svaru nosaukumi tiek norādÄ«ti ar atslēgvārdu collating-symbol (salÄ«dzinoÅ”ais simbols), jo salÄ«dzinot Unicode simbolus, kam ir vienādi svari, tiks uzskatÄ«ti par ekvivalentiem simboliem.

Kopējais sadaļas garums paÅ”reizējā faila revÄ«zijā ir apmēram 900 rindu. Es ņēmu piemērus no vairākiem avotiem, lai parādÄ«tu nosaukumu nejauŔību un dažādus sintakses veidus.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantētais lielākais simbols. Saglabājiet Ŕīs saraksta beigās
...
collating-element  no ""
collating-element  no ""

  • collating-symbol reÄ£istrē rindu OSMANYA svaru nosaukumu tabulā
  • collating-symbol .. reÄ£istrē nosaukumu secÄ«bu, kas sastāv no prefiksa S un seÅ”padsmitskaitļa numura sufiksa no 1D000 lÄ«dz 1D35F.
  • FFFF par collating-symbol izskatās kā liels bezzÄ«me skaitlis seÅ”padsmitskaitļu sistēmā, bet <SFFFF> tas ir tikai nosaukums, kas varētu izskatÄ«ties kā <VERYBIGVAL>
  • nosaukums <U0413> apzÄ«mē kodu punktu kodējumā UCS-4
  • collating-element no "" reÄ£istrē jaunu nosaukumu Unicode punktu pārim.

Kad svaru nosaukumi ir noteikti, tiek noteikti paÅ”i svari. Tā kā salÄ«dzināŔanā ir svarÄ«gas tikai attiecÄ«bas lielāks-mazāks, svari tiek noteikti ar vienkārÅ”u nosaukumu uzskaiti. Vispirms tiek uzskaitÄ«ti "vieglāki" svari, pēc tam "smagāki". Atgādinu, ka katram Unicode simbolam ir pieŔķirti četri dažādi svari. Å eit tie ir apkopoti vienotā kārtotā secÄ«bā. Teorētiski, jebkuru simbolisku nosaukumu var izmantot jebkurā no četriem lÄ«meņiem, bet komentāri norāda uz to, ka izstrādātāji garÄ«gi sadala nosaukumus pa lÄ«meņiem.

% Simboliskā svaru pieŔķirŔana

% TreŔā lÄ«meņa svaru pieŔķirÅ”ana




...
% Otrā lÄ«meņa svaru pieŔķirÅ”ana

 % KOMBINIJOÅ ANAS ZEME
 % KOMBINIJOŠANAS KOMATS AUGŠĀ
 % KOMBINIJOŠANAS APGRIEZTS KOMATS AUGŠĀ
...
% Pirmā lÄ«meņa svaru pieŔķirÅ”ana
 % HORIZONTĀLĀ TABULĀCIJA
 % RINDAS PĀRTRAUKŠANA
 % VERTIKĀLĀ TABULĀCIJA
...
 % KIRILICAS MAZA BURTA DE
 % KIRILICAS MAZA BURTA KOMI DE
 % KIRILICAS MAZA BURTA DJE
 % KIRILICAS MAZA BURTA KOMI DJE
 % KIRILICAS MAZA BURTA GJE
 % KIRILICAS MAZA BURTA ZE AR LEJUZKĀRU
 % KIRILICAS MAZA BURTA IE
 % KIRILICAS MAZA BURTA IE AR BREVI
 % KIRILICAS MAZA BURTA UKRAINAS IE
 % KIRILICAS MAZA BURTA ZHE

Visbeidzot, paŔā svaru tabula.

Svaru sekcija ir ietverta rindiņās ar atslēgvārdiem order_start un order_end. Papildu parametri order_start nosaka, kura virzienā rindiņas tiek skatÄ«tas katrā salÄ«dzinājuma lÄ«menÄ«. Noklusējuma iestatÄ«jums ir parametrs forward. Sekcijas saturs sastāv no rindiņām, kas satur simbolu kodu un četrus tā svarus. Simbola kods var tikt attēlots kā pats simbols, kodu punkts vai simboliskā nosaukuma, kas iepriekÅ” definēts. Svarus var noteikt arÄ« simboliskie nosaukumi, kodu punkti vai paÅ”i simboli. Ja tiek izmantoti kodu punkti vai simboli, tad to svars atbilst kodu punkta skaitliskajai vērtÄ«bai (pozÄ«cija Unicode tabulā). Simboli, kas nav skaidri norādÄ«ti (cik es saprotu), tiek uzskatÄ«ti par pieskaitÄ«tiem tabulai ar primārās svara pozÄ«ciju, kas atbilst pozÄ«cijai Unicode tabulā. ÄŖpaÅ”a svara vērtÄ«ba IGNORE norāda, ka attiecÄ«gajā salÄ«dzinājuma lÄ«menÄ« attiecÄ«gais simbols tiek ignorēts.

Lai parādītu svaru struktūru, es izvēlējos trīs diezgan acīmredzamus fragmentus:

  • simboli, kas tiek pilnÄ«bā ignorēti
  • simboli, kas ir ekvivalentÄ«gi skaitlim trÄ«s pirmajos divos lÄ«meņos
  • kirilicā alfabēta sākums, kas nesatur diakritiskās zÄ«mes, un tāpēc tiek Ŕķirots galvenokārt pēc pirmā un treŔā lÄ«meņa.

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

Tagad var atkal atgriezties pie piemēru ŔķiroÅ”anas no raksta sākuma. Problema slēpjas Å”ajā svaru tabulas daļā:

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

Redzams, ka Å”ajā tabulā ir pieturzÄ«mes no tabulas. ASCII (ieskaitot atstarpi) salÄ«dzinot virknes, praktiski vienmēr tiek ignorēts. Izņēmums ir tikai virknēm, kas sakrÄ«t pilnÄ«bā, izņemot pieturzÄ«mes, kas atrodas sakrÄ«tajās pozÄ«cijās. Virknes no mana piemēra (pēc ŔķiroÅ”anas) algoritma salÄ«dzināŔanai izskatās Ŕādi:

AbakanovsMihailsmākslinieks
EļkinaElakranovā
IvanovaAllamalārs
IvanovsAndrejsslēdzis

Ņemot vērā, ka svaru tabulā lielie burti krievu valodā seko maziem burtiem (treÅ”ajā lÄ«menÄ« <CAP> smagāki nekā <MIN>), ŔķiroÅ”ana izskatās absolÅ«ti pareiza.

Iestatot mainÄ«go LC_COLLATE=C ielādējas Ä«paÅ”a tabula, kas nosaka baitu salÄ«dzināŔanu

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

Tā kā Unicode koda punkts Š priekŔā A, tad virknes tiek Ŕķirotas attiecÄ«gi.

Teksta un binārās tabulas

AcÄ«mredzot virknu salÄ«dzināŔana ir ārkārtÄ«gi bieži sastopama operācija, un tabulas analÄ«ze CTT ļoti dārga procedÅ«ra. Lai optimizētu piekļuvi tabulai, tā tiek kompilēta binārā formā ar komandu localedef.

Komanda localedef pieņemot kā parametrus failu ar nacionālo Ä«paŔību tabulu (poga -i), kurā visi simboli ir attēloti ar Unicode punktiem, un failu ar Unicode punktu atbilstÄ«bām konkrētai kodÄ“Å”anai (poga -f). DarbÄ«bas rezultātā tiek izveidoti binārie faili lokalizācijai ar nosaukumu, kas norādÄ«ts pēdējā parametrā.

Glibc atbalsta divus bināro failu formātus: "tradicionālais" un "mūsdienu".

Tradicionālais formāts paredz, ka lokalizācijas nosaukums ir apakŔdirektorijas nosaukums /usr/lib/locale/. Šajā apakŔdirektorijā tiek glabāti binārie faili LC_COLLATE, LC_CTYPE, LC_TIME u.t.t. Fails LC_IDENTIFICATION satur oficiālo lokalizācijas nosaukumu (kas var atŔķirties no direktorijas nosaukuma) un komentārus.

MÅ«sdienu formāts pieņem, ka visas lokalizācijas tiek glabātas vienā arhÄ«vā /usr/lib/locale/locale-archive, kas tiek attēlots virtuālajā atmiņā visiem procesiem, kas to izmanto. glibcLokalizācijas nosaukums mÅ«sdienu formātā tiek pakļauts noteiktai kanonizācijai ā€” kodÄ“Å”anas nosaukumos paliek tikai cipari un burti, kas pārveidoti par maziem burtiem. Tā ru_RU.KOI8-R, tiks saglabāts kā ru_RU.koi8r.

Izejfailus meklē paÅ”reizējā direktorijā, kā arÄ« direktorijās /usr/share/i18n/locales/ un /usr/share/i18n/charmaps/ failiem CTT un kodējumu failiem atbilstoÅ”i.

Piemēram, komanda

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

sastādÄ«s failu /usr/share/i18n/locales/ru_RU izmantojot kodÄ“Å”anas failu /usr/share/i18n/charmaps/MAC-CYRILLIC.gz un saglabās rezultātu /usr/lib/locale/locale-archive ar nosaukumu ru_RU.maccyrillic

Ja iestatāt mainÄ«go LANG=en_US.UTF-8 tad glibc tiks meklēti binārie lokalizācijas faili Ŕādā secÄ«bā failu un direktoriju:

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

Ja lokalizācija sastopama gan tradicionālajās, gan mūsdienu formātā, tad prioritāte tiek dota mūsdienu formātam.

Sarakstu ar kompilētajām lokalizācijām var apskatīt ar komandu locale -a.

Savas salīdzināŔanas tabulas sagatavoŔana

Tagad, apbruņojoties ar zināŔanām, var izveidot savu ideālo salÄ«dzināŔanas tabulu. Å ai tabulai jāspēj pareizi salÄ«dzināt krievu burtus, tostarp burtu Š, un ņemt vērā interpunkcijas zÄ«mes saskaņā ar tabulu ASCII.

Sava salÄ«dzināŔanas tabulas sagatavoÅ”anas procesā ir divi soļi: svara tabulas rediģēŔana un tās kompilÄ“Å”ana binārā formā ar komandu localedef.

Lai salÄ«dzināŔanas tabulu varētu pielāgot ar minimālām rediģēŔanas izmaksām, tai jābÅ«t formātā ISO 14652 ir ir paredzētas svaru korekcijas sadaļas esoÅ”ajā tabulā. Sadaļa sākas ar atslēgvārdu reorder-after un pozÄ«cijas norādÄ«Å”anu, pēc kuras tiek veiktas nomaiņas. Sadaļu noslēdz rinda reorder-end. Ja ir nepiecieÅ”ams labot vairākas tabulas sadaļas, tad tiek izveidota pa sadaļai katram Ŕādam fragmentam.

Es esmu nokopējis jaunās failu versijas iso14651_t1_common un ru_RU no krātuves glibc savam mājas katalogam ~/.local/share/i18n/locales/ un nedaudz rediģējis sadaļu LC_COLLATE par ru_RU. Jaunās failu versijas pilnībā saderīgas ar manu versiju glibc. Ja vēlaties izmantot vecās failu versijas, jums būs jāmaina simboliskie nosaukumi un vieta, no kuras sākas nomaiņa tabulā.

LC_COLLATE
% Kopējiet veidni no ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % EXCLAMATION MARK
 ;;; % QUOTATION MARK
...
 ;;; % RIGHT CURLY BRACKET
 ;;; % TILDE
reorder-end
END LC_COLLATE

PatiesÄ«bā vajadzēja nomainÄ«t laukus LC_IDENTIFICATION tā, lai tie norādÄ«tu uz lokalitāti ru_MY, bet manā piemērā tas nebija nepiecieÅ”ams, jo es izslēdzu lokalitāŔu arhÄ«vu locale-archive.

Lai localedef strādāja ar failiem manā mapē caur mainÄ«go I18NPATH var pievienot papildu katalogu ievades failu meklÄ“Å”anai, bet katalogu bināro failu saglabāŔanai var norādÄ«t kā ceļu ar slÄ«psvÄ«trām:

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

POSIX pieņem, ka LANG var rakstÄ«t absolÅ«tus ceļus uz katalogiem ar lokalitātēm, kas sākas ar slÄ«psvÄ«tru, bet glibc par Linux visus ceļus uzskata no bāzes kataloga, kuru var pārdefinēt caur mainÄ«go LOCPATH. Pēc mainÄ«gā iestatÄ«Å”anas LOCPATH=~/.local/lib/locale/ visi faili, kas saistÄ«ti ar lokalizāciju, tiks meklēti tikai manā mapē. ArhÄ«vs ar lokalitātēm pie iestatÄ«ta mainÄ«gā LOCPATH tiek ignorēts.

Šis ir izŔķiroŔais tests:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanovs Mihails;krāsotājs
Jolkina Ella;krānu operators
Ivanovs Andrejs;metinātājs
Ivanova Alla;advokāts

Jā! Mēs to izdarījām!

Darbs pie kļūdām

Es jau atbildēju uz jautājumiem par rindu kārtoÅ”anu, kas tika uzdoti sākumā, bet vēl palikuÅ”as pāris jautājumu par kļūdām ā€” redzamām un neredzamām.

Atgriezīsimies pie sākotnējā uzdevuma.

Un programma kārtoÅ”ana un programma join izmanto tās paÅ”as virkņu salÄ«dzināŔanas funkcijas no glibc. Kā tā varēja sanākt, join izvadÄ«ja kārtoÅ”anas kļūdu par rindiņām, kuras kārtoja komanda kārtoÅ”ana lokalizācijā en_US.UTF-8? ŠžŃ‚Š²ŠµŃ‚ ŠæрŠ¾ŃŃ‚: kārtoÅ”ana salÄ«dzina rindiņu kopumā, bet join salÄ«dzina tikai atslēgu, kas pēc noklusējuma ir rindiņas sākums lÄ«dz pirmajam atstarpei. Manu piemērā tas noveda pie kļūdas ziņojuma, jo pirmo vārdu kārtoÅ”ana rindiņās nesakrita ar visu rindu kārtoÅ”anu.

Lokalizācija "C" garantē, ka kārtojoÅ”ajās rindiņās sākuma apakÅ”rindas lÄ«dz pirmajam atstarpei arÄ« bÅ«s sakārtotas, taču tas tikai slēpj kļūdu. Ir iespējams izvēlēties tādus datus (cilvēki ar vienādiem uzvārdiem, bet atŔķirÄ«giem vārdiem), kuri bez kļūdas ziņojuma sniegtu nepareizu rezultātu failu apvienoÅ”anā. Ja mēs vēlamies, lai join apvienotu failu rindiņas pēc vārda un uzvārda, tad pareizā pieeja bÅ«s skaidri norādÄ«t lauku atdalÄ«tāju un kārtoÅ”anu pēc atslēgas lauka, nevis pēc visas rindiņas. Šādā gadÄ«jumā gan apvienoÅ”ana notiks pareizi, un nekur lokālē nebÅ«s kļūdu:

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

VeiksmÄ«gi izpildÄ«ts piemērs kodējumā CP1251 satur vēl vienu kļūdu. Proti, ka visās zināmās izplatÄ«jumos Linux paku trÅ«kst kompilētas lokalizācijas ru_RU.CP1251. Ja kompilētā lokalizācija netiek atrasta, tad kārtoÅ”ana klusi izmanto baitu salÄ«dzinājumu, ko arÄ« novērojām.

Starp citu, ir vēl viena neliela kļūda, kas saistÄ«ta ar kompilētu lokalizāciju nepieejamÄ«bu. Komanda LOCPATH=/tmp locale -a izsniegs visu lokalizāciju sarakstu locale-archive, bet, ja ir iestatÄ«ta mainÄ«gā LOCPATH visām programmām (tostarp arÄ« paÅ”a locale) Ŕīs lokalizācijas bÅ«s nepieejamas.

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

Secinājums

Ja tu esi programmētājs, kurÅ” pieradis domāt, ka rindiņas ir baitu kopums, tad tavs izvēle LC_COLLATE=C.

Ja tu esi lingvists vai vārdnīcu sastādītājs, tad tev labāk būtu kompilēt savu lokalizāciju.

Ja tu esi parasts lietotājs, tad tev pietiks pierast pie tā, ka komanda ls -a izsniedz failus, kas sākas ar punktu, kopā ar failiem, kas sākas ar burtu, un Midnight Commander, kas izmanto savas iekŔējās funkcijas, lai sakārtotu nosaukumus, izceļ failus, kas sākas ar punktu, saraksta sākumā.

Saites

Atskaite Nr. 10 Unicode salīdzināŔanas algoritms

Simbolu svari unicode.org

ICU ā€” IBM nodroÅ”inātā bibliotēkas Ä«stenoÅ”ana, kas strādā ar Unicode.

SakārtoŔanas tests ar ICU

Simbolu svari ISO 14651

Faila formāta apraksts ar svariem ISO 14652

Diskusija par virkņu salÄ«dzināŔanu glibc

Avots: habr.com

Iegādājieties uzticamu tÄ«mekļa hostingu ar DDoS aizsardzÄ«bu, VPS VDS serveriem šŸ”„ Iegādājieties uzticamu tÄ«mekļa hostingu ar DDoS aizsardzÄ«bu, VPS VDS serveriem | ProHoster