Aféierung

Et huet alles ugefaang mat engem kuerze Skript deen Adressinformatioun kombinéiere sollt E-Mail Mataarbechter kritt aus der Lëscht vun Mailing Lëscht Benotzer, mat Employé Positiounen kritt aus der HR Departement Datebank. Béid Lëschte goufen op Unicode Textdateien exportéiert UTF-8 a gespäichert mat Unix Linn Endungen.

Inhalt mail.txt

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

Inhalt buhg.txt

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

Fir ze fusionéieren, goufen d'Dateie vum Unix Kommando zortéiert sortéieren an den Input vum Unix Programm ofgeliwwert anzeschreiwen, deen onerwaart mat engem Feeler gescheitert ass:

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

Wann Dir d'Sortéierungsresultat mat Ären Aen kuckt, huet gewisen datt allgemeng d'Sortéierung richteg ass, awer am Fall vun Zoufall vu männlechen a weibleche Familljennumm, kommen déi weiblech virun de männlechen:

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

Gesäit aus wéi e Sortéierungsfehler an Unicode oder wéi eng Manifestatioun vum Feminismus am Sortimentalgorithmus. Déi éischt ass, natierlech, méi plausibel.

Loosst eis et fir de Moment ofsetzen anzeschreiwen an konzentréieren op sortéieren. Loosst eis probéieren de Problem mat wëssenschaftleche Pocken ze léisen. Als éischt, loosst eis d'Lokaliséierung änneren en_US op ru_RU. Fir ze sortéieren, wier et genuch fir d'Ëmfeldvariabel ze setzen LC_COLLATE, awer mir verschwenden keng Zäit op Trifles:

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

Näischt geännert.

Loosst eis probéieren d'Dateien an eng Single-Byte Kodéierung ëmzekodéieren:

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

Erëm huet sech näischt geännert.

Et gëtt näischt wat Dir maache kënnt, Dir musst eng Léisung um Internet sichen. Et gëtt näischt direkt iwwer russesch Familljennumm, mä et gi Froen iwwer aner Zort oddities. Zum Beispill, hei ass e Problem: Unix Zort behandelt '-' (Dash) Charaktere als onsichtbar. Kuerz gesot, d'Saiten "a-b", "aa", "ac" ginn als "aa", "a-b", "ac" zortéiert.

D'Äntwert ass Standard iwwerall: benotzt de Programméierer Locale "C" an Dir wäert frou sinn. Loosst eis probéieren:

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

Eppes huet sech geännert. D'Ivanovs hu sech an der richteger Reiefolleg opgestallt, obwuel d'Yolkina iergendwou gerutscht ass. Loosst eis zréck op den urspréngleche Problem:

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

Et huet ouni Feeler geschafft, wéi den Internet versprach huet. An dat trotz Yolkina an der éischter Linn.

De Problem schéngt geléist ze sinn, awer just am Fall, loosst eis eng aner russesch Kodéierung probéieren - Windows CP1251:

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

D'Sortéierungsresultat, komesch genuch, wäert mat der Lokalitéit zesummefalen "C", an dat ganzt Beispill leeft deementspriechend ouni Feeler. Eng Aart vu Mystik.

Ech hu keng Mystik beim Programméiere gär well et normalerweis Feeler maskéiert. Mir mussen eescht kucke wéi et funktionéiert. sortéieren a wat beaflosst dat? LC_COLLATE .

Zum Schluss probéieren ech d'Froen ze beäntweren:

firwat goufen weiblech Familljennimm falsch zortéiert?
firwat LANG=ru_RU.CP1251 huet sech als gläichwäerteg erausgestallt LANG=C
firwat maachen sortéieren и anzeschreiwen verschidden Iddien iwwer d'Uerdnung vun zortéierten Saiten
firwat ginn et Feeler an all meng Beispiller?
endlech wéi Dir Strings no Äre Wënsch sortéiert

Sortéieren an Unicode

Den éischten Arrêt wäert technesch Bericht Nr 10 berechtegt sinn Unicode Collation Algorithmus online unicode.org. De Bericht enthält vill technesch Detailer, also loosst mech e kuerze Resumé vun den Haaptideeën ginn.

collation - "Vergläichen" Saiten ass d'Basis vun all Sortéierung Algorithmus. D'Algorithmen selwer kënnen ënnerscheeden ("Bubble", "Fusioun", "séier"), awer se benotzen all e Verglach vun e Paar Saiten fir d'Uerdnung ze bestëmmen an där se erscheinen.

D'Strings an der natierlecher Sprooch ze sortéieren ass e relativ komplexe Problem. Och an den einfachsten Single-Byte Kodéierungen, wäert d'Uerdnung vun de Buschtawen am Alphabet, och op iergendeng Manéier anescht wéi dat englesch Latäin Alphabet, net méi mat der Uerdnung vun den numeresche Wäerter zesummefalen, mat deenen dës Buschtawen kodéiert sinn. Also am däitsche Alphabet de Bréif Ö steet tëscht О и P, an an der Kodéierung CP850 si kritt tëscht ÿ и Ü.

Dir kënnt probéieren aus enger spezifescher Kodéierung ze abstrakt an "ideal" Buschtawen ze berücksichtegen, déi an iergendenger Uerdnung arrangéiert sinn, sou wéi et an Unicode gemaach gëtt. Kodéierungen UTF 8, UTF 16 oder eent-Byte KOI8-R (wann e limitéierten Ënnerdeel vun Unicode gebraucht gëtt) ginn verschidden numeresch Representatioune vu Buschtawen, awer bezéie sech op déiselwecht Elementer vun der Basistabell.

Et stellt sech eraus, datt och wa mir e Symbol Dësch vun Null bauen, mir wäerten net fäheg sinn eng universell Symbol Uerdnung ze zougewisen. A verschiddene nationalen Alfabeten déi déiselwecht Buschtawen benotzen, kann d'Uerdnung vun dëse Buschtawen ënnerschiddlech sinn. Zum Beispill op Franséisch Æ gëtt als Ligatur ugesinn an als String zortéiert AE. Op Norweegesch Æ wäert eng separat Bréif ginn, déi läit na Z. Iwwregens, nieft Ligaturen wéi Æ Et gi Bréiwer geschriwwen mat verschiddene Symboler. Also am tschecheschen Alphabet gëtt et e Bréif Ch, déi tëscht steet H и I.

Zousätzlech zu Differenzen an Alphabeten ginn et aner national Traditiounen déi d'Sortéierung beaflossen. Besonnesch stellt sech d'Fro: a wéi enger Reiefolleg sollen d'Wierder aus Grouss- a Klengbuschtawen am Wierderbuch optrieden? D'Sortéierung kann och duerch d'Benotzung vu Punktuéierungszeechen beaflosst ginn. Op Spuenesch gëtt en ëmgedréint Fragezeechen am Ufank vun engem interrogative Saz benotzt (Hutt Dir gär Musek?). An dësem Fall ass et evident datt Interrogativ Sätz net an e separaten Cluster ausserhalb vum Alphabet gruppéiere sollen, awer wéi d'Zeilen mat anere Punktuatiounszeechen ze sortéieren?

Ech wäert net op d'Sortéierung vu Strings a Sprooche ganz ënnerschiddlech vun europäeschen wunnen. Bedenkt datt a Sprooche mat enger riets-op-lénks oder uewe bis ënnen Schreifrichtung Zeechen an Zeilen héchstwahrscheinlech a Liesuerdnung gespäichert ginn, a souguer net-alphabetesch Schreifsystemer hunn hir eege Weeër fir Zeilen Charakter fir Charakter ze bestellen . Zum Beispill, Hieroglyphe kënnen no Stil bestallt ginn (Chinesesch Zeechen Schlësselen) oder duerch Aussprooch. Fir éierlech ze sinn, hunn ech keng Ahnung wéi Emojis solle arrangéiert ginn, awer Dir kënnt och eppes fir si kommen.

Baséierend op d'Features uewen opgezielt, goufen d'Basisfuerderunge fir d'Vergläiche vu Strings op Basis vun Unicode Dëscher formuléiert:

Verglach vu Strings hänkt net vun der Positioun vun den Zeechen an der Codetabelle of;
Sequenze vun Zeechen, déi en eenzege Charakter bilden, ginn op kanonesch Form reduzéiert (A + den Top Krees ass d'selwecht wéi Å);
Wann Dir Strings vergläicht, gëtt e Charakter am Kontext vum String ugesinn an, wann néideg, mat sengen Noperen an eng Eenheet vum Verglach kombinéiert (Ch op Tschechesch) oder ass an e puer opgedeelt (Æ op Franséisch);
all national Fonctiounen (Alphabet, grouss / kleng, Punktuatioun, Uerdnung vun Schreiwen Zorte) muss bis zu der manueller Aufgab vun der Uerdnung konfiguréiert ginn (Emoji);
De Verglach ass wichteg net nëmme fir ze sortéieren, awer och op villen anere Plazen, zum Beispill fir Zeilenberäicher ze spezifizéieren (ersetzen {A ... z} an ze brong);
de Verglach soll relativ séier gemaach ginn.

Zousätzlech hunn d'Autoren vum Bericht Vergläichseigenschaften formuléiert, op déi Algorithmus Entwéckler net sollten vertrauen:

de Verglach Algorithmus soll net eng separat Formatioun vun Zeeche fir all Sprooch verlaangen (Russesch an Ukrainesch Sproochen deelen déi meescht kyrillesch Zeechen);
de Verglach soll net op d'Uerdnung vun Zeechen an Unicode Dëscher vertrauen;
String Gewiicht soll net en Attribut vun der String ginn, well déi selwecht String a verschiddene kulturelle Kontexter verschidde Gewiichter hunn kann;
Reihegewichte kënne sech änneren wann se fusionéieren oder opzedeelen (vun x < y et geet dat net no xz < yz);
verschidde Saiten déi déiselwecht Gewiichter hunn, ginn aus der Siicht vum Sortéierungsalgorithmus als gläich ugesinn. Zousätzlech Uerdnung vun esou Strings aféieren ass méiglech, awer et kann d'Leeschtung degradéieren;
Wärend der widderholl Sortéierung kënne Reihen mat de selwechte Gewiichter ausgetauscht ginn. Robustheet ass e Besëtz vun engem spezifeschen Zortéieren Algorithmus, an net e Besëtz vun engem String Verglach Algorithmus (kuckt virdrun Paragraph);
Sortéierungsregele kënne mat der Zäit änneren wéi kulturell Traditiounen verfeineren / änneren.

Et ass och virgesinn datt de Verglachalgorithmus näischt iwwer d'Semantik vun de Strings weess, déi veraarbecht ginn. Also, Strings, déi nëmmen aus Ziffere besteet, däerfen net als Zuelen verglach ginn, an op Lëschte vun engleschen Nimm den Artikel (Beatles, op).

Fir all déi spezifizéiert Ufuerderungen ze erfëllen, gëtt e Multi-Level (tatsächlech véier-Niveau) Dësch Sortéierung Algorithmus proposéiert.

Virdrun sinn d'Zeechen am String op kanonesch Form reduzéiert an an Unitéiten vum Verglach gruppéiert. All Eenheet vum Verglach gëtt e puer Gewiichter zougewisen, déi zu e puer Niveaue vum Verglach entspriechen. D'Gewiichter vu Vergläichseenheeten sinn Elementer vun bestallte Sätze (an dësem Fall ganz Zuelen) déi méi oder manner verglach kënne ginn. Besonnesch Bedeitung IGNORÉIERT (0x0) heescht datt um entspriechende Vergläichsniveau dës Eenheet net am Verglach involvéiert ass. De Verglach vu Saiten kann e puer Mol widderholl ginn, andeems d'Gewichte vun den entspriechende Niveauen benotzt. Op all Niveau ginn d'Gewiichter vun de Vergläichseenheeten vun zwou Reihen sequentiell matenee verglach.

A verschiddenen Implementatiounen vum Algorithmus fir verschidden national Traditiounen kënnen d'Wäerter vun de Koeffizienten ënnerscheeden, awer den Unicode Standard enthält eng Basistabell vu Gewiichter - "Standard Unicode Collation Element Table" (DUCET). Ech géif gären notéieren datt d'Variabel setzen LC_COLLATE ass tatsächlech eng Indikatioun fir d'Auswiel vun der Gewiichtstabell an der Stringvergleichsfunktioun.

Gewiichtskoeffizienten DUCET arrangéiert wéi follegt:

um éischten Niveau sinn all Buschtawen op dee selwechte Fall reduzéiert, Diakritiker ginn verworf, Punktuéierungszeechen (net all) ignoréiert;
um zweeten Niveau ginn nëmmen Diakritik berécksiichtegt;
um drëtten Niveau gëtt nëmmen de Fall berücksichtegt;
um véierten Niveau ginn nëmmen d'Punctuatiounszeechen berécksiichtegt.

De Verglach fënnt an e puer Passë statt: éischtens ginn d'Koeffizienten vum éischte Niveau verglach; wann d'Gewiichter zesummekommen, da gëtt e widderholle Verglach mat den zweeten Niveau Gewiichter duerchgefouert; dann vläicht en Drëttel an e Véiert.

De Verglach endet wann d'Reihen passend Eenheete vum Verglach mat verschiddene Gewiichter enthalen. Reihen, déi gläichgewiicht op all véier Niveauen hunn, ginn als gläich matenee ugesinn.

Dësen Algorithmus (mat enger Rëtsch zousätzlech techneschen Detailer) huet den Numm vum Bericht Nummer 10 ginn - "Unicode Collatioun Algorithmus" (Uca).

Dëst ass wou d'Sortéierungsverhalen aus eisem Beispill e bësse méi kloer gëtt. Et wier flott et mam Unicode Standard ze vergläichen.

Fir Implementatiounen ze testen Uca et gëtt eng speziell Quiz, benotzt Gewiichter Fichier, Ëmsetzung DUCET. Dir kënnt all Zorte vu witzeg Saachen am Skala Fichier fannen. Zum Beispill gëtt et d'Uerdnung vu Mahjong an europäesch Dominoen, souwéi d'Uerdnung vun de Kostümer an enger Kaartespill (Symbol 1F000 a weider). D'Kaarte Kostümer sinn no de Regele vu Bréck plazéiert - PCBT, an d'Kaarte am Kostüm sinn an der Sequenz T, 2,3, XNUMX ... K.

Kontrolléiert manuell datt d'Zeilen korrekt no sortéiert sinn DUCET wier zimlech langweileg, awer, glécklecherweis fir eis, gëtt et eng exemplaresch Ëmsetzung vun der Bibliothéik fir mat Unicode ze schaffen - "International Komponente fir Unicode"(ICU).

Op der Websäit vun dëser Bibliothéik, entwéckelt an IBM, ginn et Demo Säiten, dorënner String Verglach Algorithmus Säit. Mir gitt eis Testlinnen mat Standardastellungen an, kuck, mir kréien perfekt russesch Sortéierung.

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

Iwwregens, der Websäit ICU Dir kënnt eng Klärung vum Verglachalgorithmus fannen wann Dir Punktuéierungszeechen veraarbecht. An de Beispiller Kollatioun FAQ Apostroph an Bindestrecken ginn ignoréiert.

Unicode huet eis gehollef, awer kuckt no Grënn fir komescht Verhalen sortéieren в Linux muss anzwousch anescht goen.

Sortéieren am Glibc

Quick Vue vun der Utility Quell Coden sortéieren aus GNU Core Utils huet gewisen datt am Utility selwer d'Lokaliséierung erof geet fir den aktuelle Wäert vun der Variabel ze drécken LC_COLLATE wann Dir am Debug Modus leeft:

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

String Vergläicher gi mat der Standardfunktioun ausgefouert strcoll, dat heescht alles wat interessant ass an der Bibliothéik glibc.

op Wiki de Projet glibc gewidmet fir Stringvergleich engem Paragraph. Aus dësem Paragraph kann et verstane ginn datt an glibc D'Sortéierung baséiert op engem Algorithmus deen eis scho bekannt ass Uca (Den Unicode Collation Algorithmus) an / oder op engem Standard no derbäi ISO 14651 (International String Uerdnung a Verglach). Wat d'läscht Standard ugeet, sollt et bemierkt datt op der Säit standards.iso.org ISO 14651 offiziell ëffentlech verfügbar deklaréiert, awer de entspriechende Link féiert op eng net existent Säit. Google bréngt e puer Säiten zréck mat Linken op offiziell Säiten, déi bidden eng elektronesch Kopie vum Standard fir honnert Euro ze kafen, awer op der drëtter oder véierter Säit vun de Sichresultater ginn et och direkt Linken op PDF. Am Allgemengen ass de Standard praktesch net anescht wéi Uca, awer ass méi langweileg ze liesen, well et keng kloer Beispiller vun nationalen Features vun der String-Sortéierung enthält.

De stäerkste interessant Informatiounen iwwert Wiki et war e Link op Käfer Tracker mat enger Diskussioun vun der Ëmsetzung vun String Verglach an glibc. Aus der Diskussioun kann een dat gewuer ginn glibc benotzt fir Strings ze vergläichen ISOperséinlech Dësch Déi gemeinsam Schabloun Dësch (CTT), d'Adress vun deem kann an der Applikatioun fonnt ginn A Standard ISO 14651. Tëscht 2000 an 2015 dëser Tabell an glibc hat keen Ënnerhalter a war ganz anescht (op d'mannst extern) vun der aktueller Versioun vum Standard. Vun 2015 bis 2018 ass d'Adaptatioun un déi nei Versioun vum Dësch stattfonnt, an elo hutt Dir eng Chance am richtege Liewen eng nei Versioun vum Dësch ze treffen (CentOS 8), an al (CentOS 7).

Elo, datt mir all d'Informatioun iwwer den Algorithmus an d'Hëllefstabellen hunn, kënne mir op den urspréngleche Problem zréckkommen a verstoen wéi d'Strings an der russescher Lokalitéit richteg sortéieren.

ISO 14651 / 14652

Quelltext vum Dësch mir interesséiert sinn CTT op déi meescht Verdeelungen Linux ass am Dossier /usr/share/i18n/locales/. Den Dësch selwer ass an der Datei iso14651_t1_common. Dann ass dëst d'Datei Direktiv kopéieren iso14651_t1_common am Dossier abegraff iso14651_t1, déi dann och an nationalen Dossieren opgeholl gëtt, inklusiv en_US и ru_RU. Op de meeschte Verdeelungen Linux All Quelldateien sinn an der Basisinstallatioun abegraff, awer wann se net präsent sinn, musst Dir en zousätzleche Package aus der Verdeelung installéieren.

Datei Struktur iso14651_t1 kann schrecklech verbose schéngen, mat net offensichtleche Regele fir Nimm ze bauen, awer wann Dir et kuckt, ass alles ganz einfach. D'Struktur ass am Standard beschriwwen ISO 14652, eng Kopie vun deem kann vun der Websäit erofgeluede ginn open-std.org. Eng aner Beschreiwung vum Dateiformat ka gelies ginn Spezifikatioune POSIX от OpenGroup. Als Alternativ fir de Standard ze liesen, kënnt Dir de Quellcode vun der Funktioun studéieren collate_liesen в glibc/locale/programs/ld-collate.c.

D'Dateistruktur gesäit esou aus:

Par défaut gëtt de Charakter als Flucht Charakter benotzt, an d'Enn vun der Zeil nom Charakter # ass e Kommentar. Béid Symboler kënnen nei definéiert ginn, dat ass wat an der neier Versioun vum Dësch gemaach gëtt:

escape_char /
comment_char %

De Fichier enthält Tokens am Format oder (Wou x - hexadezimal Ziffer). Dëst ass déi hexadezimal Representatioun vun Unicode Code Punkten an der Kodéierung UCS-4 (UTF-32). All aner Elementer an de Wénkelklammern (inklusiv , <2> an dergläiche) ginn als einfach Stringkonstanten ugesinn, déi wéineg Bedeitung ausserhalb vum Kontext hunn.

Linn LC_COLLATE erzielt eis datt nächst d'Daten ufänkt, déi de Verglach vu Strings beschreiwen.

Als éischt ginn d'Nimm fir d'Gewiichter an der Vergläichstabell uginn an d'Nimm fir d'Symbolkombinatiounen. Am Allgemengen gehéieren déi zwou Aarte vun Nimm zu zwou verschiddenen Entitéiten, awer an der aktueller Datei gi se gemëscht. D'Nimm vun de Gewiichter gi vum Schlësselwuert uginn Zesummesetzung-Symbol (Vergläich Charakter) well wann Dir vergläicht, Unicode Charaktere déi déiselwecht Gewiichter hunn, ginn als gläichwäerteg Zeechen ugesinn.

D'Gesamtlängt vun der Sektioun an der aktueller Dateirevisioun ass ongeféier 900 Zeilen. Ech hunn Beispiller aus e puer Plazen gezunn fir d'Arbiträrheet vun den Nimm a verschidden Aarte vu Syntax ze weisen.

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

collating-Symbol protokolléiert eng String OSMANYA an der Tabell vun Nimm vun Skalen
Zesummesetzung-Symbol .. registréiert eng Sequenz vun Nimm, déi aus engem Präfix besteet S an hexadezimal numeresch Suffix aus 1D000 ze Spezifikatioune vun 1D35F.
FFFF в collating-symbol gesäit wéi eng grouss unsigned ganzt an hexadecimal, mä et ass just en Numm deen ausgesäit
Numm heescht Code Punkt am Kodéierung UCS-4
Sammelelement vun "" registréiert en neien Numm fir e Paar Unicode Punkten.

Wann d'Nimm vun de Gewiichter definéiert sinn, ginn déi tatsächlech Gewiichter uginn. Zënter datt nëmme méi grouss wéi manner Relatiounen am Verglach wichteg sinn, ginn d'Gewiichter duerch eng einfach Sequenz vun Oplëschtungsnimm bestëmmt. Déi "liicht" Gewiichter ginn als éischt opgelëscht, dann déi "méi schwéier". Loosst mech Iech drun erënneren datt all Unicode Charakter véier verschidde Gewiichter zougewisen ass. Hei gi se an eng eenzeg bestallt Sequenz kombinéiert. An Theorie, kéint all symbolesch Numm op all vun de véier Niveauen benotzt ginn, mee Kommentaren weisen datt d'Entwéckler geeschteg Nimm an Niveauen trennen.

% 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

Endlech, déi tatsächlech Gewiicht Dësch.

D'Gewichte Sektioun ass a Schlësselwuertlinnen zougemaach order_start и order_end. Extra Optiounen order_start bestëmmen a wéi enger Richtung Zeile op all Niveau vum Verglach gescannt ginn. D'Default Astellung ass vir. De Kierper vun der Rubrik besteet aus Linnen déi de Symbol Code a seng véier Gewiichter enthalen. De Charaktercode kann duerch de Charakter selwer, e Codepunkt oder e symboleschen Numm vertruede ginn, dee virdru definéiert ass. Gewiichter kënnen och symbolesch Nimm ginn, Code Punkten oder d'Symboler selwer. Wann Code Punkten oder Charaktere benotzt ginn, ass hir Gewiicht d'selwecht wéi den numeresche Wäert vum Code Punkt (Positioun an der Unicode Dësch). Charaktere net explizit spezifizéiert (wéi ech verstinn) ginn ugesinn un den Dësch zougewisen mat engem primäre Gewiicht dat mat der Positioun an der Unicode Dësch entsprécht. Besonnesch Gewiicht Wäert Ignoréieren heescht datt d'Symbol um passenden Niveau vum Verglach ignoréiert gëtt.

Fir d'Struktur vun de Skalen ze demonstréieren, hunn ech dräi zimlech offensichtlech Fragmenter gewielt:

Charaktere déi komplett ignoréiert ginn
Symboler gläichwäerteg zu der Nummer dräi an den éischten zwee Niveauen
den Ufank vum kyrilleschen Alphabet, deen keng Diakritik enthält, an dofir haaptsächlech op den éischten an drëtten Niveau zortéiert ass.

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

Elo kënnt Dir zréck op d'Sortéierung vun de Beispiller vum Ufank vum Artikel. Den Ambush läit an dësem Deel vun der Gewiichtstabell:

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

Et kann gesi ginn datt an dëser Tabell d'Punctuatiounszeechen aus der Tabell sinn ASCII (inklusiv Raum) gëtt bal ëmmer ignoréiert wann Dir Strings vergläicht. Déi eenzeg Ausnahmen sinn Zeilen déi an alles passen ausser Punktuéierungszeechen, déi a passende Positiounen fonnt goufen. D'Linnen aus mengem Beispill (no der Sortéierung) fir de Verglachalgorithmus kucken esou aus:

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

Bedenkt datt an der Tabell vun de Skalen grouss Buschtawen op Russesch no kleng Buschtawen kommen (um drëtten Niveau méi schwéier wéi ), d'Sortéierung gesäit absolut korrekt aus.

Wann Dir eng Variabel setzt LC_COLLATE=C eng speziell Tabell gëtt gelueden, déi e Byte-by-byte Verglach spezifizéiert

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

Well am Unicode de Code Punkt Ё virun A kënnt, ginn d'Strings deementspriechend zortéiert.

Text a binär Dëscher

Natierlech ass Stringverglach eng extrem heefeg Operatioun, an Tabellparsing CTT zimlech deier Prozedur. Fir den Zougang zum Dësch ze optimiséieren, gëtt et a binär Form mat dem Kommando kompiléiert localdef.

Equipe localdef akzeptéiert als Parameter e Fichier mat enger Tabell vun nationalen Charakteristiken (Optioun -i), an deem all Zeechen duerch Unicode Punkte vertruede sinn, an e Korrespondenzdatei tëscht Unicode Punkten a Charaktere vun enger spezifescher Kodéierung (Optioun -f). Als Resultat vun der Aarbecht ginn binär Dateie fir d'Lokalitéit erstallt mam Numm am leschte Parameter uginn.

glibc ënnerstëtzt zwee binär Dateiformate: "traditionell" a "modern".

Dat traditionellt Format bedeit datt den Numm vun der Lokalitéit den Numm vum Ënnerverzeechnes ass /usr/lib/locale/. Dëse Subdirectory späichert binär Dateien LC_COLLATE, LC_CTYPE, LC_ZEIT a sou weider. Fichier LC_IDENTIFIKATIOUN enthält den formellen Numm vun der Lokalitéit (dee kann anescht sinn wéi den Numm vum Verzeichnis) a Kommentaren.

De modernen Format beinhalt d'Späichere vun all Lokaler an engem eenzegen Archiv /usr/lib/locale/locale-archive, déi op d'virtuell Gedächtnis vun all Prozesser mat glibc. De Lokalnumm am modernen Format ass ënnerleien zu enger Kanoniséierung - nëmmen Zuelen a Buschtawen reduzéiert op kleng Buschtawen bleiwen an de Kodéierungsnimm. Also ru_RU.KOI8-R, wäert gespäichert ginn als ru_RU.koi8r.

Inputdateien ginn am aktuellen Verzeechnes gesicht, souwéi an Verzeichnisser /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ fir Fichieren CTT a Kodéierungsdateien, respektiv.

Zum Beispill, de Kommando

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

wäert d'Datei kompiléieren /usr/share/i18n/locales/ru_RU benotzt Kodéierungsdatei /usr/share/i18n/charmaps/MAC-CYRILLIC.gz a späichert d'Resultat an /usr/lib/locale/locale-archive ënner dem Numm ru_RU.maccyrillic

Wann Dir d'Variabel setzt LANG = en_US.UTF-8 dann glibc sicht locale Binären an der folgender Sequenz vu Dateien a Verzeichnisser:

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

Wann eng Lokalitéit souwuel an traditionellen wéi och modernen Formater optrieden, da gëtt Prioritéit dem modernen.

Dir kënnt d'Lëscht vun de kompiléierte Lokaler mam Kommando kucken locale -a.

Preparéieren Äre Verglach Dësch

Elo, bewaffnet mat dem Wëssen, kënnt Dir Ären eegene ideale Stringvergleichstabell erstellen. Dës Tabell soll russesch Buschtawen korrekt vergläichen, dorënner de Bréif Ё, a gläichzäiteg d'Punctuatiounszeechen am Aklang mat der Tabell berücksichtegen. ASCII.

De Prozess vun der Preparatioun vun Ärem eegene Sortéierungsdësch besteet aus zwou Etappen: Änneren vun der Gewiichtstabell a kompiléiere se a binär Form mam Kommando localdef.

Fir datt d'Vergläichstabelle mat minimale Redaktiounskäschte ugepasst gëtt, am Format ISO 14652 Sektiounen fir d'Gewiichter vun enger existéierender Dësch ajustéieren ginn ugebueden. D'Sektioun fänkt mat engem Schlësselwuert un nei bestellen-na a beweist d'Positioun no deem den Ersatz duerchgefouert gëtt. D'Sektioun endet mat der Linn reorder-end. Wann et néideg ass fir e puer Sektiounen vun der Tabell ze korrigéieren, da gëtt eng Sektioun fir all esou Sektioun erstallt.

Ech hunn nei Versioune vun de Fichieren kopéiert iso14651_t1_common и ru_RU aus dem Repository glibc a mengem Heemverzeichnis ~/.local/share/i18n/locales/ an d'Sektioun liicht geännert LC_COLLATE в ru_RU. Nei Versioune vu Dateien si voll kompatibel mat menger Versioun glibc. Wann Dir méi al Versioune vu Dateien benotze wëllt, musst Dir déi symbolesch Nimm änneren an d'Plaz wou den Ersatz an der Tabell ufänkt.

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

Tatsächlech wier et néideg d'Felder ze änneren LC_IDENTIFIKATIOUN sou datt se op d'Lokalitéit weisen ru_MENG, mee a mengem Beispill war dat net erfuerderlech, well ech d'Archiv aus der Sich no Locale ausgeschloss hunn locale-archiv.

datt localdef geschafft mat Dateien a mengem Dossier duerch eng Variabel I18NPATH Dir kënnt en zousätzleche Verzeechnes addéieren fir no Inputdateien ze sichen, an de Verzeechnes fir binär Dateien ze späicheren kann als Wee mat Schnëttstécker spezifizéiert ginn:

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

POSIX geet dovun aus, datt an SPROOCH Dir kënnt absolut Weeër fir Verzeichnisser mat Locale Dateien schreiwen, ugefaange mat engem Forward Slash, awer glibc в Linux all Weeër sinn aus der Basis Verzeechnes gezielt, déi duerch eng Variabel iwwerdribblen kann LOCPATH. No der Installatioun LOCPATH=~/.local/lib/locale/ all Dateien am Zesummenhang mat der Lokalisatioun ginn nëmmen a mengem Dossier gesicht. Archiv vu Locale mat der Variabelset LOCPATH ignoréiert.

Hei ass den entscheedende Test:

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

Hour! Mir hunn et gemaach!

Aarbecht iwwer Bugs

Ech hu schonn d'Froen iwwer d'Stringsortéierung am Ufank geäntwert, awer et sinn nach ëmmer e puer Froen iwwer Feeler - sichtbar an onsichtbar.

Komme mer zréck op den urspréngleche Problem.

An de Programm sortéieren a Programm anzeschreiwen benotzen déi selwecht String Verglach Funktiounen aus glibc. Wéi ass dat geschitt anzeschreiwen huet e Sortéierungsfehler op Reihen, déi nom Kommando zortéiert sinn sortéieren an der Lokalitéit en_US.UTF-8? D'Äntwert ass einfach: sortéieren vergläicht de ganze String, an anzeschreiwen vergläicht nëmmen de Schlëssel, deen als Standard den Ufank vum String bis zum éischte Whitespace Charakter ass. A mengem Beispill huet dëst zu enger Fehlermeldung gefouert, well d'Sortéierung vun den éischte Wierder an de Linnen net mat der Sortéierung vun de komplette Linnen entsprécht.

Lokal "C" garantéiert datt an zortéierten Strings déi initial Substrings bis zum éischte Raum och zortéiert ginn, awer dëst maskéiert nëmmen de Feeler. Et ass méiglech Daten auszewielen (Leit mat de selwechte Familljen, awer ënnerschiddlech Virnumm), déi ouni d'Fehlermeldung e falscht Resultat vun der Dateifusioun ginn. Wa mir wëllen anzeschreiwen fusionéierte Dateilinnen mam vollen Numm, da wier de richtege Wee fir den Feldtrener explizit ze spezifizéieren an no dem Schlësselfeld ze sortéieren, an net no der ganzer Linn. An dësem Fall wäert d'Fusioun richteg virugoen an et gi keng Feeler an enger Lokalitéit:

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

Erfollegräich ausgefouert Beispill am Kodéierung CP1251 enthält en anere Feeler. D'Tatsaach ass, datt an all distributions bekannt fir mech Linux Pakete fehlen kompiléiert Locale ru_RU.CP1251. Wann déi kompiléiert Lokalitéit net fonnt gëtt, dann sortéieren benotzt roueg e Byte-by-Byte Verglach, dat ass wat mir observéiert hunn.

Iwwregens gëtt et e weidere klenge Feeler am Zesummenhang mat der Onzougänglechkeet vu kompiléierte Lokaler. Equipe LOCPATH=/tmp locale -a gëtt eng Lëscht vun all locales an locale-archiv, awer mat der Variabelset LOCPATH fir all Programmer (och déi meescht lokal) dës Uertschaften wäerten net verfügbar sinn.

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

Konklusioun

Wann Dir e Programméierer sidd dee gewinnt ass ze denken datt Strings e Set vu Bytes sinn, dann ass Äre Choix LC_COLLATE=C.

Wann Dir e Linguist oder Wierderbuch Compiler sidd, da kompiléiere besser an Ärer Lokalitéit.

Wann Dir en einfache Benotzer sidd, da musst Dir just un d'Tatsaach gewinnt ginn datt de Kommando ls -a Ausgab Dateien mat engem Punkt gemëscht mat Dateie mat engem Bréif unzefänken, an Mëtternuecht Kommandant, déi seng intern Funktiounen benotzt fir Nimm ze sortéieren, setzt Dateien mat engem Punkt am Ufank vun der Lëscht un.