Bir geliştiriciyseniz ve bir kodlama seçme göreviyle karşı karşıyaysanız, Unicode neredeyse her zaman doğru çözüm olacaktır. Spesifik temsil yöntemi bağlama bağlıdır, ancak çoğu zaman burada da evrensel bir cevap vardır - UTF-8. Bunun iyi yanı, tüm Unicode karakterlerini harcamadan kullanmanıza izin vermesidir. çok fazla çoğu durumda çok fazla bayt. Doğru, Latin alfabesinden fazlasını kullanan diller için "çok fazla değil" en azından karakter başına iki bayt. Bizi yalnızca 256 kullanılabilir karakterle sınırlayan tarih öncesi kodlamalara dönmeden daha iyisini yapabilir miyiz?
Aşağıda, bu soruyu yanıtlama girişimimi tanımanızı ve UTF-8'deki fazlalığı eklemeden dünyanın çoğu dilinde satırları saklamanıza olanak tanıyan nispeten basit bir algoritma uygulamanızı öneriyorum.
Sorumluluk reddi beyanı. Hemen birkaç önemli rezervasyon yapacağım: açıklanan çözüm UTF-8'in evrensel bir alternatifi olarak sunulmuyor, yalnızca dar bir vaka listesi için uygundur (bunlar hakkında daha fazla bilgi aşağıdadır) ve hiçbir durumda üçüncü taraf API'lerle (bunun hakkında bilgisi olmayanlar) etkileşimde bulunmak için kullanılmamalıdır. Çoğu zaman, genel amaçlı sıkıştırma algoritmaları (örneğin, deflate), büyük hacimli metin verilerinin kompakt bir şekilde depolanması için uygundur. Ek olarak, zaten çözümümü oluşturma sürecinde, Unicode'un kendisinde aynı sorunu çözen mevcut bir standart buldum - biraz daha karmaşıktır (ve genellikle daha kötüdür), ancak yine de kabul edilen bir standarttır ve sadece koymakla kalmaz birlikte diz üstünde. Size ondan da bahsedeceğim.
Unicode ve UTF-8 hakkında
Başlangıç olarak ne olduğu hakkında birkaç kelime Unicode и UTF-8.
Bildiğiniz gibi 8 bit kodlamalar eskiden popülerdi. Onlarla her şey basitti: 256 karakter, 0'dan 255'e kadar sayılarla numaralandırılabiliyor ve 0'dan 255'e kadar olan sayılar açıkça bir bayt olarak temsil edilebiliyor. En başa dönersek, ASCII kodlaması tamamen 7 bit ile sınırlıdır, dolayısıyla bayt gösterimindeki en önemli bit sıfırdır ve 8 bitlik kodlamaların çoğu onunla uyumludur (sadece "üst" kısımda farklılık gösterirler). en önemli bitin bir olduğu kısım).
Unicode'un bu kodlamalardan farkı nedir ve neden UTF-8, UTF-16 (BE ve LE), UTF-32 gibi bu kadar çok özel temsil onunla ilişkilidir? Sırasıyla çözelim.
Temel Unicode standardı yalnızca karakterler (ve bazı durumlarda karakterlerin ayrı ayrı bileşenleri) ile sayıları arasındaki yazışmayı açıklar. Ve bu standartta pek çok olası sayı var - 0x00 karşı 0x10FFFF (1 adet). Eğer bu kadar aralıktaki bir sayıyı bir değişkene koymak isteseydik ne 114 ne de 112 byte bize yeterli olurdu. Ve işlemcilerimiz üç baytlık sayılarla çalışacak şekilde tasarlanmadığından, karakter başına 1 bayta kadar kullanmak zorunda kalacağız! Bu UTF-2'dir, ancak tam da bu "israf" nedeniyle bu formatın popüler olmamasıdır.
Neyse ki Unicode'daki karakterlerin sırası rastgele değildir. Setlerinin tamamı 17'ye bölünmüştür "yüzeyleri", her biri 65536 içerir (0x10000) «kod noktaları" Buradaki “kod noktası” kavramı basitçe karakter numarası, Unicode tarafından kendisine atanmıştır. Ancak, yukarıda belirtildiği gibi, Unicode'da yalnızca bireysel karakterler değil, aynı zamanda bunların bileşenleri ve hizmet işaretleri de numaralandırılır (ve bazen hiçbir şey sayıya karşılık gelmez - belki şimdilik, ama bizim için bu o kadar önemli değil), yani sembollerden değil, her zaman özellikle sayıların sayısından bahsetmek daha doğrudur. Ancak aşağıda, konuyu kısaltmak adına, “kod noktası” terimini ima eden “sembol” kelimesini sıklıkla kullanacağım.
Unicode uçaklar. Gördüğünüz gibi çoğu (4'ten 13'e kadar olan uçaklar) hala kullanılmıyor.
En dikkat çekici olan şey, tüm ana “hamurun” sıfır düzlemde yer almasıdır, buna "Temel Çok Dilli Düzlem". Bir satırda modern dillerden birinde (Çince dahil) metin varsa, bu düzlemin ötesine geçemezsiniz. Ancak Unicode'un geri kalanını da kesemezsiniz - örneğin, emojiler esas olarak satırın sonunda bulunur sonraki uçak"Tamamlayıcı Çok Dilli Düzlem"(uzanır 0x10000 karşı 0x1FFFF). Yani UTF-16 şunu yapıyor: tüm karakterler içeri giriyor Temel Çok Dilli Düzlem, karşılık gelen iki baytlık bir sayıyla "olduğu gibi" kodlanır. Bununla birlikte, bu aralıktaki sayıların bazıları hiçbir şekilde belirli karakterleri göstermez, ancak bu bayt çiftinden sonra başka bir baytı dikkate almamız gerektiğini gösterir - bu dört baytın değerlerini bir araya getirerek kapsayan bir sayı elde ederiz. geçerli Unicode aralığının tamamı. Bu fikre "taşıyıcı çiftler" denir; onları duymuş olabilirsiniz.
Dolayısıyla UTF-16, "kod noktası" başına iki veya (çok nadir durumlarda) dört bayt gerektirir. Bu, her zaman dört bayt kullanmaktan daha iyidir, ancak Latince (ve diğer ASCII karakterleri) bu şekilde kodlandığında, alanın yarısını sıfırlarla boşa harcar. UTF-8 bunu düzeltmek için tasarlanmıştır: İçindeki ASCII, daha önce olduğu gibi yalnızca bir bayt kaplar; gelen kodlar 0x80 karşı 0x7FF - iki bayt; itibaren 0x800 karşı 0xFFFF - üç ve itibaren 0x10000 karşı 0x10FFFF - dört. Bir yandan Latin alfabesi iyi hale geldi: ASCII ile uyumluluk geri döndü ve dağıtım 1'den 4 bayta daha eşit bir şekilde "yayıldı". Ancak ne yazık ki Latince dışındaki alfabeler UTF-16'ya kıyasla hiçbir fayda sağlayamıyor ve çoğu artık iki yerine üç bayta ihtiyaç duyuyor; iki baytlık bir kaydın kapsadığı aralık 32 kat daraldı. 0xFFFF karşı 0x7FFve ne Çince ne de örneğin Gürcüce buna dahil değil. Kiril ve diğer beş alfabe - yaşasın - şanslı, karakter başına 2 bayt.
Bu neden oluyor? UTF-8'in karakter kodlarını nasıl temsil ettiğini görelim:
Sayıları doğrudan temsil etmek için burada sembolüyle işaretlenen bitler kullanılır x. İki baytlık bir kayıtta bu türden yalnızca 11 bitin (16 bitten) olduğu görülebilir. Buradaki önde gelen bitlerin yalnızca yardımcı bir işlevi vardır. Dört baytlık bir kayıt durumunda, 21 bitten 32'i kod noktası numarasına ayrılmıştır - üç bayt (toplamda 24 bit verir) yeterli gibi görünmektedir, ancak hizmet işaretçileri çok fazla yer kaplar.
Bu kötü mü? Tam olarak değil. Bir yandan, uzayı çok önemsiyorsak, tüm ekstra entropiyi ve artıklığı kolayca ortadan kaldırabilecek sıkıştırma algoritmalarımız var. Öte yandan Unicode'un amacı mümkün olan en evrensel kodlamayı sağlamaktı. Örneğin, UTF-8'de kodlanmış bir satırı daha önce yalnızca ASCII ile çalışan bir koda emanet edebiliriz ve aslında orada olmayan ASCII aralığındaki bir karakteri göreceğinden korkmayız (sonuçta, UTF-8'de tümü sıfır bitten başlayan baytlar - bu tam olarak ASCII'dir). Ve aniden büyük bir dizeden küçük bir kuyruğu, en baştan kodunu çözmeden kesmek istersek (veya hasarlı bir bölümden sonra bilginin bir kısmını geri yüklemek), bir karakterin başladığı yerdeki uzaklığı bulmak bizim için kolaydır (bu yeterlidir) bit önekine sahip baytları atlamak için 10).
O halde neden yeni bir şey icat edelim?
Aynı zamanda, deflate gibi sıkıştırma algoritmalarının yeterince uygulanamadığı ancak dizelerin kompakt bir şekilde depolanmasını istediğiniz durumlar da vardır. Şahsen ben inşaat yapmayı düşünürken bu problemle karşılaştım. isteğe bağlı dillerdeki sözcükleri içeren büyük bir sözlük için. Bir yandan, her kelime çok kısa olduğundan onu sıkıştırmak etkisiz olacaktır. Öte yandan, düşündüğüm ağaç uygulaması, depolanan dizenin her baytı ayrı bir ağaç tepe noktası oluşturacak şekilde tasarlandı, dolayısıyla sayılarını en aza indirmek çok faydalı oldu. benim kütüphanemde (De olduğu gibi , temel aldığı) benzer bir sorun basitçe çözülebilir - dizeler içine paketlenir -sözlük, orada saklanır . Ancak anlaşılması kolay olduğu gibi, bu yalnızca sınırlı bir alfabe için işe yarar; Çince bir satır böyle bir sözlüğe eklenemez.
Ayrı olarak, böyle bir veri yapısında UTF-8 kullanıldığında ortaya çıkan hoş olmayan bir nüansa daha dikkat çekmek isterim. Yukarıdaki resimde bir karakter iki byte olarak yazıldığında numarasına ait bitlerin arka arkaya gelmediği, bir çift bit ile ayrıldığı görülmektedir. 10 ortada: 110xxxxx 10xxxxxx. Bu nedenle, karakter kodunda ikinci baytın alt 6 biti taştığında (yani bir geçiş meydana geldiğinde) 10111111 → 10000000), o zaman ilk bayt da değişir. “P” harfinin baytlarla gösterildiği ortaya çıktı 0xD0 0xBF, ve bir sonraki "r" zaten 0xD1 0x80. Bir önek ağacında bu, ana düğümün önek için bir tane olmak üzere ikiye bölünmesine yol açar. 0xD0ve diğeri için 0xD1 (Kiril alfabesinin tamamı yalnızca ikinci bayt tarafından kodlanabilse de).
Ne aldım
Bu problemle karşı karşıya kaldığımda, bitlerle oyun oynama alıştırması yapmaya ve aynı zamanda bir bütün olarak Unicode'un yapısını biraz daha iyi tanımaya karar verdim. Sonuç, UTF-C kodlama formatıydı (bunun için "C"). kompakt), kod noktası başına 3 bayttan fazla harcamaz ve sıklıkla yalnızca kodlanmış satırın tamamı için ekstra bir bayt. Bu, ASCII olmayan birçok alfabede bu tür kodlamanın UTF-30'den %60-8 daha kompakt.
Kodlama ve kod çözme algoritmalarının uygulanmasına ilişkin örnekleri formda sundum bunları kodunuzda özgürce kullanabilirsiniz. Ama yine de bu formatın bir anlamda “bisiklet” olarak kaldığını vurgulayacağım ve kullanılmasını önermiyorum. neden ihtiyacın olduğunu anlamadan. Bu hala ciddi bir "UTF-8 iyileştirmesinden" ziyade bir deneydir. Bununla birlikte, buradaki kod çok sayıda yorum ve test kapsamıyla birlikte düzgün ve kısa bir şekilde yazılmıştır.
Test sonuçları ve UTF-8 ile karşılaştırma
ben de yaptım Algoritmanın performansını değerlendirebileceğiniz, ardından ilkeleri ve geliştirme süreci hakkında size daha fazla bilgi vereceğim.
Gereksiz bitlerin ortadan kaldırılması
UTF-8'i temel aldım elbette. Değiştirilebilecek ilk ve en belirgin şey, her bayttaki servis bitlerinin sayısını azaltmaktır. Örneğin, UTF-8'deki ilk bayt her zaman ikisinden biriyle başlar: 0veya ile 11 - bir önek 10 Yalnızca aşağıdaki baytlarda bu özellik bulunur. Ön eki değiştirelim 11 üzerinde 1ve sonraki baytlar için önekleri tamamen kaldıracağız. Ne olacak?
0xxxxxxx — 1 bayt
10xxxxxx xxxxxxxx - 2 bayt
110xxxxx xxxxxxxx xxxxxxxx - 3 bayt
Durun, dört baytlık kayıt nerede? Ancak artık buna gerek yok - üç bayt yazarken artık 21 bitimiz var ve bu, XNUMX'e kadar tüm sayılar için yeterli 0x10FFFF.
Burada neyi feda ettik? En önemli şey, arabellekteki rastgele bir konumdan karakter sınırlarının tespitidir. Rastgele bir bayta işaret edip ondan sonraki karakterin başlangıcını bulamayız. Bu, formatımızın bir sınırlamasıdır, ancak pratikte bu nadiren gereklidir. Genellikle arabelleği en başından itibaren çalıştırabiliriz (özellikle kısa çizgiler söz konusu olduğunda).
2 baytlık dilleri kapsama durumu da daha iyi hale geldi: artık iki baytlık format 14 bitlik bir aralık veriyor ve bunlar 0x3FFF. Çinliler şanssızdır (karakterleri çoğunlukla 0x4E00 karşı 0x9FFF), ancak Gürcüler ve diğer birçok insan daha çok eğleniyor - dilleri de karakter başına 2 bayta sığıyor.
Kodlayıcı durumunu girin
Şimdi çizgilerin özelliklerini düşünelim. Sözlük çoğunlukla aynı alfabenin karakterleriyle yazılmış sözcükleri içerir ve bu, diğer birçok metin için de geçerlidir. Bu alfabeyi bir kere belirtip, daha sonra sadece içindeki harfin numarasını belirtmek iyi olur. Bakalım Unicode tablosundaki karakterlerin düzeni bize yardımcı olacak mı?
Yukarıda belirtildiği gibi Unicode bölünmüştür uçak Her biri 65536 kod. Ancak bu çok kullanışlı bir bölme değildir (daha önce de söylediğimiz gibi çoğu zaman sıfır düzlemindeyiz). Daha ilginç olanı şuna göre bölünmedir: bloklar. Bu aralıkların artık sabit bir uzunluğu yoktur ve daha anlamlıdır; kural olarak, her biri aynı alfabedeki karakterleri birleştirir.
Bengalce alfabesinin karakterlerini içeren bir blok. Ne yazık ki, tarihsel nedenlerden dolayı bu, çok yoğun olmayan bir paketleme örneğidir - 96 karakter, 128 blok kod noktasına kaotik bir şekilde dağılmıştır.
Blokların başlangıcı ve boyutları her zaman 16'nın katlarıdır - bu sadece kolaylık sağlamak için yapılır. Ek olarak, birçok blok 128 ve hatta 256'nın katları olan değerlerle başlar ve biter - örneğin, temel Kiril alfabesi 256 bayt yer kaplar. 0x0400 karşı 0x04FF. Bu oldukça kullanışlıdır: öneki bir kez kaydedersek 0x04, herhangi bir Kiril karakteri bir bayta yazılabilir. Doğru, bu şekilde ASCII'ye (ve genel olarak diğer karakterlere) dönme fırsatını kaybedeceğiz. Bu nedenle şunu yapıyoruz:
- İki bayt
10yyyyyy yxxxxxxxyalnızca sayı içeren bir sembolü belirtmekle kalmazyyyyyy yxxxxxxx, ama aynı zamanda değiş mevcut alfabe üzerindeyyyyyy y0000000(yani en az önemli olanlar dışındaki tüm parçaları hatırlıyoruz 7 bit); - Bir bayt
0xxxxxxxmevcut alfabenin karakteri budur. Sadece 1. adımda hatırladığımız ofsete eklenmesi gerekiyor. Alfabeyi değiştirmesek de ofset sıfır olduğundan ASCII ile uyumluluğu koruduk.
Aynı şekilde 3 bayt gerektiren kodlar için:
- Üç bayt
110yyyyy yxxxxxxx xxxxxxxxbir rakamla bir sembol belirtinyyyyyy yxxxxxxx xxxxxxxx, değiştirmek mevcut alfabe üzerindeyyyyyy y0000000 00000000(küçük olanlar dışında her şeyi hatırladım) 15 bit) ve şu anda içinde bulunduğumuz kutuyu işaretleyin uzun mod (alfabeyi tekrar çift baytlık bir alfabeye değiştirirken bu bayrağı sıfırlayacağız); - İki bayt
0xxxxxxx xxxxxxxxuzun modda geçerli alfabenin karakteridir. Benzer şekilde 1. adımdaki offset ile ekliyoruz. Tek fark artık iki byte okuyoruz (çünkü bu moda geçmiştik).
Kulağa hoş geliyor: Artık aynı 7 bitlik Unicode aralığındaki karakterleri kodlamamız gerekirken, başlangıçta fazladan 1 bayt ve karakter başına toplamda bir bayt harcıyoruz.
Önceki sürümlerden birinden çalışmak. Zaten sıklıkla UTF-8'i geçiyor ancak hâlâ geliştirilebilecek noktalar var.
Daha kötü olan ne? Öncelikle bir şartımız var; mevcut alfabe ofseti ve onay kutusu uzun mod. Bu bizi daha da sınırlıyor: Artık aynı karakterler farklı bağlamlarda farklı şekilde kodlanabiliyor. Örneğin alt dizelerin aranması yalnızca baytları karşılaştırarak değil, bu dikkate alınarak yapılmalıdır. İkincisi, alfabeyi değiştirir değiştirmez, ASCII karakterlerinin kodlanması kötüleşti (ve bu sadece Latin alfabesi değil, aynı zamanda boşluklar da dahil olmak üzere temel noktalama işaretleri) - alfabeyi tekrar 0 olarak değiştirmeyi gerektiriyorlar, yani, yine fazladan bir bayt (ve sonra asıl konumuza dönmek için bir bayt daha).
Bir alfabe iyidir, iki daha iyidir
Yukarıda açıklanan üç önek yerine bir tane daha ekleyerek bit öneklerimizi biraz değiştirmeye çalışalım:
0xxxxxxx — Normal modda 1 bayt, uzun modda 2 bayt
11xxxxxx — 1 bayt
100xxxxx xxxxxxxx - 2 bayt
101xxxxx xxxxxxxx xxxxxxxx - 3 bayt
Artık iki baytlık bir kayıtta bir tane daha az kullanılabilir bit vardır - kod noktaları 0x1FFFVe 0x3FFF. Bununla birlikte, yine de çift baytlı UTF-8 kodlarından gözle görülür derecede daha büyük, en yaygın diller hala uyuyor, en dikkat çekici kayıp düştü и Japonlar üzgün.
Bu yeni kod nedir? 11xxxxxx? Bu, 64 karakter boyutunda küçük bir "zuladır", ana alfabemizi tamamlar, bu yüzden ona yardımcı adını verdim (yardımcı) alfabe. Mevcut alfabeyi değiştirdiğimizde eski alfabenin bir parçası yardımcı oluyor. Örneğin, ASCII'den Kiril alfabesine geçtik - zula artık 64 karakter içeriyor: Latin alfabesi, sayılar, boşluk ve virgül (ASCII olmayan metinlere en sık eklenenler). ASCII'ye geri döndüğünüzde Kiril alfabesinin ana kısmı yardımcı alfabe haline gelecektir.
İki alfabeye erişim sayesinde, çok sayıda metni alfabe değiştirme masraflarını minimuma indirerek işleyebiliriz (noktalama işaretleri çoğunlukla ASCII'ye geri dönüşe yol açar, ancak bundan sonra ek alfabeden ASCII olmayan birçok karakteri, tekrar geçiş yapıyorum).
Bonus: alt alfabenin önüne ekleme 11xxxxxx ve başlangıç ofsetinin seçilmesi 0xC0CP1252 ile kısmi uyumluluk elde ediyoruz. Başka bir deyişle, CP1252'de kodlanan Batı Avrupa metinlerinin çoğu (hepsi değil) UTF-C'de aynı görünecektir.
Ancak burada bir zorluk ortaya çıkıyor: Ana alfabeden yardımcı bir alfabe nasıl elde edilir? Aynı ofseti bırakabilirsiniz, ancak - ne yazık ki - burada Unicode yapısı zaten bize karşı oynuyor. Çoğu zaman alfabenin ana kısmı bloğun başında değildir (örneğin, Rusya'nın başkenti “A”nın kodu vardır) 0x0410Kiril bloğu şununla başlasa da 0x0400). Böylece ilk 64 karakteri zulaya aldıktan sonra alfabenin kuyruk kısmına erişimi kaybedebiliriz.
Bu sorunu çözmek için, farklı dillere karşılık gelen bazı blokları manuel olarak inceledim ve onlar için ana alfabe içindeki yardımcı alfabenin konumunu belirledim. Latin alfabesi istisna olarak genel olarak base64 gibi yeniden sıralandı.
Son dokunuşlar
Son olarak bir şeyi başka nerede geliştirebileceğimizi düşünelim.
Formatın 101xxxxx xxxxxxxx xxxxxxxx kadar sayıları kodlamanıza olanak tanır 0x1FFFFFve Unicode daha erken bitiyor: 0x10FFFF. Başka bir deyişle, son kod noktası şu şekilde temsil edilecektir: 10110000 11111111 11111111. Bu nedenle şunu söyleyebiliriz: eğer ilk bayt şu şekildeyse 1011xxxx (burada xxxx 0'dan büyük), o zaman başka bir anlama gelir. Örneğin, oraya bir baytta kodlama için sürekli olarak mevcut olan 15 karakter daha ekleyebilirsiniz, ancak ben bunu farklı yapmaya karar verdim.
Şimdi üç bayt gerektiren Unicode bloklarına bakalım. Temel olarak, daha önce de belirtildiği gibi, bunlar Çince karakterler - ancak onlarla bir şey yapmak zor, 21 bin tane var. Ancak hiragana ve katakana da oraya uçtu - ve artık sayıları o kadar fazla değil, iki yüzden az. Ve Japonları hatırladığımız için emojiler de var (aslında Unicode'da birçok yere dağılmışlar, ancak ana bloklar aralıkta) 0x1F300 - 0x1FBFF). Artık birden fazla kod noktasından bir araya getirilen emojilerin (örneğin, emoji ) var olduğu gerçeğini düşünürseniz 7'ye kadar koddan oluşur!), o zaman her birine üç bayt harcamak tam bir ayıp olur (7×3 = 21 bayt, bir simge uğruna, bir kabus).
Bu nedenle, emoji, hiragana ve katakana'ya karşılık gelen seçilmiş birkaç aralığı seçiyoruz, bunları sürekli bir liste halinde yeniden numaralandırıyoruz ve üç yerine iki bayt olarak kodluyoruz:
1011xxxx xxxxxxxx
Harika: yukarıda bahsedilen emoji7 kod noktasından oluşan UTF-8'de 25 byte yer kaplıyor ve bunu içine sığdırıyoruz 14 (her kod noktası için tam olarak iki bayt). Bu arada, Habr bunu sindirmeyi reddetti (hem eski hem de yeni editörde), bu yüzden onu bir resimle eklemek zorunda kaldım.
Bir sorunu daha çözmeye çalışalım. Hatırladığımız gibi temel alfabe esasen yüksek 6 bit, bunu aklımızda tutuyoruz ve bir sonraki kodu çözülen sembolün koduna yapıştırıyoruz. Bloktaki Çince karakterler durumunda 0x4E00 - 0x9FFF, bu ya bit 0 ya da 1'dir. Bu pek uygun değil: alfabeyi sürekli olarak bu iki değer arasında değiştirmemiz gerekecek (yani üç bayt harcamak). Ancak uzun modda, kısa modu kullanarak kodladığımız karakter sayısını kodun kendisinden çıkarabileceğimizi unutmayın (yukarıda açıklanan tüm hilelerden sonra bu 10240'tır) - o zaman hiyeroglif aralığı 0x2600 - 0x77FFve bu durumda, tüm bu aralık boyunca, en anlamlı 6 bit (21 üzerinden) 0'a eşit olacaktır. Bu nedenle, hiyeroglif dizileri, hiyeroglif başına iki bayt kullanacaktır (ki bu, bu kadar geniş bir aralık için en uygunudur), alfabe geçişlerine neden oluyor.
Alternatif çözümler: SCSU, BOCU-1
Makalenin başlığını yeni okuyan Unicode uzmanları, büyük olasılıkla size doğrudan Unicode standartları arasında olduğunu hatırlatmak için acele edeceklerdir. (SCSU), makalede açıklanana çok benzer bir kodlama yöntemini açıklar.
Dürüstçe itiraf ediyorum: Varlığını ancak kararımı yazmaya derinlemesine daldıktan sonra öğrendim. Bunu başından beri bilseydim, muhtemelen kendi yaklaşımımı bulmak yerine bir uygulama yazmayı denerdim.
İlginç olan, SCSU'nun benim kendi başıma bulduğum fikirlere çok benzer fikirler kullanmasıdır ("alfabe" kavramı yerine "pencereler" kullanıyorlar ve bunlardan daha fazlası mevcut). Aynı zamanda bu formatın dezavantajları da vardır: kodlama algoritmalarından ziyade sıkıştırma algoritmalarına biraz daha yakındır. Özellikle standart birçok temsil yöntemi verir, ancak en uygun olanın nasıl seçileceğini söylemez - bunun için kodlayıcının bir tür buluşsal yöntem kullanması gerekir. Dolayısıyla iyi paketleme üreten bir SCSU kodlayıcı benim algoritmamdan daha karmaşık ve daha hantal olacaktır.
Karşılaştırma için, SCSU'nun nispeten basit bir uygulamasını JavaScript'e aktardım - kod hacmi açısından UTF-C'mle karşılaştırılabilir olduğu ortaya çıktı, ancak bazı durumlarda sonuç yüzde onlarca daha kötüydü (bazen bunu aşabilir, ancak pek değil). Örneğin İbranice ve Yunanca metinler UTF-C ile kodlanmıştır. SCSU'dan %60 daha iyi (muhtemelen kompakt alfabelerinden dolayı).
Ayrı olarak, SCSU'nun yanı sıra Unicode'u kompakt bir şekilde temsil etmenin başka bir yolu olduğunu da ekleyeceğim - , ancak MIME uyumluluğunu hedefliyor (ki buna ihtiyacım yoktu) ve kodlamaya biraz farklı bir yaklaşım getiriyor. Etkinliğini değerlendirmedim ama bana öyle geliyor ki SCSU'dan daha yüksek olması pek mümkün değil.
Olası iyileştirmeler
Sunduğum algoritma tasarım gereği evrensel değil (bu muhtemelen hedeflerimin Unicode Konsorsiyumunun hedeflerinden en çok ayrıldığı noktadır). Öncelikle tek bir görev için (çok dilli bir sözlüğü bir önek ağacında saklamak) geliştirildiğini ve bazı özelliklerinin diğer görevler için pek uygun olmayabileceğini daha önce belirtmiştim. Ancak bunun bir standart olmaması bir artı olabilir. ihtiyaçlarınıza uyacak şekilde kolayca değiştirebilirsiniz.
Örneğin, açık bir şekilde durumun varlığından kurtulabilirsiniz, durumsuz kodlama yapabilirsiniz - sadece değişkenleri güncellemeyin offs, auxOffs и is21Bit kodlayıcı ve kod çözücüde. Bu durumda, aynı alfabedeki karakter dizilerini etkili bir şekilde paketlemek mümkün olmayacaktır ancak bağlamdan bağımsız olarak aynı karakterin her zaman aynı baytlarla kodlanmasının garantisi olacaktır.
Ek olarak, varsayılan durumu değiştirerek kodlayıcıyı belirli bir dile uyarlayabilirsiniz - örneğin, Rusça metinlere odaklanarak, kodlayıcıyı ve kod çözücüyü başlangıçta ayarlayabilirsiniz. offs = 0x0400 и auxOffs = 0. Bu özellikle durum bilgisi olmayan mod durumunda anlamlıdır. Genel olarak bu, eski sekiz bitlik kodlamanın kullanılmasına benzer olacaktır, ancak gerektiğinde tüm Unicode'dan karakter ekleme yeteneği ortadan kaldırılmayacaktır.
Daha önce bahsedilen bir diğer dezavantaj, UTF-C ile kodlanmış büyük metinlerde, rastgele bir bayta en yakın karakter sınırını bulmanın hızlı bir yolunun bulunmamasıdır. Kodlanmış arabelleğin son 100 baytını keserseniz, hiçbir şey yapamayacağınız çöp alma riskiyle karşı karşıya kalırsınız. Kodlama, çok gigabaytlık günlükleri depolamak için tasarlanmamıştır, ancak genel olarak bu düzeltilebilir. Bayt 0xBF asla ilk bayt olarak görünmemelidir (ancak ikinci veya üçüncü bayt da olabilir). Bu nedenle, kodlama sırasında diziyi ekleyebilirsiniz. 0xBF 0xBF 0xBF her biri 10 KB - o zaman bir sınır bulmanız gerekiyorsa, benzer bir işaret bulunana kadar seçilen parçayı taramanız yeterli olacaktır. Sonuncuyu takip ediyorum 0xBF bir karakterin başlangıcı olacağı garanti edilir. (Kod çözerken, bu üç baytlık dizinin elbette göz ardı edilmesi gerekecektir.)
Özetleme
Buraya kadar okuduysanız tebrikler! Umarım siz de benim gibi Unicode'un yapısı hakkında yeni bir şeyler öğrenmişsinizdir (veya hafızanızı tazelemişsinizdir).
Demo sayfası. İbranice örneği hem UTF-8 hem de SCSU'ya göre avantajları göstermektedir.
Yukarıda açıklanan araştırma standartlara tecavüz olarak değerlendirilmemelidir. Ancak genel olarak işimin sonuçlarından memnunum, dolayısıyla onlardan da memnunum : örneğin, küçültülmüş bir JS kitaplığı yalnızca 1710 bayt ağırlığındadır (ve elbette hiçbir bağımlılığı yoktur). Yukarıda belirttiğim gibi çalışmalarına şuradan ulaşılabilir: (ayrıca UTF-8 ve SCSU ile karşılaştırılabilecek bir dizi metin de vardır).
Son olarak UTF-C'nin kullanıldığı durumlara bir kez daha dikkat çekeceğim. değmez:
- Satırlarınız yeterince uzunsa (100-200 karakter). Bu durumda deflate gibi sıkıştırma algoritmalarını kullanmayı düşünmelisiniz.
- Eğer ihtiyacın varsa ASCII şeffaflığıyani kodlanmış dizilerin orijinal dizede olmayan ASCII kodlarını içermemesi sizin için önemlidir. Üçüncü taraf API'lerle etkileşimde bulunurken (örneğin, bir veritabanıyla çalışırken), kodlama sonucunu dizeler olarak değil soyut bir bayt kümesi olarak iletirseniz, buna duyulan ihtiyaç önlenebilir. Aksi takdirde beklenmedik güvenlik açıklarıyla karşılaşma riskiyle karşı karşıya kalırsınız.
- İsteğe bağlı bir uzaklıktaki karakter sınırlarını hızlı bir şekilde bulabilmek istiyorsanız (örneğin, bir satırın bir kısmı hasar gördüğünde). Bu yapılabilir, ancak yalnızca satırı baştan itibaren tarayarak (veya önceki bölümde açıklanan değişikliği uygulayarak).
- Dizelerin içeriği üzerinde hızlı bir şekilde işlem yapmanız gerekiyorsa (bunları sıralayın, alt dizeleri arayın, birleştirin). Bu, önce dizelerin kodunun çözülmesini gerektirir, dolayısıyla bu durumlarda UTF-C, UTF-8'den daha yavaş olacaktır (ancak sıkıştırma algoritmalarından daha hızlı). Aynı dize her zaman aynı şekilde kodlandığından, kod çözmenin tam olarak karşılaştırılması gerekli değildir ve bayt bayt bazında yapılabilir.
Güncelleme: kullanıcı UTF-C'nin uygulanabilirlik sınırlarını vurgulayan bir grafik yayınladı. Paketlenmiş dize daha kısa olduğu sürece UTF-C'nin genel amaçlı bir sıkıştırma algoritmasından (LZW'nin bir varyasyonu) daha verimli olduğunu gösterir. ~140 karakter (ancak karşılaştırmanın bir metin üzerinde yapıldığını not ediyorum; diğer diller için sonuç farklı olabilir).
Kaynak: habr.com