Introdução

Tudo começou com um pequeno script que deveria combinar informações sobre endereços e-mail de funcionários, obtidas de uma lista de usuários de mailing, com as posições dos funcionários, obtidas do banco de dados do departamento de pessoal. Ambas as listas foram exportadas para arquivos de texto em codificação Unicode UTF-8 e salvas com quebras de linha no formato Unix.

Conteúdo mail.txt

Ivanov Andrei;ia@example.com

Conteúdo buhg.txt

Ivanova Alla;pintora
Yelkina Ella;guindasteira
Ivanov Andrei;serralheiro
Abakanov Mikhail;pintor

Para combinar, os arquivos foram ordenados usando um comando Unix sort e fornecidos como entrada para um programa Unix join, que inesperadamente terminou com um erro:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: não está ordenado: Ivanov Andrei;serralheiro

A visualização do resultado da ordenação mostrou que, de modo geral, a ordenação está correta, mas em casos de coincidências de sobrenomes masculinos e femininos, os femininos aparecem antes dos masculinos:

$> sort buhg.txt
Abakanov Mikhail;pintor
Yelkina Ella;guindasteira
Ivanova Alla;pintora
Ivanov Andrei;serralheiro

Parece ser um bug na ordenação em Unicode ou uma manifestação de feminismo no algoritmo de ordenação. A primeira, claro, é mais plausível.

Vamos deixar isso de lado join e nos concentrar em sort. Vamos tentar resolver o problema pelo método da tentativa e erro. Para começar, vamos mudar a localidade de en_US para ru_RU. Para a ordenação, teria sido suficiente definir a variável de ambiente LC_COLLATE, mas não vamos ser mesquinhos:

$> LANG=ru_RU.UTF-8 sort buhg.txt
Abakanov Mikhail;pintor
Yelkina Ella;guindasteira
Ivanova Alla;pintora
Ivanov Andrei;serralheiro

Nada mudou.

Vamos tentar reencodar os arquivos em uma codificação de byte único:

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

Novamente, nada mudou.

Não tem jeito, teremos que buscar a solução na internet. Não há nada específico sobre sobrenomes russos, mas existem perguntas sobre outras estranhezas da ordenação. Veja, por exemplo, este problema: a ordenação unix trata caracteres ‘-‘ (hífen) como invisíveis. Resumindo, as strings "a-b", "aa", "ac" são ordenadas como "aa", "a-b", "ac".

A resposta em todos os lugares é padrão: use a localidade de programação "C" e será a sua felicidade. Vamos tentar:

$> LANG=C sort buhg.txt
Yelkina Ella;guindasteira
Abakanov Mikhail;pintor
Ivanov Andrei;serralheiro
Ivanova Alla;advogada

Algo mudou. Os Ivanovs foram organizados na ordem correta, embora Yelkina tenha desaparecido. Vamos voltar à tarefa original:

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

Funcionou sem erros, como prometido pela internet. E isso apesar de Ёлкин na primeira linha.

O problema parece ter sido resolvido, mas por precaução vamos tentar mais uma codificação russa — a do Windows. CP1251:

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

O resultado da ordenação, curiosamente, coincidirá com a localidade "C", e todo o exemplo, consequentemente, passa sem erros. É uma espécie de misticismo.

Eu não gosto de misticismo na programação, pois, geralmente, isso esconde erros. Terei que me debruçar seriamente sobre a questão de como funciona sort e o que influencia LC_COLLATE .

No final, tentarei responder às perguntas:

por que os sobrenomes femininos estavam sendo ordenados incorretamente
por que LANG=ru_RU.CP1251 acabou sendo equivalente LANG=C
por que há sort e join diferentes representações da ordem das linhas ordenadas
por que há erros em todos os meus exemplos
e, finalmente, como ordenar linhas ao meu gosto

Ordenação em Unicode

A primeira parada será o relatório técnico nº 10 intitulado Unicode collation algorithm no site unicode.org. O relatório contém muitos detalhes técnicos, então permitirei-me apresentar um resumo das principais ideias.

Colação — "comparação" de strings — é a base de qualquer algoritmo de ordenação. Os próprios algoritmos podem diferir ("bolha", "mesclagem", "rápido"), mas todos utilizarão a comparação de pares de strings para determinar a ordem de sua sequência.

A ordenação de strings em uma língua natural é um problema bastante complexo. Mesmo nas mais simples codificações de um byte, a ordem das letras no alfabeto, mesmo que algo diferente do alfabeto latino inglês, já não coincidirá com a ordem dos valores numéricos com os quais essas letras são codificadas. Assim, na língua alemã, a letra Ö ocupa uma posição entre A e P, enquanto na codificação CP850 ela entre ÿ e Ü.

Pode-se tentar abstrair-se da codificação específica e considerar letras "ideais", que estão dispostas em uma certa ordem, como é feito no Unicode. As codificações UTF8, UTF16 ou a de um byte KOI8-R (se for necessário um subconjunto limitado do Unicode) darão diferentes representações numéricas das letras, mas referindo-se aos mesmos elementos da tabela básica.

Descobriu-se que mesmo construindo uma tabela de caracteres do zero, não conseguiremos estabelecer uma ordem universal para os caracteres. Em diferentes alfabetos nacionais que utilizam as mesmas letras, a ordem dessas letras pode variar. Por exemplo, na língua francesa Æ será considerada uma ligadura e ordenada como uma string AE. Já na língua norueguesa Æ será uma letra separada, que aparece após Z. A propósito, além de ligaduras como Æ existem letras que são escritas com vários símbolos. Assim, no alfabeto tcheco, há a letra Ch, que está entre H e I.

Além das diferenças nos alfabetos, existem outras tradições nacionais que influenciam a ordenação. Em particular, surge a questão: qual deve ser a ordem das palavras em um dicionário que consistem de letras maiúsculas e minúsculas? Além disso, a pontuação pode influenciar a ordenação. Na língua espanhola, no início de uma frase interrogativa, coloca-se um ponto de interrogação invertido (¿Te gusta la música?). Nesse caso, é evidente que as frases interrogativas não devem ser agrupadas em um cluster separado fora do alfabeto, mas como devem ser ordenadas as strings com outros sinais de pontuação?

Não vou entrar na ordenação de strings em idiomas que diferem muito dos europeus. Destaco que em línguas com direção de escrita da direita para a esquerda ou de cima para baixo, os caracteres nas strings provavelmente são armazenados na ordem de leitura, e mesmo em sistemas de escrita não alfabéticos existem maneiras próprias de ordenar strings caracter por caracter. Por exemplo, os ideogramas podem ser ordenados de acordo com os seus traços (chaves de ideogramas chineses) ou pela pronúncia. Como os emojis devem ser ordenados, honestamente não sei, mas também pode-se inventar algo para eles.

Com base nas características mencionadas acima, foram formulados os principais requisitos para a comparação de strings, baseados em tabelas Unicode:

a comparação de strings não depende da posição dos caracteres na tabela de códigos;
as sequências de caracteres que formam um único símbolo são trazidas à forma canônica (A + um círculo superior é o mesmo que Å);
) ao comparar strings, o símbolo é considerado no contexto da string e, quando necessário, é combinado com vizinhos em uma única unidade de comparação (Ch em tcheco) ou dividido em várias (Æ em francês);
todas as características nacionais (alfabeto, maiúsculas/minúsculas, pontuação, ordem dos tipos de escrita) devem ser configuradas até a atribuição manual da ordem (emoji);
a comparação é importante não apenas para a ordenação, mas também em muitos outros lugares, como para definir intervalos de linhas (substituição {A… z} em bash);
a comparação deve ser realizada de forma suficientemente rápida.

Além disso, os autores do relatório formularam propriedades de comparação nas quais os desenvolvedores de algoritmos não devem confiar:

o algoritmo de comparação não deve exigir um conjunto separado de caracteres para cada idioma (o russo e o ucraniano usam a maioria dos caracteres cirílicos em conjunto);
a comparação não deve depender da ordem dos caracteres nas tabelas Unicode;
o peso da string não deve ser um atributo da string, uma vez que a mesma string em diferentes contextos culturais pode ter pesos diferentes;
os pesos das strings podem mudar ao mesclar ou dividir (de x < y não se deve entender que xz < yz);
strings diferentes que têm o mesmo peso são consideradas iguais do ponto de vista do algoritmo de ordenação. A introdução de uma ordenação adicional dessas strings é possível, mas pode prejudicar o desempenho;
em ordenações subsequentes, strings que têm o mesmo peso podem trocar de lugar. A estabilidade é uma propriedade de um algoritmo específico de ordenação, e não uma propriedade do algoritmo de comparação de strings (veja o ponto anterior);
as regras de ordenação podem mudar ao longo do tempo à medida que as tradições culturais são refinadas/mudadas.

Assim, está estipulado que o algoritmo de comparação não sabe nada sobre a semântica das strings processadas. Portanto, strings compostas apenas por dígitos não devem ser comparadas como números, e nos listas de nomes em inglês, o artigo não deve ser removido (Beatles, The).

Para atender a todos os requisitos mencionados, foi proposto um algoritmo de ordenação em múltiplos níveis (na verdade, de quatro níveis).

Preliminarmente, os caracteres da string são convertidos para a forma canônica e agrupados em unidades de comparação. A cada unidade de comparação são atribuídos vários pesos, correspondendo a diferentes níveis de comparação. Os pesos das unidades de comparação são elementos de conjuntos ordenados (neste caso, números inteiros) que podem ser comparados em relação a maior-menor. Um valor especial IGNORED (0x0) significa que, no nível de comparação correspondente, essa unidade não participa da comparação. A comparação de strings pode ser repetida várias vezes, usando os pesos dos níveis correspondentes. Em cada um dos níveis, os pesos das unidades de comparação de duas strings são comparados sequencialmente entre si.

Em várias implementações do algoritmo para diferentes tradições nacionais, os valores dos coeficientes podem variar, mas a tabela básica de pesos inclui-se no padrão Unicode — "Default Unicode Collation Element Table" (DUCET). Desejo observar que a definição da variável LC_COLLATE é na verdade a indicação da escolha da tabela de pesos na função de comparação de strings.

Os coeficientes de peso DUCET são dispostos da seguinte maneira:

no primeiro nível, todas as letras são convertidas para um único caso, os diacríticos são descartados e a pontuação (não toda) é ignorada;
no segundo nível, apenas os diacríticos são levados em conta;
no terceiro nível, apenas o caso é considerado;
no quarto nível, apenas a pontuação é considerada.

A comparação ocorre em várias passagens: primeiro, os coeficientes do primeiro nível são comparados; se os pesos coincidirem, uma nova comparação com os pesos do segundo nível ocorre; então, talvez, do terceiro e quarto níveis.

A comparação termina quando as strings contêm unidades de comparação correspondentes com pesos diferentes. Strings que têm pesos iguais em todos os quatro níveis são consideradas iguais entre si.

Este algoritmo (com muitas detalhes técnicos adicionais) deu nome ao relatório nº 10 — "Unicode Collation Algorithm" (UCA).

Neste ponto, o comportamento de classificação do nosso exemplo torna-se um pouco mais claro. Seria bom compará-lo com o padrão Unicode.

Para testar implementações UCA existe um teste, utilizando um arquivo de pesos, implementando DUCET. No arquivo de pesos, você pode encontrar várias curiosidades. Por exemplo, há a ordem das peças de mahjong e do dominó europeu, assim como a ordem dos naipes em um baralho de cartas (símbolo 1F000 e assim por diante). Os naipes estão dispostos de acordo com as regras do bridge — PCHBT, e as cartas nos naipes — na sequência T,2,3… K.

Verificação manual da correção da classificação das strings de acordo com DUCET seria bastante cansativa, mas, felizmente para nós, existe uma implementação exemplar da biblioteca para trabalhar com Unicode — "International Components for Unicode" (ICU).

No site dessa biblioteca, desenvolvida em IBM, há páginas de demonstração, incluindo a página do algoritmo de comparação de strings. Inserimos nossas strings de teste com as configurações padrão e, oh maravilha, obtemos uma perfeita ordenação russa.

Abakanov Mikhail;pintor
Yolkina Ella;operadora de guindaste
Ivanov Andrei;serralheiro
Ivanova Alla;advogada

A propósito, no site ICU é possível encontrar esclarecimentos sobre o funcionamento do algoritmo de comparação ao lidar com sinais de pontuação. Nos exemplos Collation FAQ são ignorados apóstrofo e hífen.

O Unicode nos ajudou, mas procurar as razões para o comportamento estranho sort em Linux teremos que fazê-lo em outro lugar.

Ordenação em glibc

Uma visualização rápida do código fonte da ferramenta sort do GNU Core Utils mostrou que na própria ferramenta a localização se resume a imprimir o valor atual da variável LC_COLLATE ao ser executada no modo de depuração:

$ sort --debug buhg.txt > buhg.srt
sort: usando regras de ordenação ‘en_US.UTF8’

A comparação de strings é realizada pela função padrão strcoll, ou seja, tudo que nos interessa está na biblioteca glibc.

Sobre wiki Apache Traffic Control glibc a comparação de strings é tratada em um parágrafo. Desse parágrafo podemos entender que em glibc a ordenação é baseada no algoritmo que já conhecemos UCA (The Unicode collation algorithm) e/ou em um padrão semelhante ISO 14651 (International string ordering and comparison). Sobre o último padrão, vale mencionar que no site standards.iso.org ISO 14651 é oficialmente declarado de acesso público, mas o link correspondente leva a uma página inexistente. O Google retorna várias páginas com links para sites oficiais que oferecem a cópia eletrônica do padrão por uma centena de euros, mas na terceira ou quarta página dos resultados de busca podem ser encontrados links diretos para PDF. No geral, o padrão não difere muito do UCA, mas é mais maçante de ler, pois não contém exemplos marcantes das particularidades nacionais na ordenação de strings.

A informação mais interessante em wiki foi o link para o rastreador de bugs com a discussão sobre a implementação da comparação de strings em glibc. Da discussão, podemos descobrir que em glibc para a comparação de strings é utilizada ISOa tabela The Common Template Table (CTT), cujo endereço pode ser encontrado no apêndice A do padrão ISO 14651. Entre 2000 e 2015, essa tabela em glibc não tinha um mantenedor e diferia bastante (pelo menos externamente) da versão atual do padrão. De 2015 a 2018, houve uma adaptação à nova versão da tabela e, atualmente, você pode encontrar na prática tanto a nova versão da tabela (CentOS 8) quanto a antiga (CentOS 7).

Agora que temos todas as informações sobre o algoritmo e as tabelas auxiliares, podemos voltar ao problema original e entender como classificar corretamente as linhas na localidade russa.

ISO 14651/14652

O código-fonte da tabela que nos interessa CTT na maioria das distribuições Linux está localizado no diretório /usr/share/i18n/locales/. A própria tabela está no arquivo iso14651_t1_common. Depois, esse arquivo é incluído no arquivo de diretiva copy iso14651_t1_common que é incluído no arquivo iso14651_t1, que, por sua vez, é incluído nos arquivos nacionais, incluindo en_US e ru_RU. Na maioria das distribuições Linux todos os arquivos-fonte estão incluídos na instalação básica, mas se eles não estiverem presentes, será necessário instalar o pacote adicional da distribuição.

A estrutura do arquivo iso14651_t1 pode parecer horrivelmente prolixo, com regras de construção de nomes pouco claras, mas, se você entender, tudo é bem simples. A estrutura é descrita no padrão ISO 14652, uma cópia do qual pode ser baixada do site open-std.org. Outra descrição do formato do arquivo pode ser lida no especificações POSIX de OpenGroup. Como alternativa à leitura do padrão, você pode estudar os códigos-fonte da função collate_read em glibc/locale/programs/ld-collate.c.

A estrutura do arquivo é a seguinte:

Por padrão, o símbolo é usado como o caractere de escape e o final da linha após o símbolo # é um comentário. Ambos os símbolos podem ser redefinidos, o que foi feito na nova versão da tabela:

escape_char /
comment_char %

O arquivo conterá tokens no formato <Uxxxx> ou <Uxxxxxxxx> (onde x — dígito hexadecimal). Esta é a representação hexadecimal dos pontos de código Unicode na codificação UCS-4 (UTF-32). Todos os outros elementos entre colchetes (incluindo <Uxxxx_xxxx>, <2> e semelhantes), são consideradas constantes de string simples, sem significado especial fora do contexto.

String LC_COLLATE diz-nos que os dados que descrevem a comparação de strings começam a seguir.

Primeiro, são definidos os nomes para os pesos na tabela de comparação e os nomes para as combinações de caracteres. De maneira geral, dois tipos de nomes pertencem a duas entidades diferentes, mas no arquivo real eles estão misturados. Os nomes dos pesos são definidos pela palavra-chave collating-symbol (caractere de comparação), pois, ao comparar caracteres Unicode com pesos idênticos, eles serão considerados como caracteres equivalentes.

O comprimento total da seção na revisão atual do arquivo é de cerca de 900 linhas. Eu extraí exemplos de vários lugares para mostrar a arbitrariedade dos nomes e alguns tipos de sintaxe.

LC_COLLATE

collating-symbol 
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol 
collating-symbol 
collating-symbol 
...
collating-symbol ..
collating-symbol  % Garantido, o maior valor de símbolo. Mantenha no final desta lista
...
collating-element  de ""
collating-element  de ""

collating-symbol registra a string OSMANYA na tabela de nomes de pesos
collating-symbol .. registra uma sequência de nomes composta por um prefixo S e um sufixo numérico hexadecimal de 1D000 até 1D35F.
FFFF em collating-symbol parece um grande inteiro sem sinal na representação hexadecimal, mas <SFFFF> é apenas um nome que poderia parecer como <VERYBIGVAL>
nome <U0413> significa um ponto de código na codificação UCS-4
collating-element de "" registra um novo nome para um par de pontos Unicode.

Quando os nomes de pesos são definidos, os pesos propriamente ditos são atribuídos. Como somente as relações de maior e menor são relevantes na comparação, os pesos são determinados por uma sequência simples de enumeração de nomes. Começa-se listando os pesos mais "leves", seguidos pelos mais "pesados". Lembro que a cada símbolo Unicode é atribuído quatro pesos diferentes. Aqui, eles são reunidos em uma única sequência ordenada. Teoricamente, qualquer nome simbólico pode ser utilizado em qualquer um dos quatro níveis, mas os comentários indicam que os desenvolvedores mentalmente dividem os nomes pelos níveis.

% Atribuições de peso simbólico

% Atribuições de peso de terceiro nível




...
% Atribuições de peso de segundo nível

 % LINHA BAIXA COMBINANTE
 % VINHO COMBINANTE ACIMA
 % VINHO INVERTIDO COMBINANTE ACIMA
...
% Atribuições de peso de primeiro nível
 % TABULAÇÃO HORIZONTAL 
 % QUEBRA DE LINHA
 % TABULAÇÃO VERTICAL
...
 % LETRA MINÚSCULA CYRILLIC DE
 % LETRA MINÚSCULA CYRILLIC KOMI DE
 % LETRA MINÚSCULA CYRILLIC DJE
 % LETRA MINÚSCULA CYRILLIC KOMI DJE
 % LETRA MINÚSCULA CYRILLIC GJE
 % LETRA MINÚSCULA CYRILLIC ZE COM DESCENSOR
 % LETRA MINÚSCULA CYRILLIC IE
 % LETRA MINÚSCULA CYRILLIC IE COM BREVE
 % LETRA MINÚSCULA CYRILLIC UE UCRANIANO
 % LETRA MINÚSCULA CYRILLIC ZHE

Finalmente, a tabela de pesos propriamente dita.

A seção de pesos está contida em linhas com palavras-chave order_start e order_end. Parâmetros adicionais order_start definem em que direção as linhas são visualizadas em cada nível de comparação. Por padrão, é utilizado o parâmetro forward. O corpo da seção consiste em linhas que contêm o código do símbolo e seus quatro pesos. O código do símbolo pode ser representado pelo próprio símbolo, pelo ponto de código ou pelo nome simbólico definido anteriormente. Os pesos também podem ser definidos por nomes simbólicos, pontos de código ou pelos próprios símbolos. Se forem utilizados pontos de código ou símbolos, seu peso corresponde ao valor numérico do ponto de código (posição na tabela Unicode). Os símbolos não explicitamente listados (na minha compreensão) são considerados como atribuídos à tabela com um peso primário igual à posição na tabela Unicode. O valor especial de peso IGNORE significa que, no nível de comparação correspondente, esse símbolo é ignorado.

Para demonstrar a estrutura dos pesos, escolhi três fragmentos bastante óbvios:

símbolos que são completamente ignorados
símbolos equivalentes ao número três nos dois primeiros níveis
o início do alfabeto cirílico, que não contém sinais diacríticos, portanto, é classificado principalmente pelos primeiros e terceiros níveis.

order_start forward;forward;forward;forward,position
 IGNORE;IGNORE;IGNORE;IGNORE % NULL (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF HEADING (in 6429)
 IGNORE;IGNORE;IGNORE;IGNORE % START OF TEXT (in 6429)
...
 ;;; % DIGIT THREE
 ;;; % FULLWIDTH DIGIT THREE
 ;;; % PARENTHESIZED DIGIT THREE
 ;;; % DIGIT THREE FULL STOP
 ;;; % MATHEMATICAL BOLD DIGIT THREE
...
 ;;; % CYRILLIC SMALL LETTER A
 ;;; % CYRILLIC CAPITAL LETTER A
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
 ;;; % CYRILLIC SMALL LETTER A WITH BREVE
...
 ;;; % CYRILLIC SMALL LETTER BE
 ;;; % CYRILLIC CAPITAL LETTER BE
 ;;; % CYRILLIC SMALL LETTER VE
 ;;; % CYRILLIC CAPITAL LETTER VE
...
order_end

Agora podemos voltar à ordenação dos exemplos do início do artigo. A pegadinha está nesta parte da tabela de pesos:

IGNORE;IGNORE;IGNORE; % ESPAÇO
 IGNORE;IGNORE;IGNORE; % PONTO DE EXCLAMAÇÃO
 IGNORE;IGNORE;IGNORE; % ASPAS
...

É evidente que nesta tabela os sinais de pontuação estão presentes na tabela ASCII (incluindo espaços) ao comparar strings, geralmente é ignorado. A única exceção são as strings que coincidem em tudo, exceto nos sinais de pontuação que aparecem nas posições correspondentes. As strings do meu exemplo (após a ordenação) para o algoritmo de comparação são assim:

AbakanovMikhailPintor
YolkinaEllacranovreparadora
IvanovaAllaPintor
IvanovAndreiSerralheiro

Tendo em conta que na tabela de pesos as letras maiúsculas em russo vêm após as minúsculas (no terceiro nível <CAP> mais pesadas do que <MIN>), a ordenação parece absolutamente correta.

Ao definir a variável LC_COLLATE=C é carregada uma tabela especial que define a comparação byte a byte

static const uint32_t collseqwc[] =
{
  8, 1, 8, 0x0, 0xff,
  /* tabela de 1º nível */
  6 * sizeof (uint32_t),
  /* tabela de 2º nível */
  7 * sizeof (uint32_t),
  /* tabela de 3º nível */
  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'
};

Como no Unicode o ponto de código Ё está antes de А, as strings são ordenadas de acordo.

Tabelas textuais e binárias

É óbvio que a comparação de strings é uma operação extremamente comum, enquanto o processamento da tabela CTT é um procedimento bastante oneroso. Para otimizar o acesso à tabela, ela é compilada em forma binária pelo comando localedef.

Time localedef que recebe como parâmetros um arquivo com a tabela de particularidades nacionais (opção -i), onde todos os símbolos são representados por pontos Unicode, e um arquivo de correspondência entre pontos Unicode e símbolos de uma codificação específica (opção --follow). Como resultado da execução, são criados arquivos binários para a localidade, com o nome especificado no último parâmetro.

Glibc suporta dois formatos de arquivos binários: "tradicional" e "moderno".

O formato tradicional implica que o nome da localidade é o nome de um subdiretório em /usr/lib/locale/. Neste subdiretório estão armazenados arquivos binários LC_COLLATE, LC_CTYPE, LC_TIME etc. O arquivo LC_IDENTIFICATION contém o nome formal da localidade (que pode diferir do nome do diretório) e comentários.

O formato moderno presume que todas as localidades sejam armazenadas em um único arquivo /usr/lib/locale/locale-archive, que é mapeado na memória virtual de todos os processos que o utilizam glibcO nome da localidade no formato moderno é sujeito a uma certa canonização — nos nomes de codificação ficam apenas dígitos e letras, convertidos para minúsculas. Assim pt_BR.KOI8-R, será mantido como pt_BR.koi8r.

Os arquivos de entrada são procurados no diretório atual e também nos diretórios /usr/share/i18n/locales/ e /usr/share/i18n/charmaps/ para arquivos CTT e arquivos de codificações, respectivamente.

Por exemplo, o comando

localedef -i pt_BR -f MAC-CYRILLIC pt_BR.MAC-CYRILLIC

compilará o arquivo /usr/share/i18n/locales/ru_RU usando o arquivo de codificação /usr/share/i18n/charmaps/MAC-CYRILLIC.gz e salvará o resultado em /usr/lib/locale/locale-archive com o nome pt_BR.maccyrillic

Se a variável LANG=en_US.UTF-8 for definida, glibc será feita a busca por arquivos binários de localidades na seguinte sequência de arquivos e diretórios:

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

Se a localidade aparecer tanto nos formatos tradicionais quanto modernos, a prioridade será dada ao moderno.

Para visualizar a lista de localidades compiladas, pode-se usar o comando locale -a.

Preparando sua própria tabela de comparação

Agora, armado com conhecimento, você pode criar sua própria tabela de comparação ideal. Esta tabela deve comparar corretamente as letras russas, incluindo a letra Ё, e também considerar a pontuação de acordo com a tabela ASCII.

O processo de preparação da sua tabela de ordenação consiste em duas etapas: edição da tabela de pesos e compilação dela em forma binária com o comando localedef.

Para que a tabela de comparação possa ser ajustada com o mínimo de esforço de edição, o formato ISO 14652 prevê seções de ajuste de pesos já existentes na tabela. A seção começa com a palavra-chave reorder-after e a indicação da posição após a qual a substituição é feita. A seção é encerrada pela linha reorder-end. Se for necessário corrigir várias partes da tabela, deve-se criar uma seção para cada uma delas.

Eu copiei novas versões dos arquivos iso14651_t1_common e ru_RU do repositório glibc para meu diretório pessoal ~/.local/share/i18n/locales/ e fiz algumas edições no trecho LC_COLLATE em ru_RU. As novas versões dos arquivos são totalmente compatíveis com minha versão glibc. Se você quiser usar as versões antigas dos arquivos, terá que alterar os nomes simbólicos e o local de onde começa a substituição na tabela.

LC_COLLATE
% Copie o modelo do ISO/IEC 14651
copy "iso14651_t1"
reorder-after 
 ;;; % ESPAÇO
 ;;; % PONTO DE EXCLAMAÇÃO
 ;;; % ASPAS
...
 ;;; % CHAVE DIREITA
 ;;; % TILDA
reorder-end
END LC_COLLATE

Na verdade, eu deveria ter trocado os campos em LC_IDENTIFICATION para que eles apontassem para a localidade pt_BR, mas no meu exemplo isso não foi necessário, pois eu excluí da busca as localidades do arquivo locale-archive.

Para localedef trabalhava com os arquivos na minha pasta através da variável I18NPATH pode-se adicionar um diretório adicional para buscar arquivos de entrada, enquanto o diretório para salvar arquivos binários pode ser fornecido como um caminho com barras:

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

POSIX supõe-se que em LANG pode-se escrever caminhos absolutos para diretórios com arquivos de localidade que começam com uma barra, mas glibc em Linux todos os caminhos são considerados a partir do diretório base, que pode ser redefinido através da variável LOCPATH. Após definir LOCPATH=~/.local/lib/locale/ todos os arquivos relacionados à localização serão procurados apenas na minha pasta. O arquivo de localidades com a variável LOCPATH é ignorado.

Aqui está o teste decisivo:

$> LANG=pt_BR.UTF-8 LOCPATH=~/.local/lib/locale/ sort buhg.txt
Abakanov Mikhail;pintor
Yolkina Ella;guindasteira
Ivanov Andrei;encanador
Ivanova Alla;advogada

Uhu! Conseguimos!

Trabalhando nos erros

Já respondi às perguntas sobre a ordenação de linhas, feitas no início, mas ainda restam algumas questões sobre erros — visíveis e invisíveis.

Vamos voltar para a tarefa original.

E o programa sort e o programa join usam as mesmas funções de comparação de strings de glibc. Como isso ocorreu que join gerou um erro de ordenação em linhas ordenadas pelo comando sort na localidade en_US.UTF-8? Ответ прост: sort compara a string inteira, enquanto join compara apenas a chave, que por padrão é o início da string até o primeiro caractere de espaço. No meu exemplo, isso levou a uma mensagem de erro, pois a ordenação das primeiras palavras nas linhas não coincidiu com a ordenação das strings completas.

Localidade "C" garante que nas linhas classificadas as substrings iniciais até o primeiro espaço também estarão classificadas, mas isso apenas mascarará o erro. É possível selecionar dados como (pessoas com sobrenomes iguais, mas nomes diferentes), que sem a mensagem de erro resultariam em um resultado incorreto na fusão de arquivos. Se quisermos que join combine linhas de arquivos por nome completo, a maneira correta seria especificar claramente o delimitador de campos e classificar pela chave primária, e não por toda a linha. Dessa forma, a fusão ocorrerá corretamente e não haverá erros em nenhuma localidade:

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

Um exemplo executado com sucesso na codificação CP1251 contém mais um erro. O fato é que em todas as distribuições que conheço Linux faltam pacotes com a localidade compilada ru_RU.CP1251. Se a localidade compilada não for encontrada, então sort utiliza silenciosamente a comparação byte a byte, que é o que observamos.

Aliás, há mais um pequeno bug relacionado à indisponibilidade de localidades compiladas. O comando LOCPATH=\/tmp locale -a produzirá uma lista de todas as localidades em locale-archive, mas com a variável definida LOCPATH para todos os programas (incluindo o próprio locale) essas localidades estarão indisponíveis.

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

Conclusão

Se você é um programador que acredita que strings são conjuntos de bytes, então sua escolha LC_COLLATE=C.

Se você é um linguista ou compilador de dicionários, então é melhor compilar sua própria localidade.

Se você é um usuário comum, basta se acostumar ao fato de que o comando ls -a produz arquivos que começam com um ponto, misturados com arquivos que começam com letras, e Midnight Commander, que usa suas funções internas para classificar nomes, coloca os arquivos que começam com ponto no início da lista.