Introduzione

Tutto è iniziato con un breve script che doveva unire le informazioni sugli indirizzi e-mail dei dipendenti, ottenute da un elenco di utenti di una mailing list, con le posizioni dei dipendenti, ricavate dal database delle risorse umane. Entrambi gli elenchi erano stati esportati in file di testo in codifica Unicode UTF-8 e salvati con linee finali unix.

Contenuto mail.txt

Ivanov Andrey;ia@example.com

Contenuto buhg.txt

Ivanova Alla;pittore
Yelkina Ella;crane operator
Ivanov Andrey;fabbro
Abakanov Mikhail;pittore

Per unire i file, sono stati ordinati con un comando unix sort e inviati a un programma unix join, che ha terminato inaspettatamente con un errore:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: non è ordinato: Ivanov Andrey;fabbro

Un'osservazione visiva del risultato dell'ordinamento ha mostrato che, in generale, l'ordinamento era corretto, ma in caso di omonimie tra cognomi maschili e femminili, i femminili precedono i maschili:

$> sort buhg.txt
Abakanov Mikhail;pittore
Yelkina Ella;crane operator
Ivanova Alla;pittore
Ivanov Andrey;fabbro

Sembra un bug nell'ordinamento in Unicode o l'emergere di femminismo nell'algoritmo di ordinamento. La prima spiegazione è certamente più plausibile.

Mettiamo in sospeso join e concentriamoci su sort. Proviamo a risolvere il problema attraverso tentativi. Iniziamo cambiando la lingua in en_US con ru_RU. Per l'ordinamento sarebbe sufficiente impostare la variabile d'ambiente LC_COLLATE, ma non ci accontenteremo:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Michail;pittore
Jolkina Ella;craneista
Ivanova Alla;pittrice
Ivanov Andrej;idraulico

Niente è cambiato.

Proviamo a ricodificare i file in un codice a singolo byte:

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

Di nuovo niente è cambiato.

Non c'è niente da fare, dovremo cercare una soluzione su internet. Non ci sono informazioni specifiche sulle famiglie russe, ma ci sono domande su altre stranezze nell'ordinamento. Ad esempio, c'è questo problema: unix sort tratta i caratteri ‘-‘ (trattino) come invisibili. In breve, le stringhe "a-b", "aa", "ac" vengono ordinate come "aa", "a-b", "ac".

La risposta è sempre la stessa: usa la locale per programmatori "C" e sarete felici. Proviamo:

$> LANG=C sort buhg.txt
Jolkina Ella;craneista
Abakanov Michail;pitore
Ivanov Andrej;idraulico
Ivanova Alla;avvocato

Qualcosa è cambiato. Gli Ivanov si sono sistemati nell'ordine corretto, ma Jolkina è sparita da qualche parte. Torniamo al compito iniziale:

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

È funzionato senza errori, come promesso da Internet. E nonostante ci sia Ёлкин nella prima riga.

Sembra che il problema sia risolto, ma per precauzione proviamo un'altra codifica russa — quella di Windows. CP1251:

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

Il risultato della sort, strano ma vero, coinciderà con la locale "C", e l'intero esempio, di conseguenza, passa senza errori. È davvero un mistero.

Non amo i misteri nella programmazione, poiché di solito nascondono errori. Dovrò occuparmi seriamente della questione di come funziona sort e su cosa influisce LC_COLLATE .

Alla fine cercherò di rispondere alle domande:

perché i cognomi femminili venivano ordinati in modo errato
perché LANG=ru_RU.CP1251 si è rivelato equivalente LANG=C
perché le persone hanno sort e join visioni diverse sull'ordine delle righe ordinate
perché nei miei esempi ci sono errori
infine, come ordinare le righe secondo il proprio gusto

Ordinamento in Unicode

La prima tappa sarà il rapporto tecnico n. 10 intitolato algoritmo di collazione Unicode sul sito unicode.org. Il rapporto contiene molti dettagli tecnici, quindi permettetemi di fornire un riassunto delle idee principali.

Collazione — "confronto" delle stringhe — è alla base di qualsiasi algoritmo di ordinamento. Gli algoritmi stessi possono variare ("a bolle", "per fusione", "rapido"), ma tutti utilizzeranno il confronto di coppie di stringhe per determinare l'ordine della loro successione.

L'ordinamento delle stringhe in linguaggio naturale è un problema piuttosto complesso. Anche nelle più semplici codifiche a byte singolo, l'ordine delle lettere nell'alfabeto, anche se differente dall'inglese, non corrisponderà all'ordine dei valori numerici con cui queste lettere sono codificate. Ad esempio, nella lingua tedesca la lettera Ö si trova tra maggiore numero di partizioni. e P, mentre nella codifica CP850 essa si colloca tra ÿ e Ü.

Si può tentare di astrarsi dalla codifica specifica e considerare le lettere "ideali", che sono disposte in un certo ordine, come avviene in Unicode. Le codifiche UTF8, UTF16 o la codifica a byte singolo KOI8-R (se è necessario un sottoinsieme limitato di Unicode) daranno rappresentazioni numeriche diverse delle lettere, ma facendo riferimento agli stessi elementi della tabella di base.

Si scopre che anche costruendo una tabella di caratteri da zero, non saremo in grado di assegnare un ordine universale ai caratteri. Nei vari alfabeti nazionali che utilizzano lettere identiche, l'ordine di queste lettere può differire. Ad esempio, nella lingua francese Æ verrà considerato un legatura e ordinato come una stringa AE. Nella lingua norvegese, invece, Æ verrà considerata una lettera separata che si trova dopo Z. A proposito, oltre alle legature tipo Æ esistono lettere scritte con più simboli. Così nell'alfabeto ceco c'è la lettera Ch, che si colloca tra H e I.

Oltre alle differenze negli alfabeti, ci sono anche altre tradizioni nazionali che influenzano l'ordinamento. In particolare, sorge la questione: in quale ordine dovrebbero seguire nel dizionario le parole composte da lettere maiuscole e minuscole? Inoltre, l'ordinamento può essere influenzato dalle peculiarità dell'uso della punteggiatura. Nella lingua spagnola, all'inizio di una frase interrogativa viene inserito un punto interrogativo rovesciato (¿Te gusta la música?). In questo caso è chiaro che le frasi interrogative non devono essere raggruppate in un cluster separato dall'alfabeto, quindi come dovrebbero essere ordinate le stringhe con altri segni di punteggiatura?

Non mi fermerò a discutere dell'ordinamento delle stringhe in lingue molto diverse da quelle europee. Vorrei sottolineare che in lingue con direzione di scrittura da destra a sinistra o dall'alto verso il basso, i simboli nelle stringhe sono probabilmente conservati nell'ordine di lettura, e anche in scritture non alfabetiche esistono modi per ordinare le stringhe simbolo per simbolo. Ad esempio, i caratteri possono essere ordinati in base alla loro forma (chiavi dei caratteri cinesi) o in base alla pronuncia. Non ho idea di come dovrebbero essere ordinati gli emoji, ma si può sicuramente trovare una soluzione anche per loro.

Sulla base delle caratteristiche sopra menzionate, sono stati formulati i requisiti principali per il confronto delle stringhe, basati sulle tabelle Unicode:

il confronto delle stringhe non dipende dalla posizione dei caratteri nella tabella dei codici;
le sequenze di caratteri che formano un unico carattere vengono portate alla forma canonica (A + il cerchietto superiore è lo stesso di Å);
Quando si confrontano le stringhe, il carattere viene considerato nel contesto della stringa e, se necessario, viene combinato con i vicini in un'unità di confronto (Ch in ceco) oppure viene suddiviso in più parti (Æ in francese);
tutte le peculiarità nazionali (alfabeto, maiuscole/minuscole, punteggiatura, ordine dei tipi di scrittura) devono essere configurabili fino a una specifica assegnazione dell'ordine (emoji);
il confronto è importante non solo per l'ordinamento, ma anche in molte altre aree, ad esempio per impostare intervalli di stringhe (sostituzione {A… я} in bash);
il confronto deve essere eseguito abbastanza rapidamente.

Inoltre, gli autori del rapporto hanno delineato le proprietà del confronto su cui gli sviluppatori dell'algoritmo non dovrebbero fare affidamento:

l'algoritmo di confronto non dovrebbe richiedere un insieme separato di caratteri per ogni lingua (le lingue russa e ucraina condividono la maggior parte dei caratteri cirillici);
il confronto non dovrebbe basarsi sull'ordine dei caratteri nelle tabelle Unicode;
il peso della stringa non dovrebbe essere un attributo della stringa, poiché la stessa stringa in diversi contesti culturali può avere pesi diversi;
il peso delle stringhe può variare durante la fusione o la divisione (da x < y non implica che xz < yz);
stringhe diverse con lo stesso peso siano considerate uguali secondo l'algoritmo di ordinamento. Introdurre un ulteriore ordinamento di tali stringhe è possibile, ma potrebbe ridurre le prestazioni;
nelle ri-ordinazioni, le stringhe con lo stesso peso possono scambiarsi di posto. La stabilità è una proprietà di un particolare algoritmo di ordinamento, non una proprietà dell'algoritmo di confronto delle stringhe (vedi punto precedente);
le regole di ordinamento possono cambiare nel tempo man mano che le tradizioni culturali vengono affinabili/cambiate.

Si specifica inoltre che l'algoritmo di confronto non sa nulla circa la semantica delle stringhe elaborate. Pertanto, stringhe costituite soltanto da cifre non devono essere confrontate come numeri, e negli elenchi di nomi inglesi non deve essere rimosso l'articolo (Beatles, The).

Per soddisfare tutti i requisiti indicati, è stato proposto un algoritmo di ordinamento tabellare multilivello (in effetti a quattro livelli).

All'inizio, i caratteri nella stringa vengono normalizzati e raggruppati in unità di confronto. A ciascuna unità di confronto sono assegnati diversi pesi, corrispondenti a vari livelli di confronto. I pesi delle unità di confronto sono elementi di insiemi ordinati (in questo caso numeri interi), che possono essere confrontati tra loro. IGNORATO (0x0) indica che a quel livello di confronto, l'unità corrispondente non partecipa. Il confronto delle stringhe può essere ripetuto più volte, utilizzando i pesi dei livelli appropriati. A ciascun livello, i pesi delle unità di confronto delle due stringhe vengono confrontati sequenzialmente.

Nelle varie implementazioni dell'algoritmo, per diverse tradizioni nazionali, i valori dei coefficienti possono variare, ma nel standard Unicode è inclusa una tabella base dei pesi — "Default Unicode Collation Element Table" (DUCET). Vorrei sottolineare che l'impostazione della variabile LC_COLLATE è in realtà un'indicazione per la scelta della tabella dei pesi nella funzione di confronto delle stringhe.

I coefficienti di peso DUCET sono strutturati come segue:

al primo livello tutte le lettere vengono portate a un'unica maiuscola, i segni diacritici vengono ignorati, la punteggiatura (non tutta) viene trascurata;
al secondo livello vengono considerati solo i segni diacritici;
al terzo livello viene considerato solo il maiuscolo e il minuscolo;
al quarto livello vengono considerati solo i segni di punteggiatura.

Il confronto avviene in più passaggi: prima vengono confrontati i coefficienti di primo livello; se i pesi coincidono, si procede a un confronto ripetuto con i pesi di secondo livello; poi, eventualmente, di terzo e quarto.

Il confronto termina quando nelle stringhe sono presenti unità di confronto corrispondenti con pesi diversi. Le stringhe che hanno pesi uguali a tutti i quattro livelli sono considerate equivalenti tra loro.

Questo algoritmo (con un sacco di dettagli tecnici aggiuntivi) ha dato il nome al rapporto n. 10 — "Unicode Collation Algorithm" (UCA).

In questo punto il comportamento dell'ordinamento del nostro esempio diventa un po' più chiaro. Sarebbe utile confrontarlo con lo standard Unicode.

Per testare le implementazioni UCA esiste un test, che utilizza un file di pesi, implementando DUCET. Nel file dei pesi si possono trovare diverse curiosità. Ad esempio, ci sono l'ordine delle tessere del mahjong e del domino europeo, così come l'ordine dei semi nel mazzo di carte (simbolo 1F000 e così via). I semi delle carte sono disposti secondo le regole del bridge — PCHBT, e le carte nei semi — in sequenza A, 2, 3... K.

La verifica manuale della correttezza dell'ordinamento delle stringhe secondo DUCET sarebbe piuttosto noiosa, ma, fortunatamente per noi, esiste un'implementazione esemplare della libreria per lavorare con Unicode — "International Components for Unicode" (ICU).

Sul sito di questa libreria, sviluppata in IBM, ci sono pagine dimostrative, inclusa la pagina dell'algoritmo di confronto delle stringhe. Introduciamo le nostre stringhe di test con le impostazioni predefinite e, oh meraviglia, otteniamo un'ordinamento russo perfetto.

Abakanov Mikhail;pittore
Yolkina Ella;gruista
Ivanov Andrey;fabbro
Ivanova Alla;avvocato

A proposito, sul sito ICU si può trovare chiarimenti sul funzionamento dell'algoritmo di confronto nella gestione dei segni di punteggiatura. Negli esempi Collation FAQ viene ignorata l'apostrofo e il trattino.

Unicode ci ha aiutato, ma bisognerà cercare le ragioni del comportamento strano sort in Linux in un altro posto.

Ordinamento in glibc

Anteprima del codice sorgente dell'utility sort di GNU Core Utils ha dimostrato che all'interno dell'utility la localizzazione si limita alla stampa del valore corrente della variabile LC_COLLATE quando eseguita in modalità di debug:

$ sort --debug buhg.txt > buhg.srt
sort: utilizza le regole di ordinamento ‘en_US.UTF8’

Il confronto delle stringhe avviene tramite la funzione standard strcoll, il che significa che tutto l'interessante si trova nella libreria glibc.

Su wiki progetto glibc dedicata al confronto delle stringhe un paragrafo. Da questo paragrafo possiamo capire che la glibc l'ordinamento si basa su un algoritmo già noto UCA (The Unicode collation algorithm) e/o su uno standard a esso simile ISO 14651 (Ordinamento e confronto delle stringhe internazionali). A proposito dell'ultimo standard, va notato che sul sito standards.iso.org ISO 14651 è ufficialmente dichiarato pubblico, ma il link corrispondente porta a una pagina inesistente. Google mostra diverse pagine con collegamenti ai siti ufficiali che offrono di acquistare una copia elettronica dello standard per un centinaio di euro, ma nelle terze o quarte pagine dei risultati di ricerca si possono trovare anche link diretti a PDF. In generale, lo standard non è praticamente diverso da UCA, ma si legge in modo più noioso, poiché non contiene esempi vividi delle particolarità nazionali dell'ordinamento delle stringhe.

Le informazioni più interessanti su wiki si sono rivelate essere il link a un tracker di bug con una discussione sull'implementazione del confronto delle stringhe in glibc. Dalla discussione si può apprendere che in glibc per il confronto delle stringhe si utilizza ISOuna tabella comune The Common Template Table (CTT), il cui indirizzo può essere trovato nell'applicazione A del standard ISO 14651. Tra il 2000 e il 2015 questa tabella in glibc non aveva un maintainer ed era abbastanza differente (almeno esteticamente) dall'attuale versione standard. Dal 2015 al 2018 c'è stata un'adattamento alla nuova versione della tabella e attualmente si può incontrare nella vita reale sia la nuova versione della tabella (CentOS 8), sia la vecchia (CentOS 7).

Ora che abbiamo tutte le informazioni sugli algoritmi e le tabelle ausiliarie, possiamo tornare al problema iniziale e capire come ordinare correttamente le stringhe nella locale russa.

ISO 14651⁄14652

Il codice sorgente della tabella che ci interessa CTT si trova nella maggior parte delle distribuzioni Linux nella directory /usr/share/i18n/locales/. La tabella stessa si trova nel file iso14651_t1_common. Poi questo file viene incluso nella direttiva copy iso14651_t1_common inclusa nel file iso14651_t1, che a sua volta è incluso nei file nazionali, compresi i en_US e ru_RU. Nella maggior parte delle distribuzioni Linux tutti i file sorgente sono inclusi nell'installazione di base, ma se non sono presenti, sarà necessario installare un pacchetto aggiuntivo dal distributore.

La struttura del file iso14651_t1 può sembrare terribilmente verbose, con regole di nomenclatura poco ovvie, ma una volta compreso, è tutto piuttosto semplice. La struttura è descritta nello standard ISO 14652, una copia del quale può essere scaricata dal sito open-std.org. Un'altra descrizione del formato file può essere letta in specifiche POSIX da OpenGroup. In alternativa alla lettura dello standard, si possono esaminare i sorgenti della funzione collate_read in glibc/locale/programs/ld-collate.c.

La struttura del file appare come segue:

Per impostazione predefinita, il simbolo viene utilizzato come carattere di escape, e la fine della linea dopo il simbolo # è un commento. Entrambi i simboli possono essere sovrascritti, come fatto nella nuova versione della tabella:

escape_char /
comment_char %

Nel file si incontreranno token nel formato <Uxxxx> o <Uxxxxxxxx> (dove x — cifra esadecimale). Questa è la rappresentazione esadecimale dei punti codice Unicode in codifica UCS-4 (UTF-32). Tutti gli altri elementi tra parentesi angolari (incluso <Uxxxx_xxxx>, <2> e simili) sono considerati costanti di stringa semplici, senza alcun significato particolare al di fuori del contesto.

Stringa LC_COLLATE ci dice che in seguito iniziano i dati che descrivono il confronto delle stringhe.

Inizialmente vengono impostati i nomi per i pesi nella tabella di confronto e i nomi per le combinazioni di caratteri. In generale, due tipi di nomi appartengono a due entità diverse, ma nel file reale sono mescolati. I nomi dei pesi sono impostati dalla parola chiave collating-symbol (simbolo di confronto), poiché nel confronto i caratteri Unicode che hanno lo stesso peso saranno considerati simboli equivalenti.

La lunghezza totale della sezione nella revisione attuale del file è di circa 900 righe. Ho estratto esempi da più luoghi per dimostrare l'arbitrarietà dei nomi e diversi tipi di sintassi.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Valore simbolo garantito più grande. Tenere alla fine di questo elenco
...
collating-element  da ""
collating-element  da ""

collating-symbol registra la stringa OSMANYA nella tabella dei nomi dei pesi
collating-symbol .. registra una sequenza di nomi, composta da un prefisso S e un suffisso numerico esadecimale da 1D000 fino a 1D35F.
FFFF in collating-symbol sembra un grande intero senza segno in forma esadecimale, ma <SFFFF> è solo un nome che potrebbe apparire come <VERYBIGVAL>
nome <U0413> indica un punto di codice in codifica UCS-4
collating-element da "" registra un nuovo nome per una coppia di punti Unicode.

Quando i nomi dei pesi sono definiti, vengono effettivamente impostati i pesi. Poiché durante il confronto conta solo il rapporto maggiore-minore, i pesi vengono definiti da una semplice sequenza di enumerazione dei nomi. Prima vengono elencati i pesi più "leggeri", poi quelli più "pesanti". Ricordo che a ciascun simbolo Unicode vengono assegnati quattro pesi diversi. Qui sono riassunti in un'unica sequenza ordinata. Teoricamente, qualsiasi nome simbolico può essere utilizzato su uno dei quattro livelli, ma i commenti indicano che gli sviluppatori tendono a classificare i nomi per livelli.

% Assegnazioni di peso simbolico

% Assegnazioni di peso di terzo livello




...
% Assegnazioni di peso di secondo livello

 % COMBINING LOW LINE
 % COMBINING COMMA ABOVE
 % COMBINING REVERSED COMMA ABOVE
...
% Assegnazioni di peso di primo livello
 % TABULAZIONE ORIZZONTALE
 % CR LF
 % TABULAZIONE VERTICALE
...
 % LETTERA CILRILLICA MINUSCOLA DE
 % LETTERA CILRILLICA MINUSCOLA KOMI DE
 % LETTERA CILRILLICA MINUSCOLA DJE
 % LETTERA CILRILLICA MINUSCOLA KOMI DJE
 % LETTERA CILRILLICA MINUSCOLA GJE
 % LETTERA CILRILLICA MINUSCOLA ZE CON DISCENDENTE
 % LETTERA CILRILLICA MINUSCOLA IE
 % LETTERA CILRILLICA MINUSCOLA IE CON BREVE
 % LETTERA CILRILLICA MINUSCOLA IE UCRAINA
 % LETTERA CILRILLICA MINUSCOLA ZHE

Infine, la tabella dei pesi vera e propria.

La sezione dei pesi è racchiusa in righe con parole chiave order_start e order_end. Parametri aggiuntivi order_start definiscono in quale direzione vengono visualizzate le righe a ogni livello di confronto. Per impostazione predefinita, viene utilizzato il parametro forward. Il corpo della sezione è composto da righe che contengono il codice del simbolo e i suoi quattro pesi. Il codice del simbolo può essere rappresentato dal simbolo stesso, dal punto di codice o da un nome simbolico definito in precedenza. I pesi possono essere anch'essi definiti tramite nomi simbolici, punti di codice o simboli stessi. Quando si utilizzano punti di codice o simboli, il loro peso corrisponde al valore numerico del punto di codice (posizione nella tabella Unicode). I simboli non specificati esplicitamente (per come capisco) sono considerati associati nella tabella con un peso primario corrispondente alla loro posizione nella tabella Unicode. Valore speciale del peso IGNORE indica che a quel livello di confronto il simbolo corrispondente viene ignorato.

Per dimostrare la struttura dei pesi, ho scelto tre frammenti abbastanza evidenti:

simboli che vengono completamente ignorati
simboli equivalenti al numero tre nei primi due livelli
inizio dell'alfabeto cirillico, che non contiene segni diacritici e quindi viene ordinato, principalmente, in base al primo e al terzo livello.

ordine_inizio forward;forward;forward;forward,posizione
 IGNORARE;IGNORARE;IGNORARE;IGNORARE % NULL (in 6429)
 IGNORARE;IGNORARE;IGNORARE;IGNORARE % INIZIO INTITOLAZIONE (in 6429)
 IGNORARE;IGNORARE;IGNORARE;IGNORARE % INIZIO TESTO (in 6429)
...
 ;;; % CIFRA TRE
 ;;; % CIFRA TRE A LARGHEZZA COMPLETA
 ;;; % CIFRA TRE TRA CITTADINI
 ;;; % CIFRA TRE PUNTO FINALE
 ;;; % CIFRA TRE BOLD MATEMATICO
...
 ;;; % LETTERA PICCOLA CYRILLICA A
 ;;; % LETTERA MAIUSCOLA CYRILLICA A
 ;;; % LETTERA PICCOLA CYRILLICA A CON BREVE
 ;;; % LETTERA PICCOLA CYRILLICA A CON BREVE
...
 ;;; % LETTERA PICCOLA CYRILLICA BE
 ;;; % LETTERA MAIUSCOLA CYRILLICA BE
 ;;; % LETTERA PICCOLA CYRILLICA VE
 ;;; % LETTERA MAIUSCOLA CYRILLICA VE
...
ordine_fine

Ora è possibile tornare a ordinare gli esempi dall'inizio dell'articolo. La trappola si nasconde in questa parte della tabella dei pesi:

IGNORARE;IGNORARE;IGNORARE; % SPAZIO
 IGNORARE;IGNORARE;IGNORARE; % PUNTO ESCLAMATIVO
 IGNORARE;IGNORARE;IGNORARE; % VIRGOLA

È evidente che in questa tabella i segni di punteggiatura sono presenti nella tabella Rasterizzazione bit per bit o byte per byte (compreso lo spazio) durante il confronto delle stringhe vengono praticamente sempre ignorati. L'eccezione è data solo dalle stringhe che coincidono in tutto, tranne che per i segni di punteggiatura presenti nelle posizioni corrispondenti. Le stringhe del mio esempio (dopo l'ordinamento) per l'algoritmo di confronto appaiono così:

AbakanovMikhailpittore
YolkinaEllaoperaia
IvanovaAlalpittore
IvanovAndreyfalegname

Considerando che nella tabella di ordinamento le lettere maiuscole in russo vengono dopo quelle minuscole (al terzo livello <CAP> più pesante di <MIN>), l'ordinamento appare assolutamente corretto.

Quando si imposta la variabile LC_COLLATE=C viene caricata una tabella speciale che definisce il confronto byte per byte

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

Poiché nel Unicode il punto di codice Ё viene prima di А, le stringhe vengono ordinate di conseguenza.

Tabelle testuali e binarie

È chiaro che il confronto delle stringhe è un'operazione estremamente comune, mentre l'analisi della tabella CTT è un processo piuttosto costoso. Per ottimizzare l'accesso alla tabella, essa viene compilata in forma binaria dalla comando localedef.

Team localedef che accetta come parametri un file con la tabella delle caratteristiche nazionali (opzione -i), in cui tutti i caratteri sono rappresentati da punti Unicode, e un file di corrispondenza dei punti Unicode ai caratteri di una specifica codifica (opzione -f). Al termine del processo, vengono creati file binari per la località, con il nome specificato nell'ultimo parametro.

Glibc supporta due formati di file binari: "tradizionale" e "moderno".

Il formato tradizionale implica che il nome della località sia il nome di una sottodirectory in /usr/lib/locale/. In questa sottodirectory vengono memorizzati i file binari LC_COLLATE, LC_CTYPE, LC_TIME e così via. Il file LC_IDENTIFICATION contiene il nome formale della località (che può differire dal nome della directory) e commenti.

Il formato moderno prevede la memorizzazione di tutte le località in un unico archivio /usr/lib/locale/locale-archive, che viene mappato nella memoria virtuale di tutti i processi che lo utilizzano. glibc. Il nome della locale nel formato moderno subisce una certa canonizzazione — nei nomi delle codifiche rimangono solo numeri e lettere, convertiti in minuscolo. Così ru_RU.KOI8-R, sarà salvato come ru_RU.koi8r.

I file di input sono cercati nella directory attuale, così come nelle directory /usr/share/i18n/locales/ e /usr/share/i18n/charmaps/ per i file CTT e per i file di codifica rispettivamente.

Ad esempio, il comando

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

compilerà il file /usr/share/i18n/locales/ru_RU utilizzando il file di codifica /usr/share/i18n/charmaps/MAC-CYRILLIC.gz e salverà il risultato in /usr/lib/locale/locale-archive con il nome ru_RU.maccyrillic

Se si imposta la variabile LANG=en_US.UTF-8 allora glibc cercherà i file binari della locale nella seguente sequenza di file e directory:

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

Se la locale si trova sia nei formati tradizionali che in quelli moderni, si dà priorità a quello moderno.

Per visualizzare l'elenco delle locale compilate, è possibile utilizzare il comando locale -a.

Preparare la propria tabella di confronto

Ora, armati della conoscenza, puoi creare la tua tabella di confronto ideale. Questa tabella dovrebbe confrontare correttamente le lettere russe, inclusa la lettera Ё, e tenere conto della punteggiatura in conformità con la tabella. Rasterizzazione bit per bit o byte per byte.

Il processo di preparazione della propria tabella di ordinamento si compone di due fasi: la modifica della tabella dei pesi e la sua compilazione in forma binaria mediante un comando. localedef.

Affinché la tabella di confronto possa essere adattata con costi minimi di modifica, viene utilizzato il formato ISO 14652 che prevede sezioni di correzione dei pesi per una tabella esistente. La sezione inizia con la parola chiave reorder-after e l'indicazione della posizione dopo la quale avviene la sostituzione. La sezione è conclusa dalla riga reorder-end. Se è necessario correggere più sezioni della tabella, si crea una sezione per ciascuna di esse.

Ho copiato le nuove versioni dei file iso14651_t1_common e ru_RU dal repository glibc nella mia cartella home ~/.local/share/i18n/locales/ e ho modificato leggermente la sezione LC_COLLATE in ru_RU. Le nuove versioni dei file sono completamente compatibili con la mia versione glibc. Se desiderate utilizzare le versioni precedenti dei file, dovrete modificare i nomi simbolici e il luogo da cui inizia la sostituzione nella tabella.

LC_COLLATE
% Copia il modello da ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPAZIO
 ;;; % PUNTO ESCLAMATIVO
 ;;; % VIRGOLA
...
 ;;; % CORTE CURVO DESTRO
 ;;; % TILDE
reorder-end
FINE LC_COLLATE

In realtà, sarebbe stato meglio cambiare i campi in LC_IDENTIFICATION in modo che puntassero alla locale it_MY, ma nel mio esempio non era necessario, poiché ho escluso dalla ricerca le locali dell'archivio locale-archive.

Per creare un file di esportazione del database di gestione sul server di origine: localedef lavorava con i file nella mia cartella tramite la variabile I18NPATH puoi aggiungere una directory aggiuntiva per cercare i file di input, mentre la directory per salvare i file binari può essere specificata come percorso con le barre:

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

POSIX presuppone che in LANG possono essere scritti percorsi assoluti alle directory con i file di locale che iniziano con una barra, ma glibc in Linux tutti i percorsi sono calcolati dalla directory base, che può essere sovrascritta tramite la variabile LOCPATH. Dopo aver impostato LOCPATH=~/.local/lib/locale/ tutti i file correlati alla localizzazione verranno cercati solo nella mia cartella. L'archivio delle locali con la variabile impostata LOCPATH viene ignorata.

Ecco il test decisivo:

$> LANG=it_IT.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;pittore
Yolkina Ella;gruista
Ivanov Andrei;meccanico
Ivanova Alla;avvocato

Evviva! Ce l'abbiamo fatta!

Lavoro di correzione degli errori

Ho già risposto alle domande sulla ordinazione delle stringhe, sollevate all'inizio, ma ci sono ancora un paio di domande sugli errori — visibili e invisibili.

Torniamo al compito iniziale.

E il programma sort e il programma join utilizza le stesse funzioni di confronto delle stringhe di glibc. Com'è possibile che join ha restituito un errore di ordinamento sulle stringhe ordinate dal comando sort nella locale en_US.UTF-8? Ответ прост: sort confronta l'intera stringa, mentre join confronta solo la chiave, che di default è l'inizio della stringa fino al primo carattere di spazio. Nel mio esempio, questo ha portato a un messaggio di errore poiché l'ordinamento delle prime parole nelle stringhe non corrispondeva all'ordinamento delle stringhe complete.

Locale "C" garantisce che, nelle righe ordinate, le sottostringhe iniziali fino al primo spazio saranno anch'esse ordinate, ma questo maschera solo l'errore. È possibile fornire dati (persone con lo stesso cognome ma nomi diversi) che, senza un messaggio di errore, potrebbero produrre un risultato errato durante la fusione dei file. Se vogliamo che join unifichi le righe dei file in base a nome e cognome, il modo corretto è indicare esplicitamente il delimitatore dei campi e ordinare in base al campo chiave, e non all'intera riga. In questo caso, la fusione funzionerà correttamente e non ci saranno errori in nessuna locale:

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

Esempio eseguito con successo in codifica CP1251 contiene un altro errore. Il fatto è che in tutte le distribuzioni che conosco Linux mancano i pacchetti della locale compilata ru_RU.CP1251. Se la locale compilata non viene trovata, sort si utilizza silenziosamente il confronto byte a byte, come abbiamo Observato.

A proposito, c'è un altro piccolo bug legato alla mancanza delle località compilate. Il comando LOCPATH=/tmp locale -a restituirà un elenco di tutte le località in locale-archive, ma con la variabile impostata LOCPATH per tutti i programmi (anche per il principale locale) queste località non saranno disponibili.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Impossibile impostare LC_CTYPE come locale predefinito: Nessun file o directory di questo tipo
locale: Impossibile impostare LC_MESSAGES come locale predefinito: Nessun file o directory di questo tipo
locale: Impossibile impostare LC_COLLATE come locale predefinito: Nessun file o directory di questo tipo
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: utilizza le regole di ordinamento ‘en_US.UTF-8’

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: utilizza un semplice confronto di byte

Conclusione

Se sei un programmatore a cui piace pensare che le stringhe siano un insieme di byte, la tua scelta LC_COLLATE=C.

Se sei un linguista o un compilatore di dizionari, è meglio che tu compili il tuo locale.

Se sei un utente semplice, è sufficiente abituarsi al fatto che il comando ls -a restituisce file che iniziano con un punto, mescolati con file che iniziano con una lettera, e Midnight Commander, che usa le proprie funzioni interne per ordinare i nomi, porta i file che iniziano con un punto all'inizio dell'elenco.