مرجع
آخر الزيارات

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

568 كلمة•0 مشاهدة•🗒️ منذ 10 أيام
باختصار: في علم الحاسوب شجرة نهايات النص أو شجرة اللواحق لسلسلة نصيّة هي شجرة رقمية مختصرة التي تحتوي على كل نهايات النص كل نص هو المفتاح ومكانهم في النص كقيم تهمّ شجرة نهايات النص تتيح تطبيق عمليات مهمة للنص بسرعة عالية. تتناول المقالة قسمين هما «تعريف» و«تاريخ».
المحتويات
  1. تعريف
  2. تاريخ
شجرة نهايات النص

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

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

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

تعريف

ابحث عن أطول بادئة مشتركة بين اللواحق و في .

جد كل جنبا إلى جنب يكرر في و k -mismatch tandem يتكرر في .

وفي هذا السياق، السلسلة التي تم الحصول عليها من خلال ربط جميع عناوين السلسلة الموجودة على المسار من الجذر إلى الورقة

إضافةً إلى ذلك، ابحث عن أطول سلسلة فرعية متناظرة لسلسلة معينة (باستخدام شجرة اللاحقة المعممة للسلسلة وعكسها) في الوقت الخطي.

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

ومن ناحية أخرى، ابحث عن نمط P بطول m مع عدم تطابق k بحد أقصى الوقت، حيث z هو عدد الزيارات.

من جهة ثانية، جد كل متناظرات قصوى في ، أو الوقت إذا كانت فجوات في الطول مسموح، أو إذا يسمح بعدم التطابق.

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

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

كذلك، ابحث عن أطول سلاسل فرعية شائعة على الأقل سلاسل في إلى عن على في زمن.

تاريخ

وفي هذا الصدد، في عام 1997، قدم العالم مارتن فاراش (Farach) أول خوارزمية لإنشاء شجرة اللواحق تناسب جميع أنواع الأبجديات؛ وتحديداً أول خوارزمية تعمل بزمن خطي للنصوص المكونة من أعداد صحيحة ضمن مجال متعدد الحدود (Polynomial range). أصبحت خوارزمية فاراش الأساس للخوارزميات الجديدة المستعملة في إنشاء كل من شجرة اللواحق ومصفوفة اللواحق، كما في تطبيقات الذاكرة الخارجية والمختصرات وغيرها.

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

وفي السياق ذاته، قُدّم هذا المفهوم لأول مرة من قبل العالم بيتر وينر (Weiner) عام 1973. وبدلاً من اللواحق (Suffixes)، قام وينر بتخزين السوابق (Prefixes) في شجرة رقمية كمعرف للموقع لكل بداية للنص؛ إلا أن عملية الإنشاء كانت تتم في زمن تربيعي بدلاً من زمن خطي.

من جهة ثانية، في سنة 1976، كان إدوارد ماكريت (McCreight) أول من أنشأ شجرة رقمية مختصرة لكل اللواحق. وبالرغم من أن اللاحقة التي تبدأ عند i تكون عادةً أطول من السابقة المعرفة لها، إلا أن مسارهما الممثل في الشجرة الرقمية المختصرة لا يختلف في الطول. من ناحية أخرى، استطاع ماكريت الاستغناء عن أغلبية هياكل البيانات الإضافية التي استعملها وينر، حيث أبقى فقط على الروابط بين لواحق النص.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.