Package-merge algorithm
پیکیج انضمام الگورتھم ایک O (nL) ٹائم الگورتھم ہے جو سائز n کے دیئے گئے حروف تہجی پر دی گئی تقسیم کے لیے زیادہ سے زیادہ لمبائی محدود ہفمین کوڈ تلاش کرنے کے لیے ہے، جہاں کوئی کوڈ لفظ L سے لمبا نہیں ہے۔ یہ ایک لالچی الگورتھم ہے، اور ہفمین کے اصل الگورتھم کی عمومی شکل ہے۔ پیکیج-انضمام کوڈ کی تعمیر کے مسئلے کو بائنری سکے کلیکٹر کے مسئلے تک کم کرکے کام کرتا ہے۔ سکے جمع کرنے والے کا مسئلہ فرض کریں کہ ایک سکے جمع کرنے والے کے پاس مختلف فرقوں کے متعدد سکے ہوتے ہیں، جن میں سے ہر ایک کی عددی قدر ہوتی ہے جس کا اس کے فرق سے کوئی تعلق نہیں ہوتا ہے۔ سکے جمع کرنے والے کے پاس پیسے ختم ہو چکے ہوتے ہیں اور اسے اپنے سکے کے مجموعے میں سے کچھ قیمت N کی چیز خریدنے کے لیے استعمال کرنے کی ضرورت ہوتی ہے۔ وہ اپنے کم از کم عددی قدر کے مجموعے سے سکوں کا ایک ذیلی مجموعہ منتخب کرنا چاہتا ہے جس کے فرقے کل N ہوتے ہیں۔ اس مسئلے کا بائنری ورژن یہ ہے کہ تمام فرقے 2 کی طاقتیں ہیں، یعنی 1، 1/2، 1/4، وغیرہ۔ ڈالر۔ پیکیج-ضم الگورتھم کی تفصیل فرض کریں کہ سب سے بڑا مالیت 1 ڈالر ہے، اور یہ کہ N ایک عدد ہے۔ (الگورتھم معمولی ترامیم کے ذریعے کام کرتا ہے یہاں تک کہ اگر یہ مفروضے برقرار نہیں رہتے ہیں۔) سکے جمع کرنے والا پہلے اپنے سکوں کو فہرستوں میں الگ کرتا ہے، ہر فرق کے لیے ایک، جو عددی قدر کے مطابق ترتیب دیا جاتا ہے۔ اس کے بعد وہ سب سے چھوٹے مالیت کے سکوں کو جوڑوں میں پیک کرتا ہے، جو سب سے چھوٹی کل عددی قدر کے جوڑے سے شروع ہوتا ہے۔ اگر ایک سکہ بچا ہے، تو یہ اس مالیت کا سب سے زیادہ عددی قدر کا سکہ ہوگا، اور اسے ایک طرف رکھ دیا جاتا ہے اور اب سے نظر انداز کر دیا جاتا ہے۔ اس کے بعد ان پیکجوں کو اگلے سب سے چھوٹے مالیت کے سکوں کی فہرست میں ضم کر دیا جاتا ہے، پھر سے عددی قدر کی ترتیب میں۔ اس فہرست میں موجود اشیاء کو پھر جوڑوں میں پیک کیا جاتا ہے، اور اگلی سب سے چھوٹی فہرست میں ضم کر دیا جاتا ہے، وغیرہ۔ آخر میں، اشیاء کی ایک فہرست ہوتی ہے، جن میں سے ہر ایک 1 ڈالر کا سکہ یا ایک پیکیج ہوتا ہے جس میں دو یا دو سے زیادہ چھوٹے سکے ہوتے ہیں جن کی مالیت کل 1 ڈالر ہوتی ہے۔ انہیں عددی قدر کی ترتیب میں بھی ترتیب دیا جاتا ہے۔ سکے جمع کرنے والا پھر ان میں سے سب سے کم قیمت N کا انتخاب کرتا ہے۔ نوٹ کریں کہ الگورتھم کا وقت سکوں کی تعداد میں لکیری ہے۔ سکے جمع کرنے والے کے مسئلے پر لمبائی محدود ہفمین کوڈنگ کو کم کرنا L کو کسی بھی کوڈ لفظ کی زیادہ سے زیادہ لمبائی ہونے دیں۔ فرض کریں کہ p1,., pn انکوڈ کیے جانے والے حروف تہجی کی علامتوں کی تعدد ہے۔ ہم سب سے پہلے علامتوں کو ترتیب دیتے ہیں تاکہ پائی ≤ پائی + 1 ہو۔ ہر علامت کے لیے L سکے بنائیں، جن کے فرق 2−1,., 2−L ہوں، جن میں سے ہر ایک کی عددی قدر پائی ہو۔ کم از کم عددی قدر والے سکوں کے سیٹ کو منتخب کرنے کے لیے پیکیج-ضم الگورتھم کا استعمال کریں جن کے فرق کل n−1 ہوں۔ آئیے کہ منتخب کردہ عددی قدر پائی کے سکوں کی تعداد ہیلو ہے۔ زیادہ سے زیادہ لمبائی محدود ہفمین کوڈ علامت i کو تھوڑا سا لمبائی ہائی کے ساتھ انکوڈ کرے گا۔ کینونکل ہفمین کوڈ کو آسانی سے ایک سادہ نیچے سے اوپر لالچی طریقہ سے بنایا جا سکتا ہے، یہ دیکھتے ہوئے کہ ہائی جانا جاتا ہے، اور یہ تیز ڈیٹا کمپریشن کی بنیاد ہو سکتا ہے۔ کارکردگی میں بہتری اور عمومی کاری اس کمی کے ساتھ، الگورتھم O (nL)-ٹائم اور O (nL)-اسپیس ہے۔ تاہم، اصل مقالہ، "زیادہ سے زیادہ لمبائی-محدود ہفمین کوڈز کے لیے ایک تیز الگورتھم"، ظاہر کرتا ہے کہ اسے O (nL)-وقت اور O (n)-جگہ تک کیسے بہتر بنایا جا سکتا ہے۔ خیال یہ ہے کہ الگورتھم کو پہلی بار چلایا جائے، صرف اتنا ڈیٹا رکھا جائے کہ وہ دو مساوی ذیلی مسائل کا تعین کر سکے جو اصل مسئلے کے نصف سائز کے برابر ہوں۔ یہ بار بار کیا جاتا ہے، جس کے نتیجے میں ایک الگورتھم ہوتا ہے جس میں تقریبا دوگنا وقت لگتا ہے لیکن اس میں صرف لکیری جگہ کی ضرورت ہوتی ہے۔ ضرب مستقل کو کم کرنے اور خاص معاملات میں اسے تیز کرنے کے لیے پیکیج-ضم الگورتھم میں بہت سی دیگر بہتریاں کی گئی ہیں، جیسے کہ بار بار پیس ہونے والے مسائل۔ پیکیج انضمام کے نقطہ نظر کو حروف تہجی کوڈنگ جیسے متعلقہ مسائل کے لیے بھی ڈھال لیا گیا ہے۔ گراف تھیوری سے متعلق طریقوں کو پیکیج-ضم الگورتھم کے مقابلے میں بہتر ایسمپٹوٹک اسپیس پیچیدگی دکھایا گیا ہے، لیکن ان میں اتنا عملی اطلاق نہیں دیکھا گیا ہے۔ حوالہ جات بیرونی روابط پیکیج انضمام الگورتھم کا نفاذ "" ایک تیز اینٹروپی کوڈر جو پیکیج انضمام الگورتھم لاس لیس کمپریشن الگورتھم کا استعمال کرتا ہے کوڈنگ تھیوری