Въведение

Всичко започна с кратък скрипт, който трябваше да съедини информацията за адресите e-mail на служителите, получени от списъка с потребители на електронната поща, с длъжностите на служителите, получени от базата на отдела по човешки ресурси. И двата списъка бяха експортирани в текстови файлове с кодировка UTF-8 UTF-8 и запазени с линеен край за юникс.

Съдържание mail.txt

Иванов Андрей;ia@example.com

Съдържание buhg.txt

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

За съединяването файловете бяха подредени с юникс командата sort и подадени на входа на юникс програмата присъединете се, която неочаквано приключи с грешка:

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

Прегледът на резултата от подредбата показа, че в общи линии подредбата е правилна, но в случай на съвпадения между мъжки и женски фамилии, женските са пред мъжките:

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

Изглежда като бъг в подредбата на Юникод или като проявление на феминизма в алгоритъма за подреждане. Първото, разбира се, е по-правдоподобно.

Отклоняваме го за момента присъединете се и се фокусираме на sort. Нека опитаме да решим задачата с метода на научния проб и грешка. За начало, ще сменим локала от en_US на ru_RU. За подредбата беше достатъчно да зададем променливата на средата LC_COLLATE, но няма да бъдем дребнави:

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

Нищо не се е променило.

Нека опитаме да преформатираме файловете в еднобайтова кодировка:

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

Отново нищо не се е променило.

Нищо не може да се направи, ще трябва да потърсим решение в интернет. Нямаше нищо конкретно за руските фамилии, но имаше въпроси за други странности в подреждането. Например, такава проблема: unix sort третира ‘-’ (тире) знаци като невидими. Накратко казано, редовете "a-b", "aa", "ac" се подреждат като "aa", "a-b", "ac".

Отговорът навсякъде е стандартен: използвайте програмистката локала "C" и ще бъдете щастливи. Опитваме:

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

Нещо се е променило. Ивановите застанаха в правилния ред, но Елкина някак си се е плъзнала. Връщаме се към основната задача:

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

Сработи без грешки, както интернетът обеща. И то независимо от Елкина в първия ред.

Проблемът изглежда е решен, но за всеки случай ще пробваме още една руска кодировка — Windows. CP1251:

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

Резултатът от сортирането, странно, ще съвпадне с локализацията "C", и целият пример, съответно, преминава без грешки. Някаква мистерия.

Не обичам мистерията в програмирането, тъй като обикновено маскира грешките. Ще се наложи сериозно да се занимавам с въпроса как работи sort и на какво влияе LC_COLLATE .

В края ще се опитам да отговоря на въпросите:

защо женските фамилии не се сортирват правилно
защо LANG=ru_RU.CP1251 се оказа еквивалент на LANG=C
защо имат sort и присъединете се различни представления за реда на сортираните редове
защо в всичките ми примери има грешки
накрая, как да сортираме редовете по свой вкус

Сортиране в Юникод

Първата спирка ще бъде техническият доклад № 10 с наименование Алгоритъм за колация в Юникод сайта unicode.org. Докладът съдържа много технически детайли, така че ще си позволя да представя кратко изложение на основните идеи.

Колация — "сравняване" на редове — основата на всеки алгоритъм за сортиране. Самите алгоритми могат да се различават ("във възходящ ред", "обединяване", "бърза"), но всички те ще използват сравнение на двойка редове, за да определят реда на тяхното следване.

Сортирането на редове на естествен език е доста сложен проблем. Дори в най-простите еднобайтови кодировки редът на буквите в азбуката, което е различно от английската латиница, вече няма да съвпадне с реда на числовите стойности, с които тези букви се кодирани. Така, в немската азбука, буквата Ö се намира между О и P, а в кодировката CP850 попада между ÿ и Ü.

Може да се опитате да се абстрахирате от конкретната кодировка и да разглеждате "идеалните" букви, разположени в определен ред, както е направено в Юникод. Кодировките UTF8, UTF16 или еднобайтовата KOI8-R (ако е необходимо ограничено подмножество на Юникод) ще дават различни числови представления на буквите, но ще се отнасят към едни и същи елементи на основната таблица.

Оказва се, че дори и да изградим таблица за символите от нулата, няма да успеем да зададем универсален ред на символите. В различните национални азбуки, които използват еднакви букви, редът на тези букви може да се различава. Например, на френски Æ ще се счита за лигатура и ще се сортира като ред AE. В норвежкия език обаче Æ ще бъде отделна буква, която се намира след Z. Между другото, освен лигатурите от типа на Æ съществуват букви, писани с няколко символа. Например, в чешката азбука има буква Ch, която стои между H и I.

Освен различията в азбуките съществуват и други национални традиции, влияещи върху сортирането. В частност, възниква въпросът какъв ред трябва да следват в речника думите, състоящи се от главни и малки букви? Също така, върху сортирането могат да повлияят особеностите на използване на препинателните знаци. На испански език в началото на въпросително изречение се поставя обърнат въпросителен знак (¿Te gusta la música?). В този случай е очевидно, че въпросителните изречения не трябва да се групират в отделен кластер извън азбуката, а как да се сортират редове с други препинателни знаци?

Не възнамерявам да се спирам на сортирането на редове в езици, които много се различават от европейските. Отбелязвам, че в езици с посока на писане отдясно наляво или отгоре надолу символите в редовете вероятно се съхраняват в реда на четене, а дори при неалфавитни писмености има свои начини за символно подреждане на редовете. Например, йероглифите могат да се подреждат по написването (ключове на китайските йероглифы) или по произношение. Как трябва да се подреждат емодзита, честно казано, не си представям, но определено може да се измисли нещо за тях.

На базата на горепосочените особености бяха формулирани основните изисквания за сравнение на редове, основани на таблиците на Юникода:

сравнението на редове не зависи от позицията на символите в кодовата таблица;
последователностите от символи, образуващи единен символ, се приведат към каноничен вид (A + горен кръгче е същото като Å);
при сравнение на редове символът се разглежда в контекста на реда и, при необходимост, се съединява с близките до него в единна единица за сравнение (Ch в чешкия) или се разделя на няколко (Æ на френски);
всички национални особености (азбука, главни/малки букви, знаци за пунктуация, ред на видовете писменост) трябва да се настройват до ръчно определяне на ред (емодзи);
сравнението е важно не само за сортиране, но и на много други места, например за задаване на диапазони от редове (заместване {А… я} в bash);
сравнението трябва да се извършва достатъчно бързо.

Освен това, авторите на доклада формулирали свойства на сравнение, на които разработчиците на алгоритми не трябва да разчитат:

алгоритъмът за сравнение не трябва да изисква отделен набор от символи за всеки език (руският и украинският език споделят повечето символи на кирилицата);
сравнението не трябва да се основава на реда на символите в таблиците на Юникод;
теглото на реда не трябва да бъде атрибут на реда, тъй като един и същ ред в различни културни контексти може да има различни тегла;
теглата на редовете могат да се променят при сливане или разделяне (от x < y не следва, че xz < yz);
различни редове, които имат еднакви тегла, се считат за равни от гледна точка на алгоритъма за сортиране. Въвеждането на допълнителен ред за такива редове е възможно, но може да влоши производителността;
при повторни сортирания, редовете, които имат еднакви тегла, могат да променят местата си. Устойчивостта е свойство на конкретния алгоритъм за сортиране, а не свойство на алгоритъма за сравнение на редове (вж. предишната точка);
правилата за сортиране могат да се променят с времето, когато културните традиции се уточняват/променят.

Така също е посочено, че алгоритъмът за сравнение не знае нищо за семантиката на обработваните редове. Така, редовете, състоящи се само от цифри, не трябва да се сравняват като числа, а в списъци с английски наименования не трябва да се премахва артикулът (Beatles, The).

За да се удовлетворят всичките посочени изисквания, е предложен многостепенен (фактически четиристепенен) табличен алгоритъм за сортиране.

Предварително, символите в реда се преобразуват в каноничен вид и се групират в единици за сравнение. На всяка единица за сравнение се присвояват няколко тегла, отговарящи на различни нива на сравнение. Теглата на единиците за сравнение са елементи от подредени множества (в този случай цели числа), които могат да се сравняват по-голямо-малко. Специална стойност IGNORED (0x0) означава, че в съответния сравнителен ниво, тази единица не участва в сравнението. Сравняването на низове може да се повтаря няколко пъти, използвайки теглата на съответните нива. На всяко от нивата теглата на единиците за сравнение на два низa последователно се сравняват помежду си.

В различни реализации на алгоритъма за различни национални традиции величините на коефициентите могат да се различават, но в състава на стандарта Юникод влиза основна таблица с тегла — "Default Unicode Collation Element Table" (DUCET). Искам да отбележа, че задаването на променливата LC_COLLATE фактически е указание за избор на таблицата с тегла в функцията за сравнение на низове.

Теглови коефициенти DUCET са устроени по следния начин:

на първото ниво всички букви се приведат към едно регистрово, диакритичните знаци се отстраняват, а пунктуацията (не всичката) се игнорира;
на второто ниво се вземат предвид само диакритичните знаци;
на третото ниво се взима предвид само регистърът;
на четвъртото ниво се вземат предвид само знаците на пунктуацията.

Сравнението се извършва в няколко прохода: първо се сравняват коефициентите на първото ниво; ако теглата съвпадат, следва повторно сравнение с теглата на второто ниво; след това, възможно, и третото и четвъртото.

Сравнението приключва, когато в низовете се намират съответстващи единици за сравнение с различни тегла. Низове, които имат равни тегла на всички четири нива, се считат за равни помежду си.

Този алгоритъм (с много допълнителни технически детайли) е дал името на отчет № 10 — "Unicode Collation Algorithm" (UCA).

На това място поведението на сортирането от примера ни става малко по-разбираемо. Бихме могли да го сравним с стандарта Юникод.

За тестване на реализациите UCA съществува специален тест, използващ файл с тегла, реализиращ DUCET. В файла с тегла може да намерите различни интересни неща. Например, там има ред на маджонг костяшки и европейски домино, както и ред на масти в колода карти (символ 1F000 и след това). Картичките са подредени по правилата на бриджа — ПЧБТ, а картите в маста — в последователност Т,2,3… К.

Ръчна проверка на правилността на сортирането на низовете в съответствие с DUCET беше доста изтощаваща, но, за щастие за нас, съществува образцова реализация на библиотеката за работа с Юникод — "Международни компоненти за Юникод" (ICU).

На сайта на тази библиотека, разработена в IBM, има демонстрационни странички, включително и страница на алгоритъма за сравнение на низове. Въвеждаме нашите тестови низове с настройки по подразбиране и, о чудо, получаваме перфектно българско подреждане.

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

Между другото, в сайта ICU можете да намерите уточнения за работата на алгоритъма за сравнение при обработка на препинателни знаци. В примерите FAQ за подредба се игнорират апостроф и тире.

Юникод ни помогна, но причините за странното поведение sort в Linux ще трябва да се търсят някъде другаде.

Подреждане в glibc

Бърз преглед на изходния код на утилитата sort от GNU Core Utils показа, че в самата утилита локализацията се свежда до печат на текущата стойност на променливата LC_COLLATE при стартиране в режим на отстраняване на грешки:

$ sort --debug buhg.txt > buhg.srt
sort: използвайки ‘en_US.UTF8’ правила за сортиране

Сравнението на низове се извършва с стандартната функция strcoll, така че всичко интересно се намира в библиотеката glibc.

На wiki проекта glibc на сравнението на низове е посветен един абзац. От този абзац можем да разберем, че в glibc подреждането се основава на вече известния ни алгоритъм UCA (Алгоритъм за подреждане в Юникод) и/или на близкия до него стандарт ISO 14651 (Международно подреждане на низове и сравнение). По отношение на последния стандарт следва да се отбележи, че на сайта standards.iso.org ISO 14651 официално е обявен за обществено достъпен, но съответната връзка води до несъществуваща страница. Google дава няколко страници с линкове към официални сайтове, които предлагат да купят електронно копие на стандарта за стотина евро, но на третата-четвъртата страница от резултатите на търсенето ще намерите и директни линкове за PDF. Като цяло, стандартът практически не се различава от UCA, но се чете по-скучно, тъй като не съдържа ярки примери за национални особености на подреждането на низове.

Най-интересната информация на wiki се оказа връзка към багтрекера с обсъждане на реализацията на сравнението на низове в glibc. От обсъждането може да се разбере, че в glibc за сравнението на низове се използва ISOтаблица Общата таблица на шаблоните (CTT), адресът на която може да бъде намерен в приложението A на стандарта ISO 14651. Между 2000 и 2015 години тази таблица в glibc нямаше мейнтейнер и сравнително се различаваше (поне на вид) от текущата версия на стандарта. От 2015 до 2018 година се извършваше адаптация към новата версия на таблицата и в момента имате шанс да срещнете в реалния живот както новия вариант на таблицата (CentOS 8), така и стария (CentOS 7).

Сега, когато имаме цялата информация за алгоритъма и помощните таблици, можем да се върнем обратно към основния проблем и да разберем как да сортираме правилно редовете в руската локализация.

ISO 14651/14652

Изходният код на интересуващата ни таблица CTT в повечето дистрибуции Linux се намира в директорията /usr/share/i18n/locales/. Самата таблица се намира в файла iso14651_t1_common. След това този файл с директивата copy iso14651_t1_common се включва във файла iso14651_t1, който от своя страна се включва в националните файлове, включително в en_US и ru_RU. В повечето дистрибуции Linux всички изходни файлове са включени в основната инсталация, но ако ги няма, ще трябва да инсталирате допълнителен пакет от дистрибуцията.

Структурата на файла iso14651_t1 може да изглежда ужасно многословна с неясни правила за построяване на имена, но ако се задълбочите, всичко е доста просто. Структурата е описана в стандарта ISO 14652, копия на който можете да изтеглите от сайта open-std.org. Друго описание на формата на файла можете да прочетете в спецификациите POSIX от OpenGroup. Като алтернатива на четенето на стандарта можете да проучите изходните текстове на функцията collate_read в glibc/locale/programs/ld-collate.c.

Структурата на файла изглежда по следния начин:

По подразбиране символът е използван като екраниращ символ и краят на реда след символа # е коментар. И двата символа могат да бъдат пренасочени, което е направено в новата версия на таблицата:

escape_char /
comment_char %

В файла ще срещнете токени в формата <Uxxxx> или <Uxxxxxxxx> (където x — шестнадесетичен знак). Това е шестнадесетичен представяне на кодовите точки на Юникод в кодирането UCS-4 (UTF-32). Всички останали елементи в остри скоби (включително <Uxxxx_xxxx>, <2> и подобни), се считат за обикновени низови константи, които нямат особено значение извън контекста.

Редът LC_COLLATE ни казва, че следва как започват данните, описващи сравнения на низовете.

Първо се задават имената на теговете в таблицата за сравнение и имената на комбинациите от символи. Обикновено, двата типа имена принадлежат на две различни същности, но в реалния файл те са смесени. Имената на теговете се задават с ключовата дума collating-symbol (символ за сравнение), тъй като при сравнението на символи Юникод с еднакви тегове, те ще се считат за еквивалентни символи.

Общата дължина на секцията в текущата ревизия на файла е около 900 реда. Извадих примери от няколко места, за да покажа произволността на имената и няколко вида синтаксис.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Гарантирано най-голямо стойност на символа. Дръжте в края на този списък
...
collating-element  от ""
collating-element  от ""

collating-symbol регистрира ред OSMANYA в таблицата с имена на тегове
collating-symbol .. регистрира последователност от имена, състоящи се от префикс S и шестнадесетичен числов суфикс от 1D000 до 1D35F.
FFFF в collating-symbol изглежда като голямо беззнаково цело число в шестнадесетична система на числата, но <SFFFF> е просто име, което може да изглежда като <VERYBIGVAL>
име <U0413> означава кодова точка в кодировката UCS-4
collating-element от "" регистрира ново име за двойка кодови точки на Юникод.

Когато имената на теговете са определени, задават се самите тегла. Тъй като при сравнението има значение само отношението по-голямо-малко, теглата се определят с проста последователност на изброяване на имената. Първо се изброяват "по-леките" тегла, след това "по-тежките". Напомням, че на всеки Юникод символ се присвояват четири различни тегла. Тук те са сведени в една подредена последователност. Теоретично, всяко символно име може да бъде използвано на който и да е от четирите нива, но коментарите подсказват, че разработчиците умствено разделят имената по нива.

% Символично тегови присвоявания

% Трето ниво тегови присвоявания




...
% Второ ниво тегови присвоявания

 % СЪЕДИНЯВАЩА НИСКА ЛИНИЯ
 % СЪЕДИНЯВАЩА ЗАПЕТА ГОРЕ
 % СЪЕДИНЯВАЩА ОБРАТНА ЗАПЕТА ГОРЕ
...
% Първо ниво тегови присвоявания
 % ХОРИЗОНТАЛНА ТАБУЛАЦИЯ
 % НОВ РЕД
 % ВЕРИТОРНА ТАБУЛАЦИЯ
...
 % КИРИЛИЧНА МАЛКА БУКВА ДЕ
 % КИРИЛИЧНА МАЛКА БУКВА КОМИ ДЕ
 % КИРИЛИЧНА МАЛКА БУКВА ДЖЕ
 % КИРИЛИЧНА МАЛКА БУКВА КОМИ ДЖЕ
 % КИРИЛИЧНА МАЛКА БУКВА ГЕ
 % КИРИЛИЧНА МАЛКА БУКВА ЗЕ С НАКЛОН
 % КИРИЛИЧНА МАЛКА БУКВА ИЕ
 % КИРИЛИЧНА МАЛКА БУКВА ИЕ С БРЕВЕ
 % КИРИЛИЧНА МАЛКА БУКВА УКРАИНСКО ИЕ
 % КИРИЛИЧНА МАЛКА БУКВА ЖЕ

Накрая, самата таблица с тегла.

Секцията с тегла е заключена в редове с ключови думи order_start и order_end. Допълнителни параметри order_start определят, в каква посока се преглеждат редовете на всяко ниво на сравнение. По подразбиране се използва параметърът forward. Тялото на секцията се състои от редове, които съдържат код на символа и четири негови тегла. Кодът на символа може да бъде представен самият символ, кодова точка или символично име, определено по-рано. Теглата могат също да се задават с символични имена, кодови точки или самите символи. Ако се използват кодови точки или символи, теглото им съвпада с числовата стойност на кодовата точка (позицията в таблицата Юникод). Символите, които не са явно посочени (както разбирам), се считат присвоени в таблицата с основно тегло, съвпадащо с позицията в таблицата Юникод. Специалната стойност на теглото IGNORE означава, че на съответното ниво на сравнение този символ се игнорира.

За демонстрация на структурата на теглата избрах три доста очевидни фрагмента:

символи, които се игнорират напълно
символи, еквивалентни на числото три на първите две нива
началото на кирилския алфавит, който не съдържа диакритични знаци и затова се сортира предимно по първо и трето ниво.

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

Сега можете отново да се върнете към сортирането на примерите от началото на статията. Проблемът е в тази част от таблицата с тежестите:

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

Ясно е, че в тази таблица знаците за препинание от таблицата ASCII (включително интервали) практически винаги се игнорират при сравняване на строки. Изключението са само строките, които съвпадат напълно, освен за знаците за препинание, които се срещат на съвпадащи позиции. Строките в моя пример (след сортиране) за алгоритъма за сравнение изглеждат така:

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

Въз основа на факта, че в таблицата с тежестите главните букви в руския език са след малките (на трето ниво <CAP> по-тежки от <MIN>), сортирането изглежда абсолютно правилно.

При задаване на променливата LC_COLLATE=C се зарежда специална таблица, която задава байтово сравнение

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* 1st-level table */
  6 * sizeof (uint32_t),
  /* 2nd-level table */
  7 * sizeof (uint32_t),
  /* 3rd-level table */
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'fe', L'xff'
};

Тъй като в Юникода кодовата точка Ё заема позиция пред А, следователно строките се сортират съответно.

Текстови и бинарни таблици

Очевидно е, че сравнението на строки е изключително често срещана операция, а анализът на таблицата CTT доста често скъпа процедура. За оптимизация на достъпа до таблицата, тя се компилира в двоичен формат с командата localedef.

Екип localedef приема като параметри файл с таблица за национални особености (опция -i), в който всички символи са представени с точки на Юникод, и файл за съвпадение на точките на Юникод с символите на конкретен кодек (опция -f). В резултат на работата се създават двоични файлове за локализация, с име, посочено в последния параметър.

Glibc поддържа два формата на двоични файлове: "традиционен" и "модерен".

Традиционният формат предполага, че името на локализацията е името на подкаталог в /usr/lib/locale/. В този подкаталог се съхраняват двоични файлове LC_COLLATE, LC_CTYPE, LC_TIME и така нататък. Файлът LC_IDENTIFICATION съдържа формалното име на локализацията (което може да се различава от името на каталога) и коментари.

Модерният формат предполага съхранение на всички локализации в единен архив /usr/lib/locale/locale-archive, който се отразява в виртуалната памет на всички процеси, които го използват glibc. Името на локализацията в модерния формат преминава през известна канонизация - в имената на кодировките остават само цифри и букви, приведени в малки букви. Така ru_RU.KOI8-R, ще бъде запазено като ru_RU.koi8r.

Входните файлове се търсят в текущия каталог, а също и в каталозите /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ за файлове CTT и файлове с кодировки съответно.

Например, командата

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

ще компилира файла /usr/share/i18n/locales/ru_RU с използване на файла с кодировка /usr/share/i18n/charmaps/MAC-CYRILLIC.gz и ще запази резултата в /usr/lib/locale/locale-archive с името ru_RU.maccyrillic

Ако зададете променливата LANG=en_US.UTF-8 , glibc ще търси двоични файлове за локализация в следната последователност от файлове и каталози:

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

Ако локализацията се среща и в традиционен, и в модерен формат, приоритетът се отдава на модерния.

Може да прегледате списъка с компилирани локализации с командата locale -a.

Подготовка на собствена таблица за сравнение

Сега, въоръжени със знания, можем да създадем собствена идеална таблица за сравнение на низове. Тази таблица трябва да сравнява правилно руските букви, включително буквата Ё, и да отчита пунктуацията в съответствие с таблицата ASCII.

Процесът на подготовка на собствената таблица за сортиране се състои от два етапа: редактиране на таблицата с тегла и компилиране в двоичен формат с командата localedef.

За да може таблицата за сравнение да бъде настроена с минимални разходи за редактиране, в формата ISO 14652 предвидени са секции за корекция на теговете в съществуващата таблица. Секцията започва с ключовата дума reorder-after и указание на позицията, след която ще се извърши замяната. Секцията се завършва с реда reorder-end. Ако е необходимо да се коригират няколко участъка от таблицата, се създава една секция за всеки такъв участък.

Копирах нови версии на файловете iso14651_t1_common и ru_RU от репозитория glibc в моя домашен каталог ~\/local\/.local\/share\/i18n\/locales\/ и леко редактирах раздела LC_COLLATE в ru_RU. Новите версии на файловете са напълно съвместими с моята версия glibc. Ако желаете да използвате старите версии на файловете, ще трябва да промените символичните имена и мястото, откъдето започва замяната в таблицата.

LC_COLLATE
% Копирайте шаблона от ISO\/IEC 14651
копирайте "iso14651_t1"
reorder-after 
 ; % SPACE
 ; % EXCLAMATION MARK
 ; % QUOTATION MARK
...
 ; % RIGHT CURLY BRACKET
 ; % TILDE
reorder-end
END LC_COLLATE

Всъщност, би трябвало да променим полетата в LC_IDENTIFICATION така че да сочат към местоположението ru_MY, но в моя пример това не беше необходимо, тъй като изключих от търсенето локалите архив locale-archive.

За да localedef работи с файловете в моята папка чрез променливата I18NPATH можете да добавите допълнителна директория за търсене на входни файлове, а директорията за съхранение на двоични файлове може да бъде посочена като път с наклонени линии:

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

POSIX предполага, че в LANG може да пишете абсолютни пътища към директории с файлове за локализация, започващи с директна наклонена линия, но glibc в Linux всички пътища се считат от базовата директория, която може да бъде пренастроена чрез променливата LOCPATH. След задаване на LOCPATH=~\/local\/lib\/locale\/ всички файлове, свързани с локализацията ще се търсят само в моята папка. Архивът на локалите при зададена променлива LOCPATH се игнорира.

Ето го решаващият тест:

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

Ура! Направихме го!

Работа по поправките

Вече отговорих на въпросите за сортиране на редовете, зададени в началото, но все още остават няколко въпроса за грешките — видими и невидими.

Да се върнем към първоначалната задача.

И програмата sort и програмата присъединете се използват едни и същи функции за сравнение на редове от glibc. Как така стана? присъединете се имаше грешка при сортирање на редиците, сортирани со команда sort в локал en_US.UTF-8? Ответ прост: sort содржи целосен споредба, а присъединете се сравнува само клучот, кој по дифолт е почетокот на редот до првото празно место. Во мојот случај, тоа доведе до порака за грешка, бидејќи сортирот на првите зборови во редовите не се совпадна со сортирот на целите редови.

Локал "C" гарантира дека во сортираните редици почетните подстроки до првото празно место исто така ќе бидат сортирани, но тоа само го маскира проблемот. Може да се изберат такви податоци (луѓе со исти презимиња, но различни имиња), кои без порака за грешка ќе дадат погрешен резултат при споите на датотеките. Ако сакаме присъединете се да споиме редиците од датотеки по Име и Презиме, правилниот начин ќе биде експлицитно да се укаже сепараторот на полињата и сортирање по клучното поле, а не по цела редица. Во тој случај, сподовите ќе се извршат правилно и во ниту една локал не ќе има грешки:

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

Успешно завршен пример во кодирање CP1251 има уште една грешка. Работата е во тоа што во сите познати дистрибуции Linux пакетите немаат компилирана локал ru_RU.CP1251. Ако компилираната локал не е пронајдена, тогаш sort тихо користи побайтно споредување, што и го набљудувавме.

Меѓутоа, има уште еден мал глюк поврзан со недостапноста на компилирани локали. Командата LOCPATH=/tmp locale -a ќе издаде список на сите локали во locale-archive, но при поставената променлива LOCPATH за сите програми (вклучувајќи ја и самата locale) овие локали ќе бидат недостапни.

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

Заключение

Ако сте програмер кој е навикнат да смета дека редиците се сет на бајтови, тогаш вашето избор LC_COLLATE=C.

Ако сте лингвист или составувач на речници, тогаш ви е подобро да ја компилирате вашата локал.

Ако сте прост корисник, доволно е да се навикнете на тоа што командата ls -a издава датотеки кои започнуваат со точка, во мешавина со датотеки кои започнуваат со буква, а Midnight Commander, който използва вътрешните си функции за сортиране на имена и изнася файловете, започващи с точка, в началото на списъка.