Generalized suffix tree
কম্পিউটার বিজ্ঞানে, একটি সাধারণীকৃত প্রত্যয় বৃক্ষ হল স্ট্রিংয়ের একটি সেটের জন্য একটি প্রত্যয় বৃক্ষ। মোট দৈর্ঘ্যের স্ট্রিংয়ের সেট দেওয়া হলে, এটি একটি প্যাট্রিসিয়া গাছ যা স্ট্রিংয়ের সমস্ত প্রত্যয় ধারণ করে। এটি বেশিরভাগ বায়োইনফরমেটিক্সে ব্যবহৃত হয়। কার্যকারিতা এটি সময় এবং স্থানে তৈরি করা যেতে পারে, এবং সময়ের দৈর্ঘ্যের একটি স্ট্রিংয়ের সমস্ত ঘটনা খুঁজে বের করতে ব্যবহার করা যেতে পারে, যা অ্যাসিম্পটোটিকভাবে সর্বোত্তম (বর্ণমালার আকার ধ্রুবক ধরে নেওয়া)। এই জাতীয় গাছ তৈরি করার সময়, প্রতিটি স্ট্রিংকে একটি অনন্য বর্ণমালার বাইরে চিহ্নিতকারী প্রতীক (বা স্ট্রিং) দিয়ে প্যাড করা উচিত যাতে নিশ্চিত করা যায় যে কোনও প্রত্যয় অন্যটির সাবস্ট্রিং নয়, প্রতিটি প্রত্যয়কে একটি অনন্য পাতার নোড দ্বারা প্রতিনিধিত্ব করা হয়। জিএসটি নির্মাণের জন্য অ্যালগরিদমগুলির মধ্যে রয়েছে ইউকনেনের অ্যালগরিদম (1995) এবং ম্যাকক্রাইটের অ্যালগরিদম (1976)। উদাহরণ ABAB এবং BABA স্ট্রিংয়ের জন্য একটি প্রত্যয় গাছ উপরের একটি চিত্রে দেখানো হয়েছে। এগুলি অনন্য টার্মিনেটর স্ট্রিং $0 এবং $1 দিয়ে প্যাড করা হয়। লিফ নোডের সংখ্যাগুলি হল স্ট্রিং নম্বর এবং শুরুর অবস্থান। লক্ষ্য করুন কিভাবে লিফ নোডের বাম থেকে ডান দিকের ট্র্যাভারসাল প্রত্যয়ের সাজানো ক্রমের সাথে মিলে যায়। টার্মিনেটরগুলি স্ট্রিং বা অনন্য একক প্রতীক হতে পারে। মূল থেকে $-এর প্রান্তগুলি এই উদাহরণে বাদ দেওয়া হয়েছে। বিকল্প একটি সাধারণীকৃত প্রত্যয় গাছ তৈরির বিকল্প হল স্ট্রিংগুলিকে একত্রিত করা এবং ফলস্বরূপ স্ট্রিংয়ের জন্য একটি নিয়মিত প্রত্যয় গাছ বা প্রত্যয় অ্যারে তৈরি করা। অনুসন্ধানের পরে যখন হিটগুলি মূল্যায়ন করা হয়, তখন বিশ্বব্যাপী অবস্থানগুলি কিছু অ্যালগরিদম এবং/অথবা ডেটা কাঠামোর সাথে নথি এবং স্থানীয় অবস্থানগুলিতে ম্যাপ করা হয়, যেমন নথির শুরু/শেষের অবস্থানে বাইনারি অনুসন্ধান। তথ্যসূত্র বাইরের লিঙ্ক দুটি স্ট্রিংয়ের জন্য জেনারেলাইজড সফিক্স ট্রি-র এ সি বাস্তবায়ন গাছ (ডেটা স্ট্রাকচার) সাবস্ট্রিং সূচক স্ট্রিং ডেটা স্ট্রাকচার কম্পিউটার বিজ্ঞান প্রত্যয়