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

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

شجرة نهايات للنص BANANA . يتم إنهاء كل سلسلة فرعية بحرف خاص $ . المسارات الستة من الجذر إلى الأوراق (تظهر كمربعات) تتوافق مع اللاحقات الست A$ و NA$ و ANA$ و NANA$ و ANANA$ و BANANA$ . تعطي الأرقام الموجودة في الأوراق موضع البداية للاحقة المقابلة. تُستخدم روابط اللاحقة ، المرسومة المتقطعة ، في وقت البناء.

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

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

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

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

تاريخ

المفهوم قدم لأول مرة عن طريقWeiner (1973) بدلا من النهايات خزن  Weiner (1973) في الشجرة الرقمية البدايات كمعرف للمكان لكل بداية للنص، لكن بدلا من إنشاء النص بزمن خطي كان الإنشاء بزمن  تربيعي.

   McCreight (1976) كان الاول الذي انشأ شجرة رقمية مختصرة لكل النهايات، بالرغم من أن النهاية التي تبدأ ب $i$ في العادة أطول من البداية المعرفة لها، مسارهما الممثل في الشجرة الرقمية المختصرة لا يختلف في الطول، من جهة أخرى، McCreight استطاع الاستغناء عن اغلبية مباني المعلومات الاضافية ل Weiner's , بقي فقط الروابط بين النهايات للنص. Ukkonen (1995) بسط أكثر الإنشاء،Ukkonen زود أول إنشاء لشجرة نهايات النص على شبكة االتواصل الاجتماعي، الآن معروفة ب خوارزمية Ukkonen , في وقت إنشاء مطابق لاسرع الخوارزميات آنذاك، تلك الخوارزميات طبقت بسرعة خطية لعدد ثابت من الحروف الابجدية، وفي الوقت الاسوء $O(n\log n)$.

Farach (1997) زود أول خوارزمية إنشاء لشجرة نهايات النص التي تناسب لكل الابجديات. في الاخص أول خوارزمية بسرعة خطية لنصوص من اعداد صحيحة في مجال متعدد الحدود (polynomial).

خوارزمية Farach's أصبحت الاساس للخوارزميات الجديدة لانشاء كلا شجرة نهايات النص ومصفوفة نهايات النص مثال: في الذاكرة الخارجية، المختصرات إلى اخره. تعريفنرمز ل شجرة نهايات النص ب $S$ وطولها ب $n$ التي معرفة كالتالي:

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

بسبب انه لا يوجد شجرة نهايات النص لكل النصوص،$S$ يبطن مع رمز لكل اطراف النهايات لا يظهر في النص هذا الامر يضمن ان لا تكون ايا نهاية تكن بداية ل أخرى لذلك يتواجد $n$ عقد ل $S$ .

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

• ابحث عن أطول بادئة مشتركة بين اللواحق $S_{i}[p..n_{i}]$ و $S_{j}[q..n_{j}]$ في $\Theta (1)$.
• ابحث عن نمط P بطول m مع عدم تطابق k بحد أقصى $O(kn+z)$ الوقت، حيث z هو عدد الزيارات.
• جد كل $z$ متناظرات قصوى في $\Theta (n)$ ، أو $\Theta (gn)$ الوقت إذا كانت فجوات في الطول $g$ مسموح، أو $\Theta (kn)$ إذا $k$ يسمح بعدم التطابق.
• جد كل $z$ جنبا إلى جنب يكرر في $O(n\log n+z)$ و k -mismatch tandem يتكرر في $O(kn\log(n/k)+z)$.
• ابحث عن أطول سلاسل فرعية شائعة على الأقل $k$ سلاسل في $D$ إلى عن على $k=2,\dots ,K$ في $\Theta (n)$ زمن.
• ابحث عن أطول سلسلة فرعية متناظرة لسلسلة معينة (باستخدام شجرة اللاحقة المعممة للسلسلة وعكسها) في الوقت الخطي.