Jika Anda seorang pengembang dan dihadapkan pada tugas memilih pengkodean, maka Unicode hampir selalu menjadi solusi yang tepat. Metode representasi spesifik bergantung pada konteksnya, tetapi paling sering ada jawaban universal di sini - UTF-8. Hal baiknya adalah memungkinkan Anda menggunakan semua karakter Unicode tanpa mengeluarkan uang terlalu banyak banyak byte dalam banyak kasus. Benar, untuk bahasa yang menggunakan lebih dari sekedar alfabet Latin, setidaknya “tidak terlalu banyak”. dua byte per karakter. Bisakah kita berbuat lebih baik tanpa kembali ke pengkodean prasejarah yang membatasi kita hanya pada 256 karakter yang tersedia?
Di bawah ini saya mengusulkan untuk membiasakan diri dengan upaya saya untuk menjawab pertanyaan ini dan menerapkan algoritma yang relatif sederhana yang memungkinkan Anda menyimpan baris dalam sebagian besar bahasa di dunia tanpa menambahkan redundansi yang ada di UTF-8.
Penafian. Saya akan segera membuat beberapa reservasi penting: solusi yang dijelaskan tidak ditawarkan sebagai pengganti universal untuk UTF-8, ini hanya cocok dalam daftar kasus yang sempit (lebih lanjut tentangnya di bawah), dan tidak boleh digunakan untuk berinteraksi dengan API pihak ketiga (yang bahkan tidak mengetahuinya). Paling sering, algoritma kompresi tujuan umum (misalnya, deflate) cocok untuk penyimpanan kompak data teks dalam jumlah besar. Selain itu, dalam proses pembuatan solusi saya, saya menemukan standar yang ada di Unicode itu sendiri, yang memecahkan masalah yang sama - ini agak lebih rumit (dan seringkali lebih buruk), tetapi tetap merupakan standar yang diterima, dan tidak hanya dimasukkan bersama-sama di lutut. Aku akan memberitahumu tentang dia juga.
Tentang Unicode dan UTF-8
Pertama, beberapa kata tentang apa itu Unicode и UTF-8.
Seperti yang Anda ketahui, pengkodean 8-bit dulunya populer. Dengan mereka, semuanya menjadi sederhana: 256 karakter dapat diberi nomor dengan angka dari 0 hingga 255, dan angka dari 0 hingga 255 jelas dapat direpresentasikan sebagai satu byte. Jika kita kembali ke awal, pengkodean ASCII sepenuhnya terbatas pada 7 bit, sehingga bit paling signifikan dalam representasi byte-nya adalah nol, dan sebagian besar pengkodean 8-bit kompatibel dengannya (hanya berbeda di bagian "atas" bagian, di mana bit paling signifikan adalah satu ).
Apa perbedaan Unicode dengan pengkodean tersebut dan mengapa begitu banyak representasi spesifik yang terkait dengannya - UTF-8, UTF-16 (BE dan LE), UTF-32? Mari kita selesaikan secara berurutan.
Standar dasar Unicode hanya menjelaskan korespondensi antara karakter (dan dalam beberapa kasus, masing-masing komponen karakter) dan nomornya. Dan ada banyak kemungkinan angka dalam standar ini - dari 0x00 untuk 0x10FFFF (1 buah). Jika kita ingin memasukkan angka dalam rentang tersebut ke dalam variabel, 114 atau 112 byte tidak akan cukup bagi kita. Dan karena prosesor kami tidak dirancang untuk bekerja dengan angka tiga byte, kami terpaksa menggunakan sebanyak 1 byte per karakter! Ini adalah UTF-2, tetapi justru karena “pemborosan” inilah format ini tidak populer.
Untungnya, urutan karakter dalam Unicode tidak acak. Seluruh set mereka dibagi menjadi 17 "pesawat", yang masing-masing berisi 65536 (0x10000) «poin kode" Konsep “titik kode” di sini sederhana saja nomor karakter, ditugaskan padanya oleh Unicode. Namun, seperti disebutkan di atas, di Unicode tidak hanya karakter individual yang diberi nomor, tetapi juga komponen dan tanda layanannya (dan terkadang tidak ada yang sesuai dengan nomor tersebut - mungkin untuk saat ini, tetapi bagi kami ini tidak begitu penting), jadi lebih tepat selalu berbicara secara spesifik tentang banyaknya angka itu sendiri, dan bukan simbolnya. Namun berikut ini, agar singkatnya, saya akan sering menggunakan kata “simbol”, yang menyiratkan istilah “titik kode”.
Pesawat Unicode. Seperti yang Anda lihat, sebagian besar (pesawat 4 sampai 13) masih belum terpakai.
Yang paling luar biasa adalah bahwa semua “bubur” utama terletak pada bidang nol, yang disebut "Bidang Multibahasa Dasar". Jika sebuah baris berisi teks dalam salah satu bahasa modern (termasuk Cina), Anda tidak akan melampaui bidang ini. Namun Anda juga tidak dapat memotong Unicode lainnya - misalnya, emoji sebagian besar terletak di akhir pesawat selanjutnya,"Pesawat Multibahasa Tambahan"(meluas dari 0x10000 untuk 0x1FFFF). Jadi UTF-16 melakukan ini: semua karakter termasuk di dalamnya Bidang Multibahasa Dasar, dikodekan “sebagaimana adanya” dengan nomor dua byte yang sesuai. Namun, beberapa angka dalam rentang ini tidak menunjukkan karakter tertentu sama sekali, tetapi menunjukkan bahwa setelah pasangan byte ini kita perlu mempertimbangkan karakter lain - dengan menggabungkan nilai keempat byte ini bersama-sama, kita mendapatkan nomor yang mencakup seluruh rentang Unicode yang valid. Ide ini disebut "pasangan pengganti" - Anda mungkin pernah mendengarnya.
Jadi UTF-16 memerlukan dua atau (dalam kasus yang sangat jarang) empat byte per "titik kode". Ini lebih baik daripada menggunakan empat byte sepanjang waktu, tetapi Latin (dan karakter ASCII lainnya) ketika dikodekan dengan cara ini menghabiskan separuh ruang pada angka nol. UTF-8 dirancang untuk memperbaiki hal ini: ASCII di dalamnya, seperti sebelumnya, hanya menempati satu byte; kode dari 0x80 untuk 0x7FF - dua byte; dari 0x800 untuk 0xFFFF - tiga, dan dari 0x10000 untuk 0x10FFFF - empat. Di satu sisi, alfabet Latin menjadi baik: kompatibilitas dengan ASCII telah kembali, dan distribusi “tersebar” lebih merata dari 1 hingga 4 byte. Namun alfabet selain Latin, sayangnya, tidak mendapatkan keuntungan apa pun dibandingkan dengan UTF-16, dan banyak yang sekarang memerlukan tiga byte, bukan dua - rentang yang dicakup oleh catatan dua byte telah menyempit sebanyak 32 kali lipat, dengan 0xFFFF untuk 0x7FF, dan baik orang Cina maupun, misalnya, orang Georgia tidak termasuk di dalamnya. Sirilik dan lima huruf lainnya - hore - beruntung, 2 byte per karakter.
Mengapa ini terjadi? Mari kita lihat bagaimana UTF-8 merepresentasikan kode karakter:
Langsung untuk merepresentasikan angka, bit yang ditandai dengan simbol digunakan di sini x. Terlihat bahwa dalam record dua byte hanya terdapat 11 bit tersebut (dari 16). Bit terdepan di sini hanya memiliki fungsi tambahan. Dalam kasus rekaman empat byte, 21 dari 32 bit dialokasikan untuk nomor titik kode - tampaknya tiga byte (yang menghasilkan total 24 bit) sudah cukup, tetapi penanda layanan memakan terlalu banyak.
Apakah ini buruk? Tidak terlalu. Di satu sisi, jika kita sangat peduli dengan ruang, kita memiliki algoritma kompresi yang dapat dengan mudah menghilangkan semua entropi dan redundansi ekstra. Di sisi lain, tujuan Unicode adalah menyediakan pengkodean yang paling universal. Misalnya, kita dapat mempercayakan baris yang dikodekan dalam UTF-8 ke kode yang sebelumnya hanya berfungsi dengan ASCII, dan tidak takut akan melihat karakter dari rentang ASCII yang sebenarnya tidak ada (lagipula, di UTF-8 semuanya byte dimulai dengan bit nol - inilah ASCII). Dan jika kita tiba-tiba ingin memotong ekor kecil dari string besar tanpa mendekodekannya dari awal (atau memulihkan sebagian informasi setelah bagian yang rusak), mudah bagi kita untuk menemukan offset di mana karakter dimulai (cukup untuk melewati byte yang memiliki awalan bit 10).
Lalu mengapa menciptakan sesuatu yang baru?
Pada saat yang sama, terkadang ada situasi ketika algoritme kompresi seperti deflate tidak dapat diterapkan dengan baik, tetapi Anda ingin mencapai penyimpanan string yang ringkas. Secara pribadi, saya mengalami masalah ini ketika memikirkan tentang membangun untuk kamus besar termasuk kata-kata dalam bahasa sewenang-wenang. Di satu sisi, setiap kata sangat pendek, sehingga mengompresinya tidak akan efektif. Di sisi lain, implementasi pohon yang saya pertimbangkan dirancang sedemikian rupa sehingga setiap byte dari string yang disimpan menghasilkan simpul pohon yang terpisah, jadi meminimalkan jumlahnya sangat berguna. Di perpustakaan saya (Seperti dalam , yang menjadi dasarnya) masalah serupa dapat diselesaikan dengan sederhana - string dimasukkan ke dalamnya -kamus, disimpan di sana . Namun, mudah dipahami, ini hanya berfungsi dengan baik untuk alfabet terbatas - satu baris dalam bahasa Mandarin tidak dapat ditambahkan ke kamus semacam itu.
Secara terpisah, saya ingin mencatat satu lagi nuansa tidak menyenangkan yang muncul saat menggunakan UTF-8 dalam struktur data seperti itu. Gambar di atas menunjukkan bahwa ketika suatu karakter ditulis sebagai dua byte, bit-bit yang berhubungan dengan nomornya tidak muncul secara berurutan, melainkan dipisahkan oleh sepasang bit. 10 di tengah-tengah: 110xxxxx 10xxxxxx. Oleh karena itu, ketika 6 bit terbawah dari byte kedua meluap dalam kode karakter (yaitu, terjadi transisi 10111111 → 10000000), maka byte pertama juga berubah. Ternyata huruf “p” dilambangkan dengan byte 0xD0 0xBF, dan “r” berikutnya sudah 0xD1 0x80. Dalam pohon awalan, hal ini menyebabkan pemisahan simpul induk menjadi dua - satu untuk awalan 0xD0, dan satu lagi untuk 0xD1 (walaupun seluruh alfabet Sirilik hanya dapat dikodekan dengan byte kedua).
Apa yang saya dapatkan
Menghadapi masalah ini, saya memutuskan untuk berlatih bermain game dengan bit, dan pada saat yang sama mengenal lebih baik struktur Unicode secara keseluruhan. Hasilnya adalah format pengkodean UTF-C ("C" untuk padat), yang menghabiskan tidak lebih dari 3 byte per titik kode, dan seringkali memungkinkan Anda untuk menghabiskannya saja satu byte tambahan untuk seluruh baris yang disandikan. Hal ini mengarah pada fakta bahwa pada banyak alfabet non-ASCII, pengkodean seperti itu ternyata terjadi 30-60% lebih ringkas dibandingkan UTF-8.
Saya telah menyajikan contoh implementasi algoritma pengkodean dan decoding dalam bentuk , Anda dapat dengan bebas menggunakannya dalam kode Anda. Namun saya tetap akan menekankan bahwa dalam arti tertentu format ini tetap menjadi “sepeda”, dan saya tidak menyarankan untuk menggunakannya tanpa menyadari mengapa Anda membutuhkannya. Ini masih lebih merupakan eksperimen daripada “perbaikan UTF-8” yang serius. Meskipun demikian, kode di sana ditulis dengan rapi, ringkas, dengan banyak komentar dan cakupan pengujian.
Hasil tes dan perbandingan dengan UTF-8
Saya juga melakukannya , di mana Anda dapat mengevaluasi kinerja algoritme, lalu saya akan memberi tahu Anda lebih banyak tentang prinsip dan proses pengembangannya.
Menghilangkan bit-bit yang berlebihan
Saya mengambil UTF-8 sebagai dasar, tentu saja. Hal pertama dan paling jelas yang dapat diubah di dalamnya adalah mengurangi jumlah bit layanan di setiap byte. Misalnya, byte pertama di UTF-8 selalu dimulai dengan salah satu dari keduanya 0, atau dengan 11 - awalan 10 Hanya byte berikut yang memilikinya. Mari kita ganti awalannya 11 pada 1, dan untuk byte berikutnya kami akan menghapus awalan sepenuhnya. Apa yang akan terjadi?
0xxxxxxx — 1 bita
10xxxxxx xxxxxxxx - 2 byte
110xxxxx xxxxxxxx xxxxxxxx - 3 byte
Tunggu, di mana rekaman empat bytenya? Tapi itu tidak lagi diperlukan - saat menulis dalam tiga byte, kami sekarang memiliki 21 bit yang tersedia dan ini cukup untuk semua angka hingga 0x10FFFF.
Apa yang telah kita korbankan di sini? Yang paling penting adalah deteksi batas karakter dari lokasi sembarang di buffer. Kita tidak dapat menunjuk pada byte sembarang dan menemukan awal karakter berikutnya darinya. Ini adalah batasan format kami, namun dalam praktiknya hal ini jarang diperlukan. Kami biasanya dapat menjalankan buffer dari awal (terutama jika menyangkut jalur pendek).
Situasi dengan bahasa yang mencakup 2 byte juga menjadi lebih baik: sekarang format dua byte memberikan rentang 14 bit, dan ini adalah kode hingga 0x3FFF. Orang Cina tidak beruntung (karakter mereka kebanyakan berkisar dari 0x4E00 untuk 0x9FFF), tetapi orang Georgia dan banyak orang lainnya lebih bersenang-senang - bahasa mereka juga muat dalam 2 byte per karakter.
Masukkan status pembuat enkode
Sekarang mari kita pikirkan tentang properti garis itu sendiri. Kamus paling sering berisi kata-kata yang ditulis dalam karakter alfabet yang sama, dan ini juga berlaku untuk banyak teks lainnya. Sebaiknya tunjukkan alfabet ini satu kali, lalu tunjukkan hanya nomor huruf di dalamnya. Mari kita lihat apakah susunan karakter dalam tabel Unicode akan membantu kita.
Seperti disebutkan di atas, Unicode dibagi menjadi pesawat terbang 65536 kode masing-masing. Tapi ini bukan pembagian yang sangat berguna (seperti yang telah dikatakan, paling sering kita berada di bidang nol). Yang lebih menarik adalah pembagiannya blok. Rentang ini tidak lagi memiliki panjang yang tetap, dan lebih bermakna - biasanya, masing-masing rentang menggabungkan karakter dari alfabet yang sama.
Sebuah blok yang berisi karakter alfabet Bengali. Sayangnya, karena alasan historis, ini adalah contoh kemasan yang tidak terlalu padat - 96 karakter tersebar secara acak di 128 titik kode blok.
Awal mula balok dan ukurannya selalu kelipatan 16 - ini dilakukan hanya untuk kenyamanan. Selain itu, banyak blok dimulai dan diakhiri dengan nilai kelipatan 128 atau bahkan 256 - misalnya, alfabet Sirilik dasar membutuhkan 256 byte dari 0x0400 untuk 0x04FF. Ini cukup mudah: jika kita menyimpan awalan satu kali 0x04, maka karakter Sirilik apa pun dapat ditulis dalam satu byte. Benar, dengan cara ini kita akan kehilangan kesempatan untuk kembali ke ASCII (dan karakter lain secara umum). Oleh karena itu kami melakukan ini:
- Dua byte
10yyyyyy yxxxxxxxtidak hanya melambangkan simbol dengan angkayyyyyy yxxxxxxx, tetapi juga berubah alfabet saat ini padayyyyyy y0000000(yaitu kita mengingat semua bagian kecuali bagian yang paling tidak signifikan 7 bit); - Satu byte
0xxxxxxxini adalah karakter alfabet saat ini. Itu hanya perlu ditambahkan ke offset yang kita ingat pada langkah 1. Meskipun kita tidak mengubah alfabet, offsetnya adalah nol, jadi kita tetap menjaga kompatibilitas dengan ASCII.
Begitu juga untuk kode yang membutuhkan 3 byte:
- Tiga byte
110yyyyy yxxxxxxx xxxxxxxxmenunjukkan simbol dengan angkayyyyyy yxxxxxxx xxxxxxxx, mengubah alfabet saat ini padayyyyyy y0000000 00000000(mengingat semuanya kecuali yang lebih muda 15 bit), dan centang kotak tempat kita berada sekarang panjang mode (saat mengubah alfabet kembali ke byte ganda, kami akan menyetel ulang tanda ini); - Dua byte
0xxxxxxx xxxxxxxxdalam mode panjang itu adalah karakter alfabet saat ini. Demikian pula, kita menambahkannya dengan offset dari langkah 1. Satu-satunya perbedaan adalah sekarang kita membaca dua byte (karena kita beralih ke mode ini).
Kedengarannya bagus: sekarang ketika kita perlu menyandikan karakter dari rentang Unicode 7-bit yang sama, kita menghabiskan 1 byte tambahan di awal dan total satu byte per karakter.
Bekerja dari salah satu versi sebelumnya. Ini sudah sering mengalahkan UTF-8, namun masih ada ruang untuk perbaikan.
Apa yang lebih buruk? Pertama, kita mempunyai syarat yaitu offset alfabet saat ini dan kotak centang modus panjang. Hal ini semakin membatasi kita: sekarang karakter yang sama dapat dikodekan secara berbeda dalam konteks berbeda. Pencarian substring, misalnya, harus dilakukan dengan mempertimbangkan hal ini, dan bukan hanya dengan membandingkan byte. Kedua, segera setelah kami mengubah alfabet, pengkodean karakter ASCII menjadi buruk (dan ini bukan hanya alfabet Latin, tetapi juga tanda baca dasar, termasuk spasi) - mereka memerlukan perubahan alfabet lagi ke 0, yaitu, lagi satu byte tambahan (dan satu byte lagi untuk kembali ke poin utama kita).
Satu alfabet bagus, dua alfabet lebih baik
Mari kita coba mengubah sedikit awalan bit kita, dengan memasukkan satu lagi dari tiga awalan yang dijelaskan di atas:
0xxxxxxx — 1 byte dalam mode normal, 2 dalam mode panjang
11xxxxxx — 1 bita
100xxxxx xxxxxxxx - 2 byte
101xxxxx xxxxxxxx xxxxxxxx - 3 byte
Sekarang dalam catatan dua byte ada satu bit yang tersedia lebih sedikit - kode menunjuk ke atas 0x1FFFDan tidak 0x3FFF. Namun, ini masih terasa lebih besar daripada kode UTF-8 byte ganda, sebagian besar bahasa umum masih dapat digunakan, kerugian yang paling nyata telah hilang и , orang Jepang sedih.
Apa kode baru ini? 11xxxxxx? Ini adalah "simpanan" kecil berukuran 64 karakter, melengkapi alfabet utama kita, jadi saya menyebutnya tambahan (bantu) alfabet. Saat kita mengganti alfabet saat ini, bagian dari alfabet lama menjadi tambahan. Misalnya, kami beralih dari ASCII ke Cyrillic - simpanan sekarang berisi 64 karakter Alfabet Latin, angka, spasi dan koma (penyisipan paling sering dalam teks non-ASCII). Beralih kembali ke ASCII - dan bagian utama alfabet Sirilik akan menjadi alfabet tambahan.
Berkat akses ke dua alfabet, kami dapat menangani sejumlah besar teks dengan biaya minimal untuk berpindah alfabet (tanda baca paling sering menyebabkan kembali ke ASCII, tetapi setelah itu kami akan mendapatkan banyak karakter non-ASCII dari alfabet tambahan, tanpa beralih lagi).
Bonus: memberi awalan pada sub-abjad 11xxxxxx dan memilih offset awalnya 0xC0, kami mendapatkan kompatibilitas parsial dengan CP1252. Dengan kata lain, banyak (tetapi tidak semua) teks Eropa Barat yang dikodekan dalam CP1252 akan terlihat sama dalam UTF-C.
Namun di sini timbul kesulitan: bagaimana cara mendapatkan alfabet tambahan dari alfabet utama? Anda dapat membiarkan offset yang sama, tetapi - sayangnya - di sini struktur Unicode sudah merugikan kita. Seringkali bagian utama alfabet tidak berada di awal blok (misalnya, huruf kapital Rusia “A” memiliki kode 0x0410, meskipun blok Sirilik dimulai dengan 0x0400). Jadi, setelah memasukkan 64 karakter pertama ke dalam simpanan, kita mungkin kehilangan akses ke bagian ekor alfabet.
Untuk memperbaiki masalah ini, saya secara manual menelusuri beberapa blok yang sesuai dengan bahasa berbeda, dan menentukan offset alfabet tambahan dalam blok utama untuk blok tersebut. Alfabet Latin, sebagai pengecualian, umumnya disusun ulang seperti base64.
Sentuhan terakhir
Mari kita pikirkan di mana lagi kita bisa meningkatkan sesuatu.
Perhatikan bahwa formatnya 101xxxxx xxxxxxxx xxxxxxxx memungkinkan Anda menyandikan angka hingga 0x1FFFFF, dan Unicode berakhir lebih awal, pada 0x10FFFF. Dengan kata lain, titik kode terakhir akan direpresentasikan sebagai 10110000 11111111 11111111. Oleh karena itu, kita dapat mengatakan bahwa jika byte pertama berbentuk 1011xxxx (di mana xxxx lebih besar dari 0), maka artinya lain. Misalnya, Anda dapat menambahkan 15 karakter lain di sana yang selalu tersedia untuk pengkodean dalam satu byte, tetapi saya memutuskan untuk melakukannya secara berbeda.
Mari kita lihat blok Unicode yang membutuhkan tiga byte sekarang. Pada dasarnya, seperti yang telah disebutkan, ini adalah karakter Cina - tetapi sulit untuk melakukan apa pun dengannya, ada 21 ribu karakter. Tapi hiragana dan katakana juga terbang ke sana - dan jumlahnya tidak banyak lagi, kurang dari dua ratus. Dan, karena kita ingat bahasa Jepang, ada juga emoji (sebenarnya tersebar di banyak tempat di Unicode, tetapi blok utamanya ada dalam jangkauan. 0x1F300 - 0x1FBFF). Kalau dipikir-pikir sekarang sudah ada emoji yang dirangkai dari beberapa titik kode sekaligus (misalnya emoji terdiri dari sebanyak 7 kode!), maka sangat disayangkan menghabiskan tiga byte untuk masing-masing kode (7×3 = 21 byte demi satu ikon, mimpi buruk).
Oleh karena itu, kami memilih beberapa rentang yang dipilih sesuai dengan emoji, hiragana, dan katakana, menomori ulang rentang tersebut menjadi satu daftar berkelanjutan dan menyandikannya sebagai dua byte, bukan tiga:
1011xxxx xxxxxxxx
Hebat: emoji yang disebutkan di atas, terdiri dari 7 titik kode, membutuhkan 8 byte dalam UTF-25, dan kami memasukkannya ke dalamnya 14 (tepatnya dua byte untuk setiap titik kode). Ngomong-ngomong, Habr menolak mencernanya (baik di editor lama maupun di editor baru), jadi saya harus menyisipkannya dengan gambar.
Mari kita coba perbaiki satu masalah lagi. Seperti yang kita ingat, alfabet dasar pada dasarnya adalah tinggi 6 bit, yang kita ingat dan tempelkan pada kode setiap simbol yang diterjemahkan berikutnya. Dalam hal karakter Cina yang ada di blok 0x4E00 - 0x9FFF, ini bit 0 atau 1. Ini sangat tidak nyaman: kita harus terus-menerus mengganti alfabet di antara dua nilai ini (yaitu menghabiskan tiga byte). Namun perlu diingat bahwa dalam mode panjang, dari kode itu sendiri kita dapat mengurangi jumlah karakter yang kita kodekan menggunakan mode pendek (setelah semua trik yang dijelaskan di atas, ini adalah 10240) - maka rentang hieroglif akan bergeser ke 0x2600 - 0x77FF, dan dalam hal ini, di seluruh rentang ini, 6 bit paling signifikan (dari 21) akan sama dengan 0. Jadi, rangkaian hieroglif akan menggunakan dua byte per hieroglif (yang optimal untuk rentang sebesar itu), tanpa menyebabkan peralihan alfabet.
Solusi alternatif: SCSU, BOCU-1
Pakar Unicode, yang baru saja membaca judul artikel, kemungkinan besar akan segera mengingatkan Anda bahwa di antara standar Unicode ada (SCSU), yang menjelaskan metode pengkodean yang sangat mirip dengan yang dijelaskan dalam artikel.
Saya akui dengan jujur: Saya mengetahui keberadaannya hanya setelah saya benar-benar tenggelam dalam menulis keputusan saya. Seandainya saya mengetahuinya sejak awal, saya mungkin akan mencoba menulis implementasinya daripada membuat pendekatan saya sendiri.
Yang menarik adalah SCSU menggunakan ide-ide yang sangat mirip dengan ide-ide yang saya buat sendiri (alih-alih konsep "abjad", mereka menggunakan "jendela", dan lebih banyak yang tersedia daripada yang saya miliki). Pada saat yang sama, format ini juga memiliki kelemahan: format ini sedikit lebih mirip dengan algoritma kompresi daripada algoritma pengkodean. Secara khusus, standar ini memberikan banyak metode representasi, tetapi tidak menjelaskan bagaimana memilih yang optimal - untuk ini, pembuat enkode harus menggunakan semacam heuristik. Jadi, encoder SCSU yang menghasilkan kemasan yang baik akan lebih kompleks dan rumit daripada algoritma saya.
Sebagai perbandingan, saya mentransfer implementasi SCSU yang relatif sederhana ke JavaScript - dalam hal volume kode ternyata sebanding dengan UTF-C saya, tetapi dalam beberapa kasus hasilnya puluhan persen lebih buruk (terkadang mungkin melebihi itu, tapi tidak banyak). Misalnya, teks dalam bahasa Ibrani dan Yunani dikodekan oleh UTF-C 60% lebih baik dari SCSU (mungkin karena hurufnya yang kompak).
Secara terpisah, saya akan menambahkan bahwa selain SCSU, ada juga cara lain untuk merepresentasikan Unicode secara kompak - , tetapi ini bertujuan untuk kompatibilitas MIME (yang tidak saya perlukan) dan mengambil pendekatan pengkodean yang sedikit berbeda. Saya belum menilai keefektifannya, namun menurut saya kemungkinannya tidak akan lebih tinggi dari SCSU.
Kemungkinan perbaikan
Algoritme yang saya sajikan tidak dirancang secara universal (mungkin di sinilah tujuan saya paling berbeda dari tujuan Konsorsium Unicode). Saya telah menyebutkan bahwa ini dikembangkan terutama untuk satu tugas (menyimpan kamus multibahasa di pohon awalan), dan beberapa fiturnya mungkin tidak cocok untuk tugas lain. Namun fakta bahwa ini bukan standar dapat menjadi nilai tambah - Anda dapat dengan mudah memodifikasinya sesuai kebutuhan Anda.
Misalnya, dengan cara yang jelas Anda dapat menghilangkan keberadaan negara, membuat pengkodean tanpa kewarganegaraan - hanya saja, jangan perbarui variabel offs, auxOffs и is21Bit dalam encoder dan decoder. Dalam hal ini, tidak mungkin mengemas rangkaian karakter dari alfabet yang sama secara efektif, namun akan ada jaminan bahwa karakter yang sama selalu dikodekan dengan byte yang sama, apa pun konteksnya.
Selain itu, Anda dapat menyesuaikan encoder ke bahasa tertentu dengan mengubah status default - misalnya, berfokus pada teks Rusia, mengatur encoder dan decoder di awal offs = 0x0400 и auxOffs = 0. Hal ini terutama masuk akal dalam kasus mode tanpa kewarganegaraan. Secara umum, ini akan mirip dengan menggunakan pengkodean delapan-bit yang lama, tetapi tanpa menghilangkan kemampuan untuk memasukkan karakter dari semua Unicode sesuai kebutuhan.
Kelemahan lain yang disebutkan sebelumnya adalah bahwa dalam teks besar yang dikodekan dalam UTF-C tidak ada cara cepat untuk menemukan batas karakter yang paling dekat dengan byte sembarang. Jika Anda memotong yang terakhir, katakanlah, 100 byte dari buffer yang disandikan, Anda berisiko mendapatkan sampah yang tidak dapat Anda gunakan untuk melakukan apa pun. Pengkodean tidak dirancang untuk menyimpan log multi-gigabyte, tetapi secara umum hal ini dapat diperbaiki. byte 0xBF tidak boleh muncul sebagai byte pertama (tetapi mungkin byte kedua atau ketiga). Oleh karena itu, saat menyandikan, Anda dapat menyisipkan urutannya 0xBF 0xBF 0xBF setiap, katakanlah, 10 KB - maka, jika Anda perlu menemukan batas, cukup memindai bagian yang dipilih hingga penanda serupa ditemukan. Mengikuti yang terakhir 0xBF dijamin menjadi awal dari sebuah karakter. (Saat mendekode, urutan tiga byte ini tentu saja perlu diabaikan.)
Menyimpulkan
Jika Anda sudah membaca sejauh ini, selamat! Saya harap Anda, seperti saya, mempelajari sesuatu yang baru (atau menyegarkan ingatan Anda) tentang struktur Unicode.
Halaman demo. Contoh bahasa Ibrani menunjukkan keunggulan dibandingkan UTF-8 dan SCSU.
Penelitian yang dijelaskan di atas tidak boleh dianggap sebagai pelanggaran terhadap standar. Namun, secara umum saya puas dengan hasil pekerjaan saya, jadi saya senang dengan hasilnya : misalnya, perpustakaan JS yang diperkecil hanya berbobot 1710 byte (dan tentu saja tidak memiliki ketergantungan). Seperti yang saya sebutkan di atas, karyanya dapat ditemukan di (ada juga sekumpulan teks yang dapat dibandingkan dengan UTF-8 dan SCSU).
Terakhir, saya akan sekali lagi menarik perhatian pada kasus-kasus di mana UTF-C digunakan tidak layak:
- Jika baris Anda cukup panjang (100-200 karakter). Dalam hal ini, Anda harus mempertimbangkan untuk menggunakan algoritma kompresi seperti deflate.
- Jika Anda membutuhkannya transparansi ASCII, artinya, penting bagi Anda bahwa urutan yang dikodekan tidak berisi kode ASCII yang tidak ada dalam string aslinya. Kebutuhan akan hal ini dapat dihindari jika, saat berinteraksi dengan API pihak ketiga (misalnya, bekerja dengan database), Anda meneruskan hasil pengkodean sebagai kumpulan byte abstrak, dan bukan sebagai string. Jika tidak, Anda berisiko mendapatkan kerentanan yang tidak terduga.
- Jika Anda ingin dapat dengan cepat menemukan batas karakter pada offset yang berubah-ubah (misalnya, ketika sebagian garis rusak). Hal ini dapat dilakukan, tetapi hanya dengan memindai garis dari awal (atau menerapkan modifikasi yang dijelaskan pada bagian sebelumnya).
- Jika Anda perlu melakukan operasi cepat pada konten string (mengurutkannya, mencari substring di dalamnya, menggabungkannya). Hal ini memerlukan string untuk didekodekan terlebih dahulu, sehingga UTF-C akan lebih lambat dari UTF-8 dalam kasus ini (tetapi lebih cepat dari algoritma kompresi). Karena string yang sama selalu dikodekan dengan cara yang sama, perbandingan decoding yang tepat tidak diperlukan dan dapat dilakukan berdasarkan byte demi byte.
Update: pemakai memposting grafik yang menyoroti batas penerapan UTF-C. Hal ini menunjukkan bahwa UTF-C lebih efisien daripada algoritma kompresi tujuan umum (variasi dari LZW) selama string yang dikemas lebih pendek ~140 karakter (namun, saya perhatikan bahwa perbandingan dilakukan pada satu teks; untuk bahasa lain hasilnya mungkin berbeda).
Sumber: www.habr.com