Wprowadzenie

Wszystko zaczęło się od krótkiego skryptu, który miał połączyć informacje o adresach e-mail pracowników, pozyskanych z listy użytkowników poczty masowej, z stanowiskami pracowników, uzyskanymi z bazy działu kadr. Obie listy zostały wyeksportowane do plików tekstowych w kodowaniu Unicode UTF-8 i zapisane z końcami linii w stylu uniksowym.

Zawartość mail.txt

Iwanow Andriej;ia@example.com

Zawartość buhg.txt

Iwanowa Alla;malarz
Jołkina Ella;dźwigowy
Iwanow Andriej;ślusarz
Abakanow Michaił;malarz

Aby je połączyć, pliki zostały posortowane za pomocą uniksowego polecenia sort i podane jako wejście do programu uniksowego join, który niespodziewanie zakończył się błędem:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: nie jest posortowane: Iwanow Andriej;ślusarz

Przeglądając wynik sortowania gołym okiem, można zauważyć, że sortowanie jest ogólnie poprawne, ale w przypadku pokrywających się nazwisk męskich i żeńskich, żeńskie są przed męskimi:

$> sort buhg.txt
Abakanow Michaił;malarz
Jołkina Ella;dźwigowy
Iwanowa Alla;malarz
Iwanow Andriej;ślusarz

Wygląda to jak błąd sortowania w Unicode lub jak przejaw feminizmu w algorytmie sortującym. Pierwsze jest, oczywiście, bardziej prawdopodobne.

Odstawmy to na razie join i skupmy się na sort. Spróbujemy rozwiązać problem metodą prób i błędów. Na początek zmienimy lokalizację na en_US na ru_RU. Do sortowania wystarczyłoby ustawić zmienną środowiskową LC_COLLATE, ale nie będziemy się drobiazgowo ograniczać:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanow Michaił;malarz
Jołkina Ella;dźwigowy
Iwanowa Alla;malarz
Iwanow Andriej;ślusarz

Nic się nie zmieniło.

Spróbujemy przekonwertować pliki na jednobajtowe kodowanie:

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

Znów nic się nie zmienia.

Trudno, będziemy musieli poszukać rozwiązania w internecie. Bezpośrednio o rosyjskich nazwiskach nic nie ma, ale są pytania o inne dziwne przypadki sortowania. Oto na przykład taki problem: unix sort treats ‘-‘ (dash) characters as invisible. Krótko mówiąc, ciągi "a-b", "aa", "ac" są sortowane jako "aa", "a-b", "ac".

Odpowiedź wszędzie jest standardowa: użyj lokalizacji programistycznej "C" i będziesz szczęśliwy. Spróbujmy:

$> LANG=C sort buhg.txt
Jołkina Ella;dźwigowy
Abakanow Michaił;malarz
Iwanow Andriej;ślusarz
Iwanowa Alla;adwokat

Coś się zmieniło. Iwanowowie ustawili się w poprawnej kolejności, chociaż Jołkina gdzieś zniknęła. Wracamy do pierwotnego zadania:

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

Zadziałało bez błędów, tak jak obiecał Internet. I to mimo obecności 'Ёлki' w pierwszym wierszu.

Problem wydaje się rozwiązany, ale na wszelki wypadek spróbujemy jeszcze jedną rosyjską kodowanie — windowsowe. CP1251:

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

Wynik sortowania, co dziwne, będzie zgodny z lokalizacją. "C", i cały przykład, odpowiednio, przechodzi bez błędów. To jakaś mistyka.

Nie lubię mistyki w programowaniu, ponieważ zwykle maskuje ona błędy. Będę musiał na poważnie zająć się kwestią, jak to działa sort i na co wpływa LC_COLLATE .

Na koniec postaram się odpowiedzieć na pytania:

dlaczego błędnie sortowały się żeńskie nazwiska
dlaczego LANG=ru_RU.CP1251 okazał się równoważny LANG=C
dlaczego mają sort i join różne reprezentacje porządku posortowanych wierszy
dlaczego we wszystkich moich przykładach są błędy
na końcu, jak sortować wiersze według własnego gustu

Sortowanie w Unicode

Pierwszym przystankiem będzie raport techniczny nr 10 pod tytułem Unicode collation algorithm na stronie unicode.org. Raport zawiera wiele szczegółów technicznych, więc pozwolę sobie na krótkie streszczenie głównych idei.

Collation — „porównanie” wierszy — to podstawa każdego algorytmu sortowania. Same algorytmy mogą się różnić (np. „bąbelkowy”, „łańcuchowy”, „szybki”), ale wszystkie będą używać porównania pary wierszy, aby określić ich kolejność.

Sortowanie wierszy w naturalnym języku to dość trudny problem. Nawet w najprostszym kodowaniu jednowymiarowym kolejność liter w alfabecie, różniąca się od angielskiego, nie będzie odpowiadać kolejności wartości numerycznych, którymi te litery są kodowane. Tak w niemieckim alfabecie litera Ö znajduje się pomiędzy o i P, a w kodowaniu CP850 ona wpada pomiędzy ÿ i Ü.

Można spróbować abstrahować od konkretnego kodowania i rozważyć „idealne” litery, które są usytuowane w pewnym porządku, jak w Unicode. Kodowania UTF8, UTF16 lub jednowymiarowe KOI8-R (jeśli potrzebne jest ograniczone podzbiór Unicode) będą miały różne numeryczne przedstawienia liter, ale będą odnosić się do tych samych elementów podstawowej tabeli.

Okazuje się, że nawet budując tabelę znaków od podstaw, nie będziemy w stanie ustalić uniwersalnego porządku znaków. W różnych krajowych alfabetach, które używają tych samych liter, kolejność tych liter może się różnić. Na przykład w języku francuskim Æ będzie uważana za ligaturę i sortowana jak ciąg AE. W języku norweskim Æ będzie oddzielną literą, która znajduje się po Z. Swoją drogą, oprócz ligatur typu Æ istnieją litery, które są zapisywane za pomocą kilku znaków. Tak w alfabecie czeskim znajduje się litera Ch, która stoi pomiędzy H i I.

. Oprócz różnic w alfabetach istnieją także inne narodowe tradycje, które wpływają na sortowanie. W szczególności pojawia się pytanie: w jakiej kolejności w słowniku powinny występować słowa z dużych i małych liter? Ważnym aspektem mogą być także zasady użycia znaków przestankowych. W języku hiszpańskim na początku zdania pytającego stawia się odwrócony znak zapytania (¿Te gusta la música?). W tym przypadku oczywiste jest, że zdania pytające nie powinny być grupowane w oddzielny klaster poza alfabetem, a jak należy sortować ciągi z innymi znakami przestankowymi?

Nie będę się zatrzymywał na sortowaniu ciągów w językach znacznie różniących się od europejskich. Zaznaczam, że w językach z kierunkiem pisania od prawej do lewej lub z góry na dół znaki w ciągach są prawdopodobnie przechowywane w kolejności czytania, a nawet w piśmiennictwach niealfabetowych istnieją sposoby porządkowania znaków. Na przykład, hieroglify mogą być porządkowane według kształtu (klucze chińskich hieroglifów) lub według wymowy. Jak należy porządkować emoji, szczerze mówiąc, nie mam pojęcia, ale także dla nich można coś wymyślić.

Na podstawie wyżej wymienionych cech sformułowano podstawowe wymagania dotyczące porównywania ciągów opartych na tabelach Unicode:

porównanie ciągów nie zależy od pozycji symboli w tabeli kodów;
sekwencje symboli, tworzące jeden symbol, są sprowadzane do postaci kanonicznej (A + górne kółko to to samo, co Å);
podczas porównywania ciągów symbol jest rozpatrywany w kontekście ciągu i, w razie potrzeby, łączony z sąsiadami w jedną jednostkę porównawczą (Ch w czeskim) lub dzielony na kilka (Æ w francuskim);
wszystkie cechy narodowe (alfabet, wielkie/małe litery, znaki interpunkcyjne, porządek rodzajów pisma) powinny być konfigurowane aż do ręcznego ustawienia porządku (emoji);
porównanie jest ważne nie tylko dla sortowania, ale także w wielu innych miejscach, na przykład do określenia zakresów wierszy (substytucja {A… я} w bash);
porównanie powinno być wystarczająco szybkie.

Ponadto autorzy raportu sformułowali cechy porównania, na które deweloperzy algorytmów nie powinni polegać:

algorytm porównania nie powinien wymagać oddzielnego zestawu znaków dla każdego języka (języki rosyjski i ukraiński wspólnie używają większości znaków cyrylickich);
porównanie nie powinno opierać się na porządku znaków w tabelach Unicode;
waga ciągu nie powinna być atrybutem ciągu, ponieważ ten sam ciąg w różnych kontekstach kulturowych może mieć różne wagi;
wagi ciągów mogą się zmieniać podczas scalania lub rozdzielania (z x < y nie oznacza, że xz < yz);
różne ciągi, które mają te same wagi, są uważane za równe z punktu widzenia algorytmu sortowania. Wprowadzenie dodatkowego porządku takich ciągów jest możliwe, ale może pogorszyć wydajność;
podczas kolejnych sortowań ciągi, które mają te same wagi, mogą zmieniać miejsca. Stabilność to cecha konkretnego algorytmu sortowania, a nie cecha algorytmu porównania ciągów (zob. poprzedni punkt);
zasady sortowania mogą się zmieniać z czasem w miarę precyzowania/zmiany tradycji kulturowych.

Również zaznaczone, że algorytm porównania nic nie wie o semantyce przetwarzanych ciągów. Tak więc ciągi składające się wyłącznie z cyfr nie powinny być porównywane jako liczby, a w listach angielskich nazw nie powinno być usuwane artykuł (Beatles, The).

Aby spełnić wszystkie wymienione wymagania, zaproponowano wielopoziomowy (w rzeczywistości czteropoziomowy) algorytm tablicowy do sortowania.

Najpierw znaki w ciągu są przekształcane do formy kanonicznej i grupowane w jednostki porównawcze. Każdej jednostce porównawczej przypisuje się kilka wag odpowiadających kilku poziomom porównania. Wagi jednostek porównawczych to elementy uporządkowanych zbiorów (w tym przypadku liczby całkowite), które można porównywać w odniesieniu do większych/mniejszych. Specjalna wartość IGNORED (0x0) oznacza, że na danym poziomie porównania, ta jednostka nie bierze udziału w porównaniu. Porównanie ciągów może powtarzać się kilka razy, z wykorzystaniem wag odpowiednich poziomów. Na każdym z poziomów wagi jednostek porównania dwóch ciągów są kolejno porównywane ze sobą.

W różnych realizacjach algorytmu dla różnych krajowych tradycji wartości współczynników mogą się różnić, ale w skład standardu Unicode wchodzi podstawowa tabela wag — "Domyślna tabela elementów porównania Unicode" (DUCET). Chcę zauważyć, że ustawienie zmiennej LC_COLLATE faktycznie polega na wskazaniu tabeli wag w funkcji porównania ciągów.

Współczynniki wag DUCET są zorganizowane w następujący sposób:

na pierwszym poziomie wszystkie litery są sprowadzane do jednego rejestru, znaki diakrytyczne są odrzucane, znaki interpunkcyjne (nie wszystkie) są ignorowane;
na drugim poziomie uwzględniane są tylko znaki diakrytyczne;
na trzecim poziomie uwzględniany jest tylko rejestr;
na czwartym poziomie uwzględniane są tylko znaki interpunkcyjne.

Porównanie odbywa się w kilku przebiegach: najpierw porównywane są współczynniki pierwszego poziomu; jeśli wagi się zgadzają, przeprowadza się ponowne porównanie z wagami drugiego poziomu; następnie, być może, trzeciego i czwartego.

Porównanie kończy się, gdy w ciągach znajdują się odpowiadające sobie jednostki porównania o różnych wagach. Ciągi, które mają równe wagi na wszystkich czterech poziomach, są uważane za równe sobie.

To właśnie ten algorytm (z mnóstwem dodatkowych szczegółów technicznych) nadał nazwę raportowi nr 10 — "Algorytm porównania Unicode" (UCA).

W tym miejscu zachowanie sortowania z naszego przykładu staje się nieco bardziej zrozumiałe. Dobrze byłoby je porównać ze standardem Unicode.

Do testowania realizacji UCA istnieje specjalny test, wykorzystujący plik wag, wdrażający DUCET. W pliku wag można znaleźć różne ciekawostki. Na przykład, tam jest kolejność kości mahjonga i europejskiego domino, a także kolejność kolorów w talii kart (symbol 1F000 i dalej). Kolory kart są uporządkowane według zasad bridża — PCHBT, a karty w kolorze — w kolejności T, 2, 3… K.

Ręczne sprawdzenie poprawności sortowania ciągów zgodnie z DUCET byłaby dość męcząca, ale na szczęście dla nas istnieje wzorcowa implementacja biblioteki do pracy z Unicode — "International Components for Unicode" (ICU).

Na stronie tej biblioteki, opracowanej w IBM, są dostępne strony demonstracyjne, w tym strona algorytmu porównywania ciągów. Wprowadzamy nasze testowe ciągi z ustawieniami domyślnymi i, o cudzie, otrzymujemy idealne rosyjskie sortowanie.

Abakanow Michał;malarz
Jołkina Ella;operator żurawia
Iwanow Andriej;ślusarz
Iwanowa Alla;adwokat

Przy okazji, na stronie ICU można znaleźć szczegółowe informacje dotyczące działania algorytmu porównywania przy przetwarzaniu znaków interpunkcyjnych. W przykładach Collation FAQ ignorowane są apostrof i myślnik.

Unicode nam pomógł, ale przyczyny dziwnego zachowania sort do Linuxa trzeba będzie szukać gdzie indziej.

Sortowanie w glibc

Szybki przegląd kodu źródłowego narzędzia sort z GNU Core Utils pokazał, że w samym narzędziu lokalizacja sprowadza się do wyświetlania aktualnej wartości zmiennej LC_COLLATE przy uruchomieniu w trybie debugowania:

$ sort --debug buhg.txt > buhg.srt
sort: używa reguł sortowania ‘en_US.UTF8’

Porównanie ciągów odbywa się za pomocą standardowej funkcji strcoll, a więc wszystko interesujące znajduje się w bibliotece glibc.

Na wiki projektu glibc poświęcony porównywaniu ciągów jeden akapit. Z tego akapitu można zrozumieć, że w glibc sortowanie opiera się na nam już znanym algorytmie UCA (The Unicode collation algorithm) i/lub na zbliżonym standardzie ISO 14651 (Międzynarodowe porządkowanie i porównywanie ciągów). Co do ostatniego standardu, należy zauważyć, że na stronie standards.iso.org ISO 14651 oficjalnie ogłoszonej jako publicznie dostępnej, jednak odpowiedni link prowadzi na nieistniejącą stronę. Google wyświetla kilka stron z linkami do oficjalnych stron, które oferują zakup elektronicznej kopii standardu za sto euro, ale na trzeciej-czwartej stronie wyników wyszukiwania można znaleźć także bezpośrednie linki do PDF. Generalnie standard niewiele różni się od UCA, ale jest trudniejszy do przeczytania, ponieważ nie zawiera żywych przykładów narodowych cech sortowania ciągów.

Najciekawszą informacją na wiki okazał się link do śledzenia błędów z dyskusją na temat implementacji porównywania ciągów w glibc. Z dyskusji można dowiedzieć się, że w glibc do porównywania ciągów używa się ISOtablicy The Common Template Table (CTT), adres której można znaleźć w załączniku A standardu ISO 14651. Między rokiem 2000 a 2015 ta tablica w glibc nie miała maintainer'a i znacznie różniła się (przynajmniej zewnętrznie) od obecnej wersji standardu. Od 2015 do 2018 roku trwała adaptacja do nowej wersji tabeli i obecnie masz szansę spotkać w rzeczywistości zarówno nową wersję tabeli (CentOS 8), jak i starą (CentOS 7).

Teraz, kiedy mamy wszystkie informacje o algorytmie i pomocniczych tabelach, możemy wrócić do pierwotnego problemu i zrozumieć, jak prawidłowo sortować wiersze w rosyjskiej lokalizacji.

ISO 14651/14652

Kod źródłowy interesującej nas tabeli CTT w większości dystrybucji Linuxa znajduje się w katalogu /usr/share/i18n/locales/. Sama tabela znajduje się w pliku iso14651_t1_common. Następnie ten plik za pomocą dyrektywy copy iso14651_t1_common jest włączany do pliku iso14651_t1, który z kolei jest włączany do plików narodowych, w tym do en_US i ru_RU. W większości dystrybucji Linuxa wszystkie pliki źródłowe są dołączone do podstawowej instalacji, ale jeśli ich nie ma, trzeba będzie zainstalować dodatkowy pakiet z dystrybucji.

Struktura pliku iso14651_t1 może wydawać się okropnie rozwlekła, z nieoczywistymi zasadami budowy nazw, ale jeśli się przyjrzeć, to wszystko jest dość proste. Struktura jest opisana w standardzie ISO 14652, którego kopię można pobrać ze strony open-std.org. Kolejny opis formatu pliku można przeczytać w specyfikacjach POSIX od OpenGroup. Alternatywnie, zamiast czytać standard, można zapoznać się z kodami źródłowymi funkcji collate_read do glibc/locale/programs/ld-collate.c.

Struktura pliku wygląda następująco:

Domyślnie, symbol jest używany jako symbol escape, a koniec linii po symbolu # jest komentarzem. Oba symbole można nadpisać, co zostało zrobione w nowej wersji tabeli:

escape_char /
comment_char %

W pliku będą występować tokeny w formacie <Uxxxx> lub <Uxxxxxxxx> (gdzie x — szesnastkowa cyfra). To szesnastkowe przedstawienie punktów kodowych Unicode w kodowaniu UCS-4 (UTF-32). Wszystkie pozostałe elementy w nawiasach kątowych (w tym <Uxxxx_xxxx>, <2> i tym podobne), są traktowane jako proste stałe tekstowe, które nie mają szczególnego sensu poza kontekstem.

Ciąg LC_COLLATE mówi nam, że dalej zaczynają się dane opisujące porównanie wierszy.

Najpierw ustala się nazwy dla wag w tabeli porównawczej oraz nazwy dla symboli kolacjowych. Ogólnie rzecz biorąc, dwa rodzaje nazw należą do dwóch różnych bytów, ale w rzeczywistym pliku są one pomieszane. Nazwy wag są ustalane za pomocą słowa kluczowego collating-symbol (symbol porównawczy), ponieważ podczas porównywania symbole Unicode, które mają te same wagi, będą uznawane za równoważne symbole.

Łączna długość sekcji w bieżącej wersji pliku wynosi około 900 wierszy. Wybierałem przykłady z różnych miejsc, aby pokazać dowolność nazw i kilka rodzajów składni.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Gwarantowana największa wartość symbolu. Należy umieścić na końcu tej listy
...
collating-element  from ""
collating-element  from ""

collating-symbol rejestruje ciąg OSMANYA w tabeli nazw wag
collating-symbol .. rejestruje sekwencję nazw składającą się z prefiksu S i szesnastkowego sufiksu od 1D000 do 1D35F.
FFFF do collating-symbol wygląda jak duża liczba całkowita bez znaku w systemie szesnastkowym, ale <SFFFF> to tylko nazwa, która mogłaby wyglądać jak <VERYBIGVAL>
nazwa <U0413> oznacza punkt kodowy w kodowaniu UCS-4
collating-element from "" rejestruje nową nazwę dla pary punktów Unicode.

Gdy nazwy wag są określone, ustala się właściwie wagi. Ponieważ podczas porównywania znaczenie mają tylko relacje większe-mniejsze, wagi są określane prostą sekwencją wymieniania nazw. Najpierw wymienia się "lżejsze" wagi, potem "cięższe". Przypominam, że każdemu symbolowi Unicode przypisuje się cztery różne wagi. Tutaj są one zebrane w jedną uporządkowaną sekwencję. Teoretycznie, każda symboliczna nazwa może być używana na dowolnym z czterech poziomów, ale komentarze wskazują, że programiści mentalnie dzielą nazwy według poziomów.

% Przypisania wag symbolicznych

% Przypisania wag trzeciego poziomu




...
% Przypisania wag drugiego poziomu

 % ŁĄCZĄCA LINIA NISKA
 % ŁĄCZĄCA PRZECINEK NAD
 % ŁĄCZĄCA ODWRÓCONA PRZECINEK NAD
...
% Przypisania wag pierwszego poziomu
 % HORYZONTALNE TABULACJE 
 % ZNAK NOWEJ LINI
 % WERTYKALNE TABULACJE
...
 % CYRYLICKA MAŁA LITERA DE
 % CYRYLICKA MAŁA LITERA KOMI DE
 % CYRYLICKA MAŁA LITERA DJE
 % CYRYLICKA MAŁA LITERA KOMI DJE
 % CYRYLICKA MAŁA LITERA GJE
 % CYRYLICKA MAŁA LITERA ZE Z ZSTĘPNIKIEM
 % CYRYLICKA MAŁA LITERA IE
 % CYRYLICKA MAŁA LITERA IE Z BREVE
 % CYRYLICKA MAŁA LITERA UKRAIŃSKIE IE
 % CYRYLICKA MAŁA LITERA ZHE

W końcu sam tabela wag.

Sekcja wag jest zawarta w wierszach z słowami kluczowymi order_start i order_end. Dodatkowe parametry order_start określają, w którym kierunku przeglądane są wiersze na każdym poziomie porównania. Domyślnie używa się parametru forward. Ciało sekcji składa się z wierszy, które zawierają kod znaku i cztery jego wagi. Kod znaku może być reprezentowany przez sam znak, kod punktowy lub symboliczne imię zdefiniowane wcześniej. Wagi mogą być również określane przez symboliczne imiona, kodowe punkty lub samą postacią. Jeżeli używane są punkty kodowe lub znaki, to ich waga odpowiada wartości liczbowej punktu kodowego (pozycji w tabeli Unicode). Znaki, które nie są określone w sposób jawny (jak rozumiem) są uważane za przypisane w tabeli z wagą podstawową odpowiadającą pozycji w tabeli Unicode. Specjalna wartość wagi IGNORE oznacza, że na odpowiednim poziomie porównania dany znak jest ignorowany.

Aby zilustrować strukturę wag, wybrałem trzy dość oczywiste fragmenty:

znaki, które są całkowicie ignorowane
znaki odpowiadające cyfrze trzy na pierwszych dwóch poziomach
początek alfabetu cyrylickiego, który nie zawiera znaków diakrytycznych, a zatem jest sortowany głównie według pierwszego i trzeciego poziomu.

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

Można teraz ponownie wrócić do sortowania przykładów z początku artykułu. Pułapka kryje się w tej części tabeli wag:

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

Widać, że w tej tabeli znaki interpunkcyjne z tabeli ASCII (w tym spacja) podczas porównywania ciągów jest niemal zawsze ignorowane. Wyjątek stanowią tylko ciągi, które są identyczne pod względem wszystkich znaków poza interpunkcją na tych samych pozycjach. Ciągi z mojego przykładu (po sortowaniu) wyglądają dla algorytmu porównania w ten sposób:

AbakanowMichałMalierz
JelkinaElkaRano
IwanowaAllaMalierz
IwanowAndrzejŚlusarz

Biorąc pod uwagę, że w tabeli wag wielkie litery w języku rosyjskim znajdują się po małych (na trzecim poziomie <CAP> cięższy niż <MIN>), sortowanie wygląda absolutnie poprawnie.

Podczas ustawiania zmiennej LC_COLLATE=C ładowana jest specjalna tabela, która określa porównanie bajtów

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'
};

Ponieważ w Unicode kodowa punktacja Ё znajduje się przed A, ciągi są sortowane odpowiednio.

Tablice tekstowe i binarne

Jest oczywiste, że porównanie ciągów to niezwykle często spotykana operacja, a analiza tabeli CTT dosyć kosztowny proces. Aby zoptymalizować dostęp do tabeli, kompilowana jest do postaci binarnej za pomocą polecenia localedef.

Zespół localedef przyjmuje jako parametry plik z tabelą narodowych szczegółów (opcja -i), w którym wszystkie znaki są reprezentowane przez punkty Unicode, oraz plik mapowania punktów Unicode na znaki konkretnej kodowania (opcja -f). W wyniku działania tworzone są pliki binarne dla lokalizacji, o nazwie podanej w ostatnim parametrze.

Glibc obsługuje dwa formaty plików binarnych: "tradycyjny" i "nowoczesny".

Tradycyjny format zakłada, że nazwa lokalizacji to nazwa podkatalogu w /usr/lib/locale/. W tym podkatalogu przechowywane są pliki binarne LC_COLLATE, LC_CTYPE, LC_TIME itd. Plik LC_IDENTIFICATION zawiera formalną nazwę lokalizacji (która może różnić się od nazwy katalogu) oraz komentarze.

Nowoczesny format zakłada przechowywanie wszystkich lokalizacji w jednym archiwum /usr/lib/locale/locale-archive, które jest mapowane do pamięci wirtualnej wszystkich procesów korzystających z glibc. Nazwa lokalizacji w nowoczesnym formacie podlega pewnej kanonizacji — w nazwach kodowania pozostają tylko cyfry i litery, przekształcone na małe litery. Tak ru_RU.KOI8-R, zostanie zachowana jako ru_RU.koi8r.

Pliki wejściowe są poszukiwane w bieżącym katalogu, a także w katalogach /usr/share/i18n/locales/ i /usr/share/i18n/charmaps/ dla plików CTT i plików kodowania odpowiednio.

Na przykład, polecenie

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

skompiluje plik /usr/share/i18n/locales/ru_RU z wykorzystaniem pliku kodowania /usr/share/i18n/charmaps/MAC-CYRILLIC.gz i zapisze wynik w /usr/lib/locale/locale-archive pod nazwą ru_RU.maccyrillic

Jeśli ustawisz zmienną LANG=en_US.UTF-8 , to glibc będzie szukacz pliki binarnych lokalizacji w następującej kolejności plików i katalogów:

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

Jeśli lokalizacja występuje zarówno w tradycyjnym, jak i nowoczesnym formacie, pierwszeństwo ma format nowoczesny.

Lista skompilowanych lokalizacji może być przeglądana za pomocą polecenia locale -a.

Przygotowanie własnej tabeli porównawczej

Teraz, uzbrojony w wiedzę, możesz stworzyć własną idealną tabelę porównawczą łańcuchów. Ta tabela powinna poprawnie porównywać rosyjskie litery, w tym literę Ё, i przy tym uwzględniać znaki przestankowe zgodnie z tabelą ASCII.

Proces przygotowania własnej tabeli sortowania składa się z dwóch etapów: edytowania tabeli wag i kompilacji jej w formę binarną za pomocą polecenia localedef.

Aby tabela porównawcza mogła być dostosowywana przy minimalnych kosztach edycyjnych, w formacie ISO 14652 zapewniają sekcje korekty wag istniejącej tabeli. Sekcja zaczyna się od słowa kluczowego reorder-after i wskazania pozycji, po której następuje zamiana. Sekcję kończy linia reorder-end. Jeśli konieczne jest poprawienie kilku fragmentów tabeli, tworzy się osobną sekcję dla każdego z takich fragmentów.

Skopiowałem nowe wersje plików iso14651_t1_common i ru_RU z repozytorium glibc do mojego katalogu domowego ~/.local/share/i18n/locales/ i lekko edytowałem sekcję LC_COLLATE do ru_RU. Nowe wersje plików są w pełni zgodne z moją wersją glibc. Jeśli chcesz użyć starych wersji plików, musisz zmienić symboliczne nazwy oraz miejsce, od którego rozpoczyna się zamiana w tabeli.

LC_COLLATE
% Skopiuj szablon z ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % WYKRZYKNIK
 ;;; % CEFKA
...
 ;;; % ZAMKNIĘCIE KLAMRY
 ;;; % TYLDA
reorder-end
KONIEC LC_COLLATE

W rzeczywistości należałoby zmienić pola w LC_IDENTIFICATION tak aby wskazywały na lokalizację ru_MY, ale w moim przykładzie nie było to konieczne, ponieważ wykluczyłem z wyszukiwania lokalizacji archiwum locale-archive.

Aby localedef pracowałem z plikami w swoim katalogu za pośrednictwem zmiennej I18NPATH można dodać dodatkowy katalog do wyszukiwania plików wejściowych, a katalog do zapisywania plików binarnych można określić jako ścieżkę z ukośnikami:

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

POSIX zakłada, że w LANG można pisać absolutne ścieżki do katalogów z plikami lokalizacyjnymi, zaczynając od ukośnika, ale glibc do Linuxa wszystkie ścieżki są liczone od katalogu bazowego, który można nadpisać przez zmienną LOCPATH. Po ustawieniu LOCPATH=~/.local/lib/locale/ wszystkie pliki związane z lokalizacją będą wyszukiwane tylko w moim katalogu. Archiwum lokalizacyjne przy ustawionej zmiennej LOCPATH jest ignorowane.

Oto on, decydujący test:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanow Michał;malarz
Jołkina Elżbieta;operator dźwigu
Iwanow Andrzej; ślusarz
Iwanowa Alla;adwokat

Hurra! Zrobiliśmy to!

Praca nad błędami

Już odpowiedziałem na pytania dotyczące sortowania linii, które zadano na początku, ale pozostało jeszcze kilka pytań dotyczących błędów — widocznych i niewidocznych.

Wróćmy do pierwotnego zadania.

I program sort i program join korzystają z tych samych funkcji porównywania linii z glibc. Jak to się mogło stać, że join generuje błąd sortowania w linijkach posortowanych komendą sort w lokalizacji en_US.UTF-8? Ответ прост: sort porównuje całą linię, a join porównuje tylko klucz, którym domyślnie jest początek linii aż do pierwszego białego znaku. W moim przykładzie prowadziło to do komunikatu o błędzie, ponieważ sortowanie pierwszych słów w linijkach nie zgadzało się z sortowaniem pełnych linii.

Lokalizacja "C" zapewnia, że w posortowanych linijkach początki podciągów aż do pierwszej spacji również będą posortowane, ale to tylko maskuje błąd. Można znaleźć takie dane (ludzie o tych samych nazwiskach, ale różnych imionach), które bez komunikatu o błędzie dawałyby niewłaściwy wynik przy scalaniu plików. Jeśli chcemy, aby join łaczył linie plików według imienia i nazwiska, to poprawnym sposobem będzie wyraźne określenie separatora pól i sortowanie według kluczowego pola, a nie według całej linii. W tym przypadku i scalanie przebiegnie poprawnie i w żadnej lokalizacji nie będzie błędów:

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

Przykład z sukcesem zakończony w kodowaniu CP1251 zawiera jeszcze jeden błąd. Chodzi o to, że we wszystkich znanych mi dystrybucjach Linuxa brakuje skompilowanej lokalizacji ru_RU.CP1251. Jeśli skompilowana lokalizacja nie zostanie znaleziona, to sort cicho używa porównania bajtowego, co mogliśmy obserwować.

A propos, jest jeszcze jeden mały bug związany z brakiem dostępnych skompilowanych lokalizacji. Komenda LOCPATH=/tmp locale -a wyświetli listę wszystkich lokalizacji w locale-archive, ale przy ustawionej zmiennej LOCPATH dla wszystkich programów (w tym dla samej locale) te lokalizacje będą niedostępne.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Nie można ustawić LC_CTYPE na domyślną lokalizację: Nie ma takiego pliku lub katalogu
locale: Nie można ustawić LC_MESSAGES na domyślną lokalizację: Nie ma takiego pliku lub katalogu
locale: Nie można ustawić LC_COLLATE na domyślną lokalizację: Nie ma takiego pliku lub katalogu
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: używam zasad sortowania ‘en_US.UTF-8’

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: używam prostego porównania bajtów

Podsumowanie

Jeśli jesteś programistą, który przywykł uważać, że linie to zbiór bajtów, to twój wybór LC_COLLATE=C.

Jeśli jesteś lingwistą lub redaktorem słowników, lepiej, abyś skompilował swoją lokalizację.

Jeśli jesteś zwykłym użytkownikiem, wystarczy, że przyzwyczaisz się do tego, że komenda ls -a wyświetla pliki zaczynające się od kropki, wymieszane z plikami zaczynającymi się od litery, a Midnight Commander, który używa swoich wewnętrznych funkcji do sortowania imion, umieszcza pliki zaczynające się od kropki na początku listy.