kirish

Hammasi manzil ma'lumotlarini birlashtirishi kerak bo'lgan qisqa skript bilan boshlandi elektron pochta pochta ro'yxati foydalanuvchilari ro'yxatidan olingan xodimlar, kadrlar bo'limi ma'lumotlar bazasidan olingan xodimlar lavozimlari bilan. Ikkala ro'yxat ham Unicode matn fayllariga eksport qilindi UTF-8 va Unix satr oxiri bilan saqlangan.

Tarkib mail.txt

Иванов Андрей;[email protected]

Tarkib buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

Birlashtirish uchun fayllar Unix buyrug'i bilan tartiblangan saralamoq va Unix dasturining kiritilishiga taqdim etiladi Qo'shiling, bu xato bilan kutilmaganda muvaffaqiyatsizlikka uchradi:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

Saralash natijasini ko'z bilan ko'rish, umuman olganda, saralash to'g'ri ekanligini ko'rsatdi, ammo erkak va ayol familiyalari mos kelgan taqdirda, ayollar erkaklardan oldin keladi:

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

Unicode-da tartiblash xatosi yoki tartiblash algoritmidagi feminizmning namoyon bo'lishi kabi ko'rinadi. Birinchisi, shubhasiz, yanada ishonchli.

Keling, buni hozircha qoldiraylik Qo'shiling va diqqatni qarating saralamoq. Keling, muammoni ilmiy poking yordamida hal qilishga harakat qilaylik. Birinchidan, mahalliy tilni o'zgartiramiz en_US haqida ru_RU. Saralash uchun muhit o'zgaruvchisini o'rnatish kifoya LC_COLLATE, lekin biz arzimas narsalarga vaqt sarflamaymiz:

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

Hech narsa o'zgarmadi.

Keling, fayllarni bir baytli kodlashda qayta kodlashga harakat qilaylik:

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

Yana hech narsa o'zgarmadi.

Hech narsa qila olmaysiz, Internetda yechim izlashingiz kerak bo'ladi. Rus familiyalari haqida to'g'ridan-to'g'ri hech narsa yo'q, lekin boshqa tartiblash g'alatiliklar haqida savollar mavjud. Masalan, bu erda muammo bor: unix sort '-' (tire) belgilarini ko'rinmas deb hisoblaydi. Xulosa qilib aytganda, “ab”, “aa”, “ac” qatorlari “aa”, “ab”, “ac” tarzida tartiblangan.

Javob hamma joyda standartdir: dasturchi tilidan foydalaning "C" va siz baxtli bo'lasiz. Kel urinib ko'ramiz:

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

Nimadir o‘zgardi. Yolkina qayoqqadir sirpanib ketgan bo'lsa-da, Ivanovlar to'g'ri tartibda saf tortdilar. Keling, asl muammoga qaytaylik:

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

Internet va'da qilganidek, xatosiz ishladi. Va bu birinchi qatorda Yolkina bo'lishiga qaramay.

Muammo hal qilinganga o'xshaydi, lekin har qanday holatda, keling, boshqa ruscha kodlashni sinab ko'raylik - Windows CP1251:

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

Saralash natijasi, g'alati darajada, mahalliy tilga to'g'ri keladi "C", va butun misol, shunga ko'ra, xatosiz ishlaydi. Tasavvufning bir turi.

Men dasturlashda tasavvufni yoqtirmayman, chunki u odatda xatolarni yashiradi. Biz uning qanday ishlashini jiddiy o'rganishimiz kerak. saralamoq va bu nimaga ta'sir qiladi? LC_COLLATE .

Oxirida men savollarga javob berishga harakat qilaman:

nega ayol familiyalari noto'g'ri tartiblangan?
nima uchun LANG=ru_RU.CP1251 ekvivalent bo'lib chiqdi LANG=C
nima uchun saralamoq и Qo'shiling saralangan satrlarning tartibi haqida turli fikrlar
nega mening barcha misollarimda xatolar bor?
nihoyat o'zingizning xohishingizga ko'ra satrlarni qanday saralash

Unicode-da saralash

Birinchi to'xtash joyi 10-sonli texnik hisobot bo'ladi Unicode solishtirish algoritmi saytda unicode.org. Hisobot juda ko'p texnik tafsilotlarni o'z ichiga oladi, shuning uchun men asosiy g'oyalarning qisqacha mazmunini keltiraman.

taqqoslash — «taqqoslash» satrlari har qanday tartiblash algoritmining asosidir. Algoritmlarning o'zi bir-biridan farq qilishi mumkin ("qabariq", "birlashma", "tezkor"), lekin ularning barchasi paydo bo'lish tartibini aniqlash uchun bir juft satrni taqqoslashdan foydalanadi.

Tabiiy tilda satrlarni saralash juda murakkab muammodir. Hatto eng oddiy bitta baytli kodlashlarda ham alifbodagi harflar tartibi, hatto ingliz lotin alifbosidan qandaydir farq qilsa ham, endi bu harflar kodlangan raqamli qiymatlar tartibiga to'g'ri kelmaydi. Shunday qilib, nemis alifbosida harf Ö orasida turadi О и P, va kodlashda CP850 u orasini oladi ÿ и Ü.

Siz ma'lum bir kodlashdan xulosa chiqarishga harakat qilishingiz va Unicode-da bo'lgani kabi, qandaydir tartibda joylashtirilgan "ideal" harflarni ko'rib chiqishingiz mumkin. Kodlashlar UTF8, UTF16 yoki bir bayt KOI8-R (agar Unicode-ning cheklangan to'plami kerak bo'lsa) harflarning turli xil raqamli ko'rinishlarini beradi, lekin asosiy jadvalning bir xil elementlariga murojaat qiladi.

Ma’lum bo‘lishicha, biz ramzlar jadvalini noldan tuzsak ham, unga universal belgilar tartibini belgilay olmaymiz. Xuddi shu harflardan foydalanadigan turli milliy alifbolarda bu harflarning tartibi farq qilishi mumkin. Masalan, frantsuz tilida Æ ligature hisoblanadi va satr sifatida tartiblanadi AE. Norveg tilida Æ keyin joylashgan alohida harf bo'ladi Z. Aytgancha, shunga o'xshash ligaturesdan tashqari Æ Bir nechta belgilar bilan yozilgan harflar mavjud. Shunday qilib, chex alifbosida harf bor Ch, orasida joylashgan H и I.

Alifbolardagi farqlardan tashqari, saralashga ta'sir qiluvchi boshqa milliy an'analar ham mavjud. Xususan, savol tug‘iladi: katta va kichik harflardan tashkil topgan so‘zlar lug‘atda qanday tartibda bo‘lishi kerak? Saralash tinish belgilaridan foydalanish bilan ham ta'sir qilishi mumkin. Ispan tilida so'roq gapning boshida teskari so'roq belgisi qo'llaniladi (Musiqani yoqtirasizmi?). Bunday holda, so'roq gaplarni alifbodan tashqarida alohida klasterga emas, balki boshqa tinish belgilariga ega bo'lgan qatorlarni qanday saralash kerakligi aniq?

Men Evropa tillaridan juda farq qiladigan tillardagi satrlarni saralash haqida to'xtalmayman. E'tibor bering, o'ngdan chapga yoki yuqoridan pastgacha yozish yo'nalishi bo'lgan tillarda, satrlardagi belgilar o'qish tartibida saqlanadi va hatto alifbo bo'lmagan yozuv tizimlarida ham belgilar bo'yicha qatorlarni tartiblashning o'ziga xos usullari mavjud. . Masalan, ierogliflarni uslub bo'yicha tartiblash mumkin (Xitoy belgilar kalitlari) yoki talaffuzi bilan. Rostini aytsam, emojilarni qanday tartibga solish kerakligini bilmayman, lekin siz ham ular uchun biror narsa o'ylab topishingiz mumkin.

Yuqorida sanab o'tilgan xususiyatlardan kelib chiqqan holda, Unicode jadvallari asosida satrlarni taqqoslash uchun asosiy talablar shakllantirildi:

satrlarni taqqoslash kodlar jadvalidagi belgilar o'rniga bog'liq emas;
bitta belgini tashkil etuvchi belgilar ketma-ketligi kanonik shaklga tushiriladi (A + yuqori doira xuddi shunday Å);
Satrlarni taqqoslashda belgi satr kontekstida ko'rib chiqiladi va kerak bo'lganda qo'shnilari bilan bir taqqoslash birligiga birlashtiriladi (Ch chex tilida) yoki bir nechaga bo'lingan (Æ frantsuz tilida);
barcha milliy xususiyatlar (alifbo, katta/kichik harflar, tinish belgilari, yozish turlarining tartibi) tartibni qo'lda belgilashgacha (emoji) sozlanishi kerak;
Taqqoslash nafaqat saralash, balki boshqa ko‘plab joylarda ham muhim, masalan, qator diapazonlarini belgilashda ({A... z} o‘rniga bosh);
taqqoslash juda tez amalga oshirilishi kerak.

Bundan tashqari, hisobot mualliflari algoritm ishlab chiquvchilar tayanmasligi kerak bo'lgan taqqoslash xususiyatlarini ishlab chiqdilar:

taqqoslash algoritmi har bir til uchun alohida belgilar to'plamini talab qilmasligi kerak (rus va ukrain tillarida ko'pchilik kirill harflari mavjud);
taqqoslash Unicode jadvallaridagi belgilar tartibiga tayanmasligi kerak;
string vazni satrning atributi bo'lmasligi kerak, chunki turli madaniy kontekstlarda bir xil satr turli og'irliklarga ega bo'lishi mumkin;
Birlashtirish yoki bo'lish paytida qator og'irliklari o'zgarishi mumkin (dan x < y bunga amal qilmaydi xz < yz);
bir xil og'irliklarga ega bo'lgan turli qatorlar tartiblash algoritmi nuqtai nazaridan teng deb hisoblanadi. Bunday satrlarni qo'shimcha tartiblashni joriy qilish mumkin, ammo bu ish faoliyatini yomonlashtirishi mumkin;
Takroriy saralash paytida bir xil og'irlikdagi qatorlarni almashtirish mumkin. Mustahkamlik qatorni taqqoslash algoritmining xususiyati emas, balki muayyan tartiblash algoritmining xususiyatidir (oldingi bandga qarang);
Saralash qoidalari vaqt o'tishi bilan madaniy an'analar yaxshilanishi/o'zgarishi bilan o'zgarishi mumkin.

Bundan tashqari, taqqoslash algoritmi qayta ishlanayotgan satrlarning semantikasi haqida hech narsa bilmasligi shart. Shunday qilib, faqat raqamlardan iborat bo'lgan satrlarni raqamlar bilan taqqoslamaslik kerak va ingliz nomlari ro'yxatida maqola (Beatles, The).

Belgilangan barcha talablarni qondirish uchun ko'p darajali (aslida to'rt darajali) jadvallarni saralash algoritmi taklif etiladi.

Ilgari, satrdagi belgilar kanonik shaklga tushirilgan va taqqoslash birliklariga guruhlangan. Taqqoslashning har bir birligiga bir nechta taqqoslash darajalariga mos keladigan bir nechta vaznlar beriladi. Taqqoslash birliklarining og'irliklari ko'proq yoki kamroq taqqoslanadigan tartiblangan to'plamlarning elementlari (bu holda butun sonlar). Maxsus ma'no E'tiborsiz (0x0) mos keladigan taqqoslash darajasida bu birlikning taqqoslashda ishtirok etmasligini bildiradi. Satrlarni taqqoslash mos keladigan darajalarning og'irliklaridan foydalangan holda bir necha marta takrorlanishi mumkin. Har bir darajada ikki qatorning taqqoslash birliklarining og'irliklari ketma-ket bir-biri bilan taqqoslanadi.

Turli xil milliy an'analar uchun algoritmni turli xil qo'llashda koeffitsientlarning qiymatlari farq qilishi mumkin, ammo Unicode standarti asosiy og'irliklar jadvalini o'z ichiga oladi - "Birlamchi Unicode harmanlama elementlari jadvali" (DUCET). Men o'zgaruvchini o'rnatishni ta'kidlashni istardim LC_COLLATE satrni taqqoslash funktsiyasida vazn jadvalini tanlashning ko'rsatkichidir.

Og'irlik koeffitsientlari DUCET quyidagicha tartibga solingan:

birinchi bosqichda barcha harflar bir xil holatga qisqartiriladi, diakritik belgilar o'chiriladi, tinish belgilari (barchasi emas) e'tiborga olinmaydi;
ikkinchi darajada faqat diakritiklar hisobga olinadi;
uchinchi darajada faqat holat hisobga olinadi;
to'rtinchi bosqichda faqat tinish belgilari hisobga olinadi.

Taqqoslash bir necha o'tishda amalga oshiriladi: birinchi navbatda, birinchi darajali koeffitsientlar solishtiriladi; agar og'irliklar mos kelsa, ikkinchi darajali og'irliklar bilan takroriy taqqoslash amalga oshiriladi; keyin, ehtimol, uchinchi va to'rtinchi.

Taqqoslash satrlarda turli og'irliklar bilan mos keladigan taqqoslash birliklari mavjud bo'lganda tugaydi. Barcha to'rt darajadagi og'irliklari teng bo'lgan qatorlar bir-biriga teng deb hisoblanadi.

Ushbu algoritm (bir qator qo'shimcha texnik tafsilotlar bilan) 10-sonli hisobotga nom berdi - "Unicode solishtirish algoritmi" (ACU).

Bu erda bizning misolimizdagi tartiblash harakati biroz aniqroq bo'ladi. Unicode standarti bilan solishtirish yaxshi bo'lardi.

Amalga oshirishni sinab ko'rish uchun ACU maxsus bor Viktorina, foydalanish vazn fayli, amalga oshirish DUCET. Tarozi faylida har xil kulgili narsalarni topishingiz mumkin. Masalan, mahjong va Evropa dominolarining tartibi, shuningdek, kartalar palubasidagi kostyumlar tartibi (ramz) mavjud. 1F000 va undan keyin). Karta kostyumlari ko'prik - PCBT qoidalariga muvofiq joylashtiriladi va kostyumdagi kartalar T, 2,3, XNUMX... K ketma-ketlikda joylashgan.

Satrlar bo'yicha to'g'ri tartiblanganligini qo'lda tekshirish DUCET Bu juda zerikarli bo'lar edi, lekin, baxtimizga, biz uchun Unicode bilan ishlash uchun kutubxonaning namunali amaliyoti mavjud - "Unicode uchun xalqaro komponentlar"(ICU).

Ushbu kutubxona veb-saytida, yilda ishlab chiqilgan IBM, demo sahifalar mavjud, jumladan satrlarni taqqoslash algoritmi sahifasi. Biz sinov liniyalarimizni standart sozlamalar bilan kiritamiz va mana, biz mukammal ruscha saralashga erishamiz.

Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Иванова Алла;адвокат

Aytgancha, veb-sayt ICU Tinish belgilarini qayta ishlashda siz taqqoslash algoritmining aniqligini topishingiz mumkin. Misollarda Jamlash tez-tez so'raladigan savollar apostrof va defisga e'tibor berilmaydi.

Unicode bizga yordam berdi, lekin g'alati xatti-harakatlarning sabablarini qidiring saralamoq в Linux boshqa joyga borishga majbur bo'ladi.

Glibc da saralash

Foydali dastur manba kodlarining tezkor ko'rinishi saralamoq dan GNU Core Utils ko'rsatdiki, yordamchi dasturning o'zida mahalliylashtirish o'zgaruvchining joriy qiymatini chop etishga tushadi LC_COLLATE disk raskadrovka rejimida ishlayotganda:

$ sort --debug buhg.txt > buhg.srt
sort: using ‘en_US.UTF8’ sorting rules

Satrlarni taqqoslash standart funksiya yordamida amalga oshiriladi strcoll, ya'ni barcha qiziqarli narsalar kutubxonada glibc.

ning Wiki loyiha glibc satrlarni taqqoslashga bag'ishlangan bitta paragraf. Ushbu paragrafdan shuni tushunish mumkinki glibc saralash bizga allaqachon ma'lum bo'lgan algoritmga asoslanadi ACU (Unicode solishtirish algoritmi) va/yoki unga yaqin standartda ISO 14651 (Xalqaro satrlarni tartiblash va taqqoslash). Eng so'nggi standartga kelsak, shuni ta'kidlash kerakki, saytda standards.iso.org ISO 14651 rasman ochiq deb e'lon qilingan, ammo tegishli havola mavjud bo'lmagan sahifaga olib keladi. Google standartning elektron nusxasini yuz evroga sotib olishni taklif qiladigan rasmiy saytlarga havolalar bilan bir nechta sahifalarni qaytaradi, ammo qidiruv natijalarining uchinchi yoki to'rtinchi sahifalarida to'g'ridan-to'g'ri havolalar ham mavjud. PDF. Umuman olganda, standart deyarli farq qilmaydi ACU, lekin oʻqish zerikarliroq, chunki unda satrlarni saralashning milliy xususiyatlarining aniq misollari mavjud emas.

Eng qiziqarli ma'lumotlar Wiki ga havola bor edi xato kuzatuvchisi da string taqqoslashni amalga oshirish muhokamasi bilan glibc. Suhbatdan shuni bilish mumkinki glibc satrlarni solishtirish uchun ishlatiladi ISOshaxsiy stol Umumiy shablonlar jadvali (CTT), uning manzilini arizada topish mumkin A standart ISO 14651. 2000 va 2015 yillar oralig'ida ushbu jadval glibc xizmat ko'rsatuvchisi yo'q edi va standartning joriy versiyasidan (hech bo'lmaganda tashqi tomondan) ancha farq qilar edi. 2015 yildan 2018 yilgacha jadvalning yangi versiyasiga moslashish amalga oshirildi va endi siz haqiqiy hayotda jadvalning yangi versiyasi bilan tanishish imkoniyatiga egasiz (CentOS 8) va eski (CentOS 7).

Endi biz algoritm va yordamchi jadvallar haqida barcha ma'lumotlarga egamiz, biz asl muammoga qaytishimiz va rus tilidagi satrlarni qanday qilib to'g'ri saralashni tushunishimiz mumkin.

ISO 14651 / 14652

Bizni qiziqtirgan jadvalning manba kodi CTT ko'pgina tarqatishlarda Linux katalogda mavjud /usr/share/i18n/locales/. Jadvalning o'zi faylda iso14651_t1_common. Keyin bu fayl direktivasi iso14651_t1_commondan nusxa oling faylga kiritilgan iso14651_t1, bu esa, o'z navbatida, milliy fayllarga kiritilgan, shu jumladan en_US и ru_RU. Ko'pgina tarqatishlarda Linux barcha manba fayllari asosiy o'rnatishga kiritilgan, ammo ular mavjud bo'lmasa, siz tarqatishdan qo'shimcha paketni o'rnatishingiz kerak bo'ladi.

Fayl tuzilishi iso14651_t1 ismlarni yaratishda aniq bo'lmagan qoidalarga ega bo'lgan dahshatli ko'rinishi mumkin, ammo agar siz unga qarasangiz, hamma narsa juda oddiy. Struktura standartda tavsiflangan ISO 14652, uning nusxasini veb-saytdan yuklab olish mumkin open-std.org. Fayl formatining yana bir tavsifini o'qish mumkin spetsifikatsiyalar POSIX от Ochiq guruh. Standartni o'qishga alternativa sifatida siz funktsiyaning manba kodini o'rganishingiz mumkin jamlash_o'qish в glibc/locale/programs/ld-collate.c.

Fayl tuzilishi quyidagicha ko'rinadi:

Odatiy bo'lib, belgi qochish belgisi sifatida ishlatiladi va # belgidan keyingi qatorning oxiri sharhdir. Ikkala belgi ham qayta belgilanishi mumkin, bu jadvalning yangi versiyasida amalga oshiriladi:

escape_char /
comment_char %

Fayl formatdagi tokenlarni o'z ichiga oladi yoki (qaerda x - o'n oltilik raqam). Bu kodlashda Unicode kod nuqtalarining o'n oltilik ko'rinishidir UCS-4 (UTF-32). Burchak qavslardagi boshqa barcha elementlar (shu jumladan , va shunga o'xshashlar) kontekstdan tashqarida kam ma'noga ega bo'lgan oddiy satr konstantalari hisoblanadi.

Chiziq LC_COLLATE keyin satrlarni solishtirishni tavsiflovchi ma'lumotlar boshlanishini aytadi.

Birinchidan, taqqoslash jadvalidagi og'irliklar uchun nomlar va belgilar birikmalari uchun nomlar ko'rsatilgan. Umuman olganda, ikki turdagi nomlar ikki xil ob'ektga tegishli, ammo haqiqiy faylda ular aralashtiriladi. Og'irliklarning nomlari kalit so'z bilan belgilanadi yig'ish belgisi (taqqoslash belgisi), chunki taqqoslashda og'irliklari bir xil bo'lgan Unicode belgilari ekvivalent belgilar hisoblanadi.

Joriy faylni qayta ko'rib chiqishdagi bo'limning umumiy uzunligi taxminan 900 qatorni tashkil qiladi. Ismlarning o'zboshimchaliklari va sintaksisning bir nechta turlarini ko'rsatish uchun men bir nechta joydan misollar keltirdim.

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

yig'ish belgisi qatorni qayd qiladi OSMANYA tarozi nomlari jadvalida
yig'ish belgisi .. prefiksdan tashkil topgan nomlar ketma-ketligini qayd qiladi S va dan o‘n oltilik son qo‘shimchasi 1D000 uchun 1D35F.
Ffff в yig'ish belgisi o'n oltilik tizimda katta belgisiz butun songa o'xshaydi, lekin bu shunchaki o'xshash bo'lishi mumkin bo'lgan ism
nomi kodlashda kod nuqtasini bildiradi UCS-4
jamlovchi element dan " " Unicode nuqtalari juftligi uchun yangi nom qayd qiladi.

Og'irliklarning nomlari aniqlangandan so'ng, haqiqiy og'irliklar ko'rsatiladi. Taqqoslashda faqat kattaroq munosabatlar muhim bo'lganligi sababli, vaznlar ro'yxat nomlarining oddiy ketma-ketligi bilan aniqlanadi. Avval "engilroq" og'irliklar, keyin esa "og'irroq" ro'yxatga olinadi. Eslatib o'taman, har bir Unicode belgisiga to'rt xil vazn berilgan. Bu erda ular bitta tartibli ketma-ketlikda birlashtirilgan. Nazariy jihatdan, har qanday ramziy nom to'rt darajadagi har qandayida ishlatilishi mumkin, ammo sharhlar shuni ko'rsatadiki, ishlab chiquvchilar nomlarni aqliy ravishda darajalarga ajratadilar.

% 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

Nihoyat, haqiqiy vazn jadvali.

Og'irliklar bo'limi kalit so'z qatoriga kiritilgan order_start и order_end. Qo'shimcha variantlar order_start har bir taqqoslash darajasida qaysi yo'nalishdagi qatorlar skanerdan o'tkazilishini aniqlang. Standart sozlama oldinga. Bo'limning tanasi belgilar kodini va uning to'rtta vaznini o'z ichiga olgan qatorlardan iborat. Belgilar kodi belgining o'zi, kod nuqtasi yoki oldindan belgilangan ramziy nom bilan ifodalanishi mumkin. Og'irliklar ramziy nomlarga, kod nuqtalariga yoki belgilarning o'ziga ham berilishi mumkin. Agar kod nuqtalari yoki belgilar ishlatilsa, ularning og'irligi kod nuqtasining raqamli qiymati bilan bir xil bo'ladi (Unicode jadvalidagi joy). Aniq ko'rsatilmagan belgilar (men tushunganimdek) Unicode jadvalidagi pozitsiyaga mos keladigan asosiy og'irlikdagi jadvalga tayinlangan deb hisoblanadi. Maxsus vazn qiymati YO'Q tegishli taqqoslash darajasida belgi e'tiborga olinmasligini bildiradi.

Tarozilarning tuzilishini ko'rsatish uchun men uchta aniq bo'lakni tanladim:

butunlay e'tiborga olinmagan belgilar
birinchi ikki darajadagi uchta raqamga teng belgilar
kirill alifbosining boshlanishi, unda diakritik belgilar mavjud emas va shuning uchun asosan birinchi va uchinchi darajalar bo'yicha tartiblangan.

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

Endi siz maqolaning boshidan misollarni saralashga qaytishingiz mumkin. Pistirma og'irliklar jadvalining ushbu qismida joylashgan:

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

Ko'rinib turibdiki, bu jadvalda tinish belgilari jadvaldan ASCII (shu jumladan bo'sh joy) satrlarni taqqoslashda deyarli har doim e'tiborga olinmaydi. Faqatgina istisnolar - bu mos keladigan pozitsiyalarda topilgan tinish belgilaridan tashqari hamma narsada mos keladigan chiziqlar. Taqqoslash algoritmi uchun misolimdagi satrlar (saralashdan keyin) quyidagicha ko'rinadi:

АбакановМихаилмаляр
ЁлкинаЭллакрановщица
ИвановаАлламаляр
ИвановАндрейслесарь

O'lchovlar jadvalida rus tilidagi bosh harflar kichik harflardan keyin kelishini hisobga olsak (uchinchi darajada). dan og'irroq ), saralash mutlaqo to'g'ri ko'rinadi.

O'zgaruvchini o'rnatishda LC_COLLATE=C bayt-bayt taqqoslashni belgilaydigan maxsus jadval yuklanadi

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

Unicode da Yo kod nuqtasi A dan oldin kelganligi sababli, satrlar mos ravishda tartiblangan.

Matn va ikkilik jadvallar

Shubhasiz, satrlarni taqqoslash juda keng tarqalgan operatsiya va jadvalni tahlil qilishdir CTT ancha qimmat protsedura. Jadvalga kirishni optimallashtirish uchun u buyruq yordamida ikkilik shaklga kompilyatsiya qilinadi localdef.

komanda localdef Milliy xususiyatlar jadvaliga ega faylni parametr sifatida qabul qiladi (variant -i), unda barcha belgilar Unicode nuqtalari bilan ifodalanadi va Unicode nuqtalari va ma'lum bir kodlash belgilari o'rtasidagi yozishmalar fayli (variant). -f). Ish natijasida oxirgi parametrda ko'rsatilgan nom bilan mahalliy til uchun ikkilik fayllar yaratiladi.

glibc ikkita ikkilik fayl formatlarini qo'llab-quvvatlaydi: "an'anaviy" va "zamonaviy".

An'anaviy format mahalliy til nomi pastki katalog nomi ekanligini anglatadi /usr/lib/locale/. Ushbu kichik katalog ikkilik fayllarni saqlaydi LC_COLLATE, LC_CTYPE, LC_TIME va h.k. Fayl LC_IDENTIFICATION mahalliy tilning rasmiy nomini (katalog nomidan farq qilishi mumkin) va izohlarni o'z ichiga oladi.

Zamonaviy format barcha tillarni bitta arxivda saqlashni o'z ichiga oladi /usr/lib/locale/locale-archive, qaysi yordamida barcha jarayonlar virtual xotiraga xaritada glibc. Zamonaviy formatdagi mahalliy til nomi ba'zi kanonizatsiyaga bog'liq - kodlash nomlarida faqat kichik harflarga qisqartirilgan raqamlar va harflar qoladi. Shunday qilib ru_RU.KOI8-R, sifatida saqlanadi ru_RU.koi8r.

Kirish fayllari joriy katalogda, shuningdek kataloglarda qidiriladi /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ fayllar uchun CTT va mos ravishda fayllarni kodlash.

Masalan, buyruq

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

faylni kompilyatsiya qiladi /usr/share/i18n/locales/ru_RU kodlash faylidan foydalanish /usr/share/i18n/charmaps/MAC-CYRILLIC.gz va natijani saqlang /usr/lib/locale/locale-archive nomi ostida ru_RU.maccyrillic

Agar siz o'zgaruvchini o'rnatsangiz LANG = uz_US.UTF-8 The glibc quyidagi fayllar va kataloglar ketma-ketligida mahalliy ikkilik fayllarni qidiradi:

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

Agar mahalliy til an'anaviy va zamonaviy formatlarda bo'lsa, u holda zamonaviyga ustunlik beriladi.

Buyruq yordamida kompilyatsiya qilingan tillar ro'yxatini ko'rishingiz mumkin mahalliy - a.

Taqqoslash jadvalini tayyorlash

Endi, bilim bilan qurollangan holda, siz o'zingizning ideal satrlarni taqqoslash jadvalini yaratishingiz mumkin. Ushbu jadval rus harflarini, shu jumladan Yo harfini to'g'ri solishtirishi va shu bilan birga jadvalga muvofiq tinish belgilarini hisobga olishi kerak. ASCII.

O'zingizning saralash jadvalingizni tayyorlash jarayoni ikki bosqichdan iborat: og'irliklar jadvalini tahrirlash va buyruq yordamida ikkilik shaklga kompilyatsiya qilish. localdef.

Taqqoslash jadvali minimal tahrirlash xarajatlari bilan formatda sozlanishi uchun ISO 14652 Mavjud jadvalning og'irliklarini sozlash uchun bo'limlar taqdim etiladi. Bo'lim kalit so'z bilan boshlanadi qayta tartiblash - keyin va almashtirish amalga oshiriladigan pozitsiyani ko'rsatadi. Bo'lim chiziq bilan tugaydi qayta tartiblash. Agar jadvalning bir nechta bo'limlarini tuzatish zarur bo'lsa, unda har bir bunday bo'lim uchun bo'lim yaratiladi.

Men fayllarning yangi versiyalaridan nusxa oldim iso14651_t1_common и ru_RU omboridan glibc mening uy katalogimga ~/.local/share/i18n/locales/ va bo'limni biroz tahrir qildim. LC_COLLATE в ru_RU. Fayllarning yangi versiyalari mening versiyamga to'liq mos keladi glibc. Agar siz fayllarning eski versiyalaridan foydalanmoqchi bo'lsangiz, jadvaldagi ramziy nomlarni va almashtirish boshlanadigan joyni o'zgartirishingiz kerak bo'ladi.

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

Aslida, maydonlarni o'zgartirish kerak bo'ladi LC_IDENTIFICATION shunday qilib, ular mahalliyga ishora qiladilar ru_MY, lekin mening misolimda bu talab qilinmadi, chunki men arxivni mahalliy tillarni qidirishdan chiqarib tashladim mahalliy-arxiv.

ekan localdef o'zgaruvchi orqali papkamdagi fayllar bilan ishladim I18NPATH Kirish fayllarini qidirish uchun qo'shimcha katalog qo'shishingiz mumkin va ikkilik fayllarni saqlash uchun katalog slash bilan yo'l sifatida ko'rsatilishi mumkin:

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

POSIX ichida deb taxmin qiladi TILI mahalliy fayllar bilan kataloglarga mutlaq yo'llarni oldinga qiyshiq chiziqdan boshlab yozishingiz mumkin, lekin glibc в Linux barcha yo'llar o'zgaruvchi orqali bekor qilinishi mumkin bo'lgan asosiy katalogdan hisoblanadi LOCPATH. O'rnatishdan keyin LOCPATH=~/.local/lib/locale/ mahalliylashtirish bilan bog'liq barcha fayllar faqat mening papkamda qidiriladi. O'zgaruvchilar to'plami bilan mahalliy tillar arxivi LOCPATH e'tiborga olinmagan.

Mana hal qiluvchi sinov:

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

Xayr! Biz uddaladik!

Hatolar ustida ishlash

Men boshida berilgan satrlarni saralash bo'yicha savollarga allaqachon javob berganman, ammo xatolar haqida bir nechta savollar mavjud - ko'rinadigan va ko'rinmas.

Keling, asl muammoga qaytaylik.

Va dastur saralamoq va dastur Qo'shiling dan bir xil satr taqqoslash funktsiyalaridan foydalaning glibc. Bu qanday bo'ldi Qo'shiling buyruq bo'yicha tartiblangan qatorlarda tartiblash xatosi berdi saralamoq mahalliy tilda en_US.UTF-8? Javob oddiy: saralamoq butun satrni taqqoslaydi va Qo'shiling faqat kalitni solishtiradi, bu sukut bo'yicha birinchi bo'sh joy belgisigacha bo'lgan satrning boshidir. Mening misolimda, bu xato xabariga olib keldi, chunki satrlardagi birinchi so'zlarni saralash to'liq satrlarni tartiblash bilan mos kelmadi.

Mahalliy "C" tartiblangan satrlarda birinchi bo'shliqgacha bo'lgan boshlang'ich pastki satrlar ham tartiblanishini kafolatlaydi, lekin bu faqat xatoni maskalaydi. Xato xabarisiz noto'g'ri fayllarni birlashtirish natijasini beradigan ma'lumotlarni (bir xil familiyalarga ega, ammo ismlari har xil bo'lgan odamlar) tanlash mumkin. Agar xohlasak Qo'shiling to'liq nomi bilan birlashtirilgan fayl satrlari, keyin to'g'ri yo'l maydon ajratuvchisini aniq belgilash va butun qator bo'yicha emas, balki kalit maydoni bo'yicha tartiblash bo'ladi. Bunday holda, birlashma to'g'ri davom etadi va hech qanday tilda xatolik bo'lmaydi:

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

Kodlashda muvaffaqiyatli bajarilgan misol CP1251 boshqa xatoni o'z ichiga oladi. Gap shundaki, menga ma'lum bo'lgan barcha tarqatishlarda Linux paketlarda kompilyatsiya qilingan til yo'q ru_RU.CP1251. Agar kompilyatsiya qilingan til topilmasa, u holda saralamoq jimgina bayt-bayt taqqoslashdan foydalanadi, bu biz kuzatgan narsadir.

Aytgancha, kompilyatsiya qilingan mahalliy tillarning mavjud emasligi bilan bog'liq yana bir kichik xatolik mavjud. Jamoa LOCPATH=/tmp mahalliy -a barcha mahalliy joylar ro'yxatini beradi mahalliy-arxiv, lekin o'zgaruvchilar to'plami bilan LOCPATH barcha dasturlar uchun (shu jumladan eng ko'p mahalliy) bu joylar mavjud bo'lmaydi.

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

xulosa

Agar siz satrlarni baytlar to'plami deb o'ylashga odatlangan dasturchi bo'lsangiz, unda sizning tanlovingiz LC_COLLATE=C.

Agar siz tilshunos yoki lug'at kompilyatori bo'lsangiz, o'zingizning tilingizda kompilyatsiya qilganingiz ma'qul.

Agar siz oddiy foydalanuvchi bo'lsangiz, unda siz shunchaki buyruqni bajarishga ko'nikishingiz kerak a-a Harf bilan boshlangan fayllar bilan aralashtirilgan nuqta bilan boshlangan fayllarni chiqaradi va Midnight Commander, nomlarni saralash uchun o'zining ichki funksiyalaridan foydalanadi, nuqta bilan boshlanadigan fayllarni ro'yxatning boshiga qo'yadi.