شجرة نهايات النص

في علم الحاسوب شجرة نهايات النص أو شجرة اللواحق لسلسلة نصيّة هي شجرة رقمية مختصرة التي تحتوي على كل نهايات النص كل نص هو المفتاح ومكانهم في النص كقيم تهمّ شجرة نهايات النص تتيح تطبيق عمليات مهمة للنص بسرعة عالية.

بناء شجرة نهايات النص يستغرق سرعة خطية وياخذ حيز خطي، بعد  البناء العديد من العمليات يتم عملها بسرعة مثال: تحديد مكان  نص فرعي، تحديد مكان نص فرعي مع عدد من الاخطاء فيه، تحديد مكان لمطابقات لنمط ايا تعبير يكن إلى نهايته.

شجرة نهايات النص تزود أول حل خطي لمشكلة أطول خط فرعي مشترك بين نصين.

تسريع هذه العمليات تحقق مقابل ثمن.

في العادة شجرة نهايات النص تشغل حيز أكبر من النص العادي.

 تاريخ 
قُدّم هذا المفهوم لأول مرة من قبل العالم بيتر وينر (Weiner) عام 1973.Weiner, P. (1973), "Linear pattern matching algorithms", 14th Annual Symposium on Switching and Automata Theory. وبدلاً من اللواحق (Suffixes)، قام وينر بتخزين السوابق (Prefixes) في شجرة رقمية كمعرف للموقع لكل بداية للنص؛ إلا أن عملية الإنشاء كانت تتم في زمن تربيعي بدلاً من زمن خطي.

في عام 1976، كان إدوارد ماكريت (McCreight) أول من أنشأ شجرة رقمية مختصرة لكل اللواحق.McCreight, Edward M. (1976), "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM. وبالرغم من أن اللاحقة التي تبدأ عند i تكون عادةً أطول من السابقة المعرفة لها، إلا أن مسارهما الممثل في الشجرة الرقمية المختصرة لا يختلف في الطول. من ناحية أخرى، استطاع ماكريت الاستغناء عن أغلبية هياكل البيانات الإضافية التي استخدمها وينر، حيث أبقى فقط على الروابط بين لواحق النص.

قام العالم إسكو أوكونين (Ukkonen) في عام 1995 بتبسيط عملية الإنشاء بشكل أكبر؛Ukkonen, E. (1995), "On-line construction of suffix trees", Algorithmica. حيث قدم أول خوارزمية لإنشاء شجرة اللواحق بنمط "الإنشاء المباشر" (On-line)، وهي المعروفة الآن باسم خوارزمية أوكونين. تميزت هذه الخوارزمية بزمن إنشاء يطابق أسرع الخوارزميات آنذاك، حيث تعمل بزمن خطي في حال كان عدد أحرف الأبجدية ثابتاً، وفي الحالة الأسوأ تعمل بزمن قدره .

في عام 1997، قدم العالم مارتن فاراش (Farach) أول خوارزمية لإنشاء شجرة اللواحق تناسب جميع أنواع الأبجديات؛Farach, Martin (1997), "Optimal suffix tree construction with large alphabets", 38th Annual Symposium on Foundations of Computer Science. وتحديداً أول خوارزمية تعمل بزمن خطي للنصوص المكونة من أعداد صحيحة ضمن مجال متعدد الحدود (Polynomial range). أصبحت خوارزمية فاراش الأساس للخوارزميات الجديدة المستخدمة في إنشاء كل من شجرة اللواحق ومصفوفة اللواحق، كما في تطبيقات الذاكرة الخارجية والمختصرات وغيرها.

 تعريف 
نرمز لشجرة نهايات النص بـ  وطولها بـ  التي معرفة كالتالي:

 للشجرة بالضبط  اوراق شجر مرقمة من 1 لـ 
 ما عدا الجذر كل عقدة داخلية لها على الاقل ولدان
 يتم تمييز كل حافة بسلسلة فرعية غير فارغة لـ 
 لا يمكن أن تحتوي حافتان تبدأان من عقدة على تسميات سلسلة تبدأ بالحرف نفسه.
 السلسلة التي تم الحصول عليها من خلال ربط جميع عناوين السلسلة الموجودة على المسار من الجذر إلى الورقة
بسبب انه لا يوجد شجرة نهايات النص لكل النصوص، يبطن مع رمز لكل اطراف النهايات لا يظهر في النص هذا الامر يضمن ان لا تكون ايا نهاية تكن بداية ل أخرى لذلك يتواجد  عقد ل  .

نظرًا لأن جميع العقد الداخلية غير الجذر تتفرع، يمكن أن يكون هناك n - 1 على الأكثر من هذه العقد و اوراق شجر / 1- عقد داخلية / 1 جذر ++1-1=2n لذلك يوجد 2n عقد.

 ابحث عن أطول بادئة مشتركة بين اللواحق  و  في ., p.196.
 ابحث عن نمط P بطول m مع عدم تطابق k بحد أقصى  الوقت، حيث z هو عدد الزيارات., p.200.
 جد كل  متناظرات قصوى في  ، , p.198. أو  الوقت إذا كانت فجوات في الطول  مسموح، أو  إذا  يسمح بعدم التطابق., p.201.
 جد كل  جنبا إلى جنب يكرر في  و k -mismatch tandem يتكرر في ., p.204.
 ابحث عن أطول سلاسل فرعية شائعة على الأقل  سلاسل في  إلى عن على  في  زمن., p.205.
 ابحث عن أطول سلسلة فرعية متناظرة لسلسلة معينة (باستخدام شجرة اللاحقة المعممة للسلسلة وعكسها) في الوقت الخطي., pp.197–199.

 مراجع 

تصنيف:أشجار (بنى معطيات)