Einführung

Alles begann mit einem kurzen Skript, das Informationen über Adressen E-Mail von Mitarbeitern, die aus einer Liste von Newsletter-Abonnenten stammen, mit den Positionen der Mitarbeiter, die aus der Personalabteilung abgeleitet wurden, zu verbinden. 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
Jolkina Ella;Kranführerin
Ivanov Andrej;Installateur
Abakanov Michail;Maler

Um die Dateien zu kombinieren, wurden sie mit dem UNIX-Befehl sortiert sortieren und an das UNIX-Programm übergeben join, das unerwartet mit einem Fehler endete:

$> 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 im Großen und Ganzen korrekt ist, aber im Falle von übereinstimmenden männlichen und weiblichen Nachnamen, die weiblichen vor den männlichen stehen:

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

Es sieht nach einem Sortierfehler in Unicode oder nach einer Ausprägung des Feminismus im Sortieralgorithmus aus. Letzteres ist natürlich glaubwürdiger.

Lassen wir das vorerst join und konzentrieren wir uns auf sortieren. Lassen Sie uns versuchen, das Problem mit wissenschaftlichem Versuch und Irrtum zu lösen. Zunächst ändern wir die Locale von en_US auf ru_RU. Für die Sortierung wäre es ausreichend gewesen, die Umgebungsvariable LC_COLLATE, aber wir wollen uns nicht kleinlich zeigen:

$> 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 ein einbyte-Format zu kodieren:

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

Was soll's, wir müssen eine Lösung im Internet suchen. Kurz über russische Nachnamen ist nichts vorhanden, aber es gibt Fragen über andere Sortieranomalien. Zum Beispiel gibt es folgendes Problem: Unix sort behandelt '-' (Bindestrich) Zeichen als unsichtbar. Kurz gesagt, die Zeilen "a-b", "aa", "ac" werden sortiert als "aa", "a-b", "ac".

Die Antwort ist überall dieselbe: Nutzen Sie die Programmierlokalität "C" und Sie werden glücklich sein. Probieren wir es aus:

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

Etwas hat sich geändert. Die Ivanovs sind in der richtigen Reihenfolge angeordnet, aber Jolkina ist irgendwo hin verschwunden. 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 Jolkino in der ersten Zeile.

Das Problem scheint gelöst zu sein, aber zur Sicherheit probieren wir noch eine russische Kodierung — 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 merkwürdigerweise mit der Locale übereinstimmen. "C", und das gesamte Beispiel wird entsprechend ohne Fehler durchlaufen. Irgendeine Mystik.

Ich mag keine Mystik in der Programmierung, da sie in der Regel Fehler maskiert. Ich werde mich ernsthaft mit der Frage beschäftigen, wie es funktioniert. sortieren und auf was es Einfluss hat. LC_COLLATE .

Am Ende werde ich versuchen, die Fragen zu beantworten:

warum die weiblichen Nachnamen falsch sortiert wurden.
warum LANG=ru_RU.CP1251 war ein Äquivalent. LANG=C
warum sortieren und join verschiedene Darstellungen der Reihenfolge der sortierten Zeilen existieren.
warum in all meinen Beispielen Fehler vorhanden sind.
schließlich, wie man die Zeilen nach eigenem Geschmack sortiert.

Sortierung in Unicode.

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

Kollation — "Vergleich" von Strings — ist die Grundlage jedes Sortieralgorithmus. Die Algorithmen selbst können unterschiedlich sein ("Blase", "Vereinigung", "schnell"), aber sie verwenden alle den Vergleich von Paaren von Strings, um die Reihenfolge ihrer Anordnung zu bestimmen.

Die Sortierung von Zeichenfolgen in natürlicher Sprache ist ein recht komplexes Problem. Selbst in den einfachsten Ein-Byte-Kodierungen stimmt die Reihenfolge der Buchstaben im Alphabet, sofern sie sich von der englischen lateinischen Schrift unterscheidet, bereits nicht mehr mit der Reihenfolge der numerischen Werte überein, die diese Buchstaben kodieren. So steht im deutschen Alphabet der Buchstabe Ö zwischen O und P, und in der Kodierung CP850 liegt er zwischen ÿ und Ü..

Man kann versuchen, sich von der spezifischen Kodierung zu abstrahieren und "ideale" Buchstaben zu betrachten, die in einer bestimmten Reihenfolge angeordnet sind, wie es in Unicode der Fall ist. Die Kodierungen UTF8, UTF16 oder die Ein-Byte-Kodierung KOI8-R (wenn eine begrenzte Teilmenge von Unicode erforderlich ist), geben unterschiedliche numerische Darstellungen der Buchstaben, beziehen sich jedoch auf dieselben Elemente der Basistabelle.

Es stellt sich heraus, dass wir selbst, wenn wir eine Zeichentabelle von Grund auf neu erstellen, keine universelle Reihenfolge der Zeichen festlegen können. In verschiedenen nationalen Alphabeten, die die gleichen Buchstaben verwenden, kann die Reihenfolge dieser Buchstaben unterschiedlich sein. Zum Beispiel im Französischen, Æ wird als Ligatur betrachtet und wie eine Zeichenfolge sortiert AE. Im Norwegischen hingegen Æ wird als eigenständiger Buchstabe betrachtet, der nach Zkommt. Übrigens gibt es neben Ligaturen wie Æ auch Buchstaben, die aus mehreren Zeichen bestehen. Im Tschechischen Alphabet gibt es den Buchstaben Ch, der zwischen H und I.

Zu den Unterschieden zwischen den Alphabeten gibt es weitere nationale Traditionen, die die Sortierung beeinflussen. Insbesondere stellt sich die Frage: In welcher Reihenfolge sollten Wörter in einem Wörterbuch angeordnet werden, die aus Groß- und Kleinbuchstaben bestehen? Auch die Verwendung von Satzzeichen kann die Sortierung beeinflussen. Im Spanischen wird am Anfang eines Fragesatzes ein umgedrehter Fragezeichen gesetzt (¿Te gusta la música?). In diesem Fall ist es offensichtlich, dass Frage-Sätze nicht in einem separaten Cluster außerhalb des Alphabets gruppiert werden sollten, sondern wie sortiert man Zeichenfolgen mit anderen Satzzeichen?

Ich werde nicht auf die Sortierung von Zeichenfolgen in Sprachen eingehen, die sich stark von europäischen unterscheiden. Ich möchte darauf hinweisen, dass Zeichen in Sprachen mit einer Schreibrichtung von rechts nach links oder von oben nach unten wahrscheinlich in der Lese-Reihenfolge gespeichert sind, und sogar in nicht-alphabetischen Schriften gibt es eigene Möglichkeiten, Zeichenfolgen zeichenweise zu ordnen. Beispielsweise können Schriftzeichen nach ihrer Form (Schlüssel von chinesischen Zeichen) oder nach ihrer Aussprache sortiert werden. Wie Emojis sortiert werden sollten, kann ich mir ehrlich gesagt nicht vorstellen, aber auch dafür kann man sich etwas überlegen.

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

Der Vergleich von Zeichenfolgen hängt nicht von der Position der Zeichen in der Codierungstabelle ab;
Zeichenfolgen, die ein einzelnes Zeichen bilden, werden in eine kanonische Form gebracht (A + oberer Kreis ist das gleiche wie Å);
); beim Vergleich von Zeichenfolgen wird das Zeichen im Kontext der Zeichenfolge betrachtet und, wenn nötig, mit Nachbarn zu einer Vergleichseinheit zusammengefügt (Ch im Tschechischen) oder in mehrere (Æ im Französischen);
Alle nationalen Besonderheiten (Alphabete, Groß-/Kleinbuchstaben, Satzzeichen, Reihenfolge der Schriftarten) müssen bis hin zur manuellen Festlegung der Reihenfolge (Emojis) konfiguriert werden;
Der Vergleich ist nicht nur für die Sortierung wichtig, sondern auch an vielen anderen Stellen, zum Beispiel um Bereichszeilen festzulegen (Ersatz {A…я} in bash);
Der Vergleich muss schnell genug durchgeführt werden.

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

Der Vergleichsalgorithmus darf nicht einen separaten Zeichensatz für jede Sprache erfordern (Russisch und Ukrainisch verwenden gemeinsam die meisten Zeichen des kyrillischen Alphabets);
Der Vergleich darf nicht auf der Reihenfolge der Zeichen in Unicode-Tabellen basieren;
Das Gewicht einer Zeichenkette darf kein Attribut des Strings sein, da dieselbe Zeichenkette in verschiedenen kulturellen Kontexten unterschiedliche Gewichte haben kann;
Die Gewichte von Strings können sich beim Zusammenführen oder Teilen ändern (aus x < y Das bedeutet nicht, dass xz < yz);
Verschiedene Strings, die das gleiche Gewicht haben, gelten aus Sicht des Sortieralgorithmus als gleich. Eine zusätzliche Ordnung solcher Strings kann möglich sein, könnte jedoch die Leistung verschlechtern;
Bei wiederholten Sortierungen können Strings mit dem gleichen Gewicht die Plätze tauschen. Stabilität ist eine Eigenschaft eines bestimmten Sortieralgorithmus, nicht eine Eigenschaft des Vergleichsalgorithmus (siehe vorheriger Punkt);
Die Sortierregeln können sich im Laufe der Zeit ändern, während die kulturellen Traditionen präzisiert oder geändert werden.

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

Um all diesen Anforderungen gerecht zu werden, wurde ein mehrstufiger (tatsächlich vierstufiger) Tabellen-Sortieralgorithmus vorgeschlagen.

Zunächst werden die Zeichen in der Zeichenkette in ihre kanonische Form gebracht 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 auf Größer-Kleiner verglichen werden können. Ein spezieller Wert IGNORED (0x0) bedeutet, dass diese Einheit auf der entsprechenden Vergleichsebene nicht an dem Vergleich teilnimmt. Der Vergleich von Zeichenfolgen kann mehrmals wiederholt werden, wobei die Gewichte der entsprechenden Ebenen verwendet werden. Auf jeder der Ebenen werden die Gewichte der Vergleichseinheiten zweier Zeichenfolgen nacheinander miteinander verglichen.

In verschiedenen Implementierungen des Algorithmus für verschiedene nationale Traditionen können die Werte der Koeffizienten unterschiedlich sein, aber im Standard von Unicode ist eine Basistabelle mit Gewichten enthalten — "Default Unicode Collation Element Table" (DUCET). Ich möchte bemerken, dass die Festlegung der Variablen LC_COLLATE tatsächlich einen Hinweis auf die Auswahl der Gewichtstabelle in der Funktion zum Vergleich von Zeichenfolgen darstellt.

Die Gewichtskoeffizienten DUCET sind wie folgt strukturiert:

Auf der ersten Ebene werden alle Buchstaben in dieselbe Groß- und Kleinschreibung umgewandelt, 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ß- und 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, erfolgt ein erneuter Vergleich mit den Gewichten der zweiten Ebene; danach möglicherweise mit der dritten und vierten.

Der Vergleich endet, wenn in den Zeichenfolgen übereinstimmende Vergleichseinheiten mit unterschiedlichen Gewichten gefunden werden. Zeichenfolgen, die auf allen vier Ebenen gleiche Gewichte haben, werden als gleich angesehen.

Dieser Algorithmus (mit einer Menge zusätzlicher technischer Details) gab dem Bericht Nr. 10 — "Unicode Collation Algorithm" (UCA).

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

Für die Testung von Implementierungen UCA gibt es einen speziellen Test, der eine Gewichtstabelle, die implementiert DUCETverwendet. In der Gewichtstabelle können verschiedene Kuriositäten gefunden werden. Zum Beispiel gibt es dort die Reihenfolge der Spielsteine von Mahjong und dem europäischen Domino sowie die Reihenfolge der Farben in einem Kartenspiel (Symbol 1F000 und weiter). Die Kartensuiten sind gemäß den Regeln des Bridge angeordnet — PIK, KREUZ, HERZ, KARO, und die Karten in der Suite — in der Reihenfolge 10, 2, 3… K.

Eine manuelle Überprüfung der Richtigkeit der Sortierung von Zeichenfolgen gemäß DUCET wäre ziemlich mühsam, aber zum Glück für uns gibt es eine vorbildliche Implementierung einer Bibliothek zur Arbeit mit Unicode — "Internationale Komponenten für Unicode" (ICU).

Auf der Website dieser Bibliothek, die in IBM, gibt es Demoseiten, einschließlich einer Seite mit dem Algorithmus zum Vergleichen von Zeichenfolgen. Wir geben unsere Teststrings mit den Standardeinstellungen ein und, oh Wunder, erhalten eine perfekte russische Sortierung.

Abakanov Michail;Maler
Jolkina Ella;Kranführerin
Ivanov Andrei;Schlosser
Ivanova Alla;Rechtsanwältin

Übrigens, auf der Website ICU kann man eine Erläuterung der Arbeitsweise des Vergleichsalgorithmus bei der Verarbeitung von Satzzeichen finden. In den Beispielen Collation FAQ werden Apostroph und Bindestrich ignoriert.

Unicode hat uns geholfen, aber die Ursachen für das merkwürdige Verhalten sortieren in Linux müssen wir woanders suchen.

Sortierung in glibc

Ein kurzer Blick auf den Quellcode des Dienstprogramms sortieren aus GNU Core Utils zeigte, dass die Lokalisierung in dem Dienstprogramm sich auf das Drucken des aktuellen Wertes der Variablen beschränkt LC_COLLATE im Debug-Modus beim Start:

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

Der Vergleich von Zeichenfolgen erfolgt durch die Standardfunktion strcoll, was bedeutet, dass alles Interessante in der Bibliothek glibc.

Auf wiki des Projekts glibc für den Vergleich von Zeichenfolgen gewidmet ist, einem Absatz. Aus diesem Absatz kann man verstehen, dass in der glibc die Sortierung auf dem uns bereits bekannten Algorithmus basiert UCA (Der Unicode-Sortieralgorithmus) und/oder auf einem ähnlichen Standard ISO 14651 (Internationale Zeichenreihenfolge und Vergleich). Zum letzten Standard sollte angemerkt werden, dass er auf der Website standards.iso.org ISO 14651 offiziell als öffentlich zugänglich erklärt wurde, der entsprechende Link jedoch auf eine nicht existierende Seite führt. Google zeigt mehrere Seiten mit Links zu offiziellen Websites, die anbieten, eine elektronische Kopie des Standards für ein paar Hundert Euro zu kaufen, aber auf der dritten oder vierten Seite der Google-Suche findet man auch direkte Links zu PDF. Insgesamt weicht der Standard kaum von UCA, ab, wird jedoch langweiliger gelesen, da er keine anschaulichen Beispiele für nationale Besonderheiten der Sortierung von Zeichenfolgen enthält.

Die interessanteste Information auf wiki war der Link zu Bug-Tracker mit einer Diskussion über die Implementierung des Zeichenfolgenvergleichs in glibc. Aus der Diskussion kann man erfahren, dass in glibc für den Vergleich von Zeichenfolgen eine ISOTabelle verwendet wird Die gemeinsame Vorlagentabelle (CTT), deren Adresse im Anhang zu finden ist A des Standards ISO 14651. Zwischen 2000 und 2015 wurde diese Tabelle in glibc hat keinen Maintainer gehabt und unterschied sich (zumindest äußerlich) erheblich von der aktuellen Version des Standards. Von 2015 bis 2018 fand eine Anpassung an die neue Version der Tabelle statt und derzeit haben Sie die Möglichkeit, sowohl die neue Version der Tabelle (CentOS 8), als auch die alte zu begegnen (CentOS 7).

Jetzt, da wir alle Informationen über den Algorithmus und die Hilfstabellen haben, können wir zur ursprünglichen Problematik zurückkehren und verstehen, wie man die Zeilen in der russischen Locale richtig sortiert.

ISO 14651/14652

Der Quellcode der betreffenden Tabelle CTT findet sich in den meisten Distributionen Linux im Verzeichnis /usr/share/i18n/locales/. Die Tabelle selbst befindet sich in der Datei iso14651_t1_common. Diese Datei wird dann mit der Direktive copy iso14651_t1_common in die Datei iso14651_t1, die ihrerseits in die nationalen Dateien eingebunden wird, einschließlich en_US und ru_RU. In den meisten Distributionen Linux sind alle Quelldateien im Basispaket enthalten, aber wenn sie nicht vorhanden sind, müssen Sie ein zusätzliches Paket aus der Distribution installieren.

Dateistruktur iso14651_t1 mag 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 ISO 14652beschrieben, eine Kopie davon kann von der Website open-std.orgheruntergeladen werden. Eine weitere Beschreibung des Dateiformats kann in den Spezifikationen POSIX ab OpenGroupgelesen werden. Als Alternative zum Lesen des Standards kann man die Quelltexte der Funktion collate_read in glibc/locale/programs/ld-collate.c.

Die Struktur der Datei sieht folgendermaßen aus:

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

escape_char /
comment_char %

In der Datei werden Token im Format <Uxxxx> oder <Uxxxxxxxx> (wo x — 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 außerhalb des Kontexts keine besondere Bedeutung haben.

Zeichenkette LC_COLLATE sagt uns, dass im Folgenden 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 Kombinationen von Zeichen festgelegt. Im Allgemeinen gehören zwei Arten von Namen zu zwei verschiedenen Entitäten, aber in der tatsächlichen Datei sind sie vermischt. Die Gewichtsbezeichner werden mit dem Schlüsselwort collating-symbol (Vergleichssymbol), da Unicode-Zeichen mit gleichen Gewichten als äquivalente Symbole betrachtet werden.

Die Gesamtlänge des Abschnitts in der aktuellen Revision der Datei beträgt etwa 900 Zeilen. Ich habe Beispiele aus verschiedenen Quellen gesammelt, um die Beliebigkeit der Namen und einige Arten der Syntax zu veranschaulichen.

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 belassen.
...
collating-element  von ""
collating-element  von ""

collating-symbol registriert die Zeichenkette OSMANYA in der Gewichtsnamentabelle
collating-symbol .. registriert eine Sequenz von Namen, die aus einem Präfix bestehen S und einem hexadezimalen Zahlensuffix von 1D000 bis 1D35F.
FFFF in collating-symbol sieht aus wie eine große nicht-negative ganze Zahl im hexadezimalen Zahlensystem, aber <SFFFF> ist einfach ein Name, der aussehen könnte wie <VERYBIGVAL>
name <U0413> steht für den Codepunkt im Encoding UCS-4
collating-element von "" registriert einen neuen Namen für ein Paar von Unicode-Punkten.

Sobald die Gewichtsnamen definiert sind, werden die tatsächlichen Gewichte festgelegt. Da bei einem Vergleich nur die Relationen größer-kleiner von Bedeutung sind, werden die Gewichte in einer einfachen Auflistung der Namen festgelegt. Zuerst werden die "leichtesten" Gewichte und dann die "schwereren" aufgelistet. Ich erinnere daran, dass jedem Unicode-Zeichen vier verschiedene Gewichte zugewiesen werden. Hier sind sie in einer einheitlichen ordentlichen Sequenz zusammengefasst. Theoretisch kann jeder symbolische Name auf jedem der vier Ebenen verwendet werden, aber Anmerkungen deuten darauf hin, dass die Entwickler die Namen mental in Ebenen unterteilen.

% Symbolische Gewichtszuweisungen

% Gewichtszuweisungen der dritten Ebene




...
% Gewichtszuweisungen der zweiten Ebene

 % KOMBINIERENDE UNTERLINIE
 % KOMBINIERENDE KOMMA OBEN
 % KOMBINIERENDE UMGEKEHRTE KOMMA OBEN
...
% Gewichtszuweisungen der ersten Ebene
 % HORIZONTALE TABULIERUNG
 % ZEILENWECHSEL
 % VERTIKALE TABULIERUNG
...
 % KIRILLESCHES KLEINES BUCHSTABEN DE
 % KIRILLESCHES KLEINES BUCHSTABEN KOMI DE
 % KIRILLESCHES KLEINES BUCHSTABEN DJE
 % KIRILLESCHES KLEINES BUCHSTABEN KOMI DJE
 % KIRILLESCHES KLEINES BUCHSTABEN GJE
 % KIRILLESCHES KLEINES BUCHSTABEN ZE MIT DESCENDER
 % KIRILLESCHES KLEINES BUCHSTABEN IE
 % KIRILLESCHES KLEINES BUCHSTABEN IE MIT BREVE
 % KIRILLESCHES KLEINES BUCHSTABEN UKRAINISCHES IE
 % KIRILLESCHES KLEINES BUCHSTABEN ZHE

Endlich 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 legen fest, in welcher Richtung die Zeilen auf jeder Vergleichsebene durchsucht werden. Standardmäßig wird der Parameter verwendet forward. Der Inhalt des Abschnitts besteht aus Zeilen, die den Zeichen-Code und vier Gewichtungen enthalten. Der Zeichen-Code kann entweder durch das Zeichen selbst, den Codepunkt oder den zuvor 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 (Position in der Unicode-Tabelle). Zeichen, die nicht ausdrücklich aufgeführt sind (so verstehe ich), werden in der Tabelle mit einem Primärgewicht angerechnet, das mit der Position in der Unicode-Tabelle übereinstimmt. Der besondere Gewichtswert IGNORE bedeutet, dass das entsprechende Zeichen auf dieser Vergleichsebene ignoriert wird.

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

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

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
 ;;; % ZIFFER DREI
 ;;; % VOLLSCHRIFT ZIFFER DREI
 ;;; % KLAUSE ZIFFER DREI
 ;;; % ZIFFER DREI PUNKT
 ;;; % MATHEMATISCH FETT ZIFFER DREI
...
 ;;; % KYRILLESCH KLEINBUCHSTABE A
 ;;; % KYRILLESCH GROSSBUCHSTABE A
 ;;; % KYRILLESCH KLEINBUCHSTABE A MIT BREVE
 ;;; % KYRILLESCH KLEINBUCHSTABE A MIT BREVE
...
 ;;; % KYRILLESCH KLEINBUCHSTABE BE
 ;;; % KYRILLESCH GROSSBUCHSTABE BE
 ;;; % KYRILLESCH KLEINBUCHSTABE VE
 ;;; % KYRILLESCH GROSSBUCHSTABE VE
...
order_end

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

IGNORIERE;IGNORIERE;IGNORIERE; % RÄUME
 IGNORIERE;IGNORIERE;IGNORIERE; % AUSRUFEZEICHEN
 IGNORIERE;IGNORIERE;IGNORIERE; % ANFÜHRUNGSZEICHEN
...

Es ist offensichtlich, dass in dieser Tabelle die Interpunktion aus der Tabelle stammt. ASCII (einschließlich Leerzeichen) wird beim Vergleich von Zeichenfolgen praktisch immer ignoriert. Die Ausnahme bilden nur Zeichenfolgen, die in allem übereinstimmen, außer in der Interpunktion, die an übereinstimmenden Positionen vorkommt. Die Zeichenfolgen aus meinem Beispiel (nach der Sortierung) sehen für den Vergleichsalgorithmus so aus:

AbakanovMikhailMaler
JolkinaEllegardistin
IvanovaAllaMalerin
IvanovAndreiZimmermann

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

Bei der Festlegung der Variablen LC_COLLATE=C wird eine spezielle Tabelle geladen, die byteweise Vergleiche festlegt.

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ärdatenbanken

Offensichtlich ist der Vergleich von Zeichenfolgen eine äußerst häufige Operation, während das Parsen der Tabelle CTT eine ziemlich aufwändige Prozedur ist. Zur Optimierung des Zugriffs auf die Tabelle wird sie mit dem Befehl localedef.

Team localedef so konfiguriert, dass sie als Parameter eine Datei mit der Tabelle der nationalen Besonderheiten (Option -i), in der alle Zeichen durch Unicode-Punkten dargestellt werden, und eine Datei mit der Zuordnung der Unicode-Punkte zu Zeichen einer bestimmten Kodierung (Option -f) erhält. Infolge der Verarbeitung werden Binärdateien für die Locale mit dem im letzten Parameter angegebenen Namen erstellt.

Glibc unterstützt zwei Formate von Binärdateien: "traditionell" und "modern".

Das traditionelle Format setzt voraus, dass der Name der Locale der Name eines Unterverzeichnisses in /usr/lib/locale/. In diesem Unterverzeichnis werden die Binärdateien aufbewahrt. 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 sieht vor, dass alle Locales in einem einzigen Archiv gespeichert werden /usr/lib/locale/locale-archive, das in den virtuellen Speicher aller Prozesse abgebildet wird, die es verwenden. glibc. Der Name der Locale im modernen Format wird einer gewissen Kanonisierung unterzogen – in den Kodierungsnamen bleiben nur Ziffern und Buchstaben, die in Kleinbuchstaben konvertiert sind. So ru_RU.KOI8-R, wird als ru_RU.koi8r.

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

Zum Beispiel, der Befehl

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

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

Wenn die Variable LANG=en_US.UTF-8 gesetzt ist, glibc wird nach binären Locale-Dateien 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 vorhanden ist, hat das moderne Format Vorrang.

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

eingesehen werden.

Erstellung einer eigenen Sortiertabelle ASCII.

Jetzt, gerüstet mit dem Wissen, kann man eine eigene ideale Vergleichstabelle von Zeichen erstellen. Diese Tabelle sollte russische Buchstaben korrekt vergleichen, einschließlich des Buchstabens Ё, und dabei die Interpunktion gemäß der Tabelle berücksichtigen. localedef.

Der Prozess der Erstellung der eigenen Sortiertabelle besteht aus zwei Phasen: der Bearbeitung der Gewichtungstabelle und ihrer Kompilierung in eine binäre Form mit dem Befehl ISO 14652 Um die Vergleichstabelle mit minimalen Bearbeitungskosten anzupassen, sieht das Format Abschnitte zur Anpassung der Gewichtung einer bereits bestehenden Tabelle vor. Der Abschnitt beginnt mit dem Schlüsselwort reorder-after und der Angabe der Position, nach der die Ersetzung erfolgt. Der Abschnitt endet mit der Zeile. Wenn mehrere Teile der Tabelle angepasst werden müssen, wird für jeden Teil ein eigener Abschnitt erstellt.

Ich habe die neuen Versionen der Dateien iso14651_t1_common und ru_RU aus dem Repository glibc in mein Heimatverzeichnis ~\/local\/share\/i18n\/locales\/ kopiert und den Abschnitt leicht bearbeitet. LC_COLLATE in ru_RUDie neuen Versionen der Dateien sind vollständig kompatibel mit meiner Version. glibcWenn Sie die alten Versionen der Dateien verwenden möchten, müssen Sie die symbolischen Namen ändern und den Ort anpassen, an dem der Austausch in der Tabelle beginnt.

LC_COLLATE
% Kopiere die Vorlage von ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPACE
 ;;; % AUSRUFEZEICHEN
 ;;; % ANFÜHRUNGSZEICHEN
...
 ;;; % RECHTE geschweifte Klammer
 ;;; % TILDE
reorder-end
END LC_COLLATE

Tatsächlich hätte man die Felder in LC_IDENTIFICATION so ändern müssen, dass sie auf die Locale ru_MYverweisen, aber in meinem Beispiel war das nicht nötig, da ich die Locales aus dem Suchearchiv ausgeschlossene locale-archive.

Um localedef mit den Dateien in meinem Ordner über die Variable I18NPATH kann ein zusätzliches Verzeichnis zur Suche nach Eingabedateien hinzugefügt werden, während das Verzeichnis zum Speichern der Binärdateien als Pfad mit Schrägstrichen angegeben werden kann:

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

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

Hier ist der entscheidende Test:

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

Hurra! Wir haben es geschafft!

Arbeiten an Fehlern

Ich habe bereits die Fragen zur Sortierung der Zeilen, die zu Beginn gestellt wurden, beantwortet, aber es bleiben noch ein paar Fragen zu Fehlern – sichtbaren und unsichtbaren.

Lassen Sie uns zur ursprünglichen Aufgabe zurückkehren.

Und das Programm sortieren und das Programm join verwendet dieselben Zeichenvergleichsfunktionen aus glibc. Wie konnte es also sein, dass join einen Sortierfehler bei den von dem Befehl sortieren in der Locale en_US.UTF-8? Ответ прост: sortieren verursachte, vergleicht die gesamte Zeichenfolge, während join nur den Schlüssel vergleicht, der standardmäßig der Anfang der Zeichenfolge bis zum ersten Leerzeichen ist. In meinem Beispiel führte das zu einer Fehlermeldung, da die Sortierung der ersten Wörter in den Zeilen nicht mit der Sortierung der vollständigen Zeilen übereinstimmte.

Die Locale "C" stellt sicher, dass in den sortierten Zeichenfolgen die anfänglichen Teilzeichenfolgen bis zum ersten Leerzeichen ebenfalls sortiert sind, aber das maskiert nur den Fehler. Es können solche Daten (Menschen mit denselben Nachnamen, aber unterschiedlichen Vornamen) ausgewählt werden, die ohne Fehlermeldung zu einem falschen Ergebnis beim Zusammenführen von Dateien führen würden. Wenn wir möchten, dass join Zeilen von Dateien nach vollständigem Namen (Vorname, Nachname) zusammenführt, dann wäre der richtige Weg die explizite Angabe des Feldtrennzeichens und die Sortierung nach dem Schlüssel, anstatt nach der gesamten Zeile. In diesem Fall erfolgt das Zusammenführen korrekt 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 ausgeführtes Beispiel in der Kodierung CP1251 enthält einen weiteren Fehler. Das Problem ist, dass in allen mir bekannten Distributionen Linux die kompilierte Locale fehlt ru_RU.CP1251. Wenn die kompilierte Locale nicht gefunden wird, sortieren verwendet es stillschweigend den byte-by-byte Vergleich, was wir beobachtet haben.

Übrigens gibt es noch einen kleinen Bug im Zusammenhang mit der Unzugänglichkeit der kompilierten Locales. Der Befehl LOCPATH=\/tmp locale -a gibt eine Liste aller Locales in locale-archive, aber mit einer gesetzten Variablen LOCPATH sind diese Locales für alle Programme (einschließlich locale) nicht verfügbar.

$> LOCPATH=\/tmp locale -a | grep en_US
locale: LC_CTYPE kann nicht auf die Standard-Locale gesetzt werden: Datei oder Verzeichnis nicht gefunden
locale: LC_MESSAGES kann nicht auf die Standard-Locale gesetzt werden: Datei oder Verzeichnis nicht gefunden
locale: LC_COLLATE kann nicht auf die Standard-Locale gesetzt werden: 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 den einfachen Byte-Vergleich

Fazit

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

Wenn Sie Linguist oder Wörterbuchmacher sind, dann sollten Sie Ihre Locale besser kompilieren.

Wenn Sie ein einfacher Benutzer sind, dann sollten Sie sich daran gewöhnen, dass der Befehl ls -a Dateien auflistet, die mit einem Punkt beginnen, vermischt mit Dateien, die mit einem Buchstaben beginnen, und Midnight Commander, der seine internen Funktionen zum Sortieren von Namen verwendet, bringt Dateien, die mit einem Punkt beginnen, an den Anfang der Liste.