Einführung

Alles begann mit einem kurzen Skript, das Adressinformationen zusammenführen sollte Email Mitarbeiter aus der Liste der Mailinglistenbenutzer, Mitarbeiterpositionen aus der Datenbank der Personalabteilung. Beide Listen wurden in Unicode-Textdateien exportiert UTF-8 und mit Unix-Zeilenenden gespeichert.

Inhalt mail.txt

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

Inhalt buhg.txt

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

Zum Zusammenführen wurden die Dateien mit dem Unix-Befehl sortiert sortieren und an den Eingang des Unix-Programms übergeben join, was unerwartet mit einem Fehler fehlschlug:

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

Die Betrachtung des Sortierergebnisses mit eigenen Augen zeigte, dass die Sortierung im Allgemeinen korrekt ist, bei Übereinstimmungen männlicher und weiblicher Nachnamen jedoch die weiblichen vor den männlichen stehen:

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

Sieht aus wie ein Sortierfehler in Unicode oder wie eine Manifestation des Feminismus im Sortieralgorithmus. Das erste ist natürlich plausibler.

Lassen wir es erst einmal aufschieben join und sich darauf konzentrieren sortieren. Versuchen wir, das Problem durch wissenschaftliches Stochern zu lösen. Ändern wir zunächst das Gebietsschema von en_US auf ru_RU. Zum Sortieren würde es ausreichen, die Umgebungsvariable zu setzen LC_COLLATE, aber wir verschwenden keine Zeit mit Kleinigkeiten:

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

Nichts hat sich geändert.

Versuchen wir, die Dateien in eine Einzelbyte-Kodierung umzukodieren:

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

Auch hier hat sich nichts geändert.

Da kann man nichts machen, man muss im Internet nach einer Lösung suchen. Es gibt nichts direktes über russische Nachnamen, aber es gibt Fragen zu anderen Kuriositäten bei der Sortierung. Hier liegt zum Beispiel ein Problem vor: Unix-Sortierung behandelt „-“ (Bindestrich)-Zeichen als unsichtbar. Kurz gesagt, die Zeichenfolgen „ab“, „aa“, „ac“ werden als „aa“, „ab“, „ac“ sortiert.

Die Antwort ist überall Standard: Verwenden Sie das Programmiergebietsschema "C" und du wirst glücklich sein. Lass es uns versuchen:

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

Etwas hat sich verändert. Die Ivanovs stellten sich in der richtigen Reihenfolge auf, obwohl Yolkina irgendwo ausrutschte. Kehren wir zum ursprünglichen Problem 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 funktionierte fehlerfrei, wie das Internet versprochen hatte. Und das trotz Yolkina in der ersten Reihe.

Das Problem scheint gelöst zu sein, aber für alle Fälle versuchen wir es mit einer anderen russischen Kodierung – Windows CP1251:

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

Seltsamerweise stimmt das Sortierergebnis mit dem Gebietsschema überein "C", und das gesamte Beispiel läuft dementsprechend fehlerfrei. Eine Art Mystik.

Ich mag Mystik beim Programmieren nicht, weil sie normalerweise Fehler maskiert. Wir müssen ernsthaft prüfen, wie es funktioniert. sortieren und welche Auswirkungen hat es? LC_COLLATE .

Am Ende werde ich versuchen, die Fragen zu beantworten:

Warum wurden weibliche Nachnamen falsch sortiert?
warum LANG=ru_RU.CP1251 stellte sich als gleichwertig heraus SPRACHE=C
warum machen sortieren и join unterschiedliche Vorstellungen über die Reihenfolge sortierter Zeichenfolgen
Warum sind in all meinen Beispielen Fehler enthalten?
Endlich erfahren Sie, wie Sie die Zeichenfolgen nach Ihren Wünschen sortieren können

Sortieren in Unicode

Die erste Station wird der technische Bericht Nr. 10 mit dem Titel sein Unicode-Sortierungsalgorithmus Online unicode.org. Der Bericht enthält viele technische Details, daher möchte ich die wichtigsten Ideen kurz zusammenfassen.

Vergleich — Das „Vergleichen“ von Zeichenfolgen ist die Grundlage jedes Sortieralgorithmus. Die Algorithmen selbst können unterschiedlich sein („Bubble“, „Merge“, „Fast“), aber alle verwenden einen Vergleich eines Zeichenfolgenpaars, um die Reihenfolge zu bestimmen, in der sie erscheinen.

Das Sortieren von Zeichenfolgen in natürlicher Sprache ist ein ziemlich komplexes Problem. Selbst bei den einfachsten Einzelbyte-Kodierungen stimmt die Reihenfolge der Buchstaben im Alphabet, auch wenn sie sich in irgendeiner Weise vom englischen Latein-Alphabet unterscheidet, nicht mehr mit der Reihenfolge der numerischen Werte überein, mit denen diese Buchstaben kodiert sind. Also im deutschen Alphabet der Buchstabe Ö steht dazwischen О и P, und in der Kodierung CP850 sie kommt dazwischen ÿ и Ü.

Sie können versuchen, von einer bestimmten Kodierung zu abstrahieren und „ideale“ Buchstaben in Betracht zu ziehen, die in einer bestimmten Reihenfolge angeordnet sind, wie dies bei Unicode der Fall ist. Kodierungen Utfxnumx, Utfxnumx oder ein Byte KOI8-R (wenn eine begrenzte Teilmenge von Unicode benötigt wird) ergibt unterschiedliche numerische Darstellungen von Buchstaben, verweist jedoch auf dieselben Elemente der Basistabelle.

Es stellt sich heraus, dass wir selbst dann, wenn wir eine Symboltabelle von Grund auf erstellen, ihr keine universelle Symbolreihenfolge zuweisen können. In verschiedenen nationalen Alphabeten, die dieselben Buchstaben verwenden, kann die Reihenfolge dieser Buchstaben unterschiedlich sein. Zum Beispiel auf Französisch Æ wird als Ligatur betrachtet und als Zeichenfolge sortiert AE. Auf Norwegisch Æ wird ein separater Buchstabe sein, der sich danach befindet Z. Übrigens, zusätzlich zu Ligaturen wie Æ Es gibt Buchstaben, die mit mehreren Symbolen geschrieben sind. Im tschechischen Alphabet gibt es also einen Buchstaben Ch, was dazwischen steht H и I.

Neben den unterschiedlichen Alphabeten gibt es auch andere nationale Traditionen, die die Sortierung beeinflussen. Insbesondere stellt sich die Frage: In welcher Reihenfolge sollen Wörter, die aus Groß- und Kleinbuchstaben bestehen, im Wörterbuch erscheinen? Die Sortierung kann auch durch die Verwendung von Satzzeichen beeinträchtigt werden. Im Spanischen wird am Anfang eines Fragesatzes ein umgekehrtes Fragezeichen verwendet (Magst du Musik?). In diesem Fall ist es offensichtlich, dass Fragesätze nicht in einem separaten Cluster außerhalb des Alphabets gruppiert werden sollten, aber wie sortiert man Zeilen mit anderen Satzzeichen?

Ich werde mich nicht mit der Sortierung von Zeichenfolgen in Sprachen befassen, die sich stark von den europäischen unterscheiden. Beachten Sie, dass in Sprachen mit einer Schreibrichtung von rechts nach links oder von oben nach unten die Zeichen in Zeilen höchstwahrscheinlich in Lesereihenfolge gespeichert werden und selbst nicht-alphabetische Schriftsysteme ihre eigenen Methoden haben, Zeilen Zeichen für Zeichen anzuordnen . Hieroglyphen können beispielsweise nach Stil sortiert werden (Chinesische Schriftzeichenschlüssel) oder durch Aussprache. Ehrlich gesagt habe ich keine Ahnung, wie Emojis angeordnet werden sollen, aber man kann sich auch etwas dafür einfallen lassen.

Basierend auf den oben aufgeführten Merkmalen wurden die grundlegenden Anforderungen für den Vergleich von Zeichenfolgen basierend auf Unicode-Tabellen formuliert:

Der String-Vergleich hängt nicht von der Position der Zeichen in der Codetabelle ab;
Zeichenfolgen, die ein einzelnes Zeichen bilden, werden auf die kanonische Form reduziert (A + Der obere Kreis ist derselbe wie Å);
Beim Vergleich von Zeichenfolgen wird ein Zeichen im Kontext der Zeichenfolge betrachtet und ggf. mit seinen Nachbarn zu einer Vergleichseinheit zusammengefasst (Ch auf Tschechisch) oder ist in mehrere unterteilt (Æ auf Französisch);
alle nationalen Merkmale (Alphabet, Groß-/Kleinschreibung, Interpunktion, Reihenfolge der Schreibarten) müssen bis hin zur manuellen Zuordnung der Reihenfolge (Emoji) konfiguriert werden;
Der Vergleich ist nicht nur zum Sortieren wichtig, sondern auch an vielen anderen Stellen, beispielsweise zum Angeben von Zeilenbereichen (Ersetzen von {A... z} in bash);
Der Vergleich sollte relativ schnell erfolgen.

Darüber hinaus formulierten die Autoren des Berichts Vergleichseigenschaften, auf die sich Algorithmenentwickler nicht verlassen sollten:

Der Vergleichsalgorithmus sollte keinen separaten Zeichensatz für jede Sprache erfordern (russische und ukrainische Sprachen haben die meisten kyrillischen Zeichen gemeinsam);
Der Vergleich sollte nicht auf der Reihenfolge der Zeichen in Unicode-Tabellen basieren.
Das String-Gewicht sollte kein Attribut des Strings sein, da derselbe String in verschiedenen kulturellen Kontexten unterschiedliche Gewichte haben kann.
Zeilengewichtungen können sich beim Zusammenführen oder Teilen ändern (von x < y daraus folgt nicht xz < yz);
Aus Sicht des Sortieralgorithmus werden verschiedene Zeichenfolgen mit den gleichen Gewichten als gleich betrachtet. Die Einführung einer zusätzlichen Reihenfolge solcher Zeichenfolgen ist möglich, kann jedoch die Leistung beeinträchtigen.
Bei wiederholter Sortierung können Zeilen mit gleichen Gewichtungen vertauscht werden. Robustheit ist eine Eigenschaft eines bestimmten Sortieralgorithmus und keine Eigenschaft eines String-Vergleichsalgorithmus (siehe vorherigen Absatz);
Sortierregeln können sich im Laufe der Zeit ändern, wenn kulturelle Traditionen verfeinert/verändert werden.

Außerdem wird festgelegt, dass der Vergleichsalgorithmus nichts über die Semantik der verarbeiteten Zeichenfolgen weiß. Daher sollten Zeichenfolgen, die nur aus Ziffern bestehen, nicht als Zahlen verglichen werden, und in Listen englischer Namen lautet der Artikel (Beatles, Die).

Um alle spezifizierten Anforderungen zu erfüllen, wird ein mehrstufiger (eigentlich vierstufiger) Tabellensortierungsalgorithmus vorgeschlagen.

Zuvor wurden die Zeichen in der Zeichenfolge auf die kanonische Form reduziert und in Vergleichseinheiten gruppiert. Jeder Vergleichseinheit werden mehrere Gewichte zugewiesen, die mehreren Vergleichsebenen entsprechen. Die Gewichte von Vergleichseinheiten sind Elemente geordneter Mengen (in diesem Fall ganze Zahlen), die mehr oder weniger verglichen werden können. Spezielle Bedeutung IGNORIERT (0x0) bedeutet, dass diese Einheit auf der entsprechenden Vergleichsebene nicht am Vergleich beteiligt ist. Der Vergleich von Zeichenfolgen kann mehrmals wiederholt werden, wobei die Gewichte der entsprechenden Ebenen verwendet werden. Auf jeder Ebene werden die Gewichte der Vergleichseinheiten zweier Zeilen sequentiell miteinander verglichen.

In verschiedenen Implementierungen des Algorithmus für unterschiedliche nationale Traditionen können die Werte der Koeffizienten unterschiedlich sein, aber der Unicode-Standard enthält eine grundlegende Gewichtstabelle – „Standard-Unicode-Sortierungselementtabelle“ (DUCET). Ich möchte das Festlegen der Variablen beachten LC_COLLATE ist eigentlich ein Hinweis auf die Auswahl der Gewichtstabelle in der String-Vergleichsfunktion.

Gewichtungskoeffizienten DUCET wie folgt angeordnet:

auf der ersten Ebene werden alle Buchstaben auf die gleiche Groß-/Kleinschreibung reduziert, diakritische Zeichen werden verworfen, Satzzeichen (nicht alle) werden ignoriert;
auf der zweiten Ebene werden nur diakritische Zeichen berücksichtigt;
auf der dritten Ebene wird nur die Groß-/Kleinschreibung berücksichtigt;
Auf der vierten Ebene werden nur Satzzeichen berücksichtigt.

Der Vergleich erfolgt in mehreren Durchgängen: Zunächst werden die Koeffizienten der ersten Ebene verglichen; Wenn die Gewichte übereinstimmen, wird ein wiederholter Vergleich mit den Gewichten der zweiten Ebene durchgeführt. dann vielleicht ein Drittel und ein Viertel.

Der Vergleich endet, wenn die Zeilen übereinstimmende Vergleichseinheiten mit unterschiedlichen Gewichtungen enthalten. Zeilen, die auf allen vier Ebenen die gleiche Gewichtung haben, gelten untereinander als gleich.

Dieser Algorithmus (mit einer Reihe zusätzlicher technischer Details) gab dem Bericht Nr. 10 den Namen - „Unicode-Sortierungsalgorithmus“ (Klimaanlage).

Hier wird das Sortierverhalten aus unserem Beispiel etwas deutlicher. Es wäre schön, es mit dem Unicode-Standard zu vergleichen.

Um Implementierungen zu testen Klimaanlage es gibt ein besonderes тест, verwenden Gewichtsdatei, umsetzen DUCET. In der Waage-Datei finden Sie allerlei lustige Dinge. Es gibt zum Beispiel die Reihenfolge von Mahjong und europäischen Dominosteinen, sowie die Reihenfolge der Farben in einem Kartenspiel (Symbol 1F000 und weiter). Die Kartenfarben werden gemäß den Bridge-Regeln (PCBT) platziert, und die Karten in der Farbe befinden sich in der Reihenfolge T, 2,3, XNUMX ... K.

Manuelles Überprüfen, ob die Zeilen korrekt sortiert sind DUCET wäre ziemlich mühsam, aber zum Glück gibt es für uns eine beispielhafte Implementierung der Bibliothek für die Arbeit mit Unicode - "Internationale Komponenten für Unicode"(ICU).

Auf der Website dieser Bibliothek, entwickelt in IBM, es gibt Demoseiten, darunter Seite zum String-Vergleichsalgorithmus. Wir geben unsere Testzeilen mit Standardeinstellungen ein und siehe da, wir erhalten eine perfekte russische Sortierung.

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

Übrigens die Webseite ICU Eine Erläuterung des Vergleichsalgorithmus bei der Verarbeitung von Satzzeichen finden Sie hier. In den Beispielen Häufig gestellte Fragen zur Sortierung Apostroph und Bindestrich werden ignoriert.

Unicode hat uns geholfen, aber suchen Sie nach Gründen für seltsames Verhalten sortieren в Linux werde woanders hingehen müssen.

Sortieren in glibc

Schneller Überblick über die Quellcodes des Dienstprogramms sortieren von GNU Core Utils zeigte, dass die Lokalisierung im Dienstprogramm selbst darauf hinausläuft, den aktuellen Wert der Variablen auszugeben LC_COLLATE beim Ausführen im Debug-Modus:

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

String-Vergleiche werden mit der Standardfunktion durchgeführt strcoll, was bedeutet, dass alles Interessante in der Bibliothek ist glibc.

Auf Wiki Projekt glibc gewidmet dem String-Vergleich ein Absatz. Aus diesem Absatz kann man verstehen, dass in glibc Die Sortierung basiert auf einem uns bereits bekannten Algorithmus Klimaanlage (Der Unicode-Sortierungsalgorithmus) und/oder bei einem Standard nahe daran ISO 14651 (Internationale Reihenfolge und Vergleich von Saiten). Bezüglich des neuesten Standards ist auf der Website zu vermerken Standards.iso.org ISO 14651 offiziell für öffentlich zugänglich erklärt, der entsprechende Link führt jedoch zu einer nicht existierenden Seite. Google gibt mehrere Seiten mit Links zu offiziellen Websites zurück, die den Kauf einer elektronischen Kopie des Standards für hundert Euro anbieten, aber auf der dritten oder vierten Seite der Suchergebnisse finden sich auch direkte Links dazu PDF. Im Allgemeinen unterscheidet sich der Standard praktisch nicht von Klimaanlage, ist aber langweiliger zu lesen, da es keine klaren Beispiele für nationale Merkmale der String-Sortierung enthält.

Die interessantesten Informationen zu Wiki Es gab einen Link dazu Bug-Tracker mit einer Diskussion der Implementierung des String-Vergleichs in glibc. Aus der Diskussion lässt sich das lernen glibc Wird zum Vergleichen von Zeichenfolgen verwendet ISOpersönlicher Tisch Die gemeinsame Vorlagentabelle (CTT), deren Adresse Sie im Antrag finden A Standard ISO 14651 . Zwischen 2000 und 2015 diese Tabelle in glibc hatte keinen Betreuer und unterschied sich (zumindest äußerlich) deutlich von der aktuellen Version des Standards. Von 2015 bis 2018 fand eine Anpassung an die neue Version der Tabelle statt, und jetzt haben Sie die Möglichkeit, eine neue Version der Tabelle im wirklichen Leben kennenzulernen (8 CentOS), und Alt (7 CentOS).

Nachdem wir nun alle Informationen über den Algorithmus und die Hilfstabellen haben, können wir zum ursprünglichen Problem zurückkehren und verstehen, wie Zeichenfolgen im russischen Gebietsschema richtig sortiert werden.

ISO 14651 / 14652

Quellcode der Tabelle, die uns interessiert CTT auf den meisten Distributionen Linux steht im Verzeichnis /usr/share/i18n/locales/. Die Tabelle selbst befindet sich in der Datei iso14651_t1_common. Dann ist dies die Dateianweisung Kopieren Sie iso14651_t1_common in der Datei enthalten iso14651_t1, die wiederum in nationalen Dateien enthalten ist, einschließlich en_US и ru_RU. Auf den meisten Distributionen Linux Alle Quelldateien sind in der Basisinstallation enthalten. Wenn sie jedoch nicht vorhanden sind, müssen Sie ein zusätzliches Paket aus der Distribution installieren.

Dateistruktur iso14651_t1 mag furchtbar ausführlich erscheinen, mit nicht offensichtlichen Regeln für die Bildung von Namen, aber wenn man es genau betrachtet, ist alles ganz einfach. Der Aufbau ist im Standard beschrieben ISO 14652 , eine Kopie davon kann von der Website heruntergeladen werden open-std.org. Eine weitere Beschreibung des Dateiformats kann eingelesen werden Spezifikationen POSIX aus Offene Gruppe. Alternativ zum Lesen des Standards können Sie den Quellcode der Funktion studieren collate_read в glibc/locale/programs/ld-collate.c.

Die Dateistruktur sieht so aus:

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

escape_char /
comment_char %

Die Datei enthält Token im Format oder (wo x - hexadezimale Ziffer). Dies ist die hexadezimale Darstellung der Unicode-Codepunkte in der Codierung UCS-4 (UTF-32). Alle anderen Elemente in spitzen Klammern (einschließlich , und dergleichen) gelten als einfache String-Konstanten, die außerhalb des Kontexts wenig Bedeutung haben.

String LC_COLLATE sagt uns, dass als nächstes die Daten beginnen, die den Vergleich von Zeichenfolgen beschreiben.

Zunächst werden Namen für die Gewichte in der Vergleichstabelle und Namen für die Symbolkombinationen angegeben. Im Allgemeinen gehören die beiden Namenstypen zu zwei verschiedenen Entitäten, in der eigentlichen Datei sind sie jedoch gemischt. Die Namen der Gewichte werden durch das Schlüsselwort angegeben Sortiersymbol (Vergleichszeichen), da beim Vergleich Unicode-Zeichen mit der gleichen Gewichtung als äquivalente Zeichen betrachtet werden.

Die Gesamtlänge des Abschnitts in der aktuellen Dateirevision beträgt etwa 900 Zeilen. Ich habe Beispiele von mehreren Stellen entnommen, um die Willkür von Namen und verschiedene Arten der Syntax zu zeigen.

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

Sortiersymbol protokolliert eine Zeichenfolge OSMANYA in der Tabelle der Skalennamen
Sortiersymbol .. registriert eine Folge von Namen, die aus einem Präfix besteht S und hexadezimales numerisches Suffix von 1D000 auf 1D35F.
FFFF в Sortiersymbol sieht aus wie eine große vorzeichenlose Ganzzahl im Hexadezimalformat, aber Es ist nur ein Name, der so aussehen könnte
Name bedeutet Codepunkt bei der Codierung UCS-4
Sortierelement aus " " Registriert einen neuen Namen für ein Paar Unicode-Punkte.

Sobald die Namen der Gewichte definiert sind, werden die tatsächlichen Gewichte angegeben. Da im Vergleich nur Größer-als-Kleiner-Beziehungen von Bedeutung sind, werden die Gewichte durch eine einfache Folge von Auflistungsnamen bestimmt. Zuerst werden die „leichteren“ Gewichte aufgeführt, dann die „schwereren“. Ich möchte Sie daran erinnern, dass jedem Unicode-Zeichen vier verschiedene Gewichtungen zugewiesen sind. Hier werden sie zu einer einzigen geordneten Sequenz zusammengefasst. Theoretisch könnte jeder symbolische Name auf jeder der vier Ebenen verwendet werden, aber Kommentare deuten darauf hin, dass die Entwickler Namen gedanklich in Ebenen unterteilen.

% 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

Zum Schluss noch die eigentliche Gewichtstabelle.

Der Abschnitt mit den Gewichtungen ist in Schlüsselwortzeilen eingeschlossen order_start и order_end. Zusätzliche Optionen order_start Bestimmen Sie, in welche Richtung Zeilen auf jeder Vergleichsebene gescannt werden. Die Standardeinstellung ist . Der Hauptteil des Abschnitts besteht aus Zeilen, die den Symbolcode und seine vier Gewichtungen enthalten. Der Zeichencode kann durch das Zeichen selbst, einen Codepunkt oder einen zuvor definierten symbolischen Namen dargestellt werden. Gewichtungen können auch symbolischen Namen, Codepunkten oder den Symbolen selbst zugewiesen werden. Wenn Codepunkte oder Zeichen verwendet werden, entspricht deren Gewicht dem numerischen Wert des Codepunkts (Position in der Unicode-Tabelle). Zeichen, die nicht explizit angegeben sind (soweit ich weiß), werden als der Tabelle mit einer primären Gewichtung zugewiesen betrachtet, die der Position in der Unicode-Tabelle entspricht. Besonderer Gewichtswert IGNORIEREN bedeutet, dass das Symbol auf der entsprechenden Vergleichsebene ignoriert wird.

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

Zeichen, die völlig ignoriert werden
Symbole, die der Zahl drei in den ersten beiden Ebenen entsprechen
der Anfang des kyrillischen Alphabets, das keine diakritischen Zeichen enthält und daher hauptsächlich nach der ersten und dritten Ebene sortiert ist.

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

Jetzt können Sie zur Sortierung der Beispiele vom Anfang des Artikels zurückkehren. Der Hinterhalt liegt in diesem Teil der Gewichtstabelle:

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

Es ist ersichtlich, dass in dieser Tabelle die Satzzeichen aus der Tabelle stammen ASCII (einschließlich Leerzeichen) wird beim Vergleich von Zeichenfolgen fast immer ignoriert. Die einzigen Ausnahmen sind Zeilen, die in allen Punkten übereinstimmen, mit Ausnahme von Satzzeichen, die an übereinstimmenden Positionen gefunden werden. Die Zeilen aus meinem Beispiel (nach Sortierung) für den Vergleichsalgorithmus sehen so aus:

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

Wenn man bedenkt, dass in der Skalentabelle Großbuchstaben im Russischen nach Kleinbuchstaben stehen (auf der dritten Ebene). schwerer als ), sieht die Sortierung absolut korrekt aus.

Beim Festlegen einer Variablen LC_COLLATE=C Es wird eine spezielle Tabelle geladen, die einen Byte-für-Byte-Vergleich angibt

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

Da in Unicode der Codepunkt Ё vor A steht, werden die Strings entsprechend sortiert.

Text- und Binärtabellen

Offensichtlich ist der String-Vergleich eine äußerst häufige Operation und das Parsen von Tabellen CTT ein ziemlich kostspieliges Verfahren. Um den Zugriff auf die Tabelle zu optimieren, wird diese mit dem Befehl in Binärform kompiliert Gebietsschemadef.

Team Gebietsschemadef akzeptiert als Parameter eine Datei mit einer Tabelle nationaler Merkmale (Option -i), in dem alle Zeichen durch Unicode-Punkte dargestellt werden, und eine Datei mit Entsprechungen zwischen Unicode-Punkten und Zeichen einer bestimmten Kodierung (Option -f). Als Ergebnis der Arbeit werden Binärdateien für das Gebietsschema mit dem im letzten Parameter angegebenen Namen erstellt.

glibc unterstützt zwei Binärdateiformate: „traditionell“ und „modern“.

Das traditionelle Format bedeutet, dass der Name des Gebietsschemas der Name des Unterverzeichnisses in ist /usr/lib/locale/. In diesem Unterverzeichnis werden Binärdateien gespeichert LC_COLLATE, LC_CTYPE, LC_TIME usw. Datei LC_IDENTIFICATION enthält den formalen Namen des Gebietsschemas (der vom Verzeichnisnamen abweichen kann) und Kommentare.

Das moderne Format beinhaltet die Speicherung aller Gebietsschemas in einem einzigen Archiv /usr/lib/locale/locale-archive, der dem virtuellen Speicher aller verwendenden Prozesse zugeordnet ist glibc. Der Gebietsschemaname im modernen Format unterliegt einer gewissen Kanonisierung – nur auf Kleinbuchstaben reduzierte Zahlen und Buchstaben verbleiben in den Kodierungsnamen. Also ru_RU.KOI8-R, wird gespeichert als ru_RU.koi8r.

Eingabedateien werden im aktuellen Verzeichnis sowie in Verzeichnissen durchsucht /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ für Dateien CTT bzw. Kodierungsdateien.

Zum Beispiel der Befehl

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

kompiliert die Datei /usr/share/i18n/locales/ru_RU Codierungsdatei verwenden /usr/share/i18n/charmaps/MAC-CYRILLIC.gz und speichern Sie das Ergebnis in /usr/lib/locale/locale-archive unter dem Namen ru_RU.maccyrillic

Wenn Sie die Variable festlegen LANG = en_US.UTF-8 dass glibc sucht in der folgenden Reihenfolge von Dateien und Verzeichnissen nach Gebietsschema-Binärdateien:

/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 ein Gebietsschema sowohl im traditionellen als auch im modernen Format vorkommt, wird dem modernen Format Vorrang eingeräumt.

Mit dem Befehl können Sie die Liste der kompilierten Gebietsschemas anzeigen Gebietsschema -a.

Bereiten Sie Ihre Vergleichstabelle vor

Mit diesem Wissen können Sie nun Ihre eigene ideale Saitenvergleichstabelle erstellen. Diese Tabelle sollte russische Buchstaben, einschließlich des Buchstabens Ё, korrekt vergleichen und gleichzeitig Satzzeichen gemäß der Tabelle berücksichtigen ASCII.

Der Prozess der Erstellung Ihrer eigenen Sortiertabelle besteht aus zwei Schritten: Bearbeiten der Gewichtstabelle und Kompilieren in binärer Form mit dem Befehl Gebietsschemadef.

Damit kann die Vergleichstabelle mit minimalem Bearbeitungsaufwand im Format angepasst werden ISO 14652 Es stehen Abschnitte zum Anpassen der Gewichte einer vorhandenen Tabelle zur Verfügung. Der Abschnitt beginnt mit einem Schlüsselwort nachbestellen und Angabe der Position, nach der der Austausch durchgeführt wird. Der Abschnitt endet mit der Zeile Nachbestellungsende. Wenn mehrere Abschnitte der Tabelle korrigiert werden müssen, wird für jeden dieser Abschnitte ein Abschnitt erstellt.

Ich habe neue Versionen der Dateien kopiert iso14651_t1_common и ru_RU aus dem Repository glibc in mein Home-Verzeichnis ~/.local/share/i18n/locales/ kopiert und den Abschnitt leicht bearbeitet LC_COLLATE в ru_RU. Neue Dateiversionen sind vollständig mit meiner Version kompatibel glibc. Wenn Sie ältere Versionen von Dateien verwenden möchten, müssen Sie die symbolischen Namen und die Stelle, an der die Ersetzung in der Tabelle beginnt, ändern.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

Tatsächlich wäre es notwendig, die Felder zu ändern LC_IDENTIFICATION sodass sie auf das Gebietsschema verweisen ru_MY, aber in meinem Beispiel war dies nicht erforderlich, da ich das Archiv von der Suche nach Gebietsschemas ausgeschlossen habe Gebietsschema-Archiv.

Dass Gebietsschemadef arbeitete mit Dateien in meinem Ordner über eine Variable I18NPATH Sie können ein zusätzliches Verzeichnis hinzufügen, um nach Eingabedateien zu suchen, 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 geht davon aus, dass in SPRACHE Sie können absolute Pfade zu Verzeichnissen mit Gebietsschemadateien schreiben, beginnend mit einem Schrägstrich, aber glibc в Linux Alle Pfade werden ab dem Basisverzeichnis gezählt, das über eine Variable überschrieben werden kann LOCPATH. Nach der Installation LOCPATH=~/.local/lib/locale/ Alle Dateien im Zusammenhang mit der Lokalisierung werden nur in meinem Ordner durchsucht. Archiv der Gebietsschemas mit dem Variablensatz LOCPATH ignoriert.

Hier der entscheidende Test:

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

Hurra! Wir haben es geschafft!

Einige Fehler

Die eingangs gestellten Fragen zur String-Sortierung habe ich bereits beantwortet, es bleiben aber noch ein paar Fragen zu Fehlern – sichtbare und unsichtbare.

Kehren wir zum ursprünglichen Problem zurück.

Und das Programm sortieren und Programm join Verwenden Sie die gleichen String-Vergleichsfunktionen von glibc. Wie ist es dazu gekommen? join gab einen Sortierfehler bei den durch den Befehl sortierten Zeilen aus sortieren im Gebietsschema de_US.UTF-8? Die Antwort ist einfach: sortieren vergleicht die gesamte Zeichenfolge und join vergleicht nur den Schlüssel, der standardmäßig der Anfang der Zeichenfolge bis zum ersten Leerzeichen ist. In meinem Beispiel führte dies zu einer Fehlermeldung, da die Sortierung der ersten Wörter in den Zeilen nicht mit der Sortierung der gesamten Zeilen übereinstimmte.

Gebietsschema "C" garantiert, dass in sortierten Zeichenfolgen auch die ersten Teilzeichenfolgen bis zum ersten Leerzeichen sortiert werden, was jedoch nur den Fehler maskiert. Es ist möglich, Daten (Personen mit gleichen Nachnamen, aber unterschiedlichen Vornamen) auszuwählen, die ohne die Fehlermeldung zu einem falschen Ergebnis beim Zusammenführen von Dateien führen würden. Wenn wir wollen join Wenn Sie Dateizeilen nach vollständigem Namen zusammenführen möchten, wäre es richtig, das Feldtrennzeichen explizit anzugeben und nach dem Schlüsselfeld und nicht nach der gesamten Zeile zu sortieren. In diesem Fall wird die Zusammenführung ordnungsgemäß durchgeführt und es treten in keinem Gebietsschema Fehler auf:

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

Erfolgreich ausgeführtes Beispiel in der Kodierung CP1251 enthält einen weiteren Fehler. Fakt ist, dass es in allen mir bekannten Distributionen so ist Linux Den Paketen fehlt das kompilierte Gebietsschema ru_RU.CP1251. Wenn das kompilierte Gebietsschema nicht gefunden wird, dann sortieren verwendet stillschweigend einen Byte-für-Byte-Vergleich, was wir beobachtet haben.

Übrigens gibt es noch einen weiteren kleinen Fehler im Zusammenhang mit der Unzugänglichkeit kompilierter Gebietsschemas. Team LOCPATH=/tmp Gebietsschema -a gibt eine Liste aller Gebietsschemas in aus Gebietsschema-Archiv, aber mit gesetzter Variable LOCPATH für alle Programme (einschließlich der meisten lokal) sind diese Gebietsschemas nicht verfügbar.

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

Abschluss

Wenn Sie ein Programmierer sind, der daran gewöhnt ist, zu denken, dass Strings eine Menge von Bytes sind, dann liegt die Wahl bei Ihnen LC_COLLATE=C.

Wenn Sie ein Linguist oder Wörterbuch-Compiler sind, kompilieren Sie besser in Ihrem Gebietsschema.

Wenn Sie ein einfacher Benutzer sind, müssen Sie sich nur an den Befehl gewöhnen ls -a gibt Dateien aus, die mit einem Punkt beginnen, gemischt mit Dateien, die mit einem Buchstaben beginnen, und Mitternachtskommandant, das seine internen Funktionen zum Sortieren von Namen verwendet, setzt Dateien, die mit einem Punkt beginnen, an den Anfang der Liste.