Generalized suffix tree
کمپیوٹر سائنس میں، ایک عمومی لاحقہ درخت تاروں کے ایک سیٹ کے لیے ایک لاحقہ درخت ہے۔ کل لمبائی کے تاروں کے سیٹ کو دیکھتے ہوئے، یہ ایک پیٹریشیا کا درخت ہے جس میں تاروں کے تمام لاحقہ ہوتے ہیں۔ یہ زیادہ تر بائیو انفارمیٹکس میں استعمال ہوتا ہے۔ فنکشنلٹی یہ وقت اور جگہ میں بنایا جا سکتا ہے، اور وقت میں لمبائی کی تار کے تمام واقعات کو تلاش کرنے کے لیے استعمال کیا جا سکتا ہے، جو کہ غیر علامتی طور پر زیادہ سے زیادہ ہے (یہ فرض کرتے ہوئے کہ حروف تہجی کا سائز مستقل ہے)۔ اس طرح کے درخت کی تعمیر کرتے وقت، ہر تار کو ایک منفرد حروف تہجی سے باہر کے مارکر کی علامت (یا تار) کے ساتھ پیڈ کیا جانا چاہیے تاکہ یہ یقینی بنایا جا سکے کہ کوئی لاحقہ دوسرے کا سبسٹرنگ نہیں ہے، اس بات کی ضمانت دیتے ہوئے کہ ہر لاحقہ کی نمائندگی ایک منفرد لیف نوڈ کے ذریعے کی جاتی ہے۔ جی ایس ٹی کی تعمیر کے لیے الگورتھم میں یوکنن کا الگورتھم (1995) اور میک کریٹ کا الگورتھم (1976) شامل ہیں۔ مثال اے بی اے بی اور بی اے بی اے تاروں کے لیے ایک لاحقہ درخت اوپر کی شکل میں دکھایا گیا ہے۔ انہیں منفرد ٹرمینیٹر سٹرنگ $0 اور $1 کے ساتھ پیڈ کیا جاتا ہے۔ پتی کے نوڈس میں نمبر سٹرنگ نمبر اور ابتدائی پوزیشن ہیں۔ نوٹ کریں کہ کس طرح لیف نوڈس کا بائیں سے دائیں ٹریورسل لاحقہ کے ترتیب شدہ ترتیب سے مطابقت رکھتا ہے۔ ٹرمینیٹر تار یا منفرد واحد علامتیں ہو سکتی ہیں۔ جڑ سے $پر کنارے اس مثال میں چھوڑے گئے ہیں۔ متبادل عمومی لاحقہ درخت بنانے کا ایک متبادل تاروں کو جوڑنا ہے، اور نتیجے میں آنے والے تار کے لیے ایک باقاعدہ لاحقہ درخت یا لاحقہ صف بنانا ہے۔ جب کسی تلاش کے بعد ہٹ کا جائزہ لیا جاتا ہے، تو عالمی پوزیشنوں کو دستاویزات اور مقامی پوزیشنوں میں کچھ الگورتھم اور/یا ڈیٹا ڈھانچے کے ساتھ نقشہ بنایا جاتا ہے، جیسے کہ دستاویزات کی ابتدائی/اختتامی پوزیشنوں میں بائنری سرچ۔ حوالہ جات بیرونی روابط A C دو تاروں کے لیے عمومی سفکس ٹری کا نفاذ درخت (ڈیٹا ڈھانچے) ذیلی تار اشاریہ سٹرنگ ڈیٹا ڈھانچے کمپیوٹر سائنس لاحقہ