Pengenalan

Semuanya bermula dengan skrip pendek yang sepatutnya menggabungkan maklumat alamat e-mel pekerja diperoleh daripada senarai pengguna senarai mel, dengan jawatan pekerja diperoleh daripada pangkalan data jabatan HR. Kedua-dua senarai telah dieksport ke fail teks Unicode UTF-8 dan disimpan dengan penghujung baris Unix.

Kandungan mail.txt

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

Kandungan buhg.txt

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

Untuk menggabungkan, fail telah diisih mengikut arahan Unix jenis dan diserahkan kepada input program Unix menyertai, yang gagal secara tidak dijangka dengan ralat:

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

Melihat hasil pengisihan dengan mata anda menunjukkan bahawa, secara umum, pengisihan adalah betul, tetapi dalam kes kebetulan nama keluarga lelaki dan perempuan, nama keluarga perempuan didahulukan sebelum nama keluarga lelaki:

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

Kelihatan seperti gangguan pengisihan dalam Unicode atau seperti manifestasi feminisme dalam algoritma pengisihan. Yang pertama, tentu saja, lebih masuk akal.

Mari kita menangguhkannya buat masa ini menyertai dan fokus pada jenis. Mari cuba selesaikan masalah menggunakan cucuk saintifik. Mula-mula, mari tukar tempat daripada en_us pada ru_RU. Untuk mengisih, sudah cukup untuk menetapkan pembolehubah persekitaran LC_COLLATE, tetapi kami tidak akan membuang masa untuk perkara-perkara kecil:

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

Tiada perubahan.

Mari cuba kod semula fail ke dalam pengekodan bait tunggal:

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

Sekali lagi tiada apa yang berubah.

Tiada apa yang boleh anda lakukan, anda perlu mencari penyelesaian di Internet. Tiada apa-apa secara langsung mengenai nama keluarga Rusia, tetapi terdapat soalan mengenai keanehan pengisihan lain. Sebagai contoh, berikut adalah masalah: jenis unix menganggap aksara '-' (sempang) sebagai tidak kelihatan. Ringkasnya, rentetan "a-b", "aa", "ac" diisih sebagai "aa", "a-b", "ac".

Jawapannya adalah standard di mana-mana: gunakan tempat pengaturcara "C" dan anda akan gembira. Mari kita cuba:

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

Sesuatu telah berubah. Ivanovs berbaris dalam susunan yang betul, walaupun Yolkina tergelincir entah ke mana. Mari kembali kepada masalah asal:

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

Ia berfungsi tanpa ralat, seperti yang dijanjikan oleh Internet. Dan ini walaupun Yolkina di baris pertama.

Masalahnya nampaknya telah diselesaikan, tetapi untuk berjaga-jaga, mari cuba pengekodan Rusia yang lain - Windows CP1251:

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

Hasil pengisihan, secara anehnya, akan bertepatan dengan tempat "C", dan keseluruhan contoh, dengan sewajarnya, berjalan tanpa ralat. Beberapa jenis mistik.

Saya tidak suka mistik dalam pengaturcaraan kerana ia biasanya menutup kesilapan. Kita perlu melihat dengan serius cara ia berfungsi. jenis dan apakah kesannya? LC_COLLATE .

Pada akhirnya saya akan cuba menjawab soalan:

mengapakah nama keluarga perempuan disusun secara tidak betul?
mengapa LANG=ru_RU.CP1251 ternyata setara LANG=C
Kenapa jenis и menyertai idea yang berbeza tentang susunan rentetan yang diisih
mengapa terdapat ralat dalam semua contoh saya?
akhirnya bagaimana untuk mengisih rentetan mengikut keinginan anda

Isih dalam Unicode

Perhentian pertama ialah laporan teknikal No. 10 bertajuk Algoritma pengumpulan Unicode talian unicode.org. Laporan itu mengandungi banyak butiran teknikal, jadi izinkan saya memberikan ringkasan ringkas tentang idea utama.

Pengumpulan — "membandingkan" rentetan ialah asas bagi mana-mana algoritma pengisihan. Algoritma itu sendiri mungkin berbeza ("gelembung", "bercantum", "cepat"), tetapi kesemuanya akan menggunakan perbandingan sepasang rentetan untuk menentukan susunan ia muncul.

Mengisih rentetan dalam bahasa semula jadi adalah masalah yang agak kompleks. Walaupun dalam pengekodan bait tunggal yang paling mudah, susunan huruf dalam abjad, walaupun dalam beberapa cara berbeza daripada abjad Latin Inggeris, tidak akan lagi bertepatan dengan susunan nilai berangka dengan mana huruf ini dikodkan. Jadi dalam abjad Jerman huruf itu Ö berdiri di antara О и P, dan dalam pengekodan CP850 dia mendapat antara ÿ и Ü.

Anda boleh cuba mengabstrak daripada pengekodan tertentu dan mempertimbangkan huruf "ideal" yang disusun dalam beberapa tertib, seperti yang dilakukan dalam Unicode. Pengekodan UTF8, UTF16 atau satu bait KOI8-R (jika subset terhad Unicode diperlukan) akan memberikan perwakilan angka huruf yang berbeza, tetapi merujuk kepada elemen yang sama pada jadual asas.

Ternyata walaupun kita membina jadual simbol dari awal, kita tidak akan dapat menetapkan susunan simbol universal kepadanya. Dalam abjad kebangsaan yang berbeza yang menggunakan huruf yang sama, susunan huruf ini mungkin berbeza. Contohnya, dalam bahasa Perancis Æ akan dianggap sebagai ligatur dan disusun sebagai rentetan AE. Dalam bahasa Norway Æ akan menjadi surat berasingan, yang terletak selepas Z. Dengan cara ini, sebagai tambahan kepada ligatur seperti Æ Terdapat huruf yang ditulis dengan beberapa simbol. Jadi dalam abjad Czech ada huruf Ch, yang berdiri di antara H и I.

Selain perbezaan dalam abjad, terdapat tradisi kebangsaan lain yang mempengaruhi penyisihan. Khususnya, persoalan timbul: dalam susunan apakah perkataan yang terdiri daripada huruf besar dan huruf kecil harus muncul dalam kamus? Pengisihan juga mungkin dipengaruhi oleh penggunaan tanda baca. Dalam bahasa Sepanyol, tanda soal terbalik digunakan pada permulaan ayat tanya (Adakah anda suka muzik?). Dalam kes ini, adalah jelas bahawa ayat tanya tidak boleh dikumpulkan ke dalam gugusan berasingan di luar abjad, tetapi bagaimana untuk mengisih baris dengan tanda baca yang lain?

Saya tidak akan memikirkan menyusun rentetan dalam bahasa yang sangat berbeza daripada bahasa Eropah. Ambil perhatian bahawa dalam bahasa dengan arah penulisan kanan ke kiri atau atas ke bawah, aksara dalam baris kemungkinan besar disimpan dalam susunan bacaan, malah sistem tulisan bukan abjad mempunyai cara tersendiri untuk menyusun baris aksara demi aksara. . Sebagai contoh, hieroglif boleh dipesan mengikut gaya (Kekunci aksara Cina) atau dengan sebutan. Sejujurnya, saya tidak tahu bagaimana emoji harus disusun, tetapi anda juga boleh membuat sesuatu untuk mereka.

Berdasarkan ciri yang disenaraikan di atas, keperluan asas untuk membandingkan rentetan berdasarkan jadual Unicode telah dirumuskan:

perbandingan rentetan tidak bergantung pada kedudukan aksara dalam jadual kod;
urutan aksara yang membentuk satu aksara dikurangkan kepada bentuk kanonik (A + bulatan atas adalah sama dengan Å);
Apabila membandingkan rentetan, watak dipertimbangkan dalam konteks rentetan dan, jika perlu, digabungkan dengan jirannya ke dalam satu unit perbandingan (Ch dalam bahasa Czech) atau dibahagikan kepada beberapa (Æ dalam bahasa Perancis);
semua ciri kebangsaan (abjad, huruf besar/huruf kecil, tanda baca, susunan jenis tulisan) mesti dikonfigurasikan sehingga tugasan manual pesanan (emoji);
perbandingan adalah penting bukan sahaja untuk mengisih, tetapi juga di banyak tempat lain, contohnya untuk menentukan julat baris (menggantikan {A... z} dalam menampar);
perbandingan harus dilakukan dengan agak cepat.

Di samping itu, pengarang laporan merumuskan sifat perbandingan yang tidak boleh bergantung pada pembangun algoritma:

algoritma perbandingan tidak sepatutnya memerlukan set aksara yang berasingan untuk setiap bahasa (bahasa Rusia dan Ukraine berkongsi kebanyakan aksara Cyrillic);
perbandingan tidak seharusnya bergantung pada susunan aksara dalam jadual Unicode;
berat rentetan tidak seharusnya menjadi atribut rentetan, kerana rentetan yang sama dalam konteks budaya yang berbeza boleh mempunyai pemberat yang berbeza;
pemberat baris boleh berubah apabila bergabung atau berpecah (daripada x < y ia tidak mengikuti itu xz < yz);
rentetan berbeza yang mempunyai berat yang sama dianggap sama dari sudut pandangan algoritma pengisihan. Memperkenalkan susunan tambahan rentetan sedemikian adalah mungkin, tetapi ia mungkin merendahkan prestasi;
Semasa pengisihan berulang, baris dengan pemberat yang sama mungkin ditukar. Keteguhan ialah sifat algoritma pengisihan tertentu, dan bukan sifat algoritma perbandingan rentetan (lihat perenggan sebelumnya);
Peraturan pengisihan mungkin berubah dari semasa ke semasa apabila tradisi budaya diperhalusi/berubah.

Ia juga ditetapkan bahawa algoritma perbandingan tidak mengetahui apa-apa tentang semantik rentetan yang sedang diproses. Oleh itu, rentetan yang hanya terdiri daripada digit tidak boleh dibandingkan sebagai nombor, dan dalam senarai nama Inggeris artikel (Beatles, The).

Untuk memenuhi semua keperluan yang ditentukan, algoritma pengisihan jadual berbilang peringkat (sebenarnya empat peringkat) dicadangkan.

Sebelum ini, aksara dalam rentetan dikurangkan kepada bentuk kanonik dan dikumpulkan ke dalam unit perbandingan. Setiap unit perbandingan diberikan beberapa pemberat sepadan dengan beberapa peringkat perbandingan. Berat unit perbandingan ialah unsur set tertib (dalam kes ini, integer) yang boleh dibandingkan lebih atau kurang. Makna istimewa DIABAIKAN (0x0) bermakna pada tahap perbandingan yang sepadan unit ini tidak terlibat dalam perbandingan. Perbandingan rentetan boleh diulang beberapa kali, menggunakan pemberat tahap yang sepadan. Pada setiap peringkat, berat unit perbandingan dua baris dibandingkan secara berurutan antara satu sama lain.

Dalam pelaksanaan algoritma yang berbeza untuk tradisi kebangsaan yang berbeza, nilai pekali mungkin berbeza, tetapi standard Unicode termasuk jadual berat asas - "Jadual Elemen Pengumpulan Unikod Lalai" (DUCET). Saya ingin ambil perhatian bahawa menetapkan pembolehubah LC_COLLATE sebenarnya merupakan petunjuk pemilihan jadual berat dalam fungsi perbandingan rentetan.

Pekali pemberat DUCET disusun seperti berikut:

pada peringkat pertama, semua huruf dikurangkan kepada kes yang sama, diakritik dibuang, tanda baca (bukan semua) diabaikan;
pada peringkat kedua, hanya diakritik diambil kira;
pada peringkat ketiga, hanya kes diambil kira;
pada tahap keempat, hanya tanda baca diambil kira.

Perbandingan berlaku dalam beberapa pas: pertama, pekali tahap pertama dibandingkan; jika pemberat bertepatan, maka perbandingan berulang dengan pemberat tahap kedua dijalankan; kemudian mungkin sepertiga dan keempat.

Perbandingan berakhir apabila baris mengandungi unit perbandingan yang sepadan dengan pemberat yang berbeza. Baris yang mempunyai berat yang sama pada keempat-empat peringkat dianggap sama antara satu sama lain.

Algoritma ini (dengan sekumpulan butiran teknikal tambahan) memberikan nama untuk melaporkan No. 10 - "Algoritma Pengumpulan Unikod" (ACU).

Di sinilah tingkah laku pengisihan daripada contoh kami menjadi lebih jelas sedikit. Adalah baik untuk membandingkannya dengan standard Unicode.

Untuk menguji pelaksanaan ACU ada yang istimewa ujian, menggunakan fail pemberat, melaksanakan DUCET. Anda boleh menemui pelbagai perkara lucu dalam fail skala. Sebagai contoh, terdapat susunan mahjong dan domino Eropah, serta susunan sut dalam dek kad (simbol 1F000 dan seterusnya). Sut kad diletakkan mengikut peraturan jambatan - PCBT, dan kad dalam saman itu berada dalam urutan T, 2,3, XNUMX... K.

Semak secara manual bahawa baris diisih dengan betul mengikut DUCET akan menjadi agak membosankan, tetapi, mujurlah bagi kami, terdapat pelaksanaan teladan perpustakaan untuk bekerja dengan Unicode - "Komponen Antarabangsa untuk Unicode"(ICU).

Di laman web perpustakaan ini, dibangunkan di IBM, terdapat halaman demo, termasuk halaman algoritma perbandingan rentetan. Kami memasukkan baris ujian kami dengan tetapan lalai dan, lihatlah, kami mendapat pengisihan Rusia yang sempurna.

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

By the way, laman web ICU Anda boleh mendapatkan penjelasan algoritma perbandingan semasa memproses tanda baca. Dalam contoh Soalan Lazim Pengumpulan apostrof dan sempang diabaikan.

Unicode membantu kami, tetapi cari sebab untuk tingkah laku pelik jenis в Linux perlu pergi ke tempat lain.

Isih dalam glibc

Pandangan pantas kod sumber utiliti jenis daripada Utiliti Teras GNU menunjukkan bahawa dalam utiliti itu sendiri, penyetempatan turun untuk mencetak nilai semasa pembolehubah LC_COLLATE apabila berjalan dalam mod nyahpepijat:

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

Perbandingan rentetan dilakukan menggunakan fungsi standard strcoll, yang bermaksud semua yang menarik ada di perpustakaan glibc.

Pada wiki projek glibc khusus untuk perbandingan rentetan satu perenggan. Daripada perenggan ini dapat difahami bahawa dalam glibc pengisihan adalah berdasarkan algoritma yang telah diketahui oleh kami ACU (Algoritma pengumpulan Unicode) dan/atau pada standard yang hampir dengannya ISO 14651 (Susunan dan perbandingan rentetan antarabangsa). Mengenai standard terkini, perlu diperhatikan bahawa di laman web ini standards.iso.org ISO 14651 diisytiharkan secara rasmi tersedia secara terbuka, tetapi pautan yang sepadan membawa kepada halaman yang tidak wujud. Google mengembalikan beberapa halaman dengan pautan ke tapak rasmi yang menawarkan untuk membeli salinan elektronik standard untuk seratus euro, tetapi pada halaman ketiga atau keempat hasil carian terdapat juga pautan terus ke PDF. Secara umum, piawaian itu boleh dikatakan tidak berbeza daripada ACU, tetapi lebih membosankan untuk dibaca kerana ia tidak mengandungi contoh yang jelas tentang ciri kebangsaan pengisihan rentetan.

Maklumat paling menarik mengenai wiki ada pautan ke penjejak pepijat dengan perbincangan pelaksanaan perbandingan rentetan dalam glibc. Daripada perbincangan itu dapat dipelajari bahawa glibc digunakan untuk membandingkan rentetan ISOmeja peribadi Jadual Templat Biasa (CTT), alamatnya boleh didapati dalam aplikasi A standard ISO 14651. Antara 2000 dan 2015 jadual ini masuk glibc tidak mempunyai penyelenggara dan agak berbeza (sekurang-kurangnya secara luaran) daripada versi standard semasa. Dari 2015 hingga 2018, penyesuaian kepada versi baharu jadual telah berlaku, dan kini anda berpeluang untuk bertemu dalam kehidupan sebenar versi baharu jadual (CentOS 8), dan lama (CentOS 7).

Sekarang setelah kami mempunyai semua maklumat tentang algoritma dan jadual tambahan, kami boleh kembali kepada masalah asal dan memahami cara mengisih rentetan dengan betul dalam tempat Rusia.

ISO 14651 / 14652

Kod sumber jadual yang kami minati CTT pada kebanyakan pengedaran Linux ada dalam katalog /usr/share/i18n/locales/. Jadual itu sendiri ada dalam fail iso14651_t1_common. Kemudian ini adalah arahan fail salin iso14651_t1_common dimasukkan ke dalam fail iso14651_t1, yang, seterusnya, termasuk dalam fail nasional, termasuk en_us и ru_RU. Pada kebanyakan pengedaran Linux semua fail sumber disertakan dalam pemasangan asas, tetapi jika ia tidak ada, anda perlu memasang pakej tambahan daripada pengedaran.

Struktur fail iso14651_t1 mungkin kelihatan sangat bertele-tele, dengan peraturan yang tidak jelas untuk membina nama, tetapi jika anda melihatnya, semuanya agak mudah. Struktur diterangkan dalam piawaian ISO 14652, salinannya boleh dimuat turun dari tapak web open-std.org. Penerangan lain tentang format fail boleh dibaca spesifikasi POSIX daripada OpenGroup. Sebagai alternatif kepada membaca standard, anda boleh mengkaji kod sumber fungsi tersebut kumpulkan_baca в glibc/locale/programs/ld-collate.c.

Struktur fail kelihatan seperti ini:

Secara lalai, watak digunakan sebagai watak melarikan diri, dan penghujung baris selepas aksara # ialah ulasan. Kedua-dua simbol boleh ditakrifkan semula, iaitu apa yang dilakukan dalam versi baharu jadual:

escape_char /
comment_char %

Fail akan mengandungi token dalam format atau (di mana x - digit heksadesimal). Ini ialah perwakilan heksadesimal bagi mata kod Unicode dalam pengekodan UCS-4 (UTF-32). Semua elemen lain dalam kurungan sudut (termasuk , <2> dan seumpamanya) dianggap pemalar rentetan mudah yang mempunyai sedikit makna di luar konteks.

Garisan LC_COLLATE memberitahu kita bahawa seterusnya bermula data yang menerangkan perbandingan rentetan.

Pertama, nama ditentukan untuk pemberat dalam jadual perbandingan dan nama untuk gabungan simbol. Secara umumnya, kedua-dua jenis nama itu tergolong dalam dua entiti yang berbeza, tetapi dalam fail sebenar ia bercampur. Nama-nama pemberat ditentukan oleh kata kunci mengumpul-simbol (aksara perbandingan) kerana apabila membandingkan, aksara Unicode yang mempunyai berat yang sama akan dianggap sebagai aksara yang setara.

Jumlah panjang bahagian dalam semakan fail semasa ialah kira-kira 900 baris. Saya menarik contoh dari beberapa tempat untuk menunjukkan kesewenang-wenangan nama dan beberapa jenis sintaks.

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

simbol penyusun log rentetan OSMANYA dalam jadual nama skala
simbol penyusun .. mendaftarkan urutan nama yang terdiri daripada awalan S dan akhiran berangka heksadesimal dari 1D000 kepada 1D35F.
FFFF в simbol penyusun kelihatan seperti integer tak bertanda besar dalam perenambelasan, tetapi ia hanya nama yang mungkin kelihatan seperti
Nama bermaksud titik kod dalam pengekodan UCS-4
elemen penyusun daripada "" mendaftarkan nama baharu untuk sepasang titik Unicode.

Setelah nama pemberat ditakrifkan, pemberat sebenar ditentukan. Oleh kerana hanya perhubungan yang lebih besar daripada kurang penting dalam perbandingan, pemberat ditentukan oleh urutan nama penyenaraian yang mudah. Berat "lebih ringan" disenaraikan dahulu, kemudian yang "lebih berat". Biar saya ingatkan anda bahawa setiap aksara Unicode diberikan empat pemberat berbeza. Di sini mereka digabungkan menjadi satu urutan tertib. Secara teorinya, sebarang nama simbolik boleh digunakan pada mana-mana daripada empat peringkat, tetapi komen menunjukkan bahawa pembangun secara mental memisahkan nama kepada peringkat.

% 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

Akhirnya, jadual berat sebenar.

Bahagian pemberat disertakan dalam baris kata kunci pesanan_mula и pesanan_akhir. Pilihan tambahan pesanan_mula tentukan arah baris mana yang diimbas pada setiap peringkat perbandingan. Tetapan lalai ialah ke hadapan. Badan bahagian terdiri daripada garisan yang mengandungi kod simbol dan empat pemberatnya. Kod aksara boleh diwakili oleh watak itu sendiri, titik kod, atau nama simbolik yang ditakrifkan sebelum ini. Pemberat juga boleh diberikan kepada nama simbolik, titik kod, atau simbol itu sendiri. Jika titik kod atau aksara digunakan, beratnya adalah sama dengan nilai berangka titik kod (kedudukan dalam jadual Unicode). Aksara yang tidak dinyatakan secara eksplisit (seperti yang saya faham) dianggap diberikan kepada jadual dengan pemberat utama yang sepadan dengan kedudukan dalam jadual Unicode. Nilai berat khas ABAI bermakna simbol itu diabaikan pada tahap perbandingan yang sesuai.

Untuk menunjukkan struktur skala, saya memilih tiga serpihan yang agak jelas:

watak yang diabaikan sama sekali
simbol yang setara dengan nombor tiga dalam dua peringkat pertama
permulaan abjad Cyrillic, yang tidak mengandungi diakritik, dan oleh itu disusun terutamanya mengikut tahap pertama dan ketiga.

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

Kini anda boleh kembali menyusun contoh dari awal artikel. Serangan hendap terletak pada bahagian jadual pemberat ini:

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

Ia boleh dilihat bahawa dalam jadual ini tanda baca daripada jadual ASCII (termasuk ruang) hampir selalu diabaikan apabila membandingkan rentetan. Satu-satunya pengecualian ialah garisan yang sepadan dalam segala-galanya kecuali tanda baca yang terdapat dalam kedudukan yang sepadan. Baris dari contoh saya (selepas menyusun) untuk algoritma perbandingan kelihatan seperti ini:

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

Memandangkan dalam jadual skala, huruf besar dalam bahasa Rusia datang selepas huruf kecil (di peringkat ketiga lebih berat daripada ), pengisihan kelihatan betul-betul betul.

Apabila menetapkan pembolehubah LC_COLLATE=C jadual khas dimuatkan yang menentukan perbandingan bait demi bait

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'
};

Memandangkan dalam Unicode titik kod Ё datang sebelum A, rentetan diisih sewajarnya.

Jadual teks dan binari

Jelas sekali, perbandingan rentetan ialah operasi yang sangat biasa, dan penghuraian jadual CTT prosedur yang agak mahal. Untuk mengoptimumkan akses kepada jadual, ia disusun ke dalam bentuk binari dengan arahan localdef.

Pasukan localdef menerima sebagai parameter fail dengan jadual ciri kebangsaan (option -i), di mana semua aksara diwakili oleh titik Unicode, dan fail surat-menyurat antara titik Unicode dan aksara pengekodan tertentu (pilihan -f). Hasil daripada kerja, fail binari dicipta untuk tempat dengan nama yang dinyatakan dalam parameter terakhir.

glibc menyokong dua format fail binari: "tradisional" dan "moden".

Format tradisional bermaksud nama tempat ialah nama subdirektori dalam /usr/lib/locale/. Subdirektori ini menyimpan fail binari LC_COLLATE, LC_CTYPE, LC_TIME dan sebagainya. Fail LC_IDENTIFICATION mengandungi nama rasmi tempat (yang mungkin berbeza daripada nama direktori) dan ulasan.

Format moden melibatkan penyimpanan semua tempat dalam satu arkib /usr/lib/locale/locale-archive, yang dipetakan ke memori maya semua proses yang menggunakan glibc. Nama tempat dalam format moden tertakluk kepada beberapa kanonisasi - hanya nombor dan huruf yang dikurangkan kepada huruf kecil kekal dalam nama pengekodan. Jadi ru_RU.KOI8-R, akan disimpan sebagai ru_RU.koi8r.

Fail input dicari dalam direktori semasa, serta dalam direktori /usr/share/i18n/locales/ и /usr/share/i18n/charmaps/ untuk fail CTT dan pengekodan fail, masing-masing.

Sebagai contoh, arahan

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

akan menyusun fail /usr/share/i18n/locales/ru_RU menggunakan fail pengekodan /usr/share/i18n/charmaps/MAC-CYRILLIC.gz dan simpan hasilnya /usr/lib/locale/locale-archive di bawah nama ru_RU.maccyrillic

Jika anda menetapkan pembolehubah LANG = en_US.UTF-8 bahawa glibc akan mencari binari setempat dalam urutan fail dan direktori berikut:

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

Jika tempat berlaku dalam kedua-dua format tradisional dan moden, maka keutamaan diberikan kepada yang moden.

Anda boleh melihat senarai tempat yang disusun dengan arahan locale -a.

Menyediakan jadual perbandingan anda

Kini, berbekalkan pengetahuan, anda boleh mencipta jadual perbandingan rentetan ideal anda sendiri. Jadual ini harus membandingkan dengan betul huruf Rusia, termasuk huruf Ё, dan pada masa yang sama mengambil kira tanda baca mengikut jadual ASCII.

Proses menyediakan jadual pengisihan anda sendiri terdiri daripada dua peringkat: mengedit jadual pemberat dan menyusunnya ke dalam bentuk binari dengan arahan localdef.

Agar jadual perbandingan boleh diselaraskan dengan kos penyuntingan yang minimum, dalam format ISO 14652 Bahagian untuk melaraskan pemberat jadual sedia ada disediakan. Bahagian bermula dengan kata kunci menyusun semula selepas dan menunjukkan kedudukan selepas penggantian dilakukan. Bahagian itu berakhir dengan garisan susun semula-tamat. Jika perlu untuk membetulkan beberapa bahagian jadual, maka bahagian dibuat untuk setiap bahagian tersebut.

Saya menyalin versi baharu fail iso14651_t1_common и ru_RU daripada repositori glibc ke direktori rumah saya ~/.local/share/i18n/locales/ dan mengedit sedikit bahagian LC_COLLATE в ru_RU. Versi baharu fail serasi sepenuhnya dengan versi saya glibc. Jika anda ingin menggunakan versi fail yang lebih lama, anda perlu menukar nama simbolik dan tempat penggantian bermula dalam jadual.

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

Malah, adalah perlu untuk menukar medan dalam LC_IDENTIFICATION supaya mereka menunjuk ke tempat tersebut ru_MY, tetapi dalam contoh saya ini tidak diperlukan, kerana saya mengecualikan arkib daripada carian untuk tempat arkib setempat.

Itu localdef bekerja dengan fail dalam folder saya melalui pembolehubah I18NPATH Anda boleh menambah direktori tambahan untuk mencari fail input, dan direktori untuk menyimpan fail binari boleh ditentukan sebagai laluan dengan garis miring:

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

POSIX menganggap bahawa dalam BAHASA anda boleh menulis laluan mutlak ke direktori dengan fail setempat, bermula dengan garis miring ke hadapan, tetapi glibc в Linux semua laluan dikira daripada direktori asas, yang boleh ditindih melalui pembolehubah LOCPATH. Selepas pemasangan LOCPATH=~/.local/lib/locale/ semua fail yang berkaitan dengan penyetempatan akan dicari hanya dalam folder saya. Arkib tempat dengan set pembolehubah LOCPATH diabaikan.

Inilah ujian yang menentukan:

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

Hooray! Kita berjaya!

Beberapa kesilapan

Saya telah menjawab soalan mengenai pengisihan rentetan yang dikemukakan pada mulanya, tetapi masih terdapat beberapa soalan tentang ralat - kelihatan dan tidak kelihatan.

Mari kita kembali kepada masalah asal.

Dan program jenis dan program menyertai gunakan fungsi perbandingan rentetan yang sama dari glibc. Bagaimana ia berlaku menyertai memberikan ralat pengisihan pada baris yang diisih mengikut arahan jenis dalam tempatan en_US.UTF-8? Jawapannya mudah: jenis membandingkan keseluruhan rentetan, dan menyertai membandingkan hanya kunci, yang secara lalai ialah permulaan rentetan sehingga aksara ruang putih pertama. Dalam contoh saya, ini mengakibatkan mesej ralat kerana pengisihan perkataan pertama dalam baris tidak sepadan dengan pengisihan baris lengkap.

Tempatan "C" menjamin bahawa dalam rentetan diisih subrentetan awal sehingga ruang pertama juga akan diisih, tetapi ini hanya menutupi ralat. Adalah mungkin untuk memilih data (orang yang mempunyai nama keluarga yang sama, tetapi nama pertama yang berbeza) yang, tanpa mesej ralat, akan memberikan hasil gabungan fail yang salah. Jika kita mahu menyertai menggabungkan baris fail dengan nama penuh, maka cara yang betul ialah dengan menyatakan secara eksplisit pemisah medan dan mengisih mengikut medan utama, dan bukan dengan keseluruhan baris. Dalam kes ini, penggabungan akan diteruskan dengan betul dan tidak akan ada ralat dalam mana-mana tempat:

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

Berjaya melaksanakan contoh dalam pengekodan CP1251 mengandungi ralat lain. Hakikatnya ialah dalam semua pengedaran yang saya ketahui Linux pakej tiada tempat tersusun ru_RU.CP1251. Jika tempat yang disusun tidak dijumpai, maka jenis secara senyap menggunakan perbandingan bait demi bait, itulah yang kami perhatikan.

Ngomong-ngomong, terdapat satu lagi gangguan kecil yang berkaitan dengan ketidakbolehcapaian tempat yang disusun. Pasukan LOCPATH=/tmp locale -a akan memberikan senarai semua tempat dalam arkib setempat, tetapi dengan set pembolehubah LOCPATH untuk semua program (termasuk yang paling banyak tempat-tempat kejadian) tempat ini tidak akan tersedia.

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

Kesimpulan

Jika anda seorang pengaturcara yang biasa berfikir bahawa rentetan adalah satu set bait, maka pilihan anda LC_COLLATE=C.

Jika anda seorang ahli bahasa atau penyusun kamus, maka lebih baik anda menyusun dalam tempat anda.

Jika anda seorang pengguna yang mudah, maka anda hanya perlu membiasakan diri dengan hakikat bahawa arahan itu ls -a mengeluarkan fail bermula dengan titik bercampur dengan fail bermula dengan huruf, dan Panglima tengah malam, yang menggunakan fungsi dalamannya untuk mengisih nama, meletakkan fail bermula dengan titik pada permulaan senarai.