Запровадження

Все почалося з короткого скрипту, який мав поєднати інформацію про адреси електронна пошта співробітників, одержаних зі списку користувачів поштового розсилання, з посадами співробітників, одержаними з бази відділу кадрів. Обидва списки були експортовані до текстових файлів у кодуванні Юнікод UTF-8 та збережені з юніксівськими кінцями рядків.

вміст mail.txt

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

вміст buhg.txt

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

Для об'єднання файли були відсортовані юніксівською командою сортувати та подані на вхід юніксівській програмі приєднатися, яка несподівано завершилася з помилкою:

$> 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
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

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

Відкладемо поки приєднатися і зосередимося на сортувати. Спробуємо вирішити задачу методом наукового тику. Для початку, поміняємо локаль з 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. Якщо коротко, то рядки "ab", "aa", "ac" сортуються як "aa", "ab", "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"і весь приклад, відповідно, проходить без помилок. Містика якась.

Я не люблю містику в програмуванні, оскільки зазвичай вона маскує помилки. Прийде всерйоз зайнятися питанням, як працює сортувати і на що впливає LC_COLLATE .

Наприкінці я спробую відповісти на запитання:

чому неправильно сортувалися жіночі прізвища
чому LANG=ua_RU.CP1251 виявився еквівалентом LANG=C
чому у сортувати и приєднатися різні уявлення про порядок відсортованих рядків
чому у всіх моїх прикладах є помилки
нарешті, як сортувати рядки на свій смак

Сортування в Юнікоді

Першою зупинкою буде технічний звіт № 10 під назвою Unicode collation algorithm на сайті unicode.org. Звіт містить багато технічних деталей, тому я дозволю собі навести короткий виклад основних ідей.

Зіставлення - "Порівняння" рядків - основа будь-якого алгоритму сортування. Самі алгоритми можуть відрізнятися ("бульбашкою", "злиттям", "швидкий"), але всі вони будуть використовувати порівняння пари рядків, для визначення порядку їх прямування.

Сортування рядків природною мовою — це досить складна проблема. Навіть у найпростіших однобайтових кодуваннях порядок літер в алфавіті, що хоч у чомусь відрізняється від англійської латиниці, вже не співпадатиме з порядком числових значень, якими ці літери кодуються. Так у німецькому алфавіті буква Ö стоїть між О и P, а в кодуванні CP850 вона потрапляє між ÿ и Ü.

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

Виявляється, що навіть побудувавши таблицю символів з нуля, ми зможемо призначити у ній універсальний порядок символів. У різних національних алфавітах, які використовують однакові літери, порядок цих літер може відрізнятись. Наприклад, у французькій мові Æ вважатиметься лігатурою і сортуватиметься як рядок AE. У норвезькій мові Æ буде окремою літерою, яка розташовується після Z. До речі, крім лігатур типу Æ існують літери, які записуються кількома символами. Так у чеському алфавіті є буква Ch, яка стоїть між H и I.

Крім відмінності в алфавітах існують інші національні традиції, що впливають на сортування. Зокрема виникає питання: в якому порядку повинні слідувати у словнику слова, що складаються з великих і малих літер? Також на сортування можуть вплинути особливості використання розділових знаків. В іспанській мові на початку запитання ставиться перевернутий знак питання (Ви любите музику?). У цьому випадку очевидно, що запитальні пропозиції не повинні групуватися в окремий кластер поза алфавітом, а як сортувати рядки з іншими розділовими знаками?

Я не зупинятимуся на сортуванні рядків у мовах, що сильно відрізняються від європейських. Зазначу, що в мовах з направленням листа праворуч наліво або зверху вниз символи в рядках, швидше за все, зберігаються в порядку читання, і навіть у неалфавітних писемностях є свої способи посимвольного впорядкування рядків. Наприклад, ієрогліфи можуть упорядковуватися за накресленням (ключі китайських ієрогліфів) або за вимовою. Як повинні впорядковуватися емодзи, я, чесно кажучи, не уявляю, але й для них можна щось вигадати.

На основі перерахованих вище особливостей були сформульовані основні вимоги до порівняння рядків, що ґрунтуються на таблицях Юнікоду:

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

Крім того, автори звіту сформулювали властивості порівняння, на які розробники алгоритму не повинні покладатися:

алгоритм порівняння не повинен вимагати окремого набору символів для кожної мови (російська та українська мови спільно використовують більшість символів кирилиці);
порівняння має спиратися на порядок символів у таблицях Юнікоду;
вага рядка не повинна бути атрибутом рядка, оскільки один і той самий рядок у різних культурних контекстах може мати різні ваги;
ваги рядків можуть змінюватися при злитті або розбиття (з x < y не слід, що xz < yz);
різні рядки, що мають однакові ваги, вважаються рівними з погляду алгоритму сортування. Введення додаткового впорядкування таких рядків можливе, але воно може погіршити продуктивність;
при повторних сортуваннях рядки, що мають однакові ваги, можуть змінюватись місцями. Стійкість — це властивість конкретного алгоритму сортування, а чи не властивість алгоритму порівняння рядків (див. попередній пункт);
правила сортування можуть змінюватися з часом у міру уточнення/зміни культурних традицій.

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

Для того, щоб задовольнити всім зазначеним вимогам, запропоновано багаторівневий (фактично чотирирівневий) табличний алгоритм сортування.

Попередньо символи в рядку наводяться до канонічного вигляду і групуються в одиниці порівняння. Кожній одиниці порівняння присвоюються кілька терезів, що відповідають декільком рівням порівняння. Вага одиниць порівняння це елементи впорядкованих множин (у разі цілі числа), які можна порівнювати більш-менш. Спеціальне значення ігноровано (0x0) означає, що на відповідному рівні порівняння ця одиниця у порівнянні не бере участі. Порівняння рядків може повторюватися кілька разів, з використанням ваги відповідних рівнів. На кожному рівні ваги одиниць порівняння двох рядків послідовно порівнюються між собою.

У різних реалізаціях алгоритму для різних національних традицій величини коефіцієнтів можуть відрізнятися, але до складу стандарту Юнікоду входить базова таблиця ваг "Default Unicode Collation Element Table" (DUCET). Хочу зауважити, що встановлення змінної LC_COLLATE фактично є вказівкою на вибір таблиці ваг у функції порівняння рядків.

Вагові коефіцієнти DUCET влаштовані наступним чином:

на першому рівні всі літери наводяться до одного регістру, діакритичні знаки відкидаються, розділові знаки (не всі) ігноруються;
на другому рівні враховуються лише діакритичні знаки;
на третьому рівні враховується лише регістр;
на четвертому рівні враховуються лише розділові знаки.

Порівняння відбувається у кілька проходів: спочатку порівнюються коефіцієнти першого рівня; якщо ваги збіглися, проходить повторне порівняння з вагами другого рівня; потім, можливо, третього та четвертого.

Порівняння закінчується, коли в рядках знаходяться одиниці одиниці порівняння з різними вагами. Рядки, що мають рівні ваги на всіх чотирьох рівнях, вважаються рівними між собою.

Ось цей алгоритм (з купою додаткових технічних деталей) і дав назву звіту № 10 "Unicode Collation Algorithm" (УЦА).

У цьому місці поведінка сортування з нашого прикладу стає дещо зрозумілішою. Добре було б його порівняти зі стандартом Юнікоду.

Для тестування реалізацій УЦА існує спеціальний тест, що використовує файл ваг, що реалізує DUCET. У файлі терезів можна знайти різні забавності. Наприклад, там є порядок кістяків маджонга та європейського доміно, а також порядок мастей у колоді карт (символ 1F000 і далі). Карткові масті розміщені за правилами бриджу - ПЧБТ, а карти в масті - у послідовності Т, 2,3, XNUMX ... До.

Ручна перевірка правильності сортування рядків відповідно до DUCET була б досить стомлюючою, але, на щастя для нас, існує зразково-показова реалізація бібліотеки для роботи з Юнікодом -Міжнародні компоненти для Unicode"(СІС).

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

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

До речі, на сайті СІС можна знайти уточнення роботи алгоритму порівняння при обробці розділових знаків. У прикладах Collation FAQ ігноруються апостроф та дефіс.

Юнікод нам допоміг, але шукати причини дивної поведінки сортувати в Linux доведеться десь ще.

Сортування у glibc

Швидкий перегляд вихідних кодів утиліти сортувати з GNU Core Utils показав, що у самій утиліті локалізація зводиться до друку поточного значення змінної LC_COLLATE при запуску в режимі налагодження:

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

Порівняння рядків виконується стандартною функцією strcoll, а значить все цікаве знаходиться у бібліотеці glibc.

На вики проекту glibc порівняння рядків присвячений один абзац. З цього абзацу можна зрозуміти, що в glibc сортування базується на вже відомому нам алгоритмі УЦА (The Unicode collation algorithm) та/або на близькому до нього стандарті ISO 14651 (International string ordering and comparison). Щодо останнього стандарту слід зазначити, що на сайті standards.iso.org ISO 14651 офіційно оголошено загальнодоступним, але відповідне посилання веде до неіснуючої сторінки. Google видає кілька сторінок із посиланнями на офіційні сайти, які пропонують купити електронну копію стандарту за сотню євро, але на третій-четвертій сторінці пошукової видачі знайдуться і прямі посилання на PDF. В цілому, стандарт практично не відрізняється від УЦА, але читається нудніше, оскільки містить яскравих прикладів національних особливостей сортування рядків.

Найцікавішою інформацією на вики виявилося посилання на багтрекер з обговоренням реалізації порівняння рядків у glibc. З обговорення можна дізнатися, що в glibc для порівняння рядків використовується ISOшна таблиця The Common Template Table (CTT), адресу якої можна знайти у додатку A стандарту ISO 14651. Між 2000 та 2015 роками ця таблиця в glibc не мала мейнтейнера і досить сильно відрізнялася (принаймні зовні) від поточної версії стандарту. З 2015 до 2018 року йшла адаптація до нової версії таблиці і зараз у вас є шанс зустріти в реальному житті як новий варіант таблиці (8 CentOS), так і старий (7 CentOS).

Тепер, коли вся інформація про алгоритм і допоміжні таблиці у нас є, можна повернутися до вихідної проблеми і зрозуміти, як правильно сортувати рядки в російській локалі.

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 %

У файлі будуть зустрічатися токени у форматі або (де x - Шістнадцяткова цифра). Це шістнадцяткове представлення кодових точок Юнікоду в кодуванні UCS-4 (UTF-32). Всі інші елементи у кутових дужках (у тому числі , <2> і їм подібні), вважаються простими строковими константами, які не мають особливого сенсу поза контекстом.

Рядок LC_COLLATE каже нам, що далі починаються дані, що описують порівняння рядків.

Спочатку задаються імена для ваг у таблиці порівняння та імена для комбінацій символів. Взагалі кажучи, два типи імен належать двом різним сутностям, але реальному файлі вони перемішані. Імена ваг задаються ключовим словом зіставлення-символ (Символ порівняння), оскільки при порівнянні символи Юнікоду, що мають однакові ваги, будуть вважатися еквівалентними символами.

Загальна довжина секції поточної ревізії файлу близько 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 у таблиці імен ваг
collating-symbol .. реєструє послідовність імен, що складаються з префіксу S і шістнадцяткового числового суфікса від 1D000 до 1D35F.
FFFF в collating-symbol виглядає як велике беззнакове ціле в шістнадцятковій системі числення, але це просто ім'я, яке могло б виглядати як
ім'я означає кодову точку в кодуванні UCS-4
collating-element від " " реєструє нове ім'я для пари юнікодівських точок.

Коли імена ваги визначені, задаються власне ваги. Оскільки при порівнянні має значення тільки відношення більш-менше, то ваги визначаються простою послідовністю перерахування імен. Спочатку перераховуються більш "легкі" ваги, потім "важчі". Нагадаю, що кожному юнікодівському символу присвоюється чотири різні ваги. Тут вони зведені в єдину впорядковану послідовність. Теоретично будь-яке символічне ім'я може використовуватися на будь-якому з чотирьох рівнів, але коментарі вказують на те, що розробники подумки поділяють імена за рівнями.

% 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 визначають, у якому напрямі проглядаються рядки кожному рівні сравнения. За промовчанням використовується параметр вперед. Тіло секції складається з рядків, які містять код символу та чотири його ваги. Код символу може бути представлений самим символом, кодовою точкою або символічним ім'ям, визначеним раніше. Ваги також можуть задаватися символічними іменами, кодовими точками або символами. Якщо використовуються кодові точки або символи, їх вага збігається числовим значенням кодової точки (позицією в таблиці Юнікоду). Символи не зазначені явно (як я розумію) вважаються приписаними до таблиці з первинною вагою, яка збігається з позицією у таблиці Юнікоду. Спеціальне значення ваги ІГНОРУВАТИ означає, що у відповідному рівні порівняння цей символ ігнорується.

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

символи, які ігноруються повністю
символи еквівалентні цифри три на перших двох рівнях
початок кириличного алфавіту, який не містить діакритичних знаків, а тому сортується, в основному, за першим та третім рівнями.

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 (включаючи пропуск) при порівнянні рядків практично завжди ігнорується. Виняток становлять лише рядки, що збігаються у всьому, крім розділових знаків, що зустрічаються в збігаються позиціях. Рядки з мого прикладу (після сортування) для алгоритму порівняння виглядають так:

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

Враховуючи, що в таблиці терезів великі літери в російській мові йдуть після малих (на третьому рівні важче ніж ), сортування виглядає абсолютно правильним.

При встановленні змінної 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_UA.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/ua_UA з використанням файлу кодування /usr/share/i18n/charmaps/MAC-CYRILLIC.gz і збереже результат у /usr/lib/locale/locale-archive під ім'ям ru_UA.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/

Якщо локаль зустрічається і в традиційному, і в сучасному форматах, то пріоритет надається сучасному.

Переглянути список скомпілованих локалів можна командою локаль -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 припускає, що в МОВА можна писати абсолютні шляхи до каталогів з файлами локалей, що починаються з прямого слеша, але glibc в Linux всі шляхи вважає від базового каталогу, який можна перевизначити через змінну LOCPATH. Після встановлення LOCPATH=~/.local/lib/locale/ всі файли, пов'язані з локалізацією, будуть шукатися тільки в моїй папці. Архів локалей при встановленій змінній LOCPATH ігнорується.

Ось він вирішальний тест:

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

Ура! Ми зробили це!

Робота над помилками

Я вже відповів на питання про сортування рядків, поставлені на початку, але ще залишилося кілька запитань про помилки — видимі й невидимі.

Повернемося до вихідного завдання.

І програма сортувати і програма приєднатися використовують одні й самі функції порівняння рядків з glibc. Як же вийшло, що приєднатися видавала помилку сортування на рядках, відсортованих командою сортувати у локалі uk_US.UTF-8? Відповідь проста: сортувати порівнює рядок повністю, а приєднатися порівнює тільки ключ, яким за замовчуванням є початок рядка до першого пробілового символу. У моєму прикладі це призвело до повідомлення про помилку, оскільки сортування перших слів у рядках не збіглося з сортуванням повних рядків.

Локаль "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_UA.CP1251. Якщо скомпільовану локаль не знайдено, то сортувати мовчки використовує побайтове порівняння, що ми й спостерігали.

До речі, є ще один маленький глюк, пов'язаний з недоступністю скомпілованих локалей. Команда LOCPATH=/tmp locale -a видасть список усіх локалів у locale-archive, але при встановленій змінній LOCPATH для всіх програм (у тому числі і для самої місце дії) ці локалі будуть недоступні.

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

Якщо ви лінгвіст чи укладач словників, то вам краще скомпілювати свою локаль.

Якщо ви звичайний юзер, то вам досить звикнути до того, що команда лс-а видає файли, що починаються з точки, упереміш з файлами, що починаються з літери, а Midnight Commander, який використовує свої внутрішні функції для сортування імен, виносить файли, що починаються з точки на початок списку.