Introdução

Tudo começou com um pequeno script que deveria combinar informações de endereço o email funcionários obtidos na lista de usuários da mailing list, com cargos obtidos no banco de dados do departamento de RH. Ambas as listas foram exportadas para arquivos de texto Unicode UTF-8 e salvo com finais de linha Unix.

Conteúdo email.txt

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

Conteúdo buhg.txt

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

Para mesclar, os arquivos foram classificados pelo comando Unix tipo e submetido à entrada do programa Unix juntar, que falhou inesperadamente com um erro:

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

A visualização do resultado da ordenação com os olhos mostrou que, em geral, a ordenação é correta, mas no caso de coincidências de sobrenomes masculinos e femininos, os femininos vêm antes dos masculinos:

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

Parece uma falha de classificação no Unicode ou uma manifestação do feminismo no algoritmo de classificação. A primeira é, obviamente, mais plausível.

Vamos adiar isso por enquanto juntar e focar em tipo. Vamos tentar resolver o problema usando cutucadas científicas. Primeiro, vamos alterar a localidade de en_US em ru_RU. Para classificar, bastaria definir a variável de ambiente LC_COLLATE, mas não perderemos tempo com ninharias:

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

Nada mudou.

Vamos tentar recodificar 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 há nada que você possa fazer, você terá que procurar uma solução na Internet. Não há nada diretamente sobre sobrenomes russos, mas há dúvidas sobre outras estranhezas de classificação. Por exemplo, aqui está um problema: ordenação unix trata caracteres ‘-‘ (traço) como invisíveis. Resumindo, as strings "ab", "aa", "ac" são classificadas como "aa", "ab", "ac".

A resposta é padrão em todos os lugares: use a localidade do programador "C" e você ficará feliz. Vamos tentar:

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

Alguma coisa mudou. Os Ivanovs alinharam-se na ordem correta, embora Yolkina tenha escorregado em algum lugar. Voltemos ao problema 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 a Internet prometeu. E isso apesar de Yolkina estar na primeira linha.

O problema parece estar resolvido, mas por precaução, vamos tentar outra codificação russa - Windows CP1251:

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

O resultado da classificação, curiosamente, coincidirá com a localidade "C", e todo o exemplo, portanto, é executado sem erros. Algum tipo de misticismo.

Não gosto de misticismo na programação porque geralmente mascara erros. Teremos que analisar seriamente como isso funciona. tipo e o que isso afeta? LC_COLLATE .

No final tentarei responder às perguntas:

por que os sobrenomes femininos foram classificados incorretamente?
por que LANG=ru_RU.CP1251 acabou por ser equivalente LANG = C
por que fazer tipo и juntar ideias diferentes sobre a ordem das strings classificadas
por que há erros em todos os meus exemplos?
finalmente como classificar strings ao seu gosto

Classificando em Unicode

A primeira parada será o relatório técnico nº 10 intitulado Algoritmo de agrupamento Unicode on-line unicode.org. O relatório contém muitos detalhes técnicos, por isso permitam-me fazer um breve resumo das ideias principais.

Colação - “comparar” strings é a base de qualquer algoritmo de classificação. Os algoritmos em si podem ser diferentes ("bolha", "mesclagem", "rápido"), mas todos usarão uma comparação de um par de strings para determinar a ordem em que aparecem.

Classificar strings em linguagem natural é um problema bastante complexo. Mesmo nas codificações mais simples de byte único, a ordem das letras no alfabeto, mesmo que seja um pouco diferente do alfabeto latino inglês, não coincidirá mais com a ordem dos valores numéricos com os quais essas letras são codificadas. Assim, no alfabeto alemão, a letra Ö fica entre О и P, e na codificação CP850 ela fica entre ÿ и Ü.

Você pode tentar abstrair de uma codificação específica e considerar letras “ideais” organizadas em alguma ordem, como é feito no Unicode. Codificações Utf8, Utf16 ou um byte KOI8-R (se for necessário um subconjunto limitado de Unicode) fornecerá diferentes representações numéricas de letras, mas fará referência aos mesmos elementos da tabela base.

Acontece que mesmo se construirmos uma tabela de símbolos do zero, não seremos capazes de atribuir a ela uma ordem universal de símbolos. Em diferentes alfabetos nacionais que usam as mesmas letras, a ordem dessas letras pode ser diferente. Por exemplo, em francês Æ será considerada uma ligadura e classificada como uma string AE. Em norueguês Æ será uma letra separada, localizada após Z. Aliás, além de ligaduras como Æ Existem letras escritas com vários símbolos. Então, no alfabeto tcheco existe uma letra Ch, que fica entre H и I.

Além das diferenças nos alfabetos, existem outras tradições nacionais que influenciam a classificação. Em particular, surge a questão: em que ordem as palavras compostas por letras maiúsculas e minúsculas devem aparecer no dicionário? A classificação também pode ser afetada pelo uso de sinais de pontuação. Em espanhol, um ponto de interrogação invertido é usado no início de uma frase interrogativa (Você gosta de música?). Nesse caso, é óbvio que as sentenças interrogativas não devem ser agrupadas em um grupo separado fora do alfabeto, mas como ordenar as linhas com outros sinais de pontuação?

Não vou me alongar na classificação de strings em idiomas muito diferentes dos europeus. Observe que em idiomas com direção de escrita da direita para a esquerda ou de cima para baixo, os caracteres nas linhas são provavelmente armazenados em ordem de leitura, e mesmo os sistemas de escrita não alfabéticos têm suas próprias maneiras de ordenar as linhas caractere por caractere . Por exemplo, os hieróglifos podem ser ordenados por estilo (Chaves de caracteres chineses) ou por pronúncia. Para ser sincero, não tenho ideia de como os emojis devem ser organizados, mas você também pode inventar algo para eles.

Com base nos recursos listados acima, foram formulados os requisitos básicos para comparação de strings baseadas em tabelas Unicode:

a comparação de strings não depende da posição dos caracteres na tabela de códigos;
sequências de caracteres formando um único caractere são reduzidas à forma canônica (A + o círculo superior é igual a Å);
Ao comparar strings, um caractere é considerado no contexto da string e, se necessário, combinado com seus vizinhos em uma unidade de comparação (Ch em tcheco) ou está dividido em vários (Æ 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 classificação, mas também em muitos outros lugares, por exemplo, para especificar intervalos de linhas (substituindo {A... z} em bater);
a comparação deve ser feita rapidamente.

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

o algoritmo de comparação não deve exigir um conjunto separado de caracteres para cada idioma (os idiomas russo e ucraniano compartilham a maioria dos caracteres cirílicos);
a comparação não deve basear-se na ordem dos caracteres nas tabelas Unicode;
o peso da string não deve ser um atributo da string, pois a mesma string em diferentes contextos culturais pode ter pesos diferentes;
os pesos das linhas podem mudar ao mesclar ou dividir (de x < y isso não segue xz < yz);
strings diferentes com os mesmos pesos são consideradas iguais do ponto de vista do algoritmo de classificação. A introdução de ordenação adicional de tais strings é possível, mas pode degradar o desempenho;
Durante a classificação repetida, as linhas com os mesmos pesos podem ser trocadas. A robustez é uma propriedade de um algoritmo de classificação específico, e não uma propriedade de um algoritmo de comparação de strings (veja o parágrafo anterior);
As regras de classificação podem mudar ao longo do tempo à medida que as tradições culturais se refinam/mudam.

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

Para satisfazer todos esses requisitos, é proposto um algoritmo de classificação de tabelas multinível (na verdade, quatro níveis).

Anteriormente, os caracteres da string eram reduzidos à forma canônica e agrupados em unidades de comparação. A cada unidade de comparação são atribuídos vários pesos correspondentes a vários níveis de comparação. Os pesos das unidades de comparação são elementos de conjuntos ordenados (neste caso, inteiros) que podem ser comparados para mais ou para menos. Significado especial IGNORADO (0x0) significa que no nível de comparação correspondente esta unidade não está envolvida na comparação. A comparação de strings pode ser repetida diversas vezes, utilizando os pesos dos níveis correspondentes. Em cada nível, os pesos das unidades de comparação de duas linhas são comparados sequencialmente entre si.

Em diferentes implementações do algoritmo para diferentes tradições nacionais, os valores dos coeficientes podem diferir, mas o padrão Unicode inclui uma tabela básica de pesos - "Tabela de elementos de agrupamento Unicode padrão" (DUCETA). Gostaria de observar que definir a variável LC_COLLATE é na verdade uma indicação da seleção da tabela de pesos na função de comparação de strings.

Coeficientes de ponderação DUCETA organizado da seguinte forma:

no primeiro nível, todas as letras são reduzidas ao mesmo caso, os diacríticos são descartados, os sinais de pontuação (não todos) são ignorados;
no segundo nível, apenas os diacríticos são considerados;
no terceiro nível, apenas o caso é levado em consideração;
no quarto nível, apenas os sinais de pontuação são considerados.

A comparação ocorre em várias etapas: primeiro, são comparados os coeficientes do primeiro nível; se os pesos coincidirem, é realizada uma comparação repetida com os pesos do segundo nível; depois talvez um terceiro e um quarto.

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

Este algoritmo (com vários detalhes técnicos adicionais) deu o nome ao relatório nº 10 - "Algoritmo de agrupamento Unicode" (ACU).

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

Para testar implementações ACU há um especial teste, usando arquivo de pesos, implementando DUCETA. Você pode encontrar todo tipo de coisas engraçadas no arquivo de escalas. Por exemplo, existe a ordem do mahjong e do dominó europeu, bem como a ordem dos naipes num baralho de cartas (símbolo 1F000 e mais). Os naipes das cartas são colocados de acordo com as regras do bridge - PCBT, e as cartas do naipe estão na sequência T, 2,3, XNUMX... K.

Verificando manualmente se as linhas estão classificadas corretamente de acordo com DUCETA seria muito entediante, mas, felizmente para nós, existe uma implementação exemplar da biblioteca para trabalhar com Unicode - "Componentes Internacionais para Unicode"(UTI).

No site desta biblioteca, desenvolvida em IBM, existem páginas de demonstração, incluindo página de algoritmo de comparação de strings. Entramos em nossas linhas de teste com configurações padrão e, vejam só, obtemos uma classificação russa perfeita.

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

A propósito, o site UTI Você pode encontrar esclarecimentos sobre o algoritmo de comparação ao processar sinais de pontuação. Em exemplos Perguntas frequentes sobre agrupamento apóstrofo e hífen são ignorados.

Unicode nos ajudou, mas procure motivos para comportamento estranho tipo в Linux terá que ir para outro lugar.

Classificando na glibc

Visualização rápida dos códigos-fonte dos utilitários tipo de Utilitários principais do GNU mostrou que no próprio utilitário a localização se resume a imprimir o valor atual da variável LC_COLLATE ao executar no modo de depuração:

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

As comparações de strings são realizadas usando a função padrão passeio, o que significa que tudo de interessante está na biblioteca glibc.

На wiki projeto glibc dedicado à comparação de strings um parágrafo. A partir deste parágrafo pode-se entender que em glibc a classificação é baseada em um algoritmo já conhecido por nós ACU (O algoritmo de agrupamento Unicode) e/ou em um padrão próximo a ele ISO 14651 (Ordenação e comparação internacional de strings). Em relação à norma mais recente, deve-se destacar que no site padrões.iso.org ISO 14651 declarado oficialmente disponível publicamente, mas o link correspondente leva a uma página inexistente. O Google devolve várias páginas com links para sites oficiais que oferecem a compra de uma cópia eletrónica da norma por cem euros, mas na terceira ou quarta página de resultados de pesquisa também existem links diretos para PDF. Em geral, o padrão praticamente não difere de ACU, mas é mais enfadonho de ler porque não contém exemplos claros de características nacionais de classificação de strings.

As informações mais interessantes sobre wiki havia um link para rastreador de bugs com uma discussão sobre a implementação da comparação de strings em glibc. Da discussão pode-se aprender que glibc usado para comparar strings ISOmesa pessoal A tabela de modelos comuns (CTT), cujo endereço pode ser encontrado no aplicativo A padrão ISO 14651. Entre 2000 e 2015 esta tabela em glibc não tinha mantenedor e era bem diferente (pelo menos externamente) da versão atual do padrão. De 2015 a 2018 ocorreu a adaptação para a nova versão da mesa, e agora você tem a chance de conhecer na vida real uma nova versão da mesa (8 CentOS), e velho (7 CentOS).

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

ISO 14651 / 14652

Código fonte da tabela que nos interessa CTT na maioria das distribuições Linux está no catálogo /usr/share/i18n/locales/. A tabela em si está no arquivo iso14651_t1_common. Então esta é a diretiva de arquivo copiar iso14651_t1_common incluído no arquivo iso14651_t1, que, por sua vez, está incluído nos arquivos nacionais, incluindo en_US и ru_RU. Na maioria das distribuições Linux Todos os arquivos fonte estão incluídos na instalação básica, mas se não estiverem presentes, você terá que instalar um pacote adicional da distribuição.

Estrutura de arquivo iso14651_t1 pode parecer terrivelmente prolixo, com regras não óbvias para a construção de nomes, mas se você observar, tudo é bastante simples. A estrutura está descrita na norma ISO 14652, cuja cópia pode ser baixada do site open-std.org. Outra descrição do formato do arquivo pode ser lida em especificações POSIX de Grupo aberto. Como alternativa à leitura do padrão, você pode estudar o código fonte da função agrupar_leitura в glibc/locale/programas/ld-collate.c.

A estrutura do arquivo é semelhante a esta:

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

escape_char /
comment_char %

O arquivo conterá tokens no formato ou (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 angulares (incluindo , e similares) são consideradas constantes de string simples que têm pouco significado fora do contexto.

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

Primeiro, os nomes são especificados para os pesos na tabela de comparação e os nomes para as combinações de símbolos. De modo geral, os dois tipos de nomes pertencem a duas entidades diferentes, mas no arquivo real eles estão misturados. Os nomes dos pesos são especificados pela palavra-chave símbolo de agrupamento (caractere de comparação) porque na comparação, os caracteres Unicode que possuem os mesmos pesos serão considerados caracteres equivalentes.

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

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 agrupamento registra uma string OSMANIA na tabela de nomes de escalas
símbolo de agrupamento .. registra uma sequência de nomes que consiste em um prefixo S e sufixo numérico hexadecimal de 1D000 para 1D35F.
Ffff в símbolo de agrupamento parece um grande número inteiro sem sinal em hexadecimal, mas é apenas um nome que pode parecer
nome significa ponto de código na codificação UCS-4
elemento de agrupamento de "" registra um novo nome para um par de pontos Unicode.

Uma vez definidos os nomes dos pesos, os pesos reais são especificados. Como apenas relações de maior que menor são importantes na comparação, os pesos são determinados por uma simples sequência de nomes de listagem. Os pesos “mais leves” são listados primeiro, depois os “mais pesados”. Deixe-me lembrá-lo de que cada caractere Unicode recebe quatro pesos diferentes. Aqui eles são combinados em uma única sequência ordenada. Em teoria, qualquer nome simbólico poderia ser usado em qualquer um dos quatro níveis, mas os comentários indicam que os desenvolvedores separam mentalmente os nomes em níveis.

% 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

Finalmente, a tabela de peso real.

A seção de pesos está entre linhas de palavras-chave pedido_início и fim_pedido. Opções extras pedido_início determine em qual direção as linhas são varridas em cada nível de comparação. A configuração padrão é para a frente. 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 caractere pode ser representado pelo próprio caractere, um ponto de código ou um nome simbólico definido anteriormente. Os pesos também podem ser atribuídos a nomes simbólicos, pontos de código ou aos próprios símbolos. Se forem usados pontos de código ou caracteres, seu peso será igual ao valor numérico do ponto de código (posição na tabela Unicode). Caracteres não especificados explicitamente (pelo que entendi) são considerados atribuídos à tabela com um peso primário que corresponde à posição na tabela Unicode. Valor de peso especial IGNORAR significa que o símbolo é ignorado no nível apropriado de comparação.

Para demonstrar a estrutura das escalas, escolhi três fragmentos bastante óbvios:

caracteres 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 diacríticos e, portanto, é classificado principalmente pelo primeiro e terceiro níveis.

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

Agora você pode voltar a classificar os exemplos do início do artigo. A emboscada está nesta parte da tabela de pesos:

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

Pode-se observar que nesta tabela os sinais de pontuação da tabela ASCII (incluindo espaço) é quase sempre ignorado ao comparar strings. As únicas exceções são as linhas que correspondem em tudo, exceto nos sinais de pontuação encontrados nas posições correspondentes. As linhas do meu exemplo (após classificação) para o algoritmo de comparação são assim:

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

Considerando que na tabela de escalas, as letras maiúsculas em russo vêm depois das letras minúsculas (no terceiro nível mais pesado que ), a classificação parece absolutamente correta.

Ao definir uma variável LC_COLLATE=C uma tabela especial é carregada que especifica uma comparação 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'
};

Como em Unicode o ponto de código Ё vem antes de A, as strings são classificadas de acordo.

Tabelas de texto e binárias

Obviamente, a comparação de strings é uma operação extremamente comum, e a análise de tabelas CTT um procedimento bastante caro. Para otimizar o acesso à tabela, ela é compilada em formato binário com o comando definição local.

Equipe definição local aceita como parâmetros um arquivo com uma tabela de características nacionais (opção -i), em que todos os caracteres são representados por pontos Unicode, e um arquivo de correspondência entre pontos Unicode e caracteres de uma codificação específica (opção -f). Como resultado do trabalho, são criados arquivos binários para o local com o nome especificado no último parâmetro.

glibc suporta dois formatos de arquivo binário: "tradicional" e "moderno".

O formato tradicional significa que o nome do locale é o nome do subdiretório em /usr/lib/locale/. Este subdiretório armazena arquivos binários LC_COLLATE, LC_CTYPE, LC_TIME e assim por diante. Arquivo LC_IDENTIFICAÇÃO contém o nome formal do código do idioma (que pode ser diferente do nome do diretório) e comentários.

O formato moderno envolve armazenar todas as localidades em um único arquivo / usr / lib / locale / locale-archive, que é mapeado para a memória virtual de todos os processos usando glibc. O nome da localidade no formato moderno está sujeito a alguma canonização - apenas números e letras reduzidos a minúsculas permanecem nos nomes codificados. Então ru_RU.KOI8-R, será salvo como ru_RU.koi8r.

Os arquivos de entrada são pesquisados no diretório atual, bem como nos diretórios /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ para arquivos CTT e codificação de arquivos, respectivamente.

Por exemplo, o comando

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

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

Se você definir a variável LANG = en_US.UTF-8 que glibc procurará binários de localidade 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 um código de idioma ocorrer nos formatos tradicional e moderno, será dada prioridade ao formato moderno.

Você pode visualizar a lista de localidades compiladas com o comando localidade -a.

Preparando sua tabela de comparação

Agora, munido do conhecimento, você pode criar sua própria tabela de comparação de strings ideal. Esta tabela deve comparar corretamente as letras russas, incluindo a letra Ё, e ao mesmo tempo levar em consideração os sinais de pontuação de acordo com a tabela ASCII.

O processo de preparação de sua própria tabela de classificação consiste em duas etapas: editar a tabela de pesos e compilá-la em formato binário com o comando definição local.

Para que a tabela comparativa seja ajustada com custos mínimos de edição, no formato ISO 14652 São fornecidas seções para ajustar os pesos de uma tabela existente. A seção começa com uma palavra-chave reordenar depois e indicando a posição após a qual a substituição é realizada. A seção termina com a linha fim do pedido. Se for necessário corrigir várias seções da tabela, será criada uma seção para cada seção.

Copiei novas versões dos arquivos iso14651_t1_common и ru_RU do repositório glibc para meu diretório pessoal ~/.local/share/i18n/locales/ e editei ligeiramente a seção LC_COLLATE в ru_RU. Novas versões de arquivos são totalmente compatíveis com minha versão glibc. Caso queira utilizar versões mais antigas de arquivos, será necessário alterar os nomes simbólicos e o local onde começa a substituição na tabela.

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

Na verdade, seria necessário alterar os campos em LC_IDENTIFICAÇÃO para que eles apontem para o local ru_MY, mas no meu exemplo isso não foi necessário, pois excluí o arquivo da busca por localidades arquivo local.

Que definição local trabalhei com arquivos da minha pasta através de uma variável I18NPATH Você pode adicionar um diretório adicional para procurar arquivos de entrada, e o diretório para salvar arquivos binários pode ser especificado como um caminho com barras:

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

POSIX assume que em GRANDE você pode escrever caminhos absolutos para diretórios com arquivos de localidade, começando com uma barra, mas glibc в Linux todos os caminhos são contados a partir do diretório base, que pode ser substituído por uma variável LOCALPATH. Depois da instalação LOCPATH=~/.local/lib/locale/ todos os arquivos relacionados à localização serão pesquisados apenas na minha pasta. Arquivo de localidades com a variável definida LOCALPATH ignorado.

Aqui está o teste decisivo:

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

Viva! Conseguimos!

Alguns erros

Já respondi às perguntas sobre classificação de strings feitas no início, mas ainda há algumas perguntas sobre erros - visíveis e invisíveis.

Voltemos ao problema original.

E o programa tipo e programa juntar use as mesmas funções de comparação de strings de glibc. Como isso aconteceu juntar deu um erro de classificação nas linhas classificadas pelo comando tipo no local pt_US.UTF-8? A resposta é simples: tipo compara a string inteira e juntar compara apenas a chave, que por padrão é o início da string até o primeiro caractere de espaço em branco. No meu exemplo, isso resultou em uma mensagem de erro porque a classificação das primeiras palavras nas linhas não correspondia à classificação das linhas completas.

Localidade "C" garante que nas strings ordenadas as substrings iniciais até o primeiro espaço também serão ordenadas, mas isso apenas mascara o erro. É possível selecionar dados (pessoas com os mesmos sobrenomes, mas nomes diferentes) que, sem a mensagem de erro, dariam um resultado incorreto de mesclagem de arquivos. Se quisermos juntar linhas de arquivo mescladas por nome completo, a maneira correta seria especificar explicitamente o separador de campo e classificar pelo campo-chave, e não pela linha inteira. Neste caso, a mesclagem prosseguirá 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

Exemplo executado com sucesso na codificação CP1251 contém outro erro. O fato é que em todas as distribuições que conheço Linux pacotes estão faltando localidade compilada ru_RU.CP1251. Se o código do idioma compilado não for encontrado, então tipo usa silenciosamente uma comparação byte por byte, que é o que observamos.

A propósito, há outra pequena falha relacionada à inacessibilidade dos locais compilados. Equipe LOCPATH=/tmp localidade -a fornecerá uma lista de todos os locais em arquivo local, mas com a variável definida LOCALPATH para todos os programas (incluindo os mais local) essas localidades não estarão disponí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 acostumado a pensar que strings são um conjunto de bytes, então sua escolha LC_COLLATE=C.

Se você é um linguista ou compilador de dicionário, é melhor compilar em sua localidade.

Se você é um usuário simples, basta se acostumar com o fato de que o comando ls -a gera arquivos começando com um ponto misturado com arquivos começando com uma letra, e Comandante da meia-noite, que usa suas funções internas para classificar nomes, coloca os arquivos começando com um ponto no início da lista.