دراجة أخرى: نقوم بتخزين سلاسل Unicode أكثر إحكاما بنسبة 30-60٪ من UTF-8

إذا كنت مطورًا وتواجه مهمة اختيار التشفير، فسيكون Unicode دائمًا هو الحل الصحيح. تعتمد طريقة التمثيل المحددة على السياق، ولكن في أغلب الأحيان توجد إجابة عالمية هنا أيضًا - UTF-8. والشيء الجيد في الأمر هو أنه يسمح لك باستخدام جميع أحرف Unicode دون إنفاق كثير جدا الكثير من البايتات في معظم الحالات. صحيح، بالنسبة للغات التي تستخدم أكثر من مجرد الأبجدية اللاتينية، فإن عبارة "ليس كثيرًا" هي على الأقل بايتين لكل حرف. هل يمكننا أن نفعل ما هو أفضل دون العودة إلى ترميزات ما قبل التاريخ التي تقصرنا على 256 حرفًا متاحًا فقط؟

أقترح أدناه التعرف على محاولتي للإجابة على هذا السؤال وتنفيذ خوارزمية بسيطة نسبيًا تسمح لك بتخزين الخطوط في معظم لغات العالم دون إضافة التكرار الموجود في UTF-8.

تنصل. سأبدي على الفور بعض التحفظات المهمة: لا يتم تقديم الحل الموصوف كبديل عالمي لـ UTF-8، فهو مناسب فقط في قائمة ضيقة من الحالات (المزيد عنها أدناه)، ولا ينبغي بأي حال من الأحوال استخدامه للتفاعل مع واجهات برمجة التطبيقات التابعة لجهات خارجية (والتي لا تعرف عنها حتى). في أغلب الأحيان، تكون خوارزميات الضغط ذات الأغراض العامة (على سبيل المثال، التفريغ) مناسبة للتخزين المدمج لكميات كبيرة من البيانات النصية. بالإضافة إلى ذلك، في عملية إنشاء الحل الخاص بي، وجدت معيارًا موجودًا في Unicode نفسه، والذي يحل نفس المشكلة - إنه أكثر تعقيدًا إلى حد ما (وغالبًا ما يكون أسوأ)، ولكنه لا يزال معيارًا مقبولًا، وليس فقط وضعه معا على الركبة. سأخبرك عنه أيضًا.

حول Unicode وUTF-8

لتبدأ، بضع كلمات حول ما هو عليه يونيكود и UTF-8.

كما تعلمون، كانت ترميزات 8 بت شائعة. معهم، كان كل شيء بسيطًا: يمكن ترقيم 256 حرفًا بأرقام من 0 إلى 255، ومن الواضح أنه يمكن تمثيل الأرقام من 0 إلى 255 كبايت واحد. إذا عدنا إلى البداية، فإن ترميز ASCII يقتصر تمامًا على 7 بتات، وبالتالي فإن البت الأكثر أهمية في تمثيل البايت الخاص به هو صفر، ومعظم ترميزات 8 بت متوافقة معه (تختلف فقط في "العلوي" الجزء، حيث الجزء الأكثر أهمية هو واحد).

كيف يختلف Unicode عن تلك الترميزات ولماذا يرتبط به الكثير من التمثيلات المحددة - UTF-8، UTF-16 (BE وLE)، UTF-32؟ دعونا فرزها بالترتيب.

يصف معيار Unicode الأساسي فقط المراسلات بين الأحرف (وفي بعض الحالات، المكونات الفردية للأحرف) وأرقامها. وهناك الكثير من الأرقام المحتملة في هذا المعيار - من 0x00 إلى 0x10FFFF (1 قطعة). إذا أردنا وضع رقم في هذا النطاق في متغير، فلن يكون 114 أو 112 بايت كافيين بالنسبة لنا. وبما أن معالجاتنا ليست مصممة للعمل مع أرقام مكونة من ثلاثة بايت، فسنضطر إلى استخدام ما يصل إلى 1 بايت لكل حرف! هذا هو UTF-2، ولكن بسبب هذا "التبذير" على وجه التحديد، لا يحظى هذا التنسيق بشعبية.

لحسن الحظ، ترتيب الأحرف داخل Unicode ليس عشوائيًا. مجموعتهم بأكملها مقسمة إلى 17 "طائرات"، كل منها يحتوي على 65536 (0x10000) «نقاط الكود" مفهوم "نقطة الكود" هنا بسيط رقم الحرف، تم تعيينه له بواسطة Unicode. ولكن، كما ذكر أعلاه، في Unicode، لا يتم ترقيم الأحرف الفردية فحسب، بل يتم أيضًا ترقيم مكوناتها وعلامات الخدمة (وأحيانًا لا شيء يتوافق مع الرقم على الإطلاق - ربما في الوقت الحالي، لكن هذا ليس مهمًا جدًا بالنسبة لنا)، لذلك فمن الأصح الحديث دائمًا على وجه التحديد عن عدد الأرقام نفسها، وليس الرموز. ومع ذلك، في ما يلي، من أجل الإيجاز، سأستخدم في كثير من الأحيان كلمة "رمز"، مما يعني ضمنا مصطلح "نقطة الرمز".

طائرات يونيكود. كما ترون، فإن معظمها (الطائرات من 4 إلى 13) لا تزال غير مستخدمة.

والأمر الأكثر لفتًا للنظر هو أن كل "اللب" الرئيسي يقع في المستوى الصفري، وهو ما يسمى "طائرة أساسية متعددة اللغات". إذا كان السطر يحتوي على نص بإحدى اللغات الحديثة (بما في ذلك اللغة الصينية)، فلن تتجاوز هذه الطائرة. ولكن لا يمكنك قطع بقية Unicode أيضًا - على سبيل المثال، توجد الرموز التعبيرية بشكل أساسي في نهاية الطائرة التالية"طائرة تكميلية متعددة اللغات"(يمتد من 0x10000 إلى 0x1FFFF). لذلك يقوم UTF-16 بهذا: جميع الأحرف تقع داخله طائرة أساسية متعددة اللغات، يتم ترميزها "كما هي" برقم مطابق مكون من بايتين. ومع ذلك، فإن بعض الأرقام في هذا النطاق لا تشير إلى أحرف محددة على الإطلاق، ولكنها تشير إلى أنه بعد هذا الزوج من البايتات نحتاج إلى النظر في واحد آخر - من خلال الجمع بين قيم هذه البايتات الأربع معًا، نحصل على رقم يغطي نطاق Unicode الصالح بأكمله. تُسمى هذه الفكرة "الأزواج البديلين" - ربما سمعت عنهم.

لذا فإن UTF-16 يتطلب وحدتين أو (في حالات نادرة جدًا) أربع بايت لكل "نقطة رمز". وهذا أفضل من استخدام أربعة بايتات طوال الوقت، ولكن اللاتينية (وأحرف ASCII الأخرى) عند تشفيرها بهذه الطريقة تهدر نصف المساحة على الأصفار. تم تصميم UTF-8 لتصحيح هذا: ASCII فيه، كما كان من قبل، يحتل بايت واحد فقط؛ رموز من 0x80 إلى 0x7FF - بايتان؛ من 0x800 إلى 0xFFFF - ثلاثة ومن 0x10000 إلى 0x10FFFF - أربعة. من ناحية، أصبحت الأبجدية اللاتينية جيدة: لقد عاد التوافق مع ASCII، وأصبح التوزيع أكثر توازنا من 1 إلى 4 بايت. لكن الحروف الهجائية غير اللاتينية، للأسف، لا تستفيد بأي شكل من الأشكال مقارنة بـ UTF-16، ويتطلب الكثير منها الآن ثلاثة بايت بدلاً من اثنتين - وقد ضاق النطاق الذي يغطيه سجل ثنائي البايت بمقدار 32 مرة، مع 0xFFFF إلى 0x7FF، ولم يتم تضمينها في اللغة الصينية أو الجورجية على سبيل المثال. السيريلية وخمس أبجديات أخرى - يا هلا - محظوظ، 2 بايت لكل حرف.

لماذا يحدث هذا؟ دعونا نرى كيف يمثل UTF-8 رموز الأحرف:

لتمثيل الأرقام مباشرة، يتم استخدام البتات المميزة بالرمز هنا x. يمكن ملاحظة أنه في السجل ثنائي البايت يوجد 11 بت فقط (من أصل 16). البتات الرائدة هنا لها وظيفة مساعدة فقط. في حالة السجل المكون من أربعة بايت، يتم تخصيص 21 بت من أصل 32 بت لرقم نقطة الرمز - يبدو أن ثلاث بايتات (والتي تعطي إجمالي 24 بت) ستكون كافية، لكن علامات الخدمة تستهلك الكثير.

هل هذا سيء؟ ليس حقيقيًا. من ناحية، إذا كنا نهتم كثيرًا بالفضاء، فلدينا خوارزميات ضغط يمكنها بسهولة التخلص من كل الإنتروبيا الإضافية والتكرار. من ناحية أخرى، كان هدف Unicode هو توفير الترميز الأكثر شمولاً الممكن. على سبيل المثال، يمكننا أن نعهد إلى سطر مشفر بـ UTF-8 برمز كان يعمل سابقًا مع ASCII فقط، ولا نخشى أنه سيشاهد حرفًا من نطاق ASCII غير موجود فعليًا (بعد كل شيء، في UTF-8 كل شيء البايتات التي تبدأ بالبت صفر - وهذا هو بالضبط ما هو ASCII). وإذا أردنا فجأة قطع ذيل صغير من سلسلة كبيرة دون فك تشفيره من البداية (أو استعادة جزء من المعلومات بعد قسم تالف)، فمن السهل علينا العثور على الإزاحة حيث يبدأ الحرف (هذا يكفي لتخطي وحدات البايت التي لها بادئة صغيرة 10).

لماذا إذن نخترع شيئًا جديدًا؟

في الوقت نفسه، هناك أحيانًا مواقف تكون فيها خوارزميات الضغط مثل الانكماش غير قابلة للتطبيق بشكل جيد، ولكنك تريد تحقيق تخزين مضغوط للسلاسل. أنا شخصياً واجهت هذه المشكلة عندما فكرت في البناء شجرة البادئة المضغوطة لقاموس كبير يتضمن كلمات بلغات عشوائية. من ناحية، كل كلمة قصيرة جدًا، لذا فإن ضغطها لن يكون فعالاً. من ناحية أخرى، تم تصميم تنفيذ الشجرة الذي فكرت فيه بحيث يقوم كل بايت من السلسلة المخزنة بإنشاء قمة شجرة منفصلة، ​​لذلك كان تقليل عددها مفيدًا للغاية. في مكتبتي Az.js (كما في تقيح الجلد2، والتي يعتمد عليها) يمكن حل مشكلة مماثلة ببساطة - سلاسل معبأة فيها دوغ-القاموس المخزن هناك جيد CP1251 القديم. ولكن، كما هو واضح، فإن هذا يعمل بشكل جيد فقط مع أبجدية محدودة - لا يمكن إضافة سطر باللغة الصينية إلى مثل هذا القاموس.

بشكل منفصل، أود أن أشير إلى فارق بسيط آخر غير سارة ينشأ عند استخدام UTF-8 في بنية البيانات هذه. توضح الصورة أعلاه أنه عندما يتم كتابة حرف ما على شكل بايتين، فإن البتات المرتبطة برقمه لا تأتي في صف واحد، بل يتم فصلها بزوج من البتات 10 في المنتصف: 110xxxxx 10xxxxxx. ولهذا السبب، عند تجاوز الـ 6 بتات السفلية من البايت الثاني في رمز الحرف (أي يحدث انتقال 10111111 → 10000000)، ثم يتغير البايت الأول أيضًا. اتضح أن الحرف "p" يُشار إليه بالبايت 0xD0 0xBF، و"r" التالي موجود بالفعل 0xD1 0x80. في شجرة البادئة، يؤدي هذا إلى تقسيم العقدة الأصلية إلى قسمين - واحدة للبادئة 0xD0، وآخر ل 0xD1 (على الرغم من أنه لا يمكن تشفير الأبجدية السيريلية بأكملها إلا بالبايت الثاني).

ماذا حصلت

في مواجهة هذه المشكلة، قررت أن أمارس الألعاب باستخدام البتات، وفي الوقت نفسه أتعرف بشكل أفضل على بنية Unicode ككل. وكانت النتيجة تنسيق ترميز UTF-C ("C" لـ اتفاق)، والذي لا ينفق أكثر من 3 بايت لكل نقطة رمز، وغالبًا ما يسمح لك بالإنفاق فقط بايت إضافي واحد للخط المشفر بأكمله. وهذا يؤدي إلى حقيقة أن هذا الترميز موجود في العديد من الأبجديات غير ASCII 30-60% أكثر إحكاما من UTF-8.

لقد قدمت أمثلة على تنفيذ خوارزميات التشفير وفك التشفير في النموذج مكتبات جافا سكريبت وGo، يمكنك استخدامها بحرية في التعليمات البرمجية الخاصة بك. لكنني سأظل أؤكد على أن هذا التنسيق يظل إلى حد ما "دراجة"، ولا أوصي باستخدامه دون أن تدرك سبب حاجتك إليه. لا تزال هذه تجربة أكثر من كونها "تحسينًا جديًا لـ 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 بايت لكل حرف.

أدخل حالة التشفير

دعونا الآن نفكر في خصائص الخطوط نفسها. يحتوي القاموس في أغلب الأحيان على كلمات مكتوبة بأحرف من نفس الأبجدية، وهذا ينطبق أيضًا على العديد من النصوص الأخرى. سيكون من الجيد الإشارة إلى هذه الأبجدية مرة واحدة، ثم الإشارة فقط إلى رقم الحرف الموجود بداخلها. دعونا نرى ما إذا كان ترتيب الأحرف في جدول Unicode سيساعدنا.

كما ذكر أعلاه، يتم تقسيم Unicode إلى طائرة 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. والفرق الوحيد هو أننا نقرأ الآن بايتين (لأننا تحولنا إلى هذا الوضع).

يبدو جيدًا: الآن بينما نحتاج إلى تشفير الأحرف من نفس نطاق Unicode ذو 7 بتات، فإننا ننفق بايتًا واحدًا إضافيًا في البداية وإجمالي بايت واحد لكل حرف.

العمل من أحد الإصدارات السابقة. غالبًا ما يتفوق على 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.

ولكن هنا تنشأ صعوبة: كيفية الحصول على حرف مساعد من الأبجدية الرئيسية؟ يمكنك ترك نفس الإزاحة، ولكن - للأسف - هنا تلعب بنية Unicode بالفعل ضدنا. في كثير من الأحيان، لا يكون الجزء الرئيسي من الأبجدية في بداية الكتلة (على سبيل المثال، يحتوي الحرف الكبير الروسي "A" على الرمز 0x0410، على الرغم من أن الكتلة السيريلية تبدأ بـ 0x0400). وبالتالي، بعد إدخال أول 64 حرفًا في المخبأ، قد نفقد إمكانية الوصول إلى الجزء الخلفي من الأبجدية.

لإصلاح هذه المشكلة، قمت يدويًا بمراجعة بعض الكتل المقابلة للغات مختلفة، وحددت إزاحة الأبجدية المساعدة داخل الأبجدية الرئيسية لها. تم إعادة ترتيب الأبجدية اللاتينية، كاستثناء، بشكل عام مثل base64.

اللمسات الأخيرة

دعونا نفكر أخيرًا في الأماكن الأخرى التي يمكننا من خلالها تحسين شيء ما.

لاحظ أن التنسيق 101xxxxx xxxxxxxx xxxxxxxx يسمح لك بتشفير أرقام تصل إلى 0x1FFFFF، وينتهي Unicode سابقًا، عند 0x10FFFF. وبعبارة أخرى، سيتم تمثيل نقطة الكود الأخيرة كـ 10110000 11111111 11111111. ولذلك يمكننا القول أنه إذا كان البايت الأول من النموذج 1011xxxx (أين xxxx أكبر من 0)، فهذا يعني شيئًا آخر. على سبيل المثال، يمكنك إضافة 15 حرفًا آخر متاحًا باستمرار للترميز ببايت واحد، لكنني قررت أن أفعل ذلك بشكل مختلف.

دعونا نلقي نظرة على كتل Unicode التي تتطلب ثلاثة بايت الآن. في الأساس، كما ذكرنا سابقًا، هذه أحرف صينية - لكن من الصعب فعل أي شيء بها، فهناك 21 ألفًا منها. لكن الهيراغانا والكاتاكانا طاروا أيضًا إلى هناك - ولم يعد هناك الكثير منهم، أقل من مائتي. وبما أننا نتذكر اللغة اليابانية، فهناك أيضًا رموز تعبيرية (في الواقع، فهي منتشرة في العديد من الأماكن في Unicode، ولكن الكتل الرئيسية موجودة في النطاق 0x1F300 - 0x1FBFF). إذا كنت تفكر في حقيقة أن هناك الآن رموز تعبيرية يتم تجميعها من عدة نقاط رمز في وقت واحد (على سبيل المثال، الرموز التعبيرية ‍‍‍) يتكون من ما يصل إلى 7 رموز!)، ومن ثم يصبح من العار تمامًا إنفاق ثلاث بايتات على كل منها (7 × 3 = 21 بايت من أجل رمز واحد، كابوس).

لذلك، نختار عددًا قليلًا من النطاقات المحددة المقابلة للرموز التعبيرية والهيراغانا والكاتاكانا، ونعيد ترقيمها في قائمة واحدة مستمرة وترميزها على شكل بايتين بدلاً من ثلاثة:

1011xxxx xxxxxxxx

عظيم: الرموز التعبيرية ‍‍‍ المذكورة أعلاه، الذي يتكون من 7 نقاط كود، يأخذ 8 بايت في UTF-25، ونقوم بتركيبه فيه 14 (بالضبط بايتان لكل نقطة رمز). بالمناسبة، رفض حبر هضمه (سواء في المحرر القديم أو الجديد)، لذلك اضطررت إلى إدراجه مع صورة.

دعونا نحاول إصلاح مشكلة أخرى. كما نتذكر، الأبجدية الأساسية هي في الأساس ارتفاع 6 بت، والتي نضعها في الاعتبار ونلصقها برمز كل رمز تم فك تشفيره بعد ذلك. في حالة الأحرف الصينية الموجودة في الكتلة 0x4E00 - 0x9FFF، هذا إما بت 0 أو 1. وهذا ليس مناسبًا جدًا: سنحتاج إلى تبديل الحروف الأبجدية باستمرار بين هاتين القيمتين (أي إنفاق ثلاث بايتات). لكن لاحظ أنه في الوضع الطويل، من الكود نفسه يمكننا طرح عدد الأحرف التي نقوم بتشفيرها باستخدام الوضع القصير (بعد كل الحيل الموضحة أعلاه، هذا هو 10240) - ثم ينتقل نطاق الحروف الهيروغليفية إلى 0x2600 - 0x77FF، وفي هذه الحالة، عبر هذا النطاق بأكمله، فإن أهم 6 بتات (من أصل 21) ستكون مساوية للصفر. وبالتالي، فإن تسلسل الحروف الهيروغليفية سيستخدم بايتين لكل هيروغليفية (وهو الأمثل لمثل هذا النطاق الكبير)، دون تسبب مفاتيح الأبجدية.

الحلول البديلة: SCSU، BOCU-1

من المرجح أن يسارع خبراء Unicode، بعد قراءة عنوان المقالة للتو، إلى تذكيرك أنه من بين معايير Unicode مباشرة يوجد نظام الضغط القياسي لـ Unicode (SCSU)، الذي يصف طريقة تشفير مشابهة جدًا لتلك الموضحة في المقالة.

أعترف بصراحة: أنني لم أعرف بوجوده إلا بعد أن كنت منغمساً في كتابة قراري. لو علمت بالأمر منذ البداية، لربما كنت سأحاول كتابة تطبيق بدلاً من التوصل إلى نهج خاص بي.

الأمر المثير للاهتمام هو أن جامعة SCSU تستخدم أفكارًا مشابهة جدًا لتلك التي توصلت إليها بمفردي (بدلاً من مفهوم "الحروف الهجائية" يستخدمون "النوافذ"، وهناك المزيد منها متاح أكثر مما لدي). في الوقت نفسه، هذا التنسيق له أيضًا عيوب: فهو أقرب قليلاً إلى خوارزميات الضغط من خوارزميات التشفير. على وجه الخصوص، يوفر المعيار العديد من طرق التمثيل، لكنه لا يذكر كيفية اختيار الطريقة الأمثل - ولهذا يجب على المشفر استخدام نوع من الاستدلال. وبالتالي، فإن جهاز التشفير SCSU الذي ينتج عبوات جيدة سيكون أكثر تعقيدًا ومرهقة من الخوارزمية الخاصة بي.

للمقارنة، قمت بنقل تطبيق SCSU بسيط نسبيًا إلى JavaScript - من حيث حجم التعليمات البرمجية، اتضح أنه مشابه لـ UTF-C الخاص بي، ولكن في بعض الحالات كانت النتيجة أسوأ بعشرات بالمائة (في بعض الأحيان قد تتجاوزها، ولكن ليس كثيرًا). على سبيل المثال، تم ترميز النصوص بالعبرية واليونانية باستخدام UTF-C 60% أفضل من SCSU (ربما بسبب الحروف الهجائية المدمجة).

بشكل منفصل، سأضيف أنه بالإضافة إلى SCSU، هناك أيضًا طريقة أخرى لتمثيل Unicode بشكل مضغوط - بوكو-1، ولكنه يهدف إلى التوافق مع MIME (وهو ما لم أكن بحاجة إليه) ويتبع أسلوبًا مختلفًا قليلاً في التشفير. لم أقم بتقييم فعاليته، ولكن يبدو لي أنه من غير المرجح أن يكون أعلى من SCSU.

التحسينات الممكنة

الخوارزمية التي قدمتها ليست عالمية من حيث التصميم (ربما يكون هذا هو المكان الذي تختلف فيه أهدافي كثيرًا عن أهداف Unicode Consortium). لقد ذكرت بالفعل أنه تم تطويره بشكل أساسي لمهمة واحدة (تخزين قاموس متعدد اللغات في شجرة بادئة)، وقد لا تكون بعض ميزاته مناسبة تمامًا لمهام أخرى. ولكن حقيقة أنه ليس معيارًا يمكن أن تكون ميزة إضافية - يمكنك تعديله بسهولة ليناسب احتياجاتك.

على سبيل المثال، بالطريقة الواضحة، يمكنك التخلص من وجود الحالة، وإنشاء ترميز عديم الحالة - فقط لا تقم بتحديث المتغيرات offs, auxOffs и is21Bit في التشفير وفك التشفير. في هذه الحالة، لن يكون من الممكن حزم تسلسلات الأحرف من نفس الأبجدية بشكل فعال، ولكن سيكون هناك ضمان بأن نفس الحرف يتم ترميزه دائمًا بنفس البايتات، بغض النظر عن السياق.

بالإضافة إلى ذلك، يمكنك تخصيص برنامج التشفير ليناسب لغة معينة عن طريق تغيير الحالة الافتراضية - على سبيل المثال، التركيز على النصوص الروسية، وضبط برنامج التشفير ووحدة فك التشفير في البداية offs = 0x0400 и auxOffs = 0. وهذا منطقي بشكل خاص في حالة وضع عديمي الجنسية. بشكل عام، سيكون هذا مشابهًا لاستخدام التشفير القديم ذي الثماني بتات، ولكن دون إزالة القدرة على إدراج أحرف من جميع Unicode حسب الحاجة.

عيب آخر تم ذكره سابقًا هو أنه في النص الكبير المشفر بـ UTF-C، لا توجد طريقة سريعة للعثور على حدود الأحرف الأقرب إلى البايت العشوائي. إذا قمت بقطع آخر 100 بايت، على سبيل المثال، من المخزن المؤقت المشفر، فإنك تخاطر بالحصول على القمامة التي لا يمكنك فعل أي شيء بها. لم يتم تصميم الترميز لتخزين سجلات متعددة الجيجابايت، ولكن بشكل عام يمكن تصحيح ذلك. بايت 0xBF يجب ألا يظهر أبدًا باعتباره البايت الأول (ولكن قد يكون الثاني أو الثالث). لذلك، عند الترميز، يمكنك إدراج التسلسل 0xBF 0xBF 0xBF كل، على سبيل المثال، 10 كيلو بايت - إذن، إذا كنت بحاجة إلى العثور على حدود، فسيكون ذلك كافيا لمسح القطعة المحددة حتى يتم العثور على علامة مماثلة. بعد الأخير 0xBF مضمون أن يكون بداية الشخصية. (عند فك التشفير، يجب بالطبع تجاهل هذا التسلسل المكون من ثلاث بايتات.)

إجمال

إذا كنت قد قرأت هذا الآن، تهانينا! أتمنى أن تكون، مثلي، قد تعلمت شيئًا جديدًا (أو أنعشت ذاكرتك) حول بنية Unicode.

الصفحة التجريبية. يوضح مثال اللغة العبرية المزايا التي يتميز بها كل من UTF-8 وSCSU.

لا ينبغي اعتبار البحث الموصوف أعلاه تعديًا على المعايير. ومع ذلك، أنا راضٍ بشكل عام عن نتائج عملي، لذلك أنا سعيد بها سهم: على سبيل المثال، تزن مكتبة JS المصغرة 1710 بايت فقط (وليس لها تبعيات بالطبع). كما ذكرت أعلاه، يمكن العثور على عملها في الصفحة التجريبية (توجد أيضًا مجموعة من النصوص التي يمكن مقارنتها بـ UTF-8 وSCSU).

أخيرًا، سألفت الانتباه مرة أخرى إلى الحالات التي يتم فيها استخدام UTF-C لا يستحق كل هذا العناء:

• إذا كانت سطورك طويلة بما يكفي (من 100-200 حرف). في هذه الحالة، يجب أن تفكر في استخدام خوارزميات الضغط مثل الانكماش.
• اذا احتجت شفافية ASCIIأي أنه من المهم بالنسبة لك ألا تحتوي التسلسلات المشفرة على رموز ASCII التي لم تكن موجودة في السلسلة الأصلية. يمكن تجنب الحاجة إلى ذلك إذا قمت، عند التفاعل مع واجهات برمجة تطبيقات الطرف الثالث (على سبيل المثال، العمل مع قاعدة بيانات)، بتمرير نتيجة التشفير كمجموعة مجردة من البايتات، وليس كسلاسل. وإلا فإنك تخاطر بالحصول على نقاط ضعف غير متوقعة.
• إذا كنت تريد أن تكون قادرًا على العثور بسرعة على حدود الأحرف عند إزاحة عشوائية (على سبيل المثال، عند تلف جزء من السطر). ويمكن القيام بذلك، ولكن فقط عن طريق مسح السطر من البداية (أو تطبيق التعديل الموضح في القسم السابق).
• إذا كنت بحاجة إلى إجراء عمليات بسرعة على محتويات السلاسل (فرزها، والبحث عن سلاسل فرعية فيها، وتسلسلها). يتطلب هذا فك تشفير السلاسل أولاً، لذا سيكون UTF-C أبطأ من UTF-8 في هذه الحالات (لكنه أسرع من خوارزميات الضغط). نظرًا لأن نفس السلسلة يتم تشفيرها دائمًا بنفس الطريقة، فلا يلزم إجراء مقارنة دقيقة لفك التشفير ويمكن إجراؤها على أساس بايت بايت.

تحديث: المستخدم تييوميتش في التعليقات أدناه نشر رسمًا بيانيًا يسلط الضوء على حدود قابلية تطبيق UTF-C. يوضح أن UTF-C أكثر كفاءة من خوارزمية الضغط للأغراض العامة (أحد أشكال LZW) طالما أن السلسلة المعبأة أقصر ~140 حرفًا (ومع ذلك، ألاحظ أن المقارنة أجريت على نص واحد، وبالنسبة للغات الأخرى قد تختلف النتيجة).


المصدر: www.habr.com