Hyrje

E gjithçka nisi me një skript të shkurtër, i cili duhej të bashkonte informacionin mbi adresat e-mail e punonjësve, të marrë nga lista e përdoruesve të grupit të postës me pozitat e punonjësve, të marra nga baza e të dhënave të departamentit të resurseve njerëzore. Të dy listat ishin eksportuar në skedarë tekstualë në kodimin Unicode UTF-8 dhe ishin ruajtur me funde rreshtash të Unix-it.

Përmbajtja mail.txt

Ivanov Andrey;ia@example.com

Përmbajtja buhg.txt

Ivanova Alla;piktore
Yolkina Ella;kranist
Ivanov Andrey;punëtor
Abakanov Mikhail;piktor

Për të bashkuar, skedarët u renditën me komandën e Unix-it sort dhe iu dorëzuan programit të Unix-it join, 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 Andrey;punëtor

Shikimi i rezultatit të renditjes me sy tregoi se renditja në përgjithësi ishte e saktë, por në rastin e përputhjeve të mbiemrave mashkullorë dhe femërorë, femrat shkojnë para mashkullorëve:

$> sort buhg.txt
Abakanov Mikhail;piktor
Yolkina Ella;kranist
Ivanova Alla;piktore
Ivanov Andrey;punëtor

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

Të lëmë mënjanë për momentin join dhe të përqendrohemi te sort. Le të provojmë të zgjidhim problemin përmes metodës së provës dhe gabimit. Për fillim, do të ndryshojmë lokacionin nga en_US në ru_RU. Për renditjen mjafton të vendosim një variabël mjedisi LC_COLLATE, por s'kemi për të u marrë me gjëra të vogla:

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

Nuk ka ndryshuar asgjë.

Le të provojmë të rikodojmë skedarët në kodim me një bajt:

$> 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 ka ndryshuar asgjë.

Nuk kemi ç'të bëjmë, do të duhet të kërkojmë një zgjidhje në internet. Në lidhje me mbiemrat rusë nuk ka informacione direkte, por ka pyetje për çështje të tjera të çuditshme në renditje. Për shembull, ka një problem të tillë: unix sort e trajton karakterin ‘-’ (zog) si të padukshëm. Shkurtimisht, vargjet "a-b", "aa", "ac" renditen si "aa", "a-b", "ac".

Përgjigja është e standardizuar: përdorni lokacionin programues "C" dhe do të jeni të lumtur. Le të provojmë:

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

Diçka është ndryshuar. Ivanët janë renditur në rendin e duhur, por Ёlkinë është zhdukur diku. Kthehemi te detyra fillestare:

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

Ka funksionoi pa gabime, siç e premtoi interneti. Dhe kjo ndodh pavarësisht nga Ёlkin në rreshtin e parë.

Problemi duket se është zgjidhur, por për çdo rast do të provojmë edhe një kodim rus — atë të Windows. CP1251:

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

Rezultati i renditjes, siç duket, do të përputhet me lokalitetin "C", dhe tërë shembulli, siç duhet, kalon pa gabime. Një lloj misteri.

Nuk më pëlqen misteri në programim, sepse zakonisht ai fsheh gabime. Do të 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 u renditën gabim mbiemrat femërorë
pse LANG=ru_RU.CP1251 doli të ishte ekuivalent LANG=C
pse kanë sort dhe join përshtypje të ndryshme mbi rendin e rreshtave të renditur
pse në të gjitha shembujt e mi ka gabime
në fund, si të renditen rreshtat sipas dëshirës time

Renditja në Unicode

Stopi i parë do të jetë raporti teknik nr. 10 me titull algoritmi i radhitjes së Unicode në faqen unicode.org. Raporti përmban shumë detaje teknike, prandaj do të lejoj veten të jap një përmbledhje të ideve kryesore.

Radhitja — "krahasimi" i vargjeve është thelbi i çdo algoritmi të renditjes. Algoritmet vetë mund të ndryshojnë ("bubullimë", "shkrirje", "i shpejtë"), por të gjithë do të përdorin krahasimin e dy vargjeve për të përcaktuar rendin e tyre.

Renditja e vargjeve në gjuhën natyrore është një problem mjaft i nd complicuar. Edhe në kodimet më të thjeshta me një byte, rendi i shkronjave në alfabet, ndonjëherë ndryshe nga latinishtja angleze, nuk do të përputhet më me rendin e vlerave numerike me të cilat kodohen këto shkronja. Kështu, në alfabetin gjerman, shkronja Ö ndodhet midis më dhe P, ndërsa në kodimin CP850 ajo ndodhet midis ÿ dhe Ü.

Mund të tentoni të abstraktoni nga kodimi konkret dhe të shqyrtoni "shkronjat" ideale të cilat janë të renditura në një rend, siç është bërë në Unicode. Kodimet UTF8, UTF16 ose një byte KOI8-R (nëse kërkohet një nëngrup i kufizuar i Unicode) do të japin përfaqësime të ndryshme numerike të shkronjave, por do të referojnë në të njëjtat elemente të tabelës bazë.

Të rezultojë se edhe duke ndërtuar një tabelë simboresh nga e para, nuk do të mund të caktojmë një rend të përgjithshëm për simbolet. 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 frënge, Æ do të konsiderohet si një ligaturë dhe do të renditet si një varg. AENë gjuhën norvegjeze, Æ do të jetë një shkronjë e veçantë, e cila ndodhet pas Z. Me sa duket, përveç ligaturave të tipit Æ ka edhe shkronja që shënohen me disa simbole. Kështu, në alfabetin çek ekziston shkronja Ch, e cila ndodhet midis H dhe I.

Përveç ndryshimeve në alfabet, 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 shkronjat e mëdha dhe të vogla? Gjithashtu, ndikuar në renditjen mund të jenë karakteristikat e përdorimit të shenjave ndarëse. Në gjuhën spanjolle në fillim të një propozimi pyetës vendoset një shenjë pyetjeje e përmbysur (¿Te gusta la música?). Në këtë rast, është e qartë se pyetjet nuk duhet të grupohen në një klasë të veçantë jashtë alfabetit, por si të kategorizohen vargjet me shenja të tjera pikësimi?

Nuk do të ndalem në renditjen e vargjeve në gjuhë që dallohen ndjeshëm nga ato evropiane. Dua të theksoj se në gjuhët me drejtim shkrimi nga e djathta në të majtë ose nga lart poshtë, simbolët në vargje, zakonisht, ruajnë rendin sipas leximit, dhe madje në shkrimet jo alfabetike ka mënyra të veta për renditjen karakter për karakter të vargjeve. Për shembull, hieroglifet mund të renditen sipas formës së tyre (çelësat e hieroglifëve kinezë) ose sipas shqiptimit. Si duhet të renditen emotikonët, sinqerisht, nuk e di, por për ta mund të shpikim diçka.

Baza e karakteristikave të përmendura më lart janë formuluar kërkesat kryesore për krahasimin e vargjeve, të bazuara në tabelat e Unicode:

krahasimi i vargjeve nuk varet nga vendosja e simboleve në tabelën e kodit;
sekuencat e simboleve që formojnë një simbol të vetëm, kthehen në formën kanonike (A + rrethi i sipërm është e njëjta gjë me Å);
kur krahasimi i fjalive, simboli shqyrtohet në kontekstin e fjalive dhe, kur është e nevojshme, bashkohet me fqinjët në njësi krahasimi (Ch në çeke) ose ndahet në disa (Æ në frëngjisht);
të gjitha karakteristikat kombëtare (alfabeti, shkronjat e mëdha/të vogla, shpërndarja e pikësimeve, rendi i llojeve të shkrimit) duhet të konfigurohen deri në caktimin manual të rendit (emoji);
krahasimi është i rëndësishëm jo vetëm për renditje, por edhe në shumë vende të tjera, për shembull për përcaktimin e intervaleve të fjalive (zëvendësimi {A… я} në bash);
krahasimi duhet të kryhet mjaft shpejt.

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

algoritmi i krahasimit nuk duhet të kërkojë një grup të veçantë simboresh për secilën gjuhë (gjuha ruse dhe ukrainase përdorin së bashku shumicën e simboleve të cirilikës);
krahasimi nuk duhet të mbështetet në rendin e simboleve në tabelat Unicode;
pesha e fjalise nuk duhet të jetë një atribut i fjalise, pasi e njëjta fjali në kontekste kulturore të ndryshme mund të ketë pesha të ndryshme;
peshat e rreshtave mund të ndryshojë gjatë bashkimit ose ndarjes (nga x < y nuk do të thotë se xz < yz);
stringjet e ndryshme që kanë peshë të njëjtë, konsiderohen të barabarta nga pikëpamja e algoritmit të renditjes. Futja e një renditje shtesë të këtyre rreshtave është e mundur, por mund të përkeqësojë performancën;
në renditjet e përsëritura, rreshtat me peshë të njëjtë mund të ndërrohen. Qëndrueshmëria është një pronë e veçantë e algoritmit të renditjes, dhe jo një pronë e algoritmit të krahasimit të rreshtave (shih pikën e mëparshme);
rregullat e renditjes mund të ndryshojnë me kalimin e kohës në përputhje me saktësimin/ndryshimin e traditave kulturore.

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

Për të përmbushur të gjitha kërkesat e përmendura, është propozuar një algoritëm renditës me shumë nivele (në fakt, katër nivele).

Fillimisht, karakteret në varg konvertohen në formën kanonike dhe grupohen në njësitë e krahasimit. Çdo njësitë e krahasimit i atribuohen disa peshash, që i korrespondojnë disa niveleve të krahasimit. Peshat e njësive të krahasimit janë elemente të grupeve të renditur, që mund të krahasohen për më shumë-pak. Vlera speciale IGNORED (0x0) do të thotë se në nivelin përkatës të krahasimit, kjo njësitë nuk merr pjesë në krahasim. Krahasimi i vargjeve mund të përsëritet disa herë, me përdorimin e peshave përkatëse të niveleve. Në çdo nivel, peshat e njësive të krahasimit të dy vargjeve krahasohen radhazi me njëri-tjetrin.

Në realizime të ndryshme të algoritmit për tradita të ndryshme kombëtare, vlerat e koeficientëve mund të ndryshojnë, por në standardin Unicode është përfshirë tabela themelore e peshave — "Default Unicode Collation Element Table" (DUCET). Dëshiroj të theksoj se vendosja e variablit LC_COLLATE në fakt është një tregues për zgjedhjen e tabelës së peshave në funksionin e krahasimit të vargjeve.

Koeficientët e peshave DUCET janë organizuar në këtë mënyrë:

në nivelin e parë, të gjitha shkronjat çohen në një regjistër, shenjat diakritike përjashtohen, shenjat e pikësimit (jo të gjitha) injorohen;
në nivelin e dytë, merren parasysh vetëm shenjat diakritike;
në nivelin e tretë, merret parasysh vetëm regjistri;
në nivelin e katërt, merren parasysh vetëm shenjat e pikësimit.

Krahasimi ndodh në disa kalime: fillimisht krahasohen pesha e nivelit të parë; nëse peshat përputhen, ndodh një krahasim i përsëritur me peshat e nivelit të dytë; pastaj, ndoshta për nivelin e tretë dhe të katërt.

Krahasimi përfundon kur në vargje ka njësitë e krahasimit që përputhen me pesha të ndryshme. Vargjet që kanë pesa të barabarta në të katër nivelet konsiderohen të barabarta me njëra-tjetrën.

Ky algoritëm (me shumë detaje 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 krahasosh me standardin e Unicode.

Për testimin e realizimeve UCA ekziston një test, që përdor skedarin e peshave, implementues DUCET. Në skedarin e peshojve mund të gjeni gjëra të ndryshme argëtuese. Për shembull, aty ka rendin e lugezve të Mahjong-ut dhe domino-s evropian, si dhe rendin e mastave në një dek kartash (simbol 1F000 dhe më tej). Mastat e kartave janë vendosur sipas rregullave të bridge-it — PÇBT, dhe kartat në mastë — në rendin 2, 3… K.

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

Në faqen e kësaj biblioteke, e zhvilluar në IBM, ka faqe demonstrimi, përfshirë faqen e algoritmit të krahasimit të rreshtave. Futim rreshtat tanë të testit me cilësimet e paracaktuara dhe, oh mrekulli, marrim renditjen perfekte shqiptare.

Abakanov Mihail;piktor
Jolkina Ella;grua kran
Ivanov Andrej;pjesë e hekurudhave
Ivanova Alla;avokat

Dhe për më tepër, në faqen e ICU mund të gjeni sqarimin e punës së algoritmit të krahasimit kur trajtoni shenjat e pikësimit. Në shembujt FAQ për Vendosjen ignorohen apostrofi dhe hifeni.

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

Renditja në glibc

Pamja e shpejtë e kodit burimor të utilitarit sort nga GNU Core Utils tregon se në utilitar vetë, lokalizimi përfshin printimin e vlerës aktuale të variablit LC_COLLATE kur ekzekutohet në modalitetin e rregullimit:

$ sort --debug buhg.txt > buhg.srt
sort: duke përdorur rregullat për renditjen ‘en_US.UTF8’

Krahason stringjet duke përdorur funksionin standard strcoll, dhe kështu çdo gjë interesante ndodhet në bibliotekë glibc.

Në wiki projekti glibc mënyrës për krahëzim stringjesh i është dedikuar një paragraf. Nga ky paragraf mund të kuptohet se glibc renditja është e bazuar në algoritmin që tashmë e njohim UCA (The Unicode collation algorithm) dhe/ose në një standard të ngjashëm ISO 14651 (Renditja dhe krahasimi ndërkombëtar i stringjeve). Sa i përket këtij standarti, duhet vënë në dukje se në faqen standards.iso.org ISO 14651 është shpallur publikisht, por lidhja përkatëse çon në një faqe që nuk ekziston. Google jep disa faqe me lidhje për faqet zyrtare që ofrojnë të blejnë një kopje elektronike të standardit për njëqind euro, por në faqen e tretë-katërt të artikujve të kërkimit mund të gjenden edhe lidhje të drejtpërdrejta për PDF. Në përgjithësi, standardi nuk ndryshon shumë nga UCA, por lexohet më monoton, pasi nuk përmban shembuj të ndritshëm të veçorive kombëtare të renditjes së stringjeve.

Informacioni më i rëndësishëm në wiki ishte lidhja te bagracker me diskutimin mbi implementimin e krahasimit të vargjeve në glibc. Nga diskutimi mund të kuptohet se në glibc përdoret ISOtabela vizuale Tabela e Përbashkët e Template-ve (CTT), adresa e së cilës mund të gjendet në aplikacionin A standardit ISO 14651. Ndërmjet viteve 2000 dhe 2015, kjo tabelë në glibc nuk kishte mbikëqyrës dhe ndryshonte shumë (të paktën në pamje) nga versi aktuale e standardit. Nga 2015 deri në 2018, ishte në proces adaptimi me versionin e ri të tabelës dhe tanimë keni mundësinë të takoni në jetë reale si versionin e ri të tabelës (CentOS 8), ashtu edhe versionin e vjetër (CentOS 7).

Tani, kur kemi të gjitha informacionet mbi algoritmin dhe tabelat ndihmëse, mund të kthehemi te problemi fillestar dhe të kuptojmë se si të renditim saktësisht vargjet në lokalizimin 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. Më pas, ky skedar përfshihet me direktivën copy iso14651_t1_common 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ë janë përfshirë në instalimin bazik, por nëse ato nuk janë aty, do të duhet të instaloni një paketë shtesë nga distribuimi.

Struktura e skedarit iso14651_t1 mund të duket tmerrësisht e zgjatur, me rregulla ndërtimi emrash që nuk janë të qarta, por nëse merresh me të, është mjaft e thjeshtë. Strukturën e përshkruan standardi ISO 14652, një kopje e të cilit mund të shkarkohet nga uebsajti open-std.org. Një përshkrim tjetër të formatit të skedarit mund të lexoni në specifikimet POSIX nga OpenGroup. Si një alternativë për të lexuar standardin, mund të studiohen skedarët burimorë të funksionit collate_read në glibc/locale/programs/ld-collate.c.

Struktura e skedarit duket si më poshtë:

Në parazgjedhje, simboli \ përdoret si simbol i shndërrimit, dhe fundi i rreshtit pas simbolit # është një komente. Të dy simbolët mund të rishkruhen, ashtu siç është bërë në versionin e ri të tabelës:

escape_char /\ncomment_char %

Në skedar do të shfaqen tokenë në formatin <Uxxxx> ose <Uxxxxxxxx> (ku x – shifër hex). Ky është përfaqësimi hex i pikave të kodit Unicode në kodimin UCS-4 (UTF-32). Elementët e tjerë në këndoret (përfshirë <Uxxxx_xxxx>, <2> dhe të ngjashme), konsiderohen si konstante stringu të thjeshta, pa ndonjë kuptim të veçantë jashtë kontekstit.

Vargu LC_COLLATE na tregon se më pas fillojnë të dhënat që përshkruajnë krahasimin e stringjeve.

Së pari vendosen emrat për peshat në tabelën e krahasimit dhe emrat për kombinimet e simboleve. Në përgjithësi, dy tipa emrash i përkasin dy entiteteve të ndryshme, por në skedarin real ato janë të përziera. Emrat e peshave vendosen me fjalën kyçe collating-symbol (simboli i krahasimit), pasi gjatë krahasimit simbolet Unicode që kanë të njëjtat pesha do të konsiderohen simbole ekuivalente.

Gjatësia e përgjithshme e seksionit në revizionin aktual të skedarit është rreth 900 rreshta. Kam marrë shembuj nga disa vende për të treguar rastësinë e emrave dhe disa lloje sintaksë.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garancia e vlerës më të madhe të simbolit. Mbani në fund të kësaj liste
...
collating-element  nga ""
collating-element  nga ""

collating-symbol regjistron një varg OSMANYA në tabelën e emrave të peshave
collating-symbol .. regjistron një sekuencë emrash që përbëhet nga prefiksi S dhe një sufiks numerik të gjashtëmbëdhjetë nga 1D000 deri te 1D35F.
FFFF në simboli i kollatimit duket si një numër të madh pa shenjë në sistemin e numrave të gjashtëmbëdhjetë, por <SFFFF> është thjesht një emër që mund të duket si <VERYBIGVAL>
emri <U0413> nënkupton një pikë kodi në kodimin UCS-4
elementi i kollatimit nga "" regjistron një emër të ri për një çift pikash unicode.

Kur emrat e peshave janë përcaktuar, caktohen vetë peshat. Duke qenë se në krahasim ka rëndësi vetëm raporti më pak-më shumë, pesha përcaktohet nga një renditje e thjeshtë e emrave. Fillimisht renditen peshat më "të lehta", pastaj ato më "të rënda". Të kujtoj se çdo simbol unicode i atribuohen katër peshë të ndryshme. Këtu ato janë përmbledhur në një renditje të vetme të organizuar. Teorikisht, çdo emër simbolik mund të përdoret në cilëndo nga katër nivelet, por komentet sugjerojnë që zhvilluesit mendërisht i ndajnë emrat sipas niveleve.

% Peshatja simbolike

% Peshatja e nivelit të tretë




...
% Peshatja e nivelit të dytë

 % KOMBI NË RAJON
 % KOMBI ME SIPËR
 % KOMBI ME PËRBRASHT
...
% Peshatja e nivelit të parë
 % TABULIM HORIZONTAL
 % KALIMI NË RRESHT
 % TABULIM VERTIKAL
...
 % LETRA E SMAL PARAFOLIT TË CIRILICËS
 % LETRA E SMAL KOMI DE
 % LETRA E SMAL DJE
 % LETRA E SMAL KOMI DJE
 % LETRA E SMAL GJE
 % LETRA E SMAL ZE ME ZBRESJE
 % LETRA E SMAL IE
 % LETRA E SMAL IE ME BREVE
 % LETRA E SMAL IE UKRAINIAN
 % LETRA E SMAL ZHE

Më në fund, tabela e vetë peshave.

Sekcioni i peshave është i mbyllur në rreshta me fjalë kyçe order_start dhe order_end. Parametrat shtesë order_start shprehin në cilin drejtim rreshtat shikohen në çdo nivel krahasimi. Në mënyrë të parazgjedhur, përdoret parametri përpara. Trupi i seksionit përbëhet nga rreshta që përmbajnë kodin e simbolit dhe katër peshat e tij. Kodi i simbolit mund të paraqitet si vetë simboli, pika kodi ose emri simbolik i përcaktuar më parë. Peshat gjithashtu mund të përcaktohen nga emra simbolikë, pika kodi ose vetë simbolat. Nëse përdoren pika kodi ose simbolat, pesha e tyre përputhet me vlerën numerike të pikës së kodit (pozita në tabelën e Unicode). Simbolat e papërshtatur (sipërfaqësisht) merren si të aneksuar në tabelë me peshë primare që përputhet me pozitën në tabelën e Unicode. Vlera speciale e peshës IGNORE do të thotë se në nivelin e krahasimit përkatës, ky simbol injorohet.

Për të demonstruar strukturën e peshave, kam zgjedhur tri fragmente mjaft të dukshme:

simbolat që injorohen plotësisht
simbolat ekuivalente me numrin tre në dy nivelet e para
fillimi i alfabetit cirilik, i cili nuk përmban shenja diakritike, dhe për këtë arsye renditet, kryesisht, sipas niveleve të para dhe të treta.

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

Tani tani, mund të ktheheni përsëri në renditjen e shembujve nga fillimi i artikullit. Problemi fshihet këtu në këtë pjesë të tabelës së peshave:

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

Duket se në këtë tabelë shenjat e pikësimit janë të dukshme nga tabela ASCII (duke përfshirë hapësirat) gjatë krahasimit të vargjeve zakonisht injorohen. Përjashtim përbëjnë vetëm vargjet që përputhen plotësisht, përveç shenjave të pikësimit që ndodhen në pozitat përputhëse. Vargjet nga shembulli im (pas renditjes) për algoritmin e krahasimit duken kështu:

AbakanovMikhailpiktor
JolkinaEllaekranist
IvanovaAllamalyr
IvanovAndreyekripar

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

Kur vendoset variabli LC_COLLATE=C ngarkohet një tabelë speciale, e cila përcakton krahasimin byte për byte

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

Duke marrë parasysh që në Unicode pika e kodit Ё është para A, vargjet renditen përkatësisht.

Tabelat tekstuale dhe binare

È e dukshme se krahasimi i vargjeve është një operacion shumë i zakonshëm, ndërsa analiza e tabelave CTT është një procedurë mjaft e shtrenjtë. Për optimizimin e qasjes në tabelë, ajo kompilizohet në formë binar nga komanda localedef.

Ekipa localedef e cila pranon si parametra një skedar me tabelën e veçorive kombëtar (opsioni -i), ku të gjitha simbolet paraqiten si pika Unicode, dhe një skedar përputhjeje të pikave Unicode me simbolet e kodimit të caktuar (opsioni -f). Si rezultat i punës krijohen skedarë binarë për lokalitetin, me emrin e specifikuar në parametrin e fundit.

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

Formati tradicional nënkupton që emri i lokalitetit është emri i një nënkatalogu në /usr/lib/locale/. Në këtë nënkatalog 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 katalogut) dhe komente.

Formati modern parashikon ruajtjen e të gjitha lokaliteteve në një arkiv të vetëm /usr/lib/locale/locale-archive, i cili shkarkohet në memorjen virtuale të të gjitha proceseve që e përdorin glibc. Emri i lokalizimit në formatin modern përjeton një formë kanonizimi—në emrat e kodimeve mbeten vetëm numrat dhe shkronjat, të cilat janë shndërruar në shkronja të vogla. Kështu, ru_RU.KOI8-R, do të ruhet si ru_RU.koi8r.

Skedarët hyrës kërkohen në katalogun aktuell, si dhe në kataloget /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, urdhri

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 të 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ët binarë të lokalizimit në renditjen e mëposhtme të skedarëve dhe katalogeve:

/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 lokalizimi shfaqet si në formatin tradicional ashtu edhe në atë modern, prioritete i jepet atij modern.

Listën e lokalizimeve të kompiluar mund ta shihni me urdhrin locale -a.

Përgatitja e tabelës suaj të krahasimit

Tani, duke u armatosur me njohuri, mund të krijoni tabelën tuaj të përsosur të krahasimit të vargjeve. Kjo tabelë duhet të krahasojë saktësisht shkronjat ruse, duke përfshirë shkronjën Ё, dhe në të njëjtën kohë të marrë parasysh shenjat e pikësimit në përputhje me tabelën ASCII.

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

Për qëllim që tabela e krahasimit të mund të përshtatet me minimumin e shpenzimeve për redaktim, në formatin ISO 14652 parashikohen seksione për rregullimin e peshave të tabelës ekzistuese. Seksonip kalohet me fjalën kyçe reorder-after dhe caktimin e pozicionit, pas të cilit bëhet zëvendësimi. Sektori përfundon me vargun reorder-end. Nëse nevojitet të rregullohen 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 repositori glibc në katalogun tim personal ~/ .local / share / i18n / locales / dhe pak e kam redaktuar seksionin LC_COLLATE në ru_RU. Versionet e reja të skedarëve janë plotësisht të pajtueshme me versionin tim glibc. Nëse doni të përdorni versionet e vjetra të skedarëve, do t'ju duhet të ndryshoni emrat simbolikë dhe vendndodhjen nga e cila fillon zëvendësimi në tabelë.

LC_COLLATE
% Kopjoni shkablonin nga ISO/IEC 14651
kopjoni "iso14651_t1"
shkallëzo pas <U000D>
<U0020> <S0020>;<Baza>;<MIN>;<U0020> % HAP
<U0021> <S0021>;<Baza>;<MIN>;<U0021> % SHENJA E KISHTËS
<U0022> <S0022>;<Baza>;<MIN>;<U0022> % SHENJA CITUARE
...
<U007D> <S007D>;<Baza>;<MIN>;<U007D> % KAVIDHA E DJATHTË
<U007E> <S007E>;<Baza>;<MIN>;<U007E> % TILDA
shkallëzo-fund
KONFIRMIM LC_COLLATE

Në të vërtetë, do të ishte mirë të kaloheshin fushat në LC_IDENTIFICATION në mënyrë që ato të tregonin për lokalitetin ru_MY, por në shembullin tim kjo nuk ishte e nevojshme, pasi e përjashtova nga kërkimi lokalitetin e arkivuar locale-archive.

Për localedef puna me skedarët në dosjen time përmes variablit I18NPATH mund të shtoni një katalog shtesë për kërkimin e skedarëve hyrës, dhe katalogu për ruajtjen e skedarëve binarë mund të tregohet si një rrugë me slashe:

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

POSIX supozon se në LANG mund të shkruhen rrugë absolute për katalogët me skedare lokalitetesh, që fillojnë me slash të drejtpërdrejtë, por glibc në Linux të gjitha rrugët merren nga katalogu bazë, i cili mund të rishkruhet përmes variablit LOCPATH. Pas vendosjes së LOCPATH=~/.local/lib/locale/ të gjitha skedarët që lidhen me lokalizimin do të kërkohen vetëm në dosjen time. Arkiva e lokaliteteve me variablën e vendosur LOCPATH injorohet.

Këtu është testi vendimtar:

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

Hura! E bëmë këtë!

Puna mbi gabimet

Unë tashmë kam përgjigjur në pyetjet për renditjen e vargjeve të shtruara më parë, por mbeten disa pyetje të tjera mbi gabimet — të dukshme dhe të padukshme.

Le të kthehemi në detyrën fillestare.

dhe programi sort dhe programi join përdorin të njëjtat funksione për krahasimin e vargjeve nga glibc. Si ndodhi që join japin një gabim renditjeje për vargjet e renditura nga komanda sort në lokalitetin en_US.UTF-8? Ответ прост: sort krahason vargun në tërësi, kurse join krahason vetëm çelësin, i cili për defaut është fillimi i vargut deri në simbolet e para të zbrazëta. Në shembullin tim, kjo çoi në një mesazh gabimi sepse renditja e fjalëve të para në vargje nuk përputhej me renditjen e vargut të plotë.

Lokaliteti "C" garanton që në stringat e renditura, nënstringat deri në hapjen e parë gjithashtu do të jenë të renditura, por kjo vetëm maskon një gabim. Mund të zgjidhen të dhëna të tilla ( të njerëzve me mbiemra të njëjtë, por emra të ndryshëm), të cilat pa një njoftim për gabim do të jepnin një rezultat të gabuar të bashkimit të skedarëve. Nëse duam që join të bashkojmë stringat e skedarëve sipas emrit dhe mbiemrit, mënyra e duhur do të ishte të tregohet qartë ndarësi i fushave dhe të renditen sipas fushës kyçe, e jo sipas të gjithë stringut. Në këtë rast, bashkimi do të kalojë siç duhet dhe në asnjë lokalitet nuk do të ketë gabime:

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

Një shembull i realizuar me sukses në kodimin CP1251 ka një tjetër gabim. Çështja është se në të gjithë shpërndarjet e njohura për mua 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-per-byte, gjë që ne po vëzhgojmë.

Për sa i përket, ka një tjetër ndjesi të vogël të lidhur me paaftësinë për të aksesuar lokalitetet e kompiluar. Komanda LOCPATH=/tmp locale -a do të japë një listë të të gjitha lokaliteteve në locale-archive, por me variablin e instaluar LOCPATH për të gjitha programet (përfshirë atë më të locale) këto locale nuk do të jenë të disponueshme.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Nuk mund të vendos LC_CTYPE në locale standarde: Nuk ka një vendndodhje të tillë ose direktor
locale: Nuk mund të vendos LC_MESSAGES në locale standarde: Nuk ka një vendndodhje të tillë ose direktor
locale: Nuk mund të vendos LC_COLLATE në locale standarde: Nuk ka një vendndodhje të tillë ose direktor
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: po përdor rregullat e renditjes ‘en_US.UTF-8’

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: po përdor krahasimin e bytes të thjeshtë

Përfundimi

Nëse jeni programues që keni zakon të mendoni se stringjet janë një grup bytes, atëherë zgjedhja juaj LC_COLLATE=C.

Nëse jeni lingvist ose kompozitor fjalorësh, është më mirë të kompilonin locale tuaj.

Nëse jeni përdorues i zakonshëm, mjafton të mësoni që komanda ls -a jep skedarë që fillojnë me pikë, së bashku me skedarë që fillojnë me shkronjë, dhe Midnight Commander, i cili përdor funksionet e tij të brendshme për të renditur emrat, i sjell skedarët që fillojnë me pikë në fillim të listës.