سلسلة فرعية

في نظرية اللغات الرسمية وعلوم الحاسوب ، السلسلة الفرعية هي تسلسل متصل من الأحرف داخل سلسلة نصية . على سبيل المثال، " the best of " هي سلسلة فرعية من " It was the best of times ". في المقابل، " Itwastimes " هي تسلسل فرعي من " It was the best of times "، ولكنها ليست سلسلة فرعية.

تُعتبر البادئات واللواحق حالات خاصة من السلاسل الفرعية. بادئة السلسلة${\displaystyle S}$هي سلسلة فرعية من${\displaystyle S}$يحدث ذلك في بداية${\displaystyle S}$وبالمثل، لاحقة سلسلة نصية${\displaystyle S}$هي سلسلة فرعية تظهر في نهاية${\displaystyle S}$.

ستكون السلاسل الفرعية للسلسلة " apple " هي: " a " و " ap " و " app " و " appl " و " apple " و " p " و " pp " و " ppl " و " pple " و " pl " و " ple " و " l " و " le " و " e " و "" (لاحظ السلسلة الفارغة في النهاية).

خيط${\displaystyle u}$هو جزء (أو عامل) ^{[ 1 ]} من سلسلة نصية${\displaystyle t}$إذا كان هناك سلسلتان${\displaystyle p}$و${\displaystyle s}$بحيث${\displaystyle t=pus}$. على وجه الخصوص، السلسلة الفارغة هي سلسلة فرعية من كل سلسلة.

مثال: السلسلة${\displaystyle u={\texttt {ana}}}$يساوي السلاسل الفرعية (والتسلسلات الفرعية) من${\displaystyle t={\texttt {banana}}}$عند إزاحتين مختلفتين:

موز ||||| أنا|| ||| أنا

يتم الحصول على أول ظهور مع${\displaystyle p={\texttt {b}}}$و${\displaystyle s={\texttt {na}}}$بينما يتم الحصول على الظهور الثاني مع ${\displaystyle p={\texttt {ban}}}$و${\displaystyle s}$كونها سلسلة فارغة.

السلسلة الفرعية من سلسلة نصية هي بادئة للاحقة من السلسلة النصية، والعكس صحيح؛ على سبيل المثال، nanهي بادئة لـ nana، والتي بدورها لاحقة لـ banana.${\displaystyle u}$هي سلسلة فرعية من${\displaystyle t}$وهي أيضًا سلسلة فرعية ، وهو مفهوم أعمّ. يمكن إيجاد تكرارات نمط معين في سلسلة نصية معينة باستخدام خوارزمية بحث السلاسل . يُعرف إيجاد أطول سلسلة نصية تُساوي سلسلة فرعية من سلسلتين نصيتين أو أكثر بمسألة أطول سلسلة فرعية مشتركة . في الأدبيات الرياضية، تُسمى السلاسل الفرعية أيضًا بالكلمات الفرعية (في أمريكا) أو العوامل (في أوروبا).

خيط${\displaystyle p}$هو بادئة ^{[ 1 ]} لسلسلة نصية${\displaystyle t}$إذا كان هناك سلسلة${\displaystyle s}$بحيث${\displaystyle t=ps}$لا يُساوي البادئة الصحيحة لسلسلة نصية السلسلة نفسها؛ ^{[ 2 ]} كما أن بعض المصادر ^{[ 3 ]} تُقيّد البادئة الصحيحة بأن تكون غير فارغة. ويمكن اعتبار البادئة حالة خاصة من السلسلة الفرعية.

مثال: السلسلة banتساوي بادئة (وسلسلة فرعية وتسلسل فرعي) من السلسلة banana:

موز ||| حظر

يُستخدم رمز المجموعة الفرعية المربعة أحيانًا للإشارة إلى البادئة، بحيث${\displaystyle p\sqsubseteq t}$يشير إلى أن${\displaystyle p}$هو بادئة لـ${\displaystyle t}$. هذا يحدد علاقة ثنائية على السلاسل، تسمى علاقة البادئة ، وهي نوع خاص من ترتيب البادئة .

خيط${\displaystyle s}$هو لاحقة ^{[ 1 ]} لسلسلة نصية${\displaystyle t}$إذا كان هناك سلسلة${\displaystyle p}$بحيث${\displaystyle t=ps}$اللاحقة الصحيحة لسلسلة نصية لا تساوي السلسلة نفسها. تفسير أضيق هو أنها ليست فارغة أيضاً.يمكن اعتبار اللاحقة حالة خاصة من السلسلة الفرعية.

مثال: السلسلة nanaتساوي لاحقة (وسلسلة فرعية وتسلسل فرعي) من السلسلة banana:

موز |||| نانا

شجرة اللواحق للسلسلة النصية هي بنية بيانات من نوع "تراي" تمثل جميع لواحقها. تُستخدم أشجار اللواحق على نطاق واسع في خوارزميات السلاسل النصية . أما مصفوفة اللواحق فهي نسخة مبسطة من هذه البنية، حيث تُدرج مواقع بداية اللواحق بترتيب أبجدي، ولها العديد من التطبيقات نفسها.

الحد هو لاحقة وبادئة لنفس السلسلة، على سبيل المثال "${\displaystyle {\texttt {bab}}}$" هو حدود "${\displaystyle {\texttt {باباب}}}$"(وأيضًا من "${\displaystyle {\texttt {بابون}}\,\,{\texttt {يأكل}}\,\,{\texttt {كباب}}}$").

سلسلة فائقة لمجموعة منتهية${\displaystyle P}$مجموعة السلاسل هي سلسلة واحدة تحتوي على كل سلسلة في${\displaystyle P}$كسلسلة فرعية. على سبيل المثال،${\displaystyle {\texttt {bcclabccefab}}}$هي سلسلة فائقة من${\displaystyle P=\{{\texttt {abcc}},{\texttt {efab}},{\texttt {bccla}}\}}$، و${\displaystyle {\texttt {efabccla}}}$وهي أقصر. دمج جميع أعضاء${\displaystyle P}$، وبترتيب عشوائي، يحصل دائمًا على سلسلة فائقة تافهة من${\displaystyle P}$إن إيجاد الأوتار الفائقة التي يكون طولها أصغر ما يمكن هو مشكلة أكثر إثارة للاهتمام.

يُطلق على السلسلة التي تحتوي على كل تبديل ممكن لمجموعة أحرف محددة اسم التبديل الفائق .

• فهرس السلاسل الفرعية
• آلة لاحقة