Inleiding

Alles begon met een kort script dat de informatie over adressen moest combineren e-mail van medewerkers, verkregen uit de lijst van gebruikers van de mailinglijst, met de functies van medewerkers, verkregen uit de HR-database. Beide lijsten zijn geëxporteerd naar tekstbestanden in Unicode-encoding UTF-8 en opgeslagen met Unix-eindes.

Inhoud mail.txt

Ivanov Andrey;ia@example.com

Inhoud buhg.txt

Ivanova Alla;schilder
Yelkina Ella;kraanmachinist
Ivanov Andrey;loodgieter
Abakanov Mikhail;schilder

Om de bestanden te combineren, werden ze gesorteerd met het Unix-commando sort en doorgegeven aan het Unix-programma join, dat onverwacht eindigde met een foutmelding:

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

Het bekijken van het sorteeresultaat gaf aan dat de sortering over het algemeen correct was, maar in het geval van overeenkomsten tussen mannelijke en vrouwelijke achternamen, zijn de vrouwelijke eerst:

$> sort buhg.txt
Abakanov Mikhail;schilder
Yelkina Ella;kraanmachinist
Ivanova Alla;schilder
Ivanov Andrey;loodgieter

Het lijkt op een fout in de sortering in Unicode of op een uiting van feminisme in het sorteeralgoritme. Het eerste lijkt natuurlijk plausibeler.

Laten we het voor nu uitstellen join en ons concentreren op sort. Laten we proberen het probleem op de proef te stellen. Laten we beginnen met het wijzigen van de locatie naar en_US en een werkende opdracht krijgen. ru_RU. Voor het sorteren zou het voldoende zijn om de omgevingsvariabele LC_COLLATE, in te stellen, maar we willen het niet zo kleinziend maken:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;schilder
Yelkina Ella;kraanmachinist
Ivanova Alla;schilder
Ivanov Andrey;loodgieter

Er is niets veranderd.

Laten we proberen de bestanden naar een eencodering te converteren:

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

Weer is er niets veranderd.

We hebben geen andere keuze dan een oplossing op internet te zoeken. Direct over Russische achternamen is niets te vinden, maar er zijn vragen over andere vreemde sorteringen. Hier is bijvoorbeeld zo'n probleem: unix sort behandelt '-' (streepje) als onzichtbaar. Kort gezegd, de strings "a-b", "aa", "ac" worden gesorteerd als "aa", "a-b", "ac".

Het antwoord is overal standaard: gebruik de programmeertaal-locatie "C" en je hebt geluk. Laten we het proberen:

$> LANG=C sort buhg.txt
Yelkina Ella;kraanmachinist
Abakanov Mikhail;schilder
Ivanov Andrey;loodgieter
Ivanova Alla;advocaat

Er is iets veranderd. De Ivanovs staan nu in de juiste volgorde, maar Yelkina is ergens naartoe geslopen. Laten we teruggaan naar de oorspronkelijke taak:

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

Het werkte zonder fouten, zoals het internet beloofde. En dat ondanks de Ёlkin op de eerste regel.

Het probleem lijkt opgelost, maar voor de zekerheid proberen we nog een Russische codering — de Windows-codering. CP1251:

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

Het sorteers resultaat zal, vreemd genoeg, overeenkomen met de locale. "C", en het hele voorbeeld passeert dus zonder fouten. Het is een soort mystiek.

Ik hou niet van mystiek in programmeren, omdat het meestal fouten verbergt. Ik moet serieus kijken naar hoe het werkt sort en op wat het invloed heeft. LC_COLLATE .

Aan het einde zal ik proberen de vragen te beantwoorden:

waarom de vrouwelijke achternamen niet goed gesorteerd waren.
waarom LANG=ru_RU.CP1251 bleek equivalent te zijn aan LANG=C
waarom sort en join verschillende opvattingen over de volgorde van gesorteerde regels hebben.
waarom er in al mijn voorbeelden fouten zitten.
en tot slot, hoe je regels naar eigen smaak kunt sorteren.

Sorteren in Unicode.

De eerste stop is het technische rapport nr. 10 met de titel Unicode collation algorithm. op de website unicode.org. Het rapport bevat veel technische details, dus ik sta mezelf toe een samenvatting van de belangrijkste ideeën te geven.

Collatie — "vergelijking" van regels — is de basis van elk sorteeralgoritme. De algoritmes zelf kunnen verschillen ("bubbel", "samensmelten", "snel"), maar ze zullen allemaal paargewijze vergelijkingen gebruiken om de volgorde te bepalen.

Het sorteren van regels in natuurlijke taal is een behoorlijk complexe zaak. Zelfs in de eenvoudigste eencoderingen zal de volgorde van de letters in een alfabet, dat op de een of andere manier verschilt van het Engelse alfabet, niet overeenkomen met de numerieke waarden waarmee die letters gecodeerd zijn. Zo staat in het Duitse alfabet de letter Ö tussen groot aantal partitions. en P, maar in de codering CP850 valt het tussen ÿ en Ü..

Je kunt proberen je los te maken van de specifieke codering en "ideale" letters te beschouwen die in een bepaalde volgorde zijn geplaatst, zoals gedaan wordt in Unicode. De coderingen UTF8, UTF16 of eencodering KOI8-R (als een beperkte subset van Unicode nodig is) zullen verschillende numerieke representaties van letters geven, maar verwijzen tegelijkertijd naar dezelfde basis tabel elementen.

Het blijkt dat zelfs als we een tekenlijst vanaf nul opbouwen, we geen universele volgorde voor de tekens kunnen vaststellen. In verschillende nationale alfabetten die dezelfde letters gebruiken, kan de volgorde van deze letters verschillen. Bijvoorbeeld, in het Frans Æ wordt als een ligatuur beschouwd en gesorteerd als een string AE. In het Noors Æ wordt het een afzonderlijke letter, die na Zkomt. Trouwens, naast ligaturen zoals Æ zijn er letters die door meerdere symbolen worden geschreven. In het Tsjechische alfabet is er de letter Ch, die tussen H en I.

staat. Behalve de verschillen in de alfabetten zijn er ook andere nationale tradities die invloed hebben op de sortering. Er rijst bijvoorbeeld de vraag: in welke volgorde moeten woorden die uit hoofdletters en kleine letters bestaan in het woordenboek worden geplaatst? Ook de specifieke manier waarop interpunctie wordt gebruikt, kan invloed hebben op de sortering. In het Spaans wordt aan het begin van een vraagzin een omgekeerd vraagteken geplaatst (¿Te gusta la música?). In dit geval is het duidelijk dat vraagzinnen niet in een aparte cluster buiten het alfabet moeten worden gegroepeerd, maar hoe moet je strings met andere interpunctie sorteren?

Ik zal niet ingaan op de sortering van strings in talen die sterk verschillen van de Europese. Ik merk op dat in talen met een schrijfrichting van rechts naar links of van boven naar beneden, de symbolen in de strings waarschijnlijk in de leesvolgorde worden opgeslagen, en zelfs in niet-alfabetische schriftsoorten zijn er manieren om strings teken voor teken te ordenen. Bijvoorbeeld, hiërogliefen kunnen worden geordend op basis van hun vorm (de sleutels van Chinese hiërogliefen) of op basis van uitspraak. Hoe emoji's moeten worden geordend, heb ik eerlijk gezegd geen idee van, maar ook daarvoor kan wel iets worden bedacht.

Op basis van de bovengenoemde kenmerken zijn de belangrijkste vereisten voor het vergelijken van strings, gebaseerd op Unicode-tabellen, geformuleerd:

de vergelijking van strings is niet afhankelijk van de positie van de symbolen in de codeertabel;
de reeksen van symbolen die een enkel teken vormen, worden in canonieke vorm gebracht (A + de bovenste cirkel is hetzelfde als Å);
); bij het vergelijken van strings wordt het teken in de context van de string beschouwd en, indien nodig, samengevoegd met buren tot een enkele vergelijkingseenheid (Ch in het Tsjechisch) of wordt het in meerdere (Æ in het Frans) opgesplitst.
alle nationale kenmerken (alfabet, hoofdletters / kleine letters, interpunctie, volgorde van schrijfwijzen) moeten volledig handmatig ingesteld kunnen worden (emoji);
vergelijking is niet alleen belangrijk voor sortering, maar ook op veel andere plaatsen, bijvoorbeeld bij het instellen van reeksen (substitutie {A… j} in bash);
de vergelijking moet snel genoeg worden uitgevoerd.

Bovendien hebben de auteurs van het rapport eigenschappen van vergelijking geformuleerd waarop ontwikkelaars van het algoritme niet moeten vertrouwen:

het vergelijkingsalgoritme mag niet een aparte set symbolen vereisen voor elke taal (de Russische en Oekraïense talen gebruiken gezamenlijk het grootste deel van het Cyrillische alfabet);
de vergelijking mag niet steunen op de volgorde van symbolen in Unicode-tabellen;
het gewicht van de string mag geen attribuut van de string zijn, aangezien dezelfde string in verschillende culturele contexten verschillende gewichten kan hebben;
gewichten van strings kunnen veranderen bij het samenvoegen of splitsen (uit x < y het is niet zo dat xz < yz);
verschillende strings met gelijke gewichten worden als gelijk beschouwd vanuit het perspectief van het sorteeralgoritme. Het introduceren van extra volgorde voor dergelijke strings is mogelijk, maar kan de prestaties verslechteren;
bij herhaalde sorteringen kunnen strings met gelijke gewichten van plaats wisselen. Stabiliteit is een eigenschap van een specifiek sorteeralgoritme, en geen eigenschap van het string vergelijkingsalgoritme (zie punt hiervoor);
sorteerregels kunnen in de loop van de tijd veranderen naarmate culturele tradities worden verfijnd / gewijzigd.

Het is ook opgemerkt dat het vergelijkingsalgoritme niets weet van de semantiek van de verwerkte strings. Strings die alleen uit cijfers bestaan, mogen niet als getallen worden vergeleken, en in lijsten met Engelse namen mag het lidwoord niet worden verwijderd (Beatles, The).

Om aan alle genoemde vereisten te voldoen, is een hiërarchisch (eigenlijk vier niveaus) tabelalgoritme voor sorteren voorgesteld.

Eerst worden de symbolen in de string naar hun canonieke vorm gebracht en gegroepeerd in vergelijkingseenheden. Aan elke vergelijkingseenheid worden verschillende gewichten toegewezen die overeenkomen met verschillende vergelijkingsniveaus. De gewichten van de vergelijkingseenheden zijn elementen van geordende verzamelingen (in dit geval gehele getallen) die met elkaar vergeleken kunnen worden op groter-kleiner. Een speciale waarde IGNORED (0x0) betekent dat de betreffende eenheid op het overeenkomstige vergelijkingsniveau niet deelneemt aan de vergelijking. De vergelijking van strings kan meerdere keren worden herhaald, met gebruik van de gewichten van de betreffende niveaus. Op elk van de niveaus worden de gewichten van de vergelijkingseenheden van twee strings achtereenvolgens met elkaar vergeleken.

In verschillende implementaties van het algoritme voor verschillende nationale tradities kunnen de waarden van de coëfficiënten verschillen, maar de basisgewichtentabel maakt deel uit van de Unicode-standaard — "Default Unicode Collation Element Table" (DUCET). Ik wil opmerken dat het instellen van een variabele LC_COLLATE feitelijk een aanwijzing is voor de keuze van de gewichtentabel in de functie voor stringvergelijking.

Gewichtcoëfficiënten DUCET zijn als volgt opgebouwd:

op het eerste niveau worden alle letters naar één hoofdlettertype omgezet, diakritische tekens worden weggelaten, en (niet alle) leestekens worden genegeerd;
op het tweede niveau worden alleen diakritische tekens in aanmerking genomen;
op het derde niveau wordt alleen de hoofdletter gebruikt;
op het vierde niveau worden alleen leestekens in aanmerking genomen.

De vergelijking vindt plaats in meerdere rondes: eerst worden de coëfficiënten van het eerste niveau met elkaar vergeleken; als de gewichten overeenkomen, vindt een hervergelijking plaats met de gewichten van het tweede niveau; vervolgens, mogelijk, het derde en vierde.

De vergelijking eindigt wanneer er overeenkomstige vergelijkingseenheden met verschillende gewichten in de strings worden gevonden. Strings die op alle vier niveaus gelijke gewichten hebben, worden als gelijk aan elkaar beschouwd.

Dit algoritme (met een hoop extra technische details) gaf de naam aan rapport nr. 10 — "Unicode Collation Algorithm" (UCA).

Op dit punt wordt het sorteergedrag van ons voorbeeld iets duidelijker. Het zou goed zijn om dit te vergelijken met de Unicode-standaard.

Voor het testen van implementaties UCA is er een speciale test, die gebruik maakt van gewichtbestand, die DUCET. In het gewichtbestand zijn verschillende curiositeiten te vinden. Bijvoorbeeld, daar is de volgorde van dominosteentjes en Europese domino, evenals de volgorde van kleuren in een spel kaarten (symbool 1F000 en verder). De kleuren van de kaarten zijn gerangschikt volgens de brugregels — PCHK, en de kaarten binnen een kleur zijn in de volgorde T,2,3… K.

Handmatig controleren van de juistheid van het sorteren van strings volgens DUCET zou behoorlijk vermoeiend zijn, maar gelukkig voor ons is er een voorbeeldige implementatie van een bibliotheek voor het werken met Unicode — "Internationale componenten voor Unicode" (ICU).

Op de website van deze bibliotheek, ontwikkeld in IBM, zijn demonstratiepagina's te vinden, waaronder de pagina met het algoritme voor stringvergelijking. We voeren onze teststrings in met de standaardinstellingen en, oh wonder, we krijgen perfecte Russische sortering.

Abakanov Mikhail;schilder
Yolkina Ella;kraanmachinist
Ivanov Andrei;loodgieter
Ivanova Alla;advocaat

Trouwens, op de website ICU is er een verduidelijking over de werking van het algoritme voor vergelijking bij het verwerken van interpunctie. In de voorbeelden Collation FAQ worden het apostrof en het koppelteken genegeerd.

Unicode heeft ons geholpen, maar we moeten de oorzaken van het vreemde gedrag sort in Linux ergens anders zoeken.

Sorteren in glibc

Een snelle blik op de broncode van de tool sort uit GNU Core Utils toonde aan dat de lokalisatie in de tool zelf neerkomt op het afdrukken van de huidige waarde van de variabele LC_COLLATE wanneer deze in de debug modus wordt uitgevoerd:

$ sort --debug buhg.txt > buhg.srt
sort: gebruikmakend van ‘en_US.UTF8’ sorteervoordelen

Stringvergelijking gebeurt met de standaardfunctie strcoll, wat betekent dat alles interessante zich bevindt in de bibliotheek glibc.

Op wiki van het project glibc waaraan stringvergelijking is gewijd één alinea. Uit deze alinea kun je begrijpen dat glibc de sortering is gebaseerd op het voor ons bekende algoritme UCA (Het Unicode sorteeralgoritme) en/of op een vergelijkbare standaard ISO 14651 (Internationale stringordening en vergelijking). Voor de laatste standaard moet worden opgemerkt dat deze op de website standards.iso.org ISO 14651 officieel als openbaar is verklaard, maar de betreffende link leidt naar een niet-bestaande pagina. Google geeft verschillende pagina's weer met links naar officiële websites die aanbieden een elektronische kopie van de standaard voor een paar honderd euro te kopen, maar op de derde of vierde pagina van de zoekresultaten vind je ook directe links naar PDF. Over het geheel genomen verschilt de standaard vrijwel niet van UCA, maar leest saaier, omdat het geen opvallende voorbeelden van nationale sorteerkenmerken bevat.

De meest interessante informatie op wiki bleek een link te zijn naar bug tracker met een discussie over de implementatie van stringvergelijking in glibc. Uit de discussie kun je leren dat in glibc voor stringvergelijking wordt gebruikt ISOeen tabel De Common Template Table (CTT), waarvan het adres te vinden is in de bijlage A van de standaard ISO 14651. Tussen 2000 en 2015 is deze tabel in glibc had no maintainer and differed significantly (at least visually) from the current version of the standard. From 2015 to 2018, there was an adaptation to the new version of the table, and at the moment you may encounter either the new table variant (CentOS 8), or the old one (CentOS 7).

Now that we have all the information about the algorithm and auxiliary tables, we can return to the original problem and understand how to correctly sort rows in the Russian locale.

ISO 14651/14652

The source code of the table of interest to us CTT is located in the most distributions Linux in the directory /usr/share/i18n/locales/. The table itself is in the file iso14651_t1_common. Then this file is included in the file with the directive copy iso14651_t1_common in the file iso14651_t1, which, in turn, is included in the national files, including en_US en ru_RU. In most distributions Linux all source files are included in the base installation, but if they are not present, you will have to install an additional package from the distribution.

dev.yaml iso14651_t1 may seem terribly verbose, with non-obvious naming rules, but if you get into it, everything is quite simple. The structure is described in the standard ISO 14652, a copy of which can be downloaded from the site open-std.org. Another description of the file format can be read in de specificaties POSIX van OpenGroup. As an alternative to reading the standard, you can study the source texts of the function collate_read in glibc/locale/programs/ld-collate.c.

The structure of the file looks as follows:

By default, the character is used as an escape character, and the end of the line after the # symbol is a comment. Both characters can be overridden, which is done in the new version of the table:

escape_char /
comment_char %

The file will contain tokens in the format <Uxxxx> of <Uxxxxxxxx> (waar x — a hexadecimal digit). This is the hexadecimal representation of Unicode code points in the encoding UCS-4 (UTF-32). All other elements in angle brackets (including <Uxxxx_xxxx>, <2> and similar ones) are considered simple string constants without special meaning outside of context.

String LC_COLLATE tells us that the data describing string comparison begins next.

First, names for the weights in the comparison table and names for combinations of characters are set. Generally speaking, the two types of names belong to two different entities, but in the real file, they are mixed. The names of the weights are defined by the keyword collating-symbol (vergelijkingssymbool), aangezien Unicode-tekens met dezelfde gewichten als equivalente tekens worden beschouwd bij de vergelijking.

De totale lengte van de sectie in de huidige revisie van het bestand is ongeveer 900 regels. Ik heb voorbeelden uit verschillende plaatsen gehaald om de willekeurigheid van de namen en enkele soorten syntaxis te laten zien.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Gegarandeerde grootste symbolwaarde. Aan het einde van deze lijst houden
...
collating-element  van ""
collating-element  van ""

collating-symbol registreert een string OSMANYA in de naamgewichtentabel
collating-symbol .. registreert een reeks namen bestaande uit een prefix S en een hexadecimale numerieke suffix van 1D000 tot 1D35F.
FFFF in collating-symbol verschijnt als een grote niet-negatieve integer in hexadecimale systeem, maar <SFFFF> het is gewoon een naam die eruit zou kunnen zien als <VERYBIGVAL>
naam <U0413> betekent een codepunt in de codering UCS-4
collating-element van "" registreert een nieuwe naam voor het paar Unicode-punten.

Wanneer de gewichtennamen zijn gedefinieerd, worden de gewichten zelf ingesteld. Aangezien alleen de grotere-kleinere relaties van belang zijn bij de vergelijking, worden de gewichten bepaald door een eenvoudige volgorde van opsomming van namen. Eerst worden de "lichtere" gewichten opgesomd, daarna de "zwaardere". Ik herinner me dat elke Unicode-teken vier verschillende gewichten krijgt toegewezen. Hier zijn ze gebundeld in één geordende volgorde. Theoretisch kan elke symbolische naam op elk van de vier niveaus worden gebruikt, maar opmerkingen geven aan dat ontwikkelaars de namen mentaal scheiden naar niveau.

% Symbolische gewichtstoewijzingen

% Derde-niveau gewichtstoewijzingen




...
% Tweede-niveau gewichtstoewijzingen

 % COMBINING LOW LINE
 % COMBINING COMMA ABOVE
 % COMBINING REVERSED COMMA ABOVE
...
% Eerste-niveau gewichtstoewijzingen
 % HORIZONTALE TABULATIE
 % REGELAFBREKING
 % VERTICALE TABULATIE
...
 % CYRILLIC KLEINE LETTER DE
 % CYRILLIC KLEINE LETTER KOMI DE
 % CYRILLIC KLEINE LETTER DJE
 % CYRILLIC KLEINE LETTER KOMI DJE
 % CYRILLIC KLEINE LETTER GJE
 % CYRILLIC KLEINE LETTER ZE MET DESCENDER
 % CYRILLIC KLEINE LETTER IE
 % CYRILLIC KLEINE LETTER IE MET BREVE
 % CYRILLIC KLEINE LETTER UKRAINIË IE
 % CYRILLIC KLEINE LETTER ZHE

Ten slotte, de eigenlijke gewichten tabel.

De sectie gewichten is verpakt in rijen met sleutelwoorden order_start en order_end. Aanvullende parameters order_start bepalen in welke richting de rijen worden bekeken op elk vergelijkingsniveau. Standaard wordt de parameter gebruikt forward. Het lichaam van de sectie bestaat uit rijen die de tekencode en vier bijbehorende gewichten bevatten. De tekencode kan worden weergegeven door het teken zelf, een codepunt of een symbolische naam die eerder is gedefinieerd. Gewichten kunnen ook worden opgegeven door symbolische namen, codepunten of de tekens zelf. Als codepunten of tekens worden gebruikt, komt hun gewicht overeen met de numerieke waarde van het codepunt (de positie in de Unicode-tabel). Tekens die niet expliciet zijn opgegeven (zoals ik begrijp) worden beschouwd als toegevoegd aan de tabel met een primaire gewicht dat overeenkomt met de positie in de Unicode-tabel. Een speciale gewichtwaarde IGNORE betekent dat dit teken op het betreffende vergelijkingsniveau wordt genegeerd.

Om de structuur van de gewichten te demonstreren, heb ik drie vrij duidelijke fragmenten gekozen:

tekens die volledig worden genegeerd
tekens die gelijk zijn aan het cijfer drie op de eerste twee niveaus
begin van het Cyrillische alfabet, dat geen diakritische tekens bevat en daarom voornamelijk op de eerste en derde niveaus wordt gesorteerd.

order_start forward;forward;forward;forward,positie
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
 ;;; % DIGIT THREE
 ;;; % FULLWIDTH DIGIT THREE
 ;;; % PARENTHESIZED DIGIT THREE
 ;;; % DIGIT THREE FULL STOP
 ;;; % MATHEMATICAL BOLD DIGIT THREE
...
 ;;; % CYRILLIC SMALL LETTER A
 ;;; % CYRILLIC CAPITAL LETTER A
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
...
 ;;; % CYRILLIC SMALL LETTER BE
 ;;; % CYRILLIC CAPITAL LETTER BE
 ;;; % CYRILLIC SMALL LETTER VE
 ;;; % CYRILLIC CAPITAL LETTER VE
...
order_end

Nu kunnen we weer terugkeren naar de sortering van de voorbeelden aan het begin van het artikel. De val zit in dit gedeelte van de gewichten tabel:

NEGEREN; NEGEREN; NEGEREN; % RUIMTE
 NEGEREN; NEGEREN; NEGEREN; % UITROEPTEKEN
 NEGEREN; NEGEREN; NEGEREN; % AANHAALTEKEN
...

Het is duidelijk dat in deze tabel leestekens uit de tabel zijn. ASCII (inclusief spaties) worden bij het vergelijken van strings vrijwel altijd genegeerd. Uitzonderingen zijn enkel de strings die in alles overeenkomen, behalve in leestekens die zich op overeenkomende posities bevinden. De strings uit mijn voorbeeld (na sortering) zien eruit als volgt voor het vergelijkingsalgoritme:

AbakanovMikhailSchilders
YolkinaEllakranovschitsa
IvanovaAllaSchilders
IvanovAndreiKlusjesman

Gegeven dat in de weegset hoofdletters in het Russisch na kleine letters komen (op de derde niveau) <CAP> zwaarder dan <MIN>), is de sortering volkomen juist.

Bij het instellen van de variabele LC_COLLATE=C wordt een speciale tabel geladen die byte-voor-byte vergelijking bepaalt.

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* 1e-niveau tabel */
  6 * sizeof (uint32_t),
  /* 2e-niveau tabel */
  7 * sizeof (uint32_t),
  /* 3e-niveau tabel */
  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'
};

Aangezien de Unicode-codepunt Ё voor A staat, worden de strings ook zo gesorteerd.

Tekst- en binaire tabellen

Het is duidelijk dat het vergelijken van strings een zeer vaak voorkomende operatie is, terwijl het parseren van de tabel CTT een vrij kostbare procedure is. Voor het optimaliseren van de toegang tot de tabel wordt deze gecompileerd naar een binaire vorm met het commando localedef.

Opdracht localedef neemt als parameters een bestand met de nationale kenmerkentabel (optie -i), waarin alle symbolen worden voorgesteld door Unicode-codepunten, en een overeenstemmingsbestand voor Unicode-codepunten met een specifieke codering (optie -f). Als resultaat van de bewerking worden er binaire bestanden voor de locale aangemaakt met de naam die in de laatste parameter is opgegeven.

Glibc ondersteunt twee formaten van binaire bestanden: "traditioneel" en "modern".

Het traditionele formaat houdt in dat de naam van de locale een naam is van de subdirectory in /usr/lib/locale/. In deze subdirectory worden binaire bestanden opgeslagen LC_COLLATE, LC_CTYPE, LC_TIME enzovoort. Het bestand LC_IDENTIFICATION bevat de formele naam van de locale (die kan verschillen van de naam van de directory) en opmerkingen.

Het moderne formaat veronderstelt dat alle locales in een enkele archief zijn opgeslagen /usr/lib/locale/locale-archive, die wordt weergegeven in het virtuele geheugen van alle processen die het gebruiken. glibcDe naam van de locale in het moderne formaat ondergaat enige canonisatie — in de naamgeving van encoderingen blijven alleen cijfers en letters behouden, omgezet naar kleine letters. Dus nl_NL.KOI8-R, zal worden bewaard als nl_NL.koi8r.

Ingangsbestanden worden gezocht in de huidige map, evenals in de mappen /usr/share/i18n/locales/ en /usr/share/i18n/charmaps/ voor bestanden CTT en bestanden van encoderingen respectievelijk.

Bijvoorbeeld, het commando

localedef -i nl_NL -f MAC-CYRILLIC nl_NL.MAC-CYRILLIC

compileert het bestand /usr/share/i18n/locales/ru_RU met behulp van het encoderingbestand /usr/share/i18n/charmaps/MAC-CYRILLIC.gz en zal het resultaat opslaan in /usr/lib/locale/locale-archive under the name nl_NL.maccyrillic

Als je de variabele LANG=en_US.UTF-8 instelt, glibc zal het binaire bestanden van de locale zoeken in de volgende volgorde van bestanden en mappen:

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

Als de locale in zowel traditionele als moderne formaten voorkomt, heeft de moderne de voorkeur.

Je kunt de lijst met gecompileerde locales bekijken met het commando locale -a.

Het voorbereiden van je eigen vergelijkingsmatrix

Nu, gewapend met kennis, kun je je eigen ideale vergelijkingsmatrix voor stringvergelijkingen creëren. Deze matrix moet correct Russische letters vergelijken, inclusief de letter Ё, en rekening houden met leestekens volgens de tabel. ASCII.

Het proces van het voorbereiden van je eigen sorteertabel bestaat uit twee fasen: het bewerken van de gewichtentabel en het compileren ervan naar binaire vorm met het commando. localedef.

Om de vergelijkingsmatrix met minimale bewerkingskosten aan te passen, biedt het formaat ISO 14652 secties voor het aanpassen van de gewichten van de bestaande tabel. Een sectie begint met het sleutelwoord reorder-after en de positionele aanwijzing, na welke de vervangingen plaatsvinden. De sectie eindigt met de regel reorder-end. Als het nodig is om meerdere delen van de tabel te corrigeren, wordt er een sectie voor elk deel gemaakt.

Ik heb nieuwe versies van de bestanden gekopieerd iso14651_t1_common en ru_RU uit de repository glibc naar mijn thuisdirectory ~/.local/share/i18n/locales/ en iets aangepast in de sectie LC_COLLATE in ru_RU. Nieuwe versies van bestanden zijn volledig compatibel met mijn versie. glibcAls je de oude versies van de bestanden wilt gebruiken, moet je de symbolische namen en de plaats waar de vervangingen beginnen in de tabel wijzigen.

LC_COLLATE
% Kopieer de sjabloon van ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPATIE
 ;;; % UITROEPTEKEN
 ;;; % AANHAALTEKEN
...
 ;;; % RECHTE KROEGENDE HAAK
 ;;; % TILDE
reorder-end
EINDE LC_COLLATE

Eigenlijk zou het nodig zijn om de velden te wijzigen in LC_IDENTIFICATION zodat ze naar de locatie verwijzen ru_MY, maar in mijn voorbeeld was dit niet nodig omdat ik de zoekopdracht naar locaties in het archief heb uitgesloten locale-archive.

Om localedef werkte met bestanden in mijn map via de variabele I18NPATH je kunt een extra map toevoegen voor het zoeken naar invoerbestanden, en de map voor het opslaan van binaire bestanden kan worden opgegeven als een pad met schuine strepen:

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

POSIX dit gaat ervan uit dat in LANG je absolute paden naar mappen met locatiebestanden kunt schrijven, beginnend met een schuin streepje, maar glibc in Linux iedereen paden beschouwt vanaf de basisdirectory, die kan worden overschreven via de variabele LOCPATH. Na het instellen van LOCPATH=~/.local/lib/locale/ zullen alle bestanden die met lokalisatie verband houden, alleen in mijn map worden gezocht. Het archief van locaties met de ingestelde variabele LOCPATH wordt genegeerd.

Hier is de beslissende test:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Michail;schilder
Jolkina Ella;kraanmachinist
Ivanov Andrej;loodgieter
Ivanova Alla;advocaat

Hoera! We hebben het gedaan!

Fouten herstellen

Ik heb al geantwoord op de vragen over het sorteren van rijen die aan het begin zijn gesteld, maar er zijn nog een paar vragen over fouten — zichtbare en onzichtbare.

Laten we terugkeren naar de oorspronkelijke taak.

En het programma sort en het programma join maken gebruik van dezelfde functies voor het vergelijken van rijen uit glibc. Hoe is het mogelijk dat join een sorteerfout gaf op rijen gesorteerd door de opdracht sort in de locatie en_US.UTF-8? Ответ прост: sort vergelijkt de volledige rij, terwijl join alleen de sleutel vergelijkt, die standaard het begin van de rij is tot het eerste spatiekarakter. In mijn voorbeeld leidde dit tot een foutmelding omdat de sortering van de eerste woorden in de rijen niet overeenkwam met de sortering van de volledige rijen.

De locatie "C" garandeert dat de gesorteerde rijen met de beginonderdelen tot de eerste spatie ook sorteren, maar dit verbergt alleen de fout. Je kunt zulke gegevens verzamelen (mensen met dezelfde achternamen, maar verschillende voornamen), die zonder foutmelding een onjuist resultaat bij het samenvoegen van bestanden zouden opleveren. Als we willen dat join de rijen van bestanden op naam en achternaam samenvoegt, dan is de juiste manier om dit te doen het expliciet opgeven van de veldscheidingsteken en sorteren op het sleutelveld, in plaats van op de hele rij. In dat geval zal ook de samenvoeging correct verlopen en zullen er in geen enkele locatie fouten optreden:

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

Een succesvol uitgevoerd voorbeeld in codering CP1251 bevat nog een andere fout. Het probleem is dat in alle distributies die ik ken Linux de pakketten geen gecompileerde locale bevatten ru_RU.CP1251. Als de gecompileerde locale niet gevonden wordt, dan sort gebruikt het stilzwijgend byte-voor-byte vergelijking, wat we hebben waargenomen.

Trouwens, er is nog een klein probleem met het ontbreken van gecompileerde locales. De opdracht LOCPATH=/tmp locale -a geeft een lijst van alle locales terug in locale-archive, maar met de ingestelde variabele LOCPATH voor alle programma's (inclusief het programma zelf locale) zijn deze locales niet beschikbaar.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Kan LC_CTYPE niet instellen op standaard locale: Bestand of map bestaat niet
locale: Kan LC_MESSAGES niet instellen op standaard locale: Bestand of map bestaat niet
locale: Kan LC_COLLATE niet instellen op standaard locale: Bestand of map bestaat niet
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: gebruikmakend van ‘en_US.UTF-8’ sorteernormen

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: gebruikmakend van eenvoudige byte vergelijking

Conclusie

Als je een programmeur bent die gewend is te denken dat strings een reeks bytes zijn, is je keuze LC_COLLATE=C.

Als je een linguïst of woordenboekmaker bent, dan kun je beter je eigen locale compileren.

Als je een gewone gebruiker bent, dan hoef je alleen maar te wennen aan het feit dat de opdracht ls -a bestanden begint met een punt, samen met bestanden die beginnen met een letter, en Midnight Commander, die zijn interne functies voor het sorteren van namen gebruikt, plaatst bestanden die beginnen met een punt, aan het begin van de lijst.