ترميز متغير الطول

في نظرية الترميز ، يُعد الترميز ذو الطول المتغير نوعًا من أنظمة ترميز الأحرف ، حيث تُستخدم رموز ذات أطوال مختلفة لترميز مجموعة من الأحرف (مجموعة من الرموز) لتمثيلها في الحاسوب . ^{[ 1 ]} المفهوم المكافئ في علوم الحاسوب هو سلسلة البتات .

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

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

عادةً ما تنتج ترميزات متعددة البايتات عن الحاجة إلى زيادة عدد الأحرف التي يمكن ترميزها دون الإخلال بالتوافق مع الأنظمة القائمة. على سبيل المثال، باستخدام بايت واحد (8 بتات) لكل حرف، يمكن ترميز 256 حرفًا ممكنًا؛ ولترميز أكثر من 256 حرفًا، يكون الخيار الأمثل هو استخدام بايتين أو أكثر لكل وحدة ترميز، حيث يسمح بايتان (16 بتًا) بترميز 65536 حرفًا ممكنًا، ولكن هذا التغيير سيؤدي إلى الإخلال بالتوافق مع الأنظمة الحالية، وبالتالي قد لا يكون عمليًا ^{على الإطلاق .}

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

الهيكل العام

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

على سبيل المثال، تُشفّر السلسلة المكونة من أربعة أحرف " I♥NY " في ترميز UTF-8 على النحو التالي (موضحة كقيم بايت سداسية عشرية ): 49 E2 99 A5 4E 59. من بين الوحدات الست في هذا التسلسل، تُمثل 49 و 4E و 59 أحرفًا منفردة (ترمز إلى I و N و Y على التوالي )، بينما تُمثل E2 وحدة البداية، و 99 و A5 وحدتي النهاية. يُرمز إلى رمز القلب بدمج وحدة البداية ووحدتي النهاية.

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

الرموز وامتداداتها

امتداد الشفرة هو عملية تحويل متواليات المصدر ذات الطول المحدود إلى سلاسل بتات ذات طول محدود، ويتم ذلك عن طريق دمج كل رمز من رموز متواليات المصدر مع الكلمة المشفرة المقابلة الناتجة عن الشفرة الأصلية. باستخدام مصطلحات من نظرية اللغات الرسمية ، يكون التعريف الرياضي الدقيق كما يلي: ليكن $S$ و $T$ لنفترض مجموعتين منتهيتين، تُسميان أبجديات المصدر وأبجديات الهدف على التوالي. رمز $C:S\to T^{*}$ هي دالة كلية ^{[ 2 ]} تربط كل رمز من $S$ إلى سلسلة من الرموز على $T$ وامتداد $C$ إلى تماثل من $S^{*}$ داخل $T^{*}$ يُشار إلى هذه العملية، التي تربط بشكل طبيعي كل تسلسل من رموز المصدر بتسلسل من رموز الهدف، باسم امتدادها .

يمكن تصنيف الرموز ذات الطول المتغير بشكل متداخل تمامًا بترتيب تنازلي للعمومية إلى رموز غير منفردة، ورموز قابلة للفك بشكل فريد، ورموز بادئة. تكون رموز البادئة دائمًا قابلة للفك بشكل فريد، وهذه بدورها تكون دائمًا غير منفردة.

الرموز غير المفردة

يكون الكود غير منفرد إذا تم تعيين كل رمز مصدر إلى سلسلة بتات مختلفة غير فارغة؛ أي أن التعيين من رموز المصدر إلى سلاسل البتات يكون أحاديًا .

على سبيل المثال، عملية رسم الخرائط $M_{1}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {0}},{\texttt {c}}\mapsto {\texttt {1}}\,\}$ لا يُعدّ هذا الترميز غير منفرد لأن كلاً من a و b يُشيران إلى نفس سلسلة البتات 0 ؛ وأي توسيع لهذا الربط سيُنتج ترميزًا مع فقدان (وليس بدون فقدان). قد يظل هذا الترميز المنفرد مفيدًا عندما يكون فقدان بعض المعلومات مقبولًا (على سبيل المثال، عند استخدام هذا الترميز في ضغط الصوت أو الفيديو، حيث يصبح الترميز مع فقدان مكافئًا لتكميم المصدر ) .

ومع ذلك، فإن عملية رسم الخرائط $M_{2}=\{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}},{\texttt {f}}\mapsto {\texttt {0}}\}$ هو غير منفرد؛ وسيؤدي امتداده إلى توليد ترميز غير فاقد للبيانات، وهو أمر مفيد لنقل البيانات بشكل عام (لكن هذه الميزة ليست مطلوبة دائمًا). ليس من الضروري أن يكون الترميز غير المنفرد أكثر إحكامًا من المصدر (وفي العديد من التطبيقات، يكون الترميز الأكبر حجمًا مفيدًا، على سبيل المثال كوسيلة لاكتشاف أخطاء الترميز أو الإرسال أو التعافي منها، أو في تطبيقات الأمان لحماية المصدر من التلاعب غير القابل للكشف).

رموز قابلة للفك بشكل فريد

تكون الشفرة قابلة للفك بشكل فريد إذا كان امتدادها غير منفرد . ويمكن تحديد ما إذا كانت شفرة معينة قابلة للفك بشكل فريد باستخدام خوارزمية سارديناس-باترسون .

رسم الخرائط $M_{3}=\{\,{\texttt {a}}\mapsto {\texttt {0}},{\texttt {b}}\mapsto {\texttt {01}},{\texttt {c}}\mapsto {\texttt {011}}\,\}$ يمكن فك تشفيرها بشكل فريد (يمكن إثبات ذلك من خلال النظر إلى مجموعة المتابعات بعد كل سلسلة بتات مستهدفة في الخريطة، لأن كل سلسلة بتات تنتهي بمجرد أن نرى ${\texttt {0}}$ (الجزء الذي لا يمكنه اتباع أي رمز موجود لإنشاء رمز صالح أطول في الخريطة، ولكنه يبدأ بشكل لا لبس فيه رمزًا جديدًا).

أعد النظر في الكود $M_{2}$ من القسم السابق. ^{[ 2 ]} لا يمكن فك تشفير هذا الرمز بشكل فريد، إذ يمكن تفسير السلسلة 011101110011 على أنها سلسلة من الكلمات المشفرة 01110 – 1110 – 011 ، وكذلك على أنها سلسلة من الكلمات المشفرة 011 – 1 – 011 – 10011. وبالتالي، يُقدم كل من cdb و babe طريقتين محتملتين لفك تشفير هذه السلسلة المشفرة . مع ذلك، يُعد هذا الرمز مفيدًا عندما تكون مجموعة جميع رموز المصدر الممكنة معروفة تمامًا ومحدودة، أو عندما توجد قيود (مثل صيغة رسمية) تُحدد ما إذا كانت عناصر المصدر لهذا الامتداد مقبولة. تسمح هذه القيود بفك تشفير الرسالة الأصلية عن طريق التحقق من أي من رموز المصدر الممكنة المُرتبطة بنفس الرمز صالحة في ظل هذه القيود.

رموز البادئة

يُسمى الرمز رمزًا بادئًا إذا لم تكن أي سلسلة بتات مستهدفة في عملية الربط بادئةً لسلسلة بتات مستهدفة لرمز مصدر مختلف في نفس عملية الربط. هذا يعني أنه يمكن فك تشفير الرموز فورًا بعد استلام كلمة الترميز كاملةً. ومن الأسماء الشائعة الأخرى لهذا المفهوم: الرمز الخالي من البادئات ، والرمز الفوري ، والرمز الخالي من السياق . ومن الحالات الخاصة للرموز البادئة: رموز الكتل ، و LEB128 ، ورموز الكمية ذات الطول المتغير (VLQ).

على سبيل المثال، عملية رسم الخرائط $M_{3}$ ما سبق ليس رمزًا بادئًا، لأننا لا نعرف بعد قراءة سلسلة البتات 0 ما إذا كانت تُشفّر رمز المصدر a ، أو ما إذا كانت بادئة لتشفير الرموز b أو c . يُعرض أدناه مثال على رمز بادئ.

رمز	كلمة السر
أ	0
ب	10
ج	110
د	111

مثال على التشفير وفك التشفير:

اباكداب → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → ابكداب

في هذا المثال، إذا كانت احتمالات $({\texttt {a}},{\texttt {b}},{\texttt {c}},{\texttt {d}})$ كان $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ ، سيكون عدد البتات المتوقع استخدامها لتمثيل رمز المصدر باستخدام الكود أعلاه كما يلي:

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

بما أن إنتروبيا هذا المصدر هي 1.75 بت لكل رمز، فإن هذا الكود يضغط المصدر قدر الإمكان بحيث يمكن استعادة المصدر بدون أي خطأ.

انظر أيضاً

شفرة غولومب
عدّ كروسكال
بنية مجموعة التعليمات § طول التعليمات في الحوسبة
wchar_t الأحرف العريضة
مجموعة أحرف لوتس متعددة البايت (LMBCS)
مجموعة الأحرف ثلاثية البايت (TBCS)
مجموعة الأحرف ثنائية البايت (DBCS)
مجموعة الأحرف أحادية البايت (SBCS)

ملحوظات

↑ كمثال واقعي على ذلك، فإن UTF-16 ، الذي يمثل الأحرف الأكثر شيوعًا بالطريقة الموصوفة للتو (ويستخدم أزواجًا من وحدات الترميز 16 بت للأحرف الأقل شيوعًا) لم يكتسب أبدًا زخمًا كترميز للنصوص المخصصة للتبادل بسبب عدم توافقه مع ترميز ASCII المنتشر 7/8 بت ، حيث تم أخذ دوره المقصود بدلاً من ذلك بواسطة UTF-8 ، الذي يحافظ على توافق ASCII.

مراجع

↑ كريسبين، م. (2005-04-01). تنسيقات التحويل الفعالة لليونيكود UTF-9 وUTF-18 . IETF . doi : 10.17487/rfc4042 .
1 2 يستند هذا الكود إلى مثال موجود في Berstel et al. (2009)، المثال 2.3.1، ص. 63.

للمزيد من القراءة

سالومون، ديفيد (سبتمبر 2007). رموز متغيرة الطول لضغط البيانات ( الطبعة الأولى). دار نشر سبرينغر . رقم ISBN 978-1-84628-958-3.(12+191 صفحة) الأخطاء 1 الأخطاء 2
بيرستل، جان؛ بيرين، دومينيك؛ رويتناور، كريستوف (2010). الشفرات والآلات . موسوعة الرياضيات وتطبيقاتها. المجلد 129. كامبريدج، المملكة المتحدة: مطبعة جامعة كامبريدج . ISBN 978-0-521-88831-8. Zbl 1187.94001 . مسودة متاحة عبر الإنترنت

[2] كمثال واقعي على ذلك، فإن UTF-16 ، الذي يمثل الأحرف الأكثر شيوعًا بالطريقة الموصوفة للتو (ويستخدم أزواجًا من وحدات الترميز 16 بت للأحرف الأقل شيوعًا) لم يكتسب أبدًا زخمًا كترميز للنصوص المخصصة للتبادل بسبب عدم توافقه مع ترميز ASCII المنتشر 7/8 بت ، حيث تم أخذ دوره المقصود بدلاً من ذلك بواسطة UTF-8 ، الذي يحافظ على توافق ASCII.

[1] كريسبين، م. (2005-04-01). تنسيقات التحويل الفعالة لليونيكود UTF-9 وUTF-18 . IETF . doi : 10.17487/rfc4042 .

[:0-3] 1 2 يستند هذا الكود إلى مثال موجود في Berstel et al. (2009)، المثال 2.3.1، ص. 63.

[ 1 ]

على الإطلاق .