Как Linux'овский sort сортирует строки

Введение

Всё началось с короткого скрипта, который должен был объединить информацию об адресах e-mail сотрудников, полученных из списка пользователей почтовой рассылки, с должностями сотрудников, полученными из базы отдела кадров. Оба списка были экспортированы в текстовые файлы в кодировке Юникод UTF-8 и сохранены с юниксовскими концами строк.

Содержимое mail.txt

Иванов Андрей;[e-mail]

Содержимое buhg.txt

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

Для объединения файлы были отсортированы юниксовской командой sort и поданы на вход юниксовской программе join, которая неожиданно завершилась с ошибкой:

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

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

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

Выглядит как глюк сортировки в Юникоде или как проявление феминизма в алгоритме сортировки. Первое, конечно, правдоподобнее.

Отложим пока 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 treats '-' (dash) characters as invisible. Если кратко, то строки "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

Сработало без ошибок, как и обещал интернет. И это несмотря на Ёлкину в первой строке.

Проблема вроде бы решена, но на всякий случай попробуем ещё одну русскую кодировку — виндоузовскую 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. Отчёт содержит много технических деталей, так что я позволю себе привести краткое изложение основных идей.

Collation — "сравнение" строк — основа любого алгоритма сортировки. Сами алгоритмы могут отличаться ("пузырьком", "слиянием", "быстрый"), но все они будут использовать сравнение пары строк, для определения порядка их следования.

Сортировка строк на естественном языке — это довольно сложная проблема. Даже в простейших однобайтовых кодировках порядок букв в алфавите, хоть в чём-то отличающемся от английской латиницы, уже не будет совпадать с порядком числовых значений, которыми эти буквы кодируются. Так в немецком алфавите буква Ö стоит между О и 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) означает, что на соответствующем уровне сравнения данная единица в сравнении не участвует. Сравнение строк может повторяться несколько раз, с использованием весов соответствующих уровней. На каждом из уровней веса единиц сравнения двух строк последовательно сравниваются между собой.

В различных реализациях алгоритма для различных национальных традиций величины коэффициентов могут отличаться, но в состав стандарта Юникода входит базовая таблица весов — "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: using ‘en_US.UTF8’ sorting rules

Сравнение строк производится стандартной функцией 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 <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>"

• collating-symbol <OSMANYA> регистрирует строку OSMANYA в таблице имён весов
• collating-symbol <S1D000>..<S1D35F> регистрирует последовательность имён, состоящих из префикса S и шестнадцатеричного числового суффикса от 1D000 до 1D35F.
• FFFF в collating-symbol <SFFFF> выглядит как большое беззнаковое целое в шестнадцатеричной системе счисления, но <SFFFF> это просто имя, которое могло бы выглядеть как <VERYBIGVAL>
• имя <U0413> означает кодовую точку в кодировке UCS-4
• collating-element <U0413_0301> from "<U0413><U0301>" регистрирует новое имя для пары юникодовских точек.

Когда имена весов определены, задаются собственно веса. Поскольку при сравнении имеет значение только отношения больше-меньше, то веса определяются простой последовательностью перечисления имён. Сначала перечисляются более "лёгкие" веса, затем более "тяжёлые". Напомню, что каждому юникодовскому символу присваивается четыре разных веса. Здесь они сведены в единую упорядоченную последовательность. Теоретически, любое символическое имя может использоваться на любом из четырех уровней, но комментарии указывают на то, что разработчики мысленно разделяют имена по уровням.

% 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

Наконец, собственно таблица весов.

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

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

• символы, которые игнорируются полностью
• символы эквивалентные цифре три на первых двух уровнях
• начало кириллического алфавита, который не содержит диакритических знаков, а потому сортируется, в основном, по первому и третьему уровням.

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

Теперь можно снова вернуться к сортировке примеров из начала статьи. Засада кроется вот в этой части таблицы весов:

<U0020> IGNORE;IGNORE;IGNORE;<U0020> % SPACE
<U0021> IGNORE;IGNORE;IGNORE;<U0021> % EXCLAMATION MARK
<U0022> IGNORE;IGNORE;IGNORE;<U0022> % 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'\xfe', 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
% 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

На самом деле, надо было бы поменять поля в 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, который использует свои внутренние функции для сортировки имён, выносит файлы, начинающиеся с точки, в начало списка.

Ссылки

Отчёт №10 Unicode collation algorithm

Веса символов на unicode.org

ICU — реализация библиотеки для работы с Unicode от IBM.

Тест сортировки с помощью ICU

Веса символов в ISO 14651

Описание формата файла с весами ISO 14652

Обсуждение сравнения строк в glibc