Introduktion

Det hela började med ett kort skript som skulle slå samman information om adresser e-post från anställdas lista i mailutskicket med anställdas roller från personalavdelningens databas. Båda listorna exporterades till textfiler i Unicode-kodning UTF-8 och sparades med Unix-radslut.

Innehåll mail.txt

Ivanov Andrei;ia@example.com

Innehåll buhg.txt

Ivanova Alla;målare
Yelkina Ella;kranförare
Ivanov Andrei;svetsare
Abakanov Mikhail;målare

För att slå samman var filerna sorterade med Unix-kommandot sort och matades in i programmet join, som oväntat avslutades med ett fel:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: är inte sorterat: Ivanov Andrei;svetsare

Översiktsgranskning av sorteringsresultatet visade att sorteringen överlag var korrekt, men när det gällde överlappningar mellan manliga och kvinnliga efternamn hamnar kvinnorna före männen:

$> sort buhg.txt
Abakanov Mikhail;målare
Yelkina Ella;kranförare
Ivanova Alla;målare
Ivanov Andrei;svetsare

Det ser ut som en bugg i Unicode-sortering eller ett uttryck för feminism i sorteringsalgoritmen. Det första verkar förstås mer rimligt.

Låt oss skjuta på det för nu join och fokusera på sort. Låt oss försöka lösa uppgiften med trial and error. Först ändrar vi locale från en_US till ru_RU. För sortering skulle det ha räckt att sätta miljövariabeln LC_COLLATE, men vi ska inte snåla:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;målare
Yelkina Ella;kranförare
Ivanova Alla;målare
Ivanov Andrei;svetsare

Ingenting har förändrats.

Låt oss försöka konvertera filerna till en enbyteskodning:

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

Återigen har ingenting förändrats.

Det är ingen utväg, vi måste söka lösningen på internet. Direkt om ryska efternamn finns inget, men det finns frågor om andra konstigheter i sortering. Till exempel finns det ett problem: unix sort behandlar ‘-’ (bindestreck) som osynliga. Kort sagt sorteras strängarna "a-b", "aa", "ac" som "aa", "a-b", "ac".

Svaren är alltid standard: använd programmerarlocale "C" och du får din lycka. Vi testar:

$> LANG=C sort buhg.txt
Yelkina Ella;kranförare
Abakanov Mikhail;målare
Ivanov Andrei;svetsare
Ivanova Alla;advokat

Något har förändrats. Ivanov-familjen har ställt sig i rätt ordning, men Jelkin har glidit bort. Vi återgår till den ursprungliga uppgiften:

$> 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, precis som internet lovade. Och detta trots Jelkin i den första raden.

Problemet verkar vara löst, men för säkerhets skull provar vi en till rysk kodning — Windows-kodningen. CP1251:

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

Sorteringsresultatet, märkligt nog, kommer att överensstämma med lokaliteten. "C", och hela exemplet går därmed igenom utan fel. Det är någon slags mystik.

Jag gillar inte mystik i programmering, eftersom den vanligtvis döljer fel. Jag måste verkligen göra en djupdykning i hur det fungerar. sort och vad det påverkar. LC_COLLATE .

Till slut kommer jag att försöka svara på frågorna:

• varför kvinnliga efternamn sorterade felaktigt.
• varför LANG=ru_RU.CP1251 visade sig vara ekvivalent. LANG=C
• varför får sort och join olika representationer av ordningen för sorterade rader.
• varför finns det fel i alla mina exempel.
• slutligen, hur man sorterar rader efter eget tycke.

Sortering i Unicode.

Den första stopppunkten kommer att vara teknisk rapport nr 10 med titeln. Unicode collation algorithm. på webbplatsen unicode.org.Rapporten innehåller många tekniska detaljer, så jag tillåter mig att ge en sammanfattning av huvuddiskussionerna.

Collation — "jämförelse" av strängar — är grunden för varje sorteringsalgoritm. Själva algoritmerna kan variera ("bubblande", "sammanfogande", "snabb"), men alla kommer att använda jämförelse av strängpar för att bestämma deras ordning.

Sortering av strängar på naturligt språk är ett ganska komplext problem. Även i de enklaste enbyte-kodningarna kan ordningen på bokstäver i alfabetet, även i något som avviker från den engelska latinska uppsättningen, redan skilja sig från den ordning av numeriska värden som dessa bokstäver koden. Så i det tyska alfabetet kommer bokstaven Ö att ligga mellan Till och P, men i kodningen CP850 hamnar den mellan ÿ och Ü..

Man kan försöka abstrahera från den specifika kodningen och betrakta "idealiska" bokstäver, som är placerade i en viss ordning, som det görs i Unicode. Kodningar UTF8, UTF16 eller enbyte-kodning KOI8-R (om ett begränsat delmängd av Unicode behövs) kommer att ge olika numeriska representationer av bokstäverna, men hänvisa till samma grundläggande tabell.

Det visar sig att även om vi bygger en teckentabell från grunden, kommer vi inte att kunna tilldela en universell ordning för tecknen. I olika nationella alfabet som använder samma bokstäver kan ordningen av dessa bokstäver skilja sig. Till exempel på franska Æ kommer att betraktas som en ligatur och sorteras som en sträng AE. I norska språket Æ kommer att vara en separat bokstav som ligger efter Z. För övrigt, förutom ligaturer av typen Æ finns det bokstäver som skrivs med flera tecken. Så i det tjeckiska alfabetet finns bokstaven Ch, som ligger mellan H och I.

Förutom skillnader i alfabeten finns det även andra nationella traditioner som påverkar sorteringen. Särskilt uppstår frågan: i vilken ordning bör ord bestående av versaler och gemener följa i ordboken? Även punktering kan påverka sorteringen. På spanska sätts en omvänd frågetecken i början av en fråga (¿Te gusta la música?). I detta fall är det uppenbart att frågande meningar inte bör grupperas i en egen kluster utanför alfabetet, men hur bör man sortera strängar med andra skiljetecken?

Jag kommer inte att gå in på sorteringen av strängar i språk som skiljer sig kraftigt från europeiska. Jag nämner att i språk med skrivriktningar från höger till vänster eller ovanifrån och ner, lagras tecknen i strängar förmodligen i läsordning, och även i icke-alphabetiska skriftsystem finns det sina egna sätten att ordna tecken för tecken. Till exempel kan hieroglyfer ordnas efter skrivsätt (nycklar för kinesiska tecken) eller efter uttal. Hur emoticons bör ordnas, kan jag ärligt talat inte föreställa mig, men även för dem kan något utarbetas.

Baserat på ovanstående egenskaper har de grundläggande kraven för jämförelse av strängar baserade på Unicode-tabeller formulerats:

• strängjämförelser är oberoende av tecknens position i kodtabellen;
• sekvenser av tecken som bildar ett enskilt tecken omvandlas till kanonisk form (A + den övre cirkeln är detsamma som Å);
• vid strängjämförelse betraktas tecken i kontexten av strängen och, om det är nödvändigt, kombineras med grannarna till en enhet för jämförelse (Ch i tjeckiska) eller delas upp i flera (Æ på franska);
• Alla nationella egenskaper (alfabet, versaler/gemener, skiljetecken, skriftspråkets ordning) bör kunna anpassas, ända ner till manuell tilldelning av ordning (emojier);
• Jämförelse är viktigt inte bara för sortering utan också på många andra ställen, till exempel för att ange radräckor (ersättning {A… я} i bash);
• Jämförelsen bör utföras tillräckligt snabbt.

Dessutom har författarna till rapporten formulerat egenskaper för jämförelse som algoritmutvecklare inte bör förlita sig på:

• Jämförelsealgoritmen bör inte kräva en separat uppsättning tecken för varje språk (ryska och ukrainska använder gemensamt majoriteten av kyrilliska tecken);
• Jämförelse bör inte bygga på tecknens ordning i Unicode-tabeller;
• Strängens vikt ska inte vara en egenskap hos strängen, eftersom samma sträng i olika kulturella sammanhang kan ha olika vikter;
• Vikterna för strängar kan förändras vid sammanslagning eller delning (från x < y Det betyder inte att xz < yz);
• Olika strängar som har samma vikt betraktas som lika från algoritmens sorteringssynpunkt. Att införa ytterligare ordning för sådana strängar är möjligt, men det kan försämra prestandan;
• Vid upprepade sorteringar kan strängar med samma vikt byta plats. Stabilitet är en egenskap hos en specifik sorteringsalgoritm, inte en egenskap hos en strängjämförelsealgoritm (se föregående punkt);
• Sorteringsregler kan förändras över tid i takt med att kulturella traditioner förtydligas/förändras.

Det konstateras också att jämförelsealgoritmen inte känner till semantiken hos de bearbetade strängarna. Så, strängar som endast består av siffror bör inte jämföras som tal, och i listor över engelska namn bör artikeln inte tas bort (Beatles, The).

För att uppfylla alla angivna krav föreslås en flernivå (faktiskt fyrnivå) tabellsorteringsalgoritm.

I förväg omvandlas tecknen i strängen till kanonisk form och grupperas i jämförelseenheter. Varje jämförelseenhet tilldelas flera vikter som motsvarar flera nivåer av jämförelse. Vikterna för jämförelseenheterna är element i ordnade mängder (i detta fall heltal) som kan jämföras som större eller mindre. Speciellt värde IGNORED (0x0) innebär att enheten i fråga inte deltar i jämförelsen på den aktuella nivå som jämförs. Strängjämförelser kan upprepas flera gånger med hjälp av vikter för de aktuella nivåerna. Vid varje nivå jämförs vikterna för jämförelseenheterna i de två strängarna med varandra.

I olika implementationer av algoritmen för olika nationella traditioner kan koefficientvärdena skilja sig, men standarden Unicode innehåller en grundläggande vikt-tabell — "Standard Unicode Collation Element Table" (DUCET). Jag vill påpeka att installationen av variabeln LC_COLLATE faktiskt är en indikation på valet av vikt-tabellen i strängjämförelsefunktionen.

Viktkoefficienterna DUCET är ordnade på följande sätt:

• på första nivån konverteras alla bokstäver till samma fall, diakritiska tecken avvisas, och skiljetecken (inte alla) ignoreras;
• på andra nivån beaktas endast diakritiska tecken;
• på tredje nivån beaktas endast fallet;
• på fjärde nivån beaktas endast skiljetecken.

Jämförelsen sker i flera genomgångar: först jämförs koefficienterna på första nivån; om vikterna stämmer överens, sker en upprepning av jämförelsen med vikterna på andra nivån; följt av kanske tredje och fjärde.

Jämförelsen avslutas när det finns motsvarande jämförelseenheter med olika vikter i strängerna. Strängar med lika vikter på alla fyra nivåerna anses vara lika.

Denna algoritm (med massor av ytterligare tekniska detaljer) gav namn åt rapport nr 10 — "Unicode Collation Algorithm" (UCA).

Vid denna punkt blir sorteringsbeteendet i vårt exempel något mer begripligt. Det vore bra att jämföra det med standarden Unicode.

För att testa implementationerna UCA finns det ett speciellt test, som använder en vikt-fil, implementerar DUCET. I vikt-filen kan man hitta olika roliga detaljer. Till exempel finns där ordningen för mahjongbrickor och europeiskt domino, samt ordningen för färger i en kortlek (symbol 1F000 och så vidare). Kortfärgerna är placerade enligt bridge-reglerna — PCHBT, och korten i varje färg — i ordningen T,2,3… K.

Manuell kontroll av korrektheten i sorteringen av strängar enligt DUCET skulle vara ganska uttröttande, men lyckligtvis för oss finns det en exemplariskt genomförd implementation av biblioteket för att arbeta med Unicode — "International Components for Unicode" (ICU).

På webbplatsen för detta bibliotek, utvecklat av IBM, finns demonstrationssidor, inklusive sidan för strängjämförelsealgoritmen. Vi matar in våra teststrängar med standardinställningar och, åh under, får en perfekt rysk sortering.

Abakanov Michail;målare
Jolkina Ella;kranförare
Ivanov Andrej;svetsare
Ivanova Alla;advokat

Förresten, på webbplatsen ICU kan man hitta en förtydligande av hur algoritmen för jämförelse fungerar vid hantering av skiljetecken. I exempel Collation FAQ ignoreras apostrof och bindestreck.

Unicode hjälpte oss, men att leta efter orsakerna till det konstiga beteendet sort på Linux kommer vi att behöva göra någon annanstans.

Sortering i glibc

En snabb titt på källkoderna för verktyget sort från GNU Core Utils visade att lokalisering i själva verktyget handlar om att skriva ut det nuvarande värdet av variabeln LC_COLLATE vid körning i felsökningsläge:

$ sort --debug buhg.txt > buhg.srt
sort: använder 'en_US.UTF8' sorteringsregler

Strängjämförelse görs av den standardiserade funktionen strcoll, vilket innebär att allt intressant finns i biblioteket glibc.

På wiki projektet glibc strängjämförelse ägnas ett stycke. Av detta stycke kan man förstå att i glibc sorteringen baseras på den redan kända algoritmen UCA (The Unicode collation algorithm) och/eller den närstående standarden ISO 14651 (Internationell strängordning och -jämförelse). Angående den senaste standarden bör nämnas att den på webbplatsen standards.iso.org ISO 14651 officiellt har utlysts offentlig, men den tillhörande länken leder till en icke-existerande sida. Google visar 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-fjärde sidan av sökresultatet finns även direkta länkar till PDF. Över lag skiljer sig standarden praktiskt taget inte från UCA, men den är tråkigare att läsa eftersom den inte innehåller tydliga exempel på nationella särdrag i strängsortering.

Den mest intressanta informationen på wiki var en länk till buggrapporten som diskuterar implementeringen av strängjämförelse i glibc. Från diskussionen kan man förstå att i glibc för strängjämförelse används ISOett tabellformat The Common Template Table (CTT), vars adress kan hittas i bilagan A till standarden ISO 14651. Mellan 2000 och 2015 var denna tabell i glibc hade ingen förvaltare och skilde sig ganska mycket (åtminstone utseendemässigt) från den aktuella standardversionen. Från 2015 till 2018 genomgick den anpassning till den nya tabellen och just nu har du en chans att möta både den nya tabellen (CentOS 8), samt den gamla (CentOS 7).

Nu när vi har all information om algoritmen och hjälp-tabellerna kan vi återvända till det ursprungliga problemet och förstå hur man korrekt sorterar strängar i rysk lokal.

ISO 14651/14652

Källkoden för den tabell vi är intresserade av CTT finns i de flesta distributioner Linux i katalogen /usr/share/i18n/locales/. Själva tabellen finns i filen iso14651_t1_common. Sedan inkluderas denna fil med direktivet copy iso14651_t1_common i filen iso14651_t1, som i sin tur inkluderas i nationella filer, inklusive en_US och ru_RU. I de flesta distributioner Linux ingår alla källfiler i den grundläggande installationen, men om de inte finns, måste du installera ett extra paket från distributionen.

Strukturen på filen iso14651_t1 kan tyckas vara fruktansvärt ordig, med oklara regler för namnens uppbyggnad, men om man begriper sig på det är allt ganska enkelt. Strukturen beskrivs i standarden ISO 14652, en kopia av vilken kan laddas ner från sidan open-std.org. En annan beskrivning av filformatet kan läsas i specifikationerna POSIX från OpenGroup. Som ett alternativ till att läsa standarden kan man studera källkoden för funktionen collate_read på glibc/locale/programs/ld-collate.c.

Filens struktur ser ut som följer:

Som standard används symbolen som en escape-symbol, och slutet av en rad efter symbolen # är en kommentar. Båda symbolerna kan åsidosättas, vilket har gjorts i den nya versionen av tabellen:

escape_char /
comment_char %

I filen förekommer det token i formatet <Uxxxx> eller <Uxxxxxxxx> (där x — är en hexadecimalt siffra). Detta är den hexadecimala representationen av Unicode-kodpunkter i kodningen UCS-4 (UTF-32). Alla andra element i vinkelparenteser (inklusive <Uxxxx_xxxx>, <2> och liknande), betraktas som vanliga strängkonstanter som saknar särskild betydelse utanför kontext.

Sträng LC_COLLATE berättar för oss att datan som beskriver strängjämförelserna börjar här.

Först anges namn för vikterna i jämförelse tabellen och namn för kombinationerna av tecken. Generellt tillhör de två namntyperna två olika entiteter, men i den verkliga filen är de blandade. Namnen på vikterna anges med nyckelordet sorteringssymbol (sorteringssymbol), eftersom Unicode-symboler med samma vikt kommer att betraktas som jämförbara symboler.

Den totala längden på sektionen i den nuvarande versionen av filen är cirka 900 rader. Jag har tagit exempel från flera ställen för att visa slumpmässigheten i namnen och några typer av syntax.

LC_COLLATE

sorteringssymbol 
sorteringssymbol 
sorteringssymbol 
sorteringssymbol 
...
sorteringssymbol 
sorteringssymbol 
sorteringssymbol 
...
sorteringssymbol ..
sorteringssymbol  % Garanterat största symbolvärdet. Behåll i slutet av denna lista
...
sorteringselement  från ""
sorteringselement  från ""

• sorteringssymbol registrerar sträng OSMANYA i viktens namn tabell
• sorteringssymbol .. registrerar en sekvens av namn som består av ett prefix S och ett hexadecimalt nummer suffix från 1D000 till 1D35F.
• FFFF på sorteringssymbol ser ut som ett stort osignerat heltal i hexadecimalt format, men <SFFFF> är bara ett namn som skulle kunna se ut som <VERYBIGVAL>
• namn <U0413> betyder kodpunkt i kodningen UCS-4
• sorteringselement från "" registrerar ett nytt namn för paret av Unicode-punkter.

När vikterna har definierats sätts de faktiskt vikterna. Eftersom endast förhållandet mellan större och mindre spelar roll i jämförelsen, bestäms vikterna av en enkel sekvens av namn. De "lättare" vikterna listas först, följt av de "tyngre". Jag påminner om att varje Unicode-symbol tilldelas fyra olika vikter. Här sammanställs de i en enhetlig ordnad sekvens. Teoretiskt kan vilket symboliskt namn som helst användas på vilket av de fyra nivåerna som helst, men kommentarer visar att utvecklarna mentalt uppdelar namnen efter nivåer.

% Symboliska viktfördelningar

% Tredje nivå viktfördelningar




...
% Andra nivå viktfördelningar

 % KOMBINERANDE LÅG LINJE
 % KOMBINERANDE KOMMA OCH ÖVER
 % KOMBINERANDE ÅTERVÄND KOMMA OCH ÖVER
...
% Första nivå viktfördelningar
 % HORIZONTAL TABULATION
 % LINJEBREAK
 % VERTIKAL TABULERING
...
 % CYRILLIC LITTLE LETTER DE
 % CYRILLIC LITTLE LETTER KOMI DE
 % CYRILLIC LITTLE LETTER DJE
 % CYRILLIC LITTLE LETTER KOMI DJE
 % CYRILLIC LITTLE LETTER GJE
 % CYRILLIC LITTLE LETTER ZE WITH DESCENDER
 % CYRILLIC LITTLE LETTER IE
 % CYRILLIC LITTLE LETTER IE WITH BREVE
 % CYRILLIC LITTLE LETTER UKRAINIAN IE
 % CYRILLIC LITTLE LETTER ZHE

Slutligen, själva vikt-tabellen.

Viktsektionen är innesluten i rader med nyckelord order_start och order_end. Ytterligare parametrar order_start bestämmer i vilken riktning raderna visas på varje jämförelse nivå. Som standard används parametern framåt. Kroppen av sektionen består av rader som innehåller teckenkod och fyra av dess vikter. Teckenkoden kan representeras av själva tecknet, kodpunkten eller det symboliska namnet som definierats tidigare. Vikterna kan också anges med symboliska namn, kodpunkter eller själva tecknen. Om kodpunkter eller tecken används, kommer deras vikt att motsvara det numeriska värdet av kodpunkten (positionen i Unicode-tabellen). Tecken som inte anges tydligt (såvitt jag förstår) anses tilldelade i tabellen med en primär vikt motsvarande positionen i Unicode-tabellen. Det speciella viktvärdet IGNORE betyder att detta tecken ignoreras på den aktuella jämförelsenivån.

För att demonstrera vikternas struktur har jag valt tre ganska uppenbara fragment:

• tecken som helt ignoreras
• tecken som är likvärdiga med siffran tre på de första två nivåerna
• början av det kyrilliska alfabetet, som inte innehåller diakritiska tecken, och därför sorteras främst efter första och tredje nivåerna.

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

Nu kan vi återgå till sorteringen av exemplen från början av artikeln. Fällan ligger just i denna del av vikt-tabellen:

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

Det är tydligt att i denna tabell är interpunktionställen från tabellen ASCII (inklusive mellanslag) vid jämförelse av strängar nästan alltid ignoreras. Undantaget utgörs av strängar som överensstämmer helt, förutom interpunktion som förekommer på matchande positioner. Strängarna i mitt exempel (efter sortering) ser ut så här för jämförelsealgoritmen:

AbakanovMihailmålare
JolkinaEllaKranskär
IvanovaAllaMålare
IvanovAndreiSmed

Med tanke på att stora bokstäver i ryska språket i vikt-tabellen kommer efter små bokstäver (på tredje nivån <CAP> tyngre än <MIN>), ser sorteringen helt korrekt ut.

Vid inställd variabel LC_COLLATE=C laddas en särskild tabell som anger 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'fe', L'xff'
};

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

Text- och binära tabeller

Det är uppenbart att strängjämförelse är en mycket vanlig operation, medan tolkning av tabellen CTT är en relativt kostsam procedur. För att optimera åtkomsten till tabellen kompileras den till binär form av kommandot localedef.

Team localedef tar emot som parametrar en fil med nationella särdrag (alternativ -i), där alla tecken representeras av Unicode-punkter, och en fil med överensstämmelse mellan Unicode-punkter och tecken i en specifik kodning (alternativ -f). Som resultat av processen skapas binärfiler för lokalinställningen, namnet som anges i den sista parametern.

Glibc stödjer två format för binära filer: "traditionellt" och "modernt".

Det traditionella formatet innebär att lokalinställningens namn är namnet på underkatalogen i /usr/lib/locale/. I denna underkatalog lagras binärfiler LC_COLLATE, LC_CTYPE, LC_TIME och så vidare. Filen LC_IDENTIFICATION innehåller det formella namnet på lokalinställningen (som kan skilja sig från katalognamnet) och kommentarer.

Det moderna formatet förutsätter att alla lokalinställningar lagras i ett enda arkiv /usr/lib/locale/locale-archive, vilket avbildas i det virtuella minnet för alla processer som använder glibc. Namnet på lokal i modern form genomgår viss kanonisering – endast siffror och bokstäver i små bokstäver kvarstår i kodningens namn. Så ru_RU.KOI8-R, sparas som ru_RU.koi8r.

Ingångsfiler söks i den aktuella katalogen, samt i kataloger /usr/share/i18n/locales/ och /usr/share/i18n/charmaps/ för filer CTT och kodningsfiler respektive.

Till exempel, kommandot

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

kompilerar filen /usr/share/i18n/locales/ru_RU med hjälp av kodningsfilen /usr/share/i18n/charmaps/MAC-CYRILLIC.gz och sparar resultatet i /usr/lib/locale/locale-archive under namnet ru_RU.maccyrillic

Om du sätter variabeln LANG=en_US.UTF-8 då glibc kommer den att leta efter binärfiler för lokal i följande ordning 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 lokal förekommer både i traditionell och modern form, ges prioritet till den moderna.

För att visa listan över kompilerade lokaler kan kommandot locale -a.

Förbereda sin egen sorteringstabell

Nu, beväpnad med kunskap, kan du skapa din egen perfekta sorteringstabell för strängar. Denna tabell ska korrekt jämföra ryska bokstäver, inklusive bokstaven Ё, och ta hänsyn till skiljetecken enligt tabellen ASCII.

Processen för att förbereda sin egen sorteringstabell består av två steg: redigering av vikt-tabellen och kompilerande av den i binär form med kommandot localedef.

För att justera sorteringstabellen med minimal redigeringskostnad, finns det sektioner för justering av vikter i det befintliga formatet. ISO 14652 Sektionen börjar med nyckelordet reorder-after och anvisningen av positionen, efter vilken ersättningen görs. Sektionen avslutas med raden reorder-end. Om du behöver justera flera avsnitt av tabellen, skapas en sektion för varje sådant avsnitt.

Jag kopierade nya versioner av filerna iso14651_t1_common och ru_RU från arkivet glibc till min hemkatalog ~\/ .local\/share\/i18n\/locales\/ och gjorde några små ändringar i avsnittet LC_COLLATE på ru_RU. De nya versionerna av filerna är helt kompatibla med min version glibc. Om du vill använda äldre versioner av filer, måste du ändra de symboliska namnen och den plats där ersättningen börjar i tabellen.

LC_COLLATE
% Kopiera mallen från ISO/IEC 14651
kopiera "iso14651_t1"
ordna-efter 
 ;;; % MELLANSPEL
 ;;; % UTTALSMÄRKE
 ;;; % CITATMÄRKE
...
 ;;; % HÖGER KLAMMERT
 ;;; % TILDE
ordna-slut
SLUT LC_COLLATE

Faktiskt borde jag ha bytt ut fälten i LC_IDENTIFICATION så att de pekade på lokaliteten ru_MY, men i mitt exempel behövdes inte det, eftersom jag uteslöt från att söka lokalarkivet locale-archive.

För att localedef fungerade med filer i min mapp via variabeln I18NPATH kan du lägga till en extra katalog för att söka ingångsfiler, och katalogen för att spara binära filer kan anges som en vä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 LANG kan skriva absoluta vägar till kataloger med lokalfiler som börjar med snedstreck, men glibc på Linux alla vägar anses från basmappen, som kan överskrivas genom variabeln LOCPATH. Efter att ha installerat LOCPATH=~/.local/lib/locale/ kommer alla filer relaterade till lokalisering att sökas endast i min mapp. Arkivet med lokaliteter kommer att ignoreras när den inställda variabeln LOCPATH är inställd.

Här är det avgörande testet:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Michail;målare
Jolkina Ella;kranoperatör
Ivanov Andrej;svetsare
Ivanova Alla;advokat

Upp med humöret! Vi gjorde det!

Arbeta med felen

Jag har redan besvarat frågorna om sortering av strängar som ställdes i början, men det finns fortfarande några frågor om fel - synliga och osynliga.

Låt oss återvända till den ursprungliga uppgiften.

Och programmet sort och programmet join använder samma strängjämförelsefunktioner från glibc. Hur kom det sig att join gav ett sorteringsfel på strängar sorterade av kommandot sort i lokaliteten en_US.UTF-8? Ответ прост: sort jämför hela strängen, medan join bara jämför nyckeln, som som standard är början av strängen fram till den första blankstegssymbolen. I mitt exempel ledde detta till ett felmeddelande eftersom sorteringen av de första orden i strängarna inte stämde överens med sorteringen av hela strängar.

Lokalitet "C" garanterar att de sorterade raderna innehåller de inledande delsträngarna fram till det första mellanslaget sorterade, men det döljer bara ett fel. Det går att hitta sådana data (människor med samma efternamn men olika förnamn) som utan felmeddelande skulle ge ett felaktigt resultat vid sammanslagning av filer. Om vi vill att join sammanslå rader från filer baserat på namn, så är den rätta metoden att uttryckligen ange fältseparatorn och sortera efter nyckelfältet, istället för hela raden. I detta fall kommer sammanslagningen att ske korrekt och det kommer inte att uppstå 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

Ett exempel som har körts framgångsrikt i en kodning CP1251 har också ett annat fel. Faktum är att i alla kända distributioner Linux finns det ingen kompilerad lokal i paketen ru_RU.CP1251. Om den kompilerade lokalen inte hittas, så sort använder den tyst byte-för-byte jämförelse, vilket vi just observerade.

Förresten finns det en annan liten bugg relaterad till avsaknaden av kompilerade lokaler. Kommando LOCPATH=/tmp locale -a visar en lista över alla lokaler i locale-archive, men med den inställda variabeln LOCPATH är dessa lokaler otillgängliga för alla program (inklusive själva locale).

$> LOCPATH=/tmp locale -a | grep en_US
locale: Kan inte ställa in LC_CTYPE till standardlokal: Ingen sådan fil eller katalog
locale: Kan inte ställa in LC_MESSAGES till standardlokal: Ingen sådan fil eller katalog
locale: Kan inte ställa in LC_COLLATE till standardlokal: Ingen sådan fil eller katalog
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: använder 'en_US.UTF-8' sorteringsregler

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: använder enkel byte-jämförelse

Slutsats

Om du är en programmerare som är van vid att betrakta strängar som en uppsättning bytes, så är ditt val LC_COLLATE=C.

Om du är lingvist eller ordboksförfattare, så är det bäst att kompilera din egen lokal.

Om du är en vanlig användare, så behöver du bara vänja dig vid att kommandot ls -a returnerar filer som börjar med en punkt, blandat med filer som börjar med en bokstav, och Midnight Commander, som använder sina interna funktioner för att sortera namn, placerar filer som börjar med en punkt i början av listan.

Länkar

Rapport nr 10 Unicode sorteringsalgoritm

Vikt av tecken på unicode.org

ICU – implementation av ett bibliotek för att hantera Unicode från IBM.

Sorteringstest med hjälp av ICU

Vikt av tecken i ISO 14651

Beskrivning av filformatet med vikter ISO 14652

Diskussion om strängjämförelse i glibc

Källa: habr.com