ProHoster > Blog > Administrim > Si siht sorton Linux

Si siht sorton Linux

Hyrje

Të gjitha filloi me një skenar të shkurtër, i cili duhej të bashkonte informacionin mbi adresat e-mail e punonjësve, të marrë nga lista e përdoruesve të dërgimit të postave, me pozitat e punonjësve, të marrë nga baza e të dhënave të departamentit të burimeve njerëzore. Të dyja listat ishin eksportuar në skedarë tekstualë në kodimin Unicode UTF-8 dhe ruajtur me përfundimet e linjave në Unix.

PĂ«rmbajtja mail.txt

Ivanov Andrei;ia@example.com

PĂ«rmbajtja buhg.txt

Ivanova Alla;piktore
Jolkina Ella;kraniste
Ivanov Andrei;sanitar
Abakanov Mihail; piktor

Për të bashkuar, skedarët u sortuan nga komanda Unix sort dhe u paraqitën si hyrje në programin Unix bashkohu, i cili përfundoi papritur me një gabim:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nuk është e renditur: Ivanov Andrei;sanitar

Shikimi i rezultatit të renditjes me sy tregoi se në përgjithësi renditja është korrekte, por në rastet e emrave të përputhur meshkuj dhe femra, emrat femra shkojnë para atyre meshkujve:

$> sort buhg.txt
Abakanov Mihail; piktor
Jolkina Ella;kraniste
Ivanova Alla;piktore
Ivanov Andrei;sanitar

Duket si një gabim i renditjes në Unicode ose si një shfaqje e feminizmit në algoritmin e renditjes. E para, sigurisht, është më e besueshme.

Ta lëmë për tani bashkohu dhe të përqendrohemi në sort. Të përpiqemi të zgjidhim problemin me metodën e provave. Për të filluar, të ndryshojmë lokalitetin nga en_US në ru_RU. Për renditjen do të ishte mjaft të vendosnim variablin e ambientit LC_COLLATE, por nuk do të jemi të kopertë:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mihail;piktor
Jolkina Ella;kraniste
Ivanova Alla;piktore
Ivanov Andrei;sanitar

Nuk ndodhi asgjë.

Të përpiqemi të rikodojmë skedarët në një kodim një-byte:

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

Përsëri nuk ndodhi asgjë.

Nuk ka çfarĂ« tĂ« bĂ«jmĂ«, do tĂ« duhet tĂ« kĂ«rkojmĂ« zgjidhje nĂ« internet. Drejt pĂ«r mbi emrat rusĂ« nuk ka asgjĂ«, por ka pyetje rreth çuditĂ«risĂ« sĂ« rendit. Ja, pĂ«r shembull, njĂ« problem i tillĂ«: renditja unix e trajton karakteret ‘-’ (zhargoni) si tĂ« padukshme. NĂ«se e shohim shkurt, fjalitĂ« "a-b", "aa", "ac" renditen si "aa", "a-b", "ac".

Përgjigjja është standarde kudo: përdorni lokalitetin programues "C" dhe do të jeni të lumtur. Provo:

$> LANG=C sort buhg.txt
Jolkina Ella;kraniste
Abakanov Mihail;piktor
Ivanov Andrei;sanitar
Ivanova Alla;advokate

Diçka ka ndryshuar. Ivanovët janë renditur në mënyrë të duhur, por Ёlkina është zvarritur diku. Po kthehemi te detyra e fillimit:

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

Ka funksionuar pa gabime, siç e premtoi interneti. Edhe kjo përkundër Ёlkina në rreshtin e parë.

Duket se problemi Ă«shtĂ« zgjidhur, por pĂ«r çdo rast do tĂ« provojmĂ« njĂ« kodim tjetĂ«r rus—atĂ« nga Windows. CP1251:

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

Rezultati i renditjes, siç Ă«shtĂ« e çuditshme, do tĂ« pĂ«rputhet me lokalitetin "C", dhe e gjithĂ« shembulli, pĂ«rkatĂ«sisht, kalon pa gabime. ËshtĂ« njĂ« mister i çuditshĂ«m.

Nuk më pëlqen misteri në programim, pasi zakonisht maskon gabimet. Më duhet të merrem seriozisht me pyetjen se si funksionon sort dhe çfarë ndikon LC_COLLATE .

Në fund do të përpiqem të përgjigjem në pyetje:

  • pse ishin tĂ« renditura gabimisht mbiemrat femra
  • pse LANG=ru_RU.CP1251 doli tĂ« ishte ekuivalent LANG=C
  • pse sort dhe bashkohu kanĂ« pĂ«rfytyrime tĂ« ndryshme mbi rendin e rreshtave tĂ« renditur
  • pse nĂ« tĂ« gjitha shembujt e mi ka gabime
  • nĂ« fund, si tĂ« renditĂ«sh rreshtat sipas dĂ«shirĂ«s

Renditja në Unicode

Pika e parĂ« do tĂ« jetĂ« raporti teknik № 10 me titullin unicode collation algorithm nĂ« faqen e internetit unicode.org. Raporti pĂ«rmban shumĂ« detaje teknike, kĂ«shtu qĂ« do tĂ« lejoj veten tĂ« jap njĂ« pĂ«rmbledhje tĂ« ideve kryesore.

Renditja — "krahasimi" i rreshtave Ă«shtĂ« baza e çdo algoritmi renditjeje. Algoritmet e vetĂ« mund tĂ« ndryshojnĂ« ("bubullimĂ«", "bashkim", "i shpejtĂ«"), por tĂ« gjitha do tĂ« pĂ«rdorin krahasimin e dy rreshtave pĂ«r tĂ« pĂ«rcaktuar rendin e tyre.

Renditja e rreshtave nĂ« gjuhĂ«n e natyrshme Ă«shtĂ« njĂ« problem mjaft i komplikuar. Edhe nĂ« kodimet mĂ« tĂ« thjeshta me njĂ« bajt, rendi i shkronjave nĂ« alfabet, ndonjĂ«herĂ« ndryshe nga alfabeti anglisht, nuk do tĂ« pĂ«rputhet me rendin e vlerave numerike qĂ« kĂ«to shkronja kodifikohen. KĂ«shtu, nĂ« alfabetin gjerman, shkronja Ö ndodhet midis Q dhe P, ndĂ«rsa nĂ« kodimin CP850 ajo bie midis Ăż dhe Ü.

Mund të përpiqesh të abstraktosh nga kodimi konkret dhe të shqyrtosh "shkronjat ideale" të cilat janë të radhitura në një rend të caktuar, siç bëhet në Unicode. Kodimet UTF8, UTF16 ose një bajt e vetme KOI8-R (nëse nevojitet një nëngrup i kufizuar i Unicode) do të japin reprezentime numerike të ndryshme të shkronjave, por do të referohen në të njëjtët elementë të tabelës themelore.

Kjo tregon se madje edhe nĂ«se ndĂ«rtuam njĂ« tabelĂ« simboresh nga zero, ne nuk do tĂ« mund ta caktojmĂ« njĂ« rend universal tĂ« simboleve. NĂ« alfabetet e ndryshme kombĂ«tare qĂ« pĂ«rdorin tĂ« njĂ«jtat shkronja, rendi i kĂ«tyre shkronjave mund tĂ« ndryshojĂ«. PĂ«r shembull, nĂ« gjuhĂ«n franceze Æ do tĂ« konsiderohet si njĂ« ligaturĂ« dhe do tĂ« renditet si njĂ« varg AE. NĂ« gjuhĂ«n norvegjeze, Æ do tĂ« jetĂ« njĂ« shkronjĂ« e veçantĂ«, e cila ndodhet pas Z. PĂ«r mĂ« tepĂ«r, pĂ«rveç ligaturave si Æ ekzistojnĂ« shkronja qĂ« regjistrohen me disa simbole. KĂ«shtu, nĂ« alphabetin çek, ka shkronjĂ«n Ch, e cila ndodhet mes H dhe I.

PĂ«rveç ndryshimeve nĂ« alfabetet, ekzistojnĂ« edhe tradita tĂ« tjera kombĂ«tare qĂ« ndikojnĂ« nĂ« renditjen. NĂ« veçanti, lind pyetja: nĂ« cilin rend duhet tĂ« ndodhen nĂ« fjalor fjalĂ«t qĂ« pĂ«rbĂ«hen nga shkronja tĂ« mĂ«dha dhe tĂ« vogla? Gjithashtu, renditjen mund ta ndikojnĂ« veçoritĂ« e pĂ«rdorimit tĂ« shenjave tĂ« ndarjes. NĂ« gjuhĂ«n spanjolle, nĂ« fillim tĂ« njĂ« pyetjeje vendoset njĂ« shenjĂ« pyetjeje e kthyer (ÂżTe gusta la mĂșsica?). NĂ« kĂ«tĂ« rast, Ă«shtĂ« e qartĂ« se propozimet pyetĂ«se nuk duhet tĂ« grumbullohen nĂ« njĂ« grup tĂ« veçantĂ« jashtĂ« alfabetit, por si duhet tĂ« renditen vargjet me shenja tĂ« tjera ndarĂ«se?

Nuk do të qëndroj mbi renditjen e vargjeve në gjuhët që dallohen shumë nga ato evropiane. Dua të theksoj se në gjuhët me drejtimin e shkrimit nga e drejta në të majtë ose nga lart poshtë, simbolet në vargje, me sa duket, ruhen në rendin e leximit, dhe madje edhe në shkrime jo-alfabetike ka mënyra të veta për renditjen e simboleve. Për shembull, hieroglifët mund të renditen sipas formës së tyre (çelësat e hieroglifëve kinezë) ose sipas shqiptimit. Si duhet të renditen emoji-t, sinqerisht nuk e di, por edhe për ta mund të mendohet diçka.

Bazuar në veçoritë e përmendura më sipër, janë formuluar kërkesat kryesore për krahasimin e vargjeve të bazuara në tabelat e Unicode:

  • krahasimi i vargjeve nuk varet nga pozita e simboleve nĂ« tabelĂ«n e kodimit;
  • sekuencat e simboleve qĂ« formojnĂ« njĂ« simbol unik, u jepen formĂ«s kanonike (A + rreth i sipĂ«rm Ă«shtĂ« e njĂ«jtĂ« me Å);
  • nĂ« krahasimin e vargjeve, simboli shqyrtohet nĂ« kontekstin e vargut dhe, nĂ«se Ă«shtĂ« e nevojshme, bashkohet me fqinjĂ«t nĂ« njĂ« njĂ«sinĂ« krahasuese (Ch nĂ« çek) ose ndahet nĂ« disa (Æ nĂ« francais);
  • tĂ« gjitha veçoritĂ« kombĂ«tare (alfabeti, shkronjat e mĂ«dha/tĂ« vogla, shenjat e pikĂ«simit, rendi i shkrimeve) duhet tĂ« konfigurohen deri nĂ« emĂ«rimin manual tĂ« rendit (emoji);
  • krahasimi Ă«shtĂ« i rĂ«ndĂ«sishĂ«m jo vetĂ«m pĂ«r renditjen, por edhe nĂ« shumĂ« vende tĂ« tjera, pĂ«r shembull pĂ«r caktimin e intervaleve tĂ« rreshtave (zĂ«vendĂ«simi {A
 ja} nĂ« bash);
  • krahasimi duhet tĂ« kryhet mjaft shpejt.

Për më tepër, autorët e raportit formuluan vetitë e krahasimit, për të cilat zhvilluesit e algoritmeve nuk duhet të mbështeten:

  • algoritmi i krahasimit nuk duhet tĂ« kĂ«rkojĂ« njĂ« grup tĂ« veçantĂ« simbolet pĂ«r çdo gjuhĂ« (gjuha ruse dhe ukrainase pĂ«rdorin shumicĂ«n e simboleve tĂ« cirilikĂ«s sĂ« bashku);
  • krahasimi nuk duhet tĂ« mbĂ«shtetet nĂ« rendin e simboleve nĂ« tabelat Unicode;
  • pesha e njĂ« rreshti nuk duhet tĂ« jetĂ« njĂ« atribut i rreshtit, pasi njĂ«soj si rreshti nĂ« kontekste tĂ« ndryshme kulturore mund tĂ« ketĂ« pesha tĂ« ndryshme;
  • pesha e rreshtave mund tĂ« ndryshojĂ« gjatĂ« bashkimit ose ndarjes (nga x < y nuk do tĂ« thotĂ« se xz < yz);
  • rreshtat e ndryshĂ«m, qĂ« kanĂ« tĂ« njĂ«jtĂ«n peshĂ«, konsiderohen tĂ« barabartĂ« nĂ« aspektin e algoritmit tĂ« renditjes. Futja e njĂ« rendi shtesĂ« pĂ«r kĂ«to rreshta Ă«shtĂ« e mundur, por mund tĂ« pĂ«rkeqĂ«sojĂ« performancĂ«n;
  • gjatĂ« renditjeve tĂ« pĂ«rsĂ«ritura, rreshtat qĂ« kanĂ« tĂ« njĂ«jtĂ«n peshĂ« mund tĂ« shkĂ«mbehen. Stabiliteti Ă«shtĂ« njĂ« pronĂ« e njĂ« algoritmi tĂ« caktuar tĂ« renditjes, dhe jo njĂ« pronĂ« e algoritmit tĂ« krahasimit tĂ« rreshtave (shiko piken e mĂ«parshme);
  • rregullat e renditjes mund tĂ« ndryshojnĂ« me kalimin e kohĂ«s ndĂ«rsa traditat kulturore saktĂ«sohen/ndryshojnĂ«.

Po ashtu është përcaktuar se algoritmi i krahasimit nuk di asgjë për semantikën e rreshtave të përpunuar. Kështu, rreshtat që përbëhen vetëm nga numra nuk duhet të krahasohen si numra, dhe në listat e emrave anglezë nuk duhet të hiqet artikulli (Beatles, The).

Për të përmbushur të gjitha kërkesat e përmendura është propozuar një algoritëm renditjeje me shumë nivele (për faktin katër nivele).

Fillimisht, simbolĂ«t nĂ« rresht do tĂ« konvertohen nĂ« formĂ« kanonike dhe do tĂ« grupohen nĂ« njĂ«sitĂ« e krahasimit. Çdo njĂ«sie krahasimi i atribuohen disa pesha, qĂ« pĂ«rputhen me disa nivele krahasimi. Pesha e njĂ«sive tĂ« krahasimit janĂ« elemente tĂ« grupeve tĂ« renditura (nĂ« kĂ«tĂ« rast numra tĂ« tĂ«rĂ«), tĂ« cilat mund tĂ« krahasohen pĂ«r mĂ« shumĂ«-mĂ« pak. Vlera speciale IGNORED (0x0) do tĂ« thotĂ« se nĂ« nivelin pĂ«rkatĂ«s tĂ« krahasimit, kjo njĂ«si nuk merr pjesĂ« nĂ« krahasim. Krahasimi i vargjeve mund tĂ« pĂ«rsĂ«ritet disa herĂ«, duke pĂ«rdorur peshat pĂ«rkatĂ«se tĂ« niveleve. NĂ« çdo nivel, pesha e njĂ«si tĂ« krahasimit tĂ« dy vargjeve krahasohet njĂ«ra me tjetrĂ«n.

NĂ« realizime tĂ« ndryshme tĂ« algoritmit pĂ«r tradita tĂ« ndryshme kombĂ«tare, madhĂ«sitĂ« e koeficientĂ«ve mund tĂ« ndryshojnĂ«, por nĂ« pĂ«rbĂ«rjen e standardit Unicode pĂ«rfshihet njĂ« tabelĂ« bazĂ« peshash — "Default Unicode Collation Element Table" (DUCET). Dua tĂ« vĂ« nĂ« dukje se vendosja e variablĂ«s LC_COLLATE faktikisht Ă«shtĂ« njĂ« tregues pĂ«r zgjedhjen e tabelĂ«s sĂ« peshave nĂ« funksionin e krahasimit tĂ« vargjeve.

Koeficientët e pesha DUCET janë strukturuar si më poshtë:

  • nĂ« nivelin e parĂ«, tĂ« gjitha shkronjat janĂ« tĂ« shndĂ«rruara nĂ« njĂ« regjistĂ«r, shenjat diakritike pĂ«rjashtohen, dhe shenjat e pikĂ«simit (jo tĂ« gjitha) injorohen;
  • nĂ« nivelin e dytĂ«, vetĂ«m shenjat diakritike merren nĂ« konsideratĂ«;
  • nĂ« nivelin e tretĂ«, merren parasysh vetĂ«m regjistrat;
  • nĂ« nivelin e katĂ«rt, merren parasysh vetĂ«m shenjat e pikĂ«simit.

Krahasimi ndodh në disa kalime: së pari krahasohen koeficientët e nivelit të parë; nëse pesha përputhet, bëhet një krahasim i ri me peshat e nivelit të dytë; për më pas, ndoshta, ata të tretë dhe të katërt.

Krahasimi përfundon kur në vargje ndodhen njësi krahasimi përkatëse me pesa të ndryshme. Vargjet që kanë pesha të barabarta në të katër nivelet konsiderohen të barabarta mes tyre.

Ky algoritĂ«m (me njĂ« mori detajesh teknike shtesĂ«) i dha emrin raportit nr. 10 — "Unicode Collation Algorithm" (UCA).

Në këtë pikë, sjellja e renditjes nga shembulli ynë bëhet pak më e qartë. Do të ishte mirë ta krahasonim me standardin Unicode.

PĂ«r testimin e realizimeve UCA ekziston njĂ« test, qĂ« pĂ«rdor skedarin e peshave, qĂ« implementon DUCET. NĂ« skedarin e peshave mund tĂ« gjeni gjĂ«ra tĂ« ndryshme interesante. PĂ«r shembull, ka rendin e domino-s europian dhe pjesĂ«ve tĂ« mahjongut, si dhe rendin e llojeve nĂ« njĂ« paketĂ« kartash (simbol 1F000 dhe mĂ« tej). Llojet e kartave janĂ« tĂ« vendosura sipas rregullave tĂ« bridge-it — PÇBT, dhe kartat brenda llojit janĂ« nĂ« renditjen T, 2, 3
 K.

Kontrolli manual i saktësisë së renditjes së vargjeve në përputhje me DUCET do të ishte mjaft e lodhshme, por, për fatin tonë, ekziston një zbatim shembullor i bibliotekës për punë me Unicode - "Komponentët Ndërkombëtarë për Unicode" (ICU).

Në faqen e kësaj biblioteke, e cila u zhvillua në IBM, ka faqe demonstrimi, përfshirë faqen e algoritmit të krahasimit të vargjeve. Futim vargjet tona testuese me cilësimet e parazgjedhura dhe, o mrekulli, marrim një renditje të përsosur në rusisht.

Abakanov Mikhail;piktor
Jolkina Ella;një grua ndihmuese
Ivanov Andrei;ndihmës
Ivanova Alla;avokate

Tani, në faqen ICU mund të gjejmë qartësimin e funksionit të algoritmit të krahasimit kur përpunohen shenjat e pikësimit. Në shembujt FAQ për Krahasimin të apostrofit dhe lidhësit injorohen.

Unicode na ndihmoi, por do të duhet të kërkojmë shkaktarin e sjelljes së çuditshme sort në Linux diku tjetër.

Renditja në glibc

Një shikim i shpejtë në kodin burimor të utilitetit sort nga GNU Core Utils tregon se, në vetë utilitetin, lokalizimi reduktohet në shfaqjen e vlerës aktuale të variablës LC_COLLATE kur ekzekutohet në modin e depuratimit:

$ sort --debug buhg.txt > buhg.srt
sort: duke pĂ«rdorur rregullat e renditjes ‘en_US.UTF8’

Krahasimi i vargjeve kryhet nga funksioni standard strcoll, kështu që gjithçka interesante ndodhet në bibliotekë glibc.

Në wiki i projektit glibc krahasimit të vargjeve i kushtohet një paragraf. Nga ky paragraf mund të kuptohet se në glibc renditja bazohet në algoritmin që tashmë e dimë UCA (Algoritmi i renditjes Unicode) dhe/ose në një standard të ngjashëm ISO 14651 (Renditja dhe krahasimi ndërkombëtar i vargjeve). Në lidhje me standardin e fundit, duhet të theksohet se në faqen standards.iso.org ISO 14651 është shpallur zyrtarisht publik, por lidhja përkatëse çon në një faqe joeksistuese. Google jep disa faqe me lidhje në faqet zyrtare që ofrojnë blerjen e një kopjeje elektronike të standardit për njëqind euro, por në faqen e tretë-katërt të rezultatet e kërkimit mund të gjenden edhe lidhje të drejtpërdrejta në PDF. Në përgjithësi, standardi praktisht nuk ndryshon nga UCA, por lexohet më ngadalë, pasi nuk përmban shembuj të dukshëm të veçorive kombëtare të renditjes së vargjeve.

Informata më interesante në wiki ka qenë lidhja mbi bug tracker me diskutimin e implementimit të krahasimit të vargjeve në glibc. Nga diskutimi mund të kuptohet se në glibc për krahasimin e vargjeve përdoret ISOtabela e zakonshme Tabela e Përbashkët e Shabllonëve (CTT), adresa e së cilës mund të gjendet në aplikacionin A standardit ISO 14651. Midis vitit 2000 dhe 2015 kjo tabelë në glibc Nuk kishte një mbajtës dhe ndryshoi mjaft (të paktën në sipërfaqe) nga versioni aktual i standardit. Nga 2015 deri në 2018, u adaptua për versionin e ri të tabelës dhe tani keni mundësinë të takoni në jetën reale si variantin e ri të tabelës (CentOS 8), ashtu dhe të vjetër (CentOS 7).

Tani që e kemi të gjithë informacionin rreth algoritmit dhe tabelave ndihmëse, mund të kthehemi te problemi fillestar dhe të kuptojmë si të rendisim rreshtat në lokalitetin rus.

ISO 14651/14652

Kodi burimor i tabelës që na intereson CTT në shumicën e distribucioneve Linux ndodhet në katalogun /usr/share/i18n/locales/. Tabela vetë ndodhet në skedarin iso14651_t1_common. Pastaj, ky skedar me direktivën copy iso14651_t1_common përfshihet në skedarin iso14651_t1, i cili, nga ana e tij, përfshihet në skedarët kombëtarë, përfshirë në en_US dhe ru_RU. Në shumicën e distribucioneve Linux të gjitha skedarët burimorë përfshihen në përbërjen e instalimit bazë, por nëse nuk ka, do të duhet të instaloni një paketë shtesë nga distribuimi.

Struktura e skedarit iso14651_t1 mund të duket shumë më e gjatë, me rregulla jo të qarta për ndërtimin e emrave, por nëse e kuptoni, është mjaft e thjeshtë. Struktura përshkruhet në standardin ISO 14652, një kopje e të cilit mund të shkarkohet nga faqja open-std.org. Një përshkrim tjetër i formatit të skedarit mund të lexoni në specifikimet POSIX nga OpenGroup. Si një alternativë për të lexuar standardin, mund të studiuesh skedaret burimore të funksionit collate_read në glibc/locale/programs/ld-collate.c.

Struktura e skedarit duket kështu:

Sipas rregullave, simbolet përdoren si simboli i shkëputjes, dhe fundi i rreshtit pas simbolit # është një koment. Të dy simbolet mund të tejkalohen, diçka që është bërë në versionin e ri të tabelës:

escape_char /
comment_char %

NĂ« skedar do tĂ« hasni toka nĂ« formatin <Uxxxx> ose <Uxxxxxxxx> (ku x — numri nĂ« hex). Ky Ă«shtĂ« njĂ« pĂ«rfaqĂ«sim heksadeshimal i pikave tĂ« kodit Unicode nĂ« kodimin UCS-4 (UTF-32). TĂ« gjitha elementet e tjera nĂ« kĂ«ndore (pĂ«rfshirĂ« <Uxxxx_xxxx>, <2> dhe tĂ« ngjashme), konsiderohen si konstanta tĂ« thjeshta tĂ« vargjeve, pa kuptim tĂ« veçantĂ« jashtĂ« kontekstit.

String LC_COLLATE na thotë se më pas fillojnë të dhënat që përshkruajnë krahasimin e vargjeve.

Fillimisht, emrat për peshat në tabelën e krahasimit dhe emrat për kombinimet e simboleve përcaktohen. Kështu që, dy lloje emrash i përkasin dy entiteteve të ndryshme, por në skedarin e vërtetë ato janë të përziera. Emrat e peshave përcaktohen nga fjala kyçe collating-symbol (simboli i krahasimit), sepse kur krahasohen simbolet Unicode që kanë pesha të njëjta, ato do të konsiderohen si simbole ekuivalente.

Gjatësia totale e seksionit në revizionin e tanishëm të skedarit është rreth 900 rreshta. Kam nxjerrë shembuj nga disa vende për të treguar rastësinë e emrave dhe disa lloje sintaksash.

LC_COLLATE

simboli-i-krahasimit <RES-1>
simboli-i-krahasimit <BLK>
simboli-i-krahasimit <MIN>
simboli-i-krahasimit <WIDE>
...
simboli-i-krahasimit <ARABIC>
simboli-i-krahasimit <ETHPC>
simboli-i-krahasimit <OSMANYA>
...
simboli-i-krahasimit <S1D000>..<S1D35F>
simboli-i-krahasimit <SFFFF> % Vlera më e madhe e garantuar e simbolit. Ruani në fund të kësaj liste
...
simboli-i-krahasimit <U0413_0301> nga "<U0413><U0301>"
simboli-i-krahasimit <U0413_0341> nga "<U0413><U0341>"

  • simboli-i-krahasimit <OSMANYA> regjistron njĂ« varg OSMANYA nĂ« tabelĂ«n e emrave tĂ« peshave
  • simboli-i-krahasimit <S1D000>..<S1D35F> regjistron njĂ« sekuencĂ« emrash qĂ« pĂ«rbĂ«het nga njĂ« prefiks S dhe njĂ« sufiks numerik nĂ« gjashtor nga 1D000 nĂ« 1D35F.
  • FFFF nĂ« simboli-i-krahasimit <SFFFF> duket si njĂ« numĂ«r i madh pa nĂ«nshkrim nĂ« sistemin e numeracionit nĂ« gjashtor, por <SFFFF> Ă«shtĂ« thjesht njĂ« emĂ«r qĂ« mund tĂ« dukej si <VERYBIGVAL>
  • emri <U0413> tregon njĂ« pikĂ« kodimi nĂ« kodimin UCS-4
  • simboli-i-krahasimit <U0413_0301> nga "<U0413><U0301>" regjistron njĂ« emĂ«r tĂ« ri pĂ«r njĂ« çift pikash unicode.

Kur emrat e peshave janë përcaktuar, peshat e vet janë caktuar. Duke qenë se në krahasim rëndësi ka vetëm marrëdhënia më e madhe-më e vogël, atëherë peshat përcaktohen nga një rend të thjeshtë të emrave. Fillimisht shpallen peshat "më të lehta", pastaj më "të rënda". Më kujtohet se çdo simbol unicode i jepet një peshë e ndryshme. Këtu ato janë të grumbulluara në një rend të vetëm të renditur. Teorikisht, çdo emër simbolik mund të përdoret në një nga katër nivellet, por komentet tregojnë se zhvilluesit mentalisht i ndajnë emrat për nivellet.

% Caktimet e peshave simbolike

% Caktimet e peshave të nivelit të tretë
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Caktimet e peshave të nivelit të dytë
<BASE>
<LOWLINE> % KOMBINUAR NË POSHTË
<PSILI> % KOMBINUAR KOMË NË SIPËR
<DASIA> % KOMBINUAR KOMË E KTHYER NË SIPËR
...
% Caktimet e peshave të nivelit të parë
<S0009> % TABULIMI HORIZONTAL
<S000A> % RRESHTI I AUTOMATIZUAR
<S000B> % TABULIMI VERTIKAL
...
<S0434> % LETRA E SMALL CYRILIC DE
<S0501> % LETRA E SMALL CYRILIC KOMI DE
<S0452> % LETRA E SMALL CYRILIC DJE
<S0503> % LETRA E SMALL CYRILIC KOMI DJE
<S0453> % LETRA E SMALL CYRILIC GJE
<S0499> % LETRA E SMALL CYRILIC ZE ME NËNTESH
<S0435> % LETRA E SMALL CYRILIC IE
<S04D7> % LETRA E SMALL CYRILIC IE ME BREVE
<S0454> % LETRA E SMALL CYRILIC IE UKRAINIAN
<S0436> % LETRA E SMALL CYRILIC ZHE

SĂ« fundi, tabela e peshave.

Seksi i peshave është i mbyllur në radhë me fjalë kyçe order_start dhe order_end. Parametrat e tjerë order_start përcaktojnë se në cilin drejtim shihen radhët në secilën nivel krahasimi. Si rregull, përdoret parametri forward. Trupi i seksionit përbëhet nga radhë që përmbajnë kodin e karakterit dhe katër peshat e tij. Kodi i karakterit mund të përfaqësohet nga vetë karakteri, pika e kodit ose emri simbolik i përcaktuar më parë. Pesha gjithashtu mund të jepet nga emra simbolikë, pika kodimi ose vetë karakteret. Nëse përdoren pika kodimi ose karaktere, pesha e tyre përputhet me vlerën numerike të pikës së kodit (pozita në tabelën e Unicode). Karakteret që nuk janë përmendur qartë (ashtu siç e kuptoj) konsiderohen të shtuar në tabelë me peshë primare, e cila përputhet me pozitat në tabelën e Unicode. Vlera speciale e peshës IGNORE do të thotë se në nivelin përkatës të krahasimit ky karakter injorohet.

Për të demonstruar strukturën e peshave, kam zgjedhur tre fragmente mjaft të qarta:

  • karaktere qĂ« injorohen krejtesisht
  • karaktere ekuivalente me numrin tre nĂ« dy nivelet e para
  • fillimi i alfabetit cirilik, i cili nuk pĂ«rmban shenja diakritike, dhe prandaj renditet, kryesisht, sipas niveleve tĂ« para dhe tĂ« treta.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (në 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % FILLIMI I TITULLIT (në 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % FILLIMI I TEKSTIT (në 6429)
...
 ;;; % NUMRI TRE
 ;;; % NUMRI TRE ME GJATËSI TË PLOTE
 ;;; % NUMRI TRE NË PRANË
 ;;; % NUMRI TRE ME PIKË
 ;;; % NUMRI TRE ME BOLD MATHEMATIK
...
 ;;; % LETRA E VOLE CIRILIKE A
 ;;; % LETRA KOKE CIRILIKE A
 ;;; % LETRA E VOLE CIRILIKE A ME BREVE
 ;;; % LETRA E VOLE CIRILIKE A ME BREVE
...
 ;;; % LETRA E VOLE CIRILIKE BE
 ;;; % LETRA KOKE CIRILIKE BE
 ;;; % LETRA E VOLE CIRILIKE VE
 ;;; % LETRA KOKE CIRILIKE VE
...
order_end

Tani është koha për të rikthyer vëmendjen në renditjen e shembujve nga fillimi i artikullit. Problemi fshihet në këtë pjesë të tabelës së peshave:

INJORO; INJORO; INJORO; % HAP
 INJORO; INJORO; INJORO; % SHENJË NGRITJE
 INJORO; INJORO; INJORO; % SHENJË CITIMI
...

ËshtĂ« e dukshme se nĂ« kĂ«tĂ« tabelĂ« shenjat e pikĂ«simit vijnĂ« nga tabela. ASCII (duke pĂ«rfshirĂ« hapĂ«sirĂ«n) kur krahasoni vargjet zakonisht injorohen. Rastet e vetme janĂ« ato vargje qĂ« pĂ«rputhen plotĂ«sisht, pĂ«rveç shenjave tĂ« pikĂ«simit qĂ« ndodhen nĂ« pozita pĂ«rputhĂ«se. Vargjet nga shembulli im (pas renditjes) pĂ«r algoritmin e krahasimit duken kĂ«shtu:

AbakanovMihailpiktor
JolkinaEllaekraniste
IvanovaAllamalpiktor
IvanovAndreypunëtor druri

Duke konsideruar se në tabelën e peshave shkronjat e mëdha në gjuhën ruse vijnë pas atyre të vogla (në nivelin e tretë. <CAP> më të rënda se <MIN>), renditja duket krejtësisht e saktë.

Kur vendosni variablin LC_COLLATE=C ngarkohet një tabelë speciale që përcakton krahasimin byte për byte

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* tabela e parë * /
  6 * sizeof (uint32_t),
  /* tabela e dytë * /
  7 * sizeof (uint32_t),
  /* tabela e tretë * /
  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'
};

Duke pasur parasysh se nĂ« Unicode pika koduese ё Ă«shtĂ« para A, kĂ«shtu qĂ« dhe vargjet renditen nĂ« pĂ«rputhje.

Tabelat tekstuale dhe binare

Sigurisht, krahasimi i vargjeve është një operacion që ndodh shumë shpesh, ndërsa analizimi i tabelës CTT është një procedurë mjaft e kushtueshme. Për optimizimin e aksesit në tabelë, ajo kompiloohet në një formë binare me komandën localedef.

Ekipa localedef pranimi i skedës me tabelën e karakteristikave kombëtare (opsioni -i), në të cilën të gjithë karakteret paraqiten me pika Unicode, dhe skedës së përputhjes së pikave Unicode me kodimin përkatës (opsioni --follow). Si rezultat i procesit krijohen skedarë binarë për lokalitetin, me emrin e caktuar në parametrin e fundit.

Glibc mbështet dy formate skedarësh binarë: "tradicional" dhe "modern".

Formati tradicional nënkupton se emri i lokalitetit është emri i një nënfolderi në /usr/lib/locale/. Në këtë nënfolder ruhen skedarët binarë LC_COLLATE, LC_CTYPE, LC_TIME etj. Skedari LC_IDENTIFICATION përmban emrin formal të lokalitetit (i cili mund të ndryshojë nga emri i folderit) dhe komente.

Formati modern supozon ruajtjen e tĂ« gjitha lokaliteteve nĂ« njĂ« arkiv tĂ« vetĂ«m /usr/lib/locale/locale-archive, i cili mapohet nĂ« memorinĂ« virtuale tĂ« tĂ« gjithĂ« proceseve qĂ« e pĂ«rdorin. glibc. Emri i lokalit nĂ« formatin modern i nĂ«nshtrohet njĂ« kanonizimi tĂ« caktuar — nĂ« emrat e kodimeve mbeten vetĂ«m numrat dhe shkronjat, tĂ« sjella nĂ« format tĂ« vogĂ«l. KĂ«shtu ru_RU.KOI8-R, do tĂ« ruhet si ru_RU.koi8r.

Skedarët hyrës kërkohen në katalogun aktual, si dhe në katalogët /usr/share/i18n/locales/ dhe /usr/share/i18n/charmaps/ për skedarët CTT dhe skedarët e kodimeve përkatësisht.

PĂ«r shembull, komanda

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

do të kompilojë skedarin /usr/share/i18n/locales/ru_RU duke përdorur skedarin e kodimit /usr/share/i18n/charmaps/MAC-CYRILLIC.gz dhe do ta ruajë rezultatin në /usr/lib/locale/locale-archive me emrin ru_RU.maccyrillic

Nëse vendosni variablën LANG=en_US.UTF-8 atëherë glibc do të kërkojë skedarë binarë të lokaliteteve në këtë rend për skedarët dhe katalogët:

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

Nëse lokaliteti shfaqet si në formatet tradicionale ashtu edhe në ato moderne, përparësia i jepet atij modernit.

Lista e lokaliteteve të kompiluar mund të shikohet me komandën locale -a.

Përgatitja e tabelës tuaj të krahasimit

Tani, me njohuritë e fituara, mund të krijoni tabelën tuaj ideale të krahasimit të vargjeve. Kjo tabelë duhet të krahasojë saktësisht shkronjat ruse, duke përfshirë shkronjën Ё, dhe gjithashtu duhet të marrë parasysh shenjat e pikësimit në përputhje me tabelën ASCII.

Procesi i përgatitjes së tabelës tuaj të renditjes përbëhet nga dy etapa: redaktimi i tabelës së peshave dhe kompaktimi i saj në formë binar me komandën localedef.

Për të përshtatur tabelën e krahasimit me minimumin e kostove për redaktim, në formatin ISO 14652 parashikohen seksione për korrigjimin e peshave të tabelës ekzistuese. Seksioni fillon me fjalën kyçe reorder-after dhe tregimi i pozicionit, pas të cilit bëhet zëvendësimi. Seksioni përfundon me rrjeshtin reorder-end. Nëse është e nevojshme të rregulloni disa pjesë të tabelës, krijohet një seksion për çdo pjesë të tillë.

Kam kopjuar versionet e reja të skedarëve iso14651_t1_common dhe ru_RU nga repozitori glibc në katalogun tim të shtëpisë ~/ .local/ share/ i18n/ locales/ dhe pak e redaktova seksionin LC_COLLATE në ru_RU. Versionet e reja të skedarëve janë plotësisht të përshtatshme me versionin tim. glibcNëse dëshironi të përdorni versionet e vjetra të skedarëve, do t'ju duhet të ndryshoni emrat simbolikë dhe vendin ku fillon zëvendësimi në tabelë.

LC_COLLATE
% Koponi shablonin nga ISO/IEC 14651
kopjo "iso14651_t1"
riorganizo-pas <U000D>
<U0020> <S0020>;<BASIS>;<MIN>;<U0020> % HAPĂ«s
<U0021> <S0021>;<BASIS>;<MIN>;<U0021> % SHENJË E KUSHTIT
<U0022> <S0022>;<BASIS>;<MIN>;<U0022> % SHENJË CITIMI
...
<U007D> <S007D>;<BASIS>;<MIN>;<U007D> % KURORË E DJATHTË
<U007E> <S007E>;<BASIS>;<MIN>;<U007E> % TILDA
riorganizimi-fund
KONC LC_COLLATE

Në të vërtetë, duhej të kishim ndryshuar fushat në LC_IDENTIFICATION në mënyrë që ato të përcaktonin lokalitetin sq_MY, por në shembullin tim kjo nuk ishte e nevojshme, pasi e hoqa nga kërkimi lokalitetin e arkivuar locale-archive.

Për localedef punoja me skedarët në dosjen time përmes variablës I18NPATH mund të shtoni një katalog të mëtejshëm për të kërkuar skedarët hyrës, dhe katalogu për ruajtjen e skedarëve binarë mund të përcaktohet si një rrugë me shqiponja:

$> I18NPATH=~\/..local\/share\/i18n localedef -i sq_RU -f UTF-8 ~\/..local\/lib\/locale\/sq_MY.UTF-8

POSIX percepton se në LANG mund të shkruhen rrugë absolute për katalogët me skedarë lokalizimi që fillojnë me një shqiponjë, por glibc në Linux të gjitha rrugët llogariten nga katalogu bazë, që mund të tejkalojë nëpërmjet variablës LOCPATH. Pas vendosjes LOCPATH=~\/..local\/lib\/locale\/ të gjitha skedaret që lidhen me lokalizimin do të kërkohen vetëm në dosjen time. Arkiva e lokaliteteve me variablën e vendosur LOCPATH neglizhohet.

Ja testi vendimtar:

$> LANG=sq_MY.UTF-8 LOCPATH=~\/..local\/lib\/locale\/ sort buhg.txt
Abakanov Mihail;piktor
Jolkina Ella;kranok
Ivanov Andrey;gazetar
Ivanova Alla;avokate

Të lumtë! E bëmë këtë!

Rregullimi i gabimeve

Kam përgjigjur tashmë në pyetjet rreth renditjes së rreshtave, të shtruara në fillim, por kanë mbetur disa pyetje rreth gabimeve - të dukshme dhe të padukshme.

Kthehemi në detyrën fillestare.

Dhe programi sort dhe programi bashkohu pĂ«rdorin tĂ« njĂ«jtat funksione krahasimi tĂ« rreshtave nga glibc. Si ndodhi qĂ« bashkohu jepte njĂ« gabim nĂ« renditje pĂ«r rreshtat e renditur nga komanda sort nĂ« lokalitetin en_US.UTF-8? ОтĐČДт ĐżŃ€ĐŸŃŃ‚: sort krahason rreshtin nĂ« tĂ«rĂ«si, ndĂ«rsa bashkohu krahason vetĂ«m çelĂ«sin, i cili pĂ«r default Ă«shtĂ« fillimi i rreshtit deri nĂ« simbolin e parĂ« tĂ« bardhĂ«. NĂ« shembullin tim, kjo çoi nĂ« njĂ« mesazh gabimi pasi renditja e fjalĂ«ve tĂ« para nĂ« rreshta nuk pĂ«rputhej me renditjen e rreshtave tĂ« plota.

Lokaliteti "C" garanton që në rreshtat e renditur, nënstringat fillestare deri në hapësirën e parë gjithashtu do të jenë të renditura, por kjo vetëm maske një gabim. Mund të zgjidhen të dhëna të tilla (persona me mbiemra të njëjtë, por me emra të ndryshëm), të cilat pa një mesazh gabimi do të jepnin rezultate të gabuara në bashkimin e skedarëve. Nëse duam që bashkohu të bashkojë rreshtat e skedarëve sipas emri mbiemri, atëherë mënyra e duhur do të ishte të tregohej qartë ndarësi i fushave dhe renditja sipas fushës kyç, e jo sipas tërë rreshtit. Në këtë rast dhe bashkimi do të kalojë në mënyrë të drejtë dhe nuk do të ketë gabime në asnjë lokalitet:

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

Shembulli i suksesshëm në kodimin CP1251 përmban edhe një gabim tjetër. E vërteta është që në të gjitha shpërndarjet që njoh Linux në paketat mungon lokaliteti i kompiluar ru_RU.CP1251. Nëse lokaliteti i kompiluar nuk gjendet, atëherë sort në heshtje përdor krahasimin byte, që ne e vërejmë.

Dhe, për t'u thënë, ka edhe një gabim të vogël që lidhet me pamundësinë e lokaliteteve të kompiluar. Komanda LOCPATH=/tmp locale -a do të japë një listë të të gjithë lokaliteteve në locale-archive, por me variablin e vendosur LOCPATH për të gjitha programet (përfshirë edhe vetë locale) këto lokalitete do të jenë të pakapshme.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Nuk mund të caktoj LC_CTYPE në lokalitetin e parazgjedhur: Nuk ekziston një skedar ose drejtor
locale: Nuk mund të caktoj LC_MESSAGES në lokalitetin e parazgjedhur: Nuk ekziston një skedar ose drejtor
locale: Nuk mund të caktoj LC_COLLATE në lokalitetin e parazgjedhur: Nuk ekziston një skedar ose drejtor
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: duke pĂ«rdorur rregullat ‘en_US.UTF-8’ tĂ« renditjes

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: duke përdorur krahasimin e thjeshtë të bajtëve

PĂ«rfundim

Nëse je programues që je mësuar të mendosh se rreshtat janë një sërë bajtësh, atëherë zgjedhja jote LC_COLLATE=C.

Nëse je një gjuhëtar ose hartues fjalorësh, atëherë është më mirë të kompilosh lokalitetin tënd.

Nëse je një përdorues i zakonshëm, atëherë është mjaft të mësosh se komanda ls -a jep skedarë që fillojnë me pikë, bashkë me skedarë që fillojnë me shkronjë, dhe Midnight Commander, e cila përdor funksionet e veta të brendshme për të renditur emrat, nxjerr skedarët që fillojnë me pikë në fillim të listës.

Linket

Raporti Nr.10 algoritmi i renditjes së Unicode

Peshat e simboleve në unicode.org

ICU — implementimi i bibliotekĂ«s pĂ«r punĂ« me Unicode nga IBM.

Testi i renditjes me ICU

Peshat e simboleve në ISO 14651

Përshkrimi i formatit të skedarit me peshat ISO 14652

Diskutimi mbi krahasimin e rreshtave në glibc

Burimi: habr.com

Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS đŸ”„ Blini hosting tĂ« besueshĂ«m pĂ«r faqe interneti me mbrojtje nga DDoS, serverĂ« VPS VDS | ProHoster