Introduktion

Det hele begyndte med et kort script, der skulle kombinere oplysninger om adresser e-mail fra medarbejdere, indsamlet fra en liste over brugere i nyhedsbrevet, med medarbejdernes stillinger, der blev hentet fra HR-databasen. Begge lister blev eksporteret til tekstfiler i Unicode-kodning UTF-8 og gemt med Unix-linjeskift.

Indhold. mail.txt

Ivanov Andrei;ia@example.com

Indhold. buhg.txt

Ivanova Alla;maler
Elkina Ella;kranfører
Ivanov Andrei;smed
Abakanov Mikhail;maler

For at kombinere blev filerne sorteret med Unix-kommandoen sort og givet som input til et Unix-program sammenføje, som uventet afsluttede med en fejl:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Ivanov Andrei;smed

En visuel gennemgang af sorteringsresultatet viste, at sorteringen generelt var korrekt, men i tilfælde af matchende mandlige og kvindelige efternavne kom de kvindelige før de mandlige:

$> sort buhg.txt
Abakanov Mikhail;maler
Elkina Ella;kranfører
Ivanova Alla;maler
Ivanov Andrei;smed

Det ser ud som en fejl i Unicode-sorteringen eller som en indikator for feminisme i sorteringsalgoritmen. Førstnævnte lyder selvfølgelig mere sandsynligt.

Lad os udskyde det for nu sammenføje og fokusere på sort. Lad os prøve at løse problemet ved hjælp af trial and error. Først skifter vi lokaliteten fra en_US og få en fungerende kommando. ru_RU. For sorteringen ville det have været tilstrækkeligt at indstille miljøvariablen LC_COLLATE, men vi vil ikke være smålige:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;maler
Elkina Ella;kranfører
Ivanova Alla;maler
Ivanov Andrei;smed

Der ændrede sig ikke noget.

Lad os prøve at re-kode filerne til en enbyte-kodning:

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

Igen ændrede der sig ikke noget.

Der er ikke meget at gøre, vi må søge løsningen på internettet. Der er ikke meget specifikt om russiske efternavne, men der er spørgsmål om andre mærkelige sorteringer. For eksempel dette problem: unix sort behandler ‘-‘ (bindestreg) tegn som usynlige. Kort sagt, sorteringerne "a-b", "aa", "ac" sorteres som "aa", "a-b", "ac".

Svaret er overalt standard: brug programmeringslokaliteten "C" og du vil være lykkelig. Vi prøver:

$> LANG=C sort buhg.txt
Elkina Ella;kranfører
Abakanov Mikhail;maler
Ivanov Andrei;smed
Ivanova Alla;advokat

Noget har ændret sig. Ivanov-familien er nu i den korrekte rækkefølge, men Elkina er forsvundet et eller andet sted. Lad os vende tilbage til den oprindelige opgave:

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

Det fungerede uden fejl, som internettet lovede. Og det på trods af Jolkin i den første linje.

Problemet ser ud til at være løst, men for en sikkerheds skyld vil vi prøve endnu en russisk kodning — Windows-versionen. CP1251:

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

Resultatet af sorteringen vil, underligt nok, være det samme som lokaliteten. "C", og hele eksemplet vil derfor gå igennem uden fejl. En eller anden mystik.

Jeg er ikke glad for mystik i programmering, da den normalt skjuler fejl. Jeg må tage spørgsmålet alvorligt om, hvordan det fungerer sort og hvad det påvirker LC_COLLATE .

Til slut vil jeg forsøge at svare på spørgsmålene:

hvorfor kvindelige efternavne blev sorteret forkert
hvorfor LANG=ru_RU.CP1251 vist sig at være ækvivalent med LANG=C
hvorfor har sort og sammenføje forskellige opfattelser af rækkefølgen af de sorterede strenge
hvorfor der er fejl i alle mine eksempler
endelig, hvordan man sorterer strenge efter egen smag

Sortering i Unicode

Den første stop vil være den tekniske rapport nr. 10 med titlen Unicode collation algorithm hjemmeside unicode.org. Rapporten indeholder mange tekniske detaljer, så jeg tillader mig at give et kort resumé af hovedideerne.

Sammenligning — "sammenligning" af strenge — er grundlaget for enhver sorteringsalgoritme. Selve algoritmerne kan variere ("boblesortering", "samling", "hurtig"), men alle bruger sammenligning af par af strenge for at bestemme rækkefølgen af dem.

Sortering af strenge på naturligt sprog er et ret komplekst problem. Selv i de enkleste en-byte-kodninger vil rækkefølgen af bogstaverne i alfabetet, som i et eller andet omfang adskiller sig fra det engelske alfabet, ikke længere stemme overens med rækkefølgen af de numeriske værdier, som disse bogstaver kodes. Så i det tyske alfabet ligger bogstavet Ö mellem O og P, og i kodningen CP850 falder det mellem ÿ og Ü.

Man kan forsøge at abstrahere fra den specifikke kodning og betragte "ideelle" bogstaver, der er placeret i en eller anden rækkefølge, som det gøres i Unicode. Kodningerne UTF8, UTF16 eller en-byte KOI8-R (hvis en begrænset delmængde af Unicode er nødvendig) vil give forskellige numeriske repræsentationer af bogstaverne, men referere til de samme elementer i den grundlæggende tabel.

Det viser sig, at selvom vi bygger en tegn tabel fra bunden, kan vi ikke tildele en universel rækkefølge af tegnene. I forskellige nationale alfabetter, der bruger de samme bogstaver, kan rækkefølgen af disse bogstaver variere. For eksempel i fransk Æ vil blive betragtet som en ligatur og sorteres som en streng. AEI det norske sprog Æ vil være et separat bogstav, der kommer efter Z. For øvrigt findes der udover ligaturer af typen Æ bogstaver, der skrives med flere tegn. Så i det tjekkiske alfabet er der et bogstav Ch, som står mellem i giver ikke andre deltagere mulighed for at genskabe den private komponent og I.

Udover forskelle i alfabetterne findes der også andre nationale traditioner, der påvirker sorteringen. Særligt opstår spørgsmålet: i hvilken rækkefølge skal ord bestående af store og små bogstaver følge i ordbogen? Derudover kan brugen af tegnsætningssymboler påvirke sorteringen. I spansk sættes der et omvendt spørgsmålstegn i begyndelsen af spørgende sætninger (¿Te gusta la música?). I dette tilfælde er det åbenlyst, at spørgende sætninger ikke bør grupperes i en separat klynge uden for alfabetet, men hvordan sorteres strenge med andre tegnsætningssymboler?

Jeg vil ikke dvæle ved sortering af strenge i sprog, der er meget forskellige fra europæiske. Jeg bemærker, at i sprog med skriftsretning fra højre mod venstre eller oppefra og ned, opbevares tegnene i strenge sandsynligvis i læserækkefølge, og selv i ikke-alfabetiske skriftformer er der måder at ordne strenge på tegn for tegn. For eksempel kan hieroglyffer sorteres efter stregtype (nøgler til kinesiske hieroglyffer) eller efter udtale. Hvordan emojis skal sorteres, ved jeg ærligt talt ikke, men der kan sikkert findes en løsning til dem også.

Baseret på de ovenfor nævnte karakteristika er de grundlæggende krav til sammenligning af strenge, der er baseret på Unicode-tabeller, blevet formuleret:

sammenligning af strenge er uafhængig af tegnenes placering i kodetabellen;
sekvenser af tegn, der udgør et enkelt tegn, bringes til en kanonisk form (A + den øverste cirkel er det samme som Å);
); ved sammenligning af strenge betragtes et tegn i konteksten af strengen og, hvis nødvendigt, sammenføjes med naboer til en enhed til sammenligning (Ch i tjekkisk) eller opdeles i flere (Æ i fransk);
alle nationale egenskaber (alfabet, versaler / minuskler, tegnsætning, rækkefølge af skriftsystemer) skal kunne justeres helt ned til manuel tildeling af rækkefølge (emoji);
sammenligning er vigtig ikke kun for sortering, men også på mange andre steder, for eksempel til at angive rækkevidder for strenge (substitution {A… я} i bash);
sammenligningen skal udføres hurtigt nok.

Derudover formulerede rapportforfatterne de egenskaber ved sammenligning, som algoritmeudviklerne ikke bør stole på:

sammenligningsalgoritmen bør ikke kræve et separat tegnsæt for hvert sprog (russisk og ukrainsk bruger fælles de fleste kyrilliske tegn);
sammenligningen må ikke bygge på rækkefølgen af tegn i Unicode-tabeller;
værdien af en streng må ikke være et attribut for strengen, da den samme streng i forskellige kulturelle kontekster kan have forskellige værdier;
strengeværdier kan ændre sig ved sammenlægning eller opdeling (fra x < y det betyder ikke, at xz < yz);
forskellige strenge, der har de samme værdier, betragtes som lige i algoritmen for sortering. Introduktion af ekstra rækkefølge for sådanne strenge er muligt, men det kan forringe ydeevnen;
ved gentagne sorteringer kan strenge med de samme værdier skifte pladser. Stabilitet er en egenskab ved den specifikke sorteringsalgoritme, ikke en egenskab ved strængesammenligningsalgoritmen (se det forrige punkt);
sorteringsreglerne kan ændre sig over tid, efterhånden som kulturelle traditioner præciseres / ændres.

Det er også specificeret, at sammenligningsalgoritmen ikke har nogen viden om semantikken for de behandlede strenge. Så, strenge bestående kun af cifre må ikke sammenlignes som tal, og i lister over engelske navne må artiklen ikke fjernes (Beatles, The).

For at imødekomme alle de angivne krav er der foreslået en flerlag (faktisk firelags) tabelsorteringsalgoritme.

Forudgående bliver tegnene i strengen konverteret til kanonisk form og grupperet i sammenligningsenheder. Hver sammenligningsenhed tildeles flere vægte, som svarer til flere niveauer af sammenligning. Vægtene for sammenligningsenhederne er elementer i ordnede mængder (i dette tilfælde hele tal), som kan sammenlignes som større eller mindre. Specialværdien IGNORED (0x0) betyder, at den pågældende enhed ikke deltager i sammenligningen på det relevante niveau. Sammenligning af strenge kan gentages flere gange ved brug af vægte for de relevante niveauer. På hvert af niveauerne sammenlignes vægtene for enhederne i de to strenge sekventielt med hinanden.

I forskellige implementeringer af algoritmen kan koefficienterne variere afhængigt af nationale traditioner, men den grundlæggende vægt-tabel indgår i Unicode-standardsættet — "Default Unicode Collation Element Table" (DUCET). Jeg vil bemærke, at indstillingen af variablen LC_COLLATE faktisk er en angivelse af valget af vægt-tabel i sammenligningsfunktionen.

Vægtniveauerne DUCET er opbygget som følger:

på det første niveau gøres alle bogstaver til samme skriftform, diakritiske tegn kasseres, og tegnsætning (ikke alle) ignoreres;
på det andet niveau tages kun diakritiske tegn i betragtning;
på det tredje niveau tages kun skriftform i betragtning;
på det fjerde niveau tages kun tegnsætning i betragtning.

Sammenligningen foregår i flere gennemgange: først sammenlignes vægtene på første niveau; hvis vægtene stemmer overens, foretages der en ny sammenligning med vægtene på andet niveau; derefter eventuelt tredje og fjerde.

Sammenligningen afsluttes, når der findes matchende enheder med forskellige vægte i strenge. Strenge med ligelige vægte på alle fire niveauer betragtes som identiske.

Denne algoritme (med en masse ekstra tekniske detaljer) gav navn til rapport nr. 10 — "Unicode Collation Algorithm" (UCA).

Her bliver sorteringsadfærden fra vores eksempel lidt mere forståelig. Det ville være godt at sammenligne det med Unicode-standarden.

Til test af implementeringer UCA er der en særlig test, der bruger en vægtfil, der implementerer DUCET. I vægtfilen kan man finde forskellige sjove ting. For eksempel findes der rækkefølgen af mahjong-brikker og europæisk dominospil samt rækkefølgen af farver i et kortspil (symbol 1F000 og videre). Kortfarverne er arrangeret efter bridge-reglerne — HJDBT, og kortene i hver farve — i rækkefølgen 10, 2, 3... K.

Manuel kontrol af korrektheden af sorteringen af strenge i henhold til DUCET ville være ret trættende, men heldigvis for os findes der et fremragende implementering af en bibliotek til arbejde med Unicode - "International Components for Unicode" (ICU).

På hjemmesiden til dette bibliotek, udviklet i IBM, er der demonstrationssider, herunder siden for stræng sammenligning algoritme. Vi indtaster vores teststrenge med standardindstillingerne, og miraklet, vi får den perfekte russiske sortering.

Abakanov Mikhail;maler
Yolkina Ella;kranfører
Ivanov Andrey;vvs'er
Ivanova Alla;advokat

Forresten, på hjemmesiden ICU kan du finde præciseringen af algoritmens arbejde med hensyn til behandling af tegnsætning. I eksemplerne Collation FAQ ignoreres apostrof og bindestreg.

Unicode hjalp os, men vi må lede efter årsagerne til den mærkelige opførsel sort i Linux et andet sted.

Sortering i glibc

En hurtig gennemgang af kildekoden til værktøjet sort af GNU Core Utils viste, at i selve værktøjet lokaliseres, når den aktuelle værdi af variablen LC_COLLATE startes i fejlsøgningsmodus:

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

Sammenligning af strenge udføres af standardfunktionen strcoll, og alt det interessante findes i biblioteket glibc.

På wiki projektet glibc er der et afsnit dedikeret til sammenligning af strenge . Fra dette afsnit kan man forstå, at ibaserer sorteringen sig på den allerede kendte algoritme glibc The Unicode collation algorithm UCA () og/eller på en nært beslægtet standardISO 14651 International string ordering and comparison (). Om den sidste standard skal bemærkes, at den på hjemmesidenstandards.iso.org officielt er erklæret offentligt tilgængelig, men det relevante link fører til en ikke-eksisterende side. Google viser flere sider med links til officielle websteder, der tilbyder at købe en elektronisk kopi af standarden for et par hundrede euro, men på den tredje-fjerde side af søgeresultatet findes der direkte links til International string ordering and comparison . Alt i alt adskiller standarden sig ikke væsentligt fra PDF, men det er mere kedeligt at læse, da den ikke indeholder markante eksempler på nationale særtræk i stræns sortering. UCADen mest interessante information på

var linket til wiki bugtracker med diskussionen om implementeringen af stræng sammenligning i . Fra diskussionen kan man lære, at i glibcbruges glibc den fælles tabel ISOThe Common Template Table CTT (), hvis adresse kan findes i bilagettil standarden A . Mellem 2000 og 2015 var denne tabel i International string ordering and comparison. Mellem 2000 og 2015 var denne tabel i glibc var ikke en maintainer og adskilte sig meget (i det mindste visuelt) fra den nuværende standardversion. Fra 2015 til 2018 blev der arbejdet på tilpasning til den nye version af tabellen, og i øjeblikket har du mulighed for at møde både den nye version af tabellen (CentOS 8), såvel som den gamle (CentOS 7).

Nu hvor vi har al information om algoritmen og hjælpe-tabellerne, kan vi vende tilbage til det oprindelige problem og forstå, hvordan man korrekt sorterer strenge i den russiske lokalitet.

ISO 14651/14652

Kilden til den tabel, vi er interesseret i ), hvis adresse kan findes i bilaget findes i de fleste distributioner Linux i mappen /usr/share/i18n/locales/. Selve tabellen findes i filen iso14651_t1_common. Derefter inkluderes denne fil med direktivet copy iso14651_t1_common i filen iso14651_t1, som i sin tur inkluderes i de nationale filer, herunder i en_US og ru_RU. I de fleste distributioner Linux alle kildefiler er inkluderet i den grundlæggende installation, men hvis de ikke er der, skal du installere en ekstra pakke fra distributionen.

Strukturen af filen iso14651_t1 kan virke frygteligt ordret, med uklare regler for navneopbygning, men hvis du først forstår det, så er alt ret simpelt. Strukturen er beskrevet i standarden ISO 14652, en kopi af hvilken kan downloades fra webstedet open-std.org. Yderligere en beskrivelse af filformatet kan læses i specifikationer POSIX fra OpenGroup. Som et alternativ til at læse standarden kan du studere kildekoden til funktionen collate_read i glibc/locale/programs/ld-collate.c.

Filstrukturen ser således ud:

Som standard anvendes symbolet som escape-tegn, og slutningen af linjen efter symbolet # er en kommentar. Begge symboler kan overskrives, hvilket også er gjort i den nye version af tabellen:

escape_char /
comment_char %

I filen vil der være tokens i formatet <Uxxxx> eller <Uxxxxxxxx> (hvor x — hexadecimale cifre). Dette er den hexadecimale repræsentation af Unicode-kodepunkter i kodningen UCS-4 (UTF-32). Alle andre elementer i vinkelparenteser (herunder <Uxxxx_xxxx>, <2> og lignende), betragtes som simple strengekonstanter, der ikke har nogen særlig betydning uden for konteksten.

Streng LC_COLLATE fortæller os, at dataene, der beskriver sammenligning af strenge, begynder her.

Først angives navne til vægtene i sammenligningstabellen og navne til kombinationer af tegn. Generelt tilhører de to typer navne to forskellige enheder, men i den faktiske fil er de blandet sammen. Navne til vægte angives med nøgleordet collating-symbol (sammenligningssymbol), da tegn i Unicode, der har samme vægt, betragtes som ækvivalente tegn ved sammenligning.

Den samlede længde af sektionen i den nuværende filrevision er omkring 900 linjer. Jeg har taget eksempler fra flere steder for at vise tilfældigheden af navne og forskellige typer syntaks.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantér den største symbolværdi. Holdes til slut i denne liste
...
collating-element  fra ""
collating-element  fra ""

collating-symbol registrerer strengen OSMANYA i vægt tabel
collating-symbol .. registrerer en sekvens af navne bestående af et præfiks Angreb op til 1,2 og et hexadecimalt nummer suffiks fra 1D000 op til 1D35F.
FFFF i collating-symbol ser ud som et stort usigneret heltal i hexadecimalt system, men <SFFFF> det er blot et navn, som kunne se sådan ud som <VERYBIGVAL>
navn <U0413> betyder en kodepunkt i kodningen UCS-4
collating-element fra "" registrerer et nyt navn for et par Unicode punkter.

Når vægtene er defineret, sættes selve vægtene. Da det kun er forholdet større-mindre, der er vigtigt ved sammenligning, bestemmes vægtene ved en simpel rækkefølge af navne. Først listes de "lettere" vægte, derefter de "tungere". Jeg minder om, at hver Unicode-tegn får tildelt fire forskellige vægte. Her er de samlet i en ordnet rækkefølge. Teoretisk set kan ethvert symbolsk navn bruges på et af de fire niveauer, men kommentarer indikerer, at udviklerne mentalt skelner navne efter niveauer.

% Symbolske vægt tildelinger

% Tredje-niveau vægt tildelinger




...
% Andet-niveau vægt tildelinger

 % KOMBINERENDE LAV LINIE
 % KOMBINERENDE KOMMA OVENFOR
 % KOMBINERENDE OMVENDT KOMMA OVENFOR
...
% Første-niveau vægt tildelinger
 % HORISONTAL TABULERING
 % LINJE SKIFT
 % VERTIKAL TABULERING
...
 % CYRILSK LILLE BOGSTAV DE
 % CYRILSK LILLE BOGSTAV KOMI DE
 % CYRILSK LILLE BOGSTAV DJE
 % CYRILSK LILLE BOGSTAV KOMI DJE
 % CYRILSK LILLE BOGSTAV GJE
 % CYRILSK LILLE BOGSTAV ZE MED DESCENDER
 % CYRILSK LILLE BOGSTAV IE
 % CYRILSK LILLE BOGSTAV IE MED BREVE
 % CYRILSK LILLE BOGSTAV UKRAINISK IE
 % CYRILSK LILLE BOGSTAV ZHE

Endelig selve vægt-tabellen.

Vægtsektionen er indkapslet i rækker med nøgleord order_start og order_end. Yderligere parametre order_start bestemmer, i hvilken retning rækkerne vises på hvert sammenligningsniveau. Som standard bruges parameteren forward. Sektionens krop består af rækker, der indeholder tegnkode og fire vægte. Tegnkoden kan præsenteres som selve tegnet, som kodepunktet eller som et symbolsk navn, der er defineret tidligere. Vægte kan også angives ved symbolske navne, kodepunkter eller selve tegnene. Hvis kodepunkter eller tegn bruges, svarer deres vægt til det numeriske værdien af kodepunktet (positionen i Unicode-tabellen). Tegn, der ikke er specificeret eksplicit (som jeg forstår), betragtes som tilknyttede i tabellen med en primær vægt svarende til positionen i Unicode-tabellen. Den specielle vægtværdi IGNORE betyder, at det pågældende tegn ignoreres på det relevante sammenligningsniveau.

For at demonstrere vægtstrukturen har jeg valgt tre ret indlysende fragmenter:

tegn, der ignoreres helt
tegn svarende til tallet tre på de første to niveauer
begyndelsen af det kyrilliske alfabet, som ikke indeholder diakritiske tegn, og derfor sorteres hovedsageligt efter det første og tredje niveau.

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 vende tilbage til sorteringen af eksemplerne fra begyndelsen af artiklen. Problemet ligger i denne del af vægt-tabellen:

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

Det er tydeligt, at denne tabel indeholder tegnsætning fra tabellen ASCII (inklusive mellemrum) ved sammenligning af strenge ignoreres stort set altid. Undtagelsen er kun strenge, der er identiske i alt andet end tegnsætning, der optræder i samme positioner. Strenge fra mit eksempel (efter sortering) vises således til sammenligningsalgoritmen:

AbakanovMikhailMalear
JolkinaEllakranovschitsa
IvanovaAllamalear
IvanovAndreiSmed

Da store bogstaver i det russiske sprog kommer efter små bogstaver i vægtabellen (på tredje niveau <CAP> tungere end <MIN>), ser sorteringen helt korrekt ud.

Ved at indstille variablen LC_COLLATE=C indlæses en særlig tabel, som angiver byte-for-byte sammenligning

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

Da Unicode-kodepunktet for Ё ligger før А, sorteres strenge i overensstemmelse hermed.

Tekst- og binærtabeller

Det er indlysende, at sammenligning af strenge er en ekstremt hyppig operation, mens analysen af tabellen ), hvis adresse kan findes i bilaget er en ret kostbar procedure. For at optimere adgangen til tabellen kompilere den i binær form ved hjælp af kommandoen localedef.

Kommandoen localedef modtager som parametre en fil med tabellen for nationale kendetegn (option -i), hvor alle tegn er repræsenteret af Unicode punkter, og en fil med overensstemmelse mellem Unicode punkter og tegn fra en bestemt kodning (option -f). Som resultat af arbejdet skabes der binære filer til lokaliteten med det navn, der er angivet i den sidste parameter.

Glibc understøtter to formater af binære filer: "traditionelt" og "moderne".

Det traditionelle format indebærer, at navnet på lokaliteten er navnet på en undermappe i /usr/lib/locale/. I denne undermappe opbevares binære filer LC_COLLATE, LC_CTYPE, LC_TIME og så videre. Filen LC_IDENTIFICATION indeholder det formelle navn på lokaliteten (som muligvis adskiller sig fra mappenavnet) og kommentarer.

Det moderne format forudsætter opbevaring af alle lokaliteter i et enkelt arkiv /usr/lib/locale/locale-archive, som kortlægges til den virtuelle hukommelse i alle processer, der bruger glibcNavnet på lokaliteten i det moderne format udsættes for en vis kanonisering - i navnene på kodninger bevares kun tal og bogstaver, der er omdannet til små bogstaver. Så ru_RU.KOI8-R, vil blive gemt som ru_RU.koi8r.

Indgangsfiler findes i den aktuelle katalog samt i katalogerne /usr/share/i18n/locales/ og /usr/share/i18n/charmaps/ for filer ), hvis adresse kan findes i bilaget og filer med kodninger henholdsvis.

For eksempel vil kommandoen

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

kompilere filen /usr/share/i18n/locales/ru_RU ved brug af kodningsfilen /usr/share/i18n/charmaps/MAC-CYRILLIC.gz og gemme resultatet i /usr/lib/locale/locale-archive med navnet ru_RU.maccyrillic

Hvis variablen LANG=en_US.UTF-8 så glibc vil kigge efter binære filer til lokaliteten i følgende sekvens af filer og 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/

Hvis lokaliteten findes både i traditionelle og moderne formater, gives der prioritet til den moderne.

For at se listen over kompileringer af lokaliteter kan kommandoen locale -a.

Forberedelse af din egen sammenligningstabel

Nu, bevæbnet med viden, kan du oprette din egen ideelle sammenligningstabel. Denne tabel skal korrekt sammenligne russiske bogstaver, inklusive bogstavet Ё, og tage højde for tegnsætningsmærker i overensstemmelse med tabellen ASCII.

Processen med at forberede sin egen sorteringstabel består af to trin: redigering af vægt tabellen og kompilering af den til binær form via kommandoen localedef.

For at sorteringstabellen kan tilpasses med minimale redigeringsomkostninger, er der sektioner til justering af vægtene i den eksisterende tabel i formatet ISO 14652 som giver mulighed for at angive en sektion. Sektionen starter med nøgleordet reorder-after og angivelsen af positionen, efter hvilken udskiftningen udføres. Sektionen afsluttes med linjenreorder-end

. Hvis det er nødvendigt at rette flere dele af tabellen, oprettes en sektion for hver del. iso14651_t1_common og ru_RU fra repository glibc Jeg har kopieret de nye versioner af filerne LC_COLLATE i ru_RUtil min hjemmebibliotek ~/.local/share/i18n/locales/ og redigeret sektionen lidt. glibcDe nye versioner af filerne er fuldt kompatible med min version.

LC_COLLATE
% Kopier skabelonen fra ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % UDRÅBSTEGN
 ;;; % CITATTEGN
...
 ;;; % HØJRE KRØLLERBRIK
 ;;; % TILDE
reorder-end
END LC_COLLATE

I virkeligheden skulle felterne ændres i LC_IDENTIFICATION så de peger på lokaliteten da_MY, men i mit eksempel var det ikke nødvendigt, da jeg udelukkede lokalarkivet fra søgningen locale-archive.

For at localedef arbejdede med filer i min mappe gennem variablen I18NPATH man kan tilføje en ekstra katalog til at søge i de indgående filer, og kataloget til opbevaring af binære filer kan angives som en sti med skråstreger:

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

POSIX betyder, at i LANG man kan skrive absolutte stier til kataloger med lokalefiler, der begynder med en direkte skråstreg, men glibc i Linux alle stier bliver betragtet fra basis-kataloget, som kan overskrives gennem variablen LOCPATH. Efter indstillingen LOCPATH=~/.local/lib/locale/ vil alle filer relateret til lokalisering kun blive søgt i min mappe. Arkivet af lokaliteter med den indstillede variabel LOCPATH ignoreres.

Her er den afgørende test:

$> LANG=da_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;maler
Yolkinna Ella;kranoperatør
Ivanov Andrey;smed
Ivanova Alla;advokat

Hurra! Vi gjorde det!

Fejlretning

Jeg har allerede besvaret spørgsmålene om sortering af strenge, der blev stillet i starten, men der er stadig et par spørgsmål om fejl - både synlige og usynlige.

Lad os vende tilbage til den oprindelige opgave.

Og programmet sort og programmet sammenføje bruger de samme funktionsmetoder til sammenligning af strenge fra glibc. Hvordan kunne det være, at sammenføje gav en sorteringsfejl på strenge, der var sorteret med kommandoen sort i lokaliteten en_US.UTF-8? Ответ прост: sort sammenligner hele strengen, mens sammenføje kun sammenligner nøglen, som som standard er begyndelsen af strengen op til det første mellemrum. I mit eksempel førte det til en fejlmeddelelse, da sorteringen af de første ord i strengene ikke stemte overens med sorteringen af de fulde strenge.

Lokaliteten "C" garanterer, at de sorterede strenge også har deres startunderskaber op til det første mellemrum sorteret, men det maskerer kun fejlen. Man kan finde data (folk med ens efternavne, men forskellige fornavne), der uden fejlmeddelelse ville give forkerte resultater ved sammensmeltning af filer. Hvis vi ønsker, at sammenføje sammensmelte strenge fra filer efter fulde navne, vil den rette måde være at angive feltseparatoren eksplicit og sortere efter nøglefeltet, ikke efter hele strengen. I dette tilfælde vil sammensmeltningen også ske korrekt, og der vil ikke være fejl i nogen lokalitet:

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

Et vellykket eksempel i kodningen CP1251 indeholder endnu en fejl. Det er sådan, at i alle de distributioner, jeg kender til, Linux mangler de kompilerede lokaler i pakkerne ru_RU.CP1251. Hvis den kompilerede lokal ikke findes, så sort bruger den stille og roligt byte-for-byte sammenligning, hvilket vi observerede.

Forresten, der er en lille bug relateret til den utilgængelige kompilerede lokal. Kommandoen LOCPATH=/tmp locale -a giver en liste over alle lokaler i locale-archive, men med den indstillede variabel LOCPATH for alle programmer (inklusive selve locale) vil disse lokaler være utilgængelige.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Kan ikke indstille LC_CTYPE til standard lokal: Ingen sådan fil eller mappe
locale: Kan ikke indstille LC_MESSAGES til standard lokal: Ingen sådan fil eller mappe
locale: Kan ikke indstille LC_COLLATE til standard lokal: Ingen sådan fil eller mappe
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: bruger ‘en_US.UTF-8’ sorteringsregler

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: bruger simpel byte sammenligning

Konklusion

Hvis du er en programmør, der er vant til at tænke på strenge som et sæt bytes, så er dit valg LC_COLLATE=C.

Hvis du er lingvist eller ordbogsforfatter, så er det bedst for dig at kompilere din egen lokal.

Hvis du er en almindelig bruger, så er det nok for dig at vænne dig til, at kommandoen ls -a viser filer, der begynder med punktum, blandet med filer, der begynder med bogstavet, og Midnight Commander, som bruger sine interne funktioner til at sortere navne, placerer filer, der begynder med punktum, i starten af listen.