خوارزمية دمج الحزم

خوارزمية دمج الحزم هي خوارزمية زمنية من رتبة O (nL) لإيجاد رمز هوفمان الأمثل ذي الطول المحدود لتوزيع معين على أبجدية معينة بحجم n ، حيث لا يتجاوز طول أي كلمة رمزية L. وهي خوارزمية جشعة ، وتعميم لخوارزمية هوفمان الأصلية . تعمل خوارزمية دمج الحزم عن طريق اختزال مشكلة بناء الرمز إلى مشكلة جامع العملات الثنائية . ^{[ 1 ]}

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

النسخة الثنائية لهذه المشكلة هي أن جميع الفئات هي قوى العدد 2، أي 1، 1/2، 1/4، إلخ. دولارات.

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

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

لاحظ أن وقت الخوارزمية يتناسب خطيًا مع عدد العملات المعدنية.

ليكن L أقصى طول مسموح به لأي كلمة رمزية. ولتكن p₁ _,  ..., pₙ ترددات رموز الأبجدية المراد ترميزها. نبدأ بترتيب الرموز بحيث يكون _pᵢ ≤ pᵢ + _{1. ثم} نُنشئ L عملة لكل رمز، بقيم ^{2⁻¹ ,} ... , _2⁻L ، ^قيمة كل منها pᵢ. نستخدم خوارزمية دمج الحزم لاختيار مجموعة العملات ذات القيمة النقدية ^الدنيا التي مجموع قيمها n⁻¹ _. ليكن hᵢ عدد العملات المختارة ذات القيمة النقدية _pᵢ . _{سيُرمِّز} رمز هوفمان الأمثل ذو الطول المحدود الرمز i بسلسلة بتات طولها hᵢ _. يمكن إنشاء رمز هوفمان القياسي بسهولة باستخدام طريقة جشعة بسيطة من الأسفل إلى الأعلى، بشرط معرفة قيم _hᵢ ، ويمكن أن يكون هذا أساسًا لضغط البيانات بسرعة . ^{[ 2 ]}       

مع هذا الاختزال، يصبح زمن الخوارزمية O(nL) ومساحتها O(nL) . مع ذلك، تُبين الورقة البحثية الأصلية، " خوارزمية سريعة لرموز هوفمان ذات الطول الأمثل المحدود "، كيف يُمكن تحسينها إلى زمن O(nL) ومساحة O(n) . الفكرة هي تشغيل الخوارزمية في المرة الأولى، مع الاحتفاظ فقط بالبيانات الكافية لتحديد مسألتين فرعيتين متكافئتين مجموعهما نصف حجم المسألة الأصلية. يتم ذلك بشكل تكراري، مما ينتج عنه خوارزمية تستغرق ضعف الوقت تقريبًا ولكنها تتطلب مساحة خطية فقط. ^{[ 1 ]}

أُدخلت العديد من التحسينات الأخرى على خوارزمية دمج الحزم لتقليل الثابت المضاعف وتسريعها في حالات خاصة، مثل تلك المشكلات التي تحتوي على عناصر p متكررة _. [ 3 ^{] كما تم} تكييف نهج دمج الحزم مع المشكلات ذات الصلة مثل الترميز الأبجدي . ^{[ 4 ]}

لقد ثبت أن الطرق التي تتضمن نظرية الرسم البياني تتمتع بتعقيد مكاني تقاربي أفضل من خوارزمية دمج الحزم، ولكن هذه الطرق لم تشهد الكثير من التطبيقات العملية.

• باير، مايكل ب. (2006). "عشرون سؤالاً (أو نحو ذلك): ترميز البادئة ذي الطول المحدود D ". arXiv : cs.IT/0602085 .
• موفات، أليستير ؛ توربين، أندرو؛ كاتاجاينن، يركي (مارس 1995). بناء رموز البادئة المثلى بكفاءة عالية من حيث المساحة . مؤتمر IEEE لضغط البيانات. سنوبيرد، يوتا، الولايات المتحدة الأمريكية. doi : 10.1109/DCC.1995.515509 .
• تطبيق لخوارزمية دمج الحزم ""
• مُشفِّر إنتروبي سريع يستخدم خوارزمية دمج الحزم