Innledning

Det hele startet med et kort manus som skulle kombinere adresseinformasjon e-post ansatte hentet fra listen over e-postlistebrukere, med ansattstillinger hentet fra HR-avdelingens database. Begge listene ble eksportert til Unicode-tekstfiler UTF-8 og lagret med Unix-linjeavslutninger.

Innhold mail.txt

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

Innhold buhg.txt

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

For å slå sammen ble filene sortert etter Unix-kommandoen Sorter og sendt til input fra Unix-programmet bli medlem, som uventet mislyktes med en feil:

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

Å se sorteringsresultatet med øynene viste at sorteringen generelt er riktig, men i tilfelle tilfeldigheter med mannlige og kvinnelige etternavn, kommer de kvinnelige før de mannlige:

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

Ser ut som en sorteringsfeil i Unicode eller som en manifestasjon av feminisme i sorteringsalgoritmen. Den første er selvfølgelig mer plausibel.

La oss utsette det for nå bli medlem og fokusere på Sorter. La oss prøve å løse problemet ved hjelp av vitenskapelig poking. Først, la oss endre lokaliteten fra no på ru_ru. For å sortere vil det være nok å sette miljøvariabelen LC_SAMLER, men vi vil ikke kaste bort tid på bagateller:

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

Ingenting endret seg.

La oss prøve å omkode filene til en enkeltbyte-koding:

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

Igjen har ingenting endret seg.

Det er ingenting du kan gjøre, du må lete etter en løsning på Internett. Det står ikke noe direkte om russiske etternavn, men det er spørsmål om andre sorteringsmerkheter. For eksempel, her er et problem: unix sort behandler '-' (strek)-tegn som usynlige. Kort sagt, strengene "a-b", "aa", "ac" er sortert som "aa", "a-b", "ac".

Svaret er standard overalt: bruk programmererens lokalitet "C" og du vil bli glad. La oss prøve:

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

Noe har endret seg. Ivanovene stilte opp i riktig rekkefølge, selv om Yolkina skled et sted. La oss gå tilbake til det opprinnelige problemet:

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

Det fungerte uten feil, som Internett lovet. Og dette til tross for Yolkina i første linje.

Problemet ser ut til å være løst, men for sikkerhets skyld, la oss prøve en annen russisk koding - Windows CP1251:

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

Sorteringsresultatet vil merkelig nok sammenfalle med lokaliteten "C", og hele eksemplet kjører følgelig uten feil. En slags mystikk.

Jeg liker ikke mystikk i programmering fordi det vanligvis maskerer feil. Vi må se seriøst på hvordan det fungerer. Sorter og hva påvirker det? LC_SAMLER .

Til slutt vil jeg prøve å svare på spørsmålene:

hvorfor ble kvinnelige etternavn sortert feil?
Hvorfor LANG=ru_RU.CP1251 viste seg å være likeverdig LANG=C
hvorfor gjøre det Sorter и bli medlem forskjellige ideer om rekkefølgen på sorterte strenger
hvorfor er det feil i alle eksemplene mine?
endelig hvordan du sorterer strenger etter din smak

Sortering i Unicode

Første stopp vil være teknisk rapport nr. 10 med tittel Unicode-kollasjonsalgoritme online unicode.org. Rapporten inneholder mange tekniske detaljer, så la meg gi en kort oppsummering av hovedideene.

Sortering — «Sammenligning» av strenger er grunnlaget for enhver sorteringsalgoritme. Algoritmene i seg selv kan variere ("boble", "sammenslå", "rask"), men de vil alle bruke en sammenligning av et par strenger for å bestemme rekkefølgen de vises i.

Sortering av strenger i naturlig språk er et ganske komplekst problem. Selv i de enkleste enkeltbyte-kodingene, vil rekkefølgen av bokstaver i alfabetet, selv på en eller annen måte forskjellig fra det engelske latinske alfabetet, ikke lenger falle sammen med rekkefølgen på de numeriske verdiene som disse bokstavene er kodet med. Så i det tyske alfabetet bokstaven Ö står mellom О и P, og i kodingen CP850 hun kommer mellom ÿ и Ü.

Du kan prøve å abstrahere fra en spesifikk koding og vurdere "ideelle" bokstaver som er ordnet i en eller annen rekkefølge, slik det gjøres i Unicode. Kodinger UTF8, UTF16 eller én-byte KOI8-R (hvis et begrenset delsett av Unicode er nødvendig) vil gi forskjellige numeriske representasjoner av bokstaver, men refererer til de samme elementene i basistabellen.

Det viser seg at selv om vi bygger en symboltabell fra bunnen av, vil vi ikke kunne tilordne en universell symbolrekkefølge til den. I forskjellige nasjonale alfabeter som bruker de samme bokstavene, kan rekkefølgen på disse bokstavene variere. For eksempel på fransk Æ vil bli betraktet som en ligatur og sortert som en streng AE. På norsk Æ vil være et eget brev, som ligger etter Z. Forresten, i tillegg til ligaturer som Æ Det er bokstaver skrevet med flere symboler. Så i det tsjekkiske alfabetet er det en bokstav Ch, som står mellom H и I.

I tillegg til forskjeller i alfabeter, er det andre nasjonale tradisjoner som påvirker sorteringen. Spesielt oppstår spørsmålet: i hvilken rekkefølge skal ord som består av store og små bokstaver vises i ordboken? Sortering kan også påvirkes av bruk av skilletegn. På spansk brukes et omvendt spørsmålstegn i begynnelsen av en spørresetning (Liker du musikk?). I dette tilfellet er det åpenbart at spørresetninger ikke bør grupperes i en egen klynge utenfor alfabetet, men hvordan sorterer man linjer med andre skilletegn?

Jeg vil ikke dvele ved å sortere strenger på språk som er veldig forskjellige fra europeiske. Merk at på språk med skriveretning fra høyre til venstre eller topp-til-bunn, er tegn i linjer mest sannsynlig lagret i leserekkefølge, og til og med ikke-alfabetiske skrivesystemer har sine egne måter å ordne linjer på tegn for tegn . For eksempel kan hieroglyfer sorteres etter stil (Taster med kinesiske tegn) eller ved uttale. For å være ærlig har jeg ingen anelse om hvordan emojier skal ordnes, men du kan finne på noe for dem også.

Basert på funksjonene som er oppført ovenfor, ble de grunnleggende kravene for å sammenligne strenger basert på Unicode-tabeller formulert:

sammenligning av strenger avhenger ikke av plasseringen av tegn i kodetabellen;
sekvenser av tegn som danner et enkelt tegn reduseres til kanonisk form (A + den øverste sirkelen er den samme som Å);
Når du sammenligner strenger, vurderes et tegn i sammenheng med strengen og, om nødvendig, kombinert med naboene til én sammenligningsenhet (Ch på tsjekkisk) eller er delt inn i flere (Æ på fransk);
alle nasjonale funksjoner (alfabet, store/små bokstaver, tegnsetting, rekkefølge på skrivetyper) må konfigureres opp til den manuelle tilordningen av rekkefølgen (emoji);
sammenligning er viktig ikke bare for sortering, men også mange andre steder, for eksempel for å spesifisere radområder (erstatter {A... z} i bash);
sammenligningen bør gjøres ganske raskt.

I tillegg formulerte rapportens forfattere sammenligningsegenskaper som algoritmeutviklere ikke bør stole på:

sammenligningsalgoritmen skal ikke kreve et separat sett med tegn for hvert språk (russiske og ukrainske språk deler de fleste kyrilliske tegn);
sammenligningen bør ikke stole på rekkefølgen av tegn i Unicode-tabeller;
strengvekt skal ikke være et attributt til strengen, siden den samme strengen i ulike kulturelle kontekster kan ha ulik vekt;
radvekter kan endres ved sammenslåing eller splitting (fra x < y det følger ikke med det xz < yz);
forskjellige strenger med samme vekt anses like fra sorteringsalgoritmens synspunkt. Det er mulig å innføre ytterligere bestilling av slike strenger, men det kan forringe ytelsen;
Ved gjentatt sortering kan rader med samme vekt byttes. Robusthet er en egenskap til en spesifikk sorteringsalgoritme, og ikke en egenskap til en strengsammenligningsalgoritme (se forrige avsnitt);
Sorteringsregler kan endres over tid ettersom kulturelle tradisjoner foredles/endres.

Det er også fastsatt at sammenligningsalgoritmen ikke vet noe om semantikken til strengene som behandles. Strenger som kun består av sifre bør derfor ikke sammenlignes som tall, og i lister over engelske navn er artikkelen (Beatles, The).

For å tilfredsstille alle de spesifiserte kravene, foreslås en flernivås (faktisk fire-nivå) tabellsorteringsalgoritme.

Tidligere ble tegnene i strengen redusert til kanonisk form og gruppert i sammenligningsenheter. Hver sammenligningsenhet tildeles flere vekter som tilsvarer flere sammenligningsnivåer. Vektene til sammenligningsenheter er elementer av ordnede sett (i dette tilfellet heltall) som kan sammenlignes for mer eller mindre. Spesiell betydning IGNORERT (0x0) betyr at på det tilsvarende sammenligningsnivået er ikke denne enheten involvert i sammenligningen. Sammenligningen av strenger kan gjentas flere ganger ved å bruke vektene til de tilsvarende nivåene. På hvert nivå blir vektene til sammenligningsenhetene for to rader sekvensielt sammenlignet med hverandre.

I forskjellige implementeringer av algoritmen for forskjellige nasjonale tradisjoner, kan verdiene til koeffisientene variere, men Unicode-standarden inkluderer en grunnleggende vekttabell - "Standard Unicode-sorteringselementtabell" (DUCET). Jeg vil merke meg at innstillingen av variabelen LC_SAMLER er faktisk en indikasjon på valget av vekttabellen i strengsammenligningsfunksjonen.

Vektkoeffisienter DUCET ordnet som følger:

på det første nivået reduseres alle bokstaver til samme store og små bokstaver, diakritiske tegn forkastes, skilletegn (ikke alle) ignoreres;
på det andre nivået tas kun hensyn til diakritiske tegn;
på det tredje nivået tas det kun hensyn til tilfelle;
på fjerde nivå tas det kun hensyn til skilletegn.

Sammenligningen foregår i flere omganger: først sammenlignes koeffisientene til det første nivået; hvis vektene sammenfaller, utføres en gjentatt sammenligning med vektene på andre nivå; så kanskje en tredje og en fjerde.

Sammenligningen avsluttes når radene inneholder samsvarende sammenligningsenheter med forskjellig vekt. Rader som har lik vekt på alle fire nivåer anses som like hverandre.

Denne algoritmen (med en haug med ytterligere tekniske detaljer) ga navnet til rapport nr. 10 - "Unicode Collation Algorithm" (ACU).

Det er her sorteringsatferden fra vårt eksempel blir litt tydeligere. Det ville vært fint å sammenligne det med Unicode-standarden.

For å teste implementeringer ACU det er en spesiell тест, ved hjelp av vekter fil, implementere DUCET. Du kan finne alle slags morsomme ting i vektfilen. For eksempel er det rekkefølgen på mahjong og europeiske dominobrikker, samt rekkefølgen på fargene i en kortstokk (symbol 1F000 og videre). Kortdraktene er plassert i henhold til reglene for bridge - PCBT, og kortene i fargen er i rekkefølgen T, 2,3, XNUMX... K.

Kontrollerer manuelt at rader er riktig sortert iht DUCET ville vært ganske kjedelig, men heldigvis for oss er det en eksemplarisk implementering av biblioteket for å jobbe med Unicode - "Internasjonale komponenter for Unicode»(ICU).

På nettstedet til dette biblioteket, utviklet i IBM, det er demosider, inkludert algoritmeside for strengsammenligning. Vi går inn på testlinjene våre med standardinnstillinger, og se, vi får perfekt russisk sortering.

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

Forresten, nettsiden ICU Du kan finne en avklaring av sammenligningsalgoritmen når du behandler skilletegn. I eksempler Vanlige spørsmål om sortering apostrof og bindestrek ignoreres.

Unicode hjalp oss, men se etter årsaker til merkelig oppførsel Sorter в Linux må gå et annet sted.

Sortering i glibc

Rask oversikt over verktøyets kildekoder Sorter av GNU Core Utils viste at i selve verktøyet kommer lokalisering ned til å skrive ut gjeldende verdi av variabelen LC_SAMLER når du kjører i feilsøkingsmodus:

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

Stringsammenlikninger utføres ved å bruke standardfunksjonen strcoll, som betyr at alt interessant er i biblioteket glibc.

På wiki prosjekt glibc dedikert til strengsammenligning ett avsnitt. Fra dette avsnittet kan det forstås at i glibc sortering er basert på en algoritme som allerede er kjent for oss ACU (Unicode-kollasjonsalgoritmen) og/eller på en standard nær det ISO 14651 (Internasjonal strengbestilling og sammenligning). Når det gjelder den nyeste standarden, bør det bemerkes at på nettstedet standards.iso.org ISO 14651 offisielt erklært offentlig tilgjengelig, men den tilsvarende lenken fører til en ikke-eksisterende side. Google returnerer flere sider med lenker til offisielle nettsteder som tilbyr å kjøpe en elektronisk kopi av standarden for hundre euro, men på den tredje eller fjerde siden med søkeresultater er det også direkte lenker til PDF. Generelt er standarden praktisk talt ikke forskjellig fra ACU, men er kjedeligere å lese fordi den ikke inneholder klare eksempler på nasjonale trekk ved strengsortering.

Den mest interessante informasjonen om wiki det var en link til feilsporer med en diskusjon av implementeringen av strengsammenligning i glibc. Det kan man lære av diskusjonen glibc brukes til å sammenligne strenger ISOpersonlig bord Den vanlige maltabellen (CTT), som du finner adressen til i søknaden A standarden ISO 14651. Mellom 2000 og 2015 denne tabellen i glibc hadde ikke en vedlikeholder og var ganske forskjellig (i det minste eksternt) fra gjeldende versjon av standarden. Fra 2015 til 2018 skjedde tilpasning til den nye versjonen av bordet, og nå har du sjansen til å møte en ny versjon av bordet i virkeligheten (8 CentOS), og gamle (7 CentOS).

Nå som vi har all informasjonen om algoritmen og hjelpetabellene, kan vi gå tilbake til det opprinnelige problemet og forstå hvordan vi sorterer strenger riktig i den russiske lokaliteten.

ISO 14651/14652

Kildekoden til tabellen vi er interessert i CTT på de fleste distribusjoner Linux er i katalogen /usr/share/i18n/locales/. Selve tabellen er i filen iso14651_t1_common. Da er dette fildirektivet kopier iso14651_t1_common inkludert i filen iso14651_t1, som igjen er inkludert i nasjonale filer, bl.a no и ru_ru. På de fleste distribusjoner Linux alle kildefilene er inkludert i den grunnleggende installasjonen, men hvis de ikke er til stede, må du installere en ekstra pakke fra distribusjonen.

Filstruktur iso14651_t1 kan virke fryktelig ordrik, med ikke-opplagte regler for å konstruere navn, men hvis du ser på det, er alt ganske enkelt. Strukturen er beskrevet i standarden ISO 14652, en kopi av denne kan lastes ned fra nettstedet open-std.org. En annen beskrivelse av filformatet kan leses inn spesifikasjoner POSIX fra OpenGroup. Som et alternativ til å lese standarden kan du studere kildekoden til funksjonen collate_read в glibc/locale/programs/ld-collate.c.

Filstrukturen ser slik ut:

Som standard brukes tegnet som et escape-tegn, og slutten av linjen etter #-tegnet er en kommentar. Begge symbolene kan omdefineres, noe som er gjort i den nye versjonen av tabellen:

escape_char /
comment_char %

Filen vil inneholde tokens i formatet eller (hvor x - heksadesimalt siffer). Dette er den heksadesimale representasjonen av Unicode-kodepunkter i koding UCS-4 (UTF-32). Alle andre elementer i vinkelparenteser (inkludert , <2> og lignende) anses som enkle strengkonstanter som har liten betydning utenfor konteksten.

Linje LC_SAMLER forteller oss at deretter begynner dataene som beskriver sammenligningen av strenger.

Først angis navn for vektene i sammenligningstabellen og navn for symbolkombinasjonene. Generelt sett tilhører de to typene navn to forskjellige enheter, men i selve filen er de blandet. Navnene på vektene er spesifisert av nøkkelordet samle-symbol (sammenligningstegn) fordi når man sammenligner, vil Unicode-tegn som har samme vekt anses som likeverdige tegn.

Den totale lengden på seksjonen i gjeldende filrevisjon er ca. 900 linjer. Jeg hentet eksempler fra flere steder for å vise navnenes vilkårlighet 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>"

samlesymbol logger en streng OSMANYA i tabellen over navn på vekter
sammenstillingssymbol .. registrerer en sekvens av navn som består av et prefiks S og heksadesimalt numerisk suffiks fra 1D000 til 1D35F.
FFFF в sammenstillingssymbol ser ut som et stort heltall uten fortegn i heksadesimal, men det er bare et navn som kan se ut
navn betyr kodepunkt i koding UCS-4
sorteringselement fra «» registrerer et nytt navn for et par Unicode-punkter.

Når navnene på vektene er definert, spesifiseres de faktiske vektene. Siden bare større enn mindre relasjoner betyr noe i sammenligning, bestemmes vektene av en enkel sekvens av listenavn. De "lettere" vektene vises først, deretter de "tyngre". La meg minne deg på at hvert Unicode-tegn er tildelt fire forskjellige vekter. Her er de kombinert til en enkelt ordnet sekvens. I teorien kan et hvilket som helst symbolsk navn brukes på hvilket som helst av de fire nivåene, men kommentarer indikerer at utviklerne mentalt skiller navn inn 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

Til slutt, selve vekttabellen.

Vektdelen er omsluttet av søkeordlinjer ordre_start и ordreslutt. Ekstra alternativer ordre_start bestemme i hvilken retning rader skannes på hvert sammenligningsnivå. Standardinnstillingen er fremover. Hoveddelen av seksjonen består av linjer som inneholder symbolkoden og dens fire vekter. Tegnkoden kan representeres av selve tegnet, et kodepunkt eller et symbolsk navn definert tidligere. Vekter kan også gis til symbolske navn, kodepunkter eller selve symbolene. Hvis kodepunkter eller tegn brukes, er vekten deres den samme som den numeriske verdien til kodepunktet (posisjon i Unicode-tabellen). Tegn som ikke er spesifisert eksplisitt (som jeg forstår) anses som tildelt tabellen med en primærvekt som samsvarer med posisjonen i Unicode-tabellen. Spesiell vektverdi OVERSE betyr at symbolet ignoreres på riktig sammenligningsnivå.

For å demonstrere strukturen til skalaene, valgte jeg tre ganske åpenbare fragmenter:

tegn som ignoreres fullstendig
symboler som tilsvarer tallet tre i de to første nivåene
begynnelsen av det kyrilliske alfabetet, som ikke inneholder diakritiske tegn, og derfor er sortert hovedsakelig etter første og tredje nivå.

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

Nå kan du gå tilbake til å sortere eksemplene fra begynnelsen av artikkelen. Bakholdet ligger i denne delen av vekttabellen:

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

Det kan sees at i denne tabellen skilletegnene fra tabellen ASCII (inkludert mellomrom) blir nesten alltid ignorert når man sammenligner strenger. De eneste unntakene er linjer som samsvarer i alt bortsett fra skilletegn som finnes i samsvarende posisjoner. Linjene fra eksemplet mitt (etter sortering) for sammenligningsalgoritmen ser slik ut:

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

Med tanke på at i skalatabellen kommer store bokstaver på russisk etter små bokstaver (på tredje nivå tyngre enn ), ser sorteringen helt riktig ut.

Når du angir en variabel LC_COLLATE=C en spesiell tabell lastes inn som spesifiserer 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'
};

Siden kodepunktet Ё i Unicode kommer før A, er strengene sortert deretter.

Tekst og binære tabeller

Tydeligvis er strengsammenligning en ekstremt vanlig operasjon, og tabellparsing CTT en ganske kostbar prosedyre. For å optimalisere tilgangen til tabellen, kompileres den til binær form med kommandoen lokaldef.

Lag lokaldef godtar som parametere en fil med en tabell over nasjonale kjennetegn (opsjon -i), der alle tegn er representert av Unicode-punkter, og en fil med korrespondanse mellom Unicode-punkter og tegn med en spesifikk koding (alternativ -f). Som et resultat av arbeidet opprettes binære filer for lokaliteten med navnet angitt i den siste parameteren.

glibc støtter to binære filformater: "tradisjonell" og "moderne".

Det tradisjonelle formatet betyr at navnet på lokaliteten er navnet på underkatalogen i /usr/lib/locale/. Denne underkatalogen lagrer binære filer LC_SAMLER, LC_CTYPE, LC_TIME og så videre. Fil LC_IDENTIFIKASJON inneholder det formelle navnet på lokaliteten (som kan være forskjellig fra katalognavnet) og kommentarer.

Det moderne formatet innebærer å lagre alle lokaliteter i ett enkelt arkiv /usr/lib/locale/locale-archive, som er tilordnet det virtuelle minnet til alle prosesser som bruker glibc. Lokalnavnet i det moderne formatet er underlagt noe kanonisering - bare tall og bokstaver redusert til små bokstaver forblir i kodingsnavnene. Så ru_RU.KOI8-R, vil bli lagret som ru_RU.koi8r.

Inndatafiler søkes i gjeldende katalog, så vel som i kataloger /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ for filer CTT og kodingsfiler, henholdsvis.

For eksempel kommandoen

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

vil kompilere filen /usr/share/i18n/locales/ru_RU ved hjelp av kodingsfil /usr/share/i18n/charmaps/MAC-CYRILLIC.gz og lagre resultatet i /usr/lib/locale/locale-archive under navnet ru_RU.maccyrillic

Hvis du setter variabelen LANG = no_US.UTF-8 at glibc vil se etter lokale binære filer i følgende sekvens av 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 en lokalitet forekommer i både tradisjonelle og moderne formater, prioriteres den moderne.

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

Forbereder sammenligningstabellen

Nå, bevæpnet med kunnskapen, kan du lage din egen ideelle strengsammenligningstabell. Denne tabellen bør korrekt sammenligne russiske bokstaver, inkludert bokstaven Ё, og samtidig ta hensyn til skilletegn i samsvar med tabellen ASCII.

Prosessen med å lage din egen sorteringstabell består av to trinn: redigering av vekttabellen og kompilering til binær form med kommandoen lokaldef.

For at sammenligningstabellen skal justeres med minimale redigeringskostnader, i formatet ISO 14652 Seksjoner for justering av vektene til en eksisterende tabell er gitt. Avsnittet starter med et nøkkelord ombestille-etter og indikere posisjonen som utskiftingen utføres etter. Seksjonen avsluttes med linjen ombestilling-slutt. Hvis det er nødvendig å korrigere flere seksjoner av tabellen, opprettes en seksjon for hver slik seksjon.

Jeg kopierte nye versjoner av filene iso14651_t1_common и ru_ru fra depotet glibc til hjemmekatalogen min ~/.local/share/i18n/locales/ og redigerte delen litt LC_SAMLER в ru_ru. Nye versjoner av filer er fullt kompatible med min versjon glibc. Hvis du vil bruke eldre versjoner av filer, må du endre de symbolske navnene og stedet 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ødvendig å endre feltene i LC_IDENTIFIKASJON slik at de peker på lokaliteten ru_MY, men i mitt eksempel var dette ikke nødvendig, siden jeg ekskluderte arkivet fra søket etter lokaliteter locale-arkiv.

At lokaldef jobbet med filer i mappen min gjennom en variabel I18NPATH Du kan legge til en ekstra katalog for å søke etter inndatafiler, og katalogen for å lagre binære filer kan spesifiseres som en bane med skråstreker:

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

POSIX antar at i SPRÅK du kan skrive absolutte baner til kataloger med lokalitetsfiler, og starter med en skråstrek, men glibc в Linux alle stier telles fra basiskatalogen, som kan overstyres gjennom en variabel LOCPATH. Etter installasjon LOCPATH=~/.local/lib/locale/ alle filer relatert til lokalisering vil bare bli søkt i mappen min. Arkiv over lokaliteter med variabelsettet LOCPATH ignorert.

Her er den avgjørende testen:

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

Hurra! Vi gjorde det!

Noen feil

Jeg har allerede svart på spørsmålene om strengsortering stilt i begynnelsen, men det er fortsatt et par spørsmål om feil - synlige og usynlige.

La oss gå tilbake til det opprinnelige problemet.

Og programmet Sorter og programmet bli medlem bruk de samme strengsammenligningsfunksjonene fra glibc. Hvordan skjedde det bli medlem ga en sorteringsfeil på rader sortert etter kommandoen Sorter i lokalitet no_US.UTF-8? Svaret er enkelt: Sorter sammenligner hele strengen, og bli medlem sammenligner bare nøkkelen, som som standard er begynnelsen på strengen opp til det første mellomromstegn. I mitt eksempel resulterte dette i en feilmelding fordi sorteringen av de første ordene i linjene ikke stemte med sorteringen av de komplette linjene.

Språk "C" garanterer at i sorterte strenger vil de første delstrengene opp til det første rommet også sorteres, men dette maskerer bare feilen. Det er mulig å velge data (personer med samme etternavn, men forskjellige fornavn) som uten feilmeldingen ville gitt feil filsammenslåingsresultat. Hvis vi vil bli medlem sammenslåtte fillinjer med fullt navn, så ville den riktige måten være å spesifisere feltseparatoren eksplisitt og sortere etter nøkkelfeltet, og ikke etter hele linjen. I dette tilfellet vil sammenslåingen fortsette på riktig måte, og det vil ikke være noen feil i noen lokalitet:

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

Vellykket utført eksempel i koding CP1251 inneholder en annen feil. Faktum er at i alle distribusjoner kjent for meg Linux pakker mangler kompilert lokalitet ru_RU.CP1251. Hvis den kompilerte lokaliteten ikke blir funnet, da Sorter bruker lydløst en byte-for-byte-sammenligning, som er det vi observerte.

Forresten, det er en annen liten feil relatert til utilgjengeligheten til kompilerte lokaliteter. Team LOCPATH=/tmp-lokale -a vil gi en liste over alle lokaliteter i locale-arkiv, men med variabelsettet LOCPATH for alle programmer (inkludert de fleste lokale) disse lokalene vil ikke være tilgjengelige.

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

Konklusjon

Hvis du er en programmerer som er vant til å tro at strenger er et sett med byte, så er ditt valg LC_COLLATE=C.

Hvis du er en lingvist eller ordbokkompilator, bør du kompilere på ditt lokale område.

Hvis du er en enkel bruker, trenger du bare å venne deg til det faktum at kommandoen ls -a sender ut filer som starter med en prikk blandet med filer som begynner med en bokstav, og Midnattssjef, som bruker sine interne funksjoner til å sortere navn, setter filer som starter med en prikk i begynnelsen av listen.