introduction

Tout a commencé avec un court script censé combiner les informations d'adresse Courriel employés obtenus à partir de la liste des utilisateurs de la liste de diffusion, avec les postes d'employés obtenus à partir de la base de données du service RH. Les deux listes ont été exportées vers des fichiers texte Unicode UTF-8 et enregistré avec les fins de ligne Unix.

teneur mail.txt

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

teneur buhg.txt

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

Pour fusionner, les fichiers ont été triés par la commande Unix sort et soumis à l'entrée du programme Unix rejoindre, qui a échoué de manière inattendue avec une erreur :

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

En regardant le résultat du tri avec vos yeux, vous constaterez que, en général, le tri est correct, mais en cas de coïncidences de noms masculins et féminins, les noms féminins précèdent les noms masculins :

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

Cela ressemble à un problème de tri dans Unicode ou à une manifestation de féminisme dans l'algorithme de tri. La première est bien entendu la plus plausible.

Remettons ça à plus tard pour l'instant rejoindre et se concentrer sur sort. Essayons de résoudre le problème en utilisant des techniques scientifiques. Tout d'abord, changeons les paramètres régionaux de en_US sur ru_RU. Pour trier, il suffirait de définir la variable d'environnement LC_COLLER, mais on ne perdra pas de temps en bagatelles :

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

Rien n'a changé.

Essayons de recoder les fichiers dans un encodage sur un seul octet :

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

Encore une fois, rien n'a changé.

Vous ne pouvez rien faire, il faudra chercher une solution sur Internet. Il n'y a rien directement sur les noms de famille russes, mais des questions se posent sur d'autres bizarreries de tri. Par exemple, voici un problème : Le tri Unix traite les caractères '-' (tiret) comme invisibles. En bref, les chaînes « ab », « aa », « ac » sont triées comme « aa », « ab », « ac ».

La réponse est standard partout : utilisez les paramètres régionaux du programmeur "C" et tu seras heureux. Essayons:

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

Quelque chose a changé. Les Ivanov se sont alignés dans le bon ordre, même si Yolkina a glissé quelque part. Revenons au problème initial :

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

Cela a fonctionné sans erreur, comme Internet le promettait. Et ce malgré Yolkina en première ligne.

Le problème semble résolu, mais juste au cas où, essayons un autre encodage russe - Windows CP1251:

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

Curieusement, le résultat du tri coïncidera avec la localisation "C", et l'ensemble de l'exemple s'exécute donc sans erreur. Une sorte de mysticisme.

Je n'aime pas le mysticisme en programmation car il masque généralement les erreurs. Il va falloir étudier sérieusement son fonctionnement. sort et qu'est-ce que cela affecte ? LC_COLLER .

A la fin, j'essaierai de répondre aux questions :

pourquoi les noms de famille féminins ont-ils été mal triés ?
pourquoi LANG=ru_RU.CP1251 s'est avéré être équivalent LANGUE=C
pourquoi faire sort и rejoindre différentes idées sur l'ordre des chaînes triées
pourquoi y a-t-il des erreurs dans tous mes exemples ?
enfin comment trier les chaînes à votre guise

Tri en Unicode

Le premier arrêt sera le rapport technique n°10 intitulé Algorithme de classement Unicode en ligne unicode.org. Le rapport contient de nombreux détails techniques, permettez-moi donc de résumer brièvement les idées principales.

Collation — La « comparaison » de chaînes est la base de tout algorithme de tri. Les algorithmes eux-mêmes peuvent différer (« bulle », « fusion », « rapide »), mais ils utiliseront tous une comparaison d'une paire de chaînes pour déterminer l'ordre dans lequel elles apparaissent.

Le tri de chaînes en langage naturel est un problème assez complexe. Même dans les codages à un octet les plus simples, l'ordre des lettres de l'alphabet, même quelque peu différent de l'alphabet latin anglais, ne coïncidera plus avec l'ordre des valeurs numériques avec lesquelles ces lettres sont codées. Donc dans l'alphabet allemand la lettre Ö se tient entre О и P, et dans l'encodage CP850 elle se situe entre ÿ и Ü.

Vous pouvez essayer de faire abstraction d'un encodage spécifique et considérer des lettres « idéales » disposées dans un certain ordre, comme cela se fait dans Unicode. Encodages UTF8, UTF16 ou un octet KOI8-R (si un sous-ensemble limité d'Unicode est nécessaire) donnera différentes représentations numériques des lettres, mais fera référence aux mêmes éléments de la table de base.

Il s'avère que même si nous construisons une table de symboles à partir de zéro, nous ne pourrons pas lui attribuer un ordre universel des symboles. Dans les différents alphabets nationaux utilisant les mêmes lettres, l’ordre de ces lettres peut différer. Par exemple, en français Æ sera considéré comme une ligature et trié comme une chaîne AE. En norvégien Æ sera une lettre séparée, située après Z. D'ailleurs, en plus des ligatures comme Æ Il y a des lettres écrites avec plusieurs symboles. Donc dans l'alphabet tchèque il y a une lettre Ch, qui se situe entre H и I.

Outre les différences entre les alphabets, il existe d’autres traditions nationales qui influencent le tri. En particulier, la question se pose : dans quel ordre les mots composés de lettres majuscules et minuscules doivent-ils apparaître dans le dictionnaire ? Le tri peut également être affecté par l’utilisation de signes de ponctuation. En espagnol, un point d'interrogation inversé est utilisé au début d'une phrase interrogative (Tu aimes la musique?). Dans ce cas, il est évident qu'il ne faut pas regrouper les phrases interrogatives dans un groupe distinct en dehors de l'alphabet, mais comment trier les lignes avec d'autres signes de ponctuation ?

Je ne m'attarderai pas sur le tri des chaînes dans des langues très différentes des langues européennes. Notez que dans les langues avec un sens d'écriture de droite à gauche ou de haut en bas, les caractères des lignes sont très probablement stockés dans l'ordre de lecture, et même les systèmes d'écriture non alphabétiques ont leurs propres façons d'ordonner les lignes caractère par caractère. . Par exemple, les hiéroglyphes peuvent être classés par style (Touches de caractères chinois) ou par prononciation. Pour être honnête, je n’ai aucune idée de la manière dont les emojis devraient être disposés, mais vous pouvez aussi leur proposer quelque chose.

Sur la base des fonctionnalités énumérées ci-dessus, les exigences de base pour comparer des chaînes basées sur des tableaux Unicode ont été formulées :

la comparaison des chaînes ne dépend pas de la position des caractères dans la table de codes ;
les séquences de caractères formant un seul caractère sont réduites à la forme canonique (A + le cercle du haut est le même que Å);
Lors de la comparaison de chaînes, un caractère est considéré dans le contexte de la chaîne et, si nécessaire, combiné avec ses voisins en une seule unité de comparaison (Ch en tchèque) ou est divisé en plusieurs (Æ en français);
toutes les caractéristiques nationales (alphabet, majuscules/minuscules, ponctuation, ordre des types d'écriture) doivent être configurées jusqu'à l'attribution manuelle de l'ordre (emoji) ;
la comparaison est importante non seulement pour le tri, mais aussi à de nombreux autres endroits, par exemple pour spécifier des plages de lignes (en remplaçant {A... z} dans bash);
la comparaison devrait être faite assez rapidement.

De plus, les auteurs du rapport ont formulé des propriétés de comparaison sur lesquelles les développeurs d'algorithmes ne devraient pas s'appuyer :

l'algorithme de comparaison ne devrait pas nécessiter un jeu de caractères distinct pour chaque langue (les langues russe et ukrainienne partagent la plupart des caractères cyrilliques) ;
la comparaison ne doit pas reposer sur l'ordre des caractères dans les tableaux Unicode ;
le poids de la chaîne ne doit pas être un attribut de la chaîne, car la même chaîne dans différents contextes culturels peut avoir des poids différents ;
les poids des lignes peuvent changer lors de la fusion ou de la division (de x < y ça ne suit pas ça xz < yz);
différentes chaînes ayant les mêmes poids sont considérées comme égales du point de vue de l'algorithme de tri. L'introduction d'un ordre supplémentaire de ces chaînes est possible, mais cela peut dégrader les performances ;
Lors d'un tri répété, les lignes avec les mêmes poids peuvent être permutées. La robustesse est une propriété d'un algorithme de tri spécifique, et non une propriété d'un algorithme de comparaison de chaînes (voir le paragraphe précédent) ;
Les règles de tri peuvent changer au fil du temps à mesure que les traditions culturelles s'affinent/changent.

Il est également précisé que l'algorithme de comparaison ne connaît rien de la sémantique des chaînes en cours de traitement. Ainsi, les chaînes composées uniquement de chiffres ne doivent pas être comparées à des nombres, et dans les listes de noms anglais, l'article (Beatles, les).

Afin de satisfaire toutes les exigences spécifiées, un algorithme de tri de table à plusieurs niveaux (en fait à quatre niveaux) est proposé.

Auparavant, les caractères de la chaîne étaient réduits sous forme canonique et regroupés en unités de comparaison. Chaque unité de comparaison se voit attribuer plusieurs poids correspondant à plusieurs niveaux de comparaison. Les poids des unités de comparaison sont des éléments d'ensembles ordonnés (dans ce cas, des nombres entiers) qui peuvent être comparés plus ou moins. Sens spécial IGNORÉ (0x0) signifie qu'au niveau de comparaison correspondant, cette unité n'est pas impliquée dans la comparaison. La comparaison des chaînes peut être répétée plusieurs fois, en utilisant les poids des niveaux correspondants. À chaque niveau, les poids des unités de comparaison de deux lignes sont comparés séquentiellement les uns aux autres.

Dans différentes implémentations de l'algorithme pour différentes traditions nationales, les valeurs des coefficients peuvent différer, mais la norme Unicode comprend un tableau de pondération de base - "Tableau des éléments de classement Unicode par défaut" (DUCET). Je voudrais noter que la définition de la variable LC_COLLER est en fait une indication de la sélection du tableau de poids dans la fonction de comparaison de chaînes.

Coefficients de pondération DUCET disposé comme suit :

au premier niveau, toutes les lettres sont réduites à la même casse, les signes diacritiques sont supprimés, les signes de ponctuation (pas tous) sont ignorés ;
au deuxième niveau, seuls les signes diacritiques sont pris en compte ;
au troisième niveau, seul le cas est pris en compte ;
au quatrième niveau, seuls les signes de ponctuation sont pris en compte.

La comparaison s'effectue en plusieurs passes : d'abord, les coefficients du premier niveau sont comparés ; si les poids coïncident, alors une comparaison répétée avec les poids de deuxième niveau est effectuée ; puis peut-être un troisième et un quatrième.

La comparaison se termine lorsque les lignes contiennent des unités de comparaison correspondantes avec des poids différents. Les lignes qui ont le même poids aux quatre niveaux sont considérées comme égales les unes aux autres.

Cet algorithme (avec un tas de détails techniques supplémentaires) a donné le nom au rapport n°10 - "Algorithme de classement Unicode" (UCA).

C'est là que le comportement de tri de notre exemple devient un peu plus clair. Ce serait bien de le comparer avec le standard Unicode.

Pour tester les implémentations UCA il y a un spécial тест, en utilisant fichier de poids, mettant en œuvre DUCET. Vous pouvez trouver toutes sortes de choses amusantes dans le fichier des balances. Par exemple, il y a l'ordre du mahjong et des dominos européens, ainsi que l'ordre des couleurs dans un jeu de cartes (symbole 1F000 et plus loin). Les combinaisons de cartes sont placées selon les règles du bridge - PCBT, et les cartes de la couleur sont dans la séquence T, 2,3, XNUMX... K.

Vérifier manuellement que les lignes sont correctement triées selon DUCET serait assez fastidieux, mais, heureusement pour nous, il existe un exemple d'implémentation de la bibliothèque pour travailler avec Unicode - "Composants internationaux pour Unicode»(ICU).

Sur le site Internet de cette bibliothèque, développée en IBM, il existe des pages de démonstration, notamment page d'algorithme de comparaison de chaînes. Nous entrons dans nos lignes de test avec les paramètres par défaut et, voilà, nous obtenons un tri russe parfait.

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

D'ailleurs, le site ICU Vous pouvez trouver une clarification de l'algorithme de comparaison lors du traitement des signes de ponctuation. Dans les exemples FAQ sur le classement l'apostrophe et le trait d'union sont ignorés.

Unicode nous a aidé, mais recherchez les raisons d'un comportement étrange sort в Linux/Unix il faudra aller ailleurs.

Tri dans la glibc

Aperçu rapide des codes sources des utilitaires sort de Utilitaires de base GNU a montré que dans l'utilitaire lui-même, la localisation revient à imprimer la valeur actuelle de la variable LC_COLLER lors de l'exécution en mode débogage :

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

Les comparaisons de chaînes sont effectuées à l'aide de la fonction standard marcher, ce qui veut dire que tout ce qui est intéressant est dans la bibliothèque glibc.

Sur wiki projet glibc dédié à la comparaison de chaînes un paragraphe. De ce paragraphe, on peut comprendre que dans glibc le tri est basé sur un algorithme que nous connaissons déjà UCA (L'algorithme de classement Unicode) et/ou à un standard proche de celui-ci ISO 14651 (Ordre et comparaison internationaux des chaînes). Concernant la dernière norme, il est à noter que sur le site standards.iso.org ISO 14651 officiellement déclaré accessible au public, mais le lien correspondant mène vers une page inexistante. Google renvoie plusieurs pages avec des liens vers des sites officiels proposant d'acheter une copie électronique de la norme pour une centaine d'euros, mais sur la troisième ou la quatrième page des résultats de recherche, il y a aussi des liens directs vers PDF. En général, la norme n'est pratiquement pas différente de UCA, mais il est plus ennuyeux à lire car il ne contient pas d'exemples clairs de caractéristiques nationales de tri de chaînes.

Les informations les plus intéressantes sur wiki il y avait un lien vers traqueur de bogues avec une discussion sur l'implémentation de la comparaison de chaînes dans glibc. De la discussion, on peut apprendre que glibc utilisé pour comparer des chaînes ISOtable personnelle Le tableau des modèles communs (CTT), dont l'adresse figure dans la demande A standard ISO 14651. Entre 2000 et 2015, ce tableau en glibc n'avait pas de responsable et était assez différent (du moins en externe) de la version actuelle de la norme. De 2015 à 2018, une adaptation à la nouvelle version de la table a eu lieu, et vous avez désormais la chance de rencontrer dans la vraie vie une nouvelle version de la table (8 CentOS), et vieux (7 CentOS).

Maintenant que nous disposons de toutes les informations sur l'algorithme et les tables auxiliaires, nous pouvons revenir au problème d'origine et comprendre comment trier correctement les chaînes dans la langue russe.

ISO 14651 / 14652

Code source de la table qui nous intéresse CTT sur la plupart des distributions Linux/Unix est dans le catalogue /usr/share/i18n/locales/. Le tableau lui-même est dans le fichier iso14651_t1_common. Alors voici la directive file copier iso14651_t1_common inclus dans le dossier iso14651_t1, qui, à son tour, est inclus dans les fichiers nationaux, y compris en_US и ru_RU. Sur la plupart des distributions Linux/Unix tous les fichiers sources sont inclus dans l'installation de base, mais s'ils ne sont pas présents, vous devrez installer un package supplémentaire depuis la distribution.

Structure du fichier iso14651_t1 peut sembler terriblement verbeux, avec des règles non évidentes pour construire des noms, mais si vous y regardez, tout est assez simple. La structure est décrite dans la norme ISO 14652, dont une copie peut être téléchargée sur le site Internet open-std.org. Une autre description du format de fichier peut être lue dans Caractéristiques POSIX à partir de Groupe Ouvert. Au lieu de lire la norme, vous pouvez étudier le code source de la fonction assembler_lire в glibc/locale/programs/ld-collate.c.

La structure du fichier ressemble à ceci :

Par défaut, le caractère est utilisé comme caractère d'échappement et la fin de la ligne après le caractère # est un commentaire. Les deux symboles peuvent être redéfinis, ce qui est ce qui est fait dans la nouvelle version du tableau :

escape_char /
comment_char %

Le fichier contiendra des jetons au format ou (où x - chiffre hexadécimal). Il s'agit de la représentation hexadécimale des points de code Unicode dans le codage UCS-4 (UTF-32). Tous les autres éléments entre crochets (y compris , et similaires) sont considérées comme de simples constantes de chaîne qui ont peu de signification en dehors du contexte.

Rangée LC_COLLER nous indique que commencent ensuite les données décrivant la comparaison des chaînes.

Tout d'abord, des noms sont spécifiés pour les poids dans le tableau de comparaison et des noms pour les combinaisons de symboles. De manière générale, les deux types de noms appartiennent à deux entités différentes, mais dans le fichier lui-même, ils sont mélangés. Les noms des poids sont précisés par le mot clé assemblage-symbole (caractère de comparaison) car lors de la comparaison, les caractères Unicode qui ont les mêmes poids seront considérés comme des caractères équivalents.

La longueur totale de la section dans la révision actuelle du fichier est d'environ 900 lignes. J'ai tiré des exemples de plusieurs endroits pour montrer le caractère arbitraire des noms et plusieurs types de syntaxe.

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

symbole de rassemblement enregistre une chaîne OSMANYA dans le tableau des noms de balances
symbole de rassemblement .. enregistre une séquence de noms constituée d'un préfixe S et suffixe numérique hexadécimal de 1D000 à 1D35F.
FFFF в symbole de rassemblement ressemble à un grand entier non signé en hexadécimal, mais c'est juste un nom qui pourrait ressembler à
nom signifie point de code dans l'encodage UCS-4
élément de collationnement depuis " " enregistre un nouveau nom pour une paire de points Unicode.

Une fois les noms des poids définis, les poids réels sont précisés. Puisque seules les relations supérieures à inférieures comptent en comparaison, les pondérations sont déterminées par une simple séquence de noms de liste. Les poids « plus légers » sont répertoriés en premier, puis les poids « plus lourds ». Permettez-moi de vous rappeler que chaque caractère Unicode se voit attribuer quatre poids différents. Ici, ils sont combinés en une seule séquence ordonnée. En théorie, n'importe quel nom symbolique pourrait être utilisé à n'importe lequel des quatre niveaux, mais les commentaires indiquent que les développeurs séparent mentalement les noms en niveaux.

% 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

Enfin, le tableau des poids réels.

La section des poids est entourée de lignes de mots-clés commande_début и fin de commande. Options supplémentaires commande_début déterminer dans quelle direction les lignes sont analysées à chaque niveau de comparaison. Le paramètre par défaut est :. Le corps de la section est constitué de lignes contenant le code du symbole et ses quatre poids. Le code du caractère peut être représenté par le caractère lui-même, un point de code ou un nom symbolique défini précédemment. Des poids peuvent également être attribués aux noms symboliques, aux points de code ou aux symboles eux-mêmes. Si des points de code ou des caractères sont utilisés, leur poids est le même que la valeur numérique du point de code (position dans la table Unicode). Les caractères non spécifiés explicitement (si je comprends bien) sont considérés comme attribués au tableau avec un poids principal qui correspond à la position dans le tableau Unicode. Valeur de poids spéciale IGNORER signifie que le symbole est ignoré au niveau de comparaison approprié.

Pour démontrer la structure des échelles, j'ai choisi trois fragments assez évidents :

des personnages complètement ignorés
symboles équivalents au chiffre trois dans les deux premiers niveaux
le début de l'alphabet cyrillique, qui ne contient pas de signes diacritiques, et est donc trié principalement par premier et troisième niveaux.

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

Vous pouvez maintenant revenir au tri des exemples depuis le début de l'article. L'embuscade se situe dans cette partie du tableau des poids :

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

On peut voir que dans ce tableau les signes de ponctuation du tableau ASCII (espace compris) est presque toujours ignoré lors de la comparaison de chaînes. Les seules exceptions sont les lignes qui correspondent partout, à l'exception des signes de ponctuation trouvés aux positions correspondantes. Les lignes de mon exemple (après tri) pour l'algorithme de comparaison ressemblent à ceci :

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

Considérant que dans le tableau des échelles, les majuscules en russe viennent après les lettres minuscules (au troisième niveau plus lourd que ), le tri semble tout à fait correct.

Lors de la définition d'une variable LC_COLLATE=C une table spéciale est chargée qui spécifie une comparaison octet par octet

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

Puisque dans Unicode le point de code Ё précède A, les chaînes sont triées en conséquence.

Tableaux texte et binaires

Évidemment, la comparaison de chaînes est une opération extrêmement courante, et l'analyse de tables CTT une procédure assez coûteuse. Pour optimiser l'accès à la table, celle-ci est compilée sous forme binaire avec la commande localdef.

Équipe localdef accepte en paramètres un fichier avec un tableau des caractéristiques nationales (option -i), dans lequel tous les caractères sont représentés par des points Unicode, et un fichier de correspondance entre les points Unicode et les caractères d'un encodage spécifique (option -f). À la suite du travail, des fichiers binaires sont créés pour la locale avec le nom spécifié dans le dernier paramètre.

GlibcComment prend en charge deux formats de fichiers binaires : « traditionnel » et « moderne ».

Le format traditionnel signifie que le nom de la locale est le nom du sous-répertoire dans /usr/lib/locale/. Ce sous-répertoire stocke les fichiers binaires LC_COLLER, LC_CTYPE, LC_TIME et ainsi de suite. Déposer LC_IDENTIFICATION contient le nom formel de la locale (qui peut être différent du nom du répertoire) et des commentaires.

Le format moderne implique de stocker tous les paramètres régionaux dans une seule archive /usr/lib/locale/locale-archive, qui est mappé à la mémoire virtuelle de tous les processus utilisant glibc. Le nom des paramètres régionaux au format moderne est soumis à une certaine canonisation - seuls les chiffres et les lettres réduits en minuscules restent dans les noms d'encodage. Donc ru_RU.KOI8-R, sera enregistré sous ru_RU.koi8r.

Les fichiers d'entrée sont recherchés dans le répertoire courant, ainsi que dans les répertoires /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ pour les fichiers CTT et encodage des fichiers, respectivement.

Par exemple, la commande

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

va compiler le fichier /usr/share/i18n/locales/ru_RU en utilisant le fichier d'encodage /usr/share/i18n/charmaps/MAC-CYRILLIC.gz et enregistrez le résultat dans /usr/lib/locale/locale-archive sous le nom ru_RU.maccyrillic

Si vous définissez la variable LANG = en_US.UTF-8 que glibc recherchera les binaires de paramètres régionaux dans la séquence suivante de fichiers et de répertoires :

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

Si un paramètre régional apparaît à la fois dans des formats traditionnels et modernes, la priorité est alors donnée au format moderne.

Vous pouvez visualiser la liste des locales compilées avec la commande locale -a.

Préparer votre tableau comparatif

Désormais, armé de ces connaissances, vous pouvez créer votre propre tableau de comparaison de chaînes idéal. Ce tableau doit comparer correctement les lettres russes, y compris la lettre Ё, et en même temps prendre en compte les signes de ponctuation conformément au tableau ASCII.

Le processus de préparation de votre propre table de tri comprend deux étapes : éditer la table des poids et la compiler sous forme binaire avec la commande localdef.

Pour que le tableau comparatif puisse être ajusté avec des coûts d'édition minimes, au format ISO 14652 Des sections permettant d'ajuster les poids d'une table existante sont fournies. La section commence par un mot-clé réorganiser après et indiquant la position après laquelle le remplacement est effectué. La section se termine par la ligne fin de commande. S'il est nécessaire de corriger plusieurs sections du tableau, une section est créée pour chacune de ces sections.

J'ai copié les nouvelles versions des fichiers iso14651_t1_common и ru_RU du référentiel glibc dans mon répertoire personnel ~/.local/share/i18n/locales/ et j'ai légèrement modifié la section LC_COLLER в ru_RU. Les nouvelles versions des fichiers sont entièrement compatibles avec ma version glibc. Si vous souhaitez utiliser des versions plus anciennes de fichiers, vous devrez modifier les noms symboliques et l'endroit où commence le remplacement dans le tableau.

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

En fait, il faudrait changer les champs dans LC_IDENTIFICATION pour qu'ils pointent vers la locale ru_MY, mais dans mon exemple, cela n'était pas obligatoire, car j'ai exclu l'archive de la recherche de paramètres régionaux archives locales.

Que localdef travaillé avec des fichiers dans mon dossier via une variable I18NPATH Vous pouvez ajouter un répertoire supplémentaire pour rechercher les fichiers d'entrée, et le répertoire dans lequel enregistrer les fichiers binaires peut être spécifié sous forme de chemin avec des barres obliques :

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

POSIX suppose que dans LANGUE vous pouvez écrire des chemins absolus vers des répertoires contenant des fichiers de paramètres régionaux, en commençant par une barre oblique, mais glibc в Linux/Unix tous les chemins sont comptés à partir du répertoire de base, qui peut être remplacé via une variable CHEMIN LOCP. Après l'installation LOCPATH=~/.local/lib/locale/ tous les fichiers liés à la localisation seront recherchés uniquement dans mon dossier. Archive des locales avec la variable définie CHEMIN LOCP ignoré.

Voici le test décisif :

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

Hourra! Nous l'avons fait!

Certaines erreurs

J'ai déjà répondu aux questions posées au début sur le tri des chaînes, mais il reste encore quelques questions sur les erreurs - visibles et invisibles.

Revenons au problème initial.

Et le programme sort et programme rejoindre utiliser les mêmes fonctions de comparaison de chaînes que celles de glibc. Comment est-il arrivé que rejoindre a donné une erreur de tri sur les lignes triées par la commande sort dans les paramètres régionaux fr_US.UTF-8? La réponse est simple : sort compare la chaîne entière, et rejoindre compare uniquement la clé, qui par défaut est le début de la chaîne jusqu'au premier caractère d'espacement. Dans mon exemple, cela entraînait un message d'erreur car le tri des premiers mots des lignes ne correspondait pas au tri des lignes complètes.

Lieu "C" garantit que dans les chaînes triées, les sous-chaînes initiales jusqu'au premier espace seront également triées, mais cela ne fait que masquer l'erreur. Il est possible de sélectionner des données (personnes portant le même nom, mais des prénoms différents) qui, sans le message d'erreur, donneraient un résultat de fusion de fichiers incorrect. Si nous voulons rejoindre Si vous fusionnez les lignes du fichier par nom complet, la manière correcte serait de spécifier explicitement le séparateur de champ et de trier par champ clé, et non par la ligne entière. Dans ce cas, la fusion se déroulera correctement et il n'y aura aucune erreur dans aucun paramètre régional :

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

Exemple d'exécution réussie lors de l'encodage CP1251 contient une autre erreur. Le fait est que dans toutes les distributions que je connais Linux/Unix les packages ne disposent pas de paramètres régionaux compilés ru_RU.CP1251. Si les paramètres régionaux compilés ne sont pas trouvés, alors sort utilise silencieusement une comparaison octet par octet, ce que nous avons observé.

À propos, il existe un autre petit problème lié à l'inaccessibilité des locales compilées. Équipe LOCPATH=/tmp locale -a donnera une liste de tous les paramètres régionaux dans archives locales, mais avec la variable définie CHEMIN LOCP pour tous les programmes (y compris les plus local) ces paramètres régionaux ne seront pas disponibles.

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

Conclusion

Si vous êtes un programmeur habitué à penser que les chaînes sont un ensemble d'octets, alors votre choix LC_COLLATE=C.

Si vous êtes un linguiste ou un compilateur de dictionnaires, il est préférable de compiler dans vos paramètres régionaux.

Si vous êtes un simple utilisateur, il vous suffit de vous habituer au fait que la commande ls -a génère des fichiers commençant par un point mélangés à des fichiers commençant par une lettre, et Commandant de minuit, qui utilise ses fonctions internes pour trier les noms, place les fichiers commençant par un point au début de la liste.