pengenalan

Semuanya dimulai dengan skrip pendek yang seharusnya menggabungkan informasi alamat email karyawan diperoleh dari daftar pengguna milis, dengan posisi karyawan diperoleh dari database departemen HR. Kedua daftar diekspor ke file teks Unicode UTF-8 dan disimpan dengan akhiran baris Unix.

Konten mail.txt

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

Konten buhg.txt

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

Untuk menggabungkan, file diurutkan berdasarkan perintah Unix jenis dan diserahkan ke input program Unix ikut, yang tiba-tiba gagal karena kesalahan:

$> 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 penyortiran dengan mata kepala sendiri menunjukkan bahwa secara umum penyortiran tersebut benar, namun jika terjadi kebetulan nama keluarga laki-laki dan perempuan, maka nama perempuan didahulukan sebelum nama laki-laki:

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

Sepertinya kesalahan penyortiran di Unicode atau seperti manifestasi feminisme dalam algoritma penyortiran. Yang pertama tentu saja lebih masuk akal.

Mari kita tunda dulu ikut dan fokus pada jenis. Mari kita coba selesaikan masalah tersebut dengan menggunakan tusukan ilmiah. Pertama, mari kita ubah lokalnya dari en_US pada ru_RU. Untuk mengurutkan, cukup dengan mengatur variabel lingkungan LC_COLLATE, tapi kami tidak akan membuang waktu untuk hal-hal sepele:

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

Tidak ada yang berubah.

Mari kita coba mengkode ulang file menjadi pengkodean byte tunggal:

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

Sekali lagi tidak ada yang berubah.

Tidak ada yang dapat Anda lakukan, Anda harus mencari solusi di Internet. Tidak ada informasi langsung tentang nama keluarga Rusia, tetapi ada pertanyaan tentang keanehan penyortiran lainnya. Misalnya, inilah masalahnya: unix sort memperlakukan karakter '-' (tanda hubung) sebagai tidak terlihat. Singkatnya, string "ab", "aa", "ac" diurutkan menjadi "aa", "ab", "ac".

Jawabannya standar di mana-mana: gunakan lokal programmer "C" dan kamu akan bahagia. Mari mencoba:

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

Sesuatu telah berubah. Keluarga Ivanov berbaris dalam urutan yang benar, meskipun Yolkina tergelincir entah kemana. Mari kita kembali ke permasalahan awal:

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

Ini berfungsi tanpa kesalahan, seperti yang dijanjikan Internet. Dan ini meskipun Yolkina berada di baris pertama.

Masalahnya tampaknya telah terpecahkan, tetapi untuk berjaga-jaga, mari kita coba pengkodean Rusia lainnya - Windows CP1251:

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

Anehnya, hasil penyortiran akan bertepatan dengan lokal "C", dan seluruh contoh berjalan tanpa kesalahan. Semacam mistisisme.

Saya tidak suka mistisisme dalam pemrograman karena biasanya menutupi kesalahan. Kita harus serius melihat cara kerjanya. jenis dan apa pengaruhnya? LC_COLLATE .

Pada akhirnya saya akan mencoba menjawab pertanyaan:

mengapa nama keluarga perempuan diurutkan secara tidak benar?
mengapa LANG=ru_RU.CP1251 ternyata setara LANG=C
kenapa jenis и ikut ide berbeda tentang urutan string yang diurutkan
mengapa ada kesalahan dalam semua contoh saya?
terakhir bagaimana cara mengurutkan string sesuai dengan keinginan anda

Menyortir dalam Unicode

Pemberhentian pertama adalah laporan teknis No. 10 yang berjudul Algoritma pemeriksaan Unicode secara online unicode.org. Laporan ini berisi banyak detail teknis, jadi izinkan saya memberikan ringkasan singkat tentang gagasan utamanya.

Pemeriksaan — “membandingkan” string adalah dasar dari algoritma pengurutan apa pun. Algoritmenya sendiri mungkin berbeda ("gelembung", "gabungan", "cepat"), tetapi semuanya akan menggunakan perbandingan sepasang string untuk menentukan urutan kemunculannya.

Mengurutkan string dalam bahasa alami merupakan masalah yang cukup kompleks. Bahkan dalam pengkodean byte tunggal yang paling sederhana, urutan huruf dalam alfabet, meskipun dalam beberapa hal berbeda dari alfabet Latin Inggris, tidak akan lagi sesuai dengan urutan nilai numerik yang digunakan untuk mengkodekan huruf-huruf ini. Jadi dalam alfabet Jerman hurufnya Ö berdiri di antara О и P, dan dalam pengkodean CP850 dia berada di antara keduanya ÿ и Ü.

Anda dapat mencoba mengabstraksi dari pengkodean tertentu dan mempertimbangkan huruf "ideal" yang disusun dalam urutan tertentu, seperti yang dilakukan di Unicode. Pengkodean UTF8, UTF16 atau satu byte KOI8-R (jika subset Unicode terbatas diperlukan) akan memberikan representasi numerik huruf yang berbeda, tetapi mengacu pada elemen tabel dasar yang sama.

Ternyata meskipun kita membuat tabel simbol dari awal, kita tidak akan dapat menetapkan urutan simbol universal padanya. Dalam alfabet nasional berbeda yang menggunakan huruf yang sama, urutan huruf tersebut mungkin berbeda. Misalnya saja dalam bahasa Perancis Æ akan dianggap sebagai pengikat dan diurutkan sebagai string AE. Dalam bahasa Norwegia Æ akan menjadi surat tersendiri, yang terletak setelahnya Z. Ngomong-ngomong, selain ligatur sejenisnya Æ Ada huruf yang ditulis dengan beberapa simbol. Jadi dalam alfabet Ceko ada sebuah huruf Ch, yang berdiri di antara H и I.

Selain perbedaan abjad, ada tradisi nasional lain yang mempengaruhi pemilahan. Secara khusus, timbul pertanyaan: dalam urutan apa kata-kata yang terdiri dari huruf besar dan huruf kecil harus muncul dalam kamus? Penyortiran juga mungkin dipengaruhi oleh penggunaan tanda baca. Dalam bahasa Spanyol, tanda tanya terbalik digunakan di awal kalimat tanya (Apakah Anda suka musik?). Dalam hal ini, jelas bahwa kalimat tanya tidak boleh dikelompokkan ke dalam kelompok tersendiri di luar alfabet, tetapi bagaimana cara mengurutkan baris dengan tanda baca lain?

Saya tidak akan membahas penyortiran string dalam bahasa yang sangat berbeda dari bahasa Eropa. Perhatikan bahwa dalam bahasa dengan arah penulisan dari kanan ke kiri atau atas ke bawah, karakter dalam baris kemungkinan besar disimpan dalam urutan bacaan, dan bahkan sistem penulisan non-abjad memiliki caranya sendiri dalam mengurutkan baris karakter demi karakter. . Misalnya, hieroglif dapat diurutkan berdasarkan gaya (Kunci karakter Cina) atau dengan pengucapan. Sejujurnya, saya tidak tahu cara mengatur emoji, tapi Anda juga bisa membuatkan sesuatu untuk emoji tersebut.

Berdasarkan fitur yang tercantum di atas, persyaratan dasar untuk membandingkan string berdasarkan tabel Unicode dirumuskan:

perbandingan string tidak bergantung pada posisi karakter dalam tabel kode;
rangkaian karakter yang membentuk satu karakter direduksi menjadi bentuk kanonik (A + lingkaran paling atas sama dengan Å);
Saat membandingkan string, sebuah karakter dipertimbangkan dalam konteks string dan, jika perlu, digabungkan dengan tetangganya menjadi satu unit perbandingan (Ch dalam bahasa Ceko) atau dibagi menjadi beberapa (Æ di Perancis);
semua fitur nasional (abjad, huruf besar/kecil, tanda baca, urutan jenis penulisan) harus dikonfigurasi hingga penetapan urutan secara manual (emoji);
perbandingan penting tidak hanya untuk pengurutan, tetapi juga di banyak tempat lain, misalnya untuk menentukan rentang baris (menggantikan {A... z} ke dalam menampar);
perbandingannya harus dilakukan dengan cukup cepat.

Selain itu, penulis laporan merumuskan properti perbandingan yang tidak boleh diandalkan oleh pengembang algoritme:

algoritme perbandingan tidak memerlukan kumpulan karakter terpisah untuk setiap bahasa (bahasa Rusia dan Ukraina memiliki sebagian besar karakter Sirilik);
perbandingannya tidak boleh bergantung pada urutan karakter dalam tabel Unicode;
bobot string tidak boleh menjadi atribut string, karena string yang sama dalam konteks budaya berbeda dapat memiliki bobot berbeda;
bobot baris dapat berubah saat menggabungkan atau memisahkan (dari x < y itu tidak mengikuti itu xz < yz);
string berbeda yang memiliki bobot yang sama dianggap sama dari sudut pandang algoritma pengurutan. Memperkenalkan pemesanan tambahan pada string tersebut dimungkinkan, tetapi hal ini dapat menurunkan kinerja;
Selama penyortiran berulang, baris dengan bobot yang sama dapat ditukar. Kekokohan adalah properti dari algoritma pengurutan tertentu, dan bukan properti dari algoritma perbandingan string (lihat paragraf sebelumnya);
Aturan penyortiran dapat berubah seiring berjalannya waktu seiring dengan penyempurnaan/perubahan tradisi budaya.

Ditetapkan juga bahwa algoritma perbandingan tidak mengetahui apa pun tentang semantik string yang sedang diproses. Jadi, string yang hanya terdiri dari angka tidak boleh dibandingkan dengan angka, dan dalam daftar nama bahasa Inggris artikel (Beatles, Itu).

Untuk memenuhi semua persyaratan yang ditentukan, algoritma pengurutan tabel multi-level (sebenarnya empat level) diusulkan.

Sebelumnya, karakter dalam string direduksi menjadi bentuk kanonik dan dikelompokkan ke dalam unit perbandingan. Setiap unit perbandingan diberi beberapa bobot yang sesuai dengan beberapa tingkat perbandingan. Bobot unit pembanding adalah elemen himpunan terurut (dalam hal ini bilangan bulat) yang dapat dibandingkan lebih besar atau lebih kecil. Arti khusus diabaikan (0x0) berarti pada tingkat perbandingan yang sesuai, unit ini tidak terlibat dalam perbandingan. Perbandingan string dapat diulangi beberapa kali menggunakan bobot level yang sesuai. Pada setiap tingkat, bobot unit perbandingan dua baris dibandingkan satu sama lain secara berurutan.

Dalam implementasi algoritme yang berbeda untuk tradisi nasional yang berbeda, nilai koefisien mungkin berbeda, tetapi standar Unicode menyertakan tabel bobot dasar - "Tabel Elemen Susunan Unicode Default" (DUCET). Saya ingin mencatat bahwa pengaturan variabel LC_COLLATE sebenarnya merupakan indikasi pemilihan tabel bobot dalam fungsi perbandingan string.

Koefisien pembobotan DUCET disusun sebagai berikut:

pada tingkat pertama, semua huruf direduksi menjadi huruf besar yang sama, diakritik dibuang, tanda baca (tidak semua) diabaikan;
pada tingkat kedua, hanya diakritik yang diperhitungkan;
pada tingkat ketiga, hanya kasus yang diperhitungkan;
pada tingkat keempat, hanya tanda baca yang diperhitungkan.

Perbandingan dilakukan dalam beberapa tahap: pertama, koefisien tingkat pertama dibandingkan; jika bobotnya sama, maka dilakukan perbandingan berulang dengan bobot tingkat kedua; lalu mungkin yang ketiga dan keempat.

Perbandingan berakhir ketika baris berisi unit perbandingan yang cocok dengan bobot berbeda. Baris-baris yang mempunyai bobot yang sama pada keempat tingkat dianggap sama satu sama lain.

Algoritme ini (dengan banyak detail teknis tambahan) memberi nama pada laporan No. 10 - "Algoritma Pengumpulan Unicode" (ACU).

Di sinilah perilaku pengurutan dari contoh kita menjadi sedikit lebih jelas. Alangkah baiknya jika membandingkannya dengan standar Unicode.

Untuk menguji implementasi ACU ada yang spesial uji, menggunakan file bobot, menerapkan DUCET. Anda dapat menemukan segala macam hal lucu di file timbangan. Misalnya ada susunan mahjong dan domino Eropa, serta susunan jas dalam setumpuk kartu (simbol 1F000 dan selanjutnya). Setelan kartu ditempatkan sesuai dengan aturan bridge - PCBT, dan kartu dalam setelan tersebut berada pada urutan T, 2,3, XNUMX... K.

Memeriksa secara manual apakah baris diurutkan dengan benar menurut DUCET akan sangat membosankan, tapi untungnya bagi kami, ada implementasi perpustakaan yang patut dicontoh untuk bekerja dengan Unicode - "Komponen Internasional untuk Unicode"(ICU).

Di situs web perpustakaan ini, dikembangkan di IBM, ada halaman demo, termasuk halaman algoritma perbandingan string. Kami memasuki jalur pengujian kami dengan pengaturan default dan, lihatlah, kami mendapatkan penyortiran Rusia yang sempurna.

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

Omong-omong, situs web ICU Anda dapat menemukan klarifikasi algoritma perbandingan saat memproses tanda baca. Dalam contoh FAQ Kolasi apostrof dan tanda hubung diabaikan.

Unicode membantu kami, tetapi mencari alasan untuk perilaku aneh jenis в Linux harus pergi ke tempat lain.

Menyortir di glibc

Tampilan cepat kode sumber utilitas jenis dari Utilitas Inti GNU menunjukkan bahwa dalam utilitas itu sendiri, lokalisasi dilakukan untuk mencetak nilai variabel saat ini LC_COLLATE saat berjalan dalam mode debug:

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

Perbandingan string dilakukan menggunakan fungsi standar jalan-jalan, artinya segala sesuatu yang menarik ada di perpustakaan glibc.

Pada wiki proyek glibc didedikasikan untuk perbandingan string satu paragraf. Dari paragraf ini dapat dipahami bahwa di glibc penyortiran didasarkan pada algoritma yang sudah kita ketahui ACU (Algoritma pemeriksaan Unicode) dan/atau pada standar yang mendekatinya ISO 14651 (Pemesanan dan perbandingan string internasional). Mengenai standar terbaru, perlu diperhatikan di situs standar.iso.org ISO 14651 secara resmi dinyatakan tersedia untuk umum, tetapi tautan yang sesuai mengarah ke halaman yang tidak ada. Google mengembalikan beberapa halaman dengan link ke situs resmi yang menawarkan untuk membeli salinan elektronik standar tersebut seharga seratus euro, tetapi pada halaman ketiga atau keempat hasil pencarian juga terdapat link langsung ke PDF. Secara umum, standarnya praktis tidak berbeda dengan ACU, tetapi lebih membosankan untuk dibaca karena tidak memuat contoh yang jelas tentang fitur nasional penyortiran string.

Informasi paling menarik tentang wiki ada tautan ke pelacak bug dengan pembahasan implementasi perbandingan string di glibc. Dari diskusi tersebut dapat diambil pelajaran bahwa glibc digunakan untuk membandingkan string ISOmeja pribadi Tabel Templat Umum (CTT), alamatnya dapat ditemukan di aplikasi A standar ISO 14651. Antara tahun 2000 dan 2015 tabel ini masuk glibc tidak memiliki pengelola dan sangat berbeda (setidaknya secara eksternal) dari versi standar saat ini. Dari 2015 hingga 2018, adaptasi ke versi tabel baru berlangsung, dan sekarang Anda memiliki kesempatan untuk bertemu dengan tabel versi baru di kehidupan nyata (8 CentOS), dan lama (7 CentOS).

Sekarang setelah kita memiliki semua informasi tentang algoritme dan tabel tambahan, kita dapat kembali ke masalah awal dan memahami cara mengurutkan string dengan benar dalam bahasa Rusia.

ISO 14651 / 14652

Kode sumber tabel yang kami minati CTT pada sebagian besar distribusi Linux ada di direktori /usr/berbagi/i18n/lokal/. Tabelnya sendiri ada di dalam file iso14651_t1_common. Maka ini adalah arahan file salin iso14651_t1_common disertakan dalam file iso14651_t1, yang, pada gilirannya, termasuk dalam arsip nasional en_US и ru_RU. Pada sebagian besar distribusi Linux Semua file sumber disertakan dalam instalasi dasar, tetapi jika tidak ada, Anda harus menginstal paket tambahan dari distribusi.

Struktur file iso14651_t1 mungkin tampak sangat bertele-tele, dengan aturan yang tidak jelas untuk membuat nama, tetapi jika Anda melihatnya, semuanya cukup sederhana. Strukturnya dijelaskan dalam standar ISO 14652, salinannya dapat diunduh dari situs web buka-std.org. Penjelasan lain mengenai format file dapat dibaca di spesifikasi POSIX dari Grup Terbuka. Sebagai alternatif untuk membaca standar, Anda dapat mempelajari kode sumber fungsi tersebut susun_baca в glibc/locale/programs/ld-collate.c.

Struktur filenya terlihat seperti ini:

Secara default, karakter digunakan sebagai karakter escape, dan akhir baris setelah karakter # adalah komentar. Kedua simbol dapat didefinisikan ulang, seperti yang dilakukan pada tabel versi baru:

escape_char /
comment_char %

File tersebut akan berisi token dalam format или (di mana x - angka heksadesimal). Ini adalah representasi heksadesimal dari titik kode Unicode dalam pengkodean UCS-4 (UTF-32). Semua elemen lain dalam tanda kurung sudut (termasuk , <2> dan sejenisnya) dianggap sebagai konstanta string sederhana yang mempunyai sedikit makna di luar konteks.

Tali LC_COLLATE memberi tahu kita bahwa selanjutnya dimulailah data yang menjelaskan perbandingan string.

Pertama, nama ditentukan untuk bobot dalam tabel perbandingan dan nama untuk kombinasi simbol. Secara umum, kedua jenis nama tersebut dimiliki oleh dua entitas yang berbeda, tetapi dalam file sebenarnya keduanya tercampur. Nama bobot ditentukan berdasarkan kata kunci menyusun-simbol (karakter perbandingan) karena ketika membandingkan, karakter Unicode yang memiliki bobot yang sama akan dianggap sebagai karakter yang setara.

Total panjang bagian dalam revisi file saat ini adalah sekitar 900 baris. Saya mengambil contoh dari beberapa tempat untuk menunjukkan kesewenang-wenangan nama dan beberapa jenis sintaksis.

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 penyusunan mencatat sebuah string OSMANYA dalam tabel nama tangga nada
simbol penyusunan .. mendaftarkan urutan nama yang terdiri dari awalan S dan akhiran numerik heksadesimal dari 1D000 untuk 1D35F.
Ffff в simbol penyusunan tampak seperti bilangan bulat besar yang tidak ditandatangani dalam heksadesimal, tapi itu hanya nama yang mungkin terlihat seperti itu
nama berarti titik kode dalam pengkodean UCS-4
elemen penyusunan dari " " mendaftarkan nama baru untuk sepasang titik Unicode.

Setelah nama bobot ditentukan, bobot sebenarnya ditentukan. Karena hanya hubungan yang lebih besar dari yang lebih kecil yang penting dalam perbandingan, bobot ditentukan oleh urutan nama daftar yang sederhana. Bobot yang “lebih ringan” dicantumkan terlebih dahulu, kemudian bobot yang “lebih berat”. Izinkan saya mengingatkan Anda bahwa setiap karakter Unicode diberi empat bobot berbeda. Di sini mereka digabungkan menjadi satu urutan berurutan. Secara teori, nama simbolik apa pun dapat digunakan di salah satu dari empat level, namun komentar menunjukkan bahwa pengembang secara mental memisahkan nama ke dalam level.

% 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

Terakhir, tabel berat sebenarnya.

Bagian bobot diapit oleh baris kata kunci pesanan_mulai и pesanan_akhir. Opsi tambahan pesanan_mulai menentukan ke arah mana baris dipindai pada setiap tingkat perbandingan. Pengaturan defaultnya adalah meneruskan. Badan bagian terdiri dari baris-baris yang memuat kode simbol dan keempat bobotnya. Kode karakter dapat diwakili oleh karakter itu sendiri, titik kode, atau nama simbolik yang telah ditentukan sebelumnya. Bobot juga dapat diberikan pada nama simbolik, titik kode, atau simbol itu sendiri. Jika titik kode atau karakter digunakan, bobotnya sama dengan nilai numerik titik kode (posisi dalam tabel Unicode). Karakter yang tidak ditentukan secara eksplisit (seperti yang saya pahami) dianggap ditugaskan ke tabel dengan bobot utama yang cocok dengan posisi di tabel Unicode. Nilai bobot khusus LAGI berarti simbol tersebut diabaikan pada tingkat perbandingan yang sesuai.

Untuk mendemonstrasikan struktur skala, saya memilih tiga fragmen yang cukup jelas:

karakter yang sepenuhnya diabaikan
simbol yang setara dengan angka tiga di dua level pertama
awal alfabet Sirilik, yang tidak mengandung diakritik, dan oleh karena itu diurutkan terutama berdasarkan tingkat 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

Sekarang Anda dapat kembali mengurutkan contoh dari awal artikel. Penyergapannya terletak pada bagian tabel bobot ini:

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

Terlihat pada tabel ini terdapat tanda baca dari tabel ASCII (termasuk spasi) hampir selalu diabaikan saat membandingkan string. Satu-satunya pengecualian adalah garis yang cocok dalam segala hal kecuali tanda baca yang ditemukan pada posisi yang cocok. Baris dari contoh saya (setelah pengurutan) untuk algoritma perbandingan terlihat seperti ini:

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

Mengingat dalam tabel skala, huruf kapital dalam bahasa Rusia berada setelah huruf kecil (pada tingkat ketiga lebih berat dari ), penyortirannya terlihat benar sekali.

Saat mengatur variabel LC_COLLATE=C tabel khusus dimuat yang menentukan perbandingan byte demi 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'
};

Karena di Unicode titik kode Ё muncul sebelum A, string diurutkan sesuai dengan itu.

Tabel teks dan biner

Jelas sekali, perbandingan string adalah operasi yang sangat umum, dan penguraian tabel CTT prosedur yang cukup mahal. Untuk mengoptimalkan akses ke tabel, tabel dikompilasi ke dalam bentuk biner dengan perintah lokaledef.

Tim lokaledef menerima sebagai parameter file dengan tabel karakteristik nasional (opsi -i), di mana semua karakter diwakili oleh titik-titik Unicode, dan file korespondensi antara titik-titik Unicode dan karakter-karakter dari pengkodean tertentu (opsi -f). Sebagai hasil dari pekerjaan tersebut, file biner dibuat untuk lokal dengan nama yang ditentukan dalam parameter terakhir.

glibc mendukung dua format file biner: "tradisional" dan "modern".

Format tradisional berarti nama lokal adalah nama subdirektori di dalamnya /usr/lib/lokal/. Subdirektori ini menyimpan file biner LC_COLLATE, LC_CTYPE, LC_TIME dan seterusnya. Mengajukan LC_IDENTIFIKASI berisi nama resmi lokal (yang mungkin berbeda dari nama direktori) dan komentar.

Format modern melibatkan penyimpanan semua lokal dalam satu arsip /usr/lib/locale/locale-archive, yang dipetakan ke memori virtual dari semua proses yang menggunakan glibc. Nama lokal dalam format modern tunduk pada beberapa kanonisasi - hanya angka dan huruf kecil yang tersisa dalam nama pengkodean. Jadi ru_RU.KOI8-R, akan disimpan sebagai ru_RU.koi8r.

File input dicari di direktori saat ini, serta di direktori /usr/berbagi/i18n/lokal/ и /usr/berbagi/i18n/charmaps/ untuk file CTT dan pengkodean file, masing-masing.

Misalnya perintah

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

akan mengkompilasi file /usr/share/i18n/locales/ru_RU menggunakan file pengkodean /usr/share/i18n/charmaps/MAC-CYRILLIC.gz dan simpan hasilnya /usr/lib/locale/locale-archive atas nama ru_RU.maccyrillic

Jika Anda mengatur variabel LANG = en_US.UTF-8 bahwa glibc akan mencari biner lokal dalam urutan file 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 suatu lokal muncul dalam format tradisional dan modern, maka prioritas diberikan pada format modern.

Anda dapat melihat daftar lokal yang dikompilasi dengan perintah lokal -a.

Mempersiapkan tabel perbandingan Anda

Sekarang, berbekal pengetahuan, Anda dapat membuat tabel perbandingan string ideal Anda sendiri. Tabel ini harus membandingkan huruf-huruf Rusia dengan benar, termasuk huruf Ё, dan pada saat yang sama memperhitungkan tanda baca sesuai dengan tabel ASCII.

Proses pembuatan tabel pengurutan sendiri terdiri dari dua tahap yaitu mengedit tabel bobot dan menyusunnya ke dalam bentuk biner dengan perintah lokaledef.

Agar tabel perbandingan dapat disesuaikan dengan biaya pengeditan yang minimal, dalam format ISO 14652 Bagian untuk mengatur bobot tabel yang ada disediakan. Bagian ini dimulai dengan kata kunci pesan ulang setelahnya dan menunjukkan posisi setelah penggantian dilakukan. Bagian ini diakhiri dengan garis pemesanan ulang-akhir. Jika perlu untuk memperbaiki beberapa bagian tabel, maka satu bagian dibuat untuk setiap bagian tersebut.

Saya menyalin file versi baru iso14651_t1_common и ru_RU dari repositori glibc ke direktori home saya ~/.local/share/i18n/locales/ dan sedikit mengedit bagian tersebut LC_COLLATE в ru_RU. File versi baru sepenuhnya kompatibel dengan versi saya glibc. Jika Anda ingin menggunakan file versi lama, Anda harus mengubah nama simbolis dan tempat dimulainya penggantian di tabel.

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

Faktanya, bidang tersebut perlu diubah LC_IDENTIFIKASI sehingga mereka menunjuk ke lokasi ru_MY, tetapi dalam contoh saya hal ini tidak diperlukan, karena saya mengecualikan arsip dari pencarian lokal arsip lokal.

Bahwa lokaledef bekerja dengan file di folder saya melalui variabel I18NPTH Anda dapat menambahkan direktori tambahan untuk mencari file masukan, dan direktori untuk menyimpan file biner dapat ditentukan sebagai jalur dengan garis miring:

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

POSIX menyarankan itu di BAHASA Anda dapat menulis jalur absolut ke direktori dengan file lokal, dimulai dengan garis miring, tapi glibc в Linux semua jalur dihitung dari direktori dasar, yang dapat diganti melalui variabel LOCPATH. Setelah instalasi LOCPATH=~/.local/lib/locale/ semua file yang berhubungan dengan lokalisasi hanya akan dicari di folder saya. Arsip lokal dengan kumpulan variabel LOCPATH diabaikan.

Inilah ujian yang menentukan:

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

Hore! Kita berhasil!

Beberapa kesalahan

Saya telah menjawab pertanyaan tentang penyortiran string yang diajukan di awal, namun masih ada beberapa pertanyaan tentang kesalahan - terlihat dan tidak terlihat.

Mari kita kembali ke masalah awal.

Dan programnya jenis dan programnya ikut gunakan fungsi perbandingan string yang sama dari glibc. Bagaimana hal itu bisa terjadi ikut memberikan kesalahan penyortiran pada baris yang diurutkan berdasarkan perintah jenis di lokal id_US.UTF-8? Jawabannya sederhana: jenis membandingkan seluruh string, dan ikut hanya membandingkan kunci, yang secara default adalah awal string hingga karakter spasi pertama. Dalam contoh saya, ini menghasilkan pesan kesalahan karena pengurutan kata pertama di baris tidak cocok dengan pengurutan baris lengkap.

Lokal "C" menjamin bahwa dalam string yang diurutkan, substring awal hingga spasi pertama juga akan diurutkan, tetapi ini hanya menutupi kesalahan. Dimungkinkan untuk memilih data (orang dengan nama keluarga yang sama, namun nama depan berbeda) yang, tanpa pesan kesalahan, akan memberikan hasil penggabungan file yang salah. Jika kita mau ikut menggabungkan baris file berdasarkan nama lengkap, maka cara yang benar adalah dengan secara eksplisit menentukan pemisah bidang dan mengurutkan berdasarkan bidang kunci, dan bukan berdasarkan seluruh baris. Dalam hal ini, penggabungan akan berjalan dengan benar dan tidak akan ada kesalahan di lokal mana pun:

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

Contoh yang berhasil dieksekusi dalam pengkodean CP1251 mengandung kesalahan lain. Faktanya adalah bahwa di semua distribusi yang saya ketahui Linux paket tidak memiliki lokal yang dikompilasi ru_RU.CP1251. Jika lokal yang dikompilasi tidak ditemukan, maka jenis secara diam-diam menggunakan perbandingan byte demi byte, itulah yang kami amati.

Omong-omong, ada kesalahan kecil lainnya terkait dengan tidak dapat diaksesnya lokal yang dikompilasi. Tim LOCPATH=/tmp lokal -a akan memberikan daftar semua lokal di arsip lokal, tetapi dengan kumpulan variabel LOCPATH untuk semua program (termasuk sebagian besar Lokal) lokal 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 programmer yang terbiasa berpikir bahwa string adalah sekumpulan byte, maka pilihan Anda LC_COLLATE=C.

Jika Anda seorang ahli bahasa atau kompiler kamus, sebaiknya Anda mengkompilasinya di lokal Anda.

Jika Anda adalah pengguna sederhana, maka Anda hanya perlu membiasakan diri dengan perintah itu ls -a mengeluarkan file yang dimulai dengan titik dicampur dengan file yang dimulai dengan huruf, dan Komandan tengah malam, yang menggunakan fungsi internalnya sendiri untuk mengurutkan nama, menempatkan file yang dimulai dengan titik di awal daftar.