Introduction

Tout a commencé par un script court, censé combiner les informations sur les adresses e-mail des employés, obtenues à partir de la liste des utilisateurs de la newsletter, avec les postes des employés, obtenus à partir de la base des ressources humaines. Les deux listes ont été exportées dans des fichiers texte en codage Unicode UTF-8 et sauvegardées avec des fins de ligne unixiennes.

Contenu mail.txt

Ivanov Andreï;ia@example.com

Contenu buhg.txt

Ivanova Alla;peintre
Yelkina Ella;grutière
Ivanov Andreï;ouvrier
Abakanov Mikhaïl;peintre

Pour combiner, les fichiers ont été triés avec la commande unixienne sort et donnés en entrée à un programme unixien joindre, qui s'est terminé 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: n'est pas trié: Ivanov Andreï;ouvrier

Un aperçu du résultat du tri a montré qu'en général le tri était correct, mais en cas de coïncidences entre les noms masculins et féminins, les féminins sont placés avant les masculins :

$> sort buhg.txt
Abakanov Mikhaïl;peintre
Yelkina Ella;grutière
Ivanova Alla;peintre
Ivanov Andreï;ouvrier

Cela ressemble à un bug de tri en Unicode ou à une manifestation du féminisme dans l'algorithme de tri. La première explication est bien sûr plus plausible.

Mettons cela de côté pour l'instant joindre et concentrons-nous sur sort. Tentons de résoudre le problème par tâtonnements. Pour commencer, changeons la locale de en_US sur ru_RU. Pour le tri, il suffirait de définir la variable d'environnement LC_COLLATE, mais nous n'allons pas faire les choses à moitié :

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhaïl;peintre
Yelkina Ella;grutière
Ivanova Alla;peintre
Ivanov Andreï;ouvrier

Rien n'a changé.

Essayons de re-coder les fichiers en une seule octet :

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

Encore rien n'a changé.

Il n'y a rien à faire, il va falloir chercher une solution sur Internet. Rien de particulier sur les noms russes, mais il y a des questions sur d'autres bizarreries du tri. Par exemple, voici un tel problème : unix sort treats ‘-‘ (dash) characters as invisible. En résumé, les chaînes "a-b", "aa", "ac" sont triées comme "aa", "a-b", "ac".

La réponse est toujours la même : utilisez la locale programmer "C" et vous serez heureux. Essayons :

$> LANG=C sort buhg.txt
Yelkina Ella;grutière
Abakanov Mikhaïl;peintre
Ivanov Andreï;ouvrier
Ivanova Alla;avocate

Il y a quelque chose qui a changé. Les Ivanov se sont rangés dans le bon ordre, mais Yelkina a disparu quelque part. Revenons à la tâche initiale :

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

Ça a fonctionné sans erreurs, tout comme l'a promis Internet. Et ce, malgré Yolkine à la première ligne.

Le problème semble résolu, mais pour être sûr, essayons une autre codage en russe — celui de Windows. CP1251:

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

Le résultat du tri, étrangement, coïncidera avec la locale. "C", et tout l'exemple, en conséquence, se déroule sans erreurs. C'est quelque chose de mystique.

Je n'aime pas la mystique en programmation, car elle dissimule généralement des erreurs. Je vais devoir m'occuper sérieusement de la façon dont les choses fonctionnent. sort et de ce à quoi cela influence. LC_COLLATE .

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

pourquoi les noms de famille des femmes n'étaient pas triés correctement.
pourquoi LANG=ru_RU.CP1251 s'est avéré équivalent. LANG=C
pourquoi il y a sort et joindre des représentations différentes de l'ordre des chaînes triées.
pourquoi il y a des erreurs dans tous mes exemples.
enfin, comment trier les chaînes selon ses propres goûts.

Le tri en Unicode.

Premier arrêt, le rapport technique n° 10 intitulé algorithme de collation Unicode. sur le site unicode.org. Le rapport contient de nombreux détails techniques, donc je vais me permettre de donner un résumé des idées principales.

Collation — "comparaison" des chaînes — est la base de tout algorithme de tri. Les algorithmes eux-mêmes peuvent varier ("bulles", "fusion", "rapide"), mais tous utilisent la comparaison de paires de chaînes pour déterminer l'ordre dans lequel elles apparaissent.

Le tri des chaînes en langue naturelle est un problème assez complexe. Même dans les encodages à un octet les plus simples, l'ordre des lettres dans un alphabet, même s'il diffère quelque peu de l'alphabet latin anglais, ne coïncide déjà plus avec l'ordre des valeurs numériques par lesquelles ces lettres sont encodées. Par exemple, dans l'alphabet allemand, la lettre Ö se situe entre O et redicted Frame), et dans l'encodage CP850 elle se trouve entre ÿ et Ü..

On peut essayer de s'abstraire de l'encodage particulier et d'envisager des "lettres idéales" qui sont disposées dans un certain ordre, comme cela est fait en Unicode. Les encodages UTF8, UTF16 ou un octet KOI8-R (si un sous-ensemble limité d'Unicode est nécessaire) donneront différentes représentations numériques des lettres, mais feront référence aux mêmes éléments de la table de base.

Il s'avère que même en construisant une table de caractères à partir de zéro, nous ne pourrons pas établir un ordre universel pour les caractères. Dans différents alphabets nationaux utilisant les mêmes lettres, l'ordre de ces lettres peut varier. Par exemple, en français, Æ sera considéré comme une ligature et trié comme une chaîne. AEDans la langue norvégienne, Æ sera une lettre à part, qui se place après Z. D'ailleurs, en plus des ligatures comme Æ il existe des lettres écrites avec plusieurs symboles. Ainsi, dans l'alphabet tchèque, il y a la lettre Ch, qui se situe entre H et I.

En plus des différences dans les alphabets, il existe d'autres traditions nationales qui influencent le tri. En particulier, une question se pose : dans quel ordre doivent apparaître dans un dictionnaire les mots composés de lettres majuscules et minuscules ? De plus, la manière dont la ponctuation est utilisée peut également influencer le tri. En espagnol, un point d'interrogation inversé est placé au début d'une phrase interrogative (¿Te gusta la música ?). Dans ce cas, il est clair que les phrases interrogatives ne doivent pas être regroupées dans un cluster séparé en dehors de l'alphabet, mais comment trier les chaînes avec d'autres signes de ponctuation ?

Je ne vais pas m'attarder sur le tri des chaînes dans des langues très différentes des européennes. Je noterai que dans les langues ayant une orientation d'écriture de droite à gauche ou de haut en bas, les symboles dans les chaînes sont probablement stockés dans l'ordre de lecture, et même dans des écritures non alphabétiques, il existe des moyens propres d'organiser les chaînes par caractère. Par exemple, les idéogrammes peuvent être classés selon leur tracé (les clés des idéogrammes chinois) ou selon leur prononciation. Je ne sais pas comment les émojis devraient être classés, mais il doit y avoir quelque chose à en dire.

Sur la base des particularités énumérées ci-dessus, les principales exigences comparatives pour les chaînes basées sur les tables Unicode ont été formulées :

la comparaison des chaînes ne dépend pas de la position des caractères dans le tableau de codes ;
les séquences de caractères formant un seul caractère sont raménées à leur forme canonique (A + un cercle supérieur est le même que Å);
lors de la comparaison de chaînes, le caractère est considéré dans le contexte de la chaîne et, si nécessaire, est combiné avec des voisines en une seule unité de comparaison (Ch en tchèque) ou est divisé en plusieurs (Æ en français);
Toutes les particularités nationales (alphabet, majuscules/minuscules, ponctuation, ordre des types d'écriture) doivent être configurées jusqu'à la désignation manuelle de l'ordre (emoji);
La comparaison est importante non seulement pour le tri, mais aussi dans de nombreux autres contextes, par exemple pour définir des plages de lignes (substitution {A... я} dans bash);
la comparaison doit être effectuée suffisamment rapidement.

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

l'algorithme de comparaison ne doit pas nécessiter un ensemble distinct de caractères pour chaque langue (les langues russe et ukrainienne partagent la plupart des caractères cyrilliques);
la comparaison ne doit pas se fonder 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 une même chaîne peut avoir des poids différents dans différents contextes culturels;
les poids des chaînes peuvent changer lors de fusions ou de divisions (de x < y il ne s'ensuit pas que xz < yz);
des chaînes différentes ayant des poids identiques sont considérées comme égales du point de vue de l'algorithme de tri. L'introduction d'un ordre supplémentaire pour ces chaînes est possible, mais cela pourrait dégrader les performances;
lors de tris répétés, les chaînes ayant des poids identiques peuvent échanger leurs places. La stabilité est une propriété d'un algorithme de tri particulier, et non d'un algorithme de comparaison de chaînes (voir point précédent);
les règles de tri peuvent changer au fil du temps à mesure que les traditions culturelles se précisent/changent.

Il est également stipulé que l'algorithme de comparaison ne connaît rien de la sémantique des chaînes traitées. Ainsi, les chaînes composées uniquement de chiffres ne doivent pas être comparées comme des nombres, et dans les listes de noms anglais, l'article ne doit pas être supprimé (Beatles, The).

Pour satisfaire toutes les exigences énoncées, un algorithme de tri en plusieurs niveaux (quatre niveaux en fait) est proposé.

Au préalable, les caractères de la chaîne sont mis sous une forme canonique et regroupés en unités de comparaison. À chaque unité de comparaison sont attribués plusieurs poids, correspondant à différents niveaux de comparaison. Les poids des unités de comparaison sont des éléments d'ensembles ordonnés (dans ce cas, des entiers), qui peuvent être comparés entre eux. Une valeur spéciale IGNORED (0x0) signifie qu'à ce niveau de comparaison, cette unité ne participe pas à 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 des deux chaînes sont comparés les uns aux autres.

Dans différentes réalisations de l'algorithme pour différentes traditions nationales, les valeurs des coefficients peuvent différer, mais le standard Unicode comprend un tableau de poids de base - "Table des éléments de collation Unicode par défaut" (DUCET). Je tiens à souligner que l'établissement de la variable LC_COLLATE est en fait une indication du choix du tableau de poids dans la fonction de comparaison de chaînes.

Les coefficients de poids DUCET sont organisés comme suit :

au premier niveau, toutes les lettres sont mises en minuscule, les signes diacritiques sont ignorés, et la plupart des signes de ponctuation sont ignorés;
au deuxième niveau, seuls les signes diacritiques sont pris en compte;
au troisième niveau, seul le registre est pris en compte;
au quatrième niveau, seuls les signes de ponctuation sont pris en compte.

La comparaison se fait en plusieurs passes : d'abord, les coefficients du premier niveau sont comparés ; si les poids correspondent, une comparaison répétée est effectuée avec les poids du deuxième niveau ; puis, éventuellement, ceux du troisième et du quatrième.

La comparaison se termine lorsque des unités de comparaison correspondantes avec des poids différents se trouvent dans les chaînes. Les chaînes ayant des poids égaux à tous les quatre niveaux sont considérées comme égales entre elles.

Cet algorithme (avec plein de détails techniques supplémentaires) a donné son nom au rapport n° 10 - "Algorithme de collation Unicode" (UCA).

À ce stade, le comportement de tri de notre exemple devient un peu plus clair. Il serait bon de le comparer au standard Unicode.

Pour tester les réalisations UCA il existe un test, utilisant un fichier de poids, implémentant DUCET. Dans le fichier de poids, on peut trouver différentes curiosités. Par exemple, il y a l'ordre des tuiles de Mahjong et du domino européen, ainsi que l'ordre des couleurs dans un jeu de cartes (symbole 1F000 et au-delà). Les couleurs des cartes sont disposées selon les règles du bridge - PCHBT, et les cartes de chaque couleur sont dans l'ordre T,2,3… K.

Une vérification manuelle de la validité du tri des chaînes selon DUCET aurait été assez fatigante, mais heureusement pour nous, il existe une réalisation exemplaire d'une bibliothèque pour travailler avec Unicode - "International Components for Unicode" (ICU).

Sur le site de cette bibliothèque, développée à IBM, il y a des pages de démonstration, y compris une page d'algorithme de comparaison de chaînes. Nous introduisons nos chaînes de test avec les paramètres par défaut et, oh miracle, nous obtenons un tri russe parfait.

Abakanov Mikhaïl;peintre
Yolkina Ella;grutière
Ivanov Andreï;ouvrier
Ivanova Alla;avocat

Au fait, sur le site ICU on peut trouver des précisions sur le fonctionnement de l'algorithme de comparaison lors du traitement des signes de ponctuation. Dans les exemples Collation FAQ l'apostrophe et le trait d'union sont ignorés.

Unicode nous a aidés, mais il faudra chercher les raisons du comportement étrange sort dans Linux ailleurs.

Tri dans glibc

Un aperçu rapide du code source de l'outil sort de GNU Core Utils a montré que dans l'outil, la localisation se limite à l'impression de la valeur actuelle de la variable LC_COLLATE lors de l'exécution en mode débogage :

$ sort --debug buhg.txt > buhg.srt
sort: utilisant les règles de tri ‘en_US.UTF8’

La comparaison de chaînes est effectuée par la fonction standard strcoll, donc tout ce qui est intéressant se trouve dans la bibliothèque glibc.

Sur wiki du projet glibc qui est dédiée à la comparaison de chaînes un paragraphe. De ce paragraphe, on peut comprendre que dans glibc le tri est basé sur l'algorithme déjà connu UCA (The Unicode collation algorithm) et/ou sur la norme proche ISO 14651 (Ordonnancement et comparaison des chaînes internationales). En ce qui concerne la dernière norme, il convient de noter qu'elle est annoncée officiellement comme publique sur le site standards.iso.org ISO 14651 , mais le lien correspondant mène à une page inexistante. Google donne plusieurs pages avec des liens vers des sites officiels qui proposent d'acheter une copie électronique de la norme pour une centaine d'euros, mais à la troisième ou quatrième page des résultats de recherche, vous trouverez aussi des liens directs vers PDF. En général, la norme ne diffère pratiquement pas de UCA, mais est plus ennuyeuse à lire car elle ne contient pas d'exemples frappants des particularités nationales de l'ordre des chaînes.

L'information la plus intéressante sur wiki s'est révélée être un lien vers le tracker de bogues avec des discussions sur la mise en œuvre de la comparaison de chaînes dans glibc. D'une discussion, on peut apprendre qu'à glibc la comparaison de chaînes utilise ISOun tableau The Common Template Table (CTT), dont l'adresse peut être trouvée dans l'annexe A de la norme ISO 14651. Entre 2000 et 2015, ce tableau a glibc n'avait pas de mainteneur et différait suffisamment (du moins visuellement) de la version actuelle de la norme. De 2015 à 2018, une adaptation à la nouvelle version du tableau a eu lieu et à l'heure actuelle, vous avez la chance de rencontrer dans la vie réelle à la fois la nouvelle version du tableau (CentOS 8), et l'ancienne (CentOS 7).

Maintenant que nous avons toutes les informations sur l'algorithme et les tableaux auxiliaires, nous pouvons revenir à la problématique initiale et comprendre comment trier correctement les lignes dans la locale russe.

ISO 14651/14652

Le code source du tableau qui nous intéresse CTT se trouve dans la plupart des distributions Linux dans le répertoire /usr/share/i18n/locales/. Le tableau lui-même se trouve dans le fichier iso14651_t1_common. Ce fichier est ensuite inclus dans le fichier copy iso14651_t1_common qui, à son tour, est inclus dans les fichiers nationaux, y compris dans . Dans la plupart des distributionstous les fichiers sources sont inclus dans l'installation de base, mais s'ils ne sont pas présents, il faudra installer un paquet supplémentaire de la distribution. en_US et ru_RUpeut sembler horriblement verbeux, avec des règles de construction de noms peu évidentes, mais une fois que vous comprenez, tout est assez simple. La structure est décrite dans la norme Linux ISO 14652

Structure du fichier . Dans la plupart des distributions , dont une copie peut être téléchargée sur le site open-std.org. Une autre description du format de fichier peut être lue dans les spécificationsOpenGroup . En alternative à la lecture de la norme, vous pouvez étudier le code source de la fonction POSIX à partir de collate_readglibc/locale/programs/ld-collate.c La structure du fichier est la suivante : dans 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 caractères peuvent être redéfinis, ce qui a été fait dans la nouvelle version du tableau :.

escape_char / comment_char %

Dans le fichier, vous rencontrerez des jetons au format

escape_char /\ncomment_char %

Le fichier contiendra des jetons au format (où ou est un chiffre hexadécimal). Cette représentation hexadécimale des points de code Unicode est en codage UCS-4 x UTF-32 ). Tous les autres éléments entre crochets (y compris (UTF-32). Tous les autres éléments entre crochets (y compris et similaires), sont considérés comme des constantes de chaîne simples, n'ayant pas de signification particulière en dehors du contexte., nous indique que les données décrivant la comparaison des chaînes commencent. Tout d'abord, des noms sont définis pour les poids dans le tableau de comparaison et des noms pour les combinaisons de caractères. En général, deux types de noms appartiennent à deux entités différentes, mais dans un fichier réel, ils sont mélangés. Les noms des poids sont définis par le mot-clé

Chaîne LC_COLLATE collating-symbol

Tout d'abord, les noms des poids dans le tableau de comparaison et les noms des combinaisons de caractères sont définis. En général, deux types de noms appartiennent à deux entités différentes, mais dans le fichier réel, ils sont mélangés. Les noms des poids sont définis par le mot clé collating-symbol (symbole de comparaison), car lors de la comparaison, les caractères Unicode ayant le même 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 extrait des exemples de plusieurs endroits pour montrer l'arbitraire des noms et quelques types de syntaxe.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Valeur de symbole maximale garantie. Gardez à la fin de cette liste
...
collating-element  à partir de ""
collating-element  à partir de ""

collating-symbol enregistre une chaîne OSMANYA dans le tableau des noms de poids
collating-symbol .. enregistre une séquence de noms, composée d'un préfixe S et d'un suffixe numérique hexadécimal allant de 1D000 à 1D35F.
FFFF dans collating-symbol apparaît comme un grand entier non signé en notation hexadécimale, mais <SFFFF> c'est juste un nom qui pourrait ressembler à <VERYBIGVAL>
nom <U0413> représente un point de code dans l'encodage ). Tous les autres éléments entre crochets (y compris
collating-element à partir de "" enregistre un nouveau nom pour une paire de points Unicode.

Une fois que les noms de poids sont définis, les poids eux-mêmes sont alors assignés. Étant donné que seules les relations de plus grand-moins sont significatives lors de la comparaison, les poids sont déterminés par une simple séquence d'énumération des noms. Les poids 'légers' sont énumérés en premier, suivis des poids 'lourds'. Rappelons que chaque caractère Unicode se voit attribuer quatre poids différents. Ils sont ici regroupés dans une seule séquence ordonnée. Théoriquement, n'importe quel nom symbolique peut être utilisé à n'importe quel niveau des quatre niveaux, mais les commentaires suggèrent que les développeurs divisent mentalement les noms par niveaux.

% Attributions de poids symboliques

% Attributions de poids de troisième niveau




...
% Attributions de poids de deuxième niveau

 % COMBINING LOW LINE
 % COMBINING COMMA ABOVE
 % COMBINING REVERSED COMMA ABOVE
...
% Attributions de poids de premier niveau
 % TABULATION HORIZONTALE
 % RETOUR À LA LIGNE
 % TABULATION VERTICALE
...
 % LETTRE MINUSCULE CYRILIQUE DE
 % LETTRE MINUSCULE CYRILIQUE KOMI DE
 % LETTRE MINUSCULE CYRILIQUE DJE
 % LETTRE MINUSCULE CYRILIQUE KOMI DJE
 % LETTRE MINUSCULE CYRILIQUE GJE
 % LETTRE MINUSCULE CYRILIQUE ZE AVEC DESCENDEUR
 % LETTRE MINUSCULE CYRILIQUE IE
 % LETTRE MINUSCULE CYRILIQUE IE AVEC BRÈVE
 % LETTRE MINUSCULE CYRILIQUE IE UKRAINIENNE
 % LETTRE MINUSCULE CYRILIQUE ZHE

Enfin, le tableau des poids.

La section des poids est encapsulée dans des lignes avec des mots-clés order_start et order_end. Des paramètres supplémentaires order_start déterminent dans quelle direction les lignes sont parcourues à chaque niveau de comparaison. Par défaut, le paramètre forward. Le corps de la section est composé de lignes contenant le code du caractère et ses quatre poids. Le code du caractère peut être représenté par le symbole lui-même, le point de code ou un nom symbolique défini auparavant. Les poids peuvent également être spécifiés par des noms symboliques, des points de code ou les symboles eux-mêmes. Si des points de code ou des symboles sont utilisés, leur poids correspond à la valeur numérique du point de code (position dans la table Unicode). Les symboles non spécifiés explicitement (tel que je le comprends) sont considérés comme ayant un poids primaire correspondant à leur position dans la table Unicode. La valeur spéciale du poids IGNORE indique qu'à ce niveau de comparaison, ce caractère est ignoré.

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

les symboles qui sont complètement ignorés
les symboles équivalents au chiffre trois aux deux premiers niveaux
le début de l'alphabet cyrillique, qui ne contient pas de signes diacritiques, et donc se trie principalement selon les premier et troisième niveaux.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (dans 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % DÉBUT DE L'EN-TÊTE (dans 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % DÉBUT DU TEXTE (dans 6429)
...
 ;;; % CHIFFRE TROIS
 ;;; % CHIFFRE TROIS EN LARGEUR PLEINE
 ;;; % CHIFFRE TROIS ENTRE PARENTHÈSES
 ;;; % CHIFFRE TROIS POINT FINAL
 ;;; % CHIFFRE TROIS EN GRAS MATHEMATIQUE
...
 ;;; % LETTRE MINUSCULE CYRILLIQUE A
 ;;; % LETTRE MAJUSCULE CYRILLIQUE A
 ;;; % LETTRE MINUSCULE CYRILLIQUE A AVEC BREVE
 ;;; % LETTRE MINUSCULE CYRILLIQUE A AVEC BREVE
...
 ;;; % LETTRE MINUSCULE CYRILLIQUE BE
 ;;; % LETTRE MAJUSCULE CYRILLIQUE BE
 ;;; % LETTRE MINUSCULE CYRILLIQUE VE
 ;;; % LETTRE MAJUSCULE CYRILLIQUE VE
...
order_end

Il est maintenant possible de revenir à la tri des exemples du début de l'article. Le piège se cache dans cette partie du tableau des poids :

IGNORE;IGNORE;IGNORE; % ESPACE
 IGNORE;IGNORE;IGNORE; % POINT D'EXCLAMATION
 IGNORE;IGNORE;IGNORE; % GUILLEMET
...

Il est évident que dans ce tableau, la ponctuation est extraite du tableau ASCII (y compris l'espace) lors de la comparaison des chaînes, elle est presque toujours ignorée. L'exception concerne uniquement les chaînes qui correspondent complètement, à l'exception de la ponctuation apparaissant aux mêmes positions. Les chaînes de mon exemple (après le tri) pour l'algorithme de comparaison apparaissent comme suit :

AbakanovMikhailPeintre
YolkinaEllaCrane
IvanovaAllaPeintre
IvanovAndreiSoudard

Étant donné que dans le tableau des poids, les majuscules en russe viennent après les minuscules (au troisième niveau <CAP> plus lourd que <MIN>), le tri apparaît absolument correct.

Lors de la définition de la variable LC_COLLATE=C une table spéciale est chargée, laquelle définit la 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'
};

Étant donné que dans Unicode, le point de code Ё se situe avant A, les chaînes sont triées en conséquence.

Tables textuelles et binaires

Il est évident que la comparaison de chaînes est une opération extrêmement fréquente, et que l'analyse de la table CTT est une procédure plutôt coûteuse. Pour optimiser l'accès à la table, elle est compilée en format binaire par la commande localedef.

Commande localedef prend en paramètre un fichier avec la table des spécificités nationales (option -i), dans lequel tous les symboles sont représentés par des points Unicode, et un fichier de correspondance entre les points Unicode et les symboles d'un encodage spécifique (option -f). À l'issue du traitement, des fichiers binaires pour la locale sont créés, portant le nom spécifié dans le dernier paramètre.

Glibc supporte deux formats de fichiers binaires : 'traditionnel' et 'moderne'.

Le format traditionnel signifie que le nom de la locale est le nom d'un sous-répertoire dans /usr/lib/locale/. Dans ce sous-répertoire se trouvent les fichiers binaires LC_COLLATE, LC_CTYPE, LC_TIME etc. Le fichier LC_IDENTIFICATION contient le nom formel de la locale (qui peut différer du nom du répertoire) et des commentaires.

Le format moderne suppose que toutes les locales sont stockées dans une seule archive /usr/lib/locale/locale-archive, qui est mappée dans la mémoire virtuelle de tous les processus utilisant glibcLe nom de la locale au format moderne subit une certaine canonisation — dans les noms d'encodage, seuls les chiffres et les lettres restent, convertis en minuscules. Ainsi, fr_FR.KOI8-R, sera conservé comme fr_FR.koi8r.

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

Par exemple, la commande

localedef -i fr_FR -f MAC-CYRILLIC fr_FR.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 enregistrera le résultat dans /usr/lib/locale/locale-archive sous le nom fr_FR.maccyrillic

Si la variable LANG=en_US.UTF-8 alors glibc elle cherchera les fichiers binaires de locale 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 la locale est présente à la fois dans les formats traditionnel et moderne, la priorité est donnée au moderne.

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

Préparation de votre propre table de comparaison

Maintenant, armé de vos connaissances, vous pouvez créer votre propre table de comparaison idéale. Cette table doit comparer correctement les lettres russes, y compris la lettre Ё, tout en tenant compte des signes de ponctuation selon le tableau ASCII.

Le processus de préparation de votre propre table de tri se compose de deux étapes : l'édition de la table des poids et sa compilation en forme binaire avec la commande localedef.

Pour que la table de comparaison puisse être ajustée avec un minimum de modifications, le format open-std.org prévoit des sections d'ajustement des poids de la table existante. La section commence par le mot clé reorder-after et l'indication de la position après laquelle le remplacement est effectué. La section se termine par la ligne reorder-end. S'il est nécessaire de corriger plusieurs parties de la table, une section est créée pour chaque partie.

J'ai copié de nouvelles versions des fichiers iso14651_t1_common et ru_RU depuis le dépôt glibc dans mon répertoire personnel ~/.local/share/i18n/locales/ et j'ai légèrement modifié la section LC_COLLATE dans ru_RU. Les nouvelles versions des fichiers sont entièrement compatibles avec ma version glibc. Si vous souhaitez utiliser les anciennes versions des fichiers, vous devrez changer les noms symboliques et l'emplacement à partir duquel le remplacement commence dans la table.

LC_COLLATE
% Copier le modèle d'ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % ESPACE
 ;;; % POINT D'EXCLAMATION
 ;;; % GUILLEMET
...
 ;;; % ACCOLADE DROITE
 ;;; % TILDE
reorder-end
END LC_COLLATE

En fait, il aurait fallu changer les champs dans LC_IDENTIFICATION pour qu'ils pointent vers la locale ru_MY, mais dans mon exemple cela n'était pas nécessaire, car j'ai exclu de la recherche la locale archive locale-archive.

Pour que localedef travaillait avec les fichiers dans mon dossier via la variable I18NPATH on peut ajouter un répertoire supplémentaire pour rechercher les fichiers d'entrée, et le répertoire pour enregistrer les fichiers binaires peut être indiqué comme un chemin avec des slashes :

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

POSIX sous-entend que LANG on peut écrire des chemins absolus vers des répertoires contenant des fichiers de locale, commençant par un slash, mais glibc dans Linux tous les chemins sont considérés par rapport au répertoire de base, qui peut être redéfini via la variable LOCPATH. Après avoir défini LOCPATH=~/.local/lib/locale/ tous les fichiers liés à la localisation seront recherchés uniquement dans mon dossier. L'archive de locales avec la variable définie LOCPATH est ignorée.

Voici le test décisif :

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;peintre
Yolkina Ella;grutière
Ivanov Andrei;serrurier
Ivanova Alla;avocate

Hourra ! Nous l'avons fait !

Travail sur les erreurs

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

Revenons à la tâche initiale.

Et le programme sort et le programme joindre utilisent les mêmes fonctions de comparaison de chaînes de glibc. Comment se fait-il que joindre a produit une erreur de tri sur les chaînes triées par la commande sort dans la locale en_US.UTF-8? Ответ прост: sort compare la chaîne dans son intégralité, tandis que joindre ne compare que la clé, qui par défaut est le début de la chaîne jusqu'au premier espace. Dans mon exemple, cela a conduit à un message d'erreur, car le tri des premiers mots des chaînes ne correspondait pas au tri des chaînes entières.

La locale "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 telles que (des personnes avec le même nom de famille mais des prénoms différents), qui donneraient un résultat incorrect lors de la fusion des fichiers sans message d'erreur. Si nous voulons que joindre fusionne les chaînes des fichiers par nom complet, la bonne méthode serait de spécifier explicitement le séparateur de champs et de trier par le champ clé, plutôt que par la chaîne entière. Dans ce cas, la fusion se déroulera correctement et il n'y aura pas d'erreurs dans aucune locale :

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

Exemple réussi dans l'encodage CP1251 contient une autre erreur. Le fait est que dans toutes les distributions que je connais Linux les paquets manquent de locales compilées ru_RU.CP1251. Si aucune locale compilée n'est trouvée, alors sort elle utilise silencieusement une comparaison au niveau des octets, ce que nous avons observé.

Au fait, il y a un autre petit bug lié à l'indisponibilité des locales compilées. La commande LOCPATH=/tmp locale -a affichera la liste de toutes les locales dans locale-archive, mais avec la variable installée LOCPATH pour tous les programmes (y compris la propre locale) ces locales seront inaccessibles.

$> LOCPATH=/tmp locale -a | grep en_US
locale : Impossible de définir LC_CTYPE sur la locale par défaut : Aucun fichier ou dossier de ce type
locale : Impossible de définir LC_MESSAGES sur la locale par défaut : Aucun fichier ou dossier de ce type
locale : Impossible de définir LC_COLLATE sur la locale par défaut : Aucun fichier ou dossier de ce type
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort : utilisation des règles de tri ‘en_US.UTF-8’

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort : utilisation d'une simple comparaison des octets

Conclusion

Si vous êtes un programmeur qui considère que les chaînes sont un ensemble d'octets, alors votre choix LC_COLLATE=C.

Si vous êtes linguiste ou rédacteur de dictionnaire, il est préférable de compiler votre locale.

Si vous êtes un utilisateur ordinaire, il vous suffit de vous habituer à ce que la commande ls -a produit des fichiers commençant par un point, mélangés avec des fichiers débutant par une lettre, alors que Midnight Commander, qui utilise ses propres fonctions internes pour trier les noms, met les fichiers commençant par un point en tête de liste.