Увядзенне

Усё пачалося з кароткага скрыпту, які павінен быў аб'яднаць інфармацыю аб адрасах. Электронная пошта супрацоўнікаў, атрыманых са спісу карыстальнікаў паштовага рассылання, з пасадамі супрацоўнікаў, атрыманымі з базы аддзела кадраў. Абодва спісы былі экспартаваныя ў тэкставыя файлы ў кадоўцы Юнікод 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".

Адказ усюды стандартны: выкарыстоўвайце праграмісцкую лакаль "С" і будзе вам шчасце. Спрабуем:

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

Вынік сартавання, як ні дзіўна, супадзе з лакаллю "С", і ўвесь прыклад, адпаведна, праходзіць без памылак. Містыка нейкая.

Я не люблю містыку ў праграмаванні, паколькі, як правіла, яна маскіруе памылкі. Прыйдзецца сур'ёзна заняцца пытаннем як працуе сартаваць і на што ўплывае LC_COLLATE .

У канцы я паспрабую адказаць на пытанні:

чаму няправільна сартаваліся жаночыя прозвішчы
чаму LANG=ru_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);
розныя радкі, якія маюць аднолькавыя вагі, лічацца роўнымі з пункту гледжання алгарытму сартавання. Увядзенне дадатковага ўпарадкавання такіх радкоў магчыма, але яно можа пагоршыць прадукцыйнасць;
пры паўторных сартаваннях радка, якія маюць аднолькавыя вагі, могуць мяняцца месцамі. Устойлівасць - гэта ўласцівасць канкрэтнага алгарытму сартавання, а не ўласцівасць алгарытму параўнання радкоў (гл. папярэдні пункт);
правілы сартавання могуць мяняцца з часам па меры ўдакладнення/змены культурных традыцый.

Гэтак жа абумоўлена, што алгарытм параўнання нічога не ведае пра семантыку апрацоўваных радкоў. Так, радкі якія складаюцца толькі з лічбаў не павінны параўноўвацца як лікі, а ў спісах ангельскіх найменняў не павінен прыбірацца артыкль (Бітлз, The).

Для таго, каб задаволіць усім названым патрабаванням прапанаваны шматузроўневы (фактычна чатырохузроўневы) таблічны алгарытм сартавання.

Папярэдне, знакі ў радку прыводзяцца да кананічнага выгляду і групуюцца ў адзінкі параўнання. Кожнай адзінцы параўнання прысвойваюцца некалькі вагаў, якія адпавядаюць некалькім узроўням параўнання. Вагі адзінак параўнання гэта элементы спарадкаваных мностваў (у дадзеным выпадку цэлыя лікі), якія можна параўноўваць на больш-менш. Спецыяльнае значэнне ІГНАРАВАЦЬ (0x0) азначае, што на адпаведным узроўні параўнання дадзеная адзінка ў параўнанні не ўдзельнічае. Параўнанне радкоў можа паўтарацца некалькі разоў, з выкарыстаннем вагаў адпаведных узроўняў. На кожным з узроўняў вагі адзінак параўнання двух радкоў паслядоўна параўноўваюцца паміж сабой.

У розных рэалізацыях алгарытму для розных нацыянальных традыцый велічыні каэфіцыентаў могуць адрознівацца, але ў склад стандарту Юнікод ўваходзіць базавая табліца вагаў "Default Unicode Collation Element Table" (DUCET). Жадаю заўважыць, што ўсталёўка зменнай LC_COLLATE фактычна з'яўляецца ўказаннем на выбар табліцы шаляў у функцыі параўнання радкоў.

Вагавыя каэфіцыенты DUCET уладкованыя наступным чынам:

на першым узроўні ўсе літары прыводзяцца да аднаго рэгістра, дыякрытычныя знакі адкідаюцца, знакі прыпынку (не ўсе) ігнаруюцца;
на другім узроўні ўлічваюцца толькі дыякрытычныя знакі;
на трэцім узроўні ўлічваецца толькі рэгістр;
на чацвёртым узроўні ўлічваюцца толькі знакі прыпынку.

Параўнанне адбываецца ў некалькі праходаў: спачатку параўноўваюцца каэфіцыенты першага ўзроўня; калі вагі супалі, тое праходзіць паўторнае параўнанне з вагамі другога ўзроўня; затым, магчыма, трэцяга і чацвёртага.

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

Вось гэты алгарытм (з кучай дадатковых тэхнічных дэталяў) і даў назву справаздачы № 10 — "Unicode Collation Algorithm" (УЦА).

У гэтым месцы паводзіны сартавання з нашага прыкладу становіцца крыху больш зразумелым. Добра было б яго параўнаць са стандартам Юнікод.

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

Ручная праверка правільнасці сартавання радкоў у адпаведнасці з DUCET была б даволі стомнай, але, на шчасце для нас, існуе ўзорна-паказальная рэалізацыя бібліятэкі для працы з Юнікодам.International Components for 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 год ішла адаптацыя да новай версіі табліцы і ў сапраўдны момант у вас ёсць шанец сустрэць у рэальным жыцці як новы варыянт табліцы (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 %

У файле будуць сустракацца токены ў фармаце або (дзе x - шаснаццатковая лічба). Гэта шаснаццатковае прадстаўленне кодавых кропак Юнікод ў кадоўцы UCS-4 (UTF-32). Усе астатнія элементы ў кутніх дужках (у тым ліку , і ім падобныя), лічацца простымі радковымі канстантамі, якія не маюць асаблівага сэнсу па-за кантэкстам.

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

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

% 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_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

Калі ўсталяваць зменную Ланг = 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. Як жа атрымалася, што далучыцца выдавала памылку сартавання на радках, адсартаваных камандай сартаваць у лакалі en_US.UTF-8? Адказ просты: сартаваць параўноўвае радок цалкам, а далучыцца параўноўвае толькі ключ, якім па змаўчанні, з'яўляецца пачатак радка да першага прабельнага знака. У маім прыкладзе гэта прывяло да паведамлення аб памылцы паколькі сартаванне першых слоў у радках не супала з сартаваннем поўных радкоў.

Лакаль "С" гарантуе, што ў адсартаваных радках пачатковыя падрадкі да першага прабелу таксама апынуцца адсартаваны, але гэта толькі маскіруе памылку. Можна падабраць такія дадзеныя (людзі з аднолькавымі прозвішчамі, але рознымі імёнамі), якія без паведамлення аб памылцы далечы б няправільны вынік зліцця файлаў. Калі мы хочам, каб далучыцца аб'ядноўваў радкі файлаў па ПІБ, то правільным спосабам будзе відавочнае ўказанне падзельніка палёў і сартаванне па ключавым полі, а не па ўсім радку. У гэтым выпадку і зліццё пройдзе правільна і ні ў якой лакалі не будзе памылак:

$> 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. Калі скампіляваная лакаль не знойдзена, то сартаваць моўчкі выкарыстоўвае пабайтавае параўнанне, што мы і назіралі.

Дарэчы, ёсць яшчэ адзін маленькі глюк злучаны з недаступнасцю скампіляваных лакаляў. Каманда 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.

Калі вы лінгвіст ці складальнік слоўнікаў, то вам лепш скампіляваць сваю лакаль.

Калі вы просты карыстальнік, то вам дастаткова прывыкнуць да таго, што каманда Ls -a выдае файлы, якія пачынаюцца з кропкі, уперамешку з файламі, якія пачынаюцца з літары, а Midnight Commander, які выкарыстоўвае свае ўнутраныя функцыі для сартавання імёнаў, выносіць файлы, якія пачынаюцца з кропкі, у пачатак спісу.