مقدمة إلى ترميز إلياس
في عالم الاتصالات الرقمية وضغط البيانات، يلعب ترميز إلياس دورًا حيويًا. يُعدّ ترميز إلياس عائلة من تقنيات الترميز غير الضائعة التي طُوّرت لتمثيل الأعداد الصحيحة الموجبة بطريقة فعالة، خاصةً عندما تكون بعض القيم أكثر احتمالًا من غيرها. الفكرة الرئيسية وراء ترميز إلياس هي تعيين رموز أقصر للأعداد الأكثر تكرارًا، مما يؤدي إلى تقليل متوسط طول الرمز وبالتالي تحقيق ضغط أفضل للبيانات.
هناك نوعان رئيسيان من ترميز إلياس:
- ترميز شانُون-فانو-إلياس (Shannon–Fano–Elias Coding)
- ترميز إلياس جاما (Elias Gamma Coding)
سنتناول كل نوع من هذه الأنواع بالتفصيل، مع شرح مبادئ عملها وخصائصها وتطبيقاتها.
ترميز شانُون-فانو-إلياس (Shannon–Fano–Elias Coding)
ترميز شانُون-فانو-إلياس هو طريقة لإنشاء رمز بادئة فريد (prefix code) بناءً على الاحتمالات التراكمية للرموز المراد ترميزها. على عكس ترميز هوفمان، الذي يبني الشجرة من الأسفل إلى الأعلى، فإن ترميز شانُون-فانو-إلياس يبنيها من الأعلى إلى الأسفل. هذه الطريقة مناسبة بشكل خاص عندما تكون الاحتمالات معروفة مسبقًا.
آلية العمل:
- حساب الاحتمالات التراكمية: لنفترض أن لدينا مجموعة من الرموز {x1, x2, …, xn} مع احتمالات {p1, p2, …, pn} على التوالي. نقوم بحساب الاحتمالات التراكمية Fi لكل رمز xi كالتالي:
- F1 = p1/2
- F2 = p1 + p2/2
- F3 = p1 + p2 + p3/2
- وهكذا…
- Fn = p1 + p2 + … + pn/2
- تمثيل الاحتمالات التراكمية في النظام الثنائي: نقوم بتمثيل كل احتمال تراكمي Fi في النظام الثنائي.
- تحديد طول الرمز: طول الرمز لكل رمز xi يتم تحديده بناءً على الاحتمال pi كالتالي: length(xi) = ceiling(-log2(pi))، حيث ceiling(x) هي دالة السقف التي تعطي أصغر عدد صحيح أكبر من أو يساوي x.
- اقتطاع التمثيل الثنائي: نقوم باقتطاع التمثيل الثنائي لـ Fi إلى length(xi) خانة بعد الفاصلة العشرية. الرمز الناتج هو رمز xi.
مثال:
لنفترض أن لدينا أربعة رموز A و B و C و D باحتمالات 0.4 و 0.3 و 0.2 و 0.1 على التوالي. لنقم بتطبيق ترميز شانُون-فانو-إلياس:
- حساب الاحتمالات التراكمية:
- FA = 0.4/2 = 0.2
- FB = 0.4 + 0.3/2 = 0.55
- FC = 0.4 + 0.3 + 0.2/2 = 0.8
- FD = 0.4 + 0.3 + 0.2 + 0.1/2 = 0.95
- تمثيل الاحتمالات التراكمية في النظام الثنائي:
- FA = 0.2 = 0.00110011…
- FB = 0.55 = 0.10001100…
- FC = 0.8 = 0.11001100…
- FD = 0.95 = 0.11110011…
- تحديد طول الرمز:
- length(A) = ceiling(-log2(0.4)) = 2
- length(B) = ceiling(-log2(0.3)) = 2
- length(C) = ceiling(-log2(0.2)) = 3
- length(D) = ceiling(-log2(0.1)) = 4
- اقتطاع التمثيل الثنائي:
- رمز A = 0.00
- رمز B = 0.10
- رمز C = 0.110
- رمز D = 0.1111
مزايا وعيوب ترميز شانُون-فانو-إلياس:
المزايا:
- سهولة التنفيذ والفهم.
- لا يتطلب معرفة مسبقة بالشجرة الاحتمالية كما هو الحال في ترميز هوفمان.
- مناسب للحالات التي تكون فيها الاحتمالات معروفة مسبقًا.
العيوب:
- قد لا يكون فعالاً مثل ترميز هوفمان في تحقيق ضغط مثالي، خاصةً عندما تكون الاحتمالات غير متوازنة.
ترميز إلياس جاما (Elias Gamma Coding)
ترميز إلياس جاما هو نوع آخر من ترميز إلياس يُستخدم لتمثيل الأعداد الصحيحة الموجبة. يتميز ببساطته وسهولة تنفيذه، مما يجعله مناسبًا للتطبيقات التي تتطلب سرعة وكفاءة في الترميز وفك الترميز.
آلية العمل:
لترميز عدد صحيح موجب N باستخدام ترميز إلياس جاما، نتبع الخطوات التالية:
- تمثيل العدد في النظام الثنائي: نكتب العدد N في صورته الثنائية.
- تحديد طول التمثيل الثنائي: نحدد طول التمثيل الثنائي للعدد N، وليكن L.
- ترميز الطول: نقوم بترميز الطول L-1 باستخدام سلسلة من الأصفار متبوعة بواحد. على سبيل المثال، إذا كان L=5، فإن ترميز الطول سيكون “00001”.
- إلحاق التمثيل الثنائي: نلحق التمثيل الثنائي للعدد N (بدون البت الأكثر أهمية) بترميز الطول الذي قمنا بإنشائه في الخطوة السابقة.
مثال:
لنفترض أننا نريد ترميز العدد 10 باستخدام ترميز إلياس جاما:
- تمثيل العدد في النظام الثنائي: 10 = 1010
- تحديد طول التمثيل الثنائي: L = 4
- ترميز الطول: ترميز الطول هو 4-1 = 3 أصفار متبوعة بواحد: “0001”
- إلحاق التمثيل الثنائي: نلحق الجزء “010” (التمثيل الثنائي بدون البت الأكثر أهمية) بترميز الطول: “0001010”
إذن، ترميز إلياس جاما للعدد 10 هو “0001010”.
فك الترميز:
لفك ترميز سلسلة إلياس جاما، نتبع الخطوات التالية:
- قراءة الأصفار: نقرأ سلسلة الأصفار حتى نصل إلى الواحد. عدد الأصفار يمثل L-1.
- حساب الطول: نضيف 1 إلى عدد الأصفار للحصول على الطول L.
- قراءة البتات: نقرأ L-1 بتات التالية بعد الواحد.
- إعادة بناء العدد: نضيف 2^(L-1) إلى العدد المكون من البتات المقروءة في الخطوة السابقة للحصول على العدد الأصلي.
مزايا وعيوب ترميز إلياس جاما:
المزايا:
- بساطة التنفيذ وسهولة الفهم.
- مناسب لتمثيل الأعداد الصحيحة الموجبة الصغيرة.
- لا يتطلب معرفة مسبقة بالاحتمالات.
العيوب:
- غير فعال لتمثيل الأعداد الصحيحة الموجبة الكبيرة، حيث يزداد طول الرمز بشكل كبير مع زيادة قيمة العدد.
تطبيقات ترميز إلياس
تُستخدم تقنيات ترميز إلياس في مجموعة متنوعة من التطبيقات، بما في ذلك:
- ضغط البيانات: تستخدم في خوارزميات ضغط البيانات لتمثيل الأعداد الصحيحة بكفاءة.
- فهرسة النصوص: تستخدم في فهرسة النصوص لتمثيل مواضع الكلمات في المستندات.
- ضغط الصور والفيديو: تستخدم في بعض تنسيقات ضغط الصور والفيديو لتمثيل معاملات التحويل.
- قواعد البيانات: تستخدم في قواعد البيانات لتمثيل معرفات السجلات والمؤشرات.
مقارنة بين ترميز شانُون-فانو-إلياس وترميز إلياس جاما
الجدول التالي يلخص أهم الفروق بين ترميز شانُون-فانو-إلياس وترميز إلياس جاما:
| الخاصية | ترميز شانُون-فانو-إلياس | ترميز إلياس جاما |
|---|---|---|
| نوع البيانات | رموز ذات احتمالات معروفة | أعداد صحيحة موجبة |
| آلية العمل | يعتمد على الاحتمالات التراكمية | يعتمد على طول التمثيل الثنائي |
| الكفاءة | يعتمد على دقة الاحتمالات | أكثر كفاءة للأعداد الصغيرة |
| التعقيد | أكثر تعقيدًا | أبسط |
خاتمة
ترميز إلياس هو أداة قوية في مجال ضغط البيانات والاتصالات الرقمية. يوفر ترميز شانُون-فانو-إلياس طريقة لإنشاء رموز فعالة بناءً على الاحتمالات، بينما يوفر ترميز إلياس جاما طريقة بسيطة لتمثيل الأعداد الصحيحة الموجبة. اختيار التقنية المناسبة يعتمد على التطبيق المحدد والخصائص الإحصائية للبيانات المراد ترميزها.