Introducció

Tot va començar amb un script breu que se suposava que combinava la informació de l'adreça e-mail empleats obtinguts de la llista d'usuaris de la llista de correu, amb llocs d'empleats obtinguts de la base de dades del departament de recursos humans. Ambdues llistes es van exportar a fitxers de text Unicode UTF-8 i desat amb els finals de línia Unix.

Contingut mail.txt

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

Contingut buhg.txt

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

Per combinar, els fitxers es van ordenar mitjançant l'ordre Unix sort i s'envia a l'entrada del programa Unix unir-se, que va fallar inesperadament amb un error:

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

Vist el resultat de la classificació amb els teus ulls demostra que, en general, l'ordenació és correcta, però en el cas de coincidències de cognoms masculins i femenins, els femenins van abans que els masculins:

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

Sembla un error d'ordenació a Unicode o una manifestació del feminisme a l'algorisme de classificació. El primer és, per descomptat, més plausible.

De moment, deixem-ho unir-se i centrar-se en sort. Intentem resoldre el problema fent servir la ciència científica. Primer, canviem la configuració regional de ca_ES en ca_ES. Per ordenar, n'hi hauria prou amb establir la variable d'entorn LC_COLLATE, però no perdrem el temps amb petiteses:

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

Res ha canviat.

Intentem recodificar els fitxers en una codificació d'un sol byte:

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

De nou no ha canviat res.

No pots fer res, hauràs de buscar una solució a Internet. No hi ha res directament sobre els cognoms russos, però hi ha preguntes sobre altres rareses de classificació. Per exemple, aquí hi ha un problema: Unix sort tracta els caràcters '-' (guionet) com a invisibles. En resum, les cadenes "ab", "aa", "ac" s'ordenen com a "aa", "ab", "ac".

La resposta és estàndard a tot arreu: utilitzeu la configuració regional del programador "C" i seràs feliç. Anem a provar:

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

Alguna cosa ha canviat. Els Ivanov es van alinear en l'ordre correcte, tot i que Yolkina va caure en algun lloc. Tornem al problema original:

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

Va funcionar sense errors, com prometia Internet. I això malgrat Yolkina a la primera línia.

Sembla que el problema s'ha resolt, però per si de cas, provem una altra codificació russa: Windows CP1251:

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

El resultat de la classificació, curiosament, coincidirà amb la configuració regional "C", i tot l'exemple, en conseqüència, s'executa sense errors. Alguna mena de misticisme.

No m'agrada el misticisme a la programació perquè acostuma a emmascarar els errors. Haurem de mirar seriosament com funciona. sort i què afecta? LC_COLLATE .

Al final intentaré respondre les preguntes:

per què es van ordenar incorrectament els cognoms femenins?
per què LANG=ru_RU.CP1251 va resultar ser equivalent LANG=C
per què fer sort и unir-se idees diferents sobre l'ordre de les cadenes ordenades
per què hi ha errors en tots els meus exemples?
finalment com ordenar les cadenes al vostre gust

Ordenació en Unicode

La primera parada serà l'informe tècnic núm. 10 titulat Algorisme de col·lació Unicode en línia unicode.org. L'informe conté molts detalls tècnics, així que permeteu-me fer un breu resum de les idees principals.

col·lació — "comparar" cadenes és la base de qualsevol algorisme d'ordenació. Els propis algorismes poden diferir ("bombolla", "fusionar", "ràpid"), però tots utilitzaran una comparació d'un parell de cadenes per determinar l'ordre en què apareixen.

Ordenar cadenes en llenguatge natural és un problema força complex. Fins i tot en les codificacions d'un sol byte més senzilles, l'ordre de les lletres de l'alfabet, fins i tot d'alguna manera diferent de l'alfabet llatí anglès, ja no coincidirà amb l'ordre dels valors numèrics amb què es codifiquen aquestes lletres. Així que en l'alfabet alemany la lletra Ö es troba entre О и P, i en la codificació CP850 ella es posa entre ÿ и Ü.

Podeu provar d'abstraure's d'una codificació específica i considerar les lletres "ideals" que estan disposades en algun ordre, com es fa a Unicode. Codificacions UTF8, UTF16 o d'un byte KOI8-R (si es necessita un subconjunt limitat d'Unicode) donarà diferents representacions numèriques de lletres, però es refereixen als mateixos elements de la taula base.

Resulta que fins i tot si construïm una taula de símbols des de zero, no podrem assignar-li un ordre de símbols universal. En diferents alfabets nacionals que utilitzen les mateixes lletres, l'ordre d'aquestes lletres pot ser diferent. Per exemple, en francès Æ es considerarà una lligadura i ordenada com una corda AE. En noruec Æ serà una lletra separada, que es troba després Z. Per cert, a més de lligadures com Æ Hi ha lletres escrites amb diversos símbols. Així que a l'alfabet txec hi ha una lletra Ch, que es troba entre H и I.

A més de les diferències en els alfabets, hi ha altres tradicions nacionals que influeixen en la classificació. En particular, sorgeix la pregunta: en quin ordre haurien d'aparèixer al diccionari les paraules que consisteixen en lletres majúscules i minúscules? L'ordenació també es pot veure afectada per l'ús de signes de puntuació. En castellà s'utilitza un signe d'interrogació invertit al començament d'una frase interrogativa (T'agrada la música?). En aquest cas, és obvi que les frases interrogatives no s'han d'agrupar en un grup separat fora de l'alfabet, però com ordenar les línies amb altres signes de puntuació?

No em detendré en ordenar cadenes en idiomes molt diferents dels europeus. Tingueu en compte que en els idiomes amb una direcció d'escriptura de dreta a esquerra o de dalt a baix, és probable que els caràcters de les línies s'emmagatzemen en ordre de lectura, i fins i tot els sistemes d'escriptura no alfabètics tenen les seves pròpies maneres d'ordenar les línies caràcter per caràcter. . Per exemple, els jeroglífics es poden ordenar per estil (Tecles de caràcters xinesos) o per la pronunciació. Per ser sincer, no tinc ni idea de com s'han d'organitzar els emojis, però també pots proposar-los alguna cosa.

A partir de les característiques enumerades anteriorment, es van formular els requisits bàsics per comparar cadenes basades en taules Unicode:

la comparació de cadenes no depèn de la posició dels caràcters a la taula de codis;
les seqüències de caràcters que formen un sol caràcter es redueixen a la forma canònica (A + el cercle superior és el mateix que Å);
Quan es comparen cadenes, es considera un caràcter en el context de la cadena i, si cal, es combina amb els seus veïns en una unitat de comparació (Ch en txec) o es divideix en diversos (Æ en francès);
totes les característiques nacionals (alfabet, majúscules/minúscules, puntuació, tipus d'ordre d'escriptura) s'han de configurar fins a l'assignació manual de l'ordre (emoji);
la comparació és important no només per ordenar, sinó també en molts altres llocs, per exemple per especificar rangs de files (substituint {A... z} a colpejar);
la comparació s'ha de fer amb força rapidesa.

A més, els autors de l'informe van formular propietats de comparació en què els desenvolupadors d'algoritmes no haurien de confiar:

l'algorisme de comparació no hauria de requerir un conjunt separat de caràcters per a cada idioma (els idiomes rus i ucraïnès comparteixen la majoria de caràcters ciríl·lics);
la comparació no hauria de dependre de l'ordre dels caràcters de les taules Unicode;
el pes de la cadena no hauria de ser un atribut de la cadena, ja que la mateixa cadena en diferents contextos culturals pot tenir pes diferents;
els pesos de les files poden canviar en combinar o dividir (des de x < y això no segueix xz < yz);
diferents cadenes que tenen els mateixos pesos es consideren iguals des del punt de vista de l'algorisme d'ordenació. És possible introduir un ordre addicional d'aquestes cadenes, però pot degradar el rendiment;
Durant l'ordenació repetida, es poden intercanviar files amb els mateixos pesos. La robustesa és una propietat d'un algorisme d'ordenació específic, i no una propietat d'un algorisme de comparació de cadenes (vegeu el paràgraf anterior);
Les regles d'ordenació poden canviar amb el temps a mesura que les tradicions culturals es perfeccionen/canvien.

També s'estipula que l'algoritme de comparació no sap res sobre la semàntica de les cadenes que s'estan processant. Així, les cadenes que consisteixen només en dígits no s'han de comparar com a nombres, i a les llistes de noms en anglès l'article (Beatles, The).

Per tal de satisfer tots els requisits especificats, es proposa un algorisme d'ordenació de taules de diversos nivells (en realitat de quatre nivells).

Anteriorment, els caràcters de la cadena es redueixen a la forma canònica i s'agrupen en unitats de comparació. A cada unitat de comparació se li assignen diversos pesos corresponents a diversos nivells de comparació. Els pesos de les unitats de comparació són elements de conjunts ordenats (en aquest cas, nombres enters) que es poden comparar per més o menys. Significat especial IGNORAT (0x0) significa que al nivell de comparació corresponent aquesta unitat no participa en la comparació. La comparació de cordes es pot repetir diverses vegades, utilitzant els pesos dels nivells corresponents. A cada nivell, els pesos de les unitats de comparació de dues files es comparen seqüencialment entre si.

En diferents implementacions de l'algorisme per a diferents tradicions nacionals, els valors dels coeficients poden diferir, però l'estàndard Unicode inclou una taula bàsica de pesos: "Taula d'elements de col·lació Unicode per defecte" (DUCET). M'agradaria assenyalar que establir la variable LC_COLLATE és en realitat una indicació de la selecció de la taula de pes a la funció de comparació de cadenes.

Coeficients de ponderació DUCET disposat de la següent manera:

al primer nivell, totes les lletres es redueixen al mateix cas, es descarten els diacrítics, s'ignoren els signes de puntuació (no tots);
al segon nivell només es tenen en compte els diacrítics;
al tercer nivell, només es té en compte el cas;
al quart nivell només es tenen en compte els signes de puntuació.

La comparació es fa en diverses passades: en primer lloc, es comparen els coeficients del primer nivell; si els pesos coincideixen, es realitza una comparació repetida amb els pesos de segon nivell; després potser un tercer i un quart.

La comparació acaba quan les files contenen unitats de comparació coincidents amb diferents pesos. Les files que tenen el mateix pes als quatre nivells es consideren iguals entre si.

Aquest algorisme (amb un munt de detalls tècnics addicionals) va donar el nom a l'informe número 10 - "Algoritme de col·lació Unicode" (UCA).

Aquí és on el comportament de classificació del nostre exemple es fa una mica més clar. Seria bo comparar-lo amb l'estàndard Unicode.

Per provar implementacions UCA hi ha un especial тест, utilitzant fitxer de peses, implementant DUCET. Podeu trobar tot tipus de coses divertides al fitxer de les escales. Per exemple, hi ha l'ordre del mahjong i el dòmino europeu, així com l'ordre dels pals en una baralla de cartes (símbol 1F000 i més enllà). Els patges de cartes es col·loquen segons les regles del pont - PCBT, i les cartes del pal estan en la seqüència T, 2,3, XNUMX... K.

Comprovació manual que les files s'ordenen correctament segons DUCET seria bastant tediós, però, afortunadament per a nosaltres, hi ha una implementació exemplar de la biblioteca per treballar amb Unicode - "Components internacionals per a Unicode"(UCI).

Al web d'aquesta biblioteca, desenvolupat a IBM, hi ha pàgines de demostració, incloses pàgina de l'algorisme de comparació de cadenes. Introduïm les nostres línies de prova amb la configuració predeterminada i, vet aquí, obtenim una classificació russa perfecta.

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

Per cert, la web UCI Podeu trobar un aclariment de l'algorisme de comparació quan processeu els signes de puntuació. En exemples Preguntes freqüents sobre la col·lació s'ignoren l'apòstrof i el guionet.

Unicode ens va ajudar, però busqueu motius per a un comportament estrany sort в Linux haurà d'anar a un altre lloc.

Ordenant a la glibc

Vista ràpida dels codis font de la utilitat sort d' GNU Core Utils va demostrar que a la pròpia utilitat, la localització es redueix a imprimir el valor actual de la variable LC_COLLATE quan s'executa en mode de depuració:

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

Les comparacions de cadenes es realitzen mitjançant la funció estàndard strcoll, que vol dir que tot allò interessant és a la biblioteca glibc.

En wiki projecte glibc dedicada a la comparació de cadenes un paràgraf. D'aquest paràgraf es pot entendre que a glibc l'ordenació es basa en un algorisme ja conegut per nosaltres UCA (L'algorisme de col·lació Unicode) i/o en un estàndard proper ISO 14651 (Ordenació i comparació de cadenes internacionals). Pel que fa a l'últim estàndard, cal tenir en compte que al lloc standards.iso.org ISO 14651 declarada oficialment disponible públicament, però l'enllaç corresponent condueix a una pàgina inexistent. Google torna diverses pàgines amb enllaços a llocs oficials que ofereixen comprar una còpia electrònica de l'estàndard per cent euros, però a la tercera o quarta pàgina de resultats de la cerca també hi ha enllaços directes a PDF. En general, l'estàndard pràcticament no és diferent UCA, però és més avorrit de llegir perquè no conté exemples clars de les característiques nacionals de l'ordenació de cadenes.

La informació més interessant wiki hi havia un enllaç a rastrejador d'errors amb una discussió sobre la implementació de la comparació de cadenes a glibc. De la discussió es pot aprendre que glibc utilitzat per comparar cadenes ISOtaula personal La taula de plantilles comuna (CTT), l'adreça de la qual es pot trobar a la sol·licitud A estàndard ISO 14651. Entre el 2000 i el 2015 aquesta taula a glibc no tenia un mantenedor i era bastant diferent (almenys externament) de la versió actual de l'estàndard. Del 2015 al 2018 es va dur a terme l'adaptació a la nova versió de la taula, i ara tens l'oportunitat de conèixer a la vida real una nova versió de la taula (CentOS 8), i vell (CentOS 7).

Ara que tenim tota la informació sobre l'algorisme i les taules auxiliars, podem tornar al problema original i entendre com ordenar correctament les cadenes a la configuració regional russa.

ISO 14651 / 14652

Codi font de la taula que ens interessa CTT a la majoria de distribucions Linux està al catàleg /usr/share/i18n/locales/. La taula en si és a l'arxiu iso14651_t1_comú. Aleshores aquesta és la directiva de fitxers copia iso14651_t1_common inclòs a l'arxiu iso14651_t1, que, al seu torn, s'inclou en els expedients nacionals, inclosos ca_ES и ca_ES. A la majoria de distribucions Linux Tots els fitxers font s'inclouen a la instal·lació bàsica, però si no estan presents, haureu d'instal·lar un paquet addicional de la distribució.

Estructura del fitxer iso14651_t1 pot semblar terriblement detallat, amb regles no òbvies per construir noms, però si t'hi fixes, tot és bastant senzill. L'estructura es descriu a la norma ISO 14652, una còpia del qual es pot descarregar des del lloc web open-std.org. Es pot llegir una altra descripció del format del fitxer especificacions POSIX d' OpenGroup. Com a alternativa a la lectura de l'estàndard, podeu estudiar el codi font de la funció col·lacionar_llegir в glibc/locale/programs/ld-collate.c.

L'estructura del fitxer té aquest aspecte:

Per defecte, el caràcter s'utilitza com a caràcter d'escapada i el final de la línia després del caràcter # és un comentari. Tots dos símbols es poden redefinir, que és el que es fa a la nova versió de la taula:

escape_char /
comment_char %

El fitxer contindrà fitxes en el format o (On x - dígit hexadecimal). Aquesta és la representació hexadecimal dels punts de codi Unicode a la codificació UCS-4 (UTF-32). Tots els altres elements entre parèntesis angulars (inclosos , <2> i similars) es consideren constants de cadena simples que tenen poc significat fora del context.

Cadena LC_COLLATE ens diu que a continuació comencen les dades que descriuen la comparació de cadenes.

En primer lloc, s'especifiquen noms per als pesos a la taula de comparació i noms per a les combinacions de símbols. En termes generals, els dos tipus de noms pertanyen a dues entitats diferents, però en el fitxer real es barregen. Els noms dels pesos s'especifiquen mitjançant la paraula clau símbol de col·lació (caràcter de comparació) perquè en comparar, els caràcters Unicode que tinguin el mateix pes es consideraran caràcters equivalents.

La longitud total de la secció a la revisió actual del fitxer és d'unes 900 línies. Vaig treure exemples de diversos llocs per mostrar l'arbitrarietat dels noms i diversos tipus de sintaxi.

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

símbol de col·lació registra una cadena OSMANYA a la taula de noms d'escales
símbol de col·lació .. registra una seqüència de noms formada per un prefix S i el sufix numèric hexadecimal de 1D000 до 1D35F.
Ffff в símbol de col·lació sembla un nombre enter gran sense signe en hexadecimal, però és només un nom que podria semblar
nom significa punt de codi en la codificació UCS-4
element de col·lació de " " registra un nom nou per a un parell de punts Unicode.

Un cop definits els noms dels pesos, s'especifiquen els pesos reals. Atès que només les relacions més grans que menys importen en comparació, els pesos es determinen mitjançant una simple seqüència de noms de llista. Primer s'enumeren els pesos "més lleugers" i després els "més pesats". Us recordo que a cada caràcter Unicode se li assignen quatre pesos diferents. Aquí es combinen en una única seqüència ordenada. En teoria, qualsevol nom simbòlic es podria utilitzar en qualsevol dels quatre nivells, però els comentaris indiquen que els desenvolupadors separen mentalment els noms en nivells.

% 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

Finalment, la taula de pes real.

La secció de pesos està inclosa en línies de paraules clau ordre_inici и order_end. Opcions addicionals ordre_inici determinar en quina direcció s'escanegen les files a cada nivell de comparació. La configuració predeterminada és endavant. El cos de la secció consta de línies que contenen el codi del símbol i els seus quatre pesos. El codi de caràcter es pot representar pel propi caràcter, un punt de codi o un nom simbòlic definit anteriorment. També es poden donar pesos als noms simbòlics, als punts de codi o als símbols. Si s'utilitzen punts de codi o caràcters, el seu pes és el mateix que el valor numèric del punt de codi (posició a la taula Unicode). Els caràcters no especificats explícitament (segons tinc entès) es consideren assignats a la taula amb un pes principal que coincideix amb la posició de la taula Unicode. Valor de pes especial Ignorar significa que el símbol s'ignora al nivell de comparació adequat.

Per demostrar l'estructura de les escales, vaig triar tres fragments força evidents:

personatges que són completament ignorats
símbols equivalents al número tres dels dos primers nivells
l'inici de l'alfabet ciríl·lic, que no conté signes diacrítics i, per tant, s'ordena principalment pel primer i tercer nivell.

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

Ara podeu tornar a ordenar els exemples des del principi de l'article. L'emboscada es troba en aquesta part de la taula de peses:

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

Es pot veure que en aquesta taula els signes de puntuació de la taula ASCII (inclòs l'espai) gairebé sempre s'ignora quan es comparen cadenes. Les úniques excepcions són les línies que coincideixen en tot excepte els signes de puntuació que es troben a les posicions coincidents. Les línies del meu exemple (després d'ordenar) per a l'algorisme de comparació són així:

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

Tenint en compte que a la taula d'escales, les majúscules en rus van després de les minúscules (al tercer nivell més pesat que ), l'ordenació sembla absolutament correcta.

Quan s'estableix una variable LC_COLLATE=C es carrega una taula especial que especifica una comparació byte a 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'
};

Com que a Unicode el punt de codi Ё està abans de A, les cadenes s'ordenen en conseqüència.

Taules de text i binàries

Òbviament, la comparació de cadenes és una operació extremadament comuna i l'anàlisi de taules CTT un procediment força costós. Per optimitzar l'accés a la taula, es compila en forma binària amb l'ordre localdef.

Equip localdef accepta com a paràmetres un fitxer amb una taula de característiques nacionals (opció -i), en què tots els caràcters estan representats per punts Unicode, i un fitxer de correspondència entre punts Unicode i caràcters d'una codificació específica (opció -f). Com a resultat del treball, es creen fitxers binaris per a la configuració regional amb el nom especificat a l'últim paràmetre.

glibc admet dos formats de fitxer binaris: "tradicional" i "modern".

El format tradicional significa que el nom de la configuració regional és el nom del subdirectori /usr/lib/locale/. Aquest subdirectori emmagatzema fitxers binaris LC_COLLATE, LC_CTYPE, LC_TIME etcètera. Dossier LC_IDENTIFICACIÓ conté el nom formal de la configuració regional (que pot ser diferent del nom del directori) i comentaris.

El format modern implica emmagatzemar totes les localitzacions en un sol arxiu /usr/lib/locale/locale-archive, que s'assigna a la memòria virtual de tots els processos que s'utilitzen glibc. El nom de la configuració regional en el format modern està subjecte a una certa canonització: només queden números i lletres reduïdes a minúscules als noms de codificació. Tan ru_RU.KOI8-R, es desarà com a ru_RU.koi8r.

Els fitxers d'entrada es cerquen al directori actual, així com als directoris /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ per a fitxers CTT i fitxers de codificació, respectivament.

Per exemple, l'ordre

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

compilarà el fitxer /usr/share/i18n/locales/ru_RU utilitzant un fitxer de codificació /usr/share/i18n/charmaps/MAC-CYRILLIC.gz i deseu el resultat a /usr/lib/locale/locale-archive sota el nom ru_RU.maccyrillic

Si configureu la variable LANG = en_US.UTF-8 que glibc buscarà binaris locals en la següent seqüència de fitxers i directoris:

/usr/lib/locale/locale-archive
/usr/lib/locale/en_US.UTF-8/
/usr/lib/locale/en_US/
/usr/lib/locale/enUTF-8/
/usr/lib/locale/en/

Si un local es presenta tant en formats tradicionals com en formats moderns, es dóna prioritat al format modern.

Podeu veure la llista de localitzacions compilades amb l'ordre locale -a.

Preparant la teva taula de comparació

Ara, armat amb el coneixement, podeu crear la vostra pròpia taula de comparació de cadenes ideals. Aquesta taula hauria de comparar correctament les lletres russes, inclosa la lletra Ё, i al mateix temps tenir en compte els signes de puntuació d'acord amb la taula. ASCII.

El procés de preparar la vostra pròpia taula d'ordenació consta de dues etapes: editar la taula de peses i compilar-la en forma binària amb l'ordre localdef.

Per tal que la taula de comparació s'ajusti amb uns costos d'edició mínims, en el format ISO 14652 Es proporcionen seccions per ajustar els pesos d'una taula existent. La secció comença amb una paraula clau reordenar-després i indicant la posició després de la qual es realitza la substitució. La secció acaba amb la línia reordenar-final. Si cal corregir diverses seccions de la taula, es crea una secció per a cadascuna d'aquestes seccions.

Vaig copiar noves versions dels fitxers iso14651_t1_comú и ca_ES des del repositori glibc al meu directori d'inici ~/.local/share/i18n/locales/ i vaig editar lleugerament la secció LC_COLLATE в ca_ES. Les noves versions dels fitxers són totalment compatibles amb la meva versió glibc. Si voleu utilitzar versions anteriors dels fitxers, haureu de canviar els noms simbòlics i el lloc on comença la substitució a la taula.

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

De fet, caldria canviar els camps LC_IDENTIFICACIÓ de manera que apunten al local ru_MY, però en el meu exemple això no era necessari, ja que vaig excloure l'arxiu de la cerca de localitzacions local-arxiu.

Que localdef treballava amb fitxers de la meva carpeta mitjançant una variable I18NPATH Podeu afegir un directori addicional per cercar fitxers d'entrada i el directori per desar fitxers binaris es pot especificar com a camí amb barres inclinades:

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

POSIX suposa que en LLENGUATGE podeu escriure camins absoluts als directoris amb fitxers de configuració regional, començant amb una barra inclinada, però glibc в Linux tots els camins es compten des del directori base, que es pot substituir mitjançant una variable LOCPATH. Després de la instal·lació LOCPATH=~/.local/lib/locale/ tots els fitxers relacionats amb la localització només es cercaran a la meva carpeta. Arxiu de localitzacions amb el conjunt de variables LOCPATH ignorat.

Aquí teniu la prova decisiva:

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

Hura! Ho hem fet!

Alguns errors

Ja he respost a les preguntes sobre l'ordenació de cadenes plantejades al principi, però encara hi ha un parell de preguntes sobre errors: visibles i invisibles.

Tornem al problema original.

I el programa sort i programa unir-se utilitzar les mateixes funcions de comparació de cadenes de glibc. Com va passar això unir-se va donar un error d'ordenació a les files ordenades per l'ordre sort en local en_US.UTF-8? La resposta és senzilla: sort compara tota la cadena i unir-se compara només la clau, que per defecte és l'inici de la cadena fins al primer caràcter d'espai en blanc. En el meu exemple, això va donar lloc a un missatge d'error perquè l'ordenació de les primeres paraules de les línies no coincidia amb l'ordenació de les línies completes.

Localització "C" garanteix que a les cadenes ordenades també s'ordenaran les subcadenes inicials fins al primer espai, però això només emmascara l'error. És possible seleccionar dades (persones amb els mateixos cognoms, però noms diferents) que, sense el missatge d'error, donarien un resultat de fusió de fitxers incorrecte. Si volem unir-se línies de fitxer combinades pel nom complet, aleshores la manera correcta seria especificar explícitament el separador de camps i ordenar pel camp clau, i no per tota la línia. En aquest cas, la fusió continuarà correctament i no hi haurà errors en cap localització:

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

Exemple executat correctament a la codificació CP1251 conté un altre error. El cas és que en totes les distribucions que jo conec Linux falten els paquets locals compilats ru_RU.CP1251. Si no es troba la configuració regional compilada, aleshores sort utilitza silenciosament una comparació byte a byte, que és el que hem observat.

Per cert, hi ha un altre petit error relacionat amb la inaccessibilitat de les configuracions locals compilades. Equip LOCPATH=/tmp local -a donarà una llista de totes les localitzacions en local-arxiu, però amb el conjunt de variables LOCPATH per a tots els programes (inclosos els més locale) aquestes localitzacions no estaran disponibles.

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

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

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

Conclusió

Si sou un programador que està acostumat a pensar que les cadenes són un conjunt de bytes, llavors la vostra elecció LC_COLLATE=C.

Si sou lingüista o compilador de diccionaris, és millor que compileu a la vostra localització.

Si sou un usuari senzill, només heu d'acostumar-vos al fet que l'ordre ls -a dóna sortida a fitxers que comencen amb un punt barrejats amb fitxers que comencen per una lletra i Comandant de mitjanit, que utilitza les seves funcions internes per ordenar els noms, posa els fitxers que comencen amb un punt al principi de la llista.