Introduzione

Tutto è iniziato con un breve script che avrebbe dovuto combinare le informazioni sull'indirizzo e-mail dipendenti ottenuti dall'elenco degli utenti della mailing list, con posizioni dei dipendenti ottenute dal database del dipartimento Risorse umane. Entrambi gli elenchi sono stati esportati in file di testo Unicode UTF-8 e salvato con terminazioni di riga Unix.

Contenuto mail.txt

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

Contenuto buhg.txt

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

Per unire, i file sono stati ordinati dal comando Unix sorta e sottoposto all'input del programma Unix join, che inaspettatamente non è riuscito con un errore:

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

Osservando con i tuoi occhi il risultato dell'ordinamento è emerso che, in generale, l'ordinamento è corretto, ma in caso di coincidenze tra cognomi maschili e femminili, quelli femminili vengono prima di quelli maschili:

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

Sembra un problema tecnico nell'ordinamento in Unicode o una manifestazione del femminismo nell'algoritmo di ordinamento. La prima è, ovviamente, più plausibile.

Mettiamolo da parte per ora join e concentrati su sorta. Proviamo a risolvere il problema usando il poking scientifico. Innanzitutto, cambiamo la lingua da it_IT su ru_RU. Per ordinare basterebbe impostare la variabile d'ambiente LC_COLLATE, ma non perderemo tempo in sciocchezze:

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

Niente è cambiato.

Proviamo a ricodificare 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 nulla è cambiato.

Non puoi fare nulla, dovrai cercare una soluzione su Internet. Non c'è nulla che riguardi direttamente i cognomi russi, ma ci sono domande su altre stranezze di ordinamento. Ad esempio, ecco un problema: Unix sort tratta i caratteri '-' (trattino) come invisibili. In breve, le stringhe "ab", "aa", "ac" vengono ordinate come "aa", "ab", "ac".

La risposta è standard ovunque: utilizzare la locale del programmatore "C" e sarai felice. Proviamo:

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

Qualcosa è cambiato. Gli Ivanov si schierarono nell'ordine corretto, anche se Yolkina scivolò da qualche parte. Torniamo al problema 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 Yolkina in prima linea.

Il problema sembra essere risolto, ma per ogni evenienza, proviamo un'altra codifica russa: Windows CP1251:

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

Il risultato dell'ordinamento, stranamente, coinciderà con la locale "C"e l'intero esempio, di conseguenza, viene eseguito senza errori. Una sorta di misticismo.

Non mi piace il misticismo nella programmazione perché di solito maschera gli errori. Dovremo esaminare seriamente come funziona. sorta e cosa influisce? LC_COLLATE .

Alla fine cercherò di rispondere alle domande:

perché i cognomi femminili sono stati ordinati in modo errato?
perché LANG=ru_RU.CP1251 si è rivelato equivalente LINGUA=C
perchè fare sorta и join idee diverse sull'ordine delle stringhe ordinate
perché ci sono errori in tutti i miei esempi?
finalmente come ordinare le stringhe a tuo piacimento

Ordinamento in Unicode

La prima tappa sarà la relazione tecnica n. 10 dal titolo Algoritmo di confronto Unicode on-line unicode.org. La relazione contiene numerosi dettagli tecnici, pertanto consentitemi di riassumere brevemente le idee principali.

Confronto — Il “confronto” delle stringhe è la base di qualsiasi algoritmo di ordinamento. Gli algoritmi stessi possono differire ("bolla", "unione", "veloce"), ma utilizzeranno tutti il confronto di una coppia di stringhe per determinare l'ordine in cui appariranno.

L'ordinamento delle stringhe in linguaggio naturale è un problema abbastanza complesso. Anche nelle più semplici codifiche a byte singolo, l'ordine delle lettere dell'alfabeto, anche in qualche modo diverso dall'alfabeto latino inglese, non coinciderà più con l'ordine dei valori numerici con cui queste lettere sono codificate. Quindi nell'alfabeto tedesco la lettera Ö sta in mezzo О и Pe nella codifica CP850 lei si mette in mezzo ÿ и Ü.

Puoi provare ad astrarre da una codifica specifica e considerare le lettere "ideali" che sono disposte in un certo ordine, come avviene in Unicode. Codifiche UTF8, UTF16 o un byte KOI8-R (se è necessario un sottoinsieme limitato di Unicode) fornirà diverse rappresentazioni numeriche delle lettere, ma farà riferimento agli stessi elementi della tabella base.

Si scopre che anche se costruiamo una tabella di simboli da zero, non saremo in grado di assegnarle un ordine di simboli universale. Nei diversi alfabeti nazionali che utilizzano le stesse lettere, l'ordine di queste lettere può differire. Ad esempio, in francese Æ sarà considerata una legatura e ordinata come una stringa AE. In norvegese Æ sarà una lettera separata, che si trova dopo Z. A proposito, oltre alle legature come Æ Ci sono lettere scritte con diversi simboli. Quindi nell'alfabeto ceco c'è una lettera Ch, che si trova in mezzo H и I.

Oltre alle differenze negli alfabeti, ci sono altre tradizioni nazionali che influenzano lo smistamento. In particolare, sorge la domanda: in quale ordine devono apparire nel dizionario le parole composte da lettere maiuscole e minuscole? L'ordinamento può essere influenzato anche dall'uso dei segni di punteggiatura. In spagnolo si usa il punto interrogativo capovolto all'inizio della frase interrogativa (Ti piace la musica?). In questo caso, è ovvio che le frasi interrogative non dovrebbero essere raggruppate in un gruppo separato al di fuori dell'alfabeto, ma come ordinare le righe con altri segni di punteggiatura?

Non mi dilungherò sull’ordinamento delle stringhe in lingue molto diverse da quelle europee. Si noti che nelle lingue con direzione di scrittura da destra a sinistra o dall'alto in basso, i caratteri nelle righe sono molto probabilmente memorizzati in ordine di lettura e anche i sistemi di scrittura non alfabetici hanno i propri modi di ordinare le righe carattere per carattere . Ad esempio, i geroglifici possono essere ordinati per stile (Tasti dei caratteri cinesi) o dalla pronuncia. Ad essere onesti, non ho idea di come dovrebbero essere organizzati gli emoji, ma puoi inventare qualcosa anche per loro.

Sulla base delle caratteristiche sopra elencate sono stati formulati i requisiti fondamentali per il confronto di stringhe basate su tabelle Unicode:

il confronto delle stringhe non dipende dalla posizione dei caratteri nella tabella dei codici;
sequenze di caratteri che formano un unico carattere sono ridotte alla forma canonica (A + il cerchio superiore è lo stesso di Å);
Quando si confrontano stringhe, un carattere viene considerato nel contesto della stringa e, se necessario, combinato con i suoi vicini in un'unità di confronto (Ch in ceco) o è diviso in più (Æ in francese);
tutte le funzionalità nazionali (alfabeto, maiuscolo/minuscolo, punteggiatura, ordine dei tipi di scrittura) dovranno essere configurate fino all'assegnazione manuale dell'ordine (emoji);
il confronto è importante non solo per l'ordinamento, ma anche in molti altri posti, ad esempio per specificare intervalli di righe (sostituendo {A... z} in bash);
il confronto dovrebbe essere fatto abbastanza velocemente.

Inoltre, gli autori del rapporto hanno formulato proprietà di confronto su cui gli sviluppatori di algoritmi non dovrebbero fare affidamento:

l'algoritmo di confronto non dovrebbe richiedere un set separato di caratteri per ciascuna 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 contesti culturali diversi può avere pesi diversi;
i pesi delle righe possono cambiare durante l'unione o la divisione (da x < y non ne consegue questo xz < yz);
stringhe diverse che hanno gli stessi pesi sono considerate uguali dal punto di vista dell'algoritmo di ordinamento. È possibile introdurre un ulteriore ordinamento di tali stringhe, ma ciò potrebbe ridurre le prestazioni;
Durante l'ordinamento ripetuto, le righe con lo stesso peso potrebbero essere scambiate. La robustezza è una proprietà di uno specifico algoritmo di ordinamento e non una proprietà di un algoritmo di confronto di stringhe (vedere il paragrafo precedente);
Le regole di smistamento possono cambiare nel tempo man mano che le tradizioni culturali si affinano/cambiano.

Si presuppone inoltre che l'algoritmo di confronto non sappia nulla della semantica delle stringhe elaborate. Pertanto, le stringhe costituite solo da cifre non dovrebbero essere confrontate come numeri e negli elenchi di nomi inglesi l'articolo (Beatles, Il).

Per soddisfare tutti questi requisiti, viene proposto un algoritmo di ordinamento delle tabelle multi-livello (in realtà quattro livelli).

In precedenza, i caratteri nella stringa venivano ridotti alla forma canonica e raggruppati in unità di confronto. A ciascuna unità di confronto vengono assegnati diversi pesi corrispondenti a diversi livelli di confronto. I pesi delle unità di confronto sono elementi di insiemi ordinati (in questo caso numeri interi) che possono essere confrontati in più o in meno. Significato speciale IGNORATO (0x0) significa che al livello di confronto corrispondente questa unità non è coinvolta nel confronto. Il confronto delle stringhe può essere ripetuto più volte, utilizzando i pesi dei livelli corrispondenti. Ad ogni livello, i pesi delle unità di confronto di due righe vengono confrontati in sequenza tra loro.

Nelle diverse implementazioni dell'algoritmo per le diverse tradizioni nazionali, i valori dei coefficienti possono differire, ma lo standard Unicode include una tabella di pesi di base - "Tabella degli elementi di confronto Unicode predefinita" (DUCETTO). Vorrei notare che l'impostazione della variabile LC_COLLATE è in realtà un'indicazione della selezione della tabella dei pesi nella funzione di confronto delle stringhe.

Coefficienti di ponderazione DUCETTO disposti come segue:

al primo livello tutte le lettere vengono ridotte allo stesso caso, i segni diacritici vengono scartati, i segni di punteggiatura (non tutti) vengono ignorati;
al secondo livello vengono presi in considerazione solo i segni diacritici;
al terzo livello viene preso in considerazione solo il caso;
al quarto livello vengono presi in considerazione solo i segni di punteggiatura.

Il confronto avviene in più passaggi: dapprima vengono confrontati i coefficienti del primo livello; se i pesi coincidono viene effettuato un confronto ripetuto con i pesi di secondo livello; poi forse un terzo e un quarto.

Il confronto termina quando le righe contengono unità di confronto corrispondenti con pesi diversi. Le righe che hanno lo stesso peso 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 - "Algoritmo di collazione Unicode" (ACU).

È qui che il comportamento di ordinamento del nostro esempio diventa un po' più chiaro. Sarebbe bello confrontarlo con lo standard Unicode.

Per testare le implementazioni ACU c'è uno speciale test, utilizzando cartella dei pesi, implementando DUCETTO. Puoi trovare ogni sorta di cose divertenti nel file delle scale. Ad esempio, esiste l'ordine del mahjong e del domino europeo, nonché l'ordine dei semi in un mazzo di carte (simbolo 1F000 e inoltre). I semi delle carte vengono posizionati secondo le regole del bridge - PCBT, e le carte del seme sono nella sequenza T, 2,3, XNUMX... K.

Verificando manualmente che le righe siano ordinate correttamente in base a DUCETTO sarebbe piuttosto noioso, ma, fortunatamente per noi, esiste un'implementazione esemplare della libreria per lavorare con Unicode - "Componenti internazionali per Unicode"(ICU).

Sul sito web di questa biblioteca, sviluppato in IBM, ci sono pagine demo, tra cui pagina dell'algoritmo di confronto delle stringhe. Inseriamo le nostre linee di prova con le impostazioni predefinite e, ecco, otteniamo un perfetto ordinamento russo.

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

A proposito, il sito web ICU Puoi trovare un chiarimento sull'algoritmo di confronto durante l'elaborazione dei segni di punteggiatura. Negli esempi Domande frequenti sulla raccolta l'apostrofo e il trattino vengono ignorati.

Unicode ci ha aiutato, ma cerca le ragioni di un comportamento strano sorta в Linux dovrà andare da qualche altra parte.

Ordinamento in glibc

Visualizzazione rapida dei codici sorgente delle utenze sorta di Utilità principali GNU ha dimostrato che nell'utilità stessa la localizzazione si riduce alla stampa del valore corrente della variabile LC_COLLATE durante l'esecuzione in modalità debug:

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

I confronti tra stringhe vengono eseguiti utilizzando la funzione standard strcoll, il che significa che tutto ciò che è interessante è nella biblioteca glibc.

Su wiki progetto glibc dedicato al confronto tra stringhe un paragrafo. Da questo paragrafo si può comprendere che in glibc l'ordinamento si basa su un algoritmo a noi già noto ACU (L'algoritmo di confronto Unicode) e/o ad uno standard ad esso prossimo ISO 14651 (Ordinamento e confronto internazionale delle stringhe). Per quanto riguarda lo standard più recente, va notato che sul sito standard.iso.org ISO 14651 dichiarato ufficialmente disponibile al pubblico, ma il collegamento corrispondente porta a una pagina inesistente. Google restituisce diverse pagine con collegamenti a siti ufficiali che offrono di acquistare una copia elettronica dello standard per cento euro, ma nella terza o quarta pagina dei risultati di ricerca si trovano anche collegamenti diretti a PDF. In generale, lo standard non è praticamente diverso da ACU, ma è più noioso da leggere perché non contiene esempi chiari delle caratteristiche nazionali dell'ordinamento delle stringhe.

Le informazioni più interessanti su wiki c'era un collegamento a localizzatore di bug con una discussione sull'implementazione del confronto tra stringhe in glibc. Dalla discussione si apprende questo glibc utilizzato per confrontare le stringhe ISOtavolo personale La tabella dei modelli comuni (CTT), il cui indirizzo figura nella domanda A standard ISO 14651. Tra il 2000 e il 2015 questa tabella è entrata glibc non aveva un manutentore ed era abbastanza diverso (almeno esternamente) dalla versione attuale dello standard. Dal 2015 al 2018 ha avuto luogo l'adattamento alla nuova versione del tavolo e ora hai la possibilità di incontrare nella vita reale una nuova versione del tavolo (8 CentOS) e vecchio (7 CentOS).

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

Codice sorgente della tabella che ci interessa CTT sulla maggior parte delle distribuzioni Linux è in catalogo /usr/share/i18n/locales/. La tabella stessa è nel file iso14651_t1_common. Allora questa è la direttiva file copia iso14651_t1_common incluso nel fascicolo iso14651_t1, che, a sua volta, è incluso nei fascicoli nazionali, compresi it_IT и ru_RU. Sulla maggior parte delle distribuzioni Linux tutti i file sorgente sono inclusi nell'installazione base, ma se non sono presenti dovrai installare un pacchetto aggiuntivo dalla distribuzione.

Struttura dei file iso14651_t1 può sembrare terribilmente prolisso, con regole non ovvie per costruire i nomi, ma se lo guardi, tutto è abbastanza semplice. La struttura è descritta nella norma ISO 14652, una copia del quale può essere scaricata dal sito open-std.org. È possibile leggere un'altra descrizione del formato del file specificazioni POSIX от OpenGroup. In alternativa alla lettura dello standard, puoi studiare il codice sorgente della funzione fascicolare_leggere в glibc/locale/programs/ld-collate.c.

La struttura del file è simile alla seguente:

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

escape_char /
comment_char %

Il file conterrà token nel formato o (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 (incluso , e simili) sono considerate semplici costanti di stringa che hanno poco significato al di fuori del contesto.

fila LC_COLLATE ci dice che poi iniziano i dati che descrivono il confronto delle stringhe.

Innanzitutto vengono specificati i nomi per i pesi nella tabella comparativa e i nomi per le combinazioni di simboli. In generale le due tipologie di nomi appartengono a due entità diverse, ma nel fascicolo vero e proprio sono mescolate. I nomi dei pesi sono specificati dalla parola chiave simbolo-collating (carattere di confronto) perché durante il confronto, i caratteri Unicode che hanno lo stesso peso verranno considerati caratteri equivalenti.

La lunghezza totale della sezione nella revisione del file corrente è di circa 900 righe. Ho estratto esempi da diversi posti per mostrare l'arbitrarietà dei nomi e diversi tipi di sintassi.

LC_COLLATE

collating-symbol <RES-1>
collating-symbol <BLK>
collating-symbol <MIN>
collating-symbol <WIDE>
...
collating-symbol <ARABIC>
collating-symbol <ETHPC>
collating-symbol <OSMANYA>
...
collating-symbol <S1D000>..<S1D35F>
collating-symbol <SFFFF> % Guaranteed largest symbol value. Keep at end of this list
...
collating-element <U0413_0301> from "<U0413><U0301>"
collating-element <U0413_0341> from "<U0413><U0341>"

simbolo di raccolta registra una stringa OSMANYA nella tabella dei nomi delle scale
simbolo di raccolta .. registra una sequenza di nomi composta da un prefisso S e suffisso numerico esadecimale da 1D000 a 1G35F.
FFFF в simbolo di raccolta sembra un grande intero senza segno in formato esadecimale, ma è solo un nome che potrebbe assomigliare
nome significa punto di codice nella codifica UCS-4
elemento di raccolta da " " registra un nuovo nome per una coppia di punti Unicode.

Una volta definiti i nomi dei pesi, vengono specificati i pesi effettivi. Poiché nel confronto contano solo le relazioni maggiore o minore, i pesi sono determinati da una semplice sequenza di nomi elencati. Vengono elencati prima i pesi “più leggeri”, poi quelli “più pesanti”. Lascia che ti ricordi che a ogni carattere Unicode vengono assegnati quattro pesi diversi. Qui sono combinati in un'unica sequenza ordinata. In teoria, qualsiasi nome simbolico potrebbe essere utilizzato in uno qualsiasi dei quattro livelli, ma i commenti indicano che gli sviluppatori separano mentalmente i nomi in livelli.

% Symbolic weight assignments

% Third-level weight assignments
<RES-1>
<BLK>
<MIN>
<WIDE>
...
% Second-level weight assignments
<BASE>
<LOWLINE> % COMBINING LOW LINE
<PSILI> % COMBINING COMMA ABOVE
<DASIA> % COMBINING REVERSED COMMA ABOVE
...
% First-level weight assignments
<S0009> % HORIZONTAL TABULATION 
<S000A> % LINE FEED
<S000B> % VERTICAL TABULATION
...
<S0434> % CYRILLIC SMALL LETTER DE
<S0501> % CYRILLIC SMALL LETTER KOMI DE
<S0452> % CYRILLIC SMALL LETTER DJE
<S0503> % CYRILLIC SMALL LETTER KOMI DJE
<S0453> % CYRILLIC SMALL LETTER GJE
<S0499> % CYRILLIC SMALL LETTER ZE WITH DESCENDER
<S0435> % CYRILLIC SMALL LETTER IE
<S04D7> % CYRILLIC SMALL LETTER IE WITH BREVE
<S0454> % CYRILLIC SMALL LETTER UKRAINIAN IE
<S0436> % CYRILLIC SMALL LETTER ZHE

Infine, la tabella dei pesi effettivi.

La sezione dei pesi è racchiusa tra le righe delle parole chiave ordine_inizio и fine_ordine. Opzioni aggiuntive ordine_inizio determinare in quale direzione vengono scansionate le righe a ciascun livello di confronto. L'impostazione predefinita è inoltrare. Il corpo della sezione è costituito da righe che contengono il codice del simbolo e i suoi quattro pesi. Il codice carattere può essere rappresentato dal carattere stesso, da un punto di codice o da un nome simbolico definito in precedenza. È inoltre possibile assegnare pesi a nomi simbolici, punti di codice o ai simboli stessi. Se vengono utilizzati punti di codice o caratteri, il loro peso è uguale al valore numerico del punto di codice (posizione nella tabella Unicode). I caratteri non specificati esplicitamente (a quanto ho capito) sono considerati assegnati alla tabella con un peso primario che corrisponde alla posizione nella tabella Unicode. Valore di peso speciale IGNORARE significa che il simbolo viene ignorato al livello di confronto appropriato.

Per dimostrare la struttura delle scale, ho scelto tre frammenti abbastanza evidenti:

personaggi completamente ignorati
simboli equivalenti al numero tre nei primi due livelli
l'inizio dell'alfabeto cirillico, che non contiene segni diacritici, e quindi è ordinato principalmente dal primo e dal terzo livello.

order_start forward;forward;forward;forward,position
<U0000> IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
<U0001> IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
<U0002> IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
<U0033> <S0033>;<BASE>;<MIN>;<U0033> % DIGIT THREE
<UFF13> <S0033>;<BASE>;<WIDE>;<UFF13> % FULLWIDTH DIGIT THREE
<U2476> <S0033>;<BASE>;<COMPAT>;<U2476> % PARENTHESIZED DIGIT THREE
<U248A> <S0033>;<BASE>;<COMPAT>;<U248A> % DIGIT THREE FULL STOP
<U1D7D1> <S0033>;<BASE>;<FONT>;<U1D7D1> % MATHEMATICAL BOLD DIGIT THREE
...
<U0430> <S0430>;<BASE>;<MIN>;<U0430> % CYRILLIC SMALL LETTER A
<U0410> <S0430>;<BASE>;<CAP>;<U0410> % CYRILLIC CAPITAL LETTER A
<U04D1> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
<U0430_0306> <S04D1>;<BASE>;<MIN>;<U04D1> % CYRILLIC SMALL LETTER A WITH BREVE
...
<U0431> <S0431>;<BASE>;<MIN>;<U0431> % CYRILLIC SMALL LETTER BE
<U0411> <S0431>;<BASE>;<CAP>;<U0411> % CYRILLIC CAPITAL LETTER BE
<U0432> <S0432>;<BASE>;<MIN>;<U0432> % CYRILLIC SMALL LETTER VE
<U0412> <S0432>;<BASE>;<CAP>;<U0412> % CYRILLIC CAPITAL LETTER VE
...
order_end

Ora puoi tornare a ordinare gli esempi dall'inizio dell'articolo. L’agguato sta in questa parte della tabella dei pesi:

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

Si può vedere che in questa tabella i segni di punteggiatura della tabella ASCII (incluso lo spazio) viene quasi sempre ignorato quando si confrontano le stringhe. Le uniche eccezioni sono le linee che corrispondono in tutto tranne i segni di punteggiatura trovati nelle posizioni corrispondenti. Le righe del mio esempio (dopo l'ordinamento) per l'algoritmo di confronto assomigliano a queste:

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

Considerando che nella tabella delle scale le maiuscole in russo vengono dopo le minuscole (al terzo livello piu pesante di ), l'ordinamento sembra assolutamente corretto.

Quando si imposta una variabile LC_COLLATE=C viene caricata una tabella speciale che specifica un 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'xfe', L'xff'
};

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

Tabelle di testo e binarie

Ovviamente, il confronto delle stringhe è un'operazione estremamente comune e l'analisi delle tabelle CTT una procedura piuttosto costosa. Per ottimizzare l'accesso alla tabella, questa viene compilata in forma binaria con il comando localdef.

Squadra localdef accetta come parametri un file con una tabella delle caratteristiche nazionali (opzione -i), in cui tutti i caratteri sono rappresentati da punti Unicode, e un file di corrispondenza tra punti Unicode e caratteri di una specifica codifica (opzione -f). Come risultato del lavoro, 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 significa che il nome della locale è il nome della sottodirectory in /usr/lib/locale/. Questa sottodirectory memorizza i file binari LC_COLLATE, LC_CTYPE, LC_TIME e così via. File LC_IDENTIFICAZIONE contiene il nome formale della locale (che può essere diverso dal nome della directory) e commenti.

Il formato moderno prevede la memorizzazione di tutte le versioni locali in un unico archivio /usr/lib/locale/archivio-locale, che è mappato sulla memoria virtuale di tutti i processi che utilizzano glibc. Il nome locale nel formato moderno è soggetto a qualche canonizzazione: nei nomi di codifica rimangono solo numeri e lettere ridotti in minuscolo. COSÌ ru_RU.KOI8-R, verrà salvato come ru_RU.koi8r.

I file di input vengono cercati nella directory corrente, così come nelle directory /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ per i file CTT e la codifica dei file, 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 salva il risultato in /usr/lib/locale/archivio-locale sotto il nome ru_RU.maccyrillic

Se imposti la variabile LANG = en_US.UTF-8 che glibc cercherà i binari locali 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 una localizzazione è presente sia nel formato tradizionale che in quello moderno, la priorità viene data a quella moderna.

È possibile visualizzare l'elenco delle versioni locali compilate con il comando locale -a.

Preparare la tabella comparativa

Ora, armato di queste conoscenze, puoi creare la tua tabella di confronto delle stringhe ideale. Questa tabella dovrebbe confrontare correttamente le lettere russe, inclusa la lettera Ё, e allo stesso tempo tenere conto dei segni di punteggiatura secondo la tabella ASCII.

Il processo di preparazione della propria tabella di ordinamento consiste in due fasi: modificare la tabella dei pesi e compilarla in forma binaria con il comando localdef.

Affinché la tabella comparativa possa essere adattata con costi di modifica minimi, nel formato ISO 14652 Vengono fornite le sezioni per la regolazione dei pesi di una tabella esistente. La sezione inizia con una parola chiave riordinare dopo e indicante la posizione dopo la quale viene effettuata la sostituzione. La sezione termina con la riga fine riordino. Se è necessario correggere più sezioni della tabella, viene creata una sezione per ciascuna di queste sezioni.

Ho copiato le nuove versioni dei file iso14651_t1_common и ru_RU dal deposito glibc nella mia directory home ~/.local/share/i18n/locales/ e ho leggermente modificato la sezione LC_COLLATE в ru_RU. Le nuove versioni dei file sono completamente compatibili con la mia versione glibc. Se desideri utilizzare versioni precedenti dei file, dovrai modificare i nomi simbolici e il punto in cui inizia la sostituzione nella tabella.

LC_COLLATE
% Copy the template from ISO/IEC 14651
copy "iso14651_t1"
reorder-after <U000D>
<U0020> <S0020>;<BASE>;<MIN>;<U0020> % SPACE
<U0021> <S0021>;<BASE>;<MIN>;<U0021> % EXCLAMATION MARK
<U0022> <S0022>;<BASE>;<MIN>;<U0022> % QUOTATION MARK
...
<U007D> <S007D>;<BASE>;<MIN>;<U007D> % RIGHT CURLY BRACKET
<U007E> <S007E>;<BASE>;<MIN>;<U007E> % TILDE
reorder-end
END LC_COLLATE

Sarebbe infatti necessario modificare i campi in LC_IDENTIFICAZIONE in modo che indichino la località ru_MY, ma nel mio esempio ciò non era richiesto, poiché ho escluso l'archivio dalla ricerca delle localizzazioni locale-archivio.

Che localdef ha lavorato con i file nella mia cartella tramite una variabile I18 NPATH Puoi aggiungere un'ulteriore directory per cercare i file di input e la directory in cui salvare i file binari può essere specificata come un percorso con barre:

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

POSIX presuppone che in LUNGO puoi scrivere percorsi assoluti alle directory con file locali, iniziando con una barra, ma glibc в Linux tutti i percorsi vengono contati dalla directory di base, che può essere sovrascritta tramite una variabile LOCPATH. Dopo l'installazione LOCPATH=~/.local/lib/locale/ tutti i file relativi alla localizzazione verranno cercati solo nella mia cartella. Archivio delle localizzazioni con la variabile set LOCPATH ignorato.

Ecco la prova decisiva:

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

Evviva! Ce l'abbiamo fatta!

Alcuni errori

Ho già risposto alle domande poste all'inizio sull'ordinamento delle stringhe, ma ci sono ancora un paio di domande sugli errori, visibili e invisibili.

Torniamo al problema originale.

E il programma sorta e programma join utilizzare le stesse funzioni di confronto delle stringhe da glibc. Come è successo? join ha dato un errore di ordinamento sulle righe ordinate dal comando sorta nel locale it_IT.UTF-8? La risposta è semplice: sorta confronta l'intera stringa e join confronta solo la chiave, che per impostazione predefinita è l'inizio della stringa fino al primo carattere di spazio. Nel mio esempio ciò ha provocato un messaggio di errore perché l'ordinamento delle prime parole nelle righe non corrispondeva all'ordinamento delle righe complete.

Locale "C" garantisce che nelle stringhe ordinate verranno ordinate anche le sottostringhe iniziali fino al primo spazio, ma questo maschera solo l'errore. È possibile selezionare dati (persone con gli stessi cognomi, ma nomi diversi) che, senza il messaggio di errore, darebbero un risultato errato della fusione dei file. Se vogliamo join righe di file unite in base al nome completo, il modo corretto sarebbe specificare esplicitamente il separatore di campo e ordinare in base al campo chiave e non all'intera riga. In questo caso, l'unione procederà correttamente e non ci saranno errori in nessuna lingua:

$> 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 correttamente nella codifica CP1251 contiene un altro errore. Il fatto è che in tutte le distribuzioni a me conosciute Linux ai pacchetti manca la locale compilata ru_RU.CP1251. Se la locale compilata non viene trovata, allora sorta utilizza silenziosamente un confronto byte per byte, che è ciò che abbiamo osservato.

A proposito, c'è un altro piccolo problema legato all'inaccessibilità delle localizzazioni compilate. Squadra LOCPATH=/tmp locale -a fornirà un elenco di tutte le località in locale-archivio, ma con la variabile impostata LOCPATH per tutti i programmi (incluso il most località) queste impostazioni locali non saranno disponibili.

$> LOCPATH=/tmp locale -a | grep en_US
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_COLLATE to default locale: No such file or directory
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: using ‘en_US.UTF-8’ sorting rules

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: using simple byte comparison

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 compilatore di dizionari, è meglio compilare nella tua locale.

Se sei un utente semplice, devi solo abituarti al fatto che il comando ls -a restituisce file che iniziano con un punto mescolati con file che iniziano con una lettera e Comandante di mezzanotte, che utilizza le sue funzioni interne per ordinare i nomi, inserisce i file che iniziano con un punto all'inizio dell'elenco.