دعونا ننظر إلى النهج تافهة، والتي في كثير من الحالات يمكن أن يكون الأمثل:
فإنه سيتم تخزين:
- عدد العناصر في النطاق (مع 31 بت ، لأن القوائم في جافا تقتصر على عناصر 2 31 - 1).
- يتبعها 1 بت لكل فهرس ، مع الإشارة إلى ما إذا كان العنصر موجودًا في المجموعة أم لا.
هذا هو التنفيذ الذي كان الإصدار الأول من ضاغط الصورة كسورية، لتخزين البيانات من الانقسامات ودمج التثليث.
على الرغم من أنه لم يكن مثاليًا ، نظرًا لأنه مع تقدم تكرارات الانقسامات ، انخفض عدد العناصر التي سيتم تخزينها ، ليصبح نسبة صغيرة جدًا من الإجمالي ، وفي هذه الحالة يمكن تحسين الترميز التافه بشكل كبير.
الهدف الآن هو تحسين هذا الترميز التافه ، لمعرفة ما إذا كان يمكن الحصول على ترميز أكثر ضغطًا من حيث عدد البتات المستخدمة.
النهج الأول عندما يكون عدد العناصر في المجموعة أصغر بكثير من حجم النطاق، يمكننا النظر في تخزين المؤشرات الحالية.
في هذه الحالة ، سيكون الاستخدام:
- 31 بت لعدد العناصر في النطاق.
- 31 بت لعدد العناصر الموجودة في المجموعة.
- 31 بت * عدد العناصر الموجودة في المجموعة.
النهج الثاني . نقوم بتحسين عدد البتات لكل عنصر مخزن:
- 31 بت لعدد العناصر في النطاق. عدد بت من أكبر عنصر في النطاق ( numBitsإليم سيتم حسابها. )
- 5 بت للتخزين numBitsإليم .....لذلك، إذا كان عدد العناصر في النطاق 1023، فسيتم تخزين 10 في هذه البتات 5.
- numBitsإليم بت ، لتخزين عدد العناصر في المجموعة.
- numBitsإليم البتات * عدد العناصر الموجودة في المجموعة.
حسناً، شيئاً فشيئاً نحن نقترب من ترميز أفضل...
التقريب الثالث . نحن ندرك أنه إذا قمنا بفرز المجموعة بترتيب تصاعدي ، فمن المحتمل أن يتم ترميز الدلتا (الاختلافات بين العناصر المتتالية) بتات أقل من عنصر مطلق في النطاق:
- 31 بت لعدد العناصر في النطاق.
- نحسب أصغر numBitsElem لترميز عنصر.كما نقوم بحساب قائمة الدلتا (قائمة الاختلافات بين العناصر المتتالية لقائمة العناصر المصنفة في المجموعة).وأخيرًا، نحسب أيضًا numBitsدلتا
- 5 بت للتخزين numBitsإليم .....
- 5 بت للتخزين numBitsدلتا .....
- numBitsإليم بت ، لتخزين عدد العناصر في المجموعة.
- numBitsدلتا البتات * عدد العناصر في المجموعة.
حسنًا ، يبدو أننا وصلنا بالفعل إلى الترميز الأمثل ، أليس كذلك؟...
دعنا نَستمرُّ...
التقريب الرابع . ونحن نركز على حقيقة أنه يمكن أن يكون هناك عدد أكبر بكثير من الدلتا الصغيرة، وربما فقط عدد قليل من أكبر بكثير منها، التي كسر ' numBitsدلتا '..
في ظل هذه الظروف ، قد نجد numOptimumBitsدلتا ' أصغر من الحد الأقصى` numMaxBitsدلتا والذي بدوره يكون أقل من أو يساوي numBitsإليم '..
ولكن كيف نقوم بتشفير عنصر دلتا يتجاوز numOptimumBitsدلتا '؟ '؟
وبما أن الدلتا لن تكون أبدا 0 (لا توجد عناصر متكررة في مجموعة)، يمكننا استخدام القيمة 0 للإشارة إلى أنها قيمة خاصة.
وأن 0 ستتبعها قيمة الدلتا، ولكن مشفرة هذه المرة بـ numMaxBitsدلتا '..يمكن حساب إجمالي عدد البتات على النحو التالي:
- 31 بت لعدد العناصر في النطاق. نحسب أصغر numBitsإليم لتكون قادرة على ترميز عنصر واحد. نحسب أيضًا قائمة الدلتا (قائمة الاختلافات بين العناصر المتتالية لقائمة العناصر المرتبة في المجموعة).
- 31 بت، لتخزين عدد العناصر في المجموعة.
- 5 بت للتخزين numOptimumBitsدلتا .....
- 5 بت للتخزين numMaxBitsدلتا .....
- numOptimumBitsدلتا البتات * عدد العناصر في المجموعة.
- numMaxBitsدلتا البتات * عدد الدلتا التي تتجاوز numOptimumBitsدلتا .....
هل وصلنا بالفعل إلى الترميز الأمثل؟
التقريب الخامس حسناً... بما أننا قمنا بالفعل ببرمجة كل هذا...يمكننا أن نفكر في الوضع التكميلي...هل من الممكن أن يؤدي ترميز مكمل المجموعة بنفس الخوارزمية إلى نتائج أكثر ضغطًا؟
يُفهم مكمل المجموعة على أنه مجموعة أخرى ، منفصلة عن المجموعة الأصلية ، التي يكون اتحادها مع المجموعة الأصلية هو النطاق بأكمله.
أي أن المجموعة التكميلية ستحتوي على جميع عناصر النطاق غائبة في المجموعة الأصلية ، ولا شيء من تلك الموجودة في المجموعة الأصلية.
الجمال هو أنه من مجموعة ، من السهل جدًا الحصول على المجموعة التكميلية ، وبالتالي يمكننا الحصول على المجموعة الأصلية ، بعد ترميز المجموعة التكميلية.
التطبيق الواضح هو مجموعة تحتوي على جميع عناصر النطاق باستثناء عنصر واحد أو عدد قليل من العناصر.
حسنًا... إذا قمنا بتخزين الغائبين فقط (المجموعة التكميلية) ، فيمكن تخزينها بحجم أصغر بكثير ، أليس كذلك؟
الترميز في هذه الحالة يمكن أن يكون مثل هذا:
- 31 بت لعدد العناصر في النطاق. نحسب أصغر numBitsإليم لتشفير عنصر. نحسب أيضًا قائمة الدلتا (قائمة الاختلافات بين العناصر المتتالية لقائمة العناصر المرتبة في المجموعة).
- 1 بت ، لتخزين ما إذا كنا نخزن المجموعة الأصلية ، أو المكمل.هذا هو الجزء الإضافي.
- 31 بت، لتخزين عدد العناصر في المجموعة.
- 5 بت للتخزين numOptimumBitsدلتا .....
- 5 بت للتخزين numMaxBitsدلتا .....
- numOptimumBitsدلتا البتات * عدد العناصر في المجموعة.
- numMaxBitsدلتا البتات * عدد الدلتا التي تتجاوز numOptimumBitsدلتا في المواقع التي تظهر فيها.
حسنا... الآن نحن نتحدث.
ولكن أنا أدرك أنه إذا كان كل تلك العجائب يمكن القيام به، ما لا يمكن القيام به من خلال البحث عن أنماط أخرى، أو ببساطة باستخدام ضاغط ضياع، مثل الرمز البريدي أو 7Z...
هذا يجب أن ينتظر، على الموقد الخلفي في المرة القادمة...
