Introducción

Todo comenzó con un breve script que debía combinar la información sobre las direcciones correo electrónico de los empleados, obtenida de la lista de usuarios del boletín, con los cargos de los empleados, obtenidos de la base de datos del departamento de Recursos Humanos. Ambas listas fueron exportadas a archivos de texto en codificación Unicode UTF-8 y se guardaron con finales de línea de tipo Unix.

Contenido mail.txt

Ivanov Andrey;ia@example.com

Contenido buhg.txt

Ivanova Alla;pintora
Yelkina Ella;grúa
Ivanov Andrey;cerrajero
Abakanov Mikhail;pintor

Para combinarlos, los archivos fueron ordenados con un comando de Unix sort y alimentados a un programa de Unix join, que finalizó inesperadamente con un error:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: no está ordenado: Ivanov Andrey;cerrajero

Una rápida revisión del resultado de la ordenación mostró que, en general, el ordenamiento era correcto, pero en caso de coincidencias de apellidos masculinos y femeninos, los femeninos iban antes que los masculinos:

$> sort buhg.txt
Abakanov Mikhail;pintor
Yelkina Ella;grúa
Ivanova Alla;pintora
Ivanov Andrey;cerrajero

Parece un error de ordenación en Unicode o una manifestación del feminismo en el algoritmo de ordenación. La primera opción es, por supuesto, más plausible.

Dejemos eso de lado por ahora join y centrémonos en sort. Intentemos resolver el problema mediante un enfoque de ensayo y error. Para comenzar, cambiaremos la configuración regional de en_US en ru_RU. Para la ordenación, habría sido suficiente establecer la variable de entorno LC_COLLATE, pero no vamos a ser mezquinos:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;pintor
Yelkina Ella;grúa
Ivanova Alla;pintora
Ivanov Andrey;cerrajero

No ha cambiado nada.

Intentemos recodificar los archivos a una codificación de un solo byte:

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

Nuevamente, no ha cambiado nada.

No hay más remedio, tendré que buscar una solución en internet. No hay nada directo sobre apellidos rusos, pero hay preguntas sobre otras rarezas en la ordenación. Aquí, por ejemplo, hay un problema así: unix sort trata los caracteres ‘-‘ (guion) como invisibles. En resumen, las cadenas "a-b", "aa", "ac" se ordenan como "aa", "a-b", "ac".

La respuesta en todas partes es la misma: use la configuración regional de programador "C" y serán felices. Probemos:

$> LANG=C sort buhg.txt
Yelkina Ella;grúa
Abakanov Mikhail;pintor
Ivanov Andrey;cerrajero
Ivanova Alla;abogada

Algo ha cambiado. Los Ivanov se han alineado en el orden correcto, aunque Yelkina se ha desviado. Volvamos 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

Funcionó sin errores, como prometió internet. Y eso a pesar de la primera línea de Yólkin.

Parece que el problema está resuelto, pero por si acaso probaremos con otra codificación rusa: la de Windows. CP1251:

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

El resultado de la ordenación, curiosamente, coincidirá con la localidad. "C", y todo el ejemplo, por lo tanto, pasa sin errores. Es algo místico.

No me gusta la mística en la programación, ya que, por lo general, oculta errores. Tendré que tomar en serio la cuestión de cómo funciona sort y en qué afecta LC_COLLATE .

Al final intentaré responder a las preguntas:

por qué los apellidos femeninos se ordenaron incorrectamente
por la cual LANG=ru_RU.CP1251 resultó ser equivalente LANG=C
por qué hay sort y join diferentes representaciones del orden de las cadenas ordenadas
por qué en todos mis ejemplos hay errores
finalmente, cómo ordenar cadenas a mi gusto

Ordenación en Unicode

La primera parada será el informe técnico número 10 titulado algoritmo de colación Unicode en el sitio web unicode.org. El informe contiene muchos detalles técnicos, así que me permitiré presentar un resumen de las ideas principales.

Colación — "comparación" de cadenas — es la base de cualquier algoritmo de ordenación. Los propios algoritmos pueden diferir ("burbuja", "fusión", "rápido"), pero todos usarán la comparación de pares de cadenas para determinar el orden de su secuencia.

La ordenación de cadenas en lenguaje natural es un problema bastante complicado. Incluso en las más simples codificaciones de un solo byte, el orden de las letras en un alfabeto que difiere de la latina inglesa no coincidirá con el orden de los valores numéricos que codifican esas letras. Así, en el alfabeto alemán, la letra Ö se encuentra entre A y P, y en la codificación CP850 se sitúa entre ÿ y Ü.

Se puede intentar abstraerse de la codificación concreta y considerar las "letras ideales", que se colocan en algún orden como se hace en Unicode. Las codificaciones UTF8, UTF16 o la de un solo byte KOI8-R (si se necesita un subconjunto limitado de Unicode) proporcionarán diferentes representaciones numéricas de las letras, pero referenciarán los mismos elementos de la tabla base.

Resulta que incluso al construir una tabla de caracteres desde cero, no podremos asignar un orden universal de los caracteres en ella. En diferentes alfabetos nacionales que utilizan las mismas letras, el orden de estas letras puede variar. Por ejemplo, en el idioma francés Æ se considerará una ligadura y se ordenará como una cadena. EAEn cambio, en el idioma noruego Æ se considerará como una letra separada, que se sitúa después de Z. Por cierto, además de ligaduras como Æ hay letras que se escriben con varios símbolos. Así, en el alfabeto checo hay una letra Ch, que se encuentra entre H y I.

Además de las diferencias en los alfabetos, existen otras tradiciones nacionales que influyen en la ordenación. En particular, surge la pregunta: ¿en qué orden deben seguir en el diccionario las palabras que consisten en letras mayúsculas y minúsculas? También las peculiaridades del uso de signos de puntuación pueden influir en la ordenación. En español, al inicio de una pregunta, se coloca un signo de interrogación invertido (¿Te gusta la música?). En este caso, está claro que las preguntas no deben agruparse en un clúster separado fuera del alfabeto, pero ¿cómo se deben ordenar las cadenas con otros signos de puntuación?

No me detendré en la ordenación de cadenas en lenguas que se diferencian significativamente de las europeas. Cabe señalar que en lenguas con dirección de escritura de derecha a izquierda o de arriba hacia abajo, los símbolos en las cadenas probablemente se almacenan en el orden de lectura, y incluso en escrituras no alfabéticas hay formas de ordenar las cadenas carácter por carácter. Por ejemplo, los caracteres pueden ordenarse por la forma (claves de los caracteres chinos) o por pronunciación. La forma en que se deben ordenar los emojis, francamente, no lo sé, pero también se puede idear algo para ellos.

Sobre la base de las características mencionadas anteriormente, se formularon los requisitos básicos para la comparación de cadenas basadas en tablas Unicode:

la comparación de cadenas no depende de la posición de los símbolos en la tabla de códigos;
las secuencias de símbolos que forman un único símbolo se llevan a su forma canónica (A + el círculo superior es lo mismo que Å);
) al comparar cadenas, el símbolo se considera en el contexto de la cadena y, si es necesario, se combina con los vecinos en una única unidad de comparación (Ch en checo) o se divide en varias (Æ en francés);
todas las características nacionales (alfabeto, letras mayúsculas/minúsculas, signos de puntuación, orden de las formas de escritura) deben configurarse hasta la asignación manual del orden (emojis);
la comparación es importante no solo para la clasificación, sino también en muchos otros lugares, como para establecer rangos de filas (sustitución {A… j} en bash);
la comparación debe realizarse lo suficientemente rápido.

Además, los autores del informe formularon las propiedades de comparación en las que los desarrolladores de algoritmos no deben confiar:

el algoritmo de comparación no debe requerir un conjunto separado de símbolos para cada idioma (el ruso y el ucraniano comparten la mayoría de los símbolos cirílicos);
la comparación no debe basarse en el orden de los caracteres en las tablas Unicode;
el peso de la cadena no debería ser un atributo de la cadena, ya que la misma cadena en diferentes contextos culturales puede tener diferentes pesos;
los pesos de las cadenas pueden cambiar al fusionarse o dividirse (de x < y no se debe interpretar que xz < yz);
diferentes cadenas que tienen el mismo peso se consideran iguales desde el punto de vista del algoritmo de clasificación. Introducir un orden adicional para tales cadenas es posible, pero puede degradar el rendimiento;
en las ordenaciones repetidas, las cadenas con el mismo peso pueden intercambiarse. La estabilidad es una propiedad de un algoritmo de clasificación específico, no de un algoritmo de comparación de cadenas (ver el punto anterior);
las reglas de clasificación pueden cambiar con el tiempo a medida que se precisan/cambian las tradiciones culturales.

También se establece que el algoritmo de comparación no sabe nada sobre la semántica de las cadenas procesadas. Así, las cadenas que consisten solo en dígitos no deben compararse como números, y en listas de nombres en inglés no debe eliminarse el artículo (Beatles, The).

Para satisfacer todos los requisitos mencionados, se propone un algoritmo de clasificación tabular multilevel (de hecho, de cuatro niveles).

Previamente, los caracteres de la cadena se normalizan y se agrupan en unidades de comparación. A cada unidad de comparación se le asignan varios pesos, correspondientes a varios niveles de comparación. Los pesos de las unidades de comparación son elementos de conjuntos ordenados (en este caso, números enteros) que se pueden comparar por mayor o menor. Un valor especial IGNORED (0x0) significa que en el nivel de comparación correspondiente, esta unidad no participa en la comparación. La comparación de cadenas puede repetirse varias veces, utilizando los pesos de los niveles correspondientes. En cada uno de los niveles, los pesos de las unidades de comparación de dos cadenas se comparan entre sí de manera secuencial.

En diversas implementaciones del algoritmo para diferentes tradiciones nacionales, los valores de los coeficientes pueden diferir, pero el estándar Unicode incluye una tabla básica de pesos — "Tabla de Elementos de Collación Unicode por Defecto" (DUCET). Quiero destacar que establecer una variable LC_COLLATE es, de hecho, una indicación para elegir la tabla de pesos en la función de comparación de cadenas.

Los coeficientes de peso DUCET están estructurados de la siguiente manera:

en el primer nivel, todas las letras se convierten a una misma mayúscula, los signos diacríticos son desechados, y los signos de puntuación (no todos) son ignorados;
en el segundo nivel, solo se tienen en cuenta los signos diacríticos;
en el tercer nivel, solo se toma en cuenta la mayúscula;
en el cuarto nivel, solo se consideran los signos de puntuación.

La comparación se lleva a cabo en varias pasadas: primero se comparan los coeficientes del primer nivel; si los pesos coinciden, se realiza una comparación repetida con los pesos del segundo nivel; luego, posiblemente, el tercero y el cuarto.

La comparación se termina cuando en las cadenas hay unidades de comparación correspondientes entre sí con diferentes pesos. Las cadenas que tienen pesos iguales en los cuatro niveles se consideran iguales entre sí.

Este algoritmo (con un montón de detalles técnicos adicionales) le dio nombre al informe nº 10 — "Algoritmo de Collación Unicode" (UCA).

Aquí el comportamiento de ordenación de nuestro ejemplo se vuelve un poco más comprensible. Sería bueno compararlo con el estándar Unicode.

Para probar implementaciones UCA existe un test, que utiliza un archivo de pesos, que implementa DUCET. En el archivo de pesos se pueden encontrar diversas curiosidades. Por ejemplo, hay un orden de fichas de mahjong y dominó europeo, así como el orden de los palos en una baraja de cartas (símbolo 1F000 y así sucesivamente). Los palos de carta están organizados según las reglas del bridge — PCHBT, y las cartas en cada palo — en secuencia de 2,3… K.

Verificar manualmente la correcta ordenación de cadenas de acuerdo con DUCET sería bastante tedioso, pero, afortunadamente para nosotros, existe una implementación ejemplar de una biblioteca para trabajar con Unicode — "Componentes Internacionales para Unicode" (ICU).

En el sitio de esta biblioteca, desarrollada en IBM, hay páginas de demostración, incluyendo la página del algoritmo de comparación de cadenas. Introducimos nuestras cadenas de prueba con la configuración predeterminada y, ¡oh maravilla!, obtenemos una clasificación rusa perfecta.

Abakanov Mikhail; pintor
Yolkina Ella; grúa
Ivanov Andrey; cerrajero
Ivanova Alla; abogada

Por cierto, en el sitio ICU se puede encontrar una aclaración sobre cómo funciona el algoritmo de comparación al procesar signos de puntuación. En los ejemplos Preguntas frecuentes sobre la clasificación se ignoran el apóstrofo y el guion.

Unicode nos ayudó, pero tendremos que buscar las razones del comportamiento extraño sort en Linux en algún otro lugar.

Clasificación en glibc

Una rápida revisión del código fuente de la utilidad sort de GNU Core Utils mostró que en la propia utilidad, la localización se reduce a imprimir el valor actual de la variable LC_COLLATE al ejecutarse en modo de depuración:

$ sort --debug buhg.txt > buhg.srt
sort: utilizando las reglas de clasificación ‘en_US.UTF8’

La comparación de cadenas se realiza mediante la función estándar strcoll, lo que significa que todo lo interesante se encuentra en la biblioteca glibc.

En wiki el proyecto glibc la comparación de cadenas está dedicada a un párrafo. De este párrafo se puede entender que en glibc la clasificación se basa en el algoritmo que ya conocemos UCA (El algoritmo de clasificación Unicode) y/o en un estándar cercano a él ISO 14651 (Ordenación y comparación de cadenas internacionales). Con respecto a este último estándar, se debe notar que en el sitio standards.iso.org ISO 14651 se declara oficialmente público, pero el enlace correspondiente lleva a una página inexistente. Google devuelve varias páginas con enlaces a sitios oficiales que ofrecen comprar una copia electrónica del estándar por un centenar de euros, pero en la tercera o cuarta página de los resultados de búsqueda se pueden encontrar enlaces directos a PDF. En general, el estándar no se diferencia prácticamente de UCA, pero se lee con más aburrimiento, ya que no contiene ejemplos vívidos de las peculiaridades nacionales en la clasificación de cadenas.

La información más interesante en wiki resultó ser un enlace a un rastreador de errores con una discusión sobre la implementación de la comparación de cadenas en glibc. De la discusión se puede saber que en glibc para la comparación de cadenas se utiliza ISOuna tabla The Common Template Table (CTT), cuya dirección se puede encontrar en el apéndice A del estándar ISO 14651. Entre 2000 y 2015, esta tabla en glibc no tenía un mantenedor y se diferenciaba notablemente (al menos en apariencia) de la versión actual del estándar. Desde 2015 hasta 2018, se llevó a cabo la adaptación a la nueva versión de la tabla y en este momento tienes la oportunidad de encontrar en la vida real tanto la nueva versión de la tabla (CentOS 8), como la antigua (CentOS 7).

Ahora que tenemos toda la información sobre el algoritmo y las tablas auxiliares, podemos volver al problema original y entender cómo se deben ordenar correctamente las cadenas en una configuración local rusa.

ISO 14651/14652

El código fuente de la tabla que nos interesa CTT se encuentra en la mayoría de las distribuciones Linux en el directorio /usr/share/i18n/locales/. La tabla en sí se encuentra en el archivo iso14651_t1_common. Luego, este archivo se incluye en el archivo copy iso14651_t1_common , que, a su vez, se incluye en los archivos nacionales, incluidos los de . En la mayoría de las distribucionestodos los archivos fuente están incluidos en la instalación base, pero si no están, deberás instalar un paquete adicional de la distribución. en_US y ru_RUpuede parecer horriblemente prolijo, con reglas poco claras para la construcción de nombres, pero si se analiza, es bastante simple. La estructura está descrita en el estándar Linux ISO 14652

Estructura del archivo . En la mayoría de las distribuciones , una copia del cual se puede descargar del sitio open-std.org. Otra descripción del formato del archivo se puede leer en OpenGroup. Como alternativa a leer el estándar, se pueden estudiar los textos fuente de la función las especificaciones POSIX desde collate_readglibc/locale/programs/ld-collate.c La estructura del archivo es la siguiente: en Por defecto, el símbolo se utiliza como carácter de escape, y el final de línea después del símbolo # es un comentario. Ambos símbolos se pueden redefinir, lo que se ha hecho en la nueva versión de la tabla:.

escape_char / comment_char %

En el archivo se encontrarán tokens en formato

escape_char /
comment_char %

В файле будут встречаться токены в формате — un dígito hexadecimal). Esta representación hexadecimal de los puntos de código Unicode está en la codificación o UCS-4 (donde x UTF-32 ). Todos los demás elementos en ángulos (incluidos (UTF-32). Все остальные элементы в угловых скобках (в том числе y similares), se consideran constantes de cadena simples, sin sentido fuera de contexto., nos dice que a continuación empiezan los datos que describen la comparación de cadenas. Primero se definen nombres para los pesos en la tabla de comparación y nombres para combinaciones de caracteres. En general, dos tipos de nombres pertenecen a dos entidades diferentes, pero en el archivo real están mezclados. Los nombres de los pesos se definen con la palabra clave

Cadena LC_COLLATE collating-symbol

Сначала задаются имена для весов в таблице сравнения и имена для комбинаций символов. Вообще говоря, два типа имён принадлежат двум разным сущностям, но в реальном файле они перемешаны. Имена весов задаются ключевым словом collating-symbol (símbolo de comparación), ya que al comparar los caracteres Unicode con pesos iguales, se considerarán símbolos equivalentes.

La longitud total de la sección en la revisión actual del archivo es de aproximadamente 900 líneas. He extraído ejemplos de varios lugares para mostrar la arbitrariedad de los nombres y varios tipos de sintaxis.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Valor de símbolo más grande garantizado. Mantener al final de esta lista
...
collating-element  from ""
collating-element  from ""

collating-symbol registra la cadena OSMANYA en la tabla de nombres de pesos
collating-symbol .. registra una secuencia de nombres compuesta por un prefijo S y un sufijo numérico hexadecimal de 1D000 hasta 1D35F.
FFFF en collating-symbol se ve como un número entero sin signo grande en el sistema hexadecimal, pero <SFFFF> es solo un nombre que podría verse como <VERYBIGVAL>
nombre <U0413> significa el punto de código en la codificación ). Todos los demás elementos en ángulos (incluidos
collating-element from "" registra un nuevo nombre para un par de puntos Unicode.

Cuando se definen los nombres de pesos, se establecen los pesos en sí. Dado que al comparar solo importa la relación de mayor a menor, los pesos se determinan por una simple secuencia de enumeración de nombres. Los pesos "más livianos" se enumeran primero, seguidos de los "más pesados". Recuerdo que a cada símbolo Unicode se le asigna cuatro pesos diferentes. Aquí se han consolidado en una única secuencia ordenada. Teóricamente, cualquier nombre simbólico puede utilizarse en cualquiera de los cuatro niveles, pero los comentarios indican que los desarrolladores separan mentalmente los nombres por niveles.

% Asignaciones de peso simbólico

% Asignaciones de peso de tercer nivel




...
% Asignaciones de peso de segundo nivel

 % COMBINANDO LINEA BAJA
 % COMBINANDO COMA ARRIBA
 % COMBINANDO COMA INVERSO ARRIBA
...
% Asignaciones de peso de primer nivel
 % TABULACIÓN HORIZONTAL 
 % SALTO DE LÍNEA
 % TABULACIÓN VERTICAL
...
 % LETRA PEQUEÑA CYRÍLICA DE
 % LETRA PEQUEÑA CYRÍLICA DE KOMI
 % LETRA PEQUEÑA CYRÍLICA DJE
 % LETRA PEQUEÑA CYRÍLICA DJE DE KOMI
 % LETRA PEQUEÑA CYRÍLICA GJE
 % LETRA PEQUEÑA CYRÍLICA ZE CON DESCENSOR
 % LETRA PEQUEÑA CYRÍLICA IE
 % LETRA PEQUEÑA CYRÍLICA IE CON BREVE
 % LETRA PEQUEÑA CYRÍLICA UKRAINIAN IE
 % LETRA PEQUEÑA CYRÍLICA ZHE

Finalmente, la tabla de pesos en sí.

La sección de pesos está encerrada en filas con palabras clave order_start y order_end. Parámetros adicionales order_start definen en qué dirección se visualizan las filas en cada nivel de comparación. Por defecto se utiliza el parámetro forward. El cuerpo de la sección consiste en filas que contienen el código de carácter y sus cuatro pesos. El código de carácter puede ser representado por el propio símbolo, el punto de código o un nombre simbólico definido anteriormente. Los pesos también pueden estar dados por nombres simbólicos, puntos de código o los propios símbolos. Si se utilizan puntos de código o símbolos, su peso coincide con el valor numérico del punto de código (posición en la tabla Unicode). Los símbolos no especificados explícitamente (según entiendo) se consideran añadidos a la tabla con un peso primario que coincide con la posición en la tabla Unicode. El valor especial del peso IGNORE significa que en el nivel de comparación correspondiente, este símbolo es ignorado.

Para demostrar la estructura de pesos, elegí tres fragmentos bastante obvios:

símbolos que se ignoran por completo
símbolos equivalentes al número tres en los dos primeros niveles
el comienzo del alfabeto cirílico, que no contiene diacríticos y, por lo tanto, se ordena principalmente por los primeros y terceros niveles.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (en 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % INICIO DE CABECERA (en 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % INICIO DE TEXTO (en 6429)
...
 ;;; % DIGITO TRES
 ;;; % DIGITO TRES DE ANCHO COMPLETO
 ;;; % DIGITO TRES ENTRE PARÉNTESIS
 ;;; % DIGITO TRES PUNTO FINAL
 ;;; % DIGITO TRES EN NEGRITA MATEMÁTICA
...
 ;;; % LETRA CIRÍLICA PEQUEÑA A
 ;;; % LETRA CIRÍLICA MAYÚSCULA A
 ;;; % LETRA CIRÍLICA PEQUEÑA A CON BREVE
 ;;; % LETRA CIRÍLICA PEQUEÑA A CON BREVE
...
 ;;; % LETRA CIRÍLICA PEQUEÑA BE
 ;;; % LETRA CIRÍLICA MAYÚSCULA BE
 ;;; % LETRA CIRÍLICA PEQUEÑA VE
 ;;; % LETRA CIRÍLICA MAYÚSCULA VE
...
order_end

Ahora podemos volver a la clasificación de ejemplos del principio del artículo. La trampa está en esta parte de la tabla de pesos:

IGNORE;IGNORE;IGNORE; % ESPACIO
 IGNORE;IGNORE;IGNORE; % SIGNO DE EXCLAMACIÓN
 IGNORE;IGNORE;IGNORE; % COMILLAS
...

Es evidente que en esta tabla los signos de puntuación provienen de la tabla. ASCII (incluido el espacio) se ignora prácticamente siempre al comparar cadenas. Las únicas excepciones son las cadenas que coinciden en todo, excepto por los signos de puntuación que se encuentran en posiciones coincidentes. Las cadenas de mi ejemplo (después de la clasificación) para el algoritmo de comparación se ven así:

AbakanovMikhailpintor
YolkinaEllacartista
IvanovaAllamalpintor
IvanovAndreycarpintero

Teniendo en cuenta que en la tabla de pesos las letras mayúsculas en el idioma ruso vienen después de las minúsculas (en el tercer nivel <CAP> más pesado que <MIN>), la clasificación parece absolutamente correcta.

Al establecer la variable LC_COLLATE=C se carga una tabla especial que define la comparación byte a byte.

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
    * tabla de primer nivel *
  6 * sizeof (uint32_t),
    * tabla de segundo nivel *
  7 * sizeof (uint32_t),
    * tabla de tercer nivel *
  L'x00', L'x01', L'x02', L'x03', L'x04', L'x05', L'x06', L'x07',
  L'x08', L'x09', L'x0a', L'x0b', L'x0c', L'x0d', L'x0e', L'x0f',

...
  L'xf8', L'xf9', L'xfa', L'xfb', L'xfc', L'xfd', L'fe', L'xff'
};

Dado que en Unicode el punto de código Ё, está antes de А, las cadenas se clasifican de manera correspondiente.

Tablas textuales y binarias

Es obvio que la comparación de cadenas es una operación extremadamente frecuente, mientras que el análisis de la tabla CTT es un procedimiento bastante costoso. Para optimizar el acceso a la tabla, se compila en forma binaria mediante el comando localedef.

Comando localedef acepta como parámetros un archivo con la tabla de características nacionales (opción , el intervalo entre el envío de paquetes.), en la que todos los símbolos están representados por puntos de Unicode, y un archivo de correspondencia de puntos de Unicode con caracteres de una codificación específica (opción -f). Como resultado del trabajo, se crean archivos binarios para la localidad, con el nombre indicado en el último parámetro.

Glibc soporta dos formatos de archivos binarios: "tradicional" y "moderno".

El formato tradicional implica que el nombre de la localidad es el nombre de un subdirectorio en /usr/lib/locale/. En este subdirectorio se almacenan los archivos binarios LC_COLLATE, LC_CTYPE, LC_TIME etc. El archivo LC_IDENTIFICATION contiene el nombre formal de la localidad (que puede diferir del nombre del directorio) y comentarios.

El formato moderno supone el almacenamiento de todas las localidades en un único archivo comprimido /usr/lib/locale/locale-archive, que se mapea en la memoria virtual de todos los procesos que lo utilizan. glibcEl nombre de la configuración regional en formato moderno se somete a cierta canonización: en los nombres de la codificación permanecen solo los números y letras, convertidos a minúsculas. Así es_ES.UTF-8, se guardará como es_ES.utf-8.

Los archivos de entrada se buscan en el directorio actual, así como en los directorios /usr/share/i18n/locales/ y /usr/share/i18n/charmaps/ para archivos CTT y archivos de codificación respectivamente.

Por ejemplo, el comando

localedef -i es_ES -f UTF-8 es_ES.UTF-8

compilará el archivo /usr/share/i18n/locales/ru_RU usando el archivo de codificación /usr/share/i18n/charmaps/MAC-CYRILLIC.gz y guardará el resultado en /usr/lib/locale/locale-archive con el nombre es_ES.utf8

Si se establece la variable LANG=es_ES.UTF-8 entonces glibc buscará archivos binarios de la configuración regional en la siguiente secuencia de archivos y directorios:

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

Si la configuración regional aparece tanto en formatos tradicionales como modernos, se da prioridad al moderno.

Se puede ver la lista de configuraciones regionales compiladas con el comando locale -a.

Preparando su propia tabla de comparación

Ahora, armado con conocimientos, puede crear su propia tabla de comparación ideal de cadenas. Esta tabla debe comparar correctamente las letras españolas, incluyendo la letra Ñ, y tener en cuenta los signos de puntuación de acuerdo con la tabla ASCII.

El proceso de preparación de su propia tabla de ordenación consta de dos etapas: la edición de la tabla de pesos y su compilación en forma binaria con el comando localedef.

Para que la tabla de comparación pueda ajustarse con un mínimo de esfuerzo de edición, en el formato open-std.org se prevén secciones de ajuste de pesos de la tabla existente. La sección comienza con la palabra clave reorder-after y la indicación de la posición después de la cual se realiza el reemplazo. La sección se cierra con la línea reorder-end. Si es necesario corregir varias partes de la tabla, se crea una sección para cada una de esas partes.

He copiado las nuevas versiones de los archivos iso14651_t1_common y ru_RU del repositorio glibc a mi directorio personal ~/local/share/i18n/locales/ y he editado ligeramente la sección LC_COLLATE en ru_RU. Las nuevas versiones de los archivos son completamente compatibles con mi versión glibc. Si desea utilizar versiones anteriores de los archivos, tendrá que cambiar los nombres simbólicos y la ubicación desde donde comienza el reemplazo en la tabla.

LC_COLLATE
% Copia la plantilla de ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % ESPACIO
 ;;; % SIGNO DE EXCLAMACIÓN
 ;;; % COMILLAS
...
 ;;; % LLAVE DERECHA
 ;;; % TILD
reorder-end
FIN LC_COLLATE

De hecho, habría que cambiar los campos en LC_IDENTIFICATION para que apunten a la localidad ru_MY, pero en mi ejemplo no fue necesario, ya que excluí de la búsqueda la localidad del archivo locale-archive.

Para localedef trabajé con archivos en mi carpeta a través de la variable I18NPATH se puede añadir un directorio adicional para la búsqueda de archivos de entrada, y el directorio para guardar los archivos binarios se puede especificar como una ruta con barras:

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

POSIX supone que en LANG se pueden escribir rutas absolutas a los directorios con archivos locales que comienzan con una barra, pero glibc en Linux todas las rutas se consideran desde el directorio base, que se puede redefinir a través de la variable LOCPATH. Después de establecer LOCPATH=~/.local/lib/locale/ todos los archivos relacionados con la localización se buscarán solo en mi carpeta. El archivo de localidades con la variable establecida LOCPATH se ignora.

Aquí está la prueba decisiva:

$> LANG=ru_MY.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;pintor
Yolkina Ella;grúa
Ivanov Andrey;cerrajero
Ivanova Alla;abogada

¡Hurra! ¡Lo hemos logrado!

Trabajando en corregir errores

Ya he respondido a las preguntas sobre la ordenación de cadenas planteadas al principio, pero aún quedan un par de preguntas sobre errores, visibles e invisibles.

Volvamos a la tarea original.

Y el programa sort y el programa join utilizan las mismas funciones de comparación de cadenas de glibc. ¿Cómo es que join proporcionó un error de ordenación en las cadenas ordenadas por el comando sort en la localidad en_US.UTF-8? Ответ прост: sort compara la cadena completa, mientras que join solo compara la clave, que por defecto es el inicio de la cadena hasta el primer carácter de espacio. En mi ejemplo, esto llevó a un mensaje de error porque la ordenación de las primeras palabras en las cadenas no coincidió con la ordenación de las cadenas completas.

La localidad "C" asegura que en las cadenas ordenadas las subcadenas iniciales hasta el primer espacio también estén ordenadas, pero esto solo oculta el error. Se pueden elegir datos como (personas con el mismo apellido pero diferentes nombres) que sin un mensaje de error darían un resultado incorrecto al fusionar archivos. Si queremos que join fusionar cadenas de archivos por nombre completo, el enfoque correcto sería especificar explícitamente el delimitador de campos y ordenar por el campo clave, no por toda la cadena. En este caso, tanto la fusión se realizará correctamente como no habrá errores en ninguna localidad:

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

Ejemplo ejecutado con éxito en la codificación CP1251 contiene otro error. El problema es que en todas las distribuciones que conozco Linux los paquetes carecen de una localización compilada ru_RU.CP1251. Si no se encuentra la localización compilada, sort silenciosamente utiliza la comparación byte a byte, que es lo que hemos observado.

Por cierto, hay un pequeño glitch relacionado con la falta de localizaciones compiladas. El comando LOCPATH=/tmp locale -a listará todas las localizaciones en locale-archive, pero si la variable está establecida LOCPATH para todos los programas (incluida la misma locale) estas localizaciones no estarán disponibles.

$> LOCPATH=/tmp locale -a | grep en_US
locale: No se puede establecer LC_CTYPE como la localización predeterminada: No existe el archivo o el directorio
locale: No se puede establecer LC_MESSAGES como la localización predeterminada: No existe el archivo o el directorio
locale: No se puede establecer LC_COLLATE como la localización predeterminada: No existe el archivo o el directorio
en_US
en_US.iso88591
en_US.iso885915
en_US.utf8

$> LC_COLLATE=en_US.UTF-8 sort --debug
sort: usando las reglas de ordenamiento ‘en_US.UTF-8’

$> LOCPATH=/tmp LC_COLLATE=en_US.UTF-8 sort --debug
sort: usando comparación simple byte a byte

Conclusión

Si eres un programador que está acostumbrado a pensar que las cadenas son un conjunto de bytes, tu elección LC_COLLATE=C.

Si eres lingüista o compilador de diccionarios, lo mejor es que compiles tu propia localización.

Si eres un usuario común, solo necesitas acostumbrarte a que el comando ls -a devuelve archivos que comienzan con un punto, mezclados con archivos que comienzan con una letra, y Midnight Commander, que utiliza sus funciones internas para ordenar nombres, coloca archivos que comienzan con un punto al inicio de la lista.