Einführung

Alles begann mit einem kurzen Skript, das Informationen über Adressen e-mail von Mitarbeitern, die aus der Liste der Mailinglistenbenutzer stammten, mit den Positionen der Mitarbeiter zu kombinieren, die aus der Datenbank der Personalabteilung gewonnen wurden. Beide Listen wurden in Textdateien im Unicode-Format exportiert UTF-8 und mit Unix-Zeilenenden gespeichert.

Inhalt mail.txt

Ivanov Andrej;ia@example.com

Inhalt buhg.txt

Ivanova Alla;Maler
Elkina Ella;Kranführerin
Ivanov Andrej;Installateur
Abakanov Michail;Maler

Um die Dateien zu kombinieren, wurden sie mit dem Unix-Befehl sortiert sortieren und an ein Unix-Programm übergeben beitreten, das unerwartet mit einem Fehler abgebrochen wurde:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: ist nicht sortiert: Ivanov Andrej;Installateur

Ein Blick auf das Sortierungsergebnis zeigte, dass die Sortierung insgesamt korrekt war, aber im Falle von Übereinstimmungen zwischen männlichen und weiblichen Nachnamen die weiblichen vor den männlichen stehen:

$> sort buhg.txt
Abakanov Michail;Maler
Elkina Ella;Kranführerin
Ivanova Alla;Maler
Ivanov Andrej;Installateur

Sieht aus wie ein Sortierfehler in Unicode oder wie eine Manifestation von Feminismus im Sortieralgorithmus. Letzteres ist natürlich wahrscheinlicher.

Lassen wir es erstmal beiseite beitreten und konzentrieren uns auf sortieren. Versuchen wir, das Problem mit Trial and Error zu lösen. Zuerst ändern wir die Locale von en_US findet man ru_RU. Für die Sortierung würde es ausreichen, die Umgebungsvariable LC_COLLATE, aber wir wollen es nicht so kleinlich machen:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Michail;Maler
Jolkina Ella;Kranführerin
Ivanova Alla;Maler
Ivanov Andrej;Installateur

Es hat sich nichts geändert.

Lassen Sie uns versuchen, die Dateien in eine einbyteartige Codierung umzuwandeln:

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

Wieder hat sich nichts geändert.

Da hilft nichts, wir müssen im Internet nach einer Lösung suchen. Direkte Informationen über russische Nachnamen gibt es nicht, aber es gibt Fragen zu anderen Sortierproblemen. Hier ist beispielsweise eine solche Problematik: unix sort behandelt ‚-‘ (Bindestrich) Zeichen als unsichtbar. Kurz gesagt, die Strings "a-b", "aa", "ac" werden als "aa", "a-b", "ac" sortiert.

Die Antwort ist überall gleich: Verwenden Sie die Programmier-Locale "C" und Sie werden glücklich sein. Probieren wir es:

$> LANG=C sort buhg.txt
Jolkina Ella;Kranführerin
Abakanov Michail;Maler
Ivanov Andrej;Installateur
Ivanova Alla;Rechtsanwältin

Etwas hat sich verändert. Die Ivanovs sind nun in der richtigen Reihenfolge, aber Jolkina ist irgendwo hin gerutscht. Kehren wir zur ursprünglichen Aufgabe zurück:

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

Es hat ohne Fehler funktioniert, wie das Internet versprochen hat. Und das trotz Jolkina in der ersten Zeile.

Das Problem scheint gelöst zu sein, aber vorsichtshalber probieren wir noch eine russische Kodierung aus – die Windows-Kodierung. CP1251:

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

Das Sortierungsergebnis wird seltsamerweise mit der Locale übereinstimmen. "C", und das gesamte Beispiel verläuft dementsprechend ohne Fehler. Irgendwelche Mystik.

Ich liebe keine Mystik in der Programmierung, da sie normalerweise Fehler verschleiert. Ich werde mich ernsthaft mit der Frage beschäftigen, wie es funktioniert. sortieren und welchen Einfluss es hat. LC_COLLATE .

Am Ende werde ich versuchen, die Fragen zu beantworten:

warum die weiblichen Nachnamen nicht richtig sortiert wurden.
das LANG=ru_RU.CP1251 stellte sich als äquivalent heraus. LANG=C
warum verschiedene sortieren und beitreten Darstellungen der sortierten Zeilen existieren.
warum alle meine Beispiele Fehler enthalten.
schließlich, wie man die Zeilen nach seinem Geschmack sortiert.

Sortierung in Unicode.

Der erste Halt wird der technische Bericht Nr. 10 mit dem Titel Unicode collation algorithm auf der Website unicode.org. Der Bericht enthält viele technische Details, daher gestatte ich mir, eine kurze Zusammenfassung der Hauptideen zu geben.

Kollation — „Vergleich“ von Strings ist die Grundlage jedes Sortieralgorithmus. Die Algorithmen selbst können variieren (z.B. „Bubble“, „Merge“, „Quick“), aber sie alle verwenden den Vergleich von Paaren von Strings, um die Reihenfolge ihrer Anordnung zu bestimmen.

Die Sortierung von Strings in natürlicher Sprache ist ein recht komplexes Problem. Selbst in den einfachsten Ein-Byte-Codierungen stimmt die Reihenfolge der Buchstaben im Alphabet, wenn es sich von der englischen lateinischen Schrift unterscheidet, nicht mit den numerischen Werten überein, die diese Buchstaben kodieren. So steht im deutschen Alphabet der Buchstabe Ö zwischen e und P, und in der Codierung CP850 liegt er zwischen ÿ und Ü.

Man kann versuchen, sich von der spezifischen Codierung zu abstrahieren und „ideale“ Buchstaben zu betrachten, die in einer bestimmten Reihenfolge angeordnet sind, wie es im Unicode der Fall ist. Die Codierungen UTF8, UTF16 oder die einbyteige KOI8-R (wenn ein begrenztes Teilmenü des Unicode benötigt wird) werden unterschiedliche numerische Darstellungen der Buchstaben liefern, sich aber gleichzeitig auf die gleichen Elemente der Basistabelle beziehen.

Es stellt sich heraus, dass wir selbst beim Erstellen einer Zeichentabelle von Grund auf keinen universellen Sortierungsauftrag für die Zeichen festlegen können. In verschiedenen nationalen Alphabeten, die dieselben Buchstaben verwenden, kann die Reihenfolge dieser Buchstaben unterschiedlich sein. Zum Beispiel im Französischen Æ wird als Ligatur betrachtet und als Zeichenfolge sortiert. Vereinigte Arabische EmirateIm Norwegischen hingegen Æ ist es ein separater Buchstabe, der nach Zzu finden ist. Übrigens gibt es neben Ligaturen wie Æ auch Buchstaben, die mit mehreren Zeichen geschrieben werden. So gibt es im Tschechischen den Buchstaben Ch, der zwischen H und I.

liegt. Neben den Unterschieden in den Alphabeten gibt es auch andere nationale Traditionen, die die Sortierung beeinflussen. Insbesondere stellt sich die Frage: In welcher Reihenfolge sollten Wörter im Wörterbuch erscheinen, die aus Groß- und Kleinbuchstaben bestehen? Auch die Verwendung von Satzzeichen kann die Sortierung beeinflussen. Im Spanischen steht am Anfang eines Fragesatzes ein umgekehrtes Fragezeichen (¿Te gusta la música?). In diesem Fall ist offensichtlich, dass Frageätze nicht außerhalb des Alphabets in einen eigenen Cluster gruppiert werden sollten. Aber wie sortiert man Strings mit anderen Satzzeichen?

Ich werde nicht auf die Sortierung von Strings in stark von europäischen Sprachen abweichenden Sprachen eingehen. Ich möchte darauf hinweisen, dass in Sprachen mit einer Schreibrichtung von rechts nach links oder von oben nach unten die Zeichen in Strings wahrscheinlich in der Reihenfolge des Lesens gespeichert sind, und selbst in nicht-alphabetischen Schriften gibt es Wege, Strings zeichenweise zu ordnen. Zum Beispiel können Hieroglyphen nach Form (Schlüsseln chinesischer Hieroglyphen) oder nach Aussprache sortiert werden. Wie Emojis sortiert werden sollten, kann ich ehrlich gesagt nicht sagen, aber auch dafür kann man sich etwas einfallen lassen.

Auf der Grundlage der oben genannten Merkmale wurden die grundlegenden Anforderungen an den Vergleich von Strings, die auf Unicode-Tabellen basieren, formuliert:

der Vergleich von Strings hängt nicht von der Position der Zeichen in der Kodierungstabelle ab;
Zeichenfolgen, die ein einzelnes Zeichen bilden, werden in die kanonische Form gebracht (A + der obere Punkt ist dasselbe wie Å);
Bei der Zeichenvergleich wird das Zeichen im Kontext der Zeichenfolge betrachtet und, falls erforderlich, mit benachbarten Zeichen zu einer Vergleichseinheit kombiniert (Ch im Tschechischen) oder in mehrere zerlegt (Æ im Französischen);
alle nationalen Besonderheiten (Alphabet, Groß-/Kleinbuchstaben, Interpunktion, Reihenfolge der Schriftarten) müssen bis hin zu manuellen Zuweisungen der Reihenfolge (Emojis) konfiguriert werden;
der Vergleich ist nicht nur für die Sortierung wichtig, sondern auch an vielen anderen Stellen, beispielsweise für die Festlegung von Zeichenfolgenbereichen (Platzhalter {A… я} in bash);
der Vergleich sollte schnell genug durchgeführt werden.

Darüber hinaus haben die Autoren des Berichts Eigenschaften des Vergleichs formuliert, auf die Algorithmusentwickler nicht vertrauen sollten:

der Vergleichsalgorithmus sollte nicht für jede Sprache ein separates Zeichenset benötigen (Russisch und Ukrainisch verwenden größtenteils dieselben kyrillischen Zeichen);
der Vergleich sollte nicht auf der Reihenfolge der Zeichen in den Unicode-Tabellen basieren;
das Gewicht einer Zeichenfolge sollte kein Attribut der Zeichenfolge sein, da eine und dieselbe Zeichenfolge in unterschiedlichen kulturellen Kontexten unterschiedliche Gewichtungen haben kann;
Die Gewichte der Zeichenfolgen können sich beim Zusammenführen oder Aufteilen ändern (aus x < y es folgt nicht, dass xz < yz);
verschiedene Zeichenfolgen, die dieselben Gewichte aufweisen, als gleich angesehen werden im Sinne des Sortieralgorithmus. Eine zusätzliche Anordnung solcher Zeichenfolgen ist möglich, kann jedoch die Leistung beeinträchtigen;
bei wiederholten Sortierungen können Zeichenfolgen mit gleichen Gewichten ihre Plätze tauschen. Stabilität ist eine Eigenschaft eines bestimmten Sortieralgorithmus und nicht eine Eigenschaft des Vergleichsalgorithmus für Zeichenfolgen (siehe den vorherigen Punkt);
Die Sortierregeln können sich im Laufe der Zeit ändern, während kulturelle Traditionen verfeinert oder geändert werden.

Es ist auch festgelegt, dass der Vergleichsalgorithmus nichts über die Semantik der verarbeiteten Zeichenfolgen weiß. So sollten Zeichenfolgen, die nur aus Ziffern bestehen, nicht als Zahlen verglichen werden, und in Listen englischer Bezeichnungen sollte der Artikel nicht entfernt werden (Beatles, The).

Um allen angegebenen Anforderungen gerecht zu werden, wurde ein mehrstufiger (tatsächlich vierstufiger) tabellarischer Sortieralgorithmus vorgeschlagen.

Zunächst werden die Zeichen in der Zeichenfolge in eine kanonische Form umgewandelt und in Vergleichseinheiten gruppiert. Jede Vergleichseinheit erhält mehrere Gewichte, die verschiedenen Vergleichsebenen entsprechen. Die Gewichte der Vergleichseinheiten sind Elemente geordneter Mengen (in diesem Fall ganze Zahlen), die in Bezug auf größer-kleiner verglichen werden können. Ein spezieller Wert IGNORED (0x0) bedeutet, dass die betreffende Einheit auf der entsprechenden Vergleichsebene nicht am Vergleich teilnimmt. Der Vergleich von Zeichenfolgen kann mehrmals unter Verwendung der Gewichte der entsprechenden Ebenen wiederholt werden. Auf jeder der Ebenen werden die Gewichte der Vergleichseinheiten zweier Zeichenfolgen nacheinander miteinander verglichen.

In verschiedenen Implementierungen des Algorithmus können die Werte der Koeffizienten je nach nationaler Tradition variieren, aber der Unicode-Standard enthält eine grundlegende Gewichtungstabelle - "Default Unicode Collation Element Table" (DUCET). Ich möchte darauf hinweisen, dass die Festlegung einer Variablen tatsächlich eine Anweisung zur Auswahl der Gewichtungstabelle in der Funktion zum Vergleich von Zeichenfolgen ist. LC_COLLATE Die Gewichtungskoeffizienten

sind wie folgt aufgebaut: DUCET sind wie folgt strukturiert:

Auf der ersten Ebene werden alle Buchstaben in eine einheitliche Schreibweise umgewandelt, diakritische Zeichen werden entfernt, und die Zeichensetzung (nicht alle) wird ignoriert;
Auf der zweiten Ebene werden nur diakritische Zeichen berücksichtigt;
Auf der dritten Ebene wird nur die Groß- und Kleinschreibung berücksichtigt;
Auf der vierten Ebene werden nur die Satzzeichen berücksichtigt.

Der Vergleich erfolgt in mehreren Durchgängen: Zunächst werden die Koeffizienten der ersten Ebene verglichen; wenn die Gewichte übereinstimmen, erfolgt ein erneuter Vergleich mit den Gewichten der zweiten Ebene; anschließend eventuell der dritten und vierten.

Der Vergleich endet, wenn in den Zeichenfolgen übereinstimmende Vergleichseinheiten mit unterschiedlichen Gewichten vorhanden sind. Zeichenfolgen, die in allen vier Ebenen die gleichen Gewichte aufweisen, gelten als gleichwertig.

Dieser Algorithmus (mit einer Menge zusätzlichen technischen Details) gab den Namen für Bericht Nr. 10 — "Unicode Collation Algorithm" (UCA).

An dieser Stelle wird das Sortierverhalten aus unserem Beispiel etwas verständlicher. Es wäre gut, dies mit dem Unicode-Standard zu vergleichen.

Für Implementierungstests UCA gibt es einen speziellen Test, der eine Gewichtedatei verwendet, die DUCET. In der Datei mit den Gewichtungen kann man verschiedene Kuriositäten finden. Zum Beispiel gibt es dort die Reihenfolge der Mahjong-Steine und des europäischen Dominospiels sowie die Reihenfolge der Farben in einem Kartenspiel (Symbol 1F000 und weiter). Die Kartenfarben sind nach den Regeln des Bridge angeordnet — PCHBT, und die Karten innerhalb der Farben — in der Reihenfolge T, 2, 3… K.

Eine manuelle Überprüfung der Richtigkeit der Sortierung der Zeilen gemäß DUCET wäre ziemlich mühsam, aber zum Glück gibt es eine vorbildliche Umsetzung einer Bibliothek zur Arbeit mit Unicode — "International Components for Unicode" (ICU).

Auf der Webseite dieser Bibliothek, die in IBM, gibt es Demoseiten, darunter auch die Seite für den Vergleich von Zeichenfolgen. Wir geben unsere Testzeichenfolgen mit den Standardeinstellungen ein und, oh Wunder, wir erhalten eine perfekte russische Sortierung.

Abakanov Michail;Maler
Yolkina Ella;Kranführerin
Ivanov Andrej;Schlosser
Ivanova Alla;Rechtsanwältin

Übrigens finden Sie auf der Webseite ICU eine Erläuterung zur Funktionsweise des Vergleichsalgorithmus bei der Verarbeitung von Satzzeichen. In den Beispielen Collation FAQ werden Apostrophe und Bindestrich ignoriert.

Unicode hat uns geholfen, aber die Gründe für das seltsame Verhalten sortieren in Linux müssen wir woanders suchen.

Sortierung in glibc

Schnellansicht des Quellcodes des Dienstprogramms sortieren von GNU Core Utils zeigte, dass die Lokalisierung in dem Dienstprogramm auf den Druck des aktuellen Wertes der Variablen beschränkt ist LC_COLLATE bei der Ausführung im Debug-Modus:

$ sort --debug buhg.txt > buhg.srt
sort: verwendet die Sortierregeln von ‘en_US.UTF8’

Der Vergleich von Zeichenfolgen erfolgt mit der Standardfunktion strcoll, was bedeutet, dass alles Interessante in der Bibliothek zu finden ist glibc..

Auf Wiki Projekts glibc. dem Vergleich von Zeichenfolgen gewidmet ein Absatz. Aus diesem Absatz kann man verstehen, dass die glibc. Sortierung auf dem bereits bekannten Algorithmus basiert UCA (The Unicode collation algorithm) und/oder einem ähnlichen Standard ISO 14651 (Internationale Reihenfolge und Vergleich von Zeichenfolgen). Zum letzten Standard sei angemerkt, dass er auf der Website standards.iso.org ISO 14651 offiziell als öffentlich zugänglich erklärt wurde, aber der entsprechende Link führt zu einer nicht existierenden Seite. Google bringt mehrere Seiten mit Links zu offiziellen Seiten hervor, die anbieten, eine elektronische Kopie des Standards für mehrere hundert Euro zu kaufen, aber auf der dritten oder vierten Seite der Suchergebnisse finden sich auch direkte Links zu PDF. Im Großen und Ganzen unterscheidet sich der Standard praktisch nicht von UCA, liest sich aber langweiliger, da er keine anschaulichen Beispiele nationaler Besonderheiten der Zeichenfolgensortierung enthält.

Die interessanteste Information war der Wiki Link zum Bugtracker mit der Diskussion über die Implementierung der Zeichenfolgenvergleiche in glibc.. Aus der Diskussion geht hervor, dass in glibc. zum Vergleich von Zeichenfolgen ISOeine Tabelle verwendet wird Die Common Template Table (CTT), deren Adresse im Anhang gefunden werden kann, A des Standards ISO 14651. Zwischen 2000 und 2015 hatte diese Tabelle keinen Maintainer und unterschied sich deutlich (zumindest optisch) von der aktuellen Version des Standards. Von 2015 bis 2018 wurde die Anpassung an die neue Version der Tabelle vorgenommen, und im Moment haben Sie die Chance, sowohl die neue Version der Tabelle ( glibc. ) als auch die alte (CentOS 8) im wirklichen Leben zu treffen. Nun, da wir alle Informationen über den Algorithmus und die Hilfstabellen haben, können wir zur ursprünglichen Problemstellung zurückkehren und verstehen, wie man Zeichenfolgen in der russischen Lokalisierung richtig sortiert.CentOS 7).

ISO 14651/14652

Der Quellcode der für uns interessanten Tabelle

befindet sich in den meisten Distributionen CTT im Verzeichnis Linux . Die Tabelle selbst befindet sich in der Datei /usr/share/i18n/locales/iso14651_t1_common . Dann wird diese Datei über die Direktivecopy iso14651_t1_common in die Datei iso14651_t1 , die wiederum in die nationalen Dateien, einschließlich in, eingebunden ist. In den meisten Distributionen en_US und ru_RU. In den meisten Distributionen Linux Alle Quelldateien sind Teil der Basisinstallation, aber falls sie fehlen, muss ein zusätzliches Paket aus der Distribution installiert werden.

Die Struktur der Datei , die wiederum in die nationalen Dateien, einschließlich in Es kann furchtbar wortreich erscheinen, mit nicht offensichtlichen Regeln zur Namensbildung, aber wenn man sich damit beschäftigt, ist alles ziemlich einfach. Die Struktur ist im Standard beschrieben ISO 14652, eine Kopie davon kann von der Website heruntergeladen werden open-std.org. Eine weitere Beschreibung des Dateiformats kann in JSR 168 und JSR 286 sowie Frameworks wie POSIX ab OpenGroupnachgelesen werden. Alternativ zur Lektüre des Standards kann man die Quelltexte der Funktion collate_read in glibc/locale/programs/ld-collate.c.

betrachten. Die Struktur der Datei sieht folgendermaßen aus:

Standardmäßig wird das Zeichen als Escape-Zeichen verwendet, und das Ende einer Zeile nach dem Zeichen # ist ein Kommentar. Beide Zeichen können überschrieben werden, was in der neuen Version der Tabelle auch geschehen ist:

escape_char /\ncomment_char %

Im Datei werden Tokens im Format <Uxxxx> oder <Uxxxxxxxx> (wo x — eine hexadezimale Ziffer). Dies ist die hexadezimale Darstellung von Unicode-Codepunkten in der Kodierung UCS-4 (UTF-32). Alle anderen Elemente in spitzen Klammern (einschließlich <Uxxxx_xxxx>, <2> und ähnliche), gelten als einfache Zeichenkonstanten, die ohne Kontext keine besondere Bedeutung haben.

Zeichenfolge LC_COLLATE sagt uns, dass die folgenden Daten die Zeichenvergleichsbeschreibung einleiten.

Zuerst werden die Gewichtsbezeichner in der Vergleichstabelle und die Namen für Zeichenkombinationen festgelegt. Grundsätzlich gehören die zwei Arten von Namen zu zwei verschiedenen Entitäten, aber in der tatsächlichen Datei sind sie vermischt. Die Gewichtsbezeichner werden durch das Schlüsselwort collating-symbol (Vergleichssymbol) angegeben, da Unicode-Zeichen mit denselben Gewichten beim Vergleichen als äquivalente Zeichen betrachtet werden.

Die Gesamtlänge des Abschnitts in der aktuellen Datei beträgt etwa 900 Zeilen. Ich habe Beispiele aus verschiedenen Stellen herausgesucht, um die Willkür der Namen und einige Arten von Syntax zu zeigen.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantierter größter Symbolwert. Am Ende dieser Liste aufbewahren
...
collating-element  von ""
collating-element  von ""

collating-symbol registriert die Zeichenfolge OSMANYA in der Gewichtsnamen-Tabelle
collating-symbol .. registriert eine Reihenfolge von Namen, bestehend aus einem Präfix O und einem hexadezimalen numerischen Suffix von 1D000 bis zu 1D35F.
FFFF in collating-symbol scheint wie eine große nicht-negative Ganzzahl im hexadezimalen Zahlensystem auszusehen, aber <SFFFF> ist einfach ein Name, der so aussehen könnte wie <VERYBIGVAL>
Name <U0413> bezeichnet einen Codepunkt in der Kodierung UCS-4
collating-element von "" registriert einen neuen Namen für ein Paar von Unicode-Punkten.

Wenn die Gewichtsnamen definiert sind, werden die eigentlichen Gewichte festgelegt. Da beim Vergleich nur das Verhältnis größer-kleiner von Bedeutung ist, werden die Gewichte durch eine einfache Reihenfolge der Aufzählung von Namen bestimmt. Zuerst werden die "leichteren" Gewichte aufgelistet, gefolgt von den "schwereren". Ich erinnere daran, dass jedem Unicode-Zeichen vier verschiedene Gewichte zugewiesen werden. Hier sind sie in einer einheitlichen, geordneten Reihenfolge zusammengefasst. Theoretisch kann jeder symbolische Name auf einem der vier Ebenen verwendet werden, aber die Kommentare deuten darauf hin, dass die Entwickler die Namen gedanklich nach Ebenen unterteilen.

% Symbolische Gewichtzuweisungen

% Gewichtzuweisungen dritter Ebene




...
% Gewichtzuweisungen zweiter Ebene

 % KOMBINIERE NIEDERLINE
 % KOMBINIERE KOMMA OBEN
 % KOMBINIERE UMGEKEHRTES KOMMA OBEN
...
% Gewichtzuweisungen erster Ebene
 % HORIZONTALE TABULIERUNG
 % ZEILENUMBRUCH
 % VERTIKALE TABULIERUNG
...
 % KIRILLLISCHES KLEINBUCHSTABE DE
 % KIRILLLISCHES KLEINBUCHSTABE KOMI DE
 % KIRILLLISCHES KLEINBUCHSTABE DJE
 % KIRILLLISCHES KLEINBUCHSTABE KOMI DJE
 % KIRILLLISCHES KLEINBUCHSTABE GJE
 % KIRILLLISCHES KLEINBUCHSTABE ZE MIT ABSTEIGEN
 % KIRILLLISCHES KLEINBUCHSTABE IE
 % KIRILLLISCHES KLEINBUCHSTABE IE MIT BREVE
 % KIRILLLISCHES KLEINBUCHSTABE UKRAINISCHES IE
 % KIRILLLISCHES KLEINBUCHSTABE ZHE

Schließlich die eigentliche Gewichtstabelle.

Der Abschnitt der Gewichte ist in Zeilen mit Schlüsselwörtern eingeschlossen order_start und order_end. Zusätzliche Parameter order_start bestimmen, in welcher Richtung die Zeilen auf jeder Vergleichsebene durchsucht werden. Standardmäßig wird der Parameter verwendet forward. Der Abschnitt besteht aus Zeilen, die den Zeichencode und vier seiner Gewichtungen enthalten. Der Zeichencode kann durch das Zeichen selbst, den Codepunkt oder einen vorher definierten symbolischen Namen dargestellt werden. Die Gewichtungen können ebenfalls durch symbolische Namen, Codepunkte oder die Zeichen selbst angegeben werden. Wenn Codepunkte oder Zeichen verwendet werden, entspricht ihr Gewicht dem numerischen Wert des Codepunkts (der Position in der Unicode-Tabelle). Nicht explizit angegebene Zeichen (so verstehe ich) werden als primär betrachtet, mit einem Gewicht, das der Position in der Unicode-Tabelle entspricht. Besondere Gewichtungswerte IGNORE bedeutet, dass dieses Zeichen auf der entsprechenden Vergleichsebene ignoriert wird.

Um die Struktur der Gewichtungen zu demonstrieren, habe ich drei ziemlich offensichtliche Fragmente ausgewählt:

Zeichen, die vollständig ignoriert werden
Zeichen, die auf den ersten beiden Ebenen dem Wert drei entsprechen
der Beginn des kyrillischen Alphabets, das keine diakritischen Zeichen enthält und daher hauptsächlich nach der ersten und dritten Ebene sortiert wird.

Bestellung_Start vor;vor;vor;vor,Position
 IGNORIEREN;IGNORIEREN;IGNORIEREN;IGNORIEREN % NULL (in 6429)
 IGNORIEREN;IGNORIEREN;IGNORIEREN;IGNORIEREN % ANFANG DES ÜBERSCHRIFTS (in 6429)
 IGNORIEREN;IGNORIEREN;IGNORIEREN;IGNORIEREN % TEXTBEGINN (in 6429)
...
 ;;; % ZIFFER DREI
 ;;; % VOLLE ZIFFER DREI
 ;;; % IN KLAMMERN GESCHRIEBENE ZIFFER DREI
 ;;; % ZIFFER DREI VOLLSTRECKE
 ;;; % MATHEMATISCH FETTE ZIFFER DREI
...
 ;;; % CYRILLIC KLEINBUCHSTABE A
 ;;; % CYRILLIC GROSSBUCHSTABE A
 ;;; % CYRILLIC KLEINBUCHSTABE A MIT BREVE
 ;;; % CYRILLIC KLEINBUCHSTABE A MIT BREVE
...
 ;;; % CYRILLIC KLEINBUCHSTABE BE
 ;;; % CYRILLIC GROSSBUCHSTABE BE
 ;;; % CYRILLIC KLEINBUCHSTABE VE
 ;;; % CYRILLIC GROSSBUCHSTABE VE
...
Bestellung_Ende

Jetzt können wir zu den Beispielen aus dem Anfang des Artikels zurückkehren. Die Falle versteckt sich in diesem Teil der Gewichtungstabelle:

IGNORIEREN;IGNORIEREN;IGNORIEREN; % LEERZEICHEN
 IGNORIEREN;IGNORIEREN;IGNORIEREN; % AUSRUFEZEICHEN
 IGNORIEREN;IGNORIEREN;IGNORIEREN; % ANFÜHRUNGSZEICHEN
...

Es ist offensichtlich, dass in dieser Tabelle die Satzzeichen ignoriert werden. ASCII (einschließlich Leerzeichen) werden beim Vergleich von Zeichenfolgen fast immer ignoriert. Die Ausnahme bilden nur Zeichenfolgen, die in allem übereinstimmen, außer bei den Satzzeichen, die an übereinstimmenden Stellen vorkommen. Die Zeichenfolgen aus meinem Beispiel (nach der Sortierung) sehen für den Vergleichsalgorithmus so aus:

AbakanovMichailMaler
JolkinaEllaKranführerin
IvanovaAllaMaler
IvanovAndreiSchlosser

Angesichts der Tatsache, dass in der Gewichtungstabelle die Großbuchstaben im Russischen nach den Kleinbuchstaben kommen (auf der dritten Ebene <CAP> schwerer als <MIN>), sieht die Sortierung absolut korrekt aus.

Bei der Einstellung der Variablen LC_COLLATE=C wird eine spezielle Tabelle geladen, die einen byteweisen Vergleich definiert.

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'fe', L'xff'
};

Da im Unicode der Codepunkt Ё vor А steht, werden die Zeichenfolgen entsprechend sortiert.

Text- und Binärtables

Es ist offensichtlich, dass der Vergleich von Zeichenfolgen eine äußerst häufige Operation ist, während das Parsen einer Tabelle CTT eine ziemlich kostenintensive Prozedur darstellt. Um den Zugriff auf die Tabelle zu optimieren, wird sie in eine binäre Form vom Befehl localedef.

Der Befehl localedef kompiliert, der als Parameter eine Datei mit der Tabelle nationaler Besonderheiten (Option -i), in der alle Zeichen durch Unicode-Punkte dargestellt sind, und eine Datei zur Zuordnung von Unicode-Punkten zu den spezifischen Codierungen (Option -f). Dadurch werden binäre Dateien für die Locale mit dem im letzten Parameter angegebenen Namen erstellt.

Glibc Es werden zwei Formate von Binärdateien unterstützt: "traditional" und "modern".

Das traditionelle Format bedeutet, dass der Name der Locale der Name eines Unterverzeichnisses in /usr/lib/locale/. In diesem Unterverzeichnis werden die Binärdateien LC_COLLATE, LC_CTYPE, LC_TIME usw. Die Datei LC_IDENTIFICATION enthält den formalen Namen der Locale (der sich vom Namen des Verzeichnisses unterscheiden kann) und Kommentare.

Das moderne Format geht davon aus, dass alle Locales in einem einzigen Archiv gespeichert werden /usr/lib/locale/locale-archive, das im virtuellen Speicher aller Prozesse angezeigt wird, die es verwenden. glibc.. Der Name der Locale im modernen Format unterliegt einer gewissen Kanonisierung – in den Kodierungsnamen bleiben nur Zahlen und Buchstaben, die in Kleinbuchstaben umgewandelt werden. So ru_RU.KOI8-R, wird als ru_RU.koi8r.

Eingabedateien werden im aktuellen Verzeichnis sowie in den Verzeichnissen /usr/share/i18n/locales/ und /usr/share/i18n/charmaps/ für Dateien CTT und Kodierungsdateien entsprechend gesucht.

Zum Beispiel wird der Befehl

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

die Datei /usr/share/i18n/locales/ru_RU unter Verwendung der Kodierungsdatei /usr/share/i18n/charmaps/MAC-CYRILLIC.gz kompilieren und das Ergebnis in /usr/lib/locale/locale-archive unter dem Namen ru_RU.maccyrillic

Wenn die Variable LANG=en_US.UTF-8 gesetzt wird, glibc. wird nach Binärdateien der Locale in der folgenden Reihenfolge von Dateien und Verzeichnissen gesucht:

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

Wenn die Locale sowohl im traditionellen als auch im modernen Format vorkommt, erhält das moderne Format Priorität.

Die Liste der kompilierten Locales kann mit dem Befehl locale -a.

vorbereitet werden.

Nun, gewappnet mit Wissen, können Sie Ihre eigene ideale Vergleichstabelle von Zeichen erstellen. Diese Tabelle sollte russische Buchstaben korrekt vergleichen, einschließlich des Buchstabens Ё, und dabei die Satzzeichen gemäß der Tabelle berücksichtigen. ASCII.

Der Prozess zur Vorbereitung Ihrer Sortiertabelle besteht aus zwei Phasen: der Bearbeitung der Gewichtstabelle und der Kompilierung in binäre Form mittels eines Befehls. localedef.

Um die Vergleichstabelle mit minimalem Bearbeitungsaufwand anzupassen, im Format ISO 14652 sind Korrekturabschnitte für bereits bestehende Tabellen vorgesehen. Ein Abschnitt beginnt mit dem Schlüsselwort reorder-after und der Angabe der Position, nach der die Ersetzung erfolgt. Ein Abschnitt endet mit der Zeile reorder-end. Wenn es notwendig ist, mehrere Bereiche der Tabelle zu korrigieren, wird für jeden solchen Bereich ein eigener Abschnitt erstellt.

Ich habe die neuen Versionen der Dateien . Dann wird diese Datei über die Direktive und ru_RU aus dem Repository glibc. in mein Home-Verzeichnis ~/.local/share/i18n/locales/ kopiert und den Abschnitt LC_COLLATE in ru_RUleicht bearbeitet. Die neuen Versionen der Dateien sind vollständig kompatibel mit meiner Version glibc.. Wenn Sie die alten Versionen der Dateien verwenden möchten, müssen Sie die symbolischen Namen und den Beginn der Ersetzung in der Tabelle ändern.

LC_COLLATE
% Kopieren Sie die Vorlage von ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ; % SPACE
 ; % AUSRUFEZEICHEN
 ; % ANFÜHRUNGSZEICHEN
...
 ; % RECHTE CURLY-KLAMMER
 ; % TILDE
reorder-end
END LC_COLLATE

Tatsächlich hätte ich die Felder ändern müssen LC_IDENTIFICATION so dass sie auf die Locale zeigen ru_MY, aber in meinem Beispiel war das nicht erforderlich, da ich das Archiv der Locales ausgeschlossen habe locale-archive.

Um localedef arbeitete mit den Dateien in meinem Ordner über die Variable I18NPATH es ist möglich, ein zusätzliches Verzeichnis für die Suche nach Eingabedateien hinzuzufügen, und das Verzeichnis zum Speichern von Binärdateien kann als Pfad mit Schrägstrichen angegeben werden:

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

POSIX es wird davon ausgegangen, dass in LANG absolute Pfade zu den Verzeichnissen mit den Locale-Dateien angegeben werden können, die mit einem normalen Schrägstrich beginnen, aber glibc. in Linux alle Pfade von dem Basisverzeichnis ausgehen, das über die Variable LOCPATHüberschrieben werden kann. Nach der Einstellung LOCPATH=~/.local/lib/locale/ werden alle mit der Lokalisierung verbundenen Dateien nur in meinem Ordner gesucht. Das Archiv der Locales wird bei gesetzter Variablen LOCPATH wird ignoriert.

Hier ist der entscheidende Test:

$> LANG=de_DE.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanow Michail;Maler
Jolkina Ella;Kranführerin
Ivanow Andrej;Schlosser
Ivanova Alla;Rechtsanwältin

Hurra! Wir haben es geschafft!

Arbeiten an Fehlern

Ich habe bereits die Fragen zur Sortierung von Strings beantwortet, die zu Beginn gestellt wurden, aber es sind noch ein paar Fragen zu den Fehlern übrig geblieben – sowohl sichtbare als auch unsichtbare.

Zurück zur ursprünglichen Aufgabe.

Und das Programm sortieren und das Programm beitreten verwenden dieselben Stringvergleichsfunktionen aus glibc.. Wie konnte es also dazu kommen, dass beitreten einen Sortierfehler bei den von der Kommandozeile sortierten Strings ausgegeben hat? sortieren in der Locale de_DE.UTF-8? Ответ прост: sortieren vergleicht die gesamte Zeichenkette, während beitreten nur den Schlüssel vergleicht, der standardmäßig der Anfang der Zeichenkette bis zum ersten Leerzeichen ist. In meinem Beispiel führte dies zu einer Fehlermeldung, da die Sortierung der ersten Wörter in den Strings nicht mit der Sortierung der gesamten Strings übereinstimmte.

Locale "C" garantiert, dass die sortierten Zeilen auch die Anfangsunterstrings bis zum ersten Leerzeichen sortiert haben, aber das ist nur ein Maskierungstrick für einen Fehler. Man kann solche Daten auswählen (Menschen mit denselben Nachnamen, aber unterschiedlichen Vornamen), die ohne Fehlermeldung zu einem falschen Ergebnis bei der Zusammenführung von Dateien führen würden. Wenn wir möchten, dass beitreten die Zeilen von Dateien nach Vollständigen Namen (FIO) zusammengeführt werden, ist die richtige Vorgehensweise die explizite Angabe des Feldtrennzeichens und die Sortierung nach dem Schlüssel, nicht nach der gesamten Zeile. In diesem Fall wird auch die Zusammenführung korrekt durchgeführt, und es gibt in keiner Locale Fehler:

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

Ein erfolgreich durchgeführtes Beispiel in der Kodierung CP1251 enthält einen weiteren Fehler. Das Problem ist, dass in allen mir bekannten Distributionen Linux in den Paketen die kompilierte Locale ru_RU.CP1251fehlt. Wenn die kompilierte Locale nicht gefunden wird, sortieren verwendet sie stillschweigend den byteweisen Vergleich, was wir auch beobachtet haben.

Übrigens gibt es noch einen kleinen Fehler im Zusammenhang mit der Nichtverfügbarkeit der kompilierten Locales. Der Befehl LOCPATH=/tmp locale -a gibt eine Liste aller Locales in locale-archive, aber mit einer gesetzten Variablen LOCPATH für alle Programme (auch für das selbst locale) werden diese Locales nicht verfügbar sein.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Kann LC_CTYPE nicht auf die Standard-Locale setzen: Datei oder Verzeichnis nicht gefunden
locale: Kann LC_MESSAGES nicht auf die Standard-Locale setzen: Datei oder Verzeichnis nicht gefunden
locale: Kann LC_COLLATE nicht auf die Standard-Locale setzen: Datei oder Verzeichnis nicht gefunden
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: verwendet die Sortierregeln von 'en_US.UTF-8'

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: verwendet einfachen Bytevergleich

Fazit

Wenn Sie ein Programmierer sind, der gewohnt ist, dass Zeichenfolgen eine Ansammlung von Bytes sind, dann ist Ihre Wahl LC_COLLATE=C.

Wenn Sie Linguist oder Wörterbuchverfasser sind, sollten Sie Ihre Locale besser selbst kompilieren.

Wenn Sie ein einfacher Benutzer sind, sollten Sie sich damit abfinden, dass der Befehl ls -a Dateien ausgibt, die mit einem Punkt beginnen, zusammen mit Dateien, die mit einem Buchstaben beginnen, und Midnight Commander, der seine eigenen internen Funktionen zur Sortierung von Namen verwendet, die Dateien, die mit einem Punkt beginnen, an den Anfang der Liste stellt.