Simplex tree
ٹپوولوجیکل ڈیٹا تجزیہ میں، سمپلیکس ٹری ایک قسم کی ٹرائی ہے جو کسی بھی عام سادہ کمپلیکس کی مؤثر طریقے سے نمائندگی کرنے کے لیے استعمال ہوتی ہے۔ اپنے نوڈس کے ذریعے، یہ ڈیٹا ڈھانچہ خاص طور پر تمام آسانیوں کی واضح طور پر نمائندگی کرتا ہے۔ اس کا لچکدار ڈھانچہ مستقل ہومیولوجی کی کمپیوٹنگ کے لیے مفید بہت سے بنیادی کارروائیوں کے نفاذ کی اجازت دیتا ہے۔ یہ ڈیٹا ڈھانچہ جین ڈینیئل بوسنناٹ اور کلیمنٹ ماریا نے 2014 میں دی سمپلیکس ٹری: جنرل سمپلیکل کمپلیکسز کے لیے ایک موثر ڈیٹا ڈھانچہ کے مضمون میں ایجاد کیا تھا۔ یہ ڈیٹا ڈھانچہ غیر معمولی سادہ کمپلیکس پر موثر آپریشن پیش کرتا ہے۔ گھنے یا زیادہ سے زیادہ آسانیوں کے لیے، سکیلٹن-بلاکر کی نمائندگی یا ٹوپلیکس میپ کی نمائندگی استعمال کی جاتی ہیں۔ تعریفیں ٹپوولوجیکل ڈیٹا تجزیہ میں بہت سے محققین سمپلیکس ٹری کو آسان کمپلیکس کے لیے سب سے زیادہ کمپیکٹ سمپلیکس پر مبنی ڈیٹا ڈھانچہ، اور ایک ڈیٹا ڈھانچہ سمجھتے ہیں جو ان کی ریاضیاتی خصوصیات کے مربوط استعمال کی وجہ سے آسان کمپلیکس کی بدیہی تفہیم کی اجازت دیتا ہے۔ کوئی بھی سادہ کمپلیکس پوائنٹس (0 طول و عرض)، لائن سیگمنٹس (1 طول و عرض)، مثلث (2 طول و عرض)، اور ان کے n جہتی ہم منصبوں پر مشتمل ایک سیٹ ہے، جسے ٹپوولوجیکل اسپیس کے اندر n-سمپلیکس کہتے ہیں۔ سمپلیکس کی ریاضیاتی خصوصیات کے مطابق، کوئی بھی n-سمپلیکس متعدد-سمپلیکس پر مشتمل ہوتا ہے۔ اس طرح، لکیریں پوائنٹس، لائنوں کے مثلث، مثلث کے ٹیٹرا ہیڈرون پر مشتمل ہوتی ہیں۔ نوٹ کریں کہ ہر اعلی سطح n-سمپلیکس کے عمودی حصوں میں 1 ورٹیکس کا اضافہ کرتی ہے۔ ڈیٹا ڈھانچہ سمپلیکس پر مبنی ہے، اس لیے اسے سمپلیکس کی وضاحت کرنے والے نکات کے ذریعے تمام سمپلیکس کی منفرد نمائندگی کرنی چاہیے۔ اس کو حاصل کرنے کا ایک آسان طریقہ یہ ہے کہ ہر سمپلیکس کی وضاحت اس کے نکات کے مطابق ترتیب میں کی جائے۔ طول و عرض k کا ایک سادہ کمپلیکس ہونے دیں، اس کا ورٹیکس سیٹ، جہاں عمودی حصوں کو 1 سے لیبل کیا جاتا ہے اور اسی کے مطابق ترتیب دیا جاتا ہے۔ اب، ایک لغت کا سائز بنائیں جس میں تمام ورٹیکس لیبل ترتیب میں ہوں۔ یہ 0 جہتی سمپلیکس کی نمائندگی کرتا ہے۔ پھر، ابتدائی ڈکشنری میں ہر اندراج کے ابتدائی ڈکشنری کے راستے کے لیے، چائلڈ ڈکشنری کے طور پر تمام عمودی حصوں کو شامل کریں جو عمودی حصوں کے موجودہ سیٹ سے مکمل طور پر جڑے ہوئے ہیں، جن میں سے سبھی پر اس سے بڑا لیبل ہے۔ کے کی سطحوں پر اس مرحلے کی نمائندگی کریں۔ واضح طور پر، پہلی لغت کو ڈیپتھ 0 کے طور پر دیکھتے ہوئے، اس ڈیٹا ڈھانچے میں کسی بھی لغت کی گہرائی میں کوئی بھی اندراج منفرد طور پر اس کے اندر ایک-سمپلیکس کی نمائندگی کرتا ہے۔ مکمل ہونے کے لیے، ابتدائی لغت کے نقطہ کو خالی سمپلیکس کی نمائندگی سمجھا جاتا ہے۔ کارروائیوں کی عملیت کے لیے، ایک ہی سطح پر دہرائے جانے والے لیبل ایک دوسرے سے جڑے ہوتے ہیں، جس سے ایک لوپڈ لنکڈ لسٹ بنتی ہے۔ آخر میں، بچوں کی لغتوں میں آباؤ اجداد تک تیز رسائی کے لیے ان کی بنیادی لغت کے اشارے بھی ہوتے ہیں۔ تعمیری تعریف آئیے طول و عرض k کا ایک سادہ کمپلیکس ہے۔ ہم سادہ کمپلیکس کو باہمی طور پر خصوصی سمپلیکس میں سڑ کر شروع کرتے ہیں۔ یہ لالچی انداز میں آسان کمپلیکس سے بار بار اعلی درجے کے سمپلیکس کو ہٹا کر حاصل کیا جا سکتا ہے جب تک کہ آسان کمپلیکس خالی نہ ہو جائے۔ اس کے بعد ہمیں ہر ورٹیکس کو 1 سے لیبل کرنے کی ضرورت ہے اور ہر سمپلیکس کو اس کے متعلقہ "لفظ" سے منسلک کرنے کی ضرورت ہے، جو کہ لیبل کے لحاظ سے اس کے عمودی حصوں کی ترتیب شدہ فہرست ہے۔ لیبلز کو آرڈر کرنا اس بات کو یقینی بناتا ہے کہ سمپلیکس ٹری میں کوئی تکرار نہ ہو، کیونکہ سمپلیکس کو بیان کرنے کا صرف ایک ہی طریقہ ہے۔ ہم ایک صفر جڑ سے شروع کرتے ہیں، جو صفر سمپلیکس کی نمائندگی کرتا ہے۔ پھر، ہم تمام سمپلیکس کے ذریعے، اور ہر سمپلیکس لفظ کے ہر لیبل کے ذریعے دہراتے ہیں۔ اگر لیبل موجودہ جڑ تک بچے کے طور پر دستیاب ہے، تو اس بچے کو اندراج کے عمل کی عارضی جڑ بنائیں، بصورت دیگر، بچے کے لیے ایک نیا نوڈ بنائیں، اسے نیا عارضی جڑ بنائیں، اور باقی لفظ کے ساتھ جاری رکھیں۔ اس عمل کے دوران، کے لغتوں کو تمام لیبلز کے ساتھ برقرار رکھا جاتا ہے اور متعلقہ لیبل کے لیے نوڈ کا پتہ داخل کیا جاتا ہے۔ اگر لغت میں اس جگہ پر پہلے سے ہی کوئی پتہ موجود ہے، تو پرانے نوڈ سے نئے نوڈ تک ایک پوائنٹر بنایا جاتا ہے۔ ایک بار عمل ختم ہونے کے بعد ہر نوڈ کے تمام بچوں کو ایک لغت میں داخل کیا جاتا ہے، اور تمام اشارے لوپ شدہ منسلک فہرستیں بنانے کے لیے لوپ ہوتے ہیں۔ یہاں لغتوں کی ایک وسیع رینج کا اطلاق کیا جا سکتا ہے، جیسے ہیش ٹیبلز، لیکن کچھ کارروائیاں اندراجات کے آرڈرڈ ٹریورسل کے امکان کو فرض کرتی ہیں، جس کی وجہ سے زیادہ تر نفاذ سرخ سیاہ درختوں کو استعمال کرنے کے لیے لغت ہیں۔ اگرچہ سمپلیکس ٹری آسان پیچیدہ نمائندگی کے لیے سب سے زیادہ جگہ کے موثر ڈیٹا ڈھانچے نہیں ہیں، لیکن کم ڈیٹا پر ان کی کارروائیوں کو جدید ترین سمجھا جاتا ہے۔ یہاں، ہم اس نمائندگی کے ذریعے ممکنہ مختلف مفید کارروائیوں کی حدود بتاتے ہیں۔ ان کارروائیوں کے بہت سے نفاذ دستیاب ہیں۔ ہم سب سے پہلے نوٹیشن متعارف کراتے ہیں۔ غور کریں کہ ایک دیا ہوا سمپلیکس ہے، ایک دیا ہوا نوڈ ہے جو آخری سرے سے مطابقت رکھتا ہے، اس نوڈ سے منسلک لیبل ہے، اس نوڈ کی گہرائی ہے، سادہ کمپلیکس کا طول و عرض ہے، لغت میں رسائی کے لیے کارروائیوں کی زیادہ سے زیادہ تعداد ہے (اگر لغت سرخ سیاہ درخت ہے، تو پیچیدگی ہے)۔ کوفیس کی تعداد پر غور کریں، اور کیا سمپلیکس ٹری کے نوڈس کی تعداد اس سے زیادہ گہرائی میں لیبل کے ساتھ ختم ہوتی ہے۔ نوٹس لیں۔ تلاش کریں، داخل کریں اور الفاظ کو ہٹا دیں۔ ایک مکمل سمپلیکس ڈالیں اور ہٹا دیں۔ مستقل ہومیولوجی کا حساب لگانا، یا زیادہ شامل طریقے سے، بیٹی نمبروں کا حساب لگانا، ایک سمپلیکس ٹری کا انتہائی موثر طریقے سے استعمال کرنا ایک کھلا مسئلہ ہے، تاہم، اس کام کے لیے موجودہ الگورتھم غیر معمولی سادہ کمپلیکس پر جدید ترین کارکردگی حاصل کرتے ہیں۔ سمپلیکس کے درختوں کی ساخت سکڑنے والے سمپلیکس کے ابتدائی خاتمے کی اجازت دیتی ہے، تاہم عام صورت میں اس عمل کی حدود معلوم نہیں ہیں۔ ابتدائی خاتمے کا ایک ذیلی کیس ایج کنٹریکشن ہے۔ کنارے کا سنکچن حاصل کیا جا سکتا ہے۔ دیئے گئے سمپلیکس کے کوفیس کا پتہ لگانے میں حاصل کیا جا سکتا ہے۔ دیئے گئے سمپلیکس کے کوفیسیٹس کا پتہ لگانے میں حاصل کیا جا سکتا ہے۔ جہاں تک تعمیر کا تعلق ہے، جیسا کہ تعمیری تعریف میں دیکھا گیا ہے، تعمیر سادہ کمپلیکس میں سمپلیکس کی تعداد اور پیچیدگی کے متناسب ہے۔ یہ خاص طور پر مہنگا ہو سکتا ہے اگر سادہ کمپلیکس گھنے ہو۔ تاہم، فلیگ کمپلیکس، رپس کمپلیکس اور وٹنس کمپلیکس سمیت مخصوص آسان کمپلیکس کے لیے کچھ اصلاح۔ ایپلی کیشنز سمپلیکس ٹری غیر معمولی سادہ کمپلیکس میں موثر ہوتے ہیں۔ اس مقصد کے لیے، اعلی جہتی حقیقی ڈیٹا (اکثر کم) پر توجہ مرکوز کرنے والے بہت سے مستقل ہومیولوجی الگورتھم ان الگورتھم کے اندر سمپلیکس ٹری کا استعمال کرتے ہیں۔ اگرچہ سمپلیکس کے درخت واقعات میٹرکس کی طرح موثر نہیں ہیں، لیکن ان کی سمپلیکس پر مبنی ساخت انہیں مستقل ہومیولوجی الگورتھم کے اندر آسان پیچیدہ اسٹوریج کے لیے مفید موثر ہونے کی اجازت دیتی ہے۔ حوالہ جات درخت (ڈیٹا ڈھانچے) آسان سیٹ