Inledning

Allt började med ett kort manus som var tänkt att kombinera adressinformation e-mail anställda hämtade från listan över e-postlistaanvändare, med anställningspositioner hämtade från HR-avdelningens databas. Båda listorna exporterades till Unicode-textfiler UTF-8 och sparas med Unix-radändelser.

Innehåll mail.txt

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

Innehåll buhg.txt

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

För att slå samman sorterades filerna med Unix-kommandot sortera och skickas till Unix-programmets input delta, som oväntat misslyckades med ett fel:

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

Att titta på sorteringsresultatet med dina ögon visade att sorteringen i allmänhet är korrekt, men vid sammanträffanden av manliga och kvinnliga efternamn kommer de kvinnliga före de manliga:

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

Ser ut som ett sorteringsfel i Unicode eller som en manifestation av feminism i sorteringsalgoritmen. Det första är förstås mer rimligt.

Låt oss lägga det åt sidan för nu delta och fokusera på sortera. Låt oss försöka lösa problemet med hjälp av vetenskaplig petning. Låt oss först byta språk från sv på ru_RU. För att sortera skulle det räcka med att ställa in miljövariabeln LC_COLLATE, men vi kommer inte att slösa tid på småsaker:

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

Inget förändrat.

Låt oss försöka koda om filerna till en enkelbytekodning:

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

Återigen ingenting har förändrats.

Det finns inget du kan göra, du måste leta efter en lösning på Internet. Det står inget direkt om ryska efternamn, men det finns frågor om andra sorteringsmärkligheter. Här är till exempel ett problem: unix sort behandlar '-' (streck) tecken som osynliga. Kort sagt, strängarna "ab", "aa", "ac" sorteras som "aa", "ab", "ac".

Svaret är standard överallt: använd programmerarens språk "C" och du kommer att bli lycklig. Låt oss försöka:

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

Något har förändrats. Ivanovs ställde upp i rätt ordning, även om Yolkina halkade någonstans. Låt oss återgå till det ursprungliga problemet:

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

Det fungerade utan fel, som Internet lovade. Och detta trots Yolkina i första raden.

Problemet verkar vara löst, men för säkerhets skull, låt oss prova en annan rysk kodning - Windows CP1251:

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

Sorteringsresultatet kommer konstigt nog att sammanfalla med språket "C", och hela exemplet, följaktligen, körs utan fel. Någon sorts mystik.

Jag gillar inte mystik i programmering eftersom det vanligtvis döljer misstag. Vi måste seriöst undersöka hur det fungerar. sortera och vad påverkar det? LC_COLLATE .

I slutet ska jag försöka svara på frågorna:

varför sorterades kvinnliga efternamn fel?
Varför LANG=ru_RU.CP1251 visade sig vara likvärdig LANG=C
varför göra sortera и delta olika idéer om ordningen på sorterade strängar
varför finns det fel i alla mina exempel?
äntligen hur man sorterar strängar efter eget tycke

Sortering i Unicode

Första stoppet blir teknisk rapport nr 10 med titeln Unicode-sorteringsalgoritm nätet unicode.org. Rapporten innehåller många tekniska detaljer, så låt mig ge en kort sammanfattning av huvudidéerna.

Sortering — Att "jämföra" strängar är grunden för alla sorteringsalgoritmer. Algoritmerna i sig kan skilja sig åt ("bubbla", "sammanfoga", "snabbt"), men de kommer alla att använda en jämförelse av ett par strängar för att bestämma i vilken ordning de visas.

Att sortera strängar i naturligt språk är ett ganska komplext problem. Även i de enklaste enkelbyte-kodningarna kommer bokstävernas ordning i alfabetet, även på något sätt som skiljer sig från det engelska latinska alfabetet, inte längre att sammanfalla med ordningen på de numeriska värdena som dessa bokstäver är kodade med. Så i det tyska alfabetet bokstaven Ö står mellan О и P, och i kodningen CP850 hon kommer emellan ÿ и Ü.

Du kan försöka abstrahera från en specifik kodning och överväga "ideala" bokstäver som är ordnade i någon ordning, som görs i Unicode. Kodningar utf8, utf16 eller en-byte KOI8-R (om en begränsad delmängd av Unicode behövs) ger olika numeriska representationer av bokstäver, men refererar till samma element i bastabellen.

Det visar sig att även om vi bygger en symboltabell från grunden, kommer vi inte att kunna tilldela den en universell symbolordning. I olika nationella alfabet som använder samma bokstäver kan ordningen på dessa bokstäver skilja sig åt. Till exempel på franska Æ kommer att betraktas som en ligatur och sorteras som en sträng AE. På norska Æ kommer att vara ett separat brev, som ligger efter Z. Förresten, förutom ligaturer som Æ Det finns bokstäver skrivna med flera symboler. Så i det tjeckiska alfabetet finns en bokstav Ch, som står mellan H и I.

Förutom skillnader i alfabet finns det andra nationella traditioner som påverkar sorteringen. I synnerhet uppstår frågan: i vilken ordning ska ord som består av stora och små bokstäver förekomma i ordboken? Sortering kan också påverkas av användningen av skiljetecken. På spanska används ett inverterat frågetecken i början av en frågesats (Gillar du musik?). I det här fallet är det uppenbart att frågesatser inte ska grupperas i ett separat kluster utanför alfabetet, men hur sorterar man rader med andra skiljetecken?

Jag kommer inte att uppehålla mig vid att sortera strängar på språk som skiljer sig mycket från europeiska. Observera att i språk med skrivriktning från höger till vänster eller uppifrån och ner, lagras tecken i rader troligen i läsordning, och även icke-alfabetiska skrivsystem har sina egna sätt att ordna rader tecken för tecken . Till exempel kan hieroglyfer sorteras efter stil (Kinesiska tecken nycklar) eller genom uttal. För att vara ärlig har jag ingen aning om hur emojis ska ordnas, men du kan hitta på något för dem också.

Baserat på funktionerna som anges ovan formulerades de grundläggande kraven för att jämföra strängar baserade på Unicode-tabeller:

jämförelse av strängar beror inte på positionen för tecken i kodtabellen;
sekvenser av tecken som bildar ett enda tecken reduceras till kanonisk form (A + den övre cirkeln är densamma som Å);
När man jämför strängar betraktas ett tecken i strängens sammanhang och, om nödvändigt, kombineras med dess grannar till en jämförelseenhet (Ch på tjeckiska) eller är uppdelad i flera (Æ på franska);
alla nationella funktioner (alfabet, versaler/gemener, skiljetecken, skrivordning) måste konfigureras fram till den manuella tilldelningen av ordningen (emoji);
jämförelse är viktigt inte bara för sortering, utan även på många andra ställen, till exempel för att specificera radintervall (ersätter {A... z} i bash);
jämförelsen bör göras ganska snabbt.

Dessutom formulerade rapportens författare jämförelseegenskaper som algoritmutvecklare inte bör lita på:

jämförelsealgoritmen bör inte kräva en separat uppsättning tecken för varje språk (ryska och ukrainska språk delar de flesta kyrilliska tecken);
jämförelsen bör inte förlita sig på teckenordningen i Unicode-tabeller;
strängens vikt ska inte vara ett attribut för strängen, eftersom samma sträng i olika kulturella sammanhang kan ha olika vikt;
radvikter kan ändras vid sammanslagning eller delning (från x < y det följer inte det xz < yz);
olika strängar som har samma vikt anses lika ur sorteringsalgoritmens synvinkel. Det är möjligt att införa ytterligare beställning av sådana strängar, men det kan försämra prestandan;
Vid upprepad sortering kan rader med samma vikt bytas. Robusthet är en egenskap hos en specifik sorteringsalgoritm och inte en egenskap hos en strängjämförelsealgoritm (se föregående stycke);
Sorteringsregler kan förändras över tid i takt med att kulturella traditioner förfinas/förändras.

Det föreskrivs också att jämförelsealgoritmen inte vet något om semantiken för de strängar som bearbetas. Strängar som endast består av siffror ska alltså inte jämföras som siffror, och i listor med engelska namn är artikeln (Beatles, The).

För att uppfylla alla specificerade krav föreslås en tabellsorteringsalgoritm på flera nivåer (faktiskt fyra nivåer).

Tidigare reducerades tecknen i strängen till kanonisk form och grupperades i jämförelseenheter. Varje jämförelseenhet tilldelas flera vikter som motsvarar flera jämförelsenivåer. Jämförelseenheternas vikter är delar av ordnade uppsättningar (i detta fall heltal) som kan jämföras för mer eller mindre. Särskild betydelse IGNORERAD (0x0) betyder att på motsvarande jämförelsenivå är denna enhet inte involverad i jämförelsen. Jämförelsen av strängar kan upprepas flera gånger med hjälp av vikterna för motsvarande nivåer. På varje nivå jämförs vikterna för jämförelseenheterna för två rader sekventiellt med varandra.

I olika implementeringar av algoritmen för olika nationella traditioner kan värdena på koefficienterna skilja sig åt, men Unicode-standarden innehåller en grundläggande vikttabell - "Standard Unicode-sorteringselementtabell" (DUCET). Jag skulle vilja notera att inställningen av variabeln LC_COLLATE är faktiskt en indikation på valet av vikttabellen i strängjämförelsefunktionen.

Viktkoefficienter DUCET ordnat enligt följande:

på den första nivån reduceras alla bokstäver till samma skiftläge, diakritiska tecken kasseras, skiljetecken (inte alla) ignoreras;
på den andra nivån tas endast hänsyn till diakritiska tecken;
på den tredje nivån beaktas endast fall;
på fjärde nivån beaktas endast skiljetecken.

Jämförelsen sker i flera omgångar: först jämförs koefficienterna för den första nivån; om vikterna sammanfaller, utförs en upprepad jämförelse med vikterna på andra nivån; sedan kanske en trea och en fjärde.

Jämförelsen avslutas när raderna innehåller matchande jämförelseenheter med olika vikter. Rader som har samma vikt på alla fyra nivåerna anses vara lika med varandra.

Denna algoritm (med en massa ytterligare tekniska detaljer) gav namnet till rapport nr 10 - "Unicode Collation Algorithm" (ACU).

Det är här sorteringsbeteendet från vårt exempel blir lite tydligare. Det skulle vara trevligt att jämföra det med Unicode-standarden.

För att testa implementeringar ACU det finns en speciell тест, använder sig av vikter fil, genomföra DUCET. Du kan hitta alla möjliga roliga saker i vågfilen. Till exempel, det finns ordningen för mahjong och europeiska dominobrickor, såväl som ordningen för färger i en kortlek (symbol 1F000 och vidare). Kortfärgerna placeras enligt reglerna för bridge - PCBT, och korten i färgen är i sekvensen T, 2,3, XNUMX... K.

Manuell kontroll av att rader är korrekt sorterade enl DUCET skulle vara ganska tråkigt, men lyckligtvis för oss finns det en exemplarisk implementering av biblioteket för att arbeta med Unicode - "Internationella komponenter för Unicode"(ICU).

På webbplatsen för detta bibliotek, utvecklad i IBM, det finns demosidor, inklusive sida för strängjämförelsealgoritm. Vi går in i våra testrader med standardinställningar och, se och häpna, vi får perfekt rysk sortering.

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

Förresten, hemsidan ICU Du kan hitta ett förtydligande av jämförelsealgoritmen vid bearbetning av skiljetecken. I exemplen Vanliga frågor om sortering apostrof och bindestreck ignoreras.

Unicode hjälpte oss, men leta efter orsaker till konstigt beteende sortera в Linux måste gå någon annanstans.

Sorterar i glibc

Snabböversikt över verktygets källkoder sortera av GNU Core Utils visade att i själva verktyget handlar lokalisering om att skriva ut variabelns nuvarande värde LC_COLLATE när du kör i felsökningsläge:

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

Strängjämförelser utförs med standardfunktionen strcoll, vilket betyder att allt intressant finns i biblioteket glibc.

På wiki projektet glibc tillägnad strängjämförelse ett stycke. Av denna paragraf kan man förstå att i glibc sortering baseras på en algoritm som vi redan känner till ACU (Unicode-sorteringsalgoritmen) och/eller med en standard som ligger nära den ISO 14651 (Internationell strängordning och jämförelse). När det gäller den senaste standarden bör det noteras att på webbplatsen standards.iso.org ISO 14651 officiellt förklarats allmänt tillgänglig, men motsvarande länk leder till en obefintlig sida. Google returnerar flera sidor med länkar till officiella webbplatser som erbjuder att köpa en elektronisk kopia av standarden för hundra euro, men på den tredje eller fjärde sidan med sökresultat finns det också direktlänkar till PDF. I allmänhet skiljer sig standarden praktiskt taget inte från ACU, men är tråkigare att läsa eftersom den inte innehåller tydliga exempel på nationella drag av strängsortering.

Den mest intressanta informationen om wiki det fanns en länk till felsökare med en diskussion om implementeringen av strängjämförelse i glibc. Av diskussionen kan man lära sig det glibc används för att jämföra strängar ISOpersonligt bord Den gemensamma malltabellen (CTT), vars adress finns i ansökan A standard ISO 14651 . Mellan 2000 och 2015 denna tabell in glibc hade ingen underhållare och var helt annorlunda (åtminstone externt) från den nuvarande versionen av standarden. Från 2015 till 2018 skedde anpassning till den nya versionen av bordet, och nu har du chansen att träffa en ny version av bordet i verkligheten (8 CentOS), och gamla (7 CentOS).

Nu när vi har all information om algoritmen och hjälptabellerna kan vi återgå till det ursprungliga problemet och förstå hur man korrekt sorterar strängar i den ryska lokalen.

ISO 14651 / 14652

Källkoden för tabellen vi är intresserade av CTT på de flesta distributioner Linux finns i katalogen /usr/share/i18n/locales/. Själva tabellen finns i filen iso14651_t1_common. Då är detta fildirektivet kopiera iso14651_t1_common ingår i filen iso14651_t1, som i sin tur ingår i nationella akter, bl.a sv и ru_RU. På de flesta distributioner Linux Alla källfiler ingår i grundinstallationen, men om de inte finns måste du installera ett extra paket från distributionen.

Filstruktur iso14651_t1 kan verka fruktansvärt mångsidigt, med icke självklara regler för att konstruera namn, men om man tittar på det är allt ganska enkelt. Strukturen beskrivs i standarden ISO 14652 , varav en kopia kan laddas ner från webbplatsen open-std.org. En annan beskrivning av filformatet kan läsas i specifikationer POSIX från OpenGroup. Som ett alternativ till att läsa standarden kan du studera funktionens källkod collate_read в glibc/locale/programs/ld-collate.c.

Filstrukturen ser ut så här:

Som standard används tecknet som ett escape-tecken, och slutet av raden efter #-tecknet är en kommentar. Båda symbolerna kan omdefinieras, vilket är vad som görs i den nya versionen av tabellen:

escape_char /
comment_char %

Filen kommer att innehålla tokens i formatet eller (Var x - hexadecimal siffra). Detta är den hexadecimala representationen av Unicode-kodpunkter i kodningen UCS-4 (UTF-32). Alla andra element inom vinkelparenteser (inklusive , <2> och liknande) anses vara enkla strängkonstanter som har liten betydelse utanför sammanhanget.

Linje LC_COLLATE berättar att härnäst börjar data som beskriver jämförelsen av strängar.

Först anges namn för vikterna i jämförelsetabellen och namn för symbolkombinationer. Generellt sett tillhör de två typerna av namn två olika enheter, men i själva filen är de blandade. Namnen på vikterna anges av nyckelordet samla-symbol (jämförelsetecken) för vid jämförelse kommer Unicode-tecken som har samma vikt att betraktas som likvärdiga tecken.

Den totala längden på avsnittet i den aktuella filrevisionen är cirka 900 rader. Jag drog exempel från flera ställen för att visa godtyckligheten i namn och flera typer av syntax.

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

samla-symbol loggar en sträng OSMANYA i tabellen över namn på vågar
samla-symbol .. registrerar en sekvens av namn som består av ett prefix S och hexadecimalt numeriskt suffix från 1D000 до 1D35F.
F F F F в samla-symbol ser ut som ett stort heltal utan tecken i hexadecimal, men det är bara ett namn som kan se ut
Namn betyder kodpunkt vid kodning UCS-4
sammanställningselement från " " registrerar ett nytt namn för ett par Unicode-punkter.

När namnen på vikterna har definierats anges de faktiska vikterna. Eftersom endast större-än-mindre relationer spelar roll i jämförelse, bestäms vikterna av en enkel sekvens av listnamn. De "lättare" vikterna listas först, sedan de "tyngre". Låt mig påminna dig om att varje Unicode-tecken tilldelas fyra olika vikter. Här kombineras de till en enda ordnad sekvens. I teorin kan vilket symboliskt namn som helst användas på vilken som helst av de fyra nivåerna, men kommentarer tyder på att utvecklarna mentalt delar upp namn i nivåer.

% 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

Slutligen den faktiska vikttabellen.

Viktsektionen är omsluten av sökordsrader order_start и order_end. Extra tillval order_start bestämma i vilken riktning rader ska skannas vid varje jämförelsenivå. Standardinställningen är fram-. Sektionens kropp består av rader som innehåller symbolkoden och dess fyra vikter. Teckenkoden kan representeras av själva tecknet, en kodpunkt eller ett symboliskt namn som definierats tidigare. Vikter kan också ges till symboliska namn, kodpunkter eller själva symbolerna. Om kodpunkter eller tecken används är deras vikt densamma som kodpunktens numeriska värde (position i Unicode-tabellen). Tecken som inte specificeras explicit (som jag förstår) anses tilldelade tabellen med en primär vikt som matchar positionen i Unicode-tabellen. Speciellt viktvärde IGNORERA betyder att symbolen ignoreras vid lämplig jämförelsenivå.

För att demonstrera strukturen på skalorna valde jag tre ganska uppenbara fragment:

karaktärer som helt ignoreras
symboler som motsvarar siffran tre i de två första nivåerna
början av det kyrilliska alfabetet, som inte innehåller diakritiska tecken, och därför sorteras huvudsakligen efter den första och tredje nivån.

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

Nu kan du återgå till att sortera exemplen från början av artikeln. Bakhållet ligger i denna del av vikttabellen:

<U0020> IGNORE;IGNORE;IGNORE;<U0020> % SPACE
<U0021> IGNORE;IGNORE;IGNORE;<U0021> % EXCLAMATION MARK
<U0022> IGNORE;IGNORE;IGNORE;<U0022> % QUOTATION MARK
...

Det kan ses att i denna tabell skiljetecken från tabellen ASCII (inklusive mellanslag) ignoreras nästan alltid när man jämför strängar. De enda undantagen är linjer som matchar i allt utom skiljetecken som finns i matchande positioner. Raderna från mitt exempel (efter sortering) för jämförelsealgoritmen ser ut så här:

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

Med tanke på att i tabellen över skalor kommer stora bokstäver på ryska efter gemener (på tredje nivån tyngre än ), ser sorteringen helt korrekt ut.

När du ställer in en variabel LC_COLLATE=C en speciell tabell laddas som specificerar en byte-för-byte-jämförelse

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

Eftersom kodpunkten Ё i Unicode kommer före A, sorteras strängarna därefter.

Text och binära tabeller

Uppenbarligen är strängjämförelse en extremt vanlig operation och tabellparsning CTT ett ganska kostsamt förfarande. För att optimera åtkomsten till tabellen kompileras den till binär form med kommandot localdef.

Team localdef accepterar som parametrar en fil med en tabell över nationella egenskaper (alternativ -i), där alla tecken representeras av Unicode-punkter, och en fil med överensstämmelse mellan Unicode-punkter och tecken med en specifik kodning (alternativ -f). Som ett resultat av arbetet skapas binära filer för lokalen med det namn som anges i den sista parametern.

glibc stöder två binära filformat: "traditionell" och "modern".

Det traditionella formatet innebär att namnet på lokalen är namnet på underkatalogen i /usr/lib/locale/. Denna underkatalog lagrar binära filer LC_COLLATE, LC_CTYPE, LC_TIME och så vidare. Fil LC_IDENTIFIKATION innehåller det formella namnet på lokalen (som kan skilja sig från katalognamnet) och kommentarer.

Det moderna formatet innebär att alla språk lagras i ett enda arkiv /usr/lib/locale/locale-archive, som mappas till det virtuella minnet för alla processer som använder glibc. Lokalnamnet i det moderna formatet är föremål för viss kanonisering - endast siffror och bokstäver reducerade till gemener finns kvar i kodningsnamnen. Så ru_RU.KOI8-R, kommer att sparas som ru_RU.koi8r.

Indatafiler söks i den aktuella katalogen, såväl som i kataloger /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ för filer CTT respektive kodningsfiler.

Till exempel kommandot

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

kommer att kompilera filen /usr/share/i18n/locales/ru_RU med hjälp av en kodningsfil /usr/share/i18n/charmaps/MAC-CYRILLIC.gz och spara resultatet i /usr/lib/locale/locale-archive under namnet ru_RU.maccyrillic

Om du ställer in variabeln LANG = en_US.UTF-8 то glibc kommer att leta efter binärer för språk i följande sekvens av filer och kataloger:

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

Om en plats förekommer i både traditionella och moderna format, prioriteras det moderna.

Du kan se listan över kompilerade språk med kommandot locale -a.

Förbereder din jämförelsetabell

Nu, beväpnad med kunskapen, kan du skapa din egen idealiska strängjämförelsetabell. Denna tabell bör korrekt jämföra ryska bokstäver, inklusive bokstaven Ё, och samtidigt ta hänsyn till skiljetecken i enlighet med tabellen ASCII.

Processen att förbereda din egen sorteringstabell består av två steg: redigera vikttabellen och kompilera den till binär form med kommandot localdef.

För att jämförelsetabellen ska kunna justeras med minimala redigeringskostnader, i formatet ISO 14652 Sektioner för justering av vikterna för ett befintligt bord finns. Avsnittet börjar med ett nyckelord ombeställ-efter och indikera den position efter vilken bytet utförs. Avsnittet avslutas med raden ombeställning-slut. Om det är nödvändigt att korrigera flera avsnitt i tabellen skapas en sektion för varje sådan sektion.

Jag kopierade nya versioner av filerna iso14651_t1_common и ru_RU från förvaret glibc till min hemkatalog ~/.local/share/i18n/locales/ och redigerade avsnittet något LC_COLLATE в ru_RU. Nya versioner av filer är helt kompatibla med min version glibc. Om du vill använda äldre versioner av filer måste du ändra de symboliska namnen och platsen där ersättningen börjar i tabellen.

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

I själva verket skulle det vara nödvändigt att ändra fälten i LC_IDENTIFIKATION så att de pekar på platsen ru_MY, men i mitt exempel krävdes inte detta, eftersom jag uteslöt arkivet från sökningen efter språk locale-arkiv.

Att localdef arbetade med filer i min mapp genom en variabel I18NPATH Du kan lägga till en extra katalog för att söka efter indatafiler, och katalogen för att spara binära filer kan anges som en sökväg med snedstreck:

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

POSIX antar att i LÅNG du kan skriva absoluta sökvägar till kataloger med lokalfiler, börja med ett snedstreck, men glibc в Linux alla sökvägar räknas från baskatalogen, som kan åsidosättas genom en variabel LOCPATH. Efter installation LOCPATH=~/.local/lib/locale/ alla filer relaterade till lokalisering kommer endast att sökas i min mapp. Arkiv över lokaler med variabeluppsättningen LOCPATH ignoreras.

Här är det avgörande testet:

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

Hurra! Vi gjorde det!

Vissa fel

Jag har redan svarat på frågorna om strängsortering som ställdes i början, men det finns fortfarande ett par frågor om fel - synliga och osynliga.

Låt oss återgå till det ursprungliga problemet.

Och programmet sortera och programmet delta använd samma strängjämförelsefunktioner från glibc. Hur gick det till det delta gav ett sorteringsfel på rader sorterade efter kommandot sortera i lokalen sv_US.UTF-8? Svaret är enkelt: sortera jämför hela strängen, och delta jämför endast nyckeln, som som standard är början på strängen upp till det första blanktecken. I mitt exempel resulterade detta i ett felmeddelande eftersom sorteringen av de första orden i raderna inte matchade sorteringen av de fullständiga raderna.

Plats "C" garanterar att i sorterade strängar kommer de initiala delsträngarna fram till det första utrymmet också att sorteras, men detta maskerar bara felet. Det är möjligt att välja data (personer med samma efternamn, men olika förnamn) som utan felmeddelandet skulle ge ett felaktigt filsammanfogningsresultat. Om vi vill delta sammanslagna filrader med fullständigt namn, då skulle det korrekta sättet vara att explicit specificera fältavgränsaren och sortera efter nyckelfältet och inte efter hela raden. I det här fallet kommer sammanslagningen att fortsätta på rätt sätt och det kommer inte att finnas några fel i någon lokal:

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

Exekverat exempel i kodning framgångsrikt CP1251 innehåller ett annat fel. Faktum är att i alla distributioner som jag känner till Linux paket saknar kompilerad lokalitet ru_RU.CP1251. Om den kompilerade lokalen inte hittas, då sortera använder tyst en byte-för-byte-jämförelse, vilket är vad vi observerade.

Förresten, det finns en annan liten glitch relaterad till otillgängligheten för kompilerade lokaler. Team LOCPATH=/tmp locale -a kommer att ge en lista över alla platser i locale-arkiv, men med variabeluppsättningen LOCPATH för alla program (inklusive de flesta locale) dessa språk kommer inte att vara tillgängliga.

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

Slutsats

Om du är en programmerare som är van att tro att strängar är en uppsättning byte, då är ditt val LC_COLLATE=C.

Om du är en lingvist eller ordbokskompilator, då är det bättre att kompilera på din plats.

Om du är en enkel användare behöver du bara vänja dig vid det faktum att kommandot ls -a matar ut filer som börjar med en prick blandad med filer som börjar med en bokstav, och Midnattskommandör, som använder sina interna funktioner för att sortera namn, placerar filer som börjar med en punkt i början av listan.