Jika anda seorang pembangun dan anda berhadapan dengan tugas untuk memilih pengekodan, maka Unicode hampir selalu menjadi penyelesaian yang tepat. Kaedah perwakilan khusus bergantung pada konteks, tetapi selalunya terdapat jawapan universal di sini juga - UTF-8. Perkara yang baik mengenainya ialah ia membolehkan anda menggunakan semua aksara Unicode tanpa berbelanja terlalu banyak banyak bait dalam kebanyakan kes. Benar, untuk bahasa yang menggunakan lebih daripada sekadar abjad Latin, "tidak terlalu banyak" adalah sekurang-kurangnya dua bait setiap aksara. Bolehkah kita melakukan yang lebih baik tanpa kembali kepada pengekodan prasejarah yang mengehadkan kita kepada hanya 256 aksara yang tersedia?
Di bawah ini saya mencadangkan untuk membiasakan diri dengan percubaan saya untuk menjawab soalan ini dan melaksanakan algoritma yang agak mudah yang membolehkan anda menyimpan baris dalam kebanyakan bahasa di dunia tanpa menambah redundansi yang ada dalam UTF-8.
Penafian. Saya akan segera membuat beberapa tempahan penting: penyelesaian yang diterangkan tidak ditawarkan sebagai pengganti universal untuk UTF-8, ia hanya sesuai dalam senarai kes yang sempit (lebih lanjut mengenainya di bawah), dan ia tidak boleh digunakan untuk berinteraksi dengan API pihak ketiga (yang tidak mengetahuinya). Selalunya, algoritma pemampatan tujuan umum (contohnya, kempis) sesuai untuk penyimpanan padat volum besar data teks. Di samping itu, sudah dalam proses mencipta penyelesaian saya, saya menemui piawaian sedia ada dalam Unicode itu sendiri, yang menyelesaikan masalah yang sama - ia agak lebih rumit (dan selalunya lebih teruk), tetapi ia masih merupakan piawaian yang diterima, dan bukan hanya meletakkan bersama-sama di atas lutut. Saya akan memberitahu anda tentang dia juga.
Mengenai Unicode dan UTF-8
Sebagai permulaan, beberapa perkataan tentang apa itu Unicode ΠΈ UTF-8.
Seperti yang anda ketahui, pengekodan 8-bit dahulunya popular. Dengan mereka, semuanya mudah: 256 aksara boleh dinomborkan dengan nombor dari 0 hingga 255, dan nombor dari 0 hingga 255 jelas boleh diwakili sebagai satu bait. Jika kita kembali ke awal, pengekodan ASCII adalah terhad sepenuhnya kepada 7 bit, jadi bit yang paling ketara dalam perwakilan baitnya ialah sifar, dan kebanyakan pengekodan 8-bit serasi dengannya (ia hanya berbeza dalam "atas" bahagian, di mana bit yang paling ketara ialah satu ).
Bagaimanakah Unicode berbeza daripada pengekodan tersebut dan mengapa begitu banyak perwakilan khusus dikaitkan dengannya - UTF-8, UTF-16 (BE dan LE), UTF-32? Mari kita susun mengikut urutan.
Piawaian Unicode asas menerangkan hanya surat-menyurat antara aksara (dan dalam beberapa kes, komponen individu aksara) dan nombornya. Dan terdapat banyak kemungkinan nombor dalam piawaian ini - dari 0x00 kepada 0x10FFFF (1 keping). Jika kita ingin meletakkan nombor dalam julat sedemikian ke dalam pembolehubah, 114 atau 112 bait tidak akan mencukupi untuk kita. Dan kerana pemproses kami tidak direka bentuk untuk bekerja dengan nombor tiga bait, kami akan terpaksa menggunakan sebanyak 1 bait setiap aksara! Ini adalah UTF-2, tetapi kerana "pembaziran" inilah format ini tidak popular.
Nasib baik, susunan aksara dalam Unicode tidak rawak. Keseluruhan set mereka dibahagikan kepada 17"kapal terbang", setiap satunya mengandungi 65536 (0x10000) "mata kod" Konsep "titik kod" di sini adalah mudah nombor aksara, diberikan kepadanya oleh Unicode. Tetapi, seperti yang dinyatakan di atas, dalam Unicode bukan sahaja aksara individu dinomborkan, tetapi juga komponen dan tanda perkhidmatan mereka (dan kadang-kadang tidak ada yang sepadan dengan nombor itu - mungkin buat masa ini, tetapi bagi kami ini tidak begitu penting), jadi ia adalah lebih betul sentiasa bercakap secara khusus tentang bilangan nombor itu sendiri, dan bukan simbol. Walau bagaimanapun, dalam perkara berikut, demi ringkasnya, saya akan sering menggunakan perkataan "simbol", membayangkan istilah "titik kod".
Pesawat Unicode. Seperti yang anda lihat, kebanyakannya (pesawat 4 hingga 13) masih tidak digunakan.
Apa yang paling luar biasa ialah semua "pulpa" utama terletak pada satah sifar, ia dipanggil "Bidang Pelbagai Bahasa Asas". Jika baris mengandungi teks dalam salah satu bahasa moden (termasuk bahasa Cina), anda tidak akan melampaui satah ini. Tetapi anda tidak boleh memotong seluruh Unicode sama ada - contohnya, emoji terletak terutamanya di hujung pesawat seterusnya,"Satah Berbilang Bahasa Tambahan"(ia bermula dari 0x10000 kepada 0x1FFFF). Jadi UTF-16 melakukan ini: semua aksara termasuk dalam Bidang Pelbagai Bahasa Asas, dikodkan "seadanya" dengan nombor dua bait yang sepadan. Walau bagaimanapun, beberapa nombor dalam julat ini tidak menunjukkan aksara tertentu sama sekali, tetapi menunjukkan bahawa selepas pasangan bait ini kita perlu mempertimbangkan satu lagi - dengan menggabungkan nilai empat bait ini bersama-sama, kita mendapat nombor yang meliputi keseluruhan julat Unicode yang sah. Idea ini dipanggil "pasangan pengganti"βanda mungkin pernah mendengar tentang mereka.
Jadi UTF-16 memerlukan dua atau (dalam kes yang jarang berlaku) empat bait setiap "titik kod". Ini lebih baik daripada menggunakan empat bait sepanjang masa, tetapi Latin (dan aksara ASCII lain) apabila dikodkan dengan cara ini membazir separuh ruang pada sifar. UTF-8 direka bentuk untuk membetulkan ini: ASCII di dalamnya menduduki, seperti sebelumnya, hanya satu bait; kod daripada 0x80 kepada 0x7FF - dua bait; daripada 0x800 kepada 0xFFFF - tiga, dan daripada 0x10000 kepada 0x10FFFF - empat. Di satu pihak, abjad Latin telah menjadi baik: keserasian dengan ASCII telah kembali, dan pengedaran lebih sekata "tersebar" dari 1 hingga 4 bait. Tetapi abjad selain daripada Latin, malangnya, tidak mendapat manfaat dalam apa jua cara berbanding dengan UTF-16, dan kebanyakannya kini memerlukan tiga bait dan bukannya dua - julat yang diliputi oleh rekod dua bait telah mengecil sebanyak 32 kali, dengan 0xFFFF kepada 0x7FF, dan Cina mahupun, sebagai contoh, bahasa Georgia tidak termasuk di dalamnya. Cyrillic dan lima abjad lain - hore - bertuah, 2 bait setiap aksara.
Mengapa ini berlaku? Mari lihat bagaimana UTF-8 mewakili kod aksara:
Secara langsung untuk mewakili nombor, bit yang ditanda dengan simbol digunakan di sini x. Ia boleh dilihat bahawa dalam rekod dua bait hanya terdapat 11 bit tersebut (daripada 16). Bit terkemuka di sini hanya mempunyai fungsi tambahan. Dalam kes rekod empat bait, 21 daripada 32 bit diperuntukkan untuk nombor titik kod - nampaknya tiga bait (yang memberikan jumlah 24 bit) akan mencukupi, tetapi penanda perkhidmatan memakan terlalu banyak.
Adakah ini teruk? Tidak juga. Di satu pihak, jika kita sangat mengambil berat tentang ruang, kita mempunyai algoritma pemampatan yang boleh menghapuskan semua entropi dan redundansi tambahan dengan mudah. Sebaliknya, matlamat Unicode adalah untuk menyediakan pengekodan paling universal yang mungkin. Sebagai contoh, kita boleh mempercayakan baris yang dikodkan dalam UTF-8 kepada kod yang sebelum ini hanya berfungsi dengan ASCII, dan jangan takut ia akan melihat aksara daripada julat ASCII yang sebenarnya tidak ada (lagipun, dalam UTF-8 semua bait bermula dengan dari bit sifar - ini adalah ASCII). Dan jika kita tiba-tiba ingin memotong ekor kecil dari rentetan besar tanpa menyahkodnya dari awal lagi (atau memulihkan sebahagian maklumat selepas bahagian yang rosak), mudah untuk kita mencari offset di mana watak bermula (cukuplah untuk melangkau bait yang mempunyai sedikit awalan 10).
Mengapa kemudian mencipta sesuatu yang baru?
Pada masa yang sama, kadangkala terdapat situasi apabila algoritma pemampatan seperti kempis tidak dapat digunakan dengan baik, tetapi anda ingin mencapai penyimpanan rentetan padat. Secara peribadi, saya menghadapi masalah ini apabila memikirkan tentang membina untuk kamus besar termasuk perkataan dalam bahasa arbitrari. Di satu pihak, setiap perkataan sangat pendek, jadi memampatkannya akan menjadi tidak berkesan. Sebaliknya, pelaksanaan pepohon yang saya pertimbangkan telah direka bentuk supaya setiap bait rentetan yang disimpan menjana puncak pokok yang berasingan, jadi meminimumkan bilangannya adalah sangat berguna. Di perpustakaan saya (Seperti dalam , di mana ia berasaskan) masalah yang sama boleh diselesaikan dengan mudah - rentetan yang dibungkus ke dalam -kamus, disimpan di sana . Tetapi, seperti yang mudah difahami, ini berfungsi dengan baik hanya untuk abjad terhad - baris dalam bahasa Cina tidak boleh ditambah pada kamus sedemikian.
Secara berasingan, saya ingin ambil perhatian satu lagi nuansa yang tidak menyenangkan yang timbul apabila menggunakan UTF-8 dalam struktur data sedemikian. Gambar di atas menunjukkan bahawa apabila aksara ditulis sebagai dua bait, bit yang berkaitan dengan nombornya tidak datang berturut-turut, tetapi dipisahkan oleh sepasang bit. 10 di tengah: 110xxxxx 10xxxxxx. Oleh sebab itu, apabila 6 bit bawah bait kedua melimpah dalam kod aksara (iaitu, peralihan berlaku 10111111 β 10000000), maka bait pertama juga berubah. Ternyata huruf "p" dilambangkan dengan bait 0xD0 0xBF, dan βrβ seterusnya sudah pun 0xD1 0x80. Dalam pepohon awalan, ini membawa kepada pemisahan nod induk kepada dua - satu untuk awalan 0xD0, dan satu lagi untuk 0xD1 (walaupun keseluruhan abjad Cyrillic boleh dikodkan hanya dengan bait kedua).
Apa yang saya dapat
Menghadapi masalah ini, saya memutuskan untuk berlatih bermain permainan dengan bit, dan pada masa yang sama membiasakan diri dengan struktur Unicode secara keseluruhan. Hasilnya ialah format pengekodan UTF-C ("C" untuk padat), yang membelanjakan tidak lebih daripada 3 bait setiap titik kod, dan selalunya membenarkan anda berbelanja sahaja satu bait tambahan untuk keseluruhan baris yang dikodkan. Ini membawa kepada fakta bahawa pada banyak abjad bukan ASCII pengekodan sedemikian ternyata 30-60% lebih padat daripada UTF-8.
Saya telah membentangkan contoh pelaksanaan algoritma pengekodan dan penyahkodan dalam bentuk , anda boleh menggunakannya secara bebas dalam kod anda. Tetapi saya masih akan menekankan bahawa dalam erti kata lain format ini kekal sebagai "basikal", dan saya tidak mengesyorkan menggunakannya tanpa menyedari mengapa anda memerlukannya. Ini masih lebih kepada percubaan daripada "penambahbaikan UTF-8" yang serius. Namun begitu, kod di sana ditulis dengan kemas, padat, dengan sejumlah besar komen dan liputan ujian.
Keputusan ujian dan perbandingan dengan UTF-8
saya pun buat , di mana anda boleh menilai prestasi algoritma, dan kemudian saya akan memberitahu anda lebih lanjut tentang prinsip dan proses pembangunannya.
Menghapuskan bit berlebihan
Saya mengambil UTF-8 sebagai asas, sudah tentu. Perkara pertama dan paling jelas yang boleh diubah di dalamnya ialah mengurangkan bilangan bit perkhidmatan dalam setiap bait. Sebagai contoh, bait pertama dalam UTF-8 sentiasa bermula dengan sama ada 0, atau dengan 11 - awalan 10 Hanya bait berikut yang memilikinya. Mari kita gantikan awalan 11 pada 1, dan untuk bait seterusnya kami akan mengalih keluar awalan sepenuhnya. Apa yang akan berlaku?
0xxxxxxx β 1 bait
10xxxxxx xxxxxxxx - 2 bait
110xxxxx xxxxxxxx xxxxxxxx - 3 bait
Tunggu, di manakah rekod empat bait? Tetapi ia tidak lagi diperlukan - apabila menulis dalam tiga bait, kita kini mempunyai 21 bit yang tersedia dan ini mencukupi untuk semua nombor sehingga 0x10FFFF.
Apa yang telah kita korbankan di sini? Perkara yang paling penting ialah pengesanan sempadan watak dari lokasi sewenang-wenangnya dalam penimbal. Kita tidak boleh menunjuk pada bait sewenang-wenangnya dan mencari permulaan aksara seterusnya daripadanya. Ini adalah had format kami, tetapi dalam amalan ini jarang diperlukan. Kami biasanya dapat menjalankan penampan dari awal (terutamanya apabila ia berkaitan dengan garis pendek).
Keadaan dengan meliputi bahasa dengan 2 bait juga telah menjadi lebih baik: kini format dua bait memberikan julat 14 bit, dan ini adalah kod sehingga 0x3FFF. Orang Cina tidak bernasib baik (watak mereka kebanyakannya terdiri daripada 0x4E00 kepada 0x9FFF), tetapi orang Georgia dan ramai orang lain lebih seronok - bahasa mereka juga sesuai dengan 2 bait setiap aksara.
Masukkan keadaan pengekod
Sekarang mari kita fikirkan tentang sifat garis itu sendiri. Kamus paling kerap mengandungi perkataan yang ditulis dalam aksara abjad yang sama, dan ini juga berlaku untuk banyak teks lain. Adalah baik untuk menunjukkan abjad ini sekali, dan kemudian menunjukkan hanya nombor huruf di dalamnya. Mari lihat sama ada susunan aksara dalam jadual Unicode akan membantu kita.
Seperti yang dinyatakan di atas, Unicode terbahagi kepada kapal terbang 65536 kod setiap satu. Tetapi ini bukan bahagian yang sangat berguna (seperti yang telah dikatakan, selalunya kita berada dalam satah sifar). Lebih menarik ialah pembahagian oleh blok. Julat ini tidak lagi mempunyai panjang tetap, dan lebih bermakna - sebagai peraturan, setiap satu menggabungkan aksara daripada abjad yang sama.
Blok yang mengandungi aksara abjad Bengali. Malangnya, atas sebab sejarah, ini adalah contoh pembungkusan yang tidak begitu padat - 96 aksara bertaburan secara huru-hara di 128 titik kod blok.
Permulaan blok dan saiznya sentiasa gandaan 16 - ini dilakukan semata-mata untuk kemudahan. Di samping itu, banyak blok bermula dan berakhir pada nilai yang gandaan 128 atau 256 - contohnya, abjad Cyrillic asas mengambil 256 bait daripada 0x0400 kepada 0x04FF. Ini agak mudah: jika kita menyimpan awalan sekali 0x04, maka sebarang aksara Cyrillic boleh ditulis dalam satu bait. Benar, dengan cara ini kita akan kehilangan peluang untuk kembali ke ASCII (dan kepada mana-mana watak lain secara umum). Oleh itu kami melakukan ini:
- Dua bait
10yyyyyy yxxxxxxxbukan sahaja menandakan simbol dengan nomboryyyyyy yxxxxxxx, tetapi juga berubah abjad semasa padayyyyyy y0000000(iaitu kita mengingati semua bit kecuali yang paling tidak penting 7 bit); - Satu bait
0xxxxxxxini adalah watak abjad semasa. Ia hanya perlu ditambahkan pada ofset yang kami ingat dalam langkah 1. Walaupun kami tidak menukar abjad, offset adalah sifar, jadi kami mengekalkan keserasian dengan ASCII.
Begitu juga untuk kod yang memerlukan 3 bait:
- Tiga bait
110yyyyy yxxxxxxx xxxxxxxxmenunjukkan simbol dengan nomboryyyyyy yxxxxxxx xxxxxxxx, ubah abjad semasa padayyyyyy y0000000 00000000(teringat segala-galanya kecuali yang lebih muda 15 bit), dan tandai kotak yang kita ada sekarang panjang mod (apabila menukar abjad kembali kepada abjad dua bait, kami akan menetapkan semula bendera ini); - Dua bait
0xxxxxxx xxxxxxxxdalam mod panjang ia adalah watak abjad semasa. Begitu juga, kami menambahnya dengan offset dari langkah 1. Satu-satunya perbezaan ialah sekarang kami membaca dua bait (kerana kami beralih kepada mod ini).
Bunyinya bagus: sekarang sementara kami perlu mengekod aksara daripada julat Unicode 7-bit yang sama, kami membelanjakan 1 bait tambahan pada permulaan dan sejumlah satu bait bagi setiap aksara.
Bekerja dari salah satu versi terdahulu. Ia sudah sering mengalahkan UTF-8, tetapi masih ada ruang untuk penambahbaikan.
Apa yang lebih teruk? Pertama, kita mempunyai syarat, iaitu abjad semasa mengimbangi dan kotak semak mod panjang. Ini mengehadkan kami lagi: kini aksara yang sama boleh dikodkan secara berbeza dalam konteks yang berbeza. Mencari subrentetan, sebagai contoh, perlu dilakukan dengan mengambil kira perkara ini, dan bukan hanya dengan membandingkan bait. Kedua, sebaik sahaja kami menukar abjad, ia menjadi buruk dengan pengekodan aksara ASCII (dan ini bukan sahaja abjad Latin, tetapi juga tanda baca asas, termasuk ruang) - mereka memerlukan menukar abjad sekali lagi kepada 0, iaitu, sekali lagi bait tambahan (dan kemudian satu lagi untuk kembali ke titik utama kami).
Satu abjad adalah baik, dua lebih baik
Mari cuba ubah sedikit awalan bit kami, masukkan satu lagi kepada tiga yang diterangkan di atas:
0xxxxxxx β 1 bait dalam mod biasa, 2 dalam mod panjang
11xxxxxx β 1 bait
100xxxxx xxxxxxxx - 2 bait
101xxxxx xxxxxxxx xxxxxxxx - 3 bait
Kini dalam rekod dua bait terdapat satu bit yang kurang tersedia - mata kod sehingga 0x1FFFDan tidak 0x3FFF. Walau bagaimanapun, ia masih ketara lebih besar daripada dalam kod dua bait UTF-8, kebanyakan bahasa biasa masih sesuai, kehilangan yang paling ketara telah hilang ΠΈ , orang Jepun sedih.
Apakah kod baharu ini? 11xxxxxx? Ini adalah "simpanan" kecil bersaiz 64 aksara, ia melengkapkan abjad utama kami, jadi saya memanggilnya tambahan (pembantu) abjad. Apabila kita menukar abjad semasa, sekeping abjad lama menjadi tambahan. Sebagai contoh, kami bertukar daripada ASCII kepada Cyrillic - simpanan kini mengandungi 64 aksara yang mengandungi Abjad Latin, nombor, ruang dan koma (sisipan paling kerap dalam teks bukan ASCII). Beralih kembali kepada ASCII - dan bahagian utama abjad Cyrillic akan menjadi abjad tambahan.
Terima kasih kepada akses kepada dua abjad, kami boleh mengendalikan sejumlah besar teks dengan kos minimum untuk menukar abjad (tanda baca selalunya akan membawa kepada kembali ke ASCII, tetapi selepas itu kami akan mendapat banyak aksara bukan ASCII daripada abjad tambahan, tanpa bertukar semula).
Bonus: awalan sub-abjad 11xxxxxx dan memilih offset awalnya untuk menjadi 0xC0, kami mendapat keserasian separa dengan CP1252. Dalam erti kata lain, banyak (tetapi bukan semua) teks Eropah Barat yang dikodkan dalam CP1252 akan kelihatan sama dalam UTF-C.
Di sini, bagaimanapun, kesukaran timbul: bagaimana untuk mendapatkan tambahan dari abjad utama? Anda boleh meninggalkan offset yang sama, tetapi - sayangnya - di sini struktur Unicode sudah bermain menentang kami. Selalunya bahagian utama abjad bukan pada permulaan blok (contohnya, ibu kota Rusia "A" mempunyai kod 0x0410, walaupun blok Cyrillic bermula dengan 0x0400). Oleh itu, setelah memasukkan 64 aksara pertama ke dalam simpanan, kita mungkin kehilangan akses kepada bahagian ekor abjad.
Untuk menyelesaikan masalah ini, saya secara manual melalui beberapa blok yang sepadan dengan bahasa yang berbeza, dan menentukan offset abjad tambahan dalam blok utama untuk mereka. Abjad Latin, sebagai pengecualian, biasanya disusun semula seperti base64.
Sentuhan akhir
Akhirnya mari kita fikirkan di mana lagi kita boleh memperbaiki sesuatu.
Perhatikan bahawa format 101xxxxx xxxxxxxx xxxxxxxx membolehkan anda mengekod nombor sehingga 0x1FFFFF, dan Unicode berakhir lebih awal, pada 0x10FFFF. Dalam erti kata lain, titik kod terakhir akan diwakili sebagai 10110000 11111111 11111111. Oleh itu, kita boleh mengatakan bahawa jika bait pertama adalah dalam bentuk 1011xxxx (di mana xxxx lebih besar daripada 0), maka ia bermakna sesuatu yang lain. Sebagai contoh, anda boleh menambah 15 aksara lagi di sana yang sentiasa tersedia untuk pengekodan dalam satu bait, tetapi saya memutuskan untuk melakukannya secara berbeza.
Mari kita lihat blok Unicode yang memerlukan tiga bait sekarang. Pada asasnya, seperti yang telah disebutkan, ini adalah aksara Cina - tetapi sukar untuk melakukan apa-apa dengan mereka, terdapat 21 ribu daripadanya. Tetapi hiragana dan katakana juga terbang ke sana - dan jumlahnya tidak begitu banyak lagi, kurang daripada dua ratus. Dan, kerana kita teringat orang Jepun, terdapat juga emoji (sebenarnya, ia bertaburan di banyak tempat dalam Unicode, tetapi blok utama berada dalam julat 0x1F300 - 0x1FBFF). Jika anda berfikir tentang hakikat bahawa kini terdapat emoji yang dipasang dari beberapa titik kod sekaligus (contohnya, emoji βββ terdiri daripada sebanyak 7 kod!), maka ia menjadi memalukan untuk menghabiskan tiga bait pada setiap satu (7Γ3 = 21 bait demi satu ikon, mimpi ngeri).
Oleh itu, kami memilih beberapa julat terpilih yang sepadan dengan emoji, hiragana dan katakana, menomborkannya semula ke dalam satu senarai berterusan dan mengekodnya sebagai dua bait dan bukannya tiga:
1011xxxx xxxxxxxx
Hebat: emoji yang disebutkan di atas, yang terdiri daripada 7 titik kod, mengambil 8 bait dalam UTF-25, dan kami memasukkannya ke dalamnya 14 (tepat dua bait untuk setiap titik kod). Dengan cara ini, Habr enggan mencernanya (baik dalam editor lama dan dalam editor baru), jadi saya terpaksa memasukkannya dengan gambar.
Mari cuba selesaikan satu lagi masalah. Seperti yang kita ingat, abjad asas pada asasnya adalah tinggi 6 bit, yang kami ingat dan lekatkan pada kod setiap simbol yang dinyahkod seterusnya. Dalam kes aksara Cina yang berada dalam blok 0x4E00 - 0x9FFF, ini sama ada bit 0 atau 1. Ini tidak begitu mudah: kita perlu sentiasa menukar abjad antara dua nilai ini (iaitu menghabiskan tiga bait). Tetapi ambil perhatian bahawa dalam mod panjang, dari kod itu sendiri kita boleh menolak bilangan aksara yang kita kodkan menggunakan mod pendek (selepas semua helah yang diterangkan di atas, ini adalah 10240) - maka julat hieroglif akan beralih ke 0x2600 - 0x77FF, dan dalam kes ini, sepanjang julat keseluruhan ini, 6 bit yang paling ketara (daripada 21) akan bersamaan dengan 0. Oleh itu, jujukan hieroglif akan menggunakan dua bait setiap hieroglif (yang optimum untuk julat yang begitu besar), tanpa menyebabkan suis abjad.
Penyelesaian alternatif: SCSU, BOCU-1
Pakar Unicode, baru sahaja membaca tajuk artikel, kemungkinan besar akan segera mengingatkan anda bahawa secara langsung antara standard Unicode terdapat (SCSU), yang menerangkan kaedah pengekodan yang hampir sama dengan yang diterangkan dalam artikel.
Saya mengakui secara jujur: Saya mengetahui tentang kewujudannya hanya selepas saya tenggelam dalam menulis keputusan saya. Sekiranya saya mengetahuinya dari awal, saya mungkin akan cuba menulis pelaksanaan dan bukannya datang dengan pendekatan saya sendiri.
Apa yang menarik ialah SCSU menggunakan idea yang hampir sama dengan idea yang saya hasilkan sendiri (bukannya konsep "abjad" mereka menggunakan "tetingkap", dan terdapat lebih banyak daripada mereka yang tersedia daripada yang saya ada). Pada masa yang sama, format ini juga mempunyai kelemahan: ia lebih dekat sedikit dengan algoritma pemampatan daripada pengekodan. Khususnya, piawaian memberikan banyak kaedah perwakilan, tetapi tidak mengatakan cara memilih yang optimum - untuk ini, pengekod mesti menggunakan beberapa jenis heuristik. Oleh itu, pengekod SCSU yang menghasilkan pembungkusan yang baik akan menjadi lebih kompleks dan lebih rumit daripada algoritma saya.
Sebagai perbandingan, saya memindahkan pelaksanaan SCSU yang agak mudah ke JavaScript - dari segi volum kod ternyata setanding dengan UTF-C saya, tetapi dalam beberapa kes hasilnya berpuluh-puluh peratus lebih teruk (kadangkala ia mungkin melebihinya, tetapi tidak banyak). Sebagai contoh, teks dalam bahasa Ibrani dan Yunani telah dikodkan oleh UTF-C 60% lebih baik daripada SCSU (mungkin disebabkan abjad padat mereka).
Secara berasingan, saya akan menambah bahawa selain SCSU terdapat juga cara lain untuk mewakili Unicode secara padat - , tetapi ia bertujuan untuk keserasian MIME (yang saya tidak perlukan) dan mengambil pendekatan yang sedikit berbeza untuk pengekodan. Saya tidak menilai keberkesanannya, tetapi nampaknya saya tidak mungkin lebih tinggi daripada SCSU.
Kemungkinan penambahbaikan
Algoritma yang saya bentangkan tidak universal mengikut reka bentuk (ini mungkin di mana matlamat saya paling berbeza daripada matlamat Konsortium Unicode). Saya telah menyebut bahawa ia dibangunkan terutamanya untuk satu tugas (menyimpan kamus berbilang bahasa dalam pokok awalan), dan beberapa cirinya mungkin tidak sesuai untuk tugas lain. Tetapi hakikat bahawa ia bukan standard boleh menjadi tambahan - anda boleh mengubah suainya dengan mudah mengikut keperluan anda.
Sebagai contoh, dengan cara yang jelas anda boleh menyingkirkan kehadiran keadaan, membuat pengekodan tanpa kewarganegaraan - cuma jangan kemas kini pembolehubah offs, auxOffs ΠΈ is21Bit dalam pengekod dan penyahkod. Dalam kes ini, tidak mungkin untuk membungkus jujukan aksara abjad yang sama dengan berkesan, tetapi akan ada jaminan bahawa aksara yang sama sentiasa dikodkan dengan bait yang sama, tanpa mengira konteksnya.
Di samping itu, anda boleh menyesuaikan pengekod kepada bahasa tertentu dengan menukar keadaan lalai - contohnya, memfokuskan pada teks Rusia, tetapkan pengekod dan penyahkod pada permulaan offs = 0x0400 ΠΈ auxOffs = 0. Ini amat masuk akal dalam kes mod tanpa kewarganegaraan. Secara umum, ini akan serupa dengan menggunakan pengekodan lapan bit lama, tetapi tanpa mengalih keluar keupayaan untuk memasukkan aksara daripada semua Unicode seperti yang diperlukan.
Kelemahan lain yang dinyatakan sebelum ini ialah dalam teks besar yang dikodkan dalam UTF-C tidak ada cara cepat untuk mencari sempadan aksara yang paling hampir dengan bait sewenang-wenangnya. Jika anda memotong yang terakhir, katakan, 100 bait daripada penimbal yang dikodkan, anda berisiko mendapat sampah yang anda tidak boleh berbuat apa-apa dengannya. Pengekodan tidak direka untuk menyimpan log berbilang gigabait, tetapi secara umum ini boleh diperbetulkan. Bait 0xBF tidak boleh muncul sebagai bait pertama (tetapi mungkin bait kedua atau ketiga). Oleh itu, apabila pengekodan, anda boleh memasukkan urutan 0xBF 0xBF 0xBF setiap, katakan, 10 KB - maka, jika anda perlu mencari sempadan, cukup untuk mengimbas bahagian yang dipilih sehingga penanda serupa ditemui. Mengikuti yang terakhir 0xBF dijamin sebagai permulaan watak. (Apabila penyahkodan, jujukan tiga bait ini, sudah tentu, perlu diabaikan.)
Merumuskan
Jika anda telah membaca sejauh ini, tahniah! Saya harap anda, seperti saya, mempelajari sesuatu yang baharu (atau menyegarkan ingatan anda) tentang struktur Unicode.
Halaman demo. Contoh bahasa Ibrani menunjukkan kelebihan berbanding UTF-8 dan SCSU.
Penyelidikan yang diterangkan di atas tidak boleh dianggap sebagai pencerobohan piawaian. Walau bagaimanapun, saya secara amnya berpuas hati dengan hasil kerja saya, jadi saya gembira dengan mereka : sebagai contoh, perpustakaan JS yang dikecilkan hanya seberat 1710 bait (dan sudah tentu tidak mempunyai kebergantungan). Seperti yang saya nyatakan di atas, karya beliau boleh didapati di (terdapat juga satu set teks yang boleh dibandingkan dengan UTF-8 dan SCSU).
Akhir sekali, saya akan sekali lagi menarik perhatian kepada kes-kes di mana UTF-C digunakan tidak berbaloi:
- Jika baris anda cukup panjang (dari 100-200 aksara). Dalam kes ini, anda harus memikirkan tentang menggunakan algoritma pemampatan seperti kempis.
- Jika kamu perlu Ketelusan ASCII, iaitu, adalah penting bagi anda bahawa jujukan yang dikodkan tidak mengandungi kod ASCII yang tiada dalam rentetan asal. Keperluan untuk ini boleh dielakkan jika, apabila berinteraksi dengan API pihak ketiga (contohnya, bekerja dengan pangkalan data), anda lulus hasil pengekodan sebagai set abstrak bait, dan bukan sebagai rentetan. Jika tidak, anda berisiko mendapat kelemahan yang tidak dijangka.
- Jika anda ingin dapat mencari sempadan aksara dengan cepat pada offset sewenang-wenangnya (contohnya, apabila sebahagian daripada garisan rosak). Ini boleh dilakukan, tetapi hanya dengan mengimbas baris dari awal (atau menggunakan pengubahsuaian yang diterangkan dalam bahagian sebelumnya).
- Jika anda perlu melakukan operasi dengan cepat pada kandungan rentetan (isih mereka, cari subrentetan di dalamnya, gabungkan). Ini memerlukan rentetan untuk dinyahkod dahulu, jadi UTF-C akan menjadi lebih perlahan daripada UTF-8 dalam kes ini (tetapi lebih pantas daripada algoritma pemampatan). Memandangkan rentetan yang sama sentiasa dikodkan dengan cara yang sama, perbandingan penyahkodan yang tepat tidak diperlukan dan boleh dilakukan berdasarkan bait demi bait.
Kini: pengguna menyiarkan graf yang menyerlahkan had kebolehgunaan UTF-C. Ia menunjukkan bahawa UTF-C adalah lebih cekap daripada algoritma pemampatan tujuan umum (variasi LZW) selagi rentetan yang dibungkus adalah lebih pendek ~140 aksara (walau bagaimanapun, saya perhatikan bahawa perbandingan dilakukan pada satu teks; untuk bahasa lain hasilnya mungkin berbeza).
Sumber: www.habr.com