Succinct data structure
کمپیوٹر سائنس میں، ایک مختصر ڈیٹا ڈھانچہ ایک ڈیٹا ڈھانچہ ہے جو معلومات کی نظریاتی نچلی حد کے "قریب" جگہ کا استعمال کرتا ہے، لیکن (دیگر کمپریسڈ نمائندگی کے برعکس) اب بھی موثر استفسار کی کارروائیوں کی اجازت دیتا ہے۔ یہ تصور اصل میں جیکبسن نے بٹ ویکٹرز، (غیر لیبل شدہ) درختوں، اور پلانر گراف کو انکوڈ کرنے کے لیے متعارف کرایا تھا۔ عام نقصان کے بغیر ڈیٹا کمپریشن الگورتھم کے برعکس، مختصر ڈیٹا ڈھانچے انہیں پہلے ڈمپریس کیے بغیر، اپنی جگہ پر استعمال کرنے کی صلاحیت کو برقرار رکھتے ہیں۔ ایک متعلقہ تصور ایک کمپریسڈ ڈیٹا ڈھانچے کا ہے، جہاں تک کہ ذخیرہ شدہ یا انکوڈ شدہ ڈیٹا کا سائز اسی طرح ڈیٹا کے مخصوص مواد پر منحصر ہے۔ فرض کریں کہ یہ کچھ ڈیٹا کو ذخیرہ کرنے کے لیے درکار بٹس کی معلومات-نظریاتی زیادہ سے زیادہ تعداد ہے۔ اس ڈیٹا کی نمائندگی کو کہا جاتا ہے: اگر یہ تھوڑی سی جگہ لیتا ہے تو مضمر، اگر یہ تھوڑی سی جگہ لیتا ہے تو مختصر، اور اگر یہ تھوڑی سی جگہ لیتا ہے تو کمپیکٹ۔ مثال کے طور پر، ایک ڈیٹا ڈھانچہ جو اسٹوریج کے بٹس کا استعمال کرتا ہے وہ کمپیکٹ ہوتا ہے، بٹس مختصر ہوتے ہیں، بٹس بھی مختصر ہوتے ہیں، اور بٹس مضمر ہوتے ہیں۔ اس طرح مضمر ڈھانچے کو عام طور پر ان پٹ ڈیٹا کی کچھ ترتیب کا استعمال کرتے ہوئے معلومات کو ذخیرہ کرنے کے لیے کم کر دیا جاتا ہے۔ اس کی سب سے مشہور مثال ڈھیر ہے۔ سوسنکٹ انڈیکس ایبل ڈکشنریز، جنہیں رینک/سلیکٹ ڈکشنریز بھی کہا جاتا ہے، بائنری ٹریز، ایری ٹریز اور ملٹی سیٹس کے ساتھ ساتھ لاحقہ ٹریز اور صفوں سمیت متعدد مختصر نمائندگی کی تکنیکوں کی بنیاد بناتی ہیں۔ بنیادی مسئلہ کائنات کے ذیلی سیٹ کو ذخیرہ کرنا ہے، جسے عام طور پر ایک بٹ صف کے طور پر پیش کیا جاتا ہے جہاں آئی ایف ایف ایک انڈیکس ایبل ڈکشنری لغتوں پر معمول کے طریقوں (سوالات، اور متحرک معاملے میں اندراج/حذف) کے ساتھ ساتھ درج ذیل کارروائیوں کی حمایت کرتی ہے: دوسرے لفظوں میں، پوزیشن تک کے برابر عناصر کی تعداد واپس کرتا ہے جبکہ-th کی موجودگی کی پوزیشن واپس کرتا ہے۔ ایک سادہ نمائندگی ہے جو اسٹوریج کی جگہ کے بٹس (اصل بٹ صف اور ایک معاون ڈھانچہ) کا استعمال کرتی ہے اور مستقل وقت میں رینک اور سلیکٹ کی حمایت کرتی ہے۔ یہ رینج-کم سے کم سوالات کے لیے اسی طرح کے خیال کا استعمال کرتا ہے ؛ محدود سائز کے ذیلی مسئلے پر رکنے سے پہلے مسلسل تعداد میں تکرار ہوتے ہیں۔ بٹ صف کو سائز کے بٹس کے بڑے بلاکس اور سائز کے بٹس کے چھوٹے بلاکس میں تقسیم کیا گیا ہے۔ ہر بڑے بلاک کے لیے، اس کے پہلے بٹ کا درجہ ایک علیحدہ ٹیبل میں محفوظ کیا جاتا ہے ؛ اس طرح کی ہر اندراج اسٹوریج کے کل بٹس کے لیے بٹس لیتا ہے۔ ایک بڑے بلاک کے اندر، ایک اور ڈائرکٹری اس میں موجود ہر چھوٹے بلاک کا درجہ محفوظ کرتی ہے۔ یہاں فرق یہ ہے کہ اسے ہر اندراج کے لیے صرف بٹس کی ضرورت ہوتی ہے، کیونکہ بڑے بلاک پر مشتمل پہلے بٹ کے رینک سے صرف فرق کو ذخیرہ کرنے کی ضرورت ہوتی ہے۔ اس طرح، یہ ٹیبل کل بٹس لیتا ہے۔ اس کے بعد ایک لک اپ ٹیبل استعمال کیا جا سکتا ہے جو ہر ممکنہ رینک کے استفسار کے جواب کو لمبائی کی ایک چھوٹی سی تار پر محفوظ کرتا ہے ؛ اس کے لیے اسٹوریج کی جگہ کے بٹس کی ضرورت ہوتی ہے۔ اس طرح، چونکہ ان معاون میزیں میں سے ہر ایک جگہ لیتا ہے، یہ ڈیٹا ڈھانچہ وقت اور جگہ کے ٹکڑوں میں درجہ بندی کے سوالات کی حمایت کرتا ہے۔ مستقل وقت میں کسی استفسار کا جواب دینے کے لیے، ایک مستقل ٹائم الگورتھم حساب کرتا ہے: عملی طور پر، لک اپ ٹیبل کو بٹ وائز آپریشنز اور چھوٹے ٹیبلز سے تبدیل کیا جا سکتا ہے جو چھوٹے بلاکس میں سیٹ کیے گئے بٹس کی تعداد تلاش کرنے کے لیے استعمال کیے جا سکتے ہیں۔ یہ اکثر فائدہ مند ہوتا ہے، کیونکہ مختصر ڈیٹا ڈھانچے بڑے ڈیٹا سیٹوں میں اپنے استعمال تلاش کرتے ہیں، ایسی صورت میں کیش کی کمی بہت زیادہ ہو جاتی ہے اور قریبی سی پی یو کیش سے لک اپ ٹیبل کے بے دخل ہونے کے امکانات زیادہ ہو جاتے ہیں۔ رینک کے لیے استعمال ہونے والے اسی معاون ڈھانچے پر بائنری سرچ کر کے منتخب سوالات کو آسانی سے سپورٹ کیا جا سکتا ہے ؛ تاہم، بدترین صورت حال میں اس میں وقت لگتا ہے۔ اضافی اسٹوریج کے بٹس کا استعمال کرتے ہوئے ایک زیادہ پیچیدہ ڈھانچہ مستقل وقت میں منتخب کرنے میں مدد کے لیے استعمال کیا جا سکتا ہے۔ عملی طور پر، ان میں سے بہت سے حلوں میں اشارے میں پوشیدہ مستقل ہوتے ہیں جو کسی بھی غیر علامتی فائدہ کے ظاہر ہونے سے پہلے غالب ہوتے ہیں۔ براڈ ورڈ آپریشنز اور لفظ سے منسلک بلاکس کا استعمال کرتے ہوئے نفاذ اکثر عملی طور پر بہتر کارکردگی کا مظاہرہ کرتے ہیں۔ اینٹروپی کمپریسڈ حل خلائی نقطہ نظر کو یہ نوٹ کر کے بہتر بنایا جا سکتا ہے کہ (یا بالکل 1 کے ساتھ لمبائی کے بائنری تار) کے الگ الگ ذیلی سیٹ موجود ہیں، اور اس طرح ذخیرہ کرنے کے لیے درکار بٹس کی تعداد پر ایک معلومات نظریاتی طور پر کم پابند ہے۔ ایک مختصر (جامد) لغت ہے جو اس حد کو حاصل کرتی ہے، یعنی جگہ کا استعمال کرتے ہوئے۔ اس ڈھانچے کو رینک کی حمایت کرنے اور سوالات کو منتخب کرنے کے لیے بڑھایا جا سکتا ہے اور یہ جگہ لیتا ہے۔ اس ڈھانچے میں درست درجہ بندی کے سوالات تاہم سیٹ میں موجود عناصر تک محدود ہیں، جو کہ کم سے کم کامل ہیشنگ افعال کے کام کرنے کے مترادف ہیں۔ اس باؤنڈ کو وقت لینے والے سوالات کے ساتھ لغت کے اسٹوریج کی جگہ کو کم کرکے اسپیس/ٹائم ٹریڈ آف تک کم کیا جا سکتا ہے۔ ایک انڈیکس ایبل ڈکشنری کی تعمیر بھی ممکن ہے جو رینک کی حمایت کرے (لیکن منتخب نہ کرے) جو بٹس سے کم استعمال کرے۔ اس طرح کی لغت کو مونوٹون منمل پرفیکٹ ہیش فنکشن کہا جاتا ہے، اور اسے کم سے کم بٹس کا استعمال کرتے ہوئے لاگو کیا جا سکتا ہے۔ ایک مختصر ہیش ٹیبل، جسے ایک مختصر غیر ترتیب شدہ لغت بھی کہا جاتا ہے، ایک ڈیٹا ڈھانچہ ہے جو خلائی بٹس کا استعمال کرتے ہوئے کائنات کی چابیاں محفوظ کرتا ہے، اور مستقل متوقع وقت میں رکنیت کے سوالات کی حمایت کرتا ہے۔ اگر ایک مختصر ہیش ٹیبل مستقل متوقع وقت میں اندراج اور حذف کرنے کی بھی حمایت کرتا ہے، تو اسے متحرک کہا جاتا ہے، اور بصورت دیگر اسے جامد کہا جاتا ہے۔ پہلی متحرک مختصر ہیش ٹیبل 2003 میں رمن اور راؤ کی وجہ سے تھی۔ اس صورت میں جہاں، ان کا حل اسپیس بٹس کا استعمال کرتا ہے۔ اس کے بعد، یہ دکھایا گیا کہ اس جگہ کی حد کو لوگرتھم کی کسی بھی مستقل تعداد کے لیے بٹس میں بہتر بنایا جا سکتا ہے۔ مؤخر الذکر حل اعلی امکان کے ساتھ بدترین صورت میں مستقل وقت میں تمام کارروائیوں کی حمایت کرتا ہے۔ پہلی جامد مختصر ہیش ٹیبل 1999 میں پاگ کی وجہ سے تھی۔ اس صورت میں جہاں، ان کا حل اسپیس بٹس کا استعمال کرتا ہے، اور بدترین صورت میں مستقل وقت کے سوالات کی حمایت کرتا ہے۔ اس باؤنڈ کو بعد میں بٹس اور پھر بٹس میں بہتر بنایا گیا۔ جبکہ پہلے دو حل بدترین صورت میں مستقل وقت کے سوالات کی حمایت کرتے ہیں، آخری ایک مستقل متوقع وقت کے سوالات کی حمایت کرتا ہے۔ حتمی حل کے لیے سائز کی لک اپ ٹیبل تک رسائی کی بھی ضرورت ہوتی ہے، لیکن یہ لک اپ ٹیبل ذخیرہ کیے جانے والے عناصر کے سیٹ سے آزاد ہے۔ دیگر مثالیں صوابدیدی لمبائی (پاسکل سٹرنگ) والی سٹرنگ Z + لاگ (Z) کی جگہ لیتی ہے، اور اس طرح مختصر ہوتی ہے۔ اگر زیادہ سے زیادہ لمبائی ہے-جو عملی طور پر معاملہ ہے، کیونکہ ڈیٹا کا 232 = 4 جی بی ایک بہت لمبا سٹرنگ ہے، اور 264 = 16 ای آئی بی ڈیٹا عملی طور پر کسی بھی سٹرنگ سے بڑا ہے-تو لمبائی والا سٹرنگ بھی مضمر ہے، جس میں زیڈ + کے کی جگہ ہے، جہاں کے زیادہ سے زیادہ لمبائی کی نمائندگی کرنے والے ڈیٹا کی تعداد ہے (مثال کے طور پر، 64 بٹس)۔ جب متغیر لمبائی والی آئٹمز (جیسے سٹرنگز) کی ترتیب کو انکوڈ کرنے کی ضرورت ہوتی ہے، تو مختلف امکانات ہوتے ہیں۔ ایک براہ راست طریقہ یہ ہے کہ ہر ریکارڈ میں ایک لمبائی اور ایک آئٹم کو محفوظ کیا جائے-پھر انہیں ایک کے بعد ایک رکھا جا سکتا ہے۔ یہ موثر اگلے کی اجازت دیتا ہے، لیکن kth آئٹم کو تلاش نہیں کرتا ہے۔ ایک متبادل یہ ہے کہ آئٹمز کو ڈیلیمیٹر کے ساتھ ترتیب میں رکھا جائے (مثال کے طور پر، کالعدم تار)۔ یہ لمبائی کے بجائے حد بندی کا استعمال کرتا ہے، اور کافی حد تک سست ہے، کیونکہ حد بندی کے لیے پوری ترتیب کو اسکین کرنا ضروری ہے۔ یہ دونوں جگہ کے لحاظ سے موثر ہیں۔ ایک متبادل نقطہ نظر بینڈ سے باہر علیحدگی ہے: اشیاء کو بغیر کسی حد بندی کے ایک کے بعد ایک رکھا جا سکتا ہے۔ آئٹم کی حدود کو پھر لمبائی کی ترتیب کے طور پر محفوظ کیا جا سکتا ہے، یا بہتر، اس ترتیب میں آفسیٹ کیا جا سکتا ہے۔ متبادل طور پر، ایک علیحدہ بائنری سٹرنگ جس میں 1s ان پوزیشنوں پر مشتمل ہوتا ہے جہاں کوئی آئٹم شروع ہوتا ہے، اور 0s ہر جگہ اس کے ساتھ انکوڈ کیا جاتا ہے۔ اس سٹرنگ کو دیکھتے ہوئے، فنکشن تیزی سے اس بات کا تعین کر سکتا ہے کہ ہر آئٹم کہاں سے شروع ہوتا ہے، اس کے انڈیکس کو دیکھتے ہوئے۔ یہ کمپیکٹ ہے لیکن مختصر نہیں ہے، کیونکہ یہ 2 زیڈ جگہ لیتا ہے، جو کہ او (زیڈ) ہے۔ ایک اور مثال بائنری ٹری کی نمائندگی ہے: نوڈس پر ایک من مانی بائنری ٹری کو بٹس میں دکھایا جا سکتا ہے جبکہ کسی بھی نوڈ پر مختلف کارروائیوں کی حمایت کی جا سکتی ہے، جس میں اس کے والدین، اس کے بائیں اور دائیں بچے کو تلاش کرنا، اور اس کے ذیلی درخت کا سائز واپس کرنا شامل ہے، ہر ایک مستقل وقت میں۔ نوڈس پر مختلف بائنری درختوں کی تعداد ہے۔ بڑے پیمانے پر، یہ تقریبا ہے ؛ اس طرح ہمیں اسے انکوڈ کرنے کے لیے کم از کم تقریبا بٹس کی ضرورت ہے۔ اس لیے ایک مختصر بائنری ٹری فی نوڈ صرف بٹس پر قبضہ کرے گا۔ یہ بھی دیکھیں کہ کم از کم کامل ہیش فنکشن سوسنکٹ نان انٹرایکٹو آرگیومنٹس آف نالج ریفرنسز