introducción

Todo comenzó con un breve guión que se suponía combinaría información de dirección. correo electrónico empleados obtenidos de la lista de usuarios de la lista de correo, con puestos de empleados obtenidos de la base de datos del departamento de recursos humanos. Ambas listas se exportaron a archivos de texto Unicode. UTF-8 y guardado con finales de línea Unix.

contenido correo.txt

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

contenido buhg.txt

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

Para fusionar, los archivos se ordenaron mediante el comando Unix. sort y enviado a la entrada del programa Unix. únete, que inesperadamente falló con 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: Иванов Андрей;слесарь

Ver el resultado de la clasificación con los ojos mostró que, en general, la clasificación es correcta, pero en el caso de coincidencias de apellidos masculinos y femeninos, los femeninos aparecen antes que los masculinos:

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

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

Dejemoslo por ahora únete y centrarse en sort. Intentemos resolver el problema mediante la investigación científica. Primero, cambiemos la ubicación de es_ES en es_ES. Para ordenar, bastaría con configurar la variable de entorno LC_COLLATE, pero no perderemos el tiempo en nimiedades:

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

Nada ha cambiado.

Intentemos recodificar los archivos en 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

De nuevo nada ha cambiado.

No hay nada que puedas hacer, tendrás que buscar una solución en Internet. No hay nada directamente sobre los apellidos rusos, pero hay preguntas sobre otras rarezas de clasificación. Por ejemplo, aquí hay un problema: La clasificación Unix trata los caracteres '-' (guión) como invisibles. En resumen, las cadenas "ab", "aa", "ac" se ordenan como "aa", "ab", "ac".

La respuesta es estándar en todas partes: use la configuración regional del programador "C" y serás feliz. Intentemos:

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

Algo ha cambiado. Los Ivanov se alinearon en el orden correcto, aunque Yolkina se deslizó en alguna parte. 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 prometía Internet. Y esto a pesar de Yolkina en primera línea.

El problema parece estar resuelto, pero por si acaso, probemos con otra codificación rusa: Windows CP1251:

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

El resultado de la clasificación, por extraño que parezca, coincidirá con la ubicación. "C"y, en consecuencia, todo el ejemplo se ejecuta sin errores. Algún tipo de misticismo.

No me gusta el misticismo en la programación porque normalmente enmascara errores. Tendremos que analizar seriamente cómo funciona. sort ¿Y en qué afecta? LC_COLLATE .

Al final intentaré responder las preguntas:

¿Por qué los apellidos femeninos se ordenaron incorrectamente?
por qué LANG=ru_RU.CP1251 resultó ser equivalente IDIOMA = C
por qué sort и únete diferentes ideas sobre el orden de las cadenas ordenadas
¿Por qué hay errores en todos mis ejemplos?
finalmente como ordenar cadenas a tu gusto

Ordenar en Unicode

La primera parada será el informe técnico N° 10 titulado Algoritmo de intercalación Unicode online unicode.org. El informe contiene muchos detalles técnicos, así que permítanme hacer un breve resumen de las ideas principales.

Colación — “Comparar” cadenas es la base de cualquier algoritmo de clasificación. Los algoritmos en sí pueden diferir ("burbuja", "fusión", "rápido"), pero todos utilizarán una comparación de un par de cadenas para determinar el orden en que aparecen.

Ordenar cadenas en lenguaje natural es un problema bastante complejo. Incluso en las codificaciones de un solo byte más simples, el orden de las letras del alfabeto, incluso de alguna manera diferente del alfabeto latino inglés, ya no coincidirá con el orden de los valores numéricos con los que están codificadas estas letras. Así, en el alfabeto alemán la letra Ö se encuentra entre О и P, y en la codificación CP850 ella se mete entre ÿ и Ü.

Puede intentar abstraerse de una codificación específica y considerar letras "ideales" que estén dispuestas en algún orden, como se hace en Unicode. Codificaciones UTF8, UTF16 o un byte KOI8-R (si se necesita un subconjunto limitado de Unicode) dará diferentes representaciones numéricas de letras, pero hará referencia a los mismos elementos de la tabla base.

Resulta que incluso si construimos una tabla de símbolos desde cero, no podremos asignarle un orden de símbolos universal. En diferentes alfabetos nacionales que utilizan las mismas letras, el orden de estas letras puede diferir. Por ejemplo, en francés Æ se considerará una ligadura y se clasificará como una cadena AE. En noruego Æ será una letra separada, que se encuentra después Z. Por cierto, además de ligaduras como Æ Hay letras escritas con varios símbolos. Entonces en el alfabeto checo hay una letra. Ch, que se sitúa entre H и I.

Además de las diferencias en los alfabetos, existen otras tradiciones nacionales que influyen en la clasificación. En particular, surge la pregunta: ¿en qué orden deberían aparecer en el diccionario las palabras que constan de letras mayúsculas y minúsculas? La clasificación también puede verse afectada por el uso de signos de puntuación. En español, se utiliza un signo de interrogación invertido al comienzo de una oración interrogativa (¿Te gusta la música?). En este caso, es obvio que las oraciones interrogativas no deben agruparse en un grupo separado fuera del alfabeto, pero ¿cómo ordenar las líneas con otros signos de puntuación?

No me detendré en ordenar cadenas en idiomas muy distintos a los europeos. Tenga en cuenta que en los idiomas con una dirección de escritura de derecha a izquierda o de arriba a abajo, lo más probable es que los caracteres en las líneas se almacenen en orden de lectura, e incluso los sistemas de escritura no alfabéticos tienen sus propias formas de ordenar las líneas carácter por carácter. . Por ejemplo, los jeroglíficos se pueden ordenar por estilo (Teclas de caracteres chinos.) o por pronunciación. Para ser honesto, no tengo idea de cómo se deben organizar los emojis, pero tú también puedes idear algo para ellos.

Con base en las características enumeradas anteriormente, se formularon los requisitos básicos para comparar cadenas basadas en tablas Unicode:

la comparación de cadenas no depende de la posición de los caracteres en la tabla de códigos;
las secuencias de caracteres que forman un solo carácter se reducen a la forma canónica (A + el círculo superior es el mismo que Å);
Al comparar cadenas, un carácter se considera en el contexto de la cadena y, si es necesario, se combina con sus vecinos en una unidad de comparación (Ch en checo) o se divide en varios (Æ en francés);
todas las características nacionales (alfabeto, mayúsculas/minúsculas, puntuación, orden de los tipos de escritura) deben configurarse hasta la asignación manual del orden (emoji);
La comparación es importante no sólo para ordenar, sino también en muchos otros lugares, por ejemplo para especificar rangos de filas (sustituyendo {A... z} en golpear);
la comparación debe hacerse con bastante rapidez.

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

el algoritmo de comparación no debería requerir un conjunto de caracteres separado para cada idioma (los idiomas ruso y ucraniano comparten la mayoría de los caracteres cirílicos);
la comparación no debe depender del orden de los caracteres en las tablas Unicode;
el peso de la cadena no debe ser un atributo de la cadena, ya que la misma cadena en diferentes contextos culturales puede tener diferentes pesos;
Los pesos de las filas pueden cambiar al fusionar o dividir (de x < y no sigue eso xz < yz);
diferentes cadenas que tienen el mismo peso se consideran iguales desde el punto de vista del algoritmo de clasificación. Es posible introducir un orden adicional de dichas cadenas, pero puede degradar el rendimiento;
Durante la clasificación repetida, se pueden intercambiar filas con el mismo peso. La robustez es una propiedad de un algoritmo de clasificación específico y no una propiedad de un algoritmo de comparación de cadenas (consulte el párrafo anterior);
Las reglas de clasificación pueden cambiar con el tiempo a medida que las tradiciones culturales se perfeccionan o cambian.

También se estipula que el algoritmo de comparación no sabe nada sobre la semántica de las cadenas que se procesan. Por lo tanto, las cadenas que constan únicamente de dígitos no deben compararse como números, y en las listas de nombres en inglés el artículo (los beatles, los).

Para satisfacer todos estos requisitos, se propone un algoritmo de clasificación de tablas de varios niveles (en realidad, cuatro niveles).

Previamente, los caracteres de la cadena se reducen a forma canónica 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 más o menos. Significado especial Ignorado (0x0) significa que en el nivel de comparación correspondiente esta unidad no participa en la comparación. La comparación de cadenas se puede repetir varias veces, utilizando los pesos de los niveles correspondientes. En cada nivel, los pesos de las unidades de comparación de dos filas se comparan secuencialmente entre sí.

En diferentes 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 clasificación Unicode predeterminada" (DUCETO). Me gustaría señalar que configurar la variable LC_COLLATE es en realidad una indicación de la selección de la tabla de pesos en la función de comparación de cadenas.

Coeficientes de ponderación DUCETO dispuestos de la siguiente manera:

en el primer nivel, todas las letras se reducen al mismo caso, se descartan los signos diacríticos, se ignoran los signos de puntuación (no todos);
en el segundo nivel sólo se tienen en cuenta los signos diacríticos;
en el tercer nivel sólo se tiene en cuenta el caso;
en el cuarto nivel, solo se tienen en cuenta los signos de puntuación.

La comparación se realiza en varias pasadas: primero se comparan los coeficientes del primer nivel; si las ponderaciones coinciden, se realiza una comparación repetida con las ponderaciones del segundo nivel; luego quizás un tercero y un cuarto.

La comparación finaliza cuando las filas contienen unidades de comparación coincidentes con pesos diferentes. Las filas que tienen pesos iguales en los cuatro niveles se consideran iguales entre sí.

Este algoritmo (con muchos detalles técnicos adicionales) dio el nombre al informe número 10: "Algoritmo de intercalación Unicode" (UCA).

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

Para probar implementaciones UCA hay un especial prueba, usando archivo de pesos, implementar DUCETO. Puedes encontrar todo tipo de cosas divertidas en el archivo de escalas. Por ejemplo, existe el orden del mahjong y del dominó europeo, así como el orden de los palos en una baraja de cartas (símbolo 1F000 y además). Los palos de las cartas se colocan de acuerdo con las reglas del bridge - PCBT, y las cartas del palo están en la secuencia T, 2,3, XNUMX... K.

Comprobar manualmente que las filas estén ordenadas correctamente según DUCETO Sería bastante tedioso, pero, afortunadamente para nosotros, existe una implementación ejemplar de la biblioteca para trabajar con Unicode: "Componentes internacionales para Unicode"(UCI).

En el sitio web de esta biblioteca, desarrollado en IBM, hay páginas de demostración, que incluyen página del algoritmo de comparación de cadenas. Ingresamos a nuestras líneas de prueba con la configuración predeterminada y, he aquí, obtenemos una clasificación rusa perfecta.

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

Por cierto, el sitio web UCI Puede encontrar una aclaración del algoritmo de comparación al procesar signos de puntuación. En ejemplos Preguntas frecuentes sobre la intercalación Se ignoran el apóstrofe y el guión.

Unicode nos ayudó, pero busque las razones del comportamiento extraño sort в Linux habrá que ir a otro sitio.

Ordenando en glibc

Vista rápida de los códigos fuente de la utilidad. sort de Utilidades principales de GNU demostró que en la propia utilidad, la localización se reduce a imprimir el valor actual de la variable LC_COLLATE cuando se ejecuta en modo de depuración:

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

Las comparaciones de cadenas se realizan utilizando la función estándar. pasear, lo que significa que todo lo interesante está en la biblioteca. glibc.

En wiki proyecto glibc dedicado a la comparación de cadenas un parrafo. De este párrafo se puede entender que en glibc La clasificación se basa en un algoritmo que ya conocemos. UCA (El algoritmo de intercalación Unicode) y/o en un estándar cercano a él ISO 14651 (Ordenamiento y comparación de cadenas internacionales). Respecto al último estándar, cabe señalar que en el sitio normas.iso.org ISO 14651 declarado oficialmente disponible públicamente, pero el enlace correspondiente conduce a una página inexistente. Google muestra varias páginas con enlaces a sitios oficiales que ofrecen comprar una copia electrónica de la norma por cien euros, pero en la tercera o cuarta página de resultados de búsqueda también hay enlaces directos a (PDF). En general, el estándar prácticamente no difiere del UCA, pero es más aburrido de leer porque no contiene ejemplos claros de las características nacionales de clasificación de cadenas.

La información más interesante sobre wiki había un enlace a localizador de bichos con una discusión sobre la implementación de la comparación de cadenas en glibc. De la discusión se puede aprender que glibc utilizado para comparar cadenas ISOmesa personal La tabla de plantillas comunes (CTT), cuya dirección se puede encontrar en la solicitud A estándar ISO 14651. Entre 2000 y 2015 esta tabla en glibc no tenía mantenedor y era bastante diferente (al menos externamente) de la versión actual del estándar. De 2015 a 2018 se realizó la adaptación a la nueva versión de la mesa, y ahora tienes la oportunidad de conocer en la vida real una nueva versión de la mesa (8 CentOS), y viejo (7 CentOS).

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

ISO 14651 / 14652

Código fuente de la tabla que nos interesa CTT en la mayoría de las distribuciones Linux esta en el directorio /usr/share/i18n/locales/. La tabla en sí está en el archivo. iso14651_t1_común. Entonces esta es la directiva de archivo. copiar iso14651_t1_common incluido en el archivo iso14651_t1, que, a su vez, se incluye en archivos nacionales, incluidos es_ES и es_ES. En la mayoría de las distribuciones Linux Todos los archivos fuente están incluidos en la instalación básica, pero si no están presentes, tendrás que instalar un paquete adicional de la distribución.

Estructura de archivos iso14651_t1 Puede parecer terriblemente detallado, con reglas no obvias para construir nombres, pero si lo miras bien, todo es bastante simple. La estructura se describe en la norma. ISO 14652, cuya copia se puede descargar desde el sitio web open-std.org. Se puede leer otra descripción del formato de archivo en especificaciones POSIX de grupo abierto. Como alternativa a leer el estándar, puedes estudiar el código fuente de la función. intercalar_leer в glibc/locale/programs/ld-collate.c.

La estructura del archivo se ve así:

De forma predeterminada, el carácter se utiliza como carácter de escape y el final de la línea después del carácter # es un comentario. Ambos símbolos se pueden redefinir, que es lo que se hace en la nueva versión de la tabla:

escape_char /
comment_char %

El archivo contendrá tokens en el formato o (donde x - dígito hexadecimal). Esta es la representación hexadecimal de los puntos del código Unicode en la codificación. UCS-4 (UTF-32). Todos los demás elementos entre paréntesis angulares (incluidos , y similares) se consideran constantes de cadena simples que tienen poco significado fuera de contexto.

Cadena LC_COLLATE nos dice que a continuación comienzan los datos que describen la comparación de cadenas.

Primero, se especifican los nombres de los pesos en la tabla de comparación y los nombres de las combinaciones de símbolos. En general, los dos tipos de nombres pertenecen a dos entidades diferentes, pero en el archivo real están mezclados. Los nombres de los pesos se especifican mediante la palabra clave. símbolo de clasificación (carácter de comparación) porque al comparar, los caracteres Unicode que tengan el mismo peso se considerarán caracteres equivalentes.

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

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ímbolo de cotejo registra una cadena OSMANYA en la tabla de nombres de escalas
símbolo de cotejo .. registra una secuencia de nombres que consta de un prefijo S y sufijo numérico hexadecimal de 1D000 a 1D35F.
FFFF в símbolo de cotejo parece un entero grande sin signo en hexadecimal, pero es solo un nombre que podría parecerse
nombre significa punto de código en codificación UCS-4
elemento de cotejo de " " registra un nuevo nombre para un par de puntos Unicode.

Una vez definidos los nombres de los pesos, se especifican los pesos reales. Dado que en comparación sólo importan las relaciones de mayor que menor, los pesos se determinan mediante una secuencia simple de nombres de listas. Primero se enumeran los pesos "más ligeros" y luego los "más pesados". Permítanme recordarles que a cada carácter Unicode se le asignan cuatro pesos diferentes. Aquí se combinan en una única secuencia ordenada. En teoría, cualquier nombre simbólico podría usarse en cualquiera de los cuatro niveles, pero los comentarios indican que los desarrolladores separan mentalmente los nombres en niveles.

% 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

Por último, la tabla de pesos reales.

La sección de pesos está encerrada entre líneas de palabras clave. inicio_orden и fin_pedido. Opciones adicionales inicio_orden determinar en qué dirección se escanean las filas en cada nivel de comparación. La configuración predeterminada es HACIA EL FUTURO. El cuerpo de la sección consta de líneas que contienen el código del símbolo y sus cuatro pesos. El código de carácter puede estar representado por el propio carácter, un punto de código o un nombre simbólico definido previamente. También se pueden dar pesos a nombres simbólicos, puntos de código o a los símbolos mismos. Si se utilizan puntos de código o caracteres, su peso es el mismo que el valor numérico del punto de código (posición en la tabla Unicode). Los caracteres no especificados explícitamente (según tengo entendido) se consideran asignados a la tabla con un peso principal que coincide con la posición en la tabla Unicode. Valor de peso especial IGNORAR significa que el símbolo se ignora en el nivel apropiado de comparación.

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

personajes que son completamente ignorados
símbolos equivalentes al número tres en los dos primeros niveles
el comienzo del alfabeto cirílico, que no contiene signos diacríticos y, por lo tanto, está ordenado principalmente por el primer y tercer nivel.

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

Ahora puedes volver a ordenar los ejemplos desde el principio del artículo. La emboscada se encuentra en esta parte de la tabla de pesos:

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

Se puede observar que en esta tabla los signos de puntuación de la tabla ASCII (incluido el espacio) casi siempre se ignora al comparar cadenas. Las únicas excepciones son las líneas que coinciden en todo excepto los signos de puntuación que se encuentran en posiciones coincidentes. Las líneas de mi ejemplo (después de ordenar) para el algoritmo de comparación se ven así:

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

Teniendo en cuenta que en la tabla de escalas, las letras mayúsculas en ruso van después de las minúsculas (en el tercer nivel mas pesado que ), la clasificación parece absolutamente correcta.

Al configurar una variable LC_COLLATE=C Se carga una tabla especial que especifica una comparación byte por 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'
};

Dado que en Unicode el punto de código Ё va antes que A, las cadenas se ordenan en consecuencia.

Tablas de texto y binarias.

Obviamente, la comparación de cadenas es una operación extremadamente común y el análisis de tablas CTT un procedimiento bastante costoso. Para optimizar el acceso a la tabla, se compila en formato binario con el comando definición local.

Equipo definición local acepta como parámetros un archivo con una tabla de características nacionales (opción -i), en el que todos los caracteres están representados por puntos Unicode, y un archivo de correspondencia entre puntos Unicode y caracteres de una codificación específica (opción -f). Como resultado del trabajo, se crean archivos binarios para la configuración regional con el nombre especificado en el último parámetro.

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

El formato tradicional significa que el nombre de la configuración regional es el nombre del subdirectorio en /usr/lib/locale/. Este subdirectorio almacena archivos binarios. LC_COLLATE, LC_CTYPE, LC_TIME etcétera. Archivo LC_IDENTIFICACIÓN contiene el nombre formal de la configuración regional (que puede ser diferente del nombre del directorio) y comentarios.

El formato moderno implica almacenar todas las configuraciones regionales en un único archivo. / usr / lib / locale / locale-archive, que se asigna a la memoria virtual de todos los procesos utilizando glibc. El nombre de la localidad en el formato moderno está sujeto a cierta canonización: en los nombres codificados solo permanecen números y letras reducidos a minúsculas. Entonces ru_RU.KOI8-R, se guardará como ru_RU.koi8r.

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

Por ejemplo, el comando

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

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 bajo el nombre ru_RU.maccirílico

Si configuras la variable LANG = en_US.UTF-8 que glibc buscará binarios locales 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 un lugar se presenta tanto en formato tradicional como moderno, entonces se le da prioridad al moderno.

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

Preparando tu tabla comparativa

Ahora, armado con el conocimiento, puedes crear tu propia tabla de comparación de cadenas ideales. Esta tabla debe comparar correctamente las letras rusas, incluida la letra Ё, y al mismo tiempo tener en cuenta los signos de puntuación de acuerdo con la tabla. ASCII.

El proceso de preparar tu propia tabla de clasificación consta de dos etapas: editar la tabla de pesos y compilarla en formato binario con el comando definición local.

Para que la tabla comparativa se ajuste con costos mínimos de edición, en el formato ISO 14652 Se proporcionan secciones para ajustar los pesos de una mesa existente. La sección comienza con una palabra clave. reordenar después e indicando la posición tras la cual se realiza la sustitución. La sección termina con la línea. fin de reorden. Si es necesario corregir varias secciones de la tabla, se crea una sección para cada una de esas secciones.

Copié nuevas versiones de los archivos. iso14651_t1_común и es_ES del repositorio glibc a mi directorio de inicio ~/.local/share/i18n/locales/ y edité ligeramente la sección LC_COLLATE в es_ES. Las nuevas versiones de archivos son totalmente compatibles con mi versión. glibc. Si desea utilizar versiones anteriores de archivos, deberá cambiar los nombres simbólicos y el lugar donde comienza el reemplazo en la tabla.

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 hecho, sería necesario cambiar los campos en LC_IDENTIFICACIÓN para que apunten a la localidad ru_MY, pero en mi ejemplo esto no fue necesario, ya que excluí el archivo de la búsqueda de configuraciones regionales archivo local.

Que definición local Trabajé con archivos en mi carpeta a través de una variable. I18NPATH Puede agregar un directorio adicional para buscar archivos de entrada y el directorio para guardar 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 IDIOMA puede escribir rutas absolutas a directorios con archivos locales, comenzando con una barra diagonal, pero glibc в Linux todas las rutas se cuentan desde el directorio base, que se puede anular mediante una variable RUTA LOCP. Después de la instalación LOCPATH=~/.local/lib/locale/ Todos los archivos relacionados con la localización se buscarán solo en mi carpeta. Archivo de locales con el conjunto de variables. RUTA LOCP ignorado

Aquí está la prueba decisiva:

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

¡Hurra! ¡Lo hicimos!

Algunos errores

Ya respondí las preguntas sobre la clasificación de cadenas planteadas al principio, pero todavía quedan un par de preguntas sobre errores, visibles e invisibles.

Volvamos al problema original.

y el programa sort y programa únete utilizar las mismas funciones de comparación de cadenas de glibc. ¿Cómo sucedió que únete dio un error de clasificación en las filas ordenadas por el comando sort en el local en_US.UTF-8? La respuesta es simple: sort compara toda la cadena, y únete compara solo la clave, que de forma predeterminada es el comienzo de la cadena hasta el primer carácter de espacio en blanco. En mi ejemplo, esto resultó en un mensaje de error porque la clasificación de las primeras palabras en las líneas no coincidía con la clasificación de las líneas completas.

Lugar "C" garantiza que en las cadenas ordenadas también se ordenarán las subcadenas iniciales hasta el primer espacio, pero esto sólo enmascara el error. Es posible seleccionar datos (personas con los mismos apellidos, pero nombres diferentes) que, sin el mensaje de error, darían un resultado de combinación de archivos incorrecto. si queremos únete líneas de archivos fusionadas por nombre completo, entonces la forma correcta sería especificar explícitamente el separador de campos y ordenar por el campo clave, y no por la línea completa. En este caso, la fusión se realizará correctamente y no habrá errores en ninguna configuración regional:

$> 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 codificación. CP1251 contiene otro error. El caso es que en todas las distribuciones que conozco Linux A los paquetes les falta la configuración regional compilada. ru_RU.CP1251. Si no se encuentra la configuración regional compilada, entonces sort utiliza silenciosamente una comparación byte por byte, que es lo que observamos.

Por cierto, hay otro pequeño fallo relacionado con la inaccesibilidad de las configuraciones regionales compiladas. Equipo LOCPATH=/tmp configuración regional -a le dará una lista de todas las configuraciones regionales en archivo local, pero con la variable establecida RUTA LOCP para todos los programas (incluidos los más local) estas configuraciones regionales no estarán 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ón

Si es un programador acostumbrado a pensar que las cadenas son un conjunto de bytes, entonces su elección LC_COLLATE=C.

Si es lingüista o compilador de diccionarios, será mejor que compile en su localidad.

Si es un usuario sencillo, sólo necesita acostumbrarse al hecho de que el comando ls -a genera archivos que comienzan con un punto mezclados con archivos que comienzan con una letra, y Comandante de medianoche, que utiliza sus funciones internas para ordenar nombres, coloca los archivos que comienzan con un punto al principio de la lista.