Kā Linux Ŕķiro virknes

Ievads

Viss sākās ar īsu skriptu, kuram vajadzēja apvienot adreses informāciju e-pasts darbinieki, kas iegūti no adresātu saraksta lietotāju saraksta, ar darbinieku amatiem, kas iegūti no HR departamenta datu bāzes. Abi saraksti tika eksportēti uz Unicode teksta failiem UTF-8 un saglabāts ar Unix rindu galotnēm.

Saturs mail.txt

Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;[email protected]

Saturs buhg.txt

Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ
ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€

Lai apvienotu, faili tika sakārtoti ar Unix komandu Ŕķirot un iesniegts Unix programmas ievadei pievienoties, kas negaidīti neizdevās ar kļūdu:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ

Apskatot ŔķiroŔanas rezultātu ar acīm, bija redzams, ka kopumā ŔķiroŔana ir pareiza, bet vīrieŔu un sievieŔu uzvārdu sakritības gadījumā sievieŔu uzvārdi ir pirms vīrieŔu uzvārdu:

$> sort buhg.txt
ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š¼Š°Š»ŃŃ€
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ

Izskatās pēc ŔķiroÅ”anas kļūmes Unicode vai pēc feminisma izpausmes ŔķiroÅ”anas algoritmā. Pirmais, protams, ir ticamāks.

Pagaidām atliksim pievienoties un koncentrēties uz Ŕķirot. Mēģināsim atrisināt problēmu, izmantojot zinātnisku poking. Vispirms mainÄ«sim lokalizāciju no lv par ru_ru. Lai sakārtotu, bÅ«tu pietiekami iestatÄ«t vides mainÄ«go LC_COLATE, bet mēs netērēsim laiku sÄ«kumiem:

$> LANG=ru_RU.UTF-8 sort buhg.txt
ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š¼Š°Š»ŃŃ€
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ

Nekas nemainījās.

Mēģināsim pārkodēt failus viena baita 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.

Neko nevar darÄ«t, bÅ«s jāmeklē risinājums internetā. Par krievu uzvārdiem tieÅ”i nekas nav, bet ir jautājumi par citām ŔķiroÅ”anas dÄ«vainÄ«bām. Piemēram, Å”eit ir problēma: unix sort uzskata ā€œ-ā€ (domuzÄ«mes) rakstzÄ«mes par neredzamām. ÄŖsāk sakot, virknes "a-b", "aa", "ac" ir sakārtotas kā "aa", "a-b", "ac".

Atbilde ir standarta visur: izmantojiet programmētāja lokalizāciju "C" un tu būsi laimīgs. Pamēģināsim:

$> LANG=C sort buhg.txt
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ
Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š°Š“Š²Š¾ŠŗŠ°Ń‚

Kaut kas ir mainījies. Ivanovi ierindojās pareizā secībā, lai gan Jolkina kaut kur paslīdēja. Atgriezīsimies pie sākotnējās problēmas:

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

Tas strādāja bez kļūdām, kā solīja internets. Un tas neskatoties uz Yolkina pirmajā rindā.

Šķiet, ka problēma ir atrisināta, bet katram gadījumam izmēģināsim citu krievu kodējumu - Windows CP1251:

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

Å Ä·iroÅ”anas rezultāts, dÄ«vainā kārtā, sakritÄ«s ar lokalizāciju "C", un attiecÄ«gi viss piemērs darbojas bez kļūdām. Kaut kāda mistika.

ProgrammÄ“Å”anā man nepatÄ«k mistika, jo tā parasti maskē kļūdas. Mums bÅ«s nopietni jāizpēta, kā tas darbojas. Ŕķirot un ko tas ietekmē? LC_COLATE .

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

  • kāpēc sievieÅ”u uzvārdi tika sakārtoti nepareizi?
  • kāpēc LANG=ru_RU.CP1251 izrādÄ«jās lÄ«dzvērtÄ«gs LANG=C
  • kāpēc Ŕķirot Šø pievienoties dažādas idejas par sakārtoto virkņu secÄ«bu
  • kāpēc visos manos piemēros ir kļūdas?
  • beidzot, kā sakārtot virknes pēc saviem ieskatiem

KārtoŔana Unicode

Pirmā pietura bÅ«s tehniskais ziņojums Nr.10 ar nosaukumu Unikoda salÄ«dzināŔanas algoritms tieÅ”saistē unicode.org. Ziņojumā ir daudz tehnisku detaļu, tāpēc ļaujiet man sniegt Ä«su galveno ideju kopsavilkumu.

SalÄ«dzināŔana ā€” virkņu ā€œsalÄ«dzināŔanaā€ ir jebkura ŔķiroÅ”anas algoritma pamatā. Algoritmi paÅ”i var atŔķirties ("burbulis", "apvienot", "ātri"), taču tie visi izmantos virkņu pāra salÄ«dzinājumu, lai noteiktu secÄ«bu, kādā tie parādās.

Virkņu kārtoÅ”ana dabiskajā valodā ir diezgan sarežģīta problēma. Pat visvienkārŔākajos viena baita kodējumos burtu secÄ«ba alfabētā, pat kaut kādā veidā atŔķiras no angļu latīņu alfabēta, vairs nesakritÄ«s ar ciparu vērtÄ«bu secÄ«bu, ar kādu Å”ie burti ir kodēti. Tātad vācu alfabētā burts Ɩ stāv starp Šž Šø P, un kodējumā CP850 viņa nonāk starp Ćæ Šø Ɯ.

Varat mēģināt abstrahēties no konkrēta kodējuma un apsvērt ā€œideālosā€ burtus, kas ir sakārtoti noteiktā secÄ«bā, kā tas tiek darÄ«ts Unicode. Kodējumi UTF8, UTF16 vai viens baits KOI8-R (ja ir nepiecieÅ”ama ierobežota Unikoda apakÅ”kopa) sniegs atŔķirÄ«gus burtu ciparu attēlojumus, bet atsauksies uz tiem paÅ”iem pamata tabulas elementiem.

Izrādās, pat ja mēs izveidosim simbolu tabulu no nulles, mēs nevarēsim tai pieŔķirt universālu simbolu secÄ«bu. Dažādos nacionālajos alfabētos, kuros tiek izmantoti vieni un tie paÅ”i burti, Å”o burtu secÄ«ba var atŔķirties. Piemēram, franču valodā Ɔ tiks uzskatÄ«ts par ligatÅ«ru un sakārtots kā virkne AE. Norvēģu valodā Ɔ bÅ«s atseviŔķa vēstule, kas atrodas pēc Z. Starp citu, papildus ligatÅ«rām patÄ«k Ɔ Ir burti, kas rakstÄ«ti ar vairākiem simboliem. Tātad čehu alfabētā ir burts Ch, kas stāv starp H Šø I.

Papildus alfabēta atŔķirÄ«bām ir arÄ« citas nacionālās tradÄ«cijas, kas ietekmē ŔķiroÅ”anu. Jo Ä«paÅ”i rodas jautājums: kādā secÄ«bā vārdnÄ«cā jāparādās vārdiem, kas sastāv no lielajiem un mazajiem burtiem? Å Ä·iroÅ”anu var ietekmēt arÄ« pieturzÄ«mju lietoÅ”ana. Spāņu valodā jautājoÅ”a teikuma sākumā tiek lietota apgriezta jautājuma zÄ«me (Vai tev patÄ«k mÅ«zika?). Å ajā gadÄ«jumā ir skaidrs, ka jautājoÅ”os teikumus nevajadzētu grupēt atseviŔķā klasterÄ« ārpus alfabēta, bet kā sakārtot rindas ar citām pieturzÄ«mēm?

Es nekavÄ“Å”os pie virkņu ŔķiroÅ”anas valodās, kas ļoti atŔķiras no Eiropas valodām. Ņemiet vērā, ka valodās ar rakstÄ«Å”anas virzienu no labās uz kreiso vai no augÅ”as uz leju, rakstzÄ«mes rindās, visticamāk, tiek saglabātas lasÄ«Å”anas secÄ«bā, un pat rakstÄ«Å”anas sistēmām, kas nav alfabēta, ir savi veidi, kā sakārtot rindas pēc rakstzÄ«mes. . Piemēram, hieroglifus var sakārtot pēc stila (ĶīnieÅ”u rakstzÄ«mju taustiņi) vai pēc izrunas. GodÄ«gi sakot, man nav ne jausmas, kā emojis ir jāizkārto, bet arÄ« tām var kaut ko izdomāt.

Pamatojoties uz iepriekÅ” uzskaitÄ«tajām funkcijām, tika formulētas pamatprasÄ«bas virkņu salÄ«dzināŔanai, pamatojoties uz Unikoda tabulām:

  • virkņu salÄ«dzināŔana nav atkarÄ«ga no rakstzÄ«mju atraÅ”anās vietas kodu tabulā;
  • rakstzÄ«mju secÄ«bas, kas veido vienu rakstzÄ«mi, tiek reducētas lÄ«dz kanoniskajai formai (A + augŔējais aplis ir tāds pats kā ƅ);
  • SalÄ«dzinot virknes, rakstzÄ«me tiek aplÅ«kota virknes kontekstā un, ja nepiecieÅ”ams, tiek apvienota ar tās kaimiņiem vienā salÄ«dzināŔanas vienÄ«bā (Ch čehu valodā) vai ir sadalÄ«ts vairākos (Ɔ franciski);
  • visas nacionālās pazÄ«mes (alfabēts, lielie/mazie burti, pieturzÄ«mes, rakstÄ«Å”anas veidu secÄ«ba) jākonfigurē lÄ«dz manuālai secÄ«bas (emoji) pieŔķirÅ”anai;
  • salÄ«dzināŔana ir svarÄ«ga ne tikai kārtoÅ”anai, bet arÄ« daudzās citās vietās, piemēram, rindu diapazonu norādÄ«Å”anai (aizstāt {A... z} stipri iesist);
  • salÄ«dzināŔana jāveic diezgan ātri.

Turklāt ziņojuma autori formulēja salÄ«dzināŔanas Ä«paŔības, uz kurām algoritmu izstrādātājiem nevajadzētu paļauties:

  • salÄ«dzināŔanas algoritmam nevajadzētu prasÄ«t atseviŔķu rakstzÄ«mju kopu katrai valodai (krievu un ukraiņu valodās ir lielāka daļa kirilicas rakstzÄ«mju);
  • salÄ«dzinājumam nevajadzētu balstÄ«ties uz rakstzÄ«mju secÄ«bu Unikoda tabulās;
  • virknes svars nedrÄ«kst bÅ«t virknes atribÅ«ts, jo vienai un tai paÅ”ai virknei dažādos kultÅ«ras kontekstos var bÅ«t atŔķirÄ«gs svars;
  • rindu svars var mainÄ«ties, apvienojot vai sadalot (no x < y no tā neizriet xz < yz);
  • dažādas virknes ar vienādu svaru tiek uzskatÄ«tas par vienādām no ŔķiroÅ”anas algoritma viedokļa. Šādu virkņu papildu secÄ«bas ievieÅ”ana ir iespējama, taču tas var pasliktināt veiktspēju;
  • Atkārtotas ŔķiroÅ”anas laikā rindas ar vienādu svaru var tikt apmainÄ«tas. Robustums ir noteikta kārtoÅ”anas algoritma Ä«paŔība, nevis virkņu salÄ«dzināŔanas algoritma Ä«paŔība (skatiet iepriekŔējo rindkopu);
  • Å Ä·iroÅ”anas noteikumi laika gaitā var mainÄ«ties, kultÅ«ras tradÄ«cijām pilnveidojoties/mainoties.

Tāpat ir noteikts, ka salÄ«dzināŔanas algoritms neko nezina par apstrādājamo virkņu semantiku. Tādējādi virknes, kas sastāv tikai no cipariem, nevajadzētu salÄ«dzināt kā skaitļus, un angļu valodas nosaukumu sarakstos raksts (Beatles, The).

Lai izpildÄ«tu visas noteiktās prasÄ«bas, tiek piedāvāts daudzlÄ«meņu (faktiski četru lÄ«meņu) tabulu ŔķiroÅ”anas algoritms.

IepriekÅ” rakstzÄ«mes virknē tika reducētas lÄ«dz kanoniskajai formai un sagrupētas 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ārtotu kopu elementi (Å”ajā gadÄ«jumā veseli skaitļi), kurus var salÄ«dzināt vairāk vai mazāk. ÄŖpaÅ”a nozÄ«me Ignorēts (0x0) nozÄ«mē, ka attiecÄ«gajā salÄ«dzināŔanas lÄ«menÄ« Ŕī vienÄ«ba nav iesaistÄ«ta salÄ«dzināŔanā. StÄ«gu salÄ«dzināŔanu var atkārtot vairākas reizes, izmantojot atbilstoÅ”o lÄ«meņu svarus. Katrā lÄ«menÄ« divu rindu salÄ«dzināŔanas vienÄ«bu svari tiek secÄ«gi salÄ«dzināti savā starpā.

Dažādos nacionālo tradÄ«ciju algoritma variantos koeficientu vērtÄ«bas var atŔķirties, taču Unikoda standartā ir iekļauta pamata svaru tabula - "Noklusējuma Unikoda ŔķiroÅ”anas elementu tabula" (DUCET). Es vēlos atzÄ«mēt, ka mainÄ«gā iestatÄ«Å”ana LC_COLATE patiesÄ«bā ir norāde uz svara tabulas atlasi virkņu salÄ«dzināŔanas funkcijā.

Svēruma koeficienti DUCET sakārtots Ŕādi:

  • pirmajā lÄ«menÄ« visi burti tiek reducēti lÄ«dz vienam un tam paÅ”am reÄ£istram, diakritiskās zÄ«mes tiek atmestas, pieturzÄ«mes (ne visas) tiek ignorētas;
  • otrajā lÄ«menÄ« tiek ņemtas vērā tikai diakritiskās zÄ«mes;
  • treÅ”ajā lÄ«menÄ« tiek ņemts vērā tikai gadÄ«jums;
  • ceturtajā lÄ«menÄ« tiek ņemtas vērā tikai pieturzÄ«mes.

SalÄ«dzināŔana notiek vairākos piegājienos: vispirms tiek salÄ«dzināti pirmā lÄ«meņa koeficienti; ja svari sakrÄ«t, tad tiek veikta atkārtota salÄ«dzināŔana ar otrā lÄ«meņa svariem; tad varbÅ«t treŔā un ceturtā.

SalÄ«dzinājums beidzas, kad rindās ir atbilstoÅ”as ā€‹ā€‹salÄ«dzināŔanas vienÄ«bas ar dažādu svaru. Rindas, kurām ir vienāds svars visos četros lÄ«meņos, tiek uzskatÄ«tas par vienādām.

Å is algoritms (ar virkni papildu tehnisko detaļu) deva nosaukumu ziņojumam Nr. 10 - "Unikoda kārtoÅ”anas algoritms" (ACU).

Å eit mÅ«su piemērā redzamā ŔķiroÅ”anas uzvedÄ«ba kļūst nedaudz skaidrāka. BÅ«tu jauki to salÄ«dzināt ar Unicode standartu.

Lai pārbaudÄ«tu implementācijas ACU ir Ä«paÅ”s pārbaude, izmantojot svaru fails, Ä«stenojot DUCET. Svaru failā var atrast visādas smieklÄ«gas lietas. Piemēram, ir madžongs un Eiropas domino, kā arÄ« mastu secÄ«ba kārÅ”u kavā (simbols 1F000 un tālāk). KārÅ”u uzvalki tiek izvietoti saskaņā ar bridža noteikumiem - PCBT, un kārtis uzvalkā ir secÄ«bā T, 2,3, XNUMX... K.

Manuāli pārbaudot, vai rindas ir sakārtotas pareizi atbilstoÅ”i DUCET tas bÅ«tu diezgan nogurdinoÅ”i, bet, par laimi mums, ir priekÅ”zÄ«mÄ«ga bibliotēkas ievieÅ”ana darbam ar Unicode - "Starptautiskie Unikoda komponenti"(ICU).

Å Ä«s bibliotēkas tÄ«mekļa vietnē, kas izstrādāta gadā IBM, ir demonstrācijas lapas, tostarp virkņu salÄ«dzināŔanas algoritma lapa. Mēs ieejam savās testa rindās ar noklusējuma iestatÄ«jumiem, un, lÅ«k, mēs iegÅ«stam perfektu krievu ŔķiroÅ”anu.

ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ
Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š°Š“Š²Š¾ŠŗŠ°Ń‚

Starp citu, vietne ICU SalÄ«dzināŔanas algoritma skaidrojumu var atrast, apstrādājot pieturzÄ«mes. Piemēros SalÄ«dzināŔanas FAQ apostrofs un defise tiek ignorēti.

Unicode mums palÄ«dzēja, bet meklējiet dÄ«vainas uzvedÄ«bas iemeslus Ŕķirot Š² Linux bÅ«s jāiet kaut kur citur.

KārtoŔana programmā glibc

Ātrs utilÄ«tu pirmkodu skats Ŕķirot no GNU Core Utils parādÄ«ja, ka paŔā utilÄ«tprogrammā lokalizācija ir atkarÄ«ga no mainÄ«gā paÅ”reizējās vērtÄ«bas drukāŔanas LC_COLATE kad darbojas atkļūdoÅ”anas režīmā:

$ sort --debug buhg.txt > buhg.srt
sort: using ā€˜en_US.UTF8ā€™ sorting rules

Virkņu salÄ«dzināŔana tiek veikta, izmantojot standarta funkciju strcoll, kas nozÄ«mē, ka viss interesantais ir bibliotēkā glibc.

uz Wiki projekts glibc veltÄ«ta stÄ«gu salÄ«dzināŔanai viena rindkopa. No Ŕī punkta var saprast, ka in glibc ŔķiroÅ”anas pamatā ir mums jau zināms algoritms ACU (Unikoda salÄ«dzināŔanas algoritms) un/vai standartam tuvu tam ISO 14651 (Starptautiskā virkņu sakārtoÅ”ana un salÄ«dzināŔana). AttiecÄ«bā uz jaunāko standartu jāatzÄ«mē, ka vietnē standards.iso.org ISO 14651 oficiāli pasludināts par publiski pieejamu, bet atbilstoŔā saite ved uz neesoÅ”u lapu. Google atgriež vairākas lapas ar saitēm uz oficiālajām vietnēm, kas piedāvā par simts eiro iegādāties standarta elektronisko kopiju, bet treÅ”ajā vai ceturtajā meklÄ“Å”anas rezultātu lapā ir arÄ« tieŔās saites uz PDF. Kopumā standarts praktiski neatŔķiras no ACU, taču ir garlaicÄ«gāk lasāms, jo tajā nav skaidru piemēru par virkņu ŔķiroÅ”anas nacionālajām iezÄ«mēm.

Interesantākā informācija par Wiki bija saite uz kļūdu izsekotājs ar diskusiju par virkņu salÄ«dzināŔanas ievieÅ”anu glibc. No diskusijas to var uzzināt glibc izmanto, lai salÄ«dzinātu virknes ISOpersonÄ«gais galds Kopējo veidņu tabula (CTT), kuras adrese atrodama pieteikumā A standarta ISO 14651. Laikā no 2000. lÄ«dz 2015. gadam Ŕī tabula glibc nebija uzturētāja un bija diezgan atŔķirÄ«gs (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 tagad jums ir iespēja dzÄ«vē satikt jaunu tabulas versiju (8 CentOS), un vecs (7 CentOS).

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

ISO 14651 / 14652

MÅ«s interesējoŔās tabulas pirmkods CTT lielākajā daļā izplatÄ«Å”anu Linux ir katalogā /usr/share/i18n/locales/. Pati tabula ir failā iso14651_t1_common. Tad Ŕī ir faila direktÄ«va kopēt iso14651_t1_common iekļauts failā iso14651_t1, kas savukārt ir iekļauts nacionālajos failos, t.sk lv Šø ru_ru. Lielākajā daļā izplatÄ«Å”anu Linux Visi avota faili ir iekļauti pamata instalācijā, taču, ja to nav, jums bÅ«s jāinstalē papildu pakotne no izplatÄ«Å”anas.

Faila struktÅ«ra iso14651_t1 var Ŕķist Å”ausmÄ«gi runÄ«gs, ar nepārprotamiem vārdu konstruÄ“Å”anas noteikumiem, bet, ja paskatās, tad viss ir pavisam vienkārÅ”i. StruktÅ«ra ir aprakstÄ«ta standartā ISO 14652, kuras kopiju var lejupielādēt no vietnes open-std.org. Vēl vienu faila formāta aprakstu var izlasÄ«t specifikācijas POSIX no OpenGroup. Kā alternatÄ«vu standarta lasÄ«Å”anai varat izpētÄ«t funkcijas avota kodu apkopot_lasÄ«t Š² glibc/locale/programs/ld-collate.c.

Faila struktūra izskatās Ŕādi:

Pēc noklusējuma rakstzīme tiek izmantota kā atsoļa rakstzīme, un rindas beigas pēc rakstzīmes # ir komentārs. Abus simbolus var definēt no jauna, kas tiek darīts jaunajā tabulas versijā:

escape_char /
comment_char %

Failā bÅ«s marÄ·ieri Ŕādā formātā vai (kur x - heksadecimālais cipars). Å is ir Unikoda koda punktu heksadecimālais attēlojums kodējumā UCS-4 (UTF-32). Visi pārējie elementi leņķa iekavās (ieskaitot , un tamlÄ«dzÄ«gi) tiek uzskatÄ«tas par vienkārŔām virkņu konstantēm, kurām ārpus konteksta ir maza nozÄ«me.

String LC_COLATE norāda, ka pēc tam sākas dati, kas apraksta virkņu salÄ«dzināŔanu.

Pirmkārt, salÄ«dzināŔanas tabulā ir norādÄ«ti nosaukumi svariem un nosaukumi simbolu kombinācijām. VispārÄ«gi runājot, abu veidu nosaukumi pieder divām dažādām entÄ«tijām, taču faktiskajā failā tie ir sajaukti. Svaru nosaukumus norāda atslēgvārds salÄ«dzināŔanas simbols (salÄ«dzinājuma rakstzÄ«me), jo, salÄ«dzinot, Unikoda rakstzÄ«mes, kurām ir vienāds svars, tiks uzskatÄ«tas par lÄ«dzvērtÄ«gām rakstzÄ«mēm.

Kopējais sadaļas garums paÅ”reizējā faila redakcijā ir aptuveni 900 rindiņas. Es izvilku piemērus no vairākām vietām, lai parādÄ«tu nosaukumu patvaļību un vairākus sintakses veidus.

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

  • salÄ«dzināŔanas simbols reÄ£istrē virkni OSMANYA svaru nosaukumu tabulā
  • salÄ«dzināŔanas simbols .. reÄ£istrē nosaukumu secÄ«bu, kas sastāv no prefiksa S un heksadecimālais ciparu sufikss no 1D000 lÄ«dz 1D35F.
  • FFFF Š² salÄ«dzināŔanas simbols izskatās kā liels neparakstÄ«ts vesels skaitlis heksadecimālā, bet tas ir tikai nosaukums, kas varētu izskatÄ«ties
  • nosaukums nozÄ«mē koda punktu kodÄ“Å”anā UCS-4
  • salÄ«dzināŔanas elements no "" reÄ£istrē jaunu nosaukumu Unikoda punktu pārim.

Kad svaru nosaukumi ir definēti, tiek norādÄ«ti faktiskie svari. Tā kā salÄ«dzinājumā ir svarÄ«gas tikai relācijas ā€œlielāks par mazākā€, svērumus nosaka vienkārÅ”a saraksta nosaukumu secÄ«ba. Vispirms tiek uzskaitÄ«ti ā€œvieglākieā€ svari, pēc tam ā€œsmagākieā€. AtgādināŔu, ka katrai Unikoda rakstzÄ«mei ir pieŔķirti četri dažādi svari. Å eit tie ir apvienoti vienā sakārtotā secÄ«bā. Teorētiski jebkuru simbolisku nosaukumu varētu izmantot jebkurā no četriem lÄ«meņiem, taču komentāri liecina, ka izstrādātāji garÄ«gi sadala nosaukumus lÄ«meņos.

% 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

Visbeidzot, faktiskā svara tabula.

Svaru sadaļa ir ietverta atslēgvārdu rindās order_start Šø order_end. Papildu iespējas order_start noteikt, kādā virzienā tiek skenētas rindas katrā salÄ«dzināŔanas lÄ«menÄ«. Noklusējuma iestatÄ«jums ir uz priekÅ”u. Sadaļas pamattekstu veido rindas, kurās ir simbola kods un tā četri svari. RakstzÄ«mju kodu var attēlot ar paÅ”u rakstzÄ«mi, koda punktu vai iepriekÅ” definētu simbolisku nosaukumu. Svarus var pieŔķirt arÄ« simboliskiem nosaukumiem, koda punktiem vai paÅ”iem simboliem. Ja tiek izmantoti koda punkti vai rakstzÄ«mes, to svars ir tāds pats kā koda punkta skaitliskā vērtÄ«ba (pozÄ«cija Unikoda tabulā). RakstzÄ«mes, kas nav skaidri norādÄ«tas (kā es saprotu), tiek uzskatÄ«tas par pieŔķirtām tabulai ar primāro svaru, kas atbilst pozÄ«cijai Unicode tabulā. ÄŖpaÅ”a svara vērtÄ«ba Ignorēt nozÄ«mē, ka simbols tiek ignorēts atbilstoŔā salÄ«dzināŔanas lÄ«menÄ«.

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

  • rakstzÄ«mes, kuras tiek pilnÄ«bā ignorētas
  • simboli, kas lÄ«dzvērtÄ«gi skaitlim trÄ«s pirmajos divos lÄ«meņos
  • kirilicas alfabēta sākums, kurā nav diakritiskās zÄ«mes, un tāpēc tas ir sakārtots galvenokārt pēc pirmā un treŔā lÄ«meņa.

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

Tagad varat atgriezties pie piemēru kārtoÅ”anas no raksta sākuma. Slazds atrodas Å”ajā svaru tabulas daļā:

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

Redzams, ka Å”ajā tabulā pieturzÄ«mes no tabulas ASCII (ieskaitot atstarpi) gandrÄ«z vienmēr tiek ignorēts, salÄ«dzinot virknes. VienÄ«gie izņēmumi ir rindas, kas sakrÄ«t visās lietās, izņemot pieturzÄ«mes, kas atrodamas atbilstoŔās pozÄ«cijās. Rindas no mana piemēra (pēc ŔķiroÅ”anas) salÄ«dzināŔanas algoritmam izskatās Ŕādi:

ŠŠ±Š°ŠŗŠ°Š½Š¾Š²ŠœŠøхŠ°ŠøŠ»Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š°Š­Š»Š»Š°ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š²Š°ŠŠ»Š»Š°Š¼Š°Š»ŃŃ€
Š˜Š²Š°Š½Š¾Š²ŠŠ½Š“рŠµŠ¹ŃŠ»ŠµŃŠ°Ń€ŃŒ

Ņemot vērā, ka skalu tabulā lielie burti krievu valodā nāk aiz mazajiem burtiem (treÅ”ajā lÄ«menÄ« smagāks par ), ŔķiroÅ”ana izskatās pilnÄ«gi pareiza.

Iestatot mainÄ«go LC_COLATE=C tiek ielādēta Ä«paÅ”a tabula, kas norāda baitu pa baitam salÄ«dzinājumu

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

Tā kā Unicode koda punkts Š ir pirms A, virknes tiek sakārtotas atbilstoÅ”i.

Teksta un binārās tabulas

AcÄ«mredzot virkņu salÄ«dzināŔana ir ārkārtÄ«gi izplatÄ«ta darbÄ«ba un tabulas parsÄ“Å”ana CTT diezgan dārga procedÅ«ra. Lai optimizētu piekļuvi tabulai, tā tiek apkopota binārā formā ar komandu localdef.

Komanda localdef pieņem kā parametrus failu ar nacionālo raksturlielumu tabulu (opcija -i), kurā visas rakstzīmes attēlo unikoda punkti, un atbilstības fails starp Unikoda punktiem un noteikta kodējuma rakstzīmēm (opcija -f). Darba rezultātā tiek izveidoti binārie faili lokalizācijai ar nosaukumu, kas norādīts pēdējā parametrā.

glibc atbalsta divus bināros failu formātus: "tradicionālo" un "moderno".

Tradicionālais formāts nozÄ«mē, ka lokalizācijas nosaukums ir apakÅ”direktorija nosaukums /usr/lib/locale/. Å ajā apakÅ”direktorijā tiek glabāti binārie faili LC_COLATE, LC_CTYPE, LC_TIME un tā tālāk. Fails LC_IDENTIFICATION satur formālo lokalizācijas nosaukumu (kas var atŔķirties no direktorija nosaukuma) un komentārus.

MÅ«sdienu formāts ietver visu lokalizāciju glabāŔanu vienā arhÄ«vā /usr/lib/locale/locale-archive, kas tiek kartēta uz visu procesu virtuālo atmiņu, kas tiek izmantota glibc. MÅ«sdienu formāta lokalizācijas nosaukums ir pakļauts zināmai kanonizācijai - kodējuma nosaukumos paliek tikai cipari un burti, kas samazināti lÄ«dz mazajiem burtiem. Tātad ru_RU.KOI8-R, tiks saglabāts kā ru_RU.koi8r.

Ievades faili tiek meklēti paÅ”reizējā direktorijā, kā arÄ« direktorijos /usr/share/i18n/locales/ Šø /usr/share/i18n/charmaps/ failiem CTT un kodÄ“Å”anas faili, attiecÄ«gi.

Piemēram, komanda

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

apkopos failu /usr/share/i18n/locales/ru_RU izmantojot kodÄ“Å”anas failu /usr/share/i18n/charmaps/MAC-CYRILLIC.gz un saglabājiet rezultātu /usr/lib/locale/locale-archive zem nosaukuma ru_RU.maccyrillic

Ja iestatāt mainÄ«go LANG = en_US.UTF-8 ka glibc meklēs lokalizācijas bināros failus Ŕādā failu un direktoriju secÄ«bā:

/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 notiek gan tradicionālajā, gan modernajā formātā, tad prioritāte tiek dota modernajam.

Ar komandu var apskatīt apkopoto lokalizāciju sarakstu locale-a.

SalīdzināŔanas tabulas sagatavoŔana

Tagad, apbruņojies ar zināŔanām, varat izveidot savu ideālo virkņu salÄ«dzināŔanas tabulu. Å ajā tabulā pareizi jāsalÄ«dzina krievu burti, ieskaitot burtu Š, un tajā paŔā laikā jāņem vērā pieturzÄ«mes saskaņā ar tabulu ASCII.

Savas ŔķiroÅ”anas tabulas sagatavoÅ”anas process sastāv no diviem posmiem: svaru tabulas rediģēŔana un kompilÄ“Å”ana binārā formā ar komandu localdef.

Lai salÄ«dzināŔanas tabula tiktu koriģēta ar minimālām rediģēŔanas izmaksām, formātā ISO 14652 Ir paredzētas sadaļas esoŔā galda svaru regulÄ“Å”anai. Sadaļa sākas ar atslēgvārdu pārkārtot pēc un norādot pozÄ«ciju, pēc kuras tiek veikta nomaiņa. Sadaļa beidzas ar lÄ«niju pārkārtot-beigas. Ja nepiecieÅ”ams labot vairākas tabulas sadaļas, tad katrai Ŕādai sadaļai tiek izveidota sadaļa.

Es nokopēju jaunas failu versijas iso14651_t1_common Šø ru_ru no krātuves glibc uz manu mājas direktoriju ~/.local/share/i18n/locales/ un nedaudz rediģēju sadaļu LC_COLATE Š² ru_ru. Jaunās failu versijas ir pilnÄ«bā saderÄ«gas ar manu versiju glibc. Ja vēlaties izmantot vecākas failu versijas, tabulā bÅ«s jāmaina simboliskie nosaukumi un vieta, kur sākas aizstāŔana.

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

PatiesÄ«bā bÅ«tu nepiecieÅ”ams mainÄ«t laukus LC_IDENTIFICATION lai tie norādÄ«tu uz lokalizāciju ru_MY, bet manā piemērā tas nebija nepiecieÅ”ams, jo es izslēdzu arhÄ«vu no lokalizāciju meklÄ“Å”anas lokalizācija-arhÄ«vs.

Ka localdef strādāju ar failiem manā mapē, izmantojot mainÄ«go I18NPATH Varat pievienot papildu direktoriju, lai meklētu ievades failus, un direktoriju 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 iekÅ” VALODA jÅ«s varat rakstÄ«t absolÅ«tos ceļus uz direktorijiem ar lokalizācijas failiem, sākot ar slÄ«psvÄ«tru, bet glibc Š² Linux visi ceļi tiek skaitÄ«ti no bāzes direktorija, kuru var ignorēt, izmantojot mainÄ«go LOCPATH. Pēc uzstādÄ«Å”anas LOCPATH=~/.local/lib/locale/ visi ar lokalizāciju saistÄ«tie faili tiks meklēti tikai manā mapē. Lokalizāciju arhÄ«vs ar mainÄ«go komplektu LOCPATH ignorēts.

Šeit ir izŔķiroŔais pārbaudījums:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
ŠŠ±Š°ŠŗŠ°Š½Š¾Š² ŠœŠøхŠ°ŠøŠ»;Š¼Š°Š»ŃŃ€
ŠŠ»ŠŗŠøŠ½Š° Š­Š»Š»Š°;ŠŗрŠ°Š½Š¾Š²Ń‰ŠøцŠ°
Š˜Š²Š°Š½Š¾Š² ŠŠ½Š“рŠµŠ¹;сŠ»ŠµŃŠ°Ń€ŃŒ
Š˜Š²Š°Š½Š¾Š²Š° ŠŠ»Š»Š°;Š°Š“Š²Š¾ŠŗŠ°Ń‚

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

Dažas kļūdas

Uz sākumā uzdotajiem jautājumiem par virkņu ŔķiroÅ”anu jau atbildēju, bet vēl ir pāris jautājumi par kļūdām - redzamām un neredzamām.

Atgriezīsimies pie sākotnējās problēmas.

Un programma Ŕķirot un programmu pievienoties izmantojiet tās paÅ”as virkņu salÄ«dzināŔanas funkcijas no glibc. Kā tas notika pievienoties radÄ«ja kārtoÅ”anas kļūdu rindās, kas sakārtotas pēc komandas Ŕķirot lokalizācijā lv_US.UTF-8? Atbilde ir vienkārÅ”a: Ŕķirot salÄ«dzina visu virkni un pievienoties salÄ«dzina tikai atslēgu, kas pēc noklusējuma ir virknes sākums lÄ«dz pirmajai atstarpes rakstzÄ«mei. Manā piemērā tika parādÄ«ts kļūdas ziņojums, jo pirmo vārdu kārtoÅ”ana rindās neatbilda visu rindu ŔķiroÅ”anai.

Lokalizācija "C" garantē, ka sakārtotajās virknēs tiks sakārtotas arÄ« sākotnējās apakÅ”virknes lÄ«dz pirmajai atstarpei, taču tas tikai maskē kļūdu. Ir iespējams atlasÄ«t datus (cilvēkus ar vienādiem uzvārdiem, bet dažādiem vārdiem), kas bez kļūdas ziņojuma dotu nepareizu failu sapludināŔanas rezultātu. Ja mēs vēlamies pievienoties apvienotas faila rindas pēc pilna nosaukuma, tad pareizais veids bÅ«tu skaidri norādÄ«t lauku atdalÄ«tāju un kārtot pēc atslēgas lauka, nevis pēc visas rindas. Šādā gadÄ«jumā sapludināŔana noritēs pareizi, un nevienā lokalizācijā 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 kodÄ“Å”anas piemērs CP1251 satur citu kļūdu. Fakts ir tāds, ka visos man zināmajos izplatÄ«jumos Linux pakotnēm trÅ«kst kompilētās lokalizācijas ru_RU.CP1251. Ja kompilētā lokalizācija nav atrasta, tad Ŕķirot klusi izmanto baitu pa baitam salÄ«dzinājumu, ko mēs novērojām.

Starp citu, ir vēl viena neliela kļūme, kas saistÄ«ta ar kompilēto lokalizāciju nepieejamÄ«bu. Komanda LOCPATH=/tmp lokalizācija -a sniegs visu lokalizāciju sarakstu lokalizācija-arhÄ«vs, bet ar mainÄ«go kopu LOCPATH visām programmām (ieskaitot lielāko daļu locale) Ŕīs lokalizācijas nebÅ«s pieejamas.

$> 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 esat programmētājs, kurÅ” ir pieradis domāt, ka virknes ir baitu kopa, tad jÅ«su izvēle LC_COLATE=C.

Ja esat valodnieks vai vārdnīcu sastādītājs, labāk kompilējiet savā lokalizācijā.

Ja esat vienkārÅ”s lietotājs, tad jums vienkārÅ”i jāpierod pie tā, ka komanda ls -a izvada failus, kas sākas ar punktu, kas sajaukti ar failiem, kas sākas ar burtu un Pusnakts komandieris, kas izmanto savas iekŔējās funkcijas, lai kārtotu nosaukumus, saraksta sākumā ievieto failus, kas sākas ar punktu.

atsauces

Ziņojums Nr. 10 Unicode salÄ«dzināŔanas algoritms

Rakstzīmju svari vietnē unicode.org

ICU ā€” IBM bibliotēkas ievieÅ”ana darbam ar Unicode.

ŠķiroŔanas tests, izmantojot ICU

Rakstzīmju svars iekŔā ISO 14651

Faila formāta apraksts ar svariem ISO 14652

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

Avots: www.habr.com

Pievieno komentāru