دوچرخه دیگر: رشته های یونیکد را 30 تا 60 درصد فشرده تر از UTF-8 ذخیره می کنیم

اگر شما یک توسعه دهنده هستید و با وظیفه انتخاب رمزگذاری روبرو هستید، یونیکد تقریبا همیشه راه حل مناسبی خواهد بود. روش نمایش خاص به زمینه بستگی دارد، اما اغلب یک پاسخ جهانی در اینجا نیز وجود دارد - UTF-8. خوبی در مورد آن این است که به شما امکان می دهد از تمام کاراکترهای یونیکد بدون هزینه استفاده کنید بیش از حد تعداد زیادی بایت در اکثر موارد. درست است، برای زبان هایی که بیش از الفبای لاتین استفاده می کنند، حداقل "نه خیلی زیاد" است. دو بایت در هر کاراکتر. آیا می‌توانیم بدون بازگشت به رمزگذاری‌های ماقبل تاریخ که ما را به ۲۵۶ کاراکتر در دسترس محدود می‌کند، بهتر عمل کنیم؟

در زیر پیشنهاد می‌کنم با تلاش من برای پاسخ به این سؤال آشنا شوید و یک الگوریتم نسبتاً ساده را پیاده‌سازی کنید که به شما امکان می‌دهد خطوط را در اکثر زبان‌های دنیا بدون اضافه کردن افزونگی که در UTF-8 است ذخیره کنید.

سلب مسئولیت. من بلافاصله چند رزرو مهم را انجام خواهم داد: راه حل توصیف شده به عنوان یک جایگزین جهانی برای UTF-8 ارائه نشده است، فقط در یک لیست باریک از موارد مناسب است (در مورد آنها در زیر توضیح داده می شود) و در هیچ موردی نباید برای تعامل با API های شخص ثالث (که حتی در مورد آن اطلاعی ندارند) استفاده شود. اغلب، الگوریتم های فشرده سازی همه منظوره (به عنوان مثال، deflate) برای ذخیره سازی فشرده حجم زیادی از داده های متنی مناسب هستند. علاوه بر این، در حال حاضر در فرآیند ایجاد راه حل خود، یک استاندارد موجود در خود یونیکد پیدا کردم، که همان مشکل را حل می کند - تا حدودی پیچیده تر است (و اغلب بدتر)، اما همچنان یک استاندارد پذیرفته شده است، و نه تنها با هم روی زانو من هم در مورد او به شما می گویم.

درباره یونیکد و UTF-8

برای شروع، چند کلمه در مورد چیستی آن یونیکد и UTF-8.

همانطور که می دانید، رمزگذاری های 8 بیتی در گذشته محبوب بودند. با آنها، همه چیز ساده بود: 256 کاراکتر را می توان با اعداد از 0 تا 255 شماره گذاری کرد، و اعداد از 0 تا 255 را می توان به وضوح به عنوان یک بایت نشان داد. اگر به همان ابتدا برگردیم، رمزگذاری ASCII کاملاً به 7 بیت محدود می شود، بنابراین مهم ترین بیت در نمایش بایت آن صفر است و اکثر رمزگذاری های 8 بیتی با آن سازگار هستند (فقط در "بالا" متفاوت هستند. بخش، که در آن مهم ترین بیت یکی است).

یونیکد چه تفاوتی با آن کدگذاری ها دارد و چرا تعداد زیادی نمایش خاص با آن مرتبط است - UTF-8، UTF-16 (BE و LE)، UTF-32؟ بیایید به ترتیب آن را مرتب کنیم.

استاندارد اصلی یونیکد تنها مطابقت بین کاراکترها (و در برخی موارد، اجزای جداگانه کاراکترها) و تعداد آنها را توصیف می کند. و تعداد زیادی اعداد ممکن در این استاندارد وجود دارد - از 0x00 به 0x10FFFF (1 قطعه). اگر بخواهیم عددی را در چنین محدوده ای در یک متغیر قرار دهیم، نه 114 و نه 112 بایت برای ما کافی نیست. و از آنجایی که پردازنده های ما برای کار با اعداد سه بایتی طراحی نشده اند، مجبور می شویم تا 1 بایت در هر کاراکتر استفاده کنیم! این UTF-2 است، اما دقیقاً به دلیل این "اسراف" است که این قالب محبوب نیست.

خوشبختانه ترتیب کاراکترها در یونیکد تصادفی نیست. کل مجموعه آنها به 17 "تقسیم شده است.هواپیماها"، که هر کدام شامل 65536 (0x10000) «نقاط کد" مفهوم "نقطه کد" در اینجا به سادگی است شماره کاراکتر، توسط یونیکد به آن اختصاص داده شده است. اما، همانطور که در بالا ذکر شد، در یونیکد نه تنها کاراکترهای فردی شماره گذاری می شوند، بلکه اجزاء و علائم خدمات آنها نیز شماره گذاری می شوند (و گاهی اوقات هیچ چیز با عدد مطابقت ندارد - شاید در حال حاضر، اما برای ما این چندان مهم نیست) درست تر است که همیشه به طور خاص در مورد تعداد خود اعداد صحبت کنید و نه نمادها. با این حال، در ادامه، به منظور اختصار، اغلب از کلمه "نماد" استفاده می کنم که به معنای "نقطه رمز" است.

هواپیماهای یونیکد همانطور که می بینید، بیشتر آن (هواپیماهای 4 تا 13) هنوز استفاده نشده است.

نکته قابل توجه این است که تمام "پالپ" اصلی در صفحه صفر قرار دارد که به آن "هواپیما چند زبانه پایهاگر خطی حاوی متنی به یکی از زبان‌های مدرن (از جمله چینی) باشد، از این صفحه فراتر نخواهید رفت. اما نمی‌توانید بقیه یونیکد را هم قطع کنید - برای مثال، شکلک‌ها عمدتاً در انتهای صفحه قرار دارند. هواپیمای بعدی"هواپیمای چند زبانه تکمیلی"(از امتداد می یابد 0x10000 به 0x1FFFF). بنابراین UTF-16 این کار را انجام می دهد: همه کاراکترها در داخل قرار می گیرند هواپیما چند زبانه پایه، "همانطور که هست" با یک عدد دو بایتی مربوطه کدگذاری می شوند. با این حال، برخی از اعداد در این محدوده به هیچ وجه نشان دهنده کاراکترهای خاصی نیستند، بلکه نشان می دهند که پس از این جفت بایت باید یکی دیگر را در نظر بگیریم - با ترکیب مقادیر این چهار بایت با هم، عددی به دست می آید که پوشش می دهد. کل محدوده معتبر یونیکد این ایده "زوج های جایگزین" نامیده می شود - ممکن است نام آنها را شنیده باشید.

بنابراین UTF-16 به دو یا (در موارد بسیار نادر) چهار بایت در هر "نقطه کد" نیاز دارد. این بهتر از استفاده مداوم از چهار بایت است، اما لاتین (و سایر کاراکترهای ASCII) وقتی به این روش کدگذاری می شوند، نیمی از فضا را روی صفرها تلف می کند. UTF-8 برای اصلاح این امر طراحی شده است: ASCII در آن، مانند قبل، تنها یک بایت را اشغال می کند. کدها از 0x80 به 0x7FF - دو بایت؛ از جانب 0x800 به 0xFFFF - سه، و از 0x10000 به 0x10FFFF - چهار از یک طرف، الفبای لاتین خوب شده است: سازگاری با ASCII بازگشته است، و توزیع به طور مساوی از 1 تا 4 بایت "گسترش" بیشتری دارد. اما متأسفانه الفبای دیگری غیر از لاتین به هیچ وجه در مقایسه با UTF-16 سودی ندارند و بسیاری از آنها اکنون به جای دو بایت به سه بایت نیاز دارند - محدوده پوشش داده شده توسط یک رکورد دو بایتی 32 برابر کاهش یافته است. 0xFFFF به 0x7FFو نه چینی و نه مثلا گرجی در آن گنجانده نشده است. سیریلیک و پنج الفبای دیگر - hurray - lucky، 2 بایت در هر کاراکتر.

چرا این اتفاق می افتد؟ بیایید ببینیم UTF-8 چگونه کدهای کاراکتر را نشان می دهد:

به طور مستقیم برای نشان دادن اعداد، بیت های مشخص شده با نماد در اینجا استفاده می شود x. مشاهده می شود که در یک رکورد دو بایتی تنها 11 بیت (از 16 بیت) وجود دارد. بیت های پیشرو در اینجا فقط یک عملکرد کمکی دارند. در مورد رکورد چهار بایتی، 21 بیت از 32 بیت برای شماره نقطه کد اختصاص داده می شود - به نظر می رسد که سه بایت (که در مجموع 24 بیت می دهد) کافی است، اما نشانگرهای سرویس بیش از حد مصرف می کنند.

این بد است؟ نه واقعا. از یک طرف، اگر به فضا اهمیت زیادی بدهیم، الگوریتم های فشرده سازی داریم که به راحتی می توانند تمام آنتروپی و افزونگی اضافی را حذف کنند. از سوی دیگر، هدف یونیکد ارائه جهانی ترین کدگذاری ممکن بود. به عنوان مثال، ما می‌توانیم خطی را که در UTF-8 کدگذاری شده است به کدهایی که قبلاً فقط با ASCII کار می‌کرد، واگذار کنیم، و نترسید که یک کاراکتر از محدوده ASCII را ببیند که در واقع وجود ندارد (بالاخره، در UTF-8 همه بایت ها با بیت صفر شروع می شوند - این دقیقا همان چیزی است که ASCII است). و اگر ناگهان بخواهیم یک دم کوچک را از یک رشته بزرگ بدون رمزگشایی از همان ابتدا جدا کنیم (یا بخشی از اطلاعات را پس از یک بخش آسیب دیده بازیابی کنیم)، پیدا کردن افست جایی که یک کاراکتر شروع می شود برای ما آسان است (کافی است برای رد شدن از بایت هایی که پیشوند بیت دارند 10).

پس چرا چیز جدیدی اختراع کرد؟

در عین حال، گاهی اوقات موقعیت‌هایی پیش می‌آید که الگوریتم‌های فشرده‌سازی مانند deflate کاربرد ضعیفی دارند، اما شما می‌خواهید به ذخیره فشرده رشته‌ها برسید. من شخصاً وقتی به ساخت و ساز فکر می کردم با این مشکل مواجه شدم درخت پیشوند فشرده برای یک فرهنگ لغت بزرگ شامل کلمات در زبان های دلخواه. از یک طرف، هر کلمه بسیار کوتاه است، بنابراین فشرده سازی آن بی اثر خواهد بود. از طرف دیگر، پیاده سازی درختی که من در نظر گرفتم طوری طراحی شده بود که هر بایت از رشته ذخیره شده یک راس درخت جداگانه ایجاد کند، بنابراین به حداقل رساندن تعداد آنها بسیار مفید بود. در کتابخانه من Az.js (همانطور که در پی مورفی 2، که بر اساس آن است) یک مشکل مشابه را می توان به سادگی حل کرد - رشته ها در بسته بندی شده اند DAWG- دیکشنری، در آنجا ذخیره شده است CP1251 خوب قدیمی. اما، همانطور که درک آن آسان است، این فقط برای یک الفبای محدود به خوبی کار می کند - یک خط به زبان چینی را نمی توان به چنین فرهنگ لغتی اضافه کرد.

به طور جداگانه، من می خواهم به یک نکته ظریف ناخوشایند دیگر اشاره کنم که هنگام استفاده از UTF-8 در چنین ساختار داده ای ایجاد می شود. تصویر بالا نشان می دهد که وقتی یک کاراکتر به صورت دو بایت نوشته می شود، بیت های مربوط به عدد آن پشت سر هم قرار نمی گیرند، بلکه با یک جفت بیت از هم جدا می شوند. 10 در وسط: 110xxxxx 10xxxxxx. به همین دلیل، هنگامی که 6 بیت پایینی بایت دوم در کد کاراکتر سرریز می شود (یعنی یک انتقال رخ می دهد 10111111 → 10000000، سپس اولین بایت نیز تغییر می کند. به نظر می رسد که حرف "p" با بایت نشان داده می شود 0xD0 0xBF، و "r" بعدی در حال حاضر است 0xD1 0x80. در درخت پیشوند، این منجر به تقسیم گره والد به دو قسمت می شود - یکی برای پیشوند. 0xD0، و دیگری برای 0xD1 (اگرچه کل الفبای سیریلیک را فقط می توان با بایت دوم رمزگذاری کرد).

چه چیزی به دست آوردم

در مواجهه با این مشکل، تصمیم گرفتم بازی های با بیت را تمرین کنم و در عین حال کمی بهتر با ساختار یونیکد به طور کلی آشنا شوم. نتیجه فرمت رمزگذاری UTF-C ("C" برای جمع و جور) که بیش از 3 بایت در هر نقطه کد مصرف نمی کند، و اغلب به شما اجازه می دهد فقط هزینه کنید یک بایت اضافی برای کل خط کدگذاری شده. این منجر به این واقعیت می شود که در بسیاری از الفبای غیر ASCII چنین رمزگذاری به نظر می رسد 30-60٪ فشرده تر از UTF-8.

نمونه هایی از پیاده سازی الگوریتم های کدگذاری و رمزگشایی را در قالب ارائه کرده ام کتابخانه های جاوا اسکریپت و برو، می توانید آزادانه از آنها در کد خود استفاده کنید. اما من همچنان تاکید می کنم که به یک معنا این قالب یک "دوچرخه" باقی می ماند و من استفاده از آن را توصیه نمی کنم بدون اینکه بفهمی چرا بهش نیاز داری. این هنوز بیشتر یک آزمایش است تا یک "بهبود جدی UTF-8". با این وجود، کد موجود در آنجا به طور منظم، مختصر، با تعداد زیادی نظرات و پوشش آزمایشی نوشته شده است.

نتایج تست و مقایسه با UTF-8

من هم انجام دادم صفحه نمایشی، که در آن می توانید عملکرد الگوریتم را ارزیابی کنید و سپس در مورد اصول و روند توسعه آن بیشتر به شما خواهم گفت.

حذف بیت های اضافی

البته من UTF-8 رو پایه گرفتم. اولین و واضح ترین چیزی که می توان در آن تغییر داد، کاهش تعداد بیت های سرویس در هر بایت است. به عنوان مثال، اولین بایت در UTF-8 همیشه با یکی شروع می شود 0، یا با 11 - یک پیشوند 10 فقط بایت های زیر آن را دارند. بیایید پیشوند را جایگزین کنیم 11 بر 1، و برای بایت های بعدی پیشوندها را به طور کامل حذف می کنیم. چه اتفاقی خواهد افتاد؟

0xxxxxxx - 1 بایت
10xxxxxx xxxxxxxx - 2 بایت
110xxxxx xxxxxxxx xxxxxxxx - 3 بایت

صبر کن رکورد چهار بایت کجاست؟ اما دیگر نیازی به آن نیست - هنگام نوشتن در سه بایت، اکنون 21 بیت در دسترس داریم و این برای همه اعداد کافی است. 0x10FFFF.

ما اینجا چه چیزی را قربانی کرده ایم؟ مهمترین چیز تشخیص مرزهای کاراکتر از یک مکان دلخواه در بافر است. ما نمی توانیم به یک بایت دلخواه اشاره کنیم و شروع کاراکتر بعدی را از آن پیدا کنیم. این یک محدودیت در قالب ما است، اما در عمل به ندرت لازم است. ما معمولاً می توانیم از همان ابتدا از طریق بافر عبور کنیم (مخصوصاً وقتی صحبت از خطوط کوتاه می شود).

وضعیت پوشش زبان ها با 2 بایت نیز بهتر شده است: اکنون فرمت دو بایتی محدوده 14 بیتی را ارائه می دهد و اینها کدهایی هستند تا حداکثر 0x3FFF. چینی ها بدشانس هستند (شخصیت های آنها عمدتاً متفاوت است 0x4E00 به 0x9FFF، اما گرجی ها و بسیاری از مردمان دیگر سرگرم کننده تر هستند - زبان آنها نیز به 2 بایت در هر کاراکتر می رسد.

وضعیت رمزگذار را وارد کنید

حالا بیایید به خواص خود خطوط فکر کنیم. فرهنگ لغت اغلب حاوی کلماتی است که با حروف الفبای یکسان نوشته شده اند و این در مورد بسیاری از متون دیگر نیز صادق است. خوب است که این الفبا را یک بار مشخص کنید و سپس فقط شماره حرف داخل آن را مشخص کنید. بیایید ببینیم ترتیب کاراکترها در جدول یونیکد به ما کمک می کند یا خیر.

همانطور که در بالا ذکر شد، یونیکد به دو دسته تقسیم می شود سطح هر کدام 65536 کد اما این یک تقسیم بندی بسیار مفید نیست (همانطور که قبلاً گفته شد، اغلب ما در صفحه صفر هستیم). جالب تر، تقسیم بر اساس است بلوک ها این محدوده‌ها دیگر طول ثابتی ندارند و معنی‌دارتر هستند - به عنوان یک قاعده، هر کدام از حروف الفبای یکسان را ترکیب می‌کنند.

بلوکی حاوی نویسه‌های الفبای بنگالی. متأسفانه، به دلایل تاریخی، این نمونه ای از بسته بندی نه چندان متراکم است - 96 کاراکتر به طور آشفته در 128 نقطه کد بلوک پراکنده شده اند.

ابتدای بلوک ها و اندازه آنها همیشه مضربی از 16 است - این کار به سادگی برای راحتی انجام می شود. علاوه بر این، بسیاری از بلوک ها با مقادیری که مضرب 128 یا حتی 256 هستند شروع و پایان می یابند - به عنوان مثال، الفبای سیریلیک پایه 256 بایت را اشغال می کند. 0x0400 به 0x04FF. این کاملاً راحت است: اگر یک بار پیشوند را ذخیره کنیم 0x04، سپس هر کاراکتر سیریلیک را می توان در یک بایت نوشت. درست است، به این ترتیب ما فرصت بازگشت به ASCII (و به طور کلی به هر شخصیت دیگر) را از دست خواهیم داد. بنابراین ما این کار را انجام می دهیم:

1. دو بایت 10yyyyyy yxxxxxxx نه تنها نماد را با یک عدد نشان دهید yyyyyy yxxxxxxx، بلکه تغییر کند الفبای فعلی بر yyyyyy y0000000 (یعنی همه بیت ها را به یاد می آوریم به جز کم اهمیت ترین آنها 7 بیت);
2. یک بایت 0xxxxxxx این ویژگی الفبای فعلی است. فقط باید به افستی که در مرحله 1 به خاطر داشتیم اضافه شود. در حالی که حروف الفبا را تغییر ندادیم، افست صفر است، بنابراین سازگاری با ASCII را حفظ کردیم.

به همین ترتیب برای کدهایی که به 3 بایت نیاز دارند:

1. سه بایت 110yyyyy yxxxxxxx xxxxxxxx نمادی را با یک عدد نشان دهید yyyyyy yxxxxxxx xxxxxxxx، تغییر دادن الفبای فعلی بر yyyyyy y0000000 00000000 (همه چیز را به یاد می آورد به جز جوان ترها 15 بیت) و کادری که اکنون در آن هستیم را علامت بزنید طولانی حالت (هنگام تغییر الفبای دو بایتی، این پرچم را بازنشانی می کنیم).
2. دو بایت 0xxxxxxx xxxxxxxx در حالت طولانی این کاراکتر الفبای فعلی است. به طور مشابه، ما آن را با افست از مرحله 1 اضافه می کنیم. تنها تفاوت این است که اکنون دو بایت می خوانیم (چون به این حالت تغییر داده ایم).

خوب به نظر می رسد: اکنون در حالی که باید کاراکترهایی را از همان محدوده یونیکد 7 بیتی رمزگذاری کنیم، در ابتدا 1 بایت اضافی و در مجموع یک بایت برای هر کاراکتر صرف می کنیم.

کار از یکی از نسخه های قبلی. در حال حاضر اغلب UTF-8 را شکست می دهد، اما هنوز جای پیشرفت وجود دارد.

چه بدتر؟ اولاً ما یک شرط داریم، یعنی افست الفبای فعلی و چک باکس حالت طولانی. این بیشتر ما را محدود می‌کند: اکنون کاراکترهای یکسان را می‌توان در زمینه‌های مختلف به طور متفاوتی کدگذاری کرد. برای مثال، جستجوی زیررشته‌ها باید با در نظر گرفتن این موضوع انجام شود و نه فقط با مقایسه بایت‌ها. ثانیاً ، به محض اینکه ما الفبا را تغییر دادیم ، با رمزگذاری کاراکترهای ASCII بد شد (و این فقط الفبای لاتین نیست ، بلکه علائم نگارشی اساسی از جمله فاصله ها نیز هست) - آنها نیاز به تغییر مجدد الفبا به 0 دارند ، یعنی دوباره یک بایت اضافی (و سپس یک بایت دیگر برای بازگشت به موضوع اصلی).

یک الفبا خوب است، دوتا بهتر است

بیایید سعی کنیم پیشوندهای بیت خود را کمی تغییر دهیم و یکی دیگر را به سه موردی که در بالا توضیح داده شد فشار دهیم:

0xxxxxxx - 1 بایت در حالت عادی، 2 بایت در حالت طولانی
11xxxxxx - 1 بایت
100xxxxx xxxxxxxx - 2 بایت
101xxxxx xxxxxxxx xxxxxxxx - 3 بایت

اکنون در یک رکورد دو بایتی یک بیت کمتر در دسترس وجود دارد - کد به بالا اشاره می کند 0x1FFFو نه 0x3FFF. با این حال، هنوز هم به طور قابل توجهی بزرگتر از کدهای UTF-8 دو بایتی است، اکثر زبان‌های رایج هنوز هم جا می‌شوند، قابل توجه‌ترین ضرر کاهش یافته است. هیراگانا и کاتاکانا، ژاپنی ها غمگین هستند.

این کد جدید چیست؟ 11xxxxxx? این یک "ذخیره" کوچک با اندازه 64 کاراکتر است، الفبای اصلی ما را تکمیل می کند، بنابراین من آن را کمکی نامیدم (کمکی) الفبا. وقتی الفبای فعلی را تغییر می دهیم، یک تکه از الفبای قدیمی کمکی می شود. به عنوان مثال، ما از ASCII به سیریلیک تغییر مکان دادیم - ذخیره اکنون شامل 64 کاراکتر است که شامل الفبای لاتین، اعداد، فاصله و کاما (متداول ترین درج ها در متون غیر ASCII). به ASCII برگردید - و بخش اصلی الفبای سیریلیک به الفبای کمکی تبدیل می شود.

به لطف دسترسی به دو الفبا، می‌توانیم تعداد زیادی متن را با حداقل هزینه برای تغییر الفبا مدیریت کنیم (نقاط نگارشی اغلب منجر به بازگشت به ASCII می‌شود، اما پس از آن، بسیاری از کاراکترهای غیر ASCII را از الفبای اضافی دریافت خواهیم کرد، بدون اینکه تعویض مجدد).

جایزه: پیشوند الفبای فرعی 11xxxxxx و افست اولیه آن را انتخاب کنید 0xC0، ما با CP1252 سازگاری جزئی دریافت می کنیم. به عبارت دیگر، بسیاری از متون اروپای غربی (و نه همه) کدگذاری شده در CP1252 در UTF-C یکسان خواهند بود.

اما در اینجا یک مشکل پیش می آید: چگونه می توان یک کمکی را از الفبای اصلی به دست آورد؟ شما می توانید همان افست را ترک کنید، اما - افسوس - در اینجا ساختار یونیکد در حال حاضر علیه ما بازی می کند. اغلب قسمت اصلی الفبا در ابتدای بلوک نیست (به عنوان مثال، پایتخت روسیه "A" دارای کد است. 0x0410، اگرچه بلوک سیریلیک با شروع می شود 0x0400). بنابراین، با وارد کردن 64 کاراکتر اول به انبار، ممکن است دسترسی به قسمت انتهایی حروف الفبا را از دست دهیم.

برای رفع این مشکل، من به صورت دستی برخی از بلوک های مربوط به زبان های مختلف را مرور کردم و افست الفبای کمکی را در الفبای اصلی برای آنها مشخص کردم. الفبای لاتین، به عنوان یک استثنا، به طور کلی مانند base64 دوباره ترتیب داده شد.

لمس های نهایی

بیایید در نهایت به این فکر کنیم که کجا می توانیم چیزی را بهبود بخشیم.

توجه داشته باشید که فرمت 101xxxxx xxxxxxxx xxxxxxxx به شما امکان می دهد تا اعداد را رمزگذاری کنید 0x1FFFFF، و یونیکد زودتر به پایان می رسد، در 0x10FFFF. به عبارت دیگر، آخرین نقطه کد به صورت نمایش داده می شود 10110000 11111111 11111111. بنابراین می توان گفت که اگر بایت اول به شکل باشد 1011xxxx (جایی که xxxx بزرگتر از 0)، سپس معنای دیگری دارد. به عنوان مثال، شما می توانید 15 کاراکتر دیگر را در آنجا اضافه کنید که دائماً برای رمزگذاری در یک بایت در دسترس هستند، اما من تصمیم گرفتم این کار را متفاوت انجام دهم.

حالا بیایید به بلوک های یونیکد که به سه بایت نیاز دارند نگاه کنیم. اساساً همانطور که قبلاً ذکر شد ، اینها حروف چینی هستند - اما انجام کاری با آنها دشوار است ، 21 هزار نفر از آنها وجود دارد. اما هیراگانا و کاتاکانا نیز به آنجا پرواز کردند - و دیگر تعداد آنها زیاد نیست، کمتر از دویست. و از آنجایی که ما ژاپنی ها را به یاد آوردیم، ایموجی ها نیز وجود دارد (در واقع، آنها در بسیاری از نقاط یونیکد پراکنده هستند، اما بلوک های اصلی در محدوده قرار دارند. 0x1F300 - 0x1FBFF). اگر به این واقعیت فکر می کنید که اکنون ایموجی هایی وجود دارند که از چندین نقطه کد به طور همزمان جمع شده اند (مثلاً ایموجی ها از 7 کد تشکیل شده است!)، سپس خرج کردن سه بایت برای هر کدام (7×3 = 21 بایت به خاطر یک نماد، یک کابوس) کاملاً شرم آور است.

بنابراین، چند محدوده انتخاب شده مربوط به ایموجی، هیراگانا و کاتاکانا را انتخاب می کنیم، آنها را در یک لیست پیوسته شماره گذاری می کنیم و به جای سه بایت، آنها را به صورت دو بایت رمزگذاری می کنیم:

1011xxxx xxxxxxxx

عالی: ایموجی فوق الذکر، متشکل از 7 نقطه کد، 8 بایت در UTF-25 می گیرد و ما آن را در 14 (دقیقا دو بایت برای هر نقطه کد). ضمناً حبر از هضم آن امتناع کرد (چه در ویرایشگر قدیم و چه در ویرایشگر جدید) بنابراین مجبور شدم آن را با یک عکس درج کنم.

بیایید سعی کنیم یک مشکل دیگر را برطرف کنیم. همانطور که به یاد داریم، الفبای اصلی اساساً است 6 بیت بالا، که آن را در نظر می گیریم و به کد هر نماد رمزگشایی شده بعدی می چسبانیم. در مورد حروف چینی که در بلوک هستند 0x4E00 - 0x9FFF، این بیت 0 یا 1 است. این خیلی راحت نیست: ما باید دائماً الفبا را بین این دو مقدار تغییر دهیم (یعنی سه بایت صرف کنیم). اما توجه داشته باشید که در حالت طولانی، از خود کد می توانیم تعداد کاراکترهایی را که با استفاده از حالت کوتاه رمزگذاری می کنیم کم کنیم (بعد از تمام ترفندهایی که در بالا توضیح داده شد، این 10240 است) - سپس محدوده هیروگلیف ها به 0x2600 - 0x77FFو در این حالت، در کل این محدوده، مهم ترین 6 بیت (از 21) برابر با 0 خواهد بود. بنابراین، دنباله های هیروگلیف از دو بایت در هر هیروگلیف استفاده می کنند (که برای چنین محدوده بزرگی بهینه است)، بدون اینکه باعث تغییر الفبا می شود.

راه حل های جایگزین: SCSU، BOCU-1

کارشناسان یونیکد، با خواندن عنوان مقاله، به احتمال زیاد عجله خواهند کرد که به شما یادآوری کنند که مستقیماً در بین استانداردهای یونیکد وجود دارد. طرح فشرده سازی استاندارد برای یونیکد (SCSU)، که یک روش رمزگذاری بسیار شبیه به آنچه در مقاله توضیح داده شده است، توصیف می کند.

صادقانه اعتراف می کنم: تنها پس از اینکه عمیقاً در نوشتن تصمیمم غوطه ور شدم از وجود آن مطلع شدم. اگر از ابتدا در مورد آن می دانستم، احتمالاً سعی می کردم به جای ارائه رویکرد خودم، یک پیاده سازی بنویسم.

جالب اینجاست که SCSU از ایده‌هایی بسیار شبیه به ایده‌هایی استفاده می‌کند که خودم به ذهنم رسید (به جای مفهوم "الفبا"، آنها از "ویندوز" استفاده می‌کنند و تعداد آنها از من بیشتر است). در عین حال، این قالب دارای معایبی نیز است: کمی به الگوریتم های فشرده سازی نسبت به الگوریتم های رمزگذاری نزدیک تر است. به طور خاص، استاندارد روش های نمایش بسیاری را ارائه می دهد، اما نحوه انتخاب بهینه را نمی گوید - برای این، رمزگذار باید از نوعی اکتشافی استفاده کند. بنابراین، یک رمزگذار SCSU که بسته بندی خوبی تولید می کند، پیچیده تر و دست و پا گیرتر از الگوریتم من خواهد بود.

برای مقایسه، من یک پیاده سازی نسبتا ساده از SCSU را به جاوا اسکریپت منتقل کردم - از نظر حجم کد با UTF-C من قابل مقایسه بود، اما در برخی موارد نتیجه ده ها درصد بدتر بود (گاهی اوقات ممکن است از آن فراتر رود، اما نه زیاد). به عنوان مثال، متون به زبان عبری و یونانی توسط UTF-C کدگذاری شدند 60 درصد بهتر از SCSU (احتمالاً به دلیل الفبای فشرده آنها).

به طور جداگانه، اضافه می کنم که علاوه بر SCSU روش دیگری نیز برای نمایش فشرده یونیکد وجود دارد - BOCU-1، اما هدف آن سازگاری با MIME است (که به آن نیازی نداشتم) و رویکرد کمی متفاوت برای رمزگذاری دارد. من اثربخشی آن را ارزیابی نکرده ام، اما به نظر من بعید است که از SCSU بالاتر باشد.

بهبودهای احتمالی

الگوریتمی که من ارائه کردم از نظر طراحی جهانی نیست (این احتمالاً جایی است که اهداف من بیشتر از اهداف کنسرسیوم یونیکد متفاوت است). قبلاً اشاره کردم که اساساً برای یک کار (ذخیره یک فرهنگ لغت چند زبانه در یک درخت پیشوند) ایجاد شده است و برخی از ویژگی های آن ممکن است برای کارهای دیگر مناسب نباشد. اما این واقعیت که استاندارد نیست می تواند یک مزیت باشد - شما به راحتی می توانید آن را مطابق با نیاز خود تغییر دهید.

به عنوان مثال، به روشی واضح می توانید از حضور حالت خلاص شوید، کدنویسی بدون حالت انجام دهید - فقط متغیرها را به روز نکنید offs, auxOffs и is21Bit در رمزگذار و رمزگشا. در این حالت، بسته بندی موثر دنباله هایی از کاراکترهای الفبای یکسان امکان پذیر نخواهد بود، اما تضمینی وجود خواهد داشت که یک کاراکتر بدون در نظر گرفتن زمینه، همیشه با بایت های یکسان رمزگذاری شود.

علاوه بر این، می‌توانید با تغییر حالت پیش‌فرض، رمزگذار را به یک زبان خاص تنظیم کنید - به عنوان مثال، تمرکز بر متون روسی، رمزگذار و رمزگشا را در ابتدا تنظیم کنید. offs = 0x0400 и auxOffs = 0. این به ویژه در مورد حالت بدون حالت منطقی است. به طور کلی، این شبیه به استفاده از رمزگذاری هشت بیتی قدیمی است، اما بدون حذف قابلیت درج کاراکترها از تمام یونیکد در صورت نیاز.

یکی دیگر از اشکالاتی که قبلا ذکر شد این است که در متن بزرگ کدگذاری شده در UTF-C هیچ راه سریعی برای یافتن مرز کاراکتر نزدیک به یک بایت دلخواه وجود ندارد. اگر آخرین مثلاً 100 بایت را از بافر رمزگذاری شده قطع کنید، خطر به دست آوردن زباله هایی را دارید که نمی توانید با آنها کاری انجام دهید. رمزگذاری برای ذخیره گزارش های چند گیگابایتی طراحی نشده است، اما به طور کلی می توان آن را اصلاح کرد. بایت 0xBF هرگز نباید به عنوان اولین بایت ظاهر شود (اما ممکن است دوم یا سوم باشد). بنابراین، هنگام رمزگذاری، می توانید دنباله را وارد کنید 0xBF 0xBF 0xBF هر، مثلاً 10 کیلوبایت - سپس، اگر نیاز به یافتن یک مرز دارید، کافی است قطعه انتخاب شده را اسکن کنید تا یک نشانگر مشابه پیدا شود. به دنبال آخرین 0xBF تضمین می شود که شروع یک شخصیت باشد. (البته هنگام رمزگشایی، این توالی سه بایتی باید نادیده گرفته شود.)

مجموع

اگر تا اینجا خوانده اید، به شما تبریک می گویم! امیدوارم شما نیز مانند من چیز جدیدی در مورد ساختار یونیکد یاد گرفته باشید (یا حافظه خود را تازه کرده باشید).

صفحه نمایشی. مثال عبری مزایای هر دو UTF-8 و SCSU را نشان می دهد.

تحقیقات فوق الذکر نباید به عنوان تجاوز به استانداردها در نظر گرفته شود. با این حال، من به طور کلی از نتایج کار خود راضی هستم، بنابراین از آنها راضی هستم سهم: برای مثال، یک کتابخانه JS کوچک شده تنها 1710 بایت وزن دارد (و البته هیچ وابستگی ندارد). همانطور که در بالا ذکر کردم، آثار او را می توان در پیدا کرد صفحه نمایشی (همچنین مجموعه ای از متون وجود دارد که می توان آن را با UTF-8 و SCSU مقایسه کرد).

در نهایت، من یک بار دیگر توجه را به مواردی که در آن از UTF-C استفاده می شود، جلب می کنم ارزشش را ندارد:

• اگر خطوط شما به اندازه کافی طولانی باشد (از 100 تا 200 کاراکتر). در این صورت باید به فکر استفاده از الگوریتم های فشرده سازی مانند deflate باشید.
• اگر لازم داری شفافیت ASCII، یعنی برای شما مهم است که دنباله های کدگذاری شده حاوی کدهای اسکی نباشند که در رشته اصلی نبوده اند. اگر هنگام تعامل با API های شخص ثالث (مثلاً کار با پایگاه داده)، نتیجه رمزگذاری را به عنوان مجموعه ای انتزاعی از بایت ها و نه به عنوان رشته ها ارسال کنید، می توان از نیاز به این امر اجتناب کرد. در غیر این صورت، خطر ابتلا به آسیب پذیری های غیرمنتظره را دارید.
• اگر می خواهید بتوانید به سرعت مرزهای کاراکترها را در یک افست دلخواه پیدا کنید (مثلاً وقتی بخشی از یک خط آسیب دیده است). این کار را می توان انجام داد، اما فقط با اسکن خط از ابتدا (یا اعمال اصلاحی که در بخش قبل توضیح داده شد).
• اگر نیاز به انجام سریع عملیات روی محتویات رشته ها دارید (آنها را مرتب کنید، زیر رشته ها را در آنها جستجو کنید، به هم متصل کنید). این مستلزم این است که ابتدا رشته ها رمزگشایی شوند، بنابراین UTF-C در این موارد کندتر از UTF-8 خواهد بود (اما سریعتر از الگوریتم های فشرده سازی). از آنجایی که رشته یکسان همیشه به یک شکل رمزگذاری می شود، مقایسه دقیق رمزگشایی لازم نیست و می توان آن را بر اساس بایت به بایت انجام داد.

به روز رسانی: کاربر تیومیچ در نظرات زیر نموداری را ارسال کرد که محدودیت‌های کاربردی UTF-C را برجسته می‌کرد. این نشان می دهد که UTF-C کارآمدتر از یک الگوریتم فشرده سازی همه منظوره (تغییر LZW) است تا زمانی که رشته بسته بندی شده کوتاهتر باشد. ~ 140 کاراکتر (با این حال، توجه می کنم که مقایسه در یک متن انجام شد؛ برای زبان های دیگر، نتیجه ممکن است متفاوت باشد).


منبع: www.habr.com