Introductie

Het begon allemaal met een kort script dat adresgegevens moest combineren e-mail werknemers verkregen uit de lijst met mailinglijstgebruikers, terwijl werknemersposities zijn verkregen uit de database van de HR-afdeling. Beide lijsten zijn geëxporteerd naar Unicode-tekstbestanden UTF-8 en opgeslagen met Unix-regeleindes.

Inhoud mail.txt

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

Inhoud buhg.txt

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

Om samen te voegen werden de bestanden gesorteerd met het Unix-commando sorteren en onderworpen aan de invoer van het Unix-programma mee, die onverwachts mislukte met een fout:

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

Als u het sorteerresultaat met uw ogen bekijkt, is gebleken dat de sortering over het algemeen correct is, maar in het geval van samenvallen van mannelijke en vrouwelijke achternamen komen de vrouwelijke vóór de mannelijke:

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

Lijkt op een sorteerfout in Unicode of op een manifestatie van feminisme in het sorteeralgoritme. Het eerste is uiteraard plausibeler.

Laten we het voorlopig uitstellen mee en focus op sorteren. Laten we proberen het probleem op te lossen met behulp van wetenschappelijk porren. Laten we eerst de landinstelling wijzigen van nl_NL op ru_RU. Om te sorteren zou het voldoende zijn om de omgevingsvariabele in te stellen LC_COLLATE, maar we zullen geen tijd verspillen aan kleinigheden:

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

Er is niets veranderd.

Laten we proberen de bestanden te hercoderen naar een codering van één byte:

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

Opnieuw is er niets veranderd.

U kunt er niets aan doen, u zult op internet naar een oplossing moeten zoeken. Er is niets direct over Russische achternamen, maar er zijn vragen over andere sorteringseigenaardigheden. Hier is bijvoorbeeld een probleem: unix sort behandelt '-' (streepjes) tekens als onzichtbaar. Kortom, de strings "ab", "aa", "ac" worden gesorteerd als "aa", "ab", "ac".

Het antwoord is overal standaard: gebruik de landinstelling van de programmeur "C" en je zult gelukkig zijn. Laten we proberen:

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

Iets is veranderd. De Ivanovs stonden in de juiste volgorde opgesteld, hoewel Yolkina ergens uitgleed. Laten we terugkeren naar het oorspronkelijke probleem:

$> 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 internet beloofde. En dit ondanks Yolkina in de eerste regel.

Het probleem lijkt opgelost, maar laten we voor het geval een andere Russische codering proberen: Windows CP1251:

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

Het sorteerresultaat zal, vreemd genoeg, samenvallen met de landinstelling "C", en het hele voorbeeld werkt dienovereenkomstig zonder fouten. Een soort mystiek.

Ik hou niet van mystiek in programmeren, omdat het meestal fouten maskeert. We zullen serieus moeten onderzoeken hoe het werkt. sorteren en wat heeft het voor invloed? LC_COLLATE .

Aan het einde zal ik proberen de vragen te beantwoorden:

Waarom werden vrouwelijke achternamen verkeerd gesorteerd?
waarom LANG=ru_RU.CP1251 bleek gelijkwaardig LANG=C
waarom doe sorteren и mee verschillende ideeën over de volgorde van gesorteerde strings
waarom staan er fouten in al mijn voorbeelden?
eindelijk hoe je strings naar wens kunt sorteren

Sorteren in Unicode

De eerste stop is technisch rapport nr. 10 getiteld Unicode-sorteeralgoritme online Unicode.org. Het rapport bevat veel technische details, dus laat ik een korte samenvatting geven van de belangrijkste ideeën.

Vergelijking — Het “vergelijken” van tekenreeksen is de basis van elk sorteeralgoritme. De algoritmen zelf kunnen verschillen ("bubble", "merge", "fast"), maar ze zullen allemaal een vergelijking van een paar strings gebruiken om de volgorde te bepalen waarin ze verschijnen.

Het sorteren van tekenreeksen in natuurlijke taal is een tamelijk complex probleem. Zelfs bij de eenvoudigste single-byte-coderingen zal de volgorde van de letters in het alfabet, zelfs op een of andere manier verschillend van het Engelse Latijnse alfabet, niet langer samenvallen met de volgorde van de numerieke waarden waarmee deze letters zijn gecodeerd. Dus in het Duitse alfabet de letter Ö staat tussen О и P, en in de codering CP850 ze komt ertussen ÿ и Ü.

Je kunt proberen te abstraheren van een specifieke codering en 'ideale' letters overwegen die in een bepaalde volgorde zijn gerangschikt, zoals dat gebeurt in Unicode. Coderingen UTF8, UTF16 of één byte KOI8-R (als een beperkte subset van Unicode nodig is) geeft verschillende numerieke representaties van letters, maar verwijst naar dezelfde elementen van de basistabel.

Het blijkt dat zelfs als we een symbooltabel helemaal opnieuw opbouwen, we er geen universele symboolvolgorde aan kunnen toewijzen. In verschillende nationale alfabetten die dezelfde letters gebruiken, kan de volgorde van deze letters verschillen. In het Frans bijvoorbeeld Æ wordt beschouwd als een ligatuur en gesorteerd als een string AE. In het Noors Æ zal een aparte brief zijn, die zich daarna bevindt Z. Trouwens, naast ligaturen zoals Æ Er zijn letters geschreven met verschillende symbolen. Dus in het Tsjechische alfabet is er een letter Ch, die ertussen staat H и I.

Naast verschillen in alfabetten zijn er nog andere nationale tradities die het sorteren beïnvloeden. In het bijzonder rijst de vraag: in welke volgorde moeten woorden bestaande uit hoofdletters en kleine letters in het woordenboek verschijnen? Het sorteren kan ook worden beïnvloed door het gebruik van leestekens. In het Spaans wordt een omgekeerd vraagteken gebruikt aan het begin van een vragende zin (Hou je van muziek?). In dit geval is het duidelijk dat vragende zinnen niet in een apart cluster buiten het alfabet mogen worden gegroepeerd, maar hoe kunnen regels met andere leestekens worden gesorteerd?

Ik zal niet stilstaan bij het sorteren van strings in talen die heel anders zijn dan de Europese. Houd er rekening mee dat in talen met een schrijfrichting van rechts naar links of van boven naar beneden karakters in regels hoogstwaarschijnlijk in leesvolgorde worden opgeslagen, en dat zelfs niet-alfabetische schrijfsystemen hun eigen manieren hebben om regels karakter voor karakter te ordenen . Hiërogliefen kunnen bijvoorbeeld worden geordend op stijl (Chinese karakterssleutels) of op uitspraak. Eerlijk gezegd heb ik geen idee hoe emoji’s gerangschikt moeten worden, maar je kunt er ook iets voor verzinnen.

Op basis van de hierboven genoemde functies zijn de basisvereisten voor het vergelijken van tekenreeksen op basis van Unicode-tabellen geformuleerd:

vergelijking van strings is niet afhankelijk van de positie van karakters in de codetabel;
reeksen karakters die één enkel karakter vormen, worden teruggebracht tot een canonieke vorm (A + de bovenste cirkel is hetzelfde als Å);
Bij het vergelijken van tekenreeksen wordt een teken in de context van de tekenreeks beschouwd en, indien nodig, gecombineerd met zijn buren tot één vergelijkingseenheid (Ch in het Tsjechisch) of is verdeeld in verschillende (Æ in het Frans);
alle nationale kenmerken (alfabet, hoofdletters/kleine letters, interpunctie, volgorde van schrijftypen) moeten worden geconfigureerd tot aan de handmatige toewijzing van de volgorde (emoji);
Vergelijking is niet alleen belangrijk voor het sorteren, maar ook op veel andere plaatsen, bijvoorbeeld voor het specificeren van rijbereiken (vervanging van {A... z} in slaan);
de vergelijking moet vrij snel worden gedaan.

Bovendien formuleerden de auteurs van het rapport vergelijkingseigenschappen waar algoritme-ontwikkelaars niet op moeten vertrouwen:

het vergelijkingsalgoritme zou geen aparte set tekens voor elke taal moeten vereisen (Russische en Oekraïense talen delen de meeste Cyrillische tekens);
de vergelijking mag niet afhankelijk zijn van de volgorde van de tekens in Unicode-tabellen;
Het tekenreeksgewicht mag geen attribuut van de tekenreeks zijn, aangezien dezelfde tekenreeks in verschillende culturele contexten verschillende gewichten kan hebben;
rijgewichten kunnen veranderen bij het samenvoegen of splitsen (vanaf x < y daar volgt het niet uit xz < yz);
verschillende strings met hetzelfde gewicht worden vanuit het oogpunt van het sorteeralgoritme als gelijk beschouwd. Het introduceren van extra bestellingen van dergelijke snaren is mogelijk, maar dit kan de prestaties verslechteren;
Bij herhaaldelijk sorteren kunnen rijen met hetzelfde gewicht worden verwisseld. Robuustheid is een eigenschap van een specifiek sorteeralgoritme, en niet een eigenschap van een stringvergelijkingsalgoritme (zie de vorige paragraaf);
Sorteerregels kunnen in de loop van de tijd veranderen naarmate culturele tradities zich verfijnen/veranderen.

Er wordt ook bepaald dat het vergelijkingsalgoritme niets weet over de semantiek van de strings die worden verwerkt. Tekenreeksen die alleen uit cijfers bestaan, mogen dus niet als getallen worden vergeleken, en in lijsten met Engelse namen moet het lidwoord (Beatles, de).

Om aan alle gespecificeerde vereisten te voldoen, wordt een tabelsorteringsalgoritme met meerdere niveaus (eigenlijk vier niveaus) voorgesteld.

Voorheen werden de karakters in de string teruggebracht tot een canonieke vorm en gegroepeerd in vergelijkingseenheden. Aan elke vergelijkingseenheid worden verschillende gewichten toegekend die overeenkomen met verschillende vergelijkingsniveaus. De gewichten van vergelijkingseenheden zijn elementen van geordende sets (in dit geval gehele getallen) die min of meer kunnen worden vergeleken. Speciale betekenis BUITEN BESCHOUWING GELATEN (0x0) betekent dat deze eenheid op het overeenkomstige vergelijkingsniveau niet bij de vergelijking betrokken is. De vergelijking van strings kan meerdere keren worden herhaald, met behulp van de gewichten van de overeenkomstige niveaus. Op elk niveau worden de gewichten van de vergelijkingseenheden van twee rijen opeenvolgend met elkaar vergeleken.

In verschillende implementaties van het algoritme voor verschillende nationale tradities kunnen de waarden van de coëfficiënten verschillen, maar de Unicode-standaard bevat een basistabel met gewichten - "Standaard Unicode-sorteerelementtabel" (DUCET). Ik zou graag willen opmerken dat het instellen van de variabele LC_COLLATE is eigenlijk een indicatie van de selectie van de gewichtstabel in de stringvergelijkingsfunctie.

Wegingscoëfficiënten DUCET als volgt gerangschikt:

op het eerste niveau worden alle letters teruggebracht tot dezelfde hoofdletter, diakritische tekens worden weggegooid en leestekens (niet alle) worden genegeerd;
op het tweede niveau wordt alleen rekening gehouden met diakritische tekens;
op het derde niveau wordt alleen rekening gehouden met gevallen;
op het vierde niveau wordt alleen rekening gehouden met leestekens.

De vergelijking vindt plaats in verschillende stappen: eerst worden de coëfficiënten van het eerste niveau vergeleken; als de gewichten samenvallen, wordt een herhaalde vergelijking met de gewichten van het tweede niveau uitgevoerd; dan misschien een derde en een vierde.

De vergelijking eindigt wanneer de rijen overeenkomende vergelijkingseenheden met verschillende gewichten bevatten. Rijen met een gelijk gewicht op alle vier de niveaus worden als gelijk aan elkaar beschouwd.

Dit algoritme (met een heleboel aanvullende technische details) gaf de naam aan rapport nr. 10 - "Unicode-collatie-algoritme" (ACU).

Dit is waar het sorteergedrag uit ons voorbeeld iets duidelijker wordt. Het zou leuk zijn om het te vergelijken met de Unicode-standaard.

Om implementaties te testen ACU er is een speciaal тест, gebruik makend van gewichten bestand, implementeren DUCET. In het weegschaalbestand vind je allerlei grappige dingen. Er is bijvoorbeeld de volgorde van mahjong en Europese dominostenen, evenals de volgorde van de kleuren in een kaartspel (symbool 1F000 en verder). Kaartkleuren worden geplaatst volgens de bridgeregels - PCBT, en de kaarten in de reeks hebben de volgorde T, 2,3, XNUMX... K.

Handmatig controleren of rijen correct zijn gesorteerd op basis van DUCET zou behoorlijk vervelend zijn, maar gelukkig voor ons is er een voorbeeldige implementatie van de bibliotheek voor het werken met Unicode - "Internationale componenten voor Unicode"(ICU).

Op de website van deze bibliotheek, ontwikkeld in IBM, er zijn demopagina's, inclusief algoritmepagina voor tekenreeksvergelijking. We voeren onze testlijnen in met standaardinstellingen en zie, we krijgen een perfecte Russische sortering.

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

Trouwens, de website ICU U kunt een verduidelijking van het vergelijkingsalgoritme vinden bij het verwerken van leestekens. In voorbeelden Veelgestelde vragen over sorteren apostrof en koppelteken worden genegeerd.

Unicode heeft ons geholpen, maar zoek naar redenen voor vreemd gedrag sorteren в Linux zal ergens anders heen moeten.

Sorteren in glibc

Snel overzicht van de broncodes van de hulpprogramma's sorteren van GNU Core-hulpprogramma's toonde aan dat lokalisatie in het hulpprogramma zelf neerkomt op het afdrukken van de huidige waarde van de variabele LC_COLLATE wanneer u in debug-modus werkt:

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

Stringvergelijkingen worden uitgevoerd met behulp van de standaardfunctie strcoll, wat betekent dat alles wat interessant is in de bibliotheek staat glibc.

Op wiki project glibc gewijd aan stringvergelijking één paragraaf. Uit deze paragraaf kan worden opgemaakt dat in glibc het sorteren is gebaseerd op een algoritme dat al bij ons bekend is ACU (Het Unicode-collatie-algoritme) en/of op een standaard die daar dichtbij ligt ISO 14651 (Internationale snaren bestellen en vergelijken). Wat de nieuwste standaard betreft, moet worden opgemerkt dat dit op de site staat normen.iso.org ISO 14651 officieel openbaar beschikbaar verklaard, maar de bijbehorende link leidt naar een niet-bestaande pagina. Google retourneert verschillende pagina's met links naar officiële sites die aanbieden om voor honderd euro een elektronische kopie van de standaard te kopen, maar op de derde of vierde pagina met zoekresultaten staan ook directe links naar PDF. Over het algemeen verschilt de standaard praktisch niet van ACU, maar is saaier om te lezen omdat het geen duidelijke voorbeelden bevat van nationale kenmerken van stringsortering.

De meest interessante informatie over wiki er was een link naar bug-tracker met een bespreking van de implementatie van stringvergelijking in glibc. Uit de discussie kan dat geleerd worden glibc gebruikt om strings te vergelijken ISOpersoonlijke tafel De gemeenschappelijke sjabloontabel (CTT), waarvan het adres te vinden is in de aanvraag A standaard- ISO 14651 . Tussen 2000 en 2015 is deze tabel in glibc had geen onderhouder en was behoorlijk verschillend (althans extern) van de huidige versie van de standaard. Van 2015 tot 2018 vond aanpassing aan de nieuwe versie van de tafel plaats, en nu heb je de kans om in het echt een nieuwe versie van de tafel te ontmoeten (8 CentOS), en oud (7 CentOS).

Nu we alle informatie over het algoritme en de hulptabellen hebben, kunnen we terugkeren naar het oorspronkelijke probleem en begrijpen hoe we tekenreeksen correct kunnen sorteren in de Russische landinstelling.

ISO 14651 / 14652

Broncode van de tabel waarin we geïnteresseerd zijn CTT op de meeste distributies Linux staat in de directory /usr/share/i18n/locales/. De tabel zelf bevindt zich in het bestand iso14651_t1_common. Dan is dit de bestandsrichtlijn kopieer iso14651_t1_common opgenomen in het bestand iso14651_t1, die op zijn beurt wordt opgenomen in nationale bestanden, waaronder nl_NL и ru_RU. Op de meeste distributies Linux alle bronbestanden zijn opgenomen in de basisinstallatie, maar als ze niet aanwezig zijn, zul je een extra pakket uit de distributie moeten installeren.

Bestandsstructuur iso14651_t1 lijkt misschien vreselijk uitgebreid, met niet voor de hand liggende regels voor het construeren van namen, maar als je ernaar kijkt, is alles vrij eenvoudig. De structuur wordt beschreven in de standaard ISO 14652 , waarvan u een kopie kunt downloaden van de website open-std.org. Een andere beschrijving van het bestandsformaat kan worden ingelezen specificaties: POSIX van OpenGroep. Als alternatief voor het lezen van de standaard kunt u de broncode van de functie bestuderen verzamelen_lezen в glibc/locale/programs/ld-collate.c.

De bestandsstructuur ziet er als volgt uit:

Standaard wordt het teken gebruikt als escape-teken, en het einde van de regel na het #-teken is commentaar. Beide symbolen kunnen opnieuw worden gedefinieerd, wat gebeurt in de nieuwe versie van de tabel:

escape_char /
comment_char %

Het bestand bevat tokens in het formaat of (Waar x - hexadecimaal cijfer). Dit is de hexadecimale weergave van Unicode-codepunten in de codering UCS-4 (UTF-32). Alle andere elementen tussen hoekhaken (inclusief , <2> en dergelijke) worden beschouwd als eenvoudige tekenreeksconstanten die buiten de context weinig betekenis hebben.

rij LC_COLLATE vertelt ons dat vervolgens de gegevens beginnen die de vergelijking van strings beschrijven.

Eerst worden namen opgegeven voor de gewichten in de vergelijkingstabel en namen voor de symboolcombinaties. Over het algemeen behoren de twee soorten namen tot twee verschillende entiteiten, maar in het eigenlijke bestand zijn ze gemengd. De namen van de gewichten worden gespecificeerd door het trefwoord sorteersymbool (vergelijkingsteken) omdat bij het vergelijken Unicode-tekens met hetzelfde gewicht als gelijkwaardige tekens worden beschouwd.

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

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

verzamel-symbool logt een string OSMANYA in de tabel met namen van schalen
verzamel-symbool .. registreert een reeks namen bestaande uit een voorvoegsel S en hexadecimaal numeriek achtervoegsel van 1D000 naar 1D35F.
FFFF в verzamel-symbool ziet eruit als een groot geheel getal zonder teken in hexadecimaal, maar het is gewoon een naam die er misschien zo uitziet
Naam betekent codepunt in codering UCS-4
verzamelelement van " " registreert een nieuwe naam voor een paar Unicode-punten.

Zodra de namen van de gewichten zijn gedefinieerd, worden de werkelijke gewichten gespecificeerd. Omdat in vergelijking alleen groter-dan-minder-relaties van belang zijn, worden de gewichten bepaald door een eenvoudige reeks lijstnamen. De “lichtere” gewichten worden eerst vermeld, daarna de “zwaardere”. Ik wil u eraan herinneren dat aan elk Unicode-teken vier verschillende gewichten zijn toegewezen. Hier worden ze gecombineerd tot een enkele geordende reeks. In theorie zou elke symbolische naam op elk van de vier niveaus kunnen worden gebruikt, maar uit opmerkingen blijkt dat de ontwikkelaars de namen mentaal in niveaus verdelen.

% 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

Tenslotte de tabel met werkelijke gewichten.

Het gewichtengedeelte is ingesloten in trefwoordregels order_start и bestelling_einde. Extra opties order_start bepalen in welke richting rijen worden gescand op elk vergelijkingsniveau. De standaardinstelling is vooruit. De hoofdtekst van de sectie bestaat uit regels die de symboolcode en de vier gewichten ervan bevatten. De tekencode kan worden weergegeven door het teken zelf, een codepunt of een eerder gedefinieerde symbolische naam. Er kunnen ook gewichten worden toegekend aan symbolische namen, codepunten of de symbolen zelf. Als er codepunten of tekens worden gebruikt, is hun gewicht hetzelfde als de numerieke waarde van het codepunt (positie in de Unicode-tabel). Tekens die niet expliciet zijn gespecificeerd (zoals ik begrijp) worden beschouwd als toegewezen aan de tabel met een primair gewicht dat overeenkomt met de positie in de Unicode-tabel. Speciale gewichtswaarde NEGEREN betekent dat het symbool wordt genegeerd op het juiste vergelijkingsniveau.

Om de structuur van de toonladders te demonstreren, heb ik drie vrij voor de hand liggende fragmenten gekozen:

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

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

Nu kunt u terugkeren naar het sorteren van de voorbeelden vanaf het begin van het artikel. De hinderlaag ligt in dit deel van de gewichtentabel:

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

Het is te zien dat in deze tabel de leestekens uit de tabel staan ASCII (inclusief spatie) wordt bijna altijd genegeerd bij het vergelijken van tekenreeksen. De enige uitzonderingen zijn regels die in alles overeenkomen, behalve leestekens die op overeenkomende posities voorkomen. De regels uit mijn voorbeeld (na sorteren) voor het vergelijkingsalgoritme zien er als volgt uit:

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

Gezien het feit dat in de tabel met schalen hoofdletters in het Russisch na kleine letters komen (op het derde niveau zwaarder dan ), de sortering ziet er absoluut correct uit.

Bij het instellen van een variabele LC_COLLATE=C er wordt een speciale tabel geladen die een byte-voor-byte-vergelijking specificeert

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

Omdat in Unicode het codepunt Ё vóór A komt, worden de strings dienovereenkomstig gesorteerd.

Tekst- en binaire tabellen

Het is duidelijk dat het vergelijken van tekenreeksen een zeer gebruikelijke bewerking is, evenals het parseren van tabellen CTT een vrij kostbare procedure. Om de toegang tot de tabel te optimaliseren, wordt deze met het commando in binaire vorm gecompileerd lokaledef.

Team lokaledef accepteert als parameters een bestand met een tabel met nationale kenmerken (optie -i), waarin alle tekens worden weergegeven door Unicode-punten, en een bestand met correspondentie tussen Unicode-punten en tekens met een specifieke codering (optie -f). Als resultaat van het werk worden binaire bestanden gemaakt voor de landinstelling met de naam die is opgegeven in de laatste parameter.

glibc ondersteunt twee binaire bestandsformaten: "traditioneel" en "modern".

Het traditionele formaat betekent dat de naam van de landinstelling de naam is van de submap waarin /usr/lib/locale/. In deze submap worden binaire bestanden opgeslagen LC_COLLATE, LC_CTYPE, LC_TIME enzovoort. Bestand LC_IDENTIFICATIE bevat de formele naam van de landinstelling (die kan verschillen van de mapnaam) en opmerkingen.

Het moderne formaat omvat het opslaan van alle landinstellingen in één enkel archief /usr/lib/locale/locale-archive, dat is toegewezen aan het virtuele geheugen van alle processen die gebruikmaken van glibc. De landinstellingsnaam in het moderne formaat is onderhevig aan enige heiligverklaring - alleen cijfers en letters, teruggebracht tot kleine letters, blijven in de coderingsnamen staan. Dus ru_RU.KOI8-R, wordt opgeslagen als ru_RU.koi8r.

Invoerbestanden worden zowel in de huidige map als in mappen doorzocht /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ voor bestanden CTT en het coderen van bestanden, respectievelijk.

Het commando bijvoorbeeld

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

zal het bestand compileren /usr/share/i18n/locales/ru_RU met behulp van een coderingsbestand /usr/share/i18n/charmaps/MAC-CYRILLIC.gz en sla het resultaat op /usr/lib/locale/locale-archive onder de naam ru_RU.maccyrillisch

Als u de variabele instelt LANG = en_US.UTF-8 то glibc zal zoeken naar binaire bestanden 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 een locale zowel in traditionele als moderne formaten voorkomt, wordt prioriteit gegeven aan de moderne.

U kunt de lijst met gecompileerde landinstellingen bekijken met de opdracht locale -a.

Uw vergelijkingstabel voorbereiden

Nu kunt u, gewapend met deze kennis, uw eigen ideale stringvergelijkingstabel maken. Deze tabel moet Russische letters correct vergelijken, inclusief de letter Ё, en tegelijkertijd rekening houden met leestekens in overeenstemming met de tabel ASCII.

Het proces van het voorbereiden van uw eigen sorteertabel bestaat uit twee fasen: het bewerken van de gewichtentabel en het compileren ervan in binaire vorm met het commando lokaledef.

Zodat de vergelijkingstabel met minimale bewerkingskosten kan worden aangepast in het formaat ISO 14652 Er zijn secties voorzien voor het aanpassen van de gewichten van een bestaande tafel. Het gedeelte begint met een trefwoord opnieuw bestellen-na en het aangeven van de positie waarna de vervanging wordt uitgevoerd. Het gedeelte eindigt met de lijn opnieuw ordenen-einde. Als het nodig is om meerdere secties van de tabel te corrigeren, wordt voor elke sectie een sectie gemaakt.

Ik heb nieuwe versies van de bestanden gekopieerd iso14651_t1_common и ru_RU uit de repository glibc naar mijn thuismap ~/.local/share/i18n/locales/ en heb de sectie enigszins bewerkt LC_COLLATE в ru_RU. Nieuwe versies van bestanden zijn volledig compatibel met mijn versie glibc. Als u oudere versies van bestanden wilt gebruiken, moet u de symbolische namen en de plaats waar de vervanging begint in de tabel wijzigen.

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

In feite zou het nodig zijn om de velden in te wijzigen LC_IDENTIFICATIE zodat ze naar de landinstelling verwijzen ru_MIJN, maar in mijn voorbeeld was dit niet vereist, omdat ik het archief had uitgesloten van het zoeken naar landinstellingen locale-archief.

Dat lokaledef werkte met bestanden in mijn map via een variabele I18NPATH U kunt een extra map toevoegen om naar invoerbestanden te zoeken, en de map om binaire bestanden op te slaan 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 gaat ervan uit dat in TAAL je kunt absolute paden schrijven naar mappen met localebestanden, beginnend met een schuine streep, maar glibc в Linux alle paden worden geteld vanuit de basismap, die kan worden overschreven via een variabele LOCPATH. Na installatie LOCPATH=~/.local/lib/locale/ alle bestanden met betrekking tot lokalisatie worden alleen in mijn map doorzocht. Archief van landinstellingen met de variabelenset LOCPATH buiten beschouwing gelaten.

Hier is de beslissende test:

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

Hoera! We hebben het gedaan!

Sommige fouten

Ik heb de vragen over het sorteren van strings die in het begin zijn gesteld al beantwoord, maar er zijn nog een paar vragen over fouten - zichtbare en onzichtbare.

Laten we terugkeren naar het oorspronkelijke probleem.

En het programma sorteren en programma mee gebruik dezelfde tekenreeksvergelijkingsfuncties van glibc. Hoe kwam het dat mee gaf een sorteerfout op rijen gesorteerd door de opdracht sorteren op locatie nl_US.UTF-8? Het antwoord is simpel: sorteren vergelijkt de hele reeks, en mee vergelijkt alleen de sleutel, die standaard het begin van de tekenreeks is tot aan het eerste witruimteteken. In mijn voorbeeld resulteerde dit in een foutmelding omdat de sortering van de eerste woorden in de regels niet overeenkwam met de sortering van de volledige regels.

Lokaal "C" garandeert dat in gesorteerde strings de initiële substrings tot aan de eerste spatie ook worden gesorteerd, maar dit maskeert alleen de fout. Het is mogelijk om gegevens te selecteren (mensen met dezelfde achternaam, maar verschillende voornamen) die, zonder de foutmelding, een onjuist resultaat van het samenvoegen van bestanden zouden opleveren. Als wij dat willen mee samengevoegde bestandsregels op volledige naam, dan zou de juiste manier zijn om expliciet het veldscheidingsteken op te geven en te sorteren op het sleutelveld, en niet op de hele regel. In dit geval zal de samenvoeging correct verlopen en zullen er geen fouten optreden in welke landinstelling dan ook:

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

Met succes uitgevoerd voorbeeld in codering CP1251 bevat nog een fout. Feit is dat het in alle mij bekende distributies voorkomt Linux pakketten missen de gecompileerde landinstelling ru_RU.CP1251. Als de gecompileerde landinstelling niet wordt gevonden, dan sorteren maakt in stilte gebruik van een byte-voor-byte-vergelijking, wat we hebben waargenomen.

Er is trouwens nog een klein probleempje dat verband houdt met de ontoegankelijkheid van gecompileerde landinstellingen. Team LOCPATH=/tmp landinstelling -a geeft een lijst met alle locales in locale-archief, maar met de variabelenset LOCPATH voor alle programma's (inclusief de meeste lokaal) zijn deze landinstellingen niet beschikbaar.

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

Conclusie

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

Als u een taalkundige of woordenboekcompiler bent, kunt u het beste in uw landinstelling compileren.

Als u een eenvoudige gebruiker bent, moet u gewoon wennen aan het feit dat de opdracht ls -a voert bestanden uit die beginnen met een punt, gemengd met bestanden die beginnen met een letter, en Middernacht commandant, dat zijn interne functies gebruikt om namen te sorteren, plaatst bestanden die beginnen met een punt aan het begin van de lijst.