Въведение

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

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

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

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

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

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

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

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

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

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

Да отложим за момента join и да се съсредоточим на 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 и join защо във всичките ми примери има грешки
накрая, как да сортираме редове по свой вкус
Сортиране в Юникод

Първото спиране ще бъде техническият доклад № 10 с название

Unicode collation algorithm unicode.org на сайта . Докладът съдържа много технически детайли, така че ще си позволя да представя кратко изложение на основните идеи.Сравнение

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

Ö е между , а в кодировката О и PCP850 тя попада между ÿ Ü и Може да се опитаме да се абстрахираме от конкретната кодировка и да разглеждаме "идеалните" букви, които са подредени в някакъв ред, както е направено в Юникод. Кодировките.

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) означава, че на съответното ниво на сравнение, единицата не участва в сравнение. Сравнението на низове може да се повтаря няколко пъти, с използване на тежестите на съответните нива. На всяко от нивата тежестите на единиците за сравнение на двата низа последователно се сравняват помежду си.

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

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

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

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

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

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

В този момент поведението на сортиране от нашия пример става малко по-разбираемо. Добре би било да го сравним с стандарта Юникод.

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

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

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

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

Струва ми се, че на сайта ICU може да се намери уточнение за работата на алгоритъма за сравнение при обработка на знаци за препинание. В примерите Collation 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 (The Unicode collation algorithm) и/или на близък до него стандарт ISO 14651 (International string ordering and comparison). По отношение на последния стандарт следва да се отбележи, че на сайта standards.iso.org ISO 14651 официално е обявен за общодостъпен, но съответната връзка води до несъществуваща страница. Гугъл показва няколко страници с връзки към официални сайтове, които предлагат да купят електронна копия на стандарта за стотина евро, но на третата-четвъртата страница на търсенето могат да се намерят и директни връзки до PDF. По принцип, стандартът почти не се различава от UCA, но се чете по-скучно, тъй като не съдържа ярки примери за национални особености в сортирането на низове.

Най-интересната информация на wiki се оказа връзка към багтрекера с обсъждането на реализацията на сравнението на низове в glibc. От обсъждането можем да научим, че в glibc за сравнение на низове се използва ISOтаблица The Common Template Table (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

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

ИГНОРИРАЙ; ИГНОРИРАЙ; ИГНОРИРАЙ; % ПРОБЕЛ
 ИГНОРИРАЙ; ИГНОРИРАЙ; ИГНОРИРАЙ; % УЗКИ ЗНАК
 ИГНОРИРАЙ; ИГНОРИРАЙ; ИГНОРИРАЙ; % ЗНАК ЗА ЦИТИРАНЕ
...

Ясно е, че в тази таблица знаците за препинание са от таблицата 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/share/i18n/locales/ и леко редактирах раздела LC_COLLATE в ru_RU. Новите версии на файловете са напълно съвместими с моята версия glibc. Ако искате да използвате старите версии на файловете, ще трябва да промените символичните имена и мястото, от което започва замяната в таблицата.

LC_COLLATE
% Копирайте шаблона от ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % ПРОБЕЛ
 ;;; % ЗНАК ВЪЗКЛИКНУВАНЕ
 ;;; % ЗНАК ЗА ЦИТИРАНЕ
...
 ;;; % ДЯСНА ЗАВИТИНА
 ;;; % ТИЛДА
reorder-end
END LC_COLLATE

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

За да localedef работала с файлами в моей папке через переменную I18NPATH можно добавить дополнительный каталог для поиска входных файлов, а каталог для сохранения двоичных файлов можно указать в виде пути со слэшами:

$> I18NPATH=~/.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 и програмата join използват одни и те же функции сравнения строк из glibc. Как же се случи така, че join показваше грешка при сортиране на редове, отсортированными командой sort в локали en_US.UTF-8? Ответ прост: sort сравнява цялата низ, а join сравнява само ключът, който по подразбиране е началото на низа до първия пробелен символ. В моем примере это привело к сообщению об ошибке поскольку сортировка первых слов в строках не совпала с сортировкой полных строк.

Локаль "C" гарантира, че в сортираните редове началените подредби до първото пространство също ще бъдат сортирани, но това само маскира грешката. Може да се подбират такива данни (хора с едни и същи фамилии, но различни имена), които без съобщение за грешка да дадат неправилен резултат при обединяване на файловете. Ако искаме, че join обединява редовете на файловете по ФИО, то правилният начин е явно да се посочи разделителя на полетата и сортиране по ключовото поле, а не по целия ред. В този случай и обединяването ще премине правилно и в никаква локализация няма да има грешки:

$> 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, който използва своите вътрешни функции за сортиране на имена, изважда файловете, започващи с точка, в началото на списъка.