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

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

1٬444 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: خوارزمية البحث عن السلاسل ، والتي تُسمى أحيانًا خوارزمية مطابقة السلاسل ، هي خوارزمية تبحث في نص عن أجزاء تتطابق مع النمط معين. تتناول المقالة 15 قسماً، منها «خوارزميات النمط الواحد»، «البحث عن سلسلة ساذجة» و«طرق الفهرس».
المحتويات
  1. خوارزميات النمط الواحد
  2. البحث عن سلسلة ساذجة
  3. طرق الفهرس
  4. الخوارزميات التي تستخدم مجموعة محدودة من الأنماط
  5. التصنيف باستخدام برامج المعالجة المسبقة
  6. قائمة NIST لخوارزميات مطابقة السلاسل
  7. التصنيف حسب استراتيجيات المطابقة
  8. البحث القائم على أتمتة الحالة المحدودة
  9. أكثر من مساحة
  10. أعقاب
  11. ملخص
  12. متغيرات أخرى
  13. (PDF) تحسين مطابقة السلاسل التقريبية المفردة والمتعددة
  14. لون
  15. التصنيف حسب عدد الأنماط

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

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

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

خوارزميات النمط الواحد

وفي السياق ذاته، 3.^ يمكن تمديده للتعامل مع مطابقة السلسلة التقريبية ومجموعات الأنماط (التي قد تكون لا نهائية) الممثلة كلغات عادية .[ بحاجة لمصدر ]

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

1.يتم التعبير عن الأوقات المقاربة باستخدام الرموز O وΩ وΘ .

ومن جهة أخرى، 2.^ يتم استخدامه لتنفيذ وظائف البحث memmem و strstr في مكتبات C القياسية glibc و musl.

البحث عن سلسلة ساذجة

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

طرق الفهرس

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

الخوارزميات التي تستخدم مجموعة محدودة من الأنماط

الخوارزميات التي تستعمل عددًا لا نهائيًا من الأنماط

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

وعلى صعيد آخر، في التجميع التالي، M هو طول النمط الأطول، m هو الطول الكلي للأنماط، n هو طول النص القابل للبحث، o هو عدد مرات الظهور.

التصنيف باستخدام برامج المعالجة المسبقة

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

قائمة NIST لخوارزميات مطابقة السلاسل

من جانب آخر، خوارزميات مطابقة السلسلة الدقيقة - الرسوم المتحركة في Java، وصف مفصل وتنفيذ C للعديد من الخوارزميات.

وفي السياق ذاته، StringsAndChars – تنفيذات للعديد من خوارزميات مطابقة السلاسل (للأنماط الفردية والمتعددة) في Java

ومن جهة أخرى، StringSearch – خوارزميات مطابقة الأنماط عالية الأداء في Java – تنفيذ الكثير من خوارزميات مطابقة السلاسل في Java (BNDM، Boyer-Moore-Horspool، Boyer-Moore-Horspool-Raita، Shift-Or)

التصنيف حسب استراتيجيات المطابقة

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

البحث القائم على أتمتة الحالة المحدودة

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

أكثر من مساحة

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

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

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

في حالات أقل شيوعًا، يتم استخدام شرطة أو شرطة ناعمة

ومن ناحية أخرى، تتضمن الكثير من اللغات روابط ، حيث يكون الحرف المركب الواحد معادلاً لحرفين أو أكثر آخرين.

في هذا الإطار، تشمل الكثير من أنظمة الرموز أحرفًا متطابقة في المعنى (على الأقل لبعض الأغراض):

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

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

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

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

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

أعقاب

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

ملخص

ومن جهة أخرى، بعض الكتب يُذاق فقط، وبعضها يُبتلع، وقليل منها يُمضغ ويُهضم.

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

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

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

علاوةً على ذلك، قد يَطلب المرء أول ظهور لكلمة "to"، وهي الكلمة الرابعة؛ أو جميع الحالات التي تظهر فيها، و عددها 3؛ أو الظهور الأخير، وهي الكلمة الخامسة من النهاية.

متغيرات أخرى

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

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

(PDF) تحسين مطابقة السلاسل التقريبية المفردة والمتعددة

ومن جهة أخرى، نيوتينجو - خوارزمية مطابقة الأنماط عالية الأداء في لغة سي - تطبيقات خوارزميات مطابقة السلاسل المتجهة والقياسية في لغة سي

ومن جهة أخرى، Kalign2: محاذاة متعددة عالية الأداء لتسلسلات البروتين والنوكليوتيدات مما يسمح بالميزات الخارجية

لون

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

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

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

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

التصنيف حسب عدد الأنماط

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

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

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

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