Indledning

Det hele startede med et kort script, der skulle kombinere adresseoplysninger e-mail medarbejdere hentet fra listen over mailinglistebrugere, med medarbejderstillinger hentet fra HR-afdelingens database. Begge lister blev eksporteret til Unicode-tekstfiler UTF-8 og gemt med Unix linjeafslutninger.

Indhold mail.txt

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

Indhold buhg.txt

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

For at flette filerne blev filerne sorteret efter Unix-kommandoen sort og forelagt input fra Unix-programmet deltage, som uventet mislykkedes 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: Иванов Андрей;слесарь

At se sorteringsresultatet med dine øjne viste, at sorteringen generelt er korrekt, men i tilfælde af tilfældigheder af mandlige og kvindelige efternavne, kommer de kvindelige før de mandlige:

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

Ligner en sorteringsfejl i Unicode eller som en manifestation af feminisme i sorteringsalgoritmen. Den første er selvfølgelig mere plausibel.

Lad os udsætte det for nu deltage og fokusere på sort. Lad os prøve at løse problemet ved hjælp af videnskabelig poking. Lad os først ændre lokaliteten fra da_DK på ru_RU. For at sortere ville det være nok at indstille miljøvariablen LC_SAMLER, men vi vil ikke spilde tid på bagateller:

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

Intet ændrede sig.

Lad os prøve at omkode filerne til en enkeltbyte-kodning:

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

Intet har igen ændret sig.

Der er ikke noget du kan gøre, du bliver nødt til at lede efter en løsning på internettet. Der er intet direkte om russiske efternavne, men der er spørgsmål om andre sorteringsmærkværdigheder. Her er for eksempel et problem: unix sort behandler '-' (bindestreg) tegn som usynlige. Kort sagt er strengene "a-b", "aa", "ac" sorteret som "aa", "a-b", "ac".

Svaret er standard overalt: brug programmørens lokalitet "C" og du vil blive glad. Lad os prøve:

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

Noget har ændret sig. Ivanovs stillede op i den rigtige rækkefølge, selvom Yolkina gled et sted. Lad os vende tilbage til det oprindelige problem:

$> 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 dette på trods af Yolkina i første linje.

Problemet ser ud til at være løst, men for en sikkerheds skyld, lad os prøve en anden russisk kodning - Windows CP1251:

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

Sorteringsresultatet vil mærkeligt nok falde sammen med lokaliteten "C", og hele eksemplet kører derfor uden fejl. En slags mystik.

Jeg kan ikke lide mystik i programmering, fordi det normalt skjuler fejl. Vi bliver nødt til seriøst at se på, hvordan det fungerer. sort og hvad påvirker det? LC_SAMLER .

Til sidst vil jeg forsøge at besvare spørgsmålene:

hvorfor blev kvindelige efternavne sorteret forkert?
hvorfor LANG=ru_RU.CP1251 viste sig at være tilsvarende LANG=C
hvorfor gøre det sort и deltage forskellige ideer om rækkefølgen af sorterede strenge
hvorfor er der fejl i alle mine eksempler?
endelig hvordan du sorterer strenge efter din smag

Sortering i Unicode

Første stop vil være teknisk rapport nr. 10 med titlen Unicode-sorteringsalgoritme online unicode.org. Rapporten indeholder mange tekniske detaljer, så lad mig give en kort opsummering af hovedideerne.

Sortering — "Sammenligning" af strenge er grundlaget for enhver sorteringsalgoritme. Algoritmerne i sig selv kan være forskellige ("boble", "flette", "hurtigt"), men de vil alle bruge en sammenligning af et par strenge til at bestemme den rækkefølge, de vises i.

Sortering af strenge i naturligt sprog er et ret komplekst problem. Selv i de enkleste enkeltbyte-kodninger vil rækkefølgen af bogstaver i alfabetet, selv på en eller anden måde forskellig fra det engelske latinske alfabet, ikke længere falde sammen med rækkefølgen af de numeriske værdier, som disse bogstaver er kodet med. Så i det tyske alfabet bogstavet Ö står imellem О и P, og i kodningen CP850 hun kommer imellem ÿ и Ü.

Du kan prøve at abstrahere fra en specifik kodning og overveje "ideelle" bogstaver, der er arrangeret i en eller anden rækkefølge, som det gøres i Unicode. Kodninger 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 bogstaver, men henviser til de samme elementer i basistabellen.

Det viser sig, at selvom vi bygger en symboltabel fra bunden, vil vi ikke være i stand til at tildele en universel symbolrækkefølge til den. I forskellige nationale alfabeter, der bruger de samme bogstaver, kan rækkefølgen af disse bogstaver variere. For eksempel på fransk Æ vil blive betragtet som en ligatur og sorteret som en streng AE. På norsk Æ vil være et særskilt brev, som er placeret efter Z. Af den måde, ud over ligaturer som Æ Der er bogstaver skrevet med flere symboler. Så i det tjekkiske alfabet er der et bogstav Ch, som står imellem H и I.

Ud over forskelle i alfabeter er der andre nationale traditioner, der har indflydelse på sorteringen. Specielt opstår spørgsmålet: i hvilken rækkefølge skal ord bestående af store og små bogstaver optræde i ordbogen? Sortering kan også blive påvirket af brugen af tegnsætningstegn. På spansk bruges et omvendt spørgsmålstegn i begyndelsen af en spørgende sætning (Kan du lide musik?). I dette tilfælde er det indlysende, at spørgende sætninger ikke bør grupperes i en separat klynge uden for alfabetet, men hvordan sorterer man linjer med andre tegnsætningstegn?

Jeg vil ikke dvæle ved at sortere strenge på sprog, der er meget forskellige fra europæiske. Bemærk, at på sprog med en skriveretning fra højre til venstre eller fra top til bund, er tegn i linjer højst sandsynligt gemt i læserækkefølge, og selv ikke-alfabetiske skrivesystemer har deres egne måder at ordne linjer på tegn for tegn . For eksempel kan hieroglyffer ordnes efter stil (Taster med kinesiske tegn) eller ved udtale. For at være ærlig har jeg ingen idé om, hvordan emojis skal arrangeres, men du kan også finde på noget til dem.

Baseret på de funktioner, der er anført ovenfor, blev de grundlæggende krav til sammenligning af strenge baseret på Unicode-tabeller formuleret:

sammenligning af strenge afhænger ikke af placeringen af tegn i kodetabellen;
sekvenser af tegn, der danner et enkelt tegn, reduceres til kanonisk form (A + den øverste cirkel er den samme som Å);
Når man sammenligner strenge, betragtes et tegn i sammenhængen med strengen og om nødvendigt kombineret med dets naboer til én sammenligningsenhed (Ch på tjekkisk) eller er opdelt i flere (Æ på fransk);
alle nationale funktioner (alfabet, store/små bogstaver, tegnsætning, rækkefølge af skrivetyper) skal konfigureres op til den manuelle tildeling af rækkefølgen (emoji);
sammenligning er vigtig ikke kun for sortering, men også mange andre steder, for eksempel for at specificere rækkeområder (erstatter {A... z} i bash);
sammenligningen bør foretages ret hurtigt.

Derudover formulerede rapportens forfattere sammenligningsegenskaber, som algoritmeudviklere ikke bør stole på:

sammenligningsalgoritmen bør ikke kræve et separat sæt tegn for hvert sprog (russiske og ukrainske sprog deler de fleste kyrilliske tegn);
sammenligningen bør ikke stole på rækkefølgen af tegn i Unicode-tabeller;
strengvægt bør ikke være en egenskab for strengen, da den samme streng i forskellige kulturelle sammenhænge kan have forskellig vægt;
rækkevægte kan ændre sig ved sammenlægning eller opdeling (fra x < y det følger ikke det xz < yz);
forskellige strenge med samme vægt betragtes som lige fra sorteringsalgoritmens synspunkt. Det er muligt at indføre yderligere rækkefølge af sådanne strenge, men det kan forringe ydeevnen;
Ved gentagen sortering kan rækker med samme vægt udskiftes. Robusthed er en egenskab ved en specifik sorteringsalgoritme og ikke en egenskab ved en strengsammenligningsalgoritme (se forrige afsnit);
Sorteringsregler kan ændre sig over tid, efterhånden som kulturelle traditioner forfiner/ændres.

Det er også fastsat, at sammenligningsalgoritmen ikke ved noget om semantikken af de strenge, der behandles. Strenge, der kun består af cifre bør derfor ikke sammenlignes som tal, og i lister over engelske navne er artiklen (Beatles, The).

For at opfylde alle disse krav foreslås en tabelsorteringsalgoritme med flere niveauer (faktisk fire niveauer).

Tidligere blev tegnene i strengen reduceret til kanonisk form og grupperet i sammenligningsenheder. Hver sammenligningsenhed tildeles flere vægte svarende til flere sammenligningsniveauer. Vægten af sammenligningsenheder er elementer af ordnede sæt (i dette tilfælde heltal), der kan sammenlignes for mere eller mindre. Særlig betydning IGNORERET (0x0) betyder, at denne enhed på det tilsvarende sammenligningsniveau ikke er involveret i sammenligningen. Sammenligningen af strenge kan gentages flere gange ved hjælp af vægtene af de tilsvarende niveauer. På hvert niveau sammenlignes vægten af sammenligningsenhederne i to rækker sekventielt med hinanden.

I forskellige implementeringer af algoritmen for forskellige nationale traditioner kan værdierne af koefficienterne variere, men Unicode-standarden inkluderer en grundlæggende vægttabel - "Standard Unicode-sorteringselementtabel" (DUCET). Jeg vil gerne bemærke, at indstilling af variablen LC_SAMLER er faktisk en indikation af valget af vægttabellen i strengsammenligningsfunktionen.

Vægtningskoefficienter DUCET arrangeret som følger:

på første niveau reduceres alle bogstaver til samme store og små bogstaver, diakritiske tegn kasseres, tegnsætningstegn (ikke alle) ignoreres;
på andet niveau tages kun diakritiske tegn i betragtning;
på tredje niveau tages der kun hensyn til tilfælde;
på fjerde niveau tages der kun hensyn til tegnsætningstegn.

Sammenligningen foregår i flere omgange: først sammenlignes koefficienterne for det første niveau; hvis vægtene falder sammen, udføres en gentagen sammenligning med vægtene på andet niveau; så måske en tredje og en fjerde.

Sammenligningen slutter, når rækkerne indeholder matchende sammenligningsenheder med forskellige vægte. Rækker, der har samme vægt på alle fire niveauer, anses for at være lig med hinanden.

Denne algoritme (med en masse yderligere tekniske detaljer) gav navnet til rapport nr. 10 - "Unicode Collation Algorithm" (ACU).

Det er her, sorteringsadfærden fra vores eksempel bliver lidt tydeligere. Det ville være rart at sammenligne det med Unicode-standarden.

At teste implementeringer ACU der er en speciel тест, ved brug af vægte fil, implementerer DUCET. Du kan finde alle mulige sjove ting i vægtfilen. For eksempel er der rækkefølgen af mahjong og europæiske dominobrikker, såvel som rækkefølgen af kulører i et spil kort (symbol 1F000 og videre). Kortdragterne placeres efter reglerne for bridge - PCBT, og kortene i kuløren er i rækkefølgen T, 2,3, XNUMX... K.

Manuel kontrol af at rækker er sorteret korrekt iflg DUCET ville være ret kedeligt, men heldigvis for os er der en eksemplarisk implementering af biblioteket til at arbejde med Unicode - "Internationale komponenter til Unicode"(ICU).

På webstedet for dette bibliotek, udviklet i IBM, der er demo-sider, bl.a side for strengsammenligningsalgoritme. Vi går ind i vores testlinjer med standardindstillinger, og lo og se, vi får perfekt russisk sortering.

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

Forresten hjemmesiden ICU Du kan finde en afklaring af sammenligningsalgoritmen ved behandling af tegnsætningstegn. I eksempler Ofte stillede spørgsmål om indsamling apostrof og bindestreg ignoreres.

Unicode hjalp os, men se efter årsager til mærkelig adfærd sort в Linux bliver nødt til at gå et andet sted hen.

Sortering i glibc

Hurtigt overblik over hjælpeprogrammets kildekoder sort af GNU Core Utils viste, at lokalisering i selve hjælpeprogrammet handler om at udskrive den aktuelle værdi af variablen LC_SAMLER når du kører i fejlretningstilstand:

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

Strengsammenligninger udføres ved hjælp af standardfunktionen strcoll, hvilket betyder, at alt interessant er på biblioteket glibc.

On wiki projekt glibc dedikeret til sammenligning af strenge ét afsnit. Ud fra dette afsnit kan det forstås, at i glibc sortering er baseret på en algoritme, som vi allerede kender ACU (Unicode-sorteringsalgoritmen) og/eller på en standard tæt på det ISO 14651 (International streng bestilling og sammenligning). Med hensyn til den seneste standard, skal det bemærkes, at på webstedet standards.iso.org ISO 14651 officielt erklæret offentligt tilgængelig, men det tilsvarende link fører til en ikke-eksisterende side. Google returnerer flere sider med links til officielle sider, der tilbyder at købe en elektronisk kopi af standarden for hundrede euro, men på den tredje eller fjerde side med søgeresultater er der også direkte links til PDF. Generelt er standarden praktisk talt ikke forskellig fra ACU, men er mere kedeligt at læse, fordi den ikke indeholder klare eksempler på nationale træk ved strengsortering.

De mest interessante oplysninger vedr wiki der var et link til bug tracker med en diskussion af implementeringen af strengsammenligning i glibc. Det kan man lære af diskussionen glibc bruges til at sammenligne strenge ISOpersonligt bord Den fælles skabelontabel (CTT), hvis adresse kan findes i ansøgningen A standarden ISO 14651. Mellem 2000 og 2015 denne tabel ind glibc havde ikke en vedligeholder og var helt anderledes (i hvert fald eksternt) fra den nuværende version af standarden. Fra 2015 til 2018 fandt tilpasning til den nye version af bordet sted, og nu har du chancen for at møde en ny version af bordet i det virkelige liv (8 CentOS), og gamle (7 CentOS).

Nu hvor vi har alle oplysninger om algoritmen og hjælpetabellerne, kan vi vende tilbage til det oprindelige problem og forstå, hvordan man korrekt sorterer strenge i den russiske lokalitet.

ISO 14651 / 14652

Kildekoden til den tabel, vi er interesseret i CTT på de fleste distributioner Linux er i mappen /usr/share/i18n/locales/. Selve tabellen er i filen iso14651_t1_common. Så er dette fildirektivet kopi iso14651_t1_common inkluderet i filen iso14651_t1, som igen indgår i nationale akter, herunder da_DK и ru_RU. På de fleste distributioner Linux alle kildefiler er inkluderet i den grundlæggende installation, men hvis de ikke er til stede, skal du installere en ekstra pakke fra distributionen.

Filstruktur iso14651_t1 kan virke frygteligt omstændeligt, med ikke-oplagte regler for at konstruere navne, men hvis man ser på det, er alt ganske enkelt. Strukturen er beskrevet i standarden ISO 14652, hvoraf en kopi kan downloades fra hjemmesiden open-std.org. En anden 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 в glibc/locale/programs/ld-collate.c.

Filstrukturen ser sådan ud:

Som standard bruges tegnet som et escape-tegn, og slutningen af linjen efter #-tegnet er en kommentar. Begge symboler kan omdefineres, hvilket er, hvad der er gjort i den nye version af tabellen:

escape_char /
comment_char %

Filen vil indeholde tokens i formatet eller (Hvor x - hexadecimalt ciffer). Dette er den hexadecimale repræsentation af Unicode-kodepunkter i kodning UCS-4 (UTF-32). Alle andre elementer i vinkelbeslag (inklusive , og lignende) betragtes som simple strengkonstanter, der har ringe betydning uden for konteksten.

Line LC_SAMLER fortæller os, at dernæst begynder dataene, der beskriver sammenligningen af strenge.

Først angives navne for vægtene i sammenligningstabellen og navne for symbolkombinationerne. Generelt hører de to typer navne til to forskellige enheder, men i selve filen er de blandet. Navnene på vægtene er angivet med nøgleordet samle-symbol (sammenligningstegn), fordi Unicode-tegn, der har samme vægt, ved sammenligning vil blive betragtet som ækvivalente tegn.

Den samlede længde af afsnittet i den aktuelle filrevision er omkring 900 linjer. Jeg trak eksempler fra flere steder for at vise vilkårligheden af navne og flere typer syntaks.

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

samle-symbol logger en streng OSMANYA i tabellen over navne på vægte
samle-symbol .. registrerer en række navne bestående af et præfiks S og hexadecimalt numerisk suffiks fra 1D000 til 1D35F.
ffff в samle-symbol ligner et stort heltal uden fortegn i hexadecimal, men det er bare et navn, der kan ligne
Navn betyder kodepunkt i kodning UCS-4
samleelement fra "" registrerer et nyt navn for et par Unicode-punkter.

Når navnene på vægtene er defineret, er de faktiske vægte angivet. Da kun større-end-mindre relationer betyder noget i sammenligning, bestemmes vægtene af en simpel sekvens af listenavne. De "lettere" vægte vises først, derefter de "tyngre". Lad mig minde dig om, at hvert Unicode-tegn er tildelt fire forskellige vægte. Her er de kombineret til en enkelt ordnet sekvens. I teorien kunne et hvilket som helst symbolsk navn bruges på et hvilket som helst af de fire niveauer, men kommentarer indikerer, at udviklerne mentalt adskiller navne i niveauer.

% 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

Til sidst selve vægttabellen.

Vægtafsnittet er omgivet af søgeordslinjer ordre_start и ordre_slut. Ekstra muligheder ordre_start bestemme, i hvilken retning rækker scannes på hvert sammenligningsniveau. Standardindstillingen er frem. Sektionens krop består af linjer, der indeholder symbolkoden og dens fire vægte. Tegnkoden kan repræsenteres af selve tegnet, et kodepunkt eller et tidligere defineret symbolsk navn. Vægt kan også gives til symbolske navne, kodepunkter eller selve symbolerne. Hvis der bruges kodepunkter eller tegn, er deres vægt den samme som den numeriske værdi af kodepunktet (position i Unicode-tabellen). Tegn, der ikke er specificeret eksplicit (som jeg forstår), anses for at være tildelt tabellen med en primær vægt, der matcher positionen i Unicode-tabellen. Særlig vægtværdi IGNORERE betyder, at symbolet ignoreres på det passende sammenligningsniveau.

For at demonstrere strukturen af skalaerne valgte jeg tre ret tydelige fragmenter:

tegn, der ignoreres fuldstændigt
symboler svarende til tallet tre i de to første niveauer
begyndelsen af det kyrilliske alfabet, som ikke indeholder diakritiske tegn, og derfor er sorteret hovedsageligt efter første og tredje niveau.

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 vende tilbage til at sortere eksemplerne fra begyndelsen af artiklen. Bagholdet ligger i denne del af vægttabellen:

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

Det kan ses, at i denne tabel er tegnsætningstegnene fra tabellen ASCII (inklusive mellemrum) ignoreres næsten altid, når man sammenligner strenge. De eneste undtagelser er linjer, der matcher i alt undtagen tegnsætningstegn fundet i matchende positioner. Linjerne fra mit eksempel (efter sortering) for sammenligningsalgoritmen ser sådan ud:

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

I betragtning af, at i tabellen over skalaer kommer store bogstaver på russisk efter små bogstaver (på tredje niveau tungere end ), ser sorteringen helt korrekt ud.

Når du indstiller en variabel LC_COLLATE=C der indlæses en speciel tabel, der specificerer en 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'xfe', L'xff'
};

Da kodepunktet Ё i Unicode kommer før A, er strengene sorteret i overensstemmelse hermed.

Tekst og binære tabeller

Det er klart, at strengsammenligning er en ekstremt almindelig operation, og tabelparsing CTT en ret bekostelig procedure. For at optimere adgangen til tabellen kompileres den til binær form med kommandoen localdef.

Team localdef accepterer som parametre en fil med en tabel over nationale karakteristika (option -i), hvor alle tegn er repræsenteret af Unicode-punkter, og en fil med korrespondance mellem Unicode-punkter og tegn med en specifik kodning (mulighed -f). Som et resultat af arbejdet oprettes binære filer for lokaliteten med det navn, der er angivet i den sidste parameter.

glibc understøtter to binære filformater: "traditionel" og "moderne".

Det traditionelle format betyder, at navnet på lokaliteten er navnet på underbiblioteket i /usr/lib/locale/. Denne undermappe gemmer binære filer LC_SAMLER, LC_CTYPE, LC_TIME og så videre. Fil LC_IDENTIFIKATION indeholder det formelle navn på lokaliteten (som kan være forskellig fra mappenavnet) og kommentarer.

Det moderne format indebærer lagring af alle lokaliteter i et enkelt arkiv /usr/lib/locale/locale-archive, som er kortlagt til den virtuelle hukommelse for alle processer, der bruger glibc. Lokalnavnet i det moderne format er underlagt en vis kanonisering - kun tal og bogstaver reduceret til små bogstaver forbliver i indkodningsnavnene. Så ru_RU.KOI8-R, vil blive gemt som ru_RU.koi8r.

Der søges i inputfiler i den aktuelle mappe såvel som i mapper /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ for filer CTT hhv. og kodningsfiler.

For eksempel kommandoen

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

vil kompilere filen /usr/share/i18n/locales/ru_RU ved hjælp af kodningsfil /usr/share/i18n/charmaps/MAC-CYRILLIC.gz og gem resultatet i /usr/lib/locale/locale-archive under navnet ru_RU.maccyrillic

Hvis du indstiller variablen LANG = en_US.UTF-8 то glibc vil lede efter binære lokaliteter i følgende sekvens af filer og mapper:

/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 en lokalitet forekommer i både traditionelle og moderne formater, prioriteres den moderne.

Du kan se listen over kompilerede lokaliteter med kommandoen locale -a.

Udarbejdelse af din sammenligningstabel

Nu, bevæbnet med viden, kan du oprette din egen ideelle strengsammenligningstabel. Denne tabel skal korrekt sammenligne russiske bogstaver, inklusive bogstavet Ё, og samtidig tage hensyn til tegnsætningstegn i overensstemmelse med tabellen ASCII.

Processen med at udarbejde din egen sorteringstabel består af to trin: redigering af vægttabellen og kompilering til binær form med kommandoen localdef.

For at sammenligningstabellen kan justeres med minimale redigeringsomkostninger, i formatet ISO 14652 Der er sektioner til justering af vægten af en eksisterende tabel. Afsnittet starter med et nøgleord genbestil-efter og angivelse af den position, hvorefter udskiftningen udføres. Afsnittet slutter med stregen genbestillingsslut. Hvis det er nødvendigt at rette flere sektioner af tabellen, oprettes en sektion for hver sådan sektion.

Jeg kopierede nye versioner af filerne iso14651_t1_common и ru_RU fra depotet glibc til min hjemmemappe ~/.local/share/i18n/locales/ og redigerede lidt i afsnittet LC_SAMLER в ru_RU. Nye versioner af filer er fuldt ud kompatible med min version glibc. Hvis du vil bruge ældre versioner af filer, skal du ændre de symbolske navne og det sted, hvor erstatningen starter 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

Faktisk ville det være nødvendigt at ændre felterne i LC_IDENTIFIKATION så de peger på lokaliteten ru_MY, men i mit eksempel var dette ikke påkrævet, da jeg udelukkede arkivet fra søgningen efter lokaliteter lokalitetsarkiv.

Det localdef arbejdede med filer i min mappe gennem en variabel I18NPATH Du kan tilføje en ekstra mappe til at søge efter inputfiler, og mappen til at gemme binære filer kan angives som en sti med skråstreger:

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

POSIX antager, at i SPROG du kan skrive absolutte stier til mapper med lokalitetsfiler, begyndende med en skråstreg, men glibc в Linux alle stier tælles fra basismappen, som kan tilsidesættes gennem en variabel LOCPATH. Efter installation LOCPATH=~/.local/lib/locale/ alle filer relateret til lokalisering vil kun blive søgt i min mappe. Arkiv over lokaliteter med variabelsættet LOCPATH ignoreret.

Her er den afgørende test:

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

Hurra! Vi gjorde det!

Nogle fejl

Jeg har allerede besvaret spørgsmålene om strengsortering stillet i begyndelsen, men der er stadig et par spørgsmål om fejl - synlige og usynlige.

Lad os vende tilbage til det oprindelige problem.

Og programmet sort og programmet deltage bruge de samme strengsammenligningsfunktioner fra glibc. Hvordan skete det deltage gav en sorteringsfejl på rækker sorteret efter kommandoen sort i lokalitet da_US.UTF-8? Svaret er enkelt: sort sammenligner hele strengen, og deltage sammenligner kun nøglen, som som standard er begyndelsen af strengen op til det første mellemrumstegn. I mit eksempel resulterede dette i en fejlmeddelelse, fordi sorteringen af de første ord i linjerne ikke stemte overens med sorteringen af de komplette linjer.

Lokalitet "C" garanterer, at i sorterede strenge vil de indledende understrenge op til det første mellemrum også blive sorteret, men dette maskerer kun fejlen. Det er muligt at vælge data (personer med samme efternavn, men forskellige fornavne), der uden fejlmeddelelsen ville give et forkert filfletningsresultat. Hvis vi vil deltage flettede fillinjer efter fulde navn, så ville den korrekte måde være at angive feltseparatoren eksplicit og sortere efter nøglefeltet og ikke efter hele linjen. I dette tilfælde vil fletningen fortsætte 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

Succesfuldt udført eksempel i kodning CP1251 indeholder en anden fejl. Faktum er, at i alle distributioner kendt for mig Linux pakker mangler kompileret lokalitet ru_RU.CP1251. Hvis den kompilerede landestandard ikke findes, så sort bruger lydløst en byte-for-byte sammenligning, hvilket er, hvad vi observerede.

Forresten er der en anden lille fejl relateret til utilgængeligheden af kompilerede lokaliteter. Hold LOCPATH=/tmp landestandard -a vil give en liste over alle lokaliteter i lokalitetsarkiv, men med variabelsættet LOCPATH for alle programmer (inklusive de fleste Local) vil disse lokaliteter ikke være tilgængelige.

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

Konklusion

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

Hvis du er en lingvist eller ordbogskompiler, så kompilerer du hellere i din lokalitet.

Hvis du er en simpel bruger, så skal du bare vænne dig til, at kommandoen ls -a udsender filer, der starter med en prik blandet med filer, der begynder med et bogstav, og Midnat kommandør, som bruger sine interne funktioner til at sortere navne, sætter filer, der starter med en prik i begyndelsen af listen.