Сгенерировать порядок сортировки списка отдельных символов

Eso tiene varios aspectos. Necesitamos enumerar todos los caracteres en el conjunto de caracteres de la configuración regional, seleccionar los gráficos (como los de 33 a 126 ASCII )y ordenarlos.

Y también está la cuestión de si tiene sentido hablar del orden de clasificación de los caracteres o si alguna vez se define. Voy a empezar con ese último punto.

El algoritmo de colación POSIX

Si estamos hablando del algoritmo de intercalación C/POSIX implementado por strcoll()y utilizado por sorto ls, o shell globs o awk/ expr's <, >operador de comparación de cadenas y, en general, la mayoría de las herramientas que ordenan el texto según la ubicación del usuario en los sistemas POSIX, tenga en cuenta que son para comparar cadenas .

Mientras que en una configuración regional en _US.UTF -8 en un sistema GNU, la cadena éque consta de un único carácter éordena después de la cadena que consta de un solo carácter e, Stéphaneordena antes deStephanie. En una configuración regional cs _CZ.UTF -8, cclasifica entre by d, pero chclasifica entre hy i.

El algoritmo de colación considera la cadena completa, no los caracteres individualmente. Por lo tanto, conocer el orden de los caracteres cuando se comparan individualmente no necesariamente nos dice cómo se compararán las cadenas que contienen esos caracteres.

Ese algoritmo está diseñado para comparar cadenas como lo hacen muchos idiomas en el mundo real, como en diccionarios y guías telefónicas. Es un poco demasiado simple para cubrir todas las sutilezas de la clasificación en diferentes culturas (, consulte ICU , que implementan diferentes algoritmos para obtener más información ), pero es lo suficientemente bueno para la mayoría de los casos.

En ese algoritmo, cotejando elementos ,que incluyen caracteres pero también combinaciones de caracteres como los grafemas de múltiples partes -del alfabeto coreano o el checo cho en algunos sistemas el éexpresado como eseguido de un acento agudo combinado (U+ 0301 )se asignan varios pesos .

y cadenas completas se comparan usando cada peso por turno, desde el peso principal hasta el último peso.

Por ejemplo, en ese en_US.UTF-8entorno local GNU, E, é, e, Étodos tienen el mismo peso principal. Stéphaney Stephaniese descomponen en

<S><t><é><p><h><a><n> <e>
<S><t><e><p><h><a><n> <i><e>

elementos de clasificación (aquí, uno por carácter ).

Hasta n, los elementos de clasificación de las dos cadenas tienen el mismo peso principal, pero el peso principal de ies mayor que el de e, por lo que Stephanieordena después de Stéphaney el el peso secundario ni siquiera tiene que ser considerado.

Ahora, para Stephanefrente a Stéphane, cuando se comparan los pesos primarios, se ordenan de la misma manera, por lo que se debe considerar el peso secundario. Si observa /usr/share/i18n/locales/iso14651_t1_commonen un sistema GNU como se usa, ya que -es por la configuración regional en _US.UTF -8, verá:

<BAS> # 15
[...]
<ACA> # 18
[...]
<U0065> <e>;<BAS>;<MIN>;IGNORE # 259 e
<U00E9> <e>;<ACA>;<MIN>;IGNORE # 260 é

Para los caracteres del alfabeto latino, el peso secundario se usa para comparar signos diacríticos. Y el carácter base(BAS)se ordena antes que el de acento agudo(ACA). Entonces Stéphaneordena después de Stephane. Para comparar STÉPHANEcon Stéphane, tendríamos que subir al tercer peso donde las mayúsculas se ordenan después de las minúsculas en inglés (contrario al estonio, por ejemplo ).

Y están los caracteres no -alfanuméricos como el espacio o la puntuación cuyo peso principal es IGNOREy no se consideran en el primer pase de comparación(de factoclasifica entre defacey degree, eso no el espacio medio se clasifica entre fyg).

Para $'STE\u0301HANE'frente a Stéphane,algunos sistemas como Solaris tratarán E\u0301como un elemento de clasificación con el mismo peso excepto el último como el carácterÉ(U+00C9 ), mientras que otros tratarán \u0301como puntuación, dando resultados no tan buenos (así $'STE\u0301HANE'antesStephane).

No es un pedido total

En los sistemas GNU el orden de clasificación de U+0301 ni siquiera está definido, y hay miles de caracteres más en ese caso . Me gusta tomar el ejemplo de los números de dígitos redondeados (U+2460..U+2473 )ya que claramente deberían tener un orden de clasificación pero no¹:

$ touch ① ② ③ ④ ⑤
$ ls
④  ③  ⑤  ②  ①
$ ls | sort -u
④

También hay caracteres que en realidad se definen con el mismo peso exacto que otros (como Ǝ, Ə, Ɛque se ordenan de la misma manera aquí ).

Por esa razón, en realidad no es posible ordenar caracteres arbitrarios en algunas configuraciones regionales, a menos que, como hacen algunas implementaciones sort(y , sea un requisito en la próxima versión principal de la especificación POSIX ), recurre a una comparación similar a memcmp()para caracteres que tienen el mismo tipo.

Listado de todos los caracteres gráficos en el conjunto de caracteres de la localidad

Las diferentes localidades pueden usar diferentes juegos de caracteres.

Hay tres categorías principales de conjuntos de caracteres, conjuntos de caracteres de un solo byte como ASCII o iso -8859 -x donde cada byte corresponde a un carácter (aunque algunos pueden no estar definidos ), multi -conjuntos de caracteres de bytes (y codificación )como UTF -8, GB18030, BIG5 o EUCJP donde los caracteres se codifican en un número variable de bytes, y con estado, donde un byte o secuencia de bytes puede representar diferentes caracteres dependiendo sobre si un código de cambio de estado -se ha emitido antes.

Esa última categoría rara vez se usa en locales en estos días y generalmente es inmanejable, por lo que podemos ignorarla por ahora.

Se garantiza que la configuración regional C en sí misma tiene un conjunto de caracteres de un solo byte -. No tiene que ser ASCII, aunque generalmente está en sistemas donde no está basado en EBCDIC -.

Tenga en cuenta que algunas secuencias de comandos como la latina que se usa en inglés se escriben de izquierda a derecha, mientras que otras se escriben de derecha a izquierda, por lo que tener caracteres de esas diferentes secuencias de comandos (compatibles con algunos juegos de caracteres )en la misma línea es no necesariamente una buena idea.

Lo mismo ocurre con la combinación de caracteres que terminarían combinándose en caracteres aleatorios y juntos.

También tenga en cuenta que algunos juegos de caracteres como Unicode todavía están evolucionando. Si bien ahora está fijo en rangos de puntos de código 0..0xD7FF, 0xE000..0x10FFFF, la mayoría de ellos aún no están asignados y cada nueva versión de Unicode asigna nuevos, y los proveedores de sistemas intentan mantenerse al día.

Los caracteres clasificados como graphse enumeran en el Informe técnico ISO/IEC 30112 (2014 )que da seguimiento a ISO/IEC TR 14652 (2002 ). Los locales de GNU parecen seguir eso, algunos otros (como FreeBSD/Solaris )no, pero no los culpo ya que no parece tener mucho sentido para mí. Por ejemplo, excluye la mayoría de los caracteres de espaciado, pero no U+00A0 (no -espacio de separación ), U+2007 (espacio de cifras )ni U+200B (espacio de ancho cero ). Incluye caracteres que consideraría como caracteres de control , como U+200C..U+200F, U+202D, U+202E...² este último, el derecho -a -la anulación izquierda es fundamental para esta pregunta y respuesta, ya que invierte el orden de los caracteres izquierdos -a -derechos:

$ printf '%b\n' '\u202E' a b c | sort | paste -sd '\0' -
‮abc

(algunos navegadores mostrarán cbasi lo admiten, otrosabc).

También incluye la mayoría decaracteres de etiqueta y también los miles de caracteres de uso privado , que es poco probable que se asignen,y mucho menos dibujable en su sistema.

Para conjuntos de caracteres de un solo byte (en sistemas GNU, aquellos para los que locale ctype-mb-cur-maxdevuelve 1 ), la lista de caracteres gráficos debería ser simplemente una cuestión de recorrer todos los valores de 255 bytes (omitiendo el primero, NUL en cada conjunto de caracteres que no es gráfico y causaría problemas )y compararlos con [[:graph:]].

Uno podría hacer eso con awkpor ejemplo:

awk '
  BEGIN{
    for (i = 1; i < 256; i++) {
      c = sprintf("%c", i)
      if (c ~ /[[:graph:]]/) print c
    }
  }' | sort | paste -sd '\0' -

En una configuración regional el_GR.iso88597, griego usando el juego de caracteres iso8859 -de 7 bytes individuales, eso daría:

`^¨~<=>¦°_­-,;:!?/.·'ʽʼ"«»()[]{}§©@$£¤¥*\&#%+±ª―΄΅0½12²3³456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZΑαΆάΒβΓγΔδΕεΈέΖζΗηΉήΘθΙιΊίΪϊΐΚκΛλΜμΝνΞξΟοΌόΠπΡρΣσςΤτΥυΎύΫϋΰΦφΧχΨψΩωΏώ 

(con el espacio final no -que se rompe -clasificado como "gráfico" por las configuraciones regionales de GNU ).

Ese enfoque no se puede usar para caracteres de múltiples -bytes.

Si su iconvadmite una codificación de juego de caracteres UCS-4BEo UTF32BE, puede generar todos los puntos de código Unicode como números big endian de 32 bits y convertirlos al juego de caracteres local:

perl -e 'print pack("L>*", $_, 10) for 1..0xd7ff, 0xe000..0x10ffff' |
  iconv -cf UCS-4BE |
  grep '[[:graph:]]' |
  sort

O si soporta un UTF -8 uno:

perl -C -M-warnings=nonchar -le 'print chr$_ for 1..0xd7ff, 0xe000..0x10ffff' |
  iconv -cf UTF-8 |
  grep '[[:graph:]]' |
  sort

(dejado en un carácter por línea para evitar los problemas mencionados anteriormente y también para evitar generar una línea demasiado larga ).

Eso funciona en el hecho de que Unicode (y, por lo tanto, sus codificaciones )están destinados a incluir caracteres de todos los demás conjuntos de caracteres posibles, por lo que siempre habrá un punto de código Unicode para cada carácter en cualquier conjunto de caracteres. Los sistemas modernos en realidad definen sus conjuntos de caracteres en relación con Unicode y su wchar_tgeneralmente corresponde a puntos de código Unicode.

Ahora, como se discutió anteriormente, ordenar recurre a una comparación basada enmemcmp()-para caracteres que ordenan lo mismo con strcoll(). Para juegos de caracteres de un solo byte -, eso será una clasificación en el punto de código en esos juegos de caracteres; para UTF -8, se ordenará en el punto de código Unicode como UTF -8 tiene esa propiedad específica. Para otras codificaciones de Unicode como el chino GB18030 u otros juegos de caracteres multibyte, eso puede parecer más o menos aleatorio.

En cualquier caso, eso significará que para dos configuraciones regionales con el mismo orden de clasificación, la salida de sortserá diferente si esas configuraciones regionales usan juegos de caracteres diferentes.

Por ejemplo, si volvemos a nuestros ①②③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳ números redondeados. Unicode los especifica en ese orden (punto de código 0x2460 a 0x2473 ). En las configuraciones regionales de GNU, su orden no está definido (① no es ni antes ni después de ② ). Ordenar colocará ② después de ① en una configuración regional usando UTF -8 porque el orden de UTF -8 sigue el orden de punto de código Unicode. Pero en una configuración regional como zh _CN.gb18030 que usa GB18030, otra codificación de Unicode de China, el orden se convierte en ⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳①②③④⑤⑥⑦⑧⑨⑩, según cómo se codifican esos caracteres a nivel de byte (o (t para este error que los hace ordenar como ①②③④⑤⑥⑦⑧⑨⑩⑮⑯⑰⑱⑲⑳⑪⑫⑬⑭ en lugar de ).

Si desea ordenar los caracteres de una cadena en función de su orden de clasificación, conzsh:

printf "%s\n" ${(j::)${(s::o)string}}

Tenga en cuenta que zsh puede tener caracteres NUL en sus variables, pero strcoll()no funciona con ellos. zshintenta solucionar eso, pero no es perfecto .

El resultado no sería -determinista si las cadenas contuvieran diferentes caracteres con el mismo orden de clasificación.

^{¹ Edición de 2019 el orden de ① ② ③ ④ ⑤ desde entonces se ha corregido en las versiones más nuevas de GNU libc, pero a partir de la 2.30, más del 95 % de los caracteres aún no tienen un orden definido, puede reemplazar ① ② ③ ④ ⑤ con, por ejemplo. Con suerte, las configuraciones regionales de GNU finalmente se solucionarán por completo (, tendrán que hacerlo si quieren cumplir con la próxima revisión del estándar )y el problema se limitará a las configuraciones regionales definidas por el usuario -}

^{² Creo que la razón es que el no -romper el espacio, figurar el espacio,el espacio de ancho cero, etc., no se incluyen en la categoría spacedebido a que no deben usarse como delimitadores(ISO30112 los define como caracteres para ser clasificados como espacios en blanco -caracteres, para encontrar límites sintácticos ), y graphse define como los caracteres imprimibles sin -espaciados (los caracteres que están en la categoría printy no en la categoría space, aunque el texto de ISO30112 lo define como caracteres para ser clasificados como caracteres imprimibles, no incluido el carácter ). Entonces, en efecto, son caracteres gráficos y caracteres imprimibles no gráficos -que no se usan como límites sintácticos.}

В bash и zsh легко сгенерировать диапазон чисел:

$ printf '\\x%x' {53..63}
\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f

А также легко преобразовать числа UNICODE в символы:

$ printf '%b' "$(printf '\\U%x' {53..63})"
56789:;<=>?

Это подарок от bash coder, что диапазон для \UXXXXXXXXне имеет ограничений, он работает от кода 0 до 10FFFF (1114111 в десятичном виде ).

Итак, мы можем сгенерировать все первые 127 символов с помощью этого простого кода:

$ printf '%b' "$(printf '\\U%x' {0..127})" | hd
00000000  00 01 02 03 04 05 06 07  08 09 0a 0b 0c 0d 0e 0f  |................|
00000010  10 11 12 13 14 15 16 17  18 19 1a 1b 1c 1d 1e 1f  |................|
00000020  20 21 22 23 24 25 26 27  28 29 2a 2b 2c 2d 2e 2f  | !"#$%&'()*+,-./|
00000030  30 31 32 33 34 35 36 37  38 39 3a 3b 3c 3d 3e 3f  |0123456789:;<=>?|
00000040  40 41 42 43 44 45 46 47  48 49 4a 4b 4c 4d 4e 4f  |@ABCDEFGHIJKLMNO|
00000050  50 51 52 53 54 55 56 57  58 59 5a 5b 5c 5d 5e 5f  |PQRSTUVWXYZ[\]^_|
00000060  60 61 62 63 64 65 66 67  68 69 6a 6b 6c 6d 6e 6f  |`abcdefghijklmno|
00000070  70 71 72 73 74 75 76 77  78 79 7a 7b 7c 7d 7e 7f  |pqrstuvwxyz{|}~.|
00000080

Добавляя символ NUL (0x00 )для каждого символа и используя сортировку -z, мы можем видеть порядок сортировки:

$  printf '%b' "$(printf '\\U%x\\0' {0..127})" | sort -z
`^~<=>| _-,;:!?/.'"()[]{}@$*\&#%+


▒▒123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

И, удалив NUL, увидеть числовой порядок:

$ printf '%b' "$(printf '\\U%x\\0' {0..127})" | sort -z | tr -d '\0' | hd
00000000  60 5e 7e 3c 3d 3e 7c 20  5f 2d 2c 3b 3a 21 3f 2f  |`^~<=>| _-,;:!?/|
00000010  2e 27 22 28 29 5b 5d 7b  7d 40 24 2a 5c 26 23 25  |.'"()[]{}@$*\&#%|
00000020  2b 01 02 03 04 05 06 07  08 09 0a 0b 0c 0d 0e 0f  |+...............|
00000030  10 11 12 13 14 15 16 17  18 19 1a 1b 1c 1d 1e 1f  |................|
00000040  7f 30 31 32 33 34 35 36  37 38 39 61 41 62 42 63  |.0123456789aAbBc|
00000050  43 64 44 65 45 66 46 67  47 68 48 69 49 6a 4a 6b  |CdDeEfFgGhHiIjJk|
00000060  4b 6c 4c 6d 4d 6e 4e 6f  4f 70 50 71 51 72 52 73  |KlLmMnNoOpPqQrRs|
00000070  53 74 54 75 55 76 56 77  57 78 58 79 59 7a 5a     |StTuUvVwWxXyYzZ|
0000007f

Обратите внимание на разницу в порядке локали C:

$ printf '%b' "$(printf '\\U%x\\0' {0..127})" | LC_COLLATE=C sort -z | tr -d '\0' | hd
00000000  01 02 03 04 05 06 07 08  09 0a 0b 0c 0d 0e 0f 10  |................|
00000010  11 12 13 14 15 16 17 18  19 1a 1b 1c 1d 1e 1f 20  |............... |
00000020  21 22 23 24 25 26 27 28  29 2a 2b 2c 2d 2e 2f 30  |!"#$%&'()*+,-./0|
00000030  31 32 33 34 35 36 37 38  39 3a 3b 3c 3d 3e 3f 40  |123456789:;<=>?@|
00000040  41 42 43 44 45 46 47 48  49 4a 4b 4c 4d 4e 4f 50  |ABCDEFGHIJKLMNOP|
00000050  51 52 53 54 55 56 57 58  59 5a 5b 5c 5d 5e 5f 60  |QRSTUVWXYZ[\]^_`|
00000060  61 62 63 64 65 66 67 68  69 6a 6b 6c 6d 6e 6f 70  |abcdefghijklmnop|
00000070  71 72 73 74 75 76 77 78  79 7a 7b 7c 7d 7e 7f     |qrstuvwxyz{|}~.|
0000007f

128 значений, которые байт может иметь за пределами диапазона ASCII, печатаются как utf8, выход (без сортировки по порядку сортировки):

$ printf '%b' "$(printf '\\U%x' {125..255})"
}~ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏ
ÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ

Тот же диапазон, отсортированный по порядку сортировки: (обратите внимание, что первый символ представляет собой острый ударение и чередование гласных нижнего и верхнего регистра):

$ printf '%b' "$(printf '\\U%x\\0' {125..255})" | sort -z
´¨~÷׬¦°µ¯­¡¿·¸«»}§¶©®¤¢£¥±¼½¾¹²³áÁàÀâÂåÅäÄãêæÆ
çÇðÐéÉèÈêÊëËíÍìÌîÎïÏñÑóÓòÒôÔöÖõÕøغßúÚùÙûÛüÜýÝÿþÞ

И порядок сортировки становится намного сложнее, когда диапазон расширяется:

$ printf '%b' "$(printf '\\U%x\\0' {0..500})" | sort -z | tr -d '\0'
´`^¨~÷×<=>¬|¦°µ _¯­-,;:!¡?¿/.·¸'"«»()[]{}§¶©®@¤¢$£¥*\&#%+
±ƀƂƃƄƅƉƋƌƍƑƒƔƖƗƚƛƜƝƞƤƥƦƧƨƩƪƫƬƭƮƱƲƸƹƺƻƼƽƾǀǁǂǃ

▒▒0¼½¾1¹2²3³456789aAáÁàÀăĂâÂǎǍåÅäǟÄǞãÃǡǠąĄāĀªæǣÆǢ
bBƁcCćĆĉĈčČċĊçÇƈƇdDďĎđĐƊðÐdzDzDZdžDžDŽeEéÉèÈĕĔêÊěĚëËėĖęĘēĒǝƎƏƐ
fFgGǴğĞĝĜǧǦġĠǥǤģĢƓƣƢhHĥĤħĦƕiIíÍìÌĭĬîÎǐǏïÏĩĨįĮīĪıİijIJ
jJĵĴǰkKǩǨķĶƙƘlLĺĹľĽŀĿłŁļĻljLjLJmMnNńŃňŇñÑņŅʼnŋŊnjNjNJ
oOóÓòÒŏŎôÔǒǑöÖƟőŐõÕøØǫǭǪǬōŌơƠºƆœŒpPqQĸrRŕŔřŘŗŖ
sSśŚŝŜšŠşŞſßtTťŤŧŦţŢuUúÚùÙŭŬûÛǔǓůŮüǘǜǚǖÜǗǛǙǕűŰũŨųŲūŪưƯ
vVwWŵŴƿxXyYýÝŷŶÿŸƴƳzZźŹžŽżŻƶƵþÞƷǯǮ

Сортировка такой большой группы символов в чистой локали C невозможна, так как printf генерирует символы как пары байтов в utf8, а sort (с простой локалью C )попытается отсортировать байты. Или printf завершится ошибкой с \U…для локали C. Что необходимо, так это эквивалентная локаль, которая допускает больше символов, чем 256, которые может содержать байт :

$ LC_ALL=C.UTF-8 printf "$(printf '\\U%x' {32..500})" | sort
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ 
[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶· 
¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñò 
óôõö÷øùúûüýþÿĀāĂ㥹ĆćĈĉĊċČčĎďĐđĒēĔĕĖėĘęĚěĜĝĞğĠġĢģĤĥĦħĨĩĪīĬĭ 
ĮįİıIJijĴĵĶķĸĹĺĻļĽľĿŀŁłŃńŅņŇňʼnŊŋŌōŎŏŐőŒœŔŕŖŗŘřŚśŜŝŞşŠšŢţŤťŦŧŨ
ũŪūŬŭŮůŰűŲųŴŵŶŷŸŹźŻżŽžſƀƁƂƃƄƅƆƇƈƉƊƋƌƍƎƏƐƑƒƓƔƕƖƗƘƙƚƛƜƝƞƟƠơƢƣ
ƤƥƦƧƨƩƪƫƬƭƮƯưƱƲƳƴƵƶƷƸƹƺƻƼƽƾƿǀǁǂǃDŽDždžLJLjljNJNjnjǍǎǏǐǑǒǓǔǕǖǗǘǙǚǛǜǝǞ
ǟǠǡǢǣǤǥǦǧǨǩǪǫǬǭǮǯǰDZDzdzǴ

Последовательность сортировки определяется файлами локали. Вот последовательность всех символов ASCII в локали en _US:

codes=$(for i in {32..126}; do echo "u$(printf '%04x' "$i")"; done)
grep_patterns=$(echo "$codes" | sed 's/^/^</; s/$/>/')
codes_locale=$(grep -oif - <<<"$grep_patterns" /usr/share/i18n/locales/iso14651_t1_common | tr -d '<>')

# "ASCII sequence"
for c in $codes; do echo -ne "\\$c"; done; echo
# "en_US sequence"
for c in $codes_locale; do echo -ne "\\$c"; done; echo

# OUTPUT:
#  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
#  !"#%&'()*+,-./:;<=>?@[\]^_`{|}~$0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Следует помнить, что порядок последовательности не совпадает с порядком сортировки. При сортировке применяются дополнительные правила.