Inleiding

Dit het alles begin met 'n kort draaiboek wat veronderstel was om inligting oor adresse te kombineer e-pos werknemers verkry uit die lys van poslysgebruikers met werknemerposisies verkry vanaf die HR-databasis. Albei lyste is na Unicode-tekslêers uitgevoer. UTF-8 en gestoor met Unix-lyn eindes.

inhoud pos.txt

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

inhoud buhg.txt

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

Om saam te smelt, is die lêers volgens die Unix-opdrag gesorteer soort en voorgelê aan die insette van die Unix-program sluit, wat onverwags geëindig het met die fout:

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

Deur die sorteringsresultaat met die oë te bekyk, het getoon dat die sortering oor die algemeen korrek is, maar in die geval van toevallighede van manlike en vroulike vanne, gaan die vroulikes voor die manlikes:

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

Lyk soos 'n sorteerfout in Unicode of soos 'n manifestasie van feminisme in die sorteeralgoritme. Die eerste is natuurlik meer aanneemlik.

Kom ons stel dit vir eers uit sluit en fokus op soort. Kom ons probeer om die probleem op te los deur die metode van wetenskaplike steek. Verander eers die plek van nl_NL> op ru_RU. Vir sortering sal dit genoeg wees om die omgewingsveranderlike in te stel LC_COLLATE, maar ons sal nie tyd mors op kleinighede nie:

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

Niks het verander nie.

Kom ons probeer om die lêers in 'n enkelgreep-kodering te herkodeer:

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

Weereens, niks het verander nie.

Niks kan gedoen word nie, jy moet 'n oplossing op die internet soek. Daar is niks direk oor Russiese vanne nie, maar daar is vrae oor ander sorteer vreemdhede. Hier is byvoorbeeld 'n probleem: unix sort behandel '-' (streep) karakters as onsigbaar. Kortom, die stringe "ab", "aa", "ac" word gesorteer as "aa", "ab", "ac".

Die antwoord is oral standaard: gebruik die programmeerder se ligging "C" en jy sal gelukkig wees. Ons probeer:

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

Iets het verander. Die Ivanovs het in die regte volgorde opgetree, hoewel Yolkina iewers gegly het. Kom ons gaan terug na die oorspronklike probleem:

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

Dit het sonder foute gewerk, soos deur die internet belowe. En dit ten spyte van Yolkina in die eerste reël.

Dit lyk of die probleem opgelos is, maar net vir ingeval, kom ons probeer 'n ander Russiese enkodering - Windows CP1251:

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

Die sorteerresultaat sal, vreemd genoeg, by die plek pas "C", en die hele voorbeeld gaan dus sonder foute verby. Een of ander mistikus.

Ek hou nie van mistiek in programmering nie, want dit verberg gewoonlik foute. Ons sal ernstig moet raak oor hoe dit werk. soort en wat beïnvloed LC_COLLATE .

Aan die einde sal ek probeer om die vrae te beantwoord:

waarom vroue se vanne verkeerd gesorteer is
hoekom LANG=ru_RU.CP1251 blyk die ekwivalent te wees LANG=C
hoekom u soort и sluit verskillende idees oor die volgorde van gesorteerde snare
hoekom is daar foute in al my voorbeelde
uiteindelik hoe om stringe na jou smaak te sorteer

Sorteer in Unicode

Eerste stop sal tegniese verslag #10 getiteld wees Unicode-kollasie-algoritme aanlyn unicode.org. Die verslag bevat baie tegniese besonderhede, so ek sal die vrymoedigheid neem om 'n opsomming van die hoofgedagtes te gee.

Kollasie - "vergelyking" van snare is die basis van enige sorteeralgoritme. Die algoritmes self kan verskil ("borrel", "smelt saam", "vinnig"), maar hulle sal almal 'n vergelyking van 'n paar snare gebruik om hul volgorde te bepaal.

Om stringe in natuurlike taal te sorteer is 'n taamlik moeilike probleem. Selfs in die eenvoudigste enkelgreep-enkoderings sal die volgorde van letters in die alfabet, selfs al is dit ietwat anders as die Engelse Latynse alfabet, nie meer saamval met die volgorde van die numeriese waardes waarmee hierdie letters geënkodeer word nie. So in die Duitse alfabet die letter Ö tussen staan О и P, en in die enkodering CP850 sy val tussen ÿ и Ü.

Jy kan probeer om weg te abstraheer van die spesifieke enkodering en oorweeg "ideale" letters wat in een of ander volgorde gerangskik is, soos in Unicode gedoen word. Enkoderings UTF8, UTF16 of enkelgreep KOI8-R (indien 'n beperkte subset van Unicode benodig word) sal verskillende numeriese voorstellings van die letters gee, maar verwys na dieselfde basistabelelemente.

Dit blyk dat selfs al bou ons 'n simbooltabel van nuuts af, kan ons nie 'n universele simboolorde daaraan toeken nie. In verskillende nasionale alfabette wat dieselfde letters gebruik, kan die volgorde van hierdie letters verskil. Byvoorbeeld, in Frans Æ sal as 'n ligatuur behandel word en as 'n tou gesorteer word AE. In die Noorse taal Æ sal 'n aparte brief wees, wat na geleë is Z. Terloops, afgesien van ligature soos Æ daar is letters wat met verskeie karakters geskryf is. So in die Tsjeggiese alfabet is daar 'n letter Ch, wat tussen staan H и I.

Benewens die verskil in alfabette, is daar ander nasionale tradisies wat sortering beïnvloed. Veral die vraag ontstaan: in watter volgorde moet woorde wat uit hoofletters en kleinletters bestaan in die woordeboek verskyn? Sortering kan ook beïnvloed word deur die eienaardighede van die gebruik van leestekens. In Spaans word 'n onderstebo vraagteken aan die begin van 'n ondervragende sin geplaas (Hou jy van musiek?). In hierdie geval is dit voor die hand liggend dat ondervragende sinne nie in 'n aparte groepie buite die alfabet gegroepeer moet word nie, maar hoe om lyne met verskillende leestekens te sorteer?

Ek sal nie stilstaan by stringsortering in tale wat baie anders as Europese tale is nie. Let daarop dat tale van regs na links of bo-na-onder geneig is om karakters in reëls in leesvolgorde te stoor, en selfs nie-alfabetiese skrifte het hul eie manier om reëls karakter-vir-karakter te orden. Byvoorbeeld, hiërogliewe kan volgens styl gerangskik word (Chinese karaktersleutels) of deur uitspraak. Hoe emoji bestel moet word, ek het eerlikwaar geen idee nie, maar jy kan aan iets vir hulle dink.

Gebaseer op die kenmerke hierbo gelys, is die hoofvereistes vir die vergelyking van stringe gebaseer op Unicode-tabelle geformuleer:

stringvergelyking hang nie af van die posisie van karakters in die kodetabel nie;
reekse karakters wat 'n enkele karakter vorm, word gereduseer tot die kanonieke vorm (A + die boonste sirkel is dieselfde as Å);
wanneer stringe vergelyk word, word 'n karakter in die konteks van 'n string beskou en, indien nodig, gekombineer met bure in een eenheid van vergelyking (Ch in Tsjeggies) of verdeel in verskeie (Æ in Frans);
alle nasionale kenmerke (alfabet, hoofletters/kleinletters, leestekens, volgorde van skryftipes) moet gekonfigureer word tot handmatige toewysing van die volgorde (emoji);
vergelyking is nie net belangrik vir sortering nie, maar ook op baie ander plekke, byvoorbeeld om reekse stringe te spesifiseer (vervang {A ... z} in bash);
vergelyking moet vinnig genoeg wees.

Daarbenewens het die skrywers van die verslag vergelykingseienskappe geformuleer waarop algoritme-ontwikkelaars nie moet staatmaak nie:

die vergelykingsalgoritme moet nie 'n aparte karakterstel vir elke taal vereis nie (Russiese en Oekraïense tale deel die meeste Cyrilliese karakters);
die vergelyking moet nie gebaseer wees op die volgorde van karakters in Unicode-tabelle nie;
die gewig van die tou moet nie 'n kenmerk van die tou wees nie, aangesien dieselfde tou in verskillende kulturele kontekste verskillende gewigte kan hê;
ry gewigte kan verander wanneer saamgevoeg of verdeel word (van x < y dit volg nie daarop nie xz < yz);
verskillende stringe wat dieselfde gewigte het, word as gelyk beskou in terme van die sorteeralgoritme. Die bekendstelling van addisionele ordening van sulke snare is moontlik, maar dit kan prestasie verswak;
rye met dieselfde gewigte kan tydens herhaalde sorterings omgeruil word. Volharding is 'n eienskap van 'n bepaalde sorteeralgoritme, nie 'n eienskap van die stringvergelykingsalgoritme nie (sien vorige punt);
sorteerreëls kan met verloop van tyd verander namate kulturele praktyke verfyn/verander word.

Daar word ook bepaal dat die vergelykingsalgoritme niks weet van die semantiek van die verwerkte snare nie. Strings wat slegs uit getalle bestaan, moet dus nie as getalle vergelyk word nie, en in lyste Engelse name moet die artikel nie verwyder word nie (Beatles, Die).

Ten einde aan al hierdie vereistes te voldoen, word 'n meervlakkige (eintlik viervlak) tabelsorteeralgoritme voorgestel.

Voorheen is die karakters in die string omgeskakel na kanonieke vorm en in vergelykingseenhede gegroepeer. Elke eenheid van vergelyking word verskeie gewigte toegeken wat ooreenstem met verskeie vlakke van vergelyking. Die gewigte van eenhede van vergelyking is elemente van geordende stelle (in hierdie geval heelgetalle) wat vir min of meer vergelyk kan word. spesiale betekenis geïgnoreer (0x0) beteken dat hierdie eenheid nie by die vergelyking op die ooreenstemmende vlak van vergelyking betrokke is nie. Die snaarvergelyking kan verskeie kere herhaal word deur die gewigte van die toepaslike vlakke te gebruik. Op elke vlak word die gewigte van die vergelykingseenhede van twee stringe opeenvolgend met mekaar vergelyk.

In verskillende implementerings van die algoritme vir verskillende nasionale tradisies, kan die waardes van die koëffisiënte verskil, maar die Unicode-standaard sluit 'n basiese gewigtabel in - "Verstek Unicode-kollasie-elementtabel" (DUCET). Ek wil daarop let dat die instelling van die veranderlike LC_COLLATE is eintlik 'n aanduiding van die keuse van die gewigtabel in die string vergelyking funksie.

Gewigskoëffisiënte DUCET soos volg gerangskik:

op die eerste vlak word alle letters tot dieselfde hoofletters verminder, diakritiese tekens word weggegooi, leestekens (nie almal nie) word geïgnoreer;
op die tweede vlak word slegs diakritiese tekens in ag geneem;
die derde vlak is slegs geval;
op die vierde vlak word slegs leestekens in ag geneem.

Die vergelyking vind in verskeie passe plaas: eerstens word die koëffisiënte van die eerste vlak vergelyk; as die gewigte ooreenstem, dan word dit weer vergelyk met die gewigte van die tweede vlak; dan miskien 'n derde en 'n vierde.

Die vergelyking eindig wanneer die stringe ooreenstemmende vergelykingseenhede met verskillende gewigte bevat. Rye wat gelyke gewigte op al vier vlakke het, word as gelyk aan mekaar beskou.

Hierdie algoritme (met 'n klomp bykomende tegniese besonderhede) het die naam gegee om #10 te rapporteer - Unicode Collation Algoritme (ACU).

Dit is hier waar die sorteergedrag uit ons voorbeeld 'n bietjie duideliker word. Dit sal lekker wees om dit met die Unicode-standaard te vergelyk.

Vir die toets van implementerings ACU daar is 'n spesiale die toetsgebruik gewig lêer, besef DUCET. In die gewigte-lêer kan jy verskeie vermaaklikheid vind. Daar is byvoorbeeld die volgorde van mahjong en Europese domino's, sowel as die volgorde van pakke in 'n pak kaarte (simbool 1F000 en verder). Kaartpakke word geplaas volgens die reëls van die brug - PCBT, en kaarte in die pak - in die volgorde T,2,3 ... K.

Handmatige verifikasie van die korrekte sortering van snare in ooreenstemming met DUCET sal nogal vervelig wees, maar gelukkig vir ons is daar 'n verwysingsbiblioteekimplementering om met Unicode te werk - "Internasionale komponente vir Unicode"(ICU).

Op die webwerf van hierdie biblioteek, ontwikkel in IBM, daar is demo bladsye, insluitend string vergelyking algoritme bladsy. Ons voer ons toetsstringe in met verstekinstellings en kyk en kyk, ons kry die perfekte Russiese sortering.

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

Terloops, die webwerf ICU jy kan 'n verfyning van die vergelykingsalgoritme vind wanneer leestekens verwerk word. In die voorbeelde Insameling Gereelde Vrae apostrof en koppelteken word geïgnoreer.

Unicode het ons gehelp, maar soek die oorsake van vreemde gedrag soort в Linux sal iewers anders moet gaan.

Sorteer in glibc

Vinnige oorsig van nutsbronkodes soort van GNU Core Utils het getoon dat in die nut self, lokalisering neerkom op die druk van die huidige waarde van die veranderlike LC_COLLATE wanneer dit in ontfoutingsmodus uitgevoer word:

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

Stringvergelyking word deur die standaardfunksie uitgevoer strcoll, wat beteken dat alles wat interessant is in die biblioteek is glibc.

Op wiki die projek glibc toegewy aan snaarvergelyking een paragraaf. Uit hierdie paragraaf kan dit verstaan word dat glibc sortering is gebaseer op die algoritme wat reeds aan ons bekend is ACU (Die Unicode-kollasie-algoritme) en/of op 'n standaard naby daaraan ISO 14651 (Internasionale string ordening en vergelyking). Met betrekking tot die nuutste standaard, moet daarop gelet word dat op die webwerf standards.iso.org ISO 14651 amptelik openbaar verklaar, maar die ooreenstemmende skakel lei na 'n nie-bestaande bladsy. Google gee verskeie bladsye uit met skakels na amptelike webwerwe wat aanbied om 'n elektroniese kopie van die standaard vir honderd euro te koop, maar op die derde of vierde bladsy van die soekresultate is daar ook direkte skakels na PDF. Oor die algemeen verskil die standaard feitlik nie van ACU, maar dit lees meer vervelig omdat dit nie aanskoulike voorbeelde van nasionale kenmerke van stringsortering bevat nie.

Die interessantste inligting wiki daar was 'n skakel na gogga spoorsnyer met 'n bespreking van die implementering van string vergelyking in glibc. Uit die bespreking kan gesien word dat glibc vir string vergelyking word gebruik ISOshnaya tafel Die algemene sjabloon tabel (CTT), waarvan die adres in die aansoek gevind kan word A standaard ISO 14651. Tussen 2000 en 2015 hierdie tabel in glibc het nie 'n onderhouer gehad nie en was heeltemal anders (ten minste uiterlik) van die huidige weergawe van die standaard. Van 2015 tot 2018 was daar 'n aanpassing by die nuwe weergawe van die tabel, en op die oomblik het jy 'n kans om in die werklike lewe te ontmoet as 'n nuwe weergawe van die tabel (CentOS 8) en die ou een (CentOS 7).

Noudat ons al die inligting oor die algoritme en hulptabelle het, kan ons terugkeer na die oorspronklike probleem en verstaan hoe om stringe behoorlik in die Russiese plek te sorteer.

ISO 14651 / 14652

Die bronkode van die tabel waarin ons belangstel CTT op die meeste verspreidings Linux is in die gids /usr/share/i18n/locales/. Die tabel self is in die lêer iso14651_t1_algemeen. Dan is hierdie lêer 'n opdrag kopieer iso14651_t1_common ingesluit in die lêer iso14651_t1, wat op sy beurt in nasionale lêers ingesluit is, insluitend nl_NL> и ru_RU. Op die meeste verspreidings Linux alle bronlêers is by die basisinstallasie ingesluit, maar as dit nie is nie, sal jy 'n bykomende pakket vanaf die verspreiding moet installeer.

Lêerstruktuur iso14651_t1 kan verskriklik verbose lyk, met nie-vanselfsprekende reëls vir die bou van name, maar as jy dit uitvind, is alles redelik eenvoudig. Die struktuur word in die standaard beskryf ISO 14652, waarvan 'n kopie van die webwerf afgelaai kan word oop-std.org. Nog 'n beskrywing van die lêerformaat kan gevind word in spesifikasies POSIX van oop groep. As alternatief vir die lees van die standaard, kan jy die brontekste van die funksie bestudeer versamel_lees в glibc/locale/programs/ld-collate.c.

Die lêerstruktuur lyk soos volg:

By verstek word die karakter as 'n ontsnappingskarakter gebruik, en die einde van die reël na die # karakter is 'n opmerking. Beide simbole kan herdefinieer word, wat in die nuwe weergawe van die tabel gedoen word:

escape_char /
comment_char %

Die lêer sal tekens in die formaat bevat of (Waar x is 'n heksadesimale syfer). Dit is die heksadesimale voorstelling van Unicode-kodepunte in die enkodering UCS-4 (UTF-32). Alle ander elemente in hoekhakies (insluitend , <2> en dies meer) word beskou as eenvoudige stringkonstantes wat nie veel sin maak buite konteks nie.

ry LC_COLLATE vertel ons dat data wat stringvergelykings beskryf volgende begin.

Eerstens word name gegee vir gewigte in die vergelykingstabel en name vir karakterkombinasies. Oor die algemeen behoort twee tipes name aan twee verskillende entiteite, maar in die werklike lêer is hulle deurmekaar. Die name van gewigte word deur die sleutelwoord gegee versamelsimbool (vergelykingskarakter) omdat Unicode-karakters wat dieselfde gewigte het as ekwivalente karakters hanteer sal word wanneer dit vergelyk word.

Die totale lengte van die afdeling in die huidige hersiening van die lêer is ongeveer 900 reëls. Ek het voorbeelde van verskeie plekke getrek om ewekansige name en verskeie soorte sintaksis te wys.

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

versamelsimbool teken 'n string aan OSMANYA in die skaalnaamtabel
versamelsimbool .. registreer 'n reeks name wat uit 'n voorvoegsel bestaan S en 'n heksadesimale numeriese agtervoegsel van 1D000 aan 1D35F.
FFFF в versamelsimbool lyk soos 'n groot ongetekende heelgetal in heksadesimale, maar dit is net 'n naam wat kan lyk
naam beteken kodepunt in enkodering UCS-4
versamelingselement van" " registreer 'n nuwe naam vir 'n paar unicode-kolletjies.

Sodra die name van die gewigte gedefinieer is, word die werklike gewigte gespesifiseer. Aangesien slegs groter-minder verhoudings saak maak in vergelyking, word die gewigte bepaal deur 'n eenvoudige volgorde van opsommende name. Die "ligter" gewigte word eerste gelys, dan die "swaarder" gewigte. Ter herinnering, aan elke Unicode-karakter word vier verskillende gewigte toegeken. Hier word hulle in 'n enkele geordende volgorde opgesom. Teoreties kan enige simboliese naam op enige van die vier vlakke gebruik word, maar die kommentaar dui daarop dat die ontwikkelaars die name verstandelik in vlakke skei.

% 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

Ten slotte, die werklike gewig tabel.

Die gewigsafdeling is in sleutelwoordlyne ingesluit bestel_begin и bestelling_einde. Ekstra opsies bestel_begin bepaal in watter rigting rye op elke vlak van vergelyking geskandeer word. Die verstekinstelling is vorentoe. Die liggaam van die afdeling bestaan uit reëls wat die karakterkode en sy vier gewigte bevat. 'n Karakterkode kan voorgestel word deur die karakter self, 'n kodepunt of 'n simboliese naam wat voorheen gedefinieer is. Gewigte kan ook aan simboliese name, kodepunte of die simbole self gegee word. As kodepunte of karakters gebruik word, is hul gewig dieselfde as die numeriese waarde van die kodepunt (posisie in die Unicode-tabel). Karakters wat nie eksplisiet (soos ek dit verstaan nie) word beskou as toegewys aan die tabel met 'n primêre gewig wat ooreenstem met die posisie in die Unicode-tabel. Spesiale gewig waarde IGNOREER beteken dat die gegewe karakter op die ooreenstemmende vlak van vergelyking geïgnoreer word.

Om die struktuur van die gewigte te demonstreer, het ek drie redelik duidelike fragmente gekies:

karakters wat heeltemal geïgnoreer word
karakters gelykstaande aan die getal drie in die eerste twee vlakke
die begin van die Cyrilliese alfabet, wat nie diakritiese tekens bevat nie, en daarom hoofsaaklik volgens die eerste en derde vlak gesorteer word.

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

Nou kan jy terugkeer na die sortering van die voorbeelde vanaf die begin van die artikel. Die hinderlaag lê in hierdie deel van die gewigtabel:

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

Dit kan gesien word dat in hierdie tabel die leestekens uit die tabel ASCII (insluitend spasie) word byna altyd geïgnoreer wanneer stringe vergelyk word. Die enigste uitsonderings is stringe wat in alles ooreenstem, behalwe vir leestekens wat in ooreenstemmende posisies voorkom. Die lyne van my voorbeeld (na sortering) vir die vergelykingsalgoritme lyk soos volg:

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

Aangesien in die gewigstabel hoofletters in Russies na kleinletters kom (op die derde vlak moeiliker as ), lyk die sortering absoluut korrek.

Wanneer 'n veranderlike opgestel word LC_COLLATE=C 'n spesiale tabel word gelaai wat 'n greep-vir-greep-vergelyking spesifiseer

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

Aangesien die Unicode-kodepunt Ё voor A kom, word die stringe dienooreenkomstig gesorteer.

Teks en binêre tabelle

Dit is duidelik dat stringvergelyking 'n uiters algemene bewerking is, en om 'n tabel te ontleed CTT nogal 'n duur prosedure. Om toegang tot die tabel te optimaliseer, word dit in binêre vorm saamgestel met die opdrag localdef.

Span localdef aanvaar as parameters 'n lêer met 'n tabel van nasionale kenmerke (opsie -i), waarin alle karakters deur Unicode-punte voorgestel word, en 'n Unicode-puntkarteringlêer vir karakters van 'n spesifieke enkodering (opsie -f). As gevolg van die werk word binêre lêers vir die locale geskep, met die naam gespesifiseer in die laaste parameter.

glibc ondersteun twee binêre lêerformate: "tradisioneel" en "modern".

Die tradisionele formaat impliseer dat die pleknaam die naam is van 'n subgids in /usr/lib/locale/. Hierdie subgids bevat die binaries LC_COLLATE, LC_CTYPE, LC_TIME en so aan. lêer LC_IDENTIFIKASIE bevat die formele pleknaam (wat dalk verskil van die gidsnaam) en opmerkings.

Die moderne formaat behels die stoor van alle plekke in 'n enkele argief /usr/lib/locale/locale-argief, wat gekarteer word na die virtuele geheue van alle prosesse wat gebruik word glibc. Die naam van die plek in die moderne formaat ondergaan 'n mate van kanonisering - slegs syfers en letters verminder tot kleinletters bly in die naam van die enkodering. Dus af_RU.KOI8-R, sal gestoor word as ru_RU.koi8r.

Invoerlêers word in die huidige gids gesoek, sowel as in gidse /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ vir lêers CTT en enkodering lêers, onderskeidelik.

Byvoorbeeld, die opdrag

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

sal die lêer saamstel /usr/share/i18n/locales/ru_RU met behulp van enkodering lêer /usr/share/i18n/charmaps/MAC-CYRILLIC.gz en stoor die resultaat in /usr/lib/locale/locale-argief onder die naam en_RU.maccyrillic

As jy 'n veranderlike stel Lang = en_US.UTF-8 dat glibc sal soek vir locale binaries in die volgende volgorde van lêers en gidse:

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

As 'n plek in beide die tradisionele en moderne formate voorkom, geniet die moderne een voorrang.

U kan die lys van saamgestelde plekke met die opdrag bekyk locale -a.

Berei jou vergelykingstabel voor

Nou, gewapen met kennis, kan jy jou eie ideale snaarvergelykingstabel skep. Hierdie tabel moet Russiese letters, insluitend die letter Ё, korrek vergelyk en terselfdertyd leestekens in ag neem in ooreenstemming met die tabel ASCII.

Die proses om jou sorteertabel voor te berei bestaan uit twee fases: redigeer die gewigstabel en stel dit in binêre vorm saam met die opdrag localdef.

Sodat die vergelykingstabel aangepas kan word met minimale redigeringskoste, in die formaat ISO 14652 afdelings vir die aanpassing van die gewigte van 'n bestaande tabel word verskaf. Afdeling begin met sleutelwoord herrangskik-na en spesifiseer die posisie waarna die vervanging uitgevoer word. Eindig die gedeelte met 'n lyn herrangskik-einde. As dit nodig is om verskeie afdelings van die tabel reg te stel, word 'n afdeling vir elke sodanige afdeling geskep.

Ek het die nuwe weergawes van die lêers gekopieer iso14651_t1_algemeen и ru_RU uit die bewaarplek glibc na jou tuisgids ~/.local/share/i18n/locales/ en het die afdeling effens gewysig LC_COLLATE в ru_RU. Die nuwe weergawes van die lêers is ten volle versoenbaar met my weergawe glibc. As jy ouer weergawes van lêers wil gebruik, sal jy die simboliese name en die plek waar die vervanging begin in die tabel moet verander.

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

Trouens, dit sou nodig wees om die velde in te verander LC_IDENTIFIKASIE sodat hulle na die plek wys af_MY, maar in my voorbeeld was dit nie nodig nie, aangesien ek die argief uitgesluit het van die soektog na locales locale-argief.

Wat localdef gewerk met lêers in my gids deur 'n veranderlike I18NPATH jy kan 'n bykomende gids byvoeg om na invoerlêers te soek, en die gids om binaries te stoor kan gespesifiseer word as 'n pad met skuinsstrepe:

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

POSIX stel voor dat in NET jy kan absolute paaie na gidse skryf met locale lêers, begin met 'n voorwaartse skuinsstreep, maar glibc в Linux alle paaie word vanaf die basisgids getel, wat deur 'n veranderlike oorskryf kan word LOCPATH. Na installasie LOCPATH=~/.local/lib/locale/ alle lêers wat met lokalisering verband hou, sal slegs in my gids gesoek word. Plaas argief wanneer veranderlike ingestel is LOCPATH geïgnoreer.

Hier is die finale toets:

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

Hoera! Ons het dit gedoen!

Bug werk

Ek het reeds die vrae oor die sortering van stringe, wat aan die begin gestel is, beantwoord, maar daar is nog 'n paar vrae oor foute - sigbaar en onsigbaar.

Kom ons keer terug na die oorspronklike probleem.

En die program soort en die program sluit gebruik dieselfde string vergelyking funksies vanaf glibc. Hoe het dit so gebeur sluit het 'n sorteerfout gegee op lyne wat volgens die opdrag gesorteer is soort in locale af_US.UTF-8? Die antwoord is eenvoudig: soort vergelyk die hele string, en sluit vergelyk slegs die sleutel, wat by verstek die begin van die string tot by die eerste witspasie karakter is. In my voorbeeld het dit 'n foutboodskap tot gevolg gehad omdat die sortering van die eerste woorde in die reëls nie ooreenstem met die sortering van die vol reëls nie.

locale "C" waarborg dat in die gesorteerde stringe die voorste substringe tot by die eerste spasie ook gesorteer sal word, maar dit masker net die fout. Dit is moontlik om sulke data op te tel (mense met dieselfde vanne, maar verskillende name), wat sonder 'n foutboodskap 'n verkeerde resultaat van die samevoeging van lêers sou gee. As ons wil sluit gekombineerde lêerlyne volgens volle naam, dan sal die korrekte manier wees om die veldskeier uitdruklik te spesifiseer en volgens die sleutelveld te sorteer, en nie volgens die hele reël nie. In hierdie geval sal die samevoeging ook korrek werk en daar sal geen foute in enige plek wees nie:

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

Gekodeerde voorbeeld suksesvol uitgevoer CP1251 bevat nog 'n fout. Die feit is dat in alle verspreidings wat aan my bekend is Linux pakkette ontbreek saamgestelde plek af_RU.CP1251. As die saamgestelde plek nie gevind word nie, dan soort gebruik stilweg greep-vir-greep vergelyking, wat is wat ons waargeneem het.

Terloops, daar is nog 'n klein fout wat verband hou met die ontoeganklikheid van saamgestelde plekke. Span LOCPATH=/tmp locale -a sal 'n lys van alle plekke in terugstuur locale-argief, maar met die veranderlike stel LOCPATH vir alle programme (insluitend die meeste plaaslike) hierdie plekke sal nie beskikbaar wees nie.

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

Gevolgtrekking

As jy 'n programmeerder is wat gewoond is om te dink dat snare 'n versameling grepe is, dan is jou keuse LC_COLLATE=C.

As jy 'n taalkundige of 'n woordeboeksamesteller is, moet jy beter jou plek saamstel.

As jy 'n eenvoudige gebruiker is, moet jy net gewoond raak aan die feit dat die opdrag ls -a druk lêers uit wat begin met 'n punt afgewissel met lêers wat met 'n letter begin, en Middernag bevelvoerder, wat sy interne funksies gebruik om name te sorteer, skuif lêers wat met 'n punt begin, na die voorkant van die lys.