Introduzione

Tutto è iniziato con un breve script che doveva unire le informazioni sugli indirizzi e-mail dei dipendenti, ottenute da un elenco di utenti della mailing list, con le posizioni dei dipendenti, ottenute dal database del personale. Entrambi gli elenchi sono stati esportati in file di testo in codifica Unicode UTF-8 e salvati con terminazioni di riga Unix.

Contenuto mail.txt

Ivanov Andrei;ia@example.com

Contenuto buhg.txt

Ivanova Alla;imbianchino
Eltkina Ella;gruista
Ivanov Andrei;installatore
Abakanov Michail;imbianchino

Per unire i file, sono stati ordinati con il comando Unix sort e forniti come input a un programma Unix upgrade, che è 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 Andrei;installatore

Una revisione del risultato dell'ordinamento ha mostrato che, in generale, l'ordinamento era corretto, ma nel caso di nomi maschili e femminili coincidenti, i nomi femminili vengono prima:

$> sort buhg.txt
Abakanov Michail;imbianchino
Eltkina Ella;gruista
Ivanova Alla;imbianchino
Ivanov Andrei;installatore

Sembra un bug nell'ordinamento Unicode o un'espressione del femminismo nell'algoritmo di ordinamento. La prima opzione è certamente più plausibile.

Lasciamo per ora upgrade e concentriamoci su sort. Proviamo a risolvere il problema con il metodo del tentativo ed errore. Per cominciare, cambiamo la localizzazione da en_US in ru_RU. Per l'ordinamento sarebbe bastato impostare la variabile d'ambiente LC_COLLATE, ma non ci accontenteremo:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Michail;imbianchino
Eltkina Ella;gruista
Ivanova Alla;imbianchino
Ivanov Andrei;installatore

Niente è cambiato.

Proviamo a riconvertire i file in una codifica a byte singolo:

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

Ancora una volta, niente è cambiato.

Non abbiamo scelta, dovremo cercare una soluzione su Internet. Non ci sono informazioni specifiche sulle famiglie russe, ma ci sono domande su altre stranezze nell'ordinamento. Ecco, per esempio, un problema: l'ordinamento Unix 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 localizzazione per programmatori "C" e sarete felici. Proviamo:

$> LANG=C sort buhg.txt
Eltkina Ella;gruista
Abakanov Michail;imbianchino
Ivanov Andrei;installatore
Ivanova Alla;avvocato

Qualcosa è cambiato. Gli Ivanov sono stati ordinati nel modo giusto, ma Eltkina è scomparsa da qualche parte. Torniamo al compito originale:

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

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

Il problema sembra 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 dell'ordinamento, strano ma vero, corrisponderà alla localizzazione. "C", e l'intero esempio, di conseguenza, passa senza errori. È una sorta di mistero.

Non amo i misteri nella programmazione, poiché in genere mascherano errori. Dovrò prendere seriamente in considerazione come funziona sort e su cosa influisce LC_COLLATE .

Alla fine cercherò di rispondere alle domande:

perché i cognomi femminili non venivano ordinati correttamente
perché LANG=ru_RU.CP1251 si è rivelata equivalente LANG=C
perché sort e upgrade hanno differenti rappresentazioni dell'ordine delle righe ordinate
perché ci sono errori in tutti i miei esempi
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 una breve sintesi delle idee principali.

Collazione — "confronto" delle righe — è alla base di qualsiasi algoritmo di ordinamento. Gli algoritmi stessi possono differire ("bubble sort", "merge sort", "quick sort"), ma tutti utilizzeranno il confronto tra coppie di righe per determinare l'ordine della loro sequenza.

Ordinare le righe in un linguaggio naturale è un problema piuttosto complesso. Anche nelle più semplici codifiche a byte singolo, l'ordine delle lettere nell'alfabeto, in qualsivoglia modo diverso dall'alfabeto latino inglese, non corrisponderà più all'ordine dei valori numerici che codificano quelle lettere. Così, nell'alfabeto tedesco, la lettera Ö si trova tra O e P, ma nella codifica CP850 si colloca tra ÿ e Ü.

Si può cercare di astrarsi dalla codifica specifica e considerare le "lettere ideali", che sono disposte in un certo ordine, come fatto 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 faranno riferimento agli stessi elementi della tabella di base.

Scopriamo che anche costruendo una tabella dei caratteri da zero, non saremo in grado di impostare un ordine universale dei caratteri. Negli alfabeti nazionali diversi che utilizzano le stesse lettere, l'ordine di queste lettere può variare. Ad esempio, nella lingua francese Æ sarà considerata una ligatura e ordinata come una stringa AE. Nella lingua norvegese, invece, Æ sarà una lettera separata, che si trova dopo Z. A proposito, oltre alle ligature come Æ esistono lettere scritte con più caratteri. Ad esempio, nell'alfabeto ceco c'è la lettera Ch, che si trova tra H e I.

Oltre alla differenza negli alfabeti, ci sono anche altre tradizioni nazionali che influenzano l'ordinamento. In particolare, si pone la questione: in quale ordine dovrebbero seguire in un dizionario le parole composte da lettere maiuscole e minuscole? Inoltre, l'uso della punteggiatura può influenzare l'ordinamento. Nella lingua spagnola, all'inizio di una frase interrogativa si colloca un punto interrogativo rovesciato (¿Te gusta la música?). In questo caso è evidente che le frasi interrogative non dovrebbero essere raggruppate in un cluster separato al di fuori dell'alfabeto, ma come si devono ordinare le stringhe con altri segni di punteggiatura?

Non mi soffermerò sull'ordinamento delle stringhe in lingue molto diverse da quelle europee. Sottolineo che nelle lingue con direzione di scrittura da destra a sinistra o dall'alto verso il basso, i caratteri nelle stringhe vengono probabilmente memorizzati nell'ordine di lettura, e anche nelle scritture non alfabetiche ci sono modi per ordinare le stringhe carattere per carattere. Ad esempio, i caratteri possono essere ordinati in base alla loro forma (chiavi dei caratteri cinesi) o sulla base della pronuncia. Come dovrebbero essere ordinati gli emoji, francamente, non lo so, ma anche per loro si può inventare qualcosa.

Sulla base delle caratteristiche sopra elencate, sono stati formulati i requisiti fondamentali 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 a una forma canonica (A + il cerchietto sopra è lo stesso di Å);
nel confronto delle stringhe, il carattere viene considerato nel contesto della stringa e, se necessario, viene unito con i vicini in un'unità di confronto (Ch in ceco) oppure viene suddiviso in più unità (Æ in francese);
tutte le peculiarità nazionali (alfabeto, maiuscole/minuscole, segni di punteggiatura, ordine dei tipi di scrittura) devono essere configurate fino all'assegnazione manuale dell'ordine (emoji);
il confronto è importante non solo per l'ordinamento, ma anche in molti altri contesti, ad esempio per definire gli intervalli di righe (sostituzione {A… z} in bash);
il confronto deve essere eseguito piuttosto rapidamente.

Inoltre, gli autori del rapporto hanno definito delle proprietà di confronto su cui i programmatori dell'algoritmo non devono basarsi:

l'algoritmo di confronto non deve richiedere un insieme separato di caratteri per ogni lingua (le lingue russa e ucraina condividono la maggior parte dei caratteri cirillici);
il confronto non deve dipendere dall'ordine dei caratteri nelle tabelle Unicode;
il peso di una stringa non deve essere un attributo della stringa, poiché la stessa stringa in diversi contesti culturali può avere pesi differenti;
i pesi delle stringhe possono variare durante fusioni o divisioni (da x < y non si deve intendere che xz < yz);
stringhe diverse che hanno lo stesso peso sono considerate uguali dal punto di vista dell'algoritmo di ordinamento. Introduzione di ulteriori ordinamenti di tali stringhe è possibile, ma potrebbe ridurre le prestazioni;
in ordinamenti ripetuti, le stringhe con lo stesso peso potrebbero scambiarsi di posto. La stabilità è una proprietà specifica di un algoritmo di ordinamento, e non una proprietà dell'algoritmo di confronto delle stringhe (vedi punto precedente);
le regole di ordinamento possono cambiare nel tempo con la definizione/cambiamento delle tradizioni culturali.

È inoltre specificato che l'algoritmo di confronto non ha conoscenze sulla semantica delle stringhe elaborate. Pertanto, le stringhe costituite solo 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 multistrato (in realtà a quattro livelli).

Prima, i caratteri nella stringa sono portati alla forma canonica e raggruppati in unità di confronto. A ciascuna unità di confronto vengono assegnati vari pesi, corrispondenti a diversi livelli di confronto. I pesi delle unità di confronto sono elementi di insiemi ordinati (in questo caso interi), che possono essere confrontabili tra loro in termini di maggiore-minore. Un valore speciale IGNORED (0x0) significa che a quel livello di confronto l'unità corrispondente non partecipa al confronto. Il confronto delle stringhe può ripetersi più volte, utilizzando i pesi dei livelli corrispondenti. A ciascun livello, i pesi delle unità di confronto di due stringhe vengono confrontati sequenzialmente tra loro.

Nelle diverse implementazioni dell'algoritmo per le diverse tradizioni nazionali, i valori dei coefficienti possono variare, ma fa parte dello standard Unicode una tabella base dei pesi - "Default Unicode Collation Element Table" (DUCET). Vorrei sottolineare che impostare la variabile LC_COLLATE è in effetti un'indicazione per la scelta della tabella dei pesi nella funzione di confronto delle stringhe.

I coefficienti di peso DUCET sono strutturati nel seguente modo:

al primo livello tutte le lettere vengono ridotte a un unico case, i segni diacritici vengono scartati, la punteggiatura (non tutta) viene ignorata;
al secondo livello si considerano solo i segni diacritici;
al terzo livello si considera solo il case;
al quarto livello si considerano solo i segni di punteggiatura.

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

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

Questo algoritmo (con una serie di dettagli tecnici aggiuntivi) ha dato il nome al rapporto n. 10 - "Unicode Collation Algorithm" (UCA).

A questo punto, il comportamento della ordinazione dal nostro esempio diventa un po' più chiaro. Sarebbe utile confrontarlo con lo standard Unicode.

Per testare le implementazioni UCA esiste un apposito test, che utilizza un file di pesi, realizzando DUCET. Nel file di pesi si possono trovare vari divertimenti. 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 oltre). I semi delle carte sono disposti secondo le regole del bridge - PCHBT, e le carte in ogni seme seguono la sequenza 2,3… K.

Verifica manuale della correttezza dell'ordinamento delle stringhe secondo DUCET sarebbe piuttosto faticosa, ma, per fortuna, esiste un'implementazione egregia della libreria per lavorare con Unicode — "International Components for Unicode" (ICU).

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

Abakanov Michail;pittore
Jolkina Ella;grùista
Ivanov Andrej;idraulico
Ivanova Alla;avvocato

A proposito, sul sito ICU si può trovare un chiarimento sul funzionamento dell'algoritmo di confronto nella gestione della punteggiatura. Negli esempi Collation FAQ si ignorano l'apostrofo e il trattino.

Unicode ci ha aiutato, ma bisognerà cercare le cause del comportamento strano sort in Linux da qualche altra parte.

Ordinamento in glibc

Una rapida visione del codice sorgente dello strumento sort da GNU Core Utils ha mostrato che nella stessa utility la localizzazione si riduce alla stampa del valore attuale 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 viene effettuato dalla funzione standard strcoll, il che significa che tutto l'interessante si trova nella libreria glibc.

A wiki del progetto glibc il confronto delle stringhe è dedicato a un paragrafo. Da questo paragrafo si può capire che in glibc l'ordinamento si basa già sull'algoritmo che conosciamo UCA (The Unicode collation algorithm) e/o su uno standard simile ISO 14651 (Ordinamento e confronto delle stringhe internazionali). Riguardo a quest'ultimo standard va notato che sul sito standards.iso.org ISO 14651 è ufficialmente dichiarato accessibile al pubblico, ma il link corrispondente porta a una pagina inesistente. Google restituisce diverse pagine con link a siti ufficiali che offrono l'acquisto di una copia elettronica dello standard per diverse centinaia di euro, ma nelle terza-quarta pagina dei risultati di ricerca si trovano anche collegamenti diretti a PDF. In generale, lo standard non si discosta praticamente da UCA, ma è meno interessante da leggere poiché non contiene esempi vividi delle peculiarità nazionali dell'ordinamento delle stringhe.

La informazione più interessante su wiki è stata un collegamento a bug tracker con una discussione sull'implementazione del confronto delle stringhe in glibc. Dalla discussione si può scoprire che in glibc per il confronto delle stringhe viene utilizzata ISOla tabella The Common Template Table (CTT), il cui indirizzo può essere trovato nell'allegato A dello standard ISO 14651. Tra il 2000 e il 2015 questa tabella in glibc non aveva un mantenitore e differiva notevolmente (perlomeno esternamente) dalla versione attuale dello standard. Dal 2015 al 2018 si è svolta un'adattamento alla nuova versione della tabella e al momento avete la possibilità di incontrare nella vita reale sia la nuova variante della tabella (CentOS 8), sia la vecchia (CentOS 7).

Ora che abbiamo tutte le informazioni sull'algoritmo e sulle tabelle ausiliarie, possiamo tornare al problema originale e capire come ordinare correttamente le stringhe nella locale russa.

ISO 14651/14652

Il codice sorgente della tabella che ci interessa CTT è presente 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 con la direttiva copy iso14651_t1_common viene incluso nel file iso14651_t1, che, a sua volta, è incluso nei file nazionali, compresi en_US e ru_RU. Nella maggior parte delle distribuzioni Linux tutti i file sorgente sono inclusi nella versione base, ma se non ci sono, sarà necessario installare un pacchetto aggiuntivo dalla distribuzione.

La struttura del file iso14651_t1 può sembrare terribilmente prolisso, con regole non ovvie per la costruzione dei nomi, ma se ci si mette d’impegno, 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 del file può essere letta in specifiche POSIX di OpenGroup. In alternativa alla lettura dello standard, si possono studiare i testi sorgente della funzione collate_read in glibc/locale/programs/ld-collate.c.

La struttura del file appare come segue:

Per impostazione predefinita, il simbolo è utilizzato come carattere di escape, e la fine della riga 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 di codice Unicode nella codifica UCS-4 (UTF-32). Tutti gli altri elementi tra parentesi angolari (inclusi <Uxxxx_xxxx>, <2> e simili), sono considerati costanti di stringa semplici, prive di un significato speciale al di fuori del contesto.

Riga LC_COLLATE ci dice che di seguito iniziano i dati che descrivono il confronto delle stringhe.

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

La lunghezza complessiva della sezione nell'attuale revisione del file è di circa 900 righe. Ho estratto esempi da diversi 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  % Garantito il valore simbolico più grande. Mantieni 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 costituita da un prefisso S e un suffisso numerico esadecimale di 1D000 fino a 1D35F.
FFFF in collating-symbol sembra un grande intero senza segno in notazione esadecimale, ma <SFFFF> è semplicemente un nome che potrebbe sembrare come <VERYBIGVAL>
nome <U0413> indica un punto di codice nella codifica UCS-4
collating-element da "" registra un nuovo nome per una coppia di punti Unicode.

Quando i nomi dei pesi sono definiti, vengono assegnati i pesi propriamente detti. Poiché nel confronto conta solo la relazione maggiore-minore, i pesi sono 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 riuniti in un'unica sequenza ordinata. Teoricamente, qualsiasi nome simbolico può essere utilizzato a uno dei quattro livelli, ma i commenti indicano che gli sviluppatori mentalmente dividono i nomi per livelli.

% Assegnazione di pesi simbolici

% Assegnazione di pesi di terzo livello




...
% Assegnazione di pesi di secondo livello

 % LINEA BASSA COMBINANTE
 % VIRGOLA COMBINANTE SOPRA
 % VIRGOLA ROVESCIATA COMBINANTE SOPRA
...
% Assegnazione di pesi di primo livello
 % TABULAZIONE ORIZZONTALE 
 % CARRIAGE RETURN
 % TABULAZIONE VERTICALE
...
 % LETTERA MINUSCOLA CYRILLIC DE
 % LETTERA MINUSCOLA CYRILLIC KOMI DE
 % LETTERA MINUSCOLA CYRILLIC DJE
 % LETTERA MINUSCOLA CYRILLIC KOMI DJE
 % LETTERA MINUSCOLA CYRILLIC GJE
 % LETTERA MINUSCOLA CYRILLIC ZE CON DISCENDENTE
 % LETTERA MINUSCOLA CYRILLIC IE
 % LETTERA MINUSCOLA CYRILLIC IE CON BREVE
 % LETTERA MINUSCOLA CYRILLIC IE UCRAINO
 % LETTERA MINUSCOLA CYRILLIC ZHE

Finalmente, la tabella dei pesi.

La sezione dei pesi è racchiusa in righe con parole chiave order_start e order_end. Ulteriori parametri order_start determinano in quale direzione vengono visualizzate le righe a ciascun livello di confronto. Di default viene utilizzato il parametro forward. Il corpo della sezione consiste in righe che contengono il codice del simbolo e i quattro pesi corrispondenti. Il codice del simbolo può essere rappresentato dal simbolo stesso, dal punto codice o da un nome simbolico definito in precedenza. I pesi possono essere assegnati anche a nomi simbolici, punti codice o simboli stessi. Se vengono utilizzati punti codice o simboli, il loro peso corrisponde al valore numerico del punto codice (posizione nella tabella Unicode). I simboli non specificati esplicitamente (come comprendo) sono considerati assegnati alla tabella con un peso primario corrispondente alla posizione nella tabella Unicode. Il valore speciale del peso IGNORE significa che a quel livello di confronto il simbolo corrispondente viene ignorato.

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

simboli che vengono completamente ignorati
simboli equivalenti al numero tre ai primi due livelli
l'inizio dell'alfabeto cirillico, che non contiene segni diacritici, quindi ordinato principalmente nei primi e terzi livelli.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % INIZIO INTITOLAZIONE (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % INIZIO TESTO (in 6429)
...
 ;;; % DIGITO TRE
 ;;; % DIGITO TRE IN FORMATO LARGHI
 ;;; % DIGITO TRE TRA LETTERE
 ;;; % DIGITO TRE PUNTO FINALE
 ;;; % DIGITO TRE BOLDO MATEMATICO
...
 ;;; % LETTERA CIRILLICA PICCOLA A
 ;;; % LETTERA CIRILLICA MAIUSCOLA A
 ;;; % LETTERA CIRILLICA PICCOLA A CON BREVIO
 ;;; % LETTERA CIRILLICA PICCOLA A CON BREVIO
...
 ;;; % LETTERA CIRILLICA PICCOLA BE
 ;;; % LETTERA CIRILLICA MAIUSCOLA BE
 ;;; % LETTERA CIRILLICA PICCOLA VE
 ;;; % LETTERA CIRILLICA MAIUSCOLA VE
...
order_end

Ora possiamo tornare all'ordinamento degli esempi dall'inizio dell'articolo. La trappola si nasconde proprio in questa parte della tabella dei pesi:

IGNORA;IGNORA;IGNORA; % SPAZIO
 IGNORA;IGNORA;IGNORA; % PUNTO ESCLAMATIVO
 IGNORA;IGNORA;IGNORA; % VIRGOLA
...

È evidente che in questa tabella i segni di punteggiatura provengono dalla tabella Rasterizzazione bit per bit o byte per byte (incluso gli spazi) durante il confronto delle stringhe viene praticamente sempre ignorato. L'unica eccezione sono le stringhe che coincidono in tutto, tranne che per i segni di punteggiatura, che si trovano nelle posizioni corrispondenti. Le stringhe del mio esempio (dopo l'ordinamento) per l'algoritmo di confronto appaiono così:

AbakanovMikhailpittore
YolkinaEllaGiornata
IvanovaAllamalz
IvanovAndreiFabbro

Tenendo conto che nella tabella dei pesi le lettere maiuscole in russo seguono quelle minuscole (al terzo livello <CAP> più pesante di <MIN>), l'ordinamento appare assolutamente corretto.

Durante l'impostazione della variabile LC_COLLATE=C viene caricata una particolare tabella, che definisce il confronto byte per byte

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  
  /* tabella di 1° livello */
  6 * sizeof (uint32_t),
  /* tabella di 2° livello */
  7 * sizeof (uint32_t),
  /* tabella di 3° livello */
  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'
};

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

Tabelle testuali e binarie

È evidente che il confronto delle stringhe è un'operazione estremamente comune, mentre l'analisi della tabella CTT è una procedura piuttosto costosa. Per ottimizzare l'accesso alla tabella, viene compilata in forma binaria tramite il comando localedef.

Team localedef accetta come parametri un file con la tabella delle peculiarità nazionali (opzione -i), in cui tutti i caratteri sono rappresentati da punti Unicode, e un file di corrispondenza tra i punti Unicode e i caratteri di una particolare codifica (opzione -f). A seguito dell'esecuzione vengono creati file binari per la locale, 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 locale sia il nome di una sottocartella in /usr/lib/locale/. In questa sottocartella sono memorizzati i file binari LC_COLLATE, LC_CTYPE, LC_TIME e così via. Il file LC_IDENTIFICATION contiene il nome formale della locale (che può differire dal nome della cartella) e commenti.

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

I file di input vengono cercati nella directory corrente e anche nelle directory /usr/share/i18n/locales/ e /usr/share/i18n/charmaps/ per i file CTT e per i file delle codifiche 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 imposti la variabile LANG=en_US.UTF-8 allora glibc cercerà 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 presenta sia nei formati tradizionali che moderni, si darà priorità al formato moderno.

Puoi visualizzare l'elenco delle locali compilate con il comando locale -a.

Preparazione della propria tabella di confronto

Ora, armati delle conoscenze, puoi creare la tua tabella ideale di confronto delle stringhe. Questa tabella deve confrontare correttamente le lettere russe, inclusa la lettera Ё, considerando anche la punteggiatura secondo la tabella Rasterizzazione bit per bit o byte per byte.

Il processo di preparazione della propria tabella di ordinamento consiste in due fasi: modifica della tabella dei pesi e compilazione in forma binaria con il comando localedef.

Per rendere la tabella di confronto facilmente modificabile con minimi costi di editing, nel formato ISO 14652 sono previste sezioni per la modifica dei pesi della tabella esistente. La sezione inizia con la parola chiave reorder-after e l'indicazione della posizione, dopo la quale avviene la sostituzione. La sezione termina con la 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 directory home ~/.local/share/i18n/locales/ e ho leggermente modificato la sezione LC_COLLATE in ru_RU. Le nuove versioni dei file sono completamente compatibili con la mia versione glibc. Se desideri utilizzare versioni precedenti dei file, dovrai cambiare i nomi simbolici e il punto in cui inizia la sostituzione nella tabella.

LC_COLLATE
% Copia il template da ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % SPAZIO
 ;;; % PUNTO ESCLAMATIVO
 ;;; % VIRGOLETTA
...
 ;;; % CORSO DESTRO
 ;;; % TILDE
reorder-end
END LC_COLLATE

In realtà, bisognerebbe cambiare i campi in LC_IDENTIFICATION in modo che puntino alla locale ru_MY, ma nel mio esempio non è stato necessario, poiché ho escluso dalla ricerca le locali dell'archivio locale-archive.

Per localedef lavorava con i file nella mia cartella tramite la variabile I18NPATH si può aggiungere una directory aggiuntiva per cercare i file di input, e la directory per salvare i file binari può essere specificata come un percorso con le barre:

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

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

Ecco il test decisivo:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Michail;pittore
Jolkina Ella;gruista
Ivanov Andrei;fabbro
Ivanova Alla;avvocato

Evviva! Ce l'abbiamo fatta!

Lavoro sugli errori

Ho già risposto alle domande sulla ordinamento delle righe, sollevate all'inizio, ma restano un paio di domande sugli errori — visibili e invisibili.

Torniamo al compito originale.

E il programma sort e il programma upgrade utilizzano le stesse funzioni di confronto delle stringhe da glibc. Come ha fatto quindi upgrade a generare un errore di ordinamento su righe ordinate dal comando sort nella locale en_US.UTF-8? Ответ прост: sort confronta l'intera stringa, mentre upgrade confronta solo la chiave, che per default è l'inizio della stringa fino al primo carattere di spazio. Nel mio esempio ciò ha portato a un messaggio di errore poiché l'ordinamento delle prime parole nelle righe non corrispondeva all'ordinamento delle righe intere.

La locale "C" garantisce che le sottostringhe iniziali fino al primo spazio siano anch'esse ordinate nelle righe ordinate, ma questo nasconde solo l'errore. È possibile trovare dati (persone con lo stesso cognome ma nomi diversi) che senza messaggi di errore darebbero un risultato errato nella fusione dei file. Se vogliamo che upgrade unisce le righe dei file per cognome e nome, il modo corretto è specificare esplicitamente il delimitatore dei campi e ordinare sulla chiave, non sull'intera stringa. In questo caso, sia la fusione andrà bene sia 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 a me note Linux nei pacchetti manca la locale compilata ru_RU.CP1251. Se la locale compilata non viene trovata, allora sort utilizza silenziosamente il confronto byte per byte, come abbiamo osservato.

A proposito, c'è un altro piccolo bug legato all'inaccessibilità delle locali compilate. Il comando LOCPATH=/tmp locale -a restituirà un elenco di tutte le locali in locale-archive, ma con la variabile impostata LOCPATH per tutti i programmi (incluso il locale) queste locali saranno inaccessibili.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Impossibile impostare LC_CTYPE sulla locale predefinita: nessun file o directory
locale: Impossibile impostare LC_MESSAGES sulla locale predefinita: nessun file o directory
locale: Impossibile impostare LC_COLLATE sulla locale predefinita: nessun file o directory
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 byte

Conclusione

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

Se sei un linguista o un redattore di dizionari, ti conviene compilare la tua locale.

Se sei un normale utente, ti basta abituarti 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 utilizza le proprie funzioni interne per l'ordinamento dei nomi, porta i file che iniziano con un punto all'inizio dell'elenco.