خوارزمية بحث في سلسلة محارف

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

مثال أساسي على البحث في السلاسل هو عندما يكون النمط والنص المُراد البحث فيها عبارة عن مصفوفات من عناصر تنتمي إلى أبجدية ( مجموعة محدودة ) Σ. قد تكون Σ أبجدية لغة بشرية، مثل، قد تستخدم الحروف من A إلى Z والتطبيقات الأخرى أبجدية ثنائية (Σ = {0,1}) أو أبجدية DNA (Σ = {A,C,G,T}) في المعلوماتية الحيوية .

في الممارسة العملية، قد تتأثر طريقة خوارزمية البحث عن السلاسل النصية بصيغة ترميز السلسلة. على وجه الخصوص، إذا كان الترميز المستخدم ذا عرض متغير ، فقد يستغرق الوصول إلى الحرف رقم N وقتًا يتناسب مع N. مما قد يؤدي إلى إبطاء بعض خوارزميات البحث بشكل ملحوظ. أحد الحلول العديدة الممكنة هو البحث عن تسلسل وحدات التعليمات البرمجية بدلاً من ذلك، ولكن القيام بِذلك قد يؤدي إلى تطابقات خاطئة ما لم يتم تصميم الترميز خصيصًا لتجنب ذلك.

 ملخص 
أبسط حالة من حالات البحث في السلاسل النصية تتضمن سلسلة واحدة (غالبًا ما تكون طويلة جدًا)، تُعرف أحيانًا بـ كومة القش ، وسلسلة أخرى (غالبًا ما تكون قصيرة جدًا)، تُعرف بـ" الإبرة" . و الهدف هو العثور على واحدة أو أكثر من مرات ظهور الإبرة داخل كومة القش. على سبيل المثال، قد يبحث المرء عن "to " ضمن:
 بعض الكتب يُذاق فقط، وبعضها يُبتلع، وقليل منها يُمضغ ويُهضم.
قد يَطلب المرء أول ظهور لكلمة "to"، وهي الكلمة الرابعة؛ أو جميع الحالات التي تظهر فيها، و عددها 3؛ أو الظهور الأخير، وهي الكلمة الخامسة من النهاية.

لكن من الشائع جدًا إضافة قيود مختلفة. على سبيل المثال، قد يرغب المرء في مطابقة "الإبرة" فقط عندما تتكوّن من كلمة واحدة (أو أكثر) كاملة - ربما تُعرَّف على أنها لا تحتوي على حروف أخرى مجاورة مباشرة من أي جانب. في هذه الحالة، ينبغي أن تفشل عملية البحث عن "hew" أو "low" لجملة المثال أعلاه، على الرغم من ظهور هذه السلاسل الحرفية.

مثال شائع آخر يتعلق بـ"التطبيع". في كثير من الحالات، يجب أن تنجح عملية البحث عن عبارة مثل "to be" حتى في الأماكن التي يوجد فيها شيء آخر يتدخل بين "to" و"be":

 أكثر من مساحة
 أحرف "المسافة البيضاء" الأخرى مثل علامات التبويب، والمسافات غير القابلة للكسر، وفواصل الأسطر، وما إلى ذلك.
 في حالات أقل شيوعًا، يتم استخدام شرطة أو شرطة ناعمة
 في النصوص المنظمة، العلامات أو حتى الأشياء الكبيرة بشكل تعسفي ولكن "بين قوسين" مثل الحواشي، أو أرقام القائمة أو العلامات الأخرى، والصور المضمنة، وما إلى ذلك.

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

أخيرًا، بالنسبة للسلاسل التي تمثل لغة طبيعية، تدخل جوانب اللغة نفسها في العملية. على سبيل المثال، قد يرغب المرء في إيجاد جميع تكرارات "كلمة" رغم من وجود تهجئات أو بادئات أو لاحقات بديلة، وما إلى ذلك.

نوع آخر أكثر تعقيدًا من البحث وهو البحث بالتعبيرات النمطية ، حيث يقوم المستخدم بإنشاء نمط من الأحرف أو الرموز الأخرى، وأي تطابق مع النمط يجب أن يفي بمتطلبات البحث. على سبيل المثال، لالتقاط الكلمة "color" الأمريكية الإنجليزية ومرادفها البريطاني"colour"، بدلاً من البحث عن سلسلتين حرفيتين مختلفتين، قد يستخدم المرء تعبيرًا منتظمًا مثل:

 لون 
حيث أن "?" يجعل تقليديا الحرف السابق ("u") اختياريا.

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

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

 أمثلة على خوارزميات البحث 

 البحث عن سلسلة ساذجة 
طريقة بسيطة وغير الفعالة لمعرفة مكان حدوث سلسلة داخل أخرى هي الفحص عند كل موضع، واحدًا تلو الآخر. أولاً، نتحقق إذا كان هناك نسخة من الإبرة تبدأ عند الحرف الأول من كومة القش؛ إذا لم تكن موجودة، نتحقق عند الحرف الثاني، وهكذا. في الحالة العادية، نحتاج فقط لفحص حرف أو حرفين عند كل موضع خاطئ لنرى أنه موضع خاطئ، لذا في الحالة المتوسطة، يستغرق هذا الأمر O ( n + m ) خطوات، حيث n هو طول كومة القش و m هو طول الإبرة؛ ولكن في أسوأ الحالات، عند البحث عن سلسلة مثل "aaaab" في سلسلة مثل "aaaaaaaaab"، يستغرق الأمر O ( nm )

 البحث القائم على أتمتة الحالة المحدودة 
يسار|289x289بك
في هذا النهج، تجنب التراجع عن طريق بناء أتمتة محدودة حتمية (DFA) تتعرف على سلسلة البحث المخزنة. هذه الآلات مكلفة في البناء — عادةً ما تُنشأ باستخدام مجموعة الطاقة — لكنها سريعة جدًا في الاستخدام. على سبيل المثال، يتعرف DFA الموضح على اليمين على كلمة "MOMMY". يتم تعميم هذا النهج في كثير من الأحيان في الممارسة العملية للبحث عن تعبيرات منتظمة عشوائية.

 أعقاب 
يقوم خوارزمية Knuth–Morris–Pratt بحساب آلة حالات منتهية حتمية DFA تتعرف على المدخلات التي تحتوي على السلسلة المُراد البحث عنها كلاحقة، بينما تبدأ Boyer–Moore البحث من نهاية الإبرة، مما يسمح لها عادةً بالقفز للأمام بطول الإبرة بالكامل في كل خطوة. يتتبع Baeza–Yates ما إذا كانت الأحرف j السابقة عبارة عن بادئة لسلسلة البحث، وبالتالي فهو قابل للتكيف مع البحث عن السلسلة الغامضة . خوارزمية bitap هي تطبيق لمنهج بايزا-ياتس.

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

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

 تصنيف خوارزميات البحث 

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

 خوارزميات النمط الواحد 
في التَجمِيع التالي، m هو طول النَمط، وn هو طُول النَص القَابِل للبحث، و k = |Σ| هو حجم الأبجدية.
خوارزمية وقت المعالجة المسبقة وقت المطابقة فضاء خوارزمية ساذجة لا أحد Θ(n+m) في المتوسط، O(mn) لا أحد رابين-كارب Θ(م) Θ(n) في المتوسط، O(mn) في أسوأ الأحوال O(1) كنوث-موريس-برات Θ(م) Θ(n) Θ(م) بوير مور Θ(م + ك) Ω(n/m) في أفضل الأحوال، O(mn) في أسوأ الأحوال Θ(k) خوارزمية ثنائية الاتجاه  Θ(م) على) O(log(m)) مطابقة DAWG غير الحتمية العكسية (BNDM)  O(م) Ω(n/m) في أفضل الأحوال، O(mn) في أسوأ الأحوال مطابقة أوراكل العكسية (BOM)  O(م) O(mn)

 1.يتم التعبير عن الأوقات المقاربة باستخدام الرموز O وΩ وΘ .
 2.^ يتم استخدامه لتنفيذ وظائف البحث memmem و <i id="mwvA">strstr</i> في مكتبات C القياسية glibc  و musl.
 3.^ يمكن تمديده للتعامل مع مطابقة السلسلة التقريبية ومجموعات الأنماط (التي قد تكون لا نهائية) الممثلة كلغات عادية .[ بحاجة لمصدر ]

يُعد خوارزمية البحث عن السلاسل Boyer–Moore معيارًا قياسيًا في أدبيات البحث العملي عن السلاسل.

 الخوارزميات التي تستخدم مجموعة محدودة من الأنماط 
في التجميع التالي، M هو طول النمط الأطول، m هو الطول الكلي للأنماط، n هو طول النص القابل للبحث، o هو عدد مرات الظهور.
خوارزمية تمديد وقت المعالجة المسبقة وقت المطابقة فضاء أهو-كوراسيك كنوث-موريس-برات Θ(م) Θ(n + o) Θ(م) كومنتس-والتر بوير مور Θ(م) Θ(M * n) أسوأ حالة دون خطي في المتوسط  Θ(م) مجموعة-BOM مطابقة أوراكل العكسية

 الخوارزميات التي تستخدم عددًا لا نهائيًا من الأنماط 
من الطبيعي، أنه لا يمكن تعداد الأنماط بشكل نهائي في هذه الحالة. يتم تمثيلها عادةً بقواعد نحوية منتظمة أو تعبير منتظم .

 التصنيف باستخدام برامج المعالجة المسبقة 
توجد تصنيفات أخرى ممكنة. أحد أكثرها شيوعًا يستخدم المعالجة المُسبقة كمعيار رئيسي.
+فئات خوارزميات البحث عن السلسلة Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ . النص غير معالج مسبقًا نص معالج مسبقًا الأنماط غير المعالجة مسبقًا الخوارزميات الأولية طرق الفهرس الأنماط المعالجة مسبقًا محركات البحث المُنشأة طرق التوقيع 

 التصنيف حسب استراتيجيات المطابقة 
تصنيف آخر يُقسم الخوارزميات حسب استراتيجية المطابقة الخاصة بها:

 قم بمطابقة البادئة أولاً (Knuth–Morris–Pratt، Shift-And، Aho–Corasick)
 قم بمطابقة اللاحقة أولاً (Boyer–Moore والمتغيرات، Commentz-Walter)
 قم بمطابقة أفضل عامل أولاً (BNDM، BOM، Set-BOM)
 استراتيجية أخرى (السذاجة، رابين-كارب، المتجهات)

 انظر أيضًا 

 محاذاة التسلسل
 مطابقة الرسم البياني
 مطابقة الأنماط
 مطابقة الأنماط المضغوطة
 مطابقة البطاقات البدل
 البحث عن النص الكامل

 المراجع 

 RS Boyer و JS Moore، خوارزمية البحث السريع عن السلسلة ، كاروم. ACM 20، (10)، 262-272(1977).
 توماس هـ. كورمين ، وتشارلز إي. ليسرسون ، ورونالد إل. ريفست ، وكليفورد ستاين . مقدمة في الخوارزميات ، الطبعة الثالثة. MIT Press و McGraw-Hill، 2009.رقم ISBN 0-262-03293-7 . الفصل 32: مطابقة السلسلة، ص. 985–1013.

 روابط خارجية 

 قائمة ضخمة من الروابط المطابقة للأنماط  آخر تحديث: 27/12/2008 20:18:38
 قائمة كبيرة (مُحافظ عليها) من خوارزميات مطابقة السلسلة
 قائمة NIST لخوارزميات مطابقة السلاسل
 StringSearch – خوارزميات مطابقة الأنماط عالية الأداء في Java – تنفيذ العديد من خوارزميات مطابقة السلاسل في Java (BNDM، Boyer-Moore-Horspool، Boyer-Moore-Horspool-Raita، Shift-Or)
 StringsAndChars – تنفيذات للعديد من خوارزميات مطابقة السلاسل (للأنماط الفردية والمتعددة) في Java
 خوارزميات مطابقة السلسلة الدقيقة - الرسوم المتحركة في Java، وصف مفصل وتنفيذ C للعديد من الخوارزميات.
 (PDF) تحسين مطابقة السلاسل التقريبية المفردة والمتعددة 
 Kalign2: محاذاة متعددة عالية الأداء لتسلسلات البروتين والنوكليوتيدات مما يسمح بالميزات الخارجية
 نيوتينجو - خوارزمية مطابقة الأنماط عالية الأداء في لغة سي - تطبيقات خوارزميات مطابقة السلاسل المتجهة والقياسية في لغة سي

تصنيف:سلسلة (علم الحاسوب)
تصنيف:حاسوب ميكانيكي
تصنيف:حاسوب محطة العمل
تصنيف:خوارزميات
تصنيف:خوارزم
تصنيف:نص
تصنيف:نصوص
تصنيف:نص برمجي مصدري