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

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

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

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

ملخص

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

بعض الكتب يجب تذوقها، وبعضها الآخر يجب ابتلاعها، وقليل منها يجب مضغها وهضمها.

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

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

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

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

تتضمن العديد من أنظمة الرموز أحرفًا مترادفة (على الأقل لبعض الأغراض):

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

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

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

لون

حيث أن علامة الاستفهام "؟" تجعل الحرف السابق ("u") اختياريًا بشكل تقليدي.

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

تُعدّ مشكلة المطابقة التامة القصوى (MEM) مشكلةً مشابهةً في مجال المعلوماتية الحيوية وعلم الجينوم. ^{[ 1 ]} فعند وجود سلسلتين نصيتين، تكون المطابقة التامة القصوى عبارة عن سلاسل فرعية مشتركة لا يمكن تمديدها من اليسار أو اليمين دون التسبب في عدم تطابق. ^{[ 2 ]}

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

بحث بسيط عن سلسلة نصية

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

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

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

بقايا

تحسب خوارزمية كنوت-موريس-برات آلة حتمية محدودة (DFA) تتعرف على المدخلات التي تحتوي على السلسلة المراد البحث عنها كلاحقة. أما خوارزمية بوير-مور، فتبدأ البحث من نهاية الإبرة، لذا يمكنها عادةً التقدم مسافة طول الإبرة كاملةً في كل خطوة. وتتتبع خوارزمية بايزا-ييتس ما إذا كانت الأحرف j السابقة تمثل بادئة لسلسلة البحث، وبالتالي فهي قابلة للتكيف مع البحث التقريبي عن السلاسل . وتُعد خوارزمية bitap تطبيقًا لنهج بايزا-ييتس.

طرق الفهرسة

تُعالج خوارزميات البحث الأسرع النص مسبقًا. بعد إنشاء فهرس للسلاسل الفرعية ، مثل شجرة اللواحق أو مصفوفة اللواحق ، يُمكن العثور على حالات ظهور نمط معين بسرعة. على سبيل المثال، يُمكن إنشاء شجرة لواحق في $\Theta (n)$ الوقت، وكل شيء $z$ يمكن العثور على حالات تكرار نمط معين في $O(m)$ يُفترض أن حجم الأبجدية ثابت وأن جميع العقد الداخلية في شجرة اللواحق تعرف الأوراق التي تقع أسفلها. ويمكن تحقيق ذلك بتشغيل خوارزمية البحث العمقي أولاً (DFS) من جذر شجرة اللواحق.

متغيرات أخرى

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

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

التصنيف وفقًا لعدد من الأنماط

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

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

في التجميع التالي، m هو طول النمط، و n هو طول النص القابل للبحث، و k = |Σ| هو حجم الأبجدية.

الخوارزمية	وقت المعالجة المسبقة	وقت المطابقة	فضاء
خوارزمية ساذجة	لا أحد	Θ(n+m) في المتوسط، O(mn)	لا أحد
المطابقة القائمة على الأتمتة	Θ(كم)	Θ(n)	Θ(كم)
رابين-كارب	Θ(m)	Θ(n) في المتوسط، و O(mn) في أسوأ الأحوال	O(1)
كنوت-موريس-برات	Θ(m)	Θ(n)	Θ(m)
بوير-مور	Θ(m + k)	O(n/m) في أفضل الأحوال، O(mn) في أسوأ الأحوال	Θ(k)
خوارزمية ثنائية الاتجاه ^{[ 3 ]}	Θ(m)	على)	O(log(m))
المطابقة العكسية غير الحتمية DAWG (BNDM) ^{[ 4 ]}	O(m)	Ω(n/m) في أفضل الأحوال، O(mn) في أسوأ الأحوال
مطابقة أوراكل العكسية (BOM) ^{[ 5 ]}	O(m)	O(mn)

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

2. ^ يستخدم لتنفيذ وظائف البحث memmem و strstr في مكتبات glibc ^[⁶^] و musl ^[⁷^] القياسية للغة C.

3. ^ يمكن توسيعها للتعامل مع مطابقة السلاسل التقريبية ومجموعات الأنماط (التي قد تكون غير محدودة) الممثلة كلغات منتظمة .

تُعتبر خوارزمية بحث السلاسل بوير-مور المعيار القياسي في أدبيات البحث العملي عن السلاسل. ^{[ 8 ]}

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

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

الخوارزمية	امتداد	وقت المعالجة المسبقة	وقت المطابقة	فضاء
أهو-كوراسيك	كنوت-موريس-برات	Θ(m)	Θ(n + o)	Θ(m)
تعليق والتر	بوير-مور	Θ(m)	Θ(M * n) أسوأ حالة شبه خطية في المتوسط ^{[ 9 ]}	Θ(m)
مجموعة المكونات	مطابقة أوراكل العكسية

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

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

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

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

فئات خوارزميات البحث عن السلاسل النصية ^{[ 10 ]}
	نص غير معالج مسبقًا	تمت معالجة النص مسبقًا
الأنماط غير المعالجة مسبقًا	الخوارزميات الأساسية	طرق الفهرسة
أنماط مُعالجة مسبقًا	محركات البحث المصممة	أساليب التوقيع ^{[ 11 ]}

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

يصنف تصنيف آخر الخوارزميات حسب استراتيجية المطابقة الخاصة بها: ^{[ 12 ]}

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

مطابقة السلاسل في الوقت الفعلي

في مطابقة السلاسل النصية في الوقت الحقيقي، يُطلب من المُطابق إخراج استجابة بعد قراءة كل حرف من النص، تُشير إلى ما إذا كان هذا الحرف هو الأخير في المطابقة. يجب أن تُقدَّم الاستجابة في غضون زمن ثابت. تختلف متطلبات المعالجة المسبقة: فقد يُسمح بمعالجة مسبقة من رتبة O( m ) بعد قراءة النمط (ولكن قبل قراءة النص)، أو قد يُفرض شرط أكثر صرامة يقضي بتوقف المُطابق لمدة زمنية ثابتة على الأكثر بعد قراءة أي حرف من النمط (بما في ذلك الحرف الأخير). بالنسبة للنسخة الأكثر تساهلاً، إذا لم يكن هناك مانع من أن يعتمد وقت المعالجة المسبقة ومتطلبات الذاكرة على حجم الأبجدية، فإن مطابقة الأوتوماتون تُوفر حلاً في الوقت الحقيقي. طوّر زفي جليل طريقة لتحويل بعض الخوارزميات إلى خوارزميات تعمل في الوقت الحقيقي، وطبّقها لإنتاج نسخة مُعدّلة من مُطابق KMP تعمل في الوقت الحقيقي في ظل الشرط الصارم. ^{[ 13 ]}

البحث عن السلاسل النصية باستخدام عبارة "لا يهم"

في هذا الإصدار من مسألة البحث عن السلاسل النصية، يوجد رمز خاص، ø (يُقرأ: لا يهم)، والذي يمكن أن يُطابق أي رمز آخر (بما في ذلك ø آخر). يمكن أن تظهر رموز "لا يهم" إما في النمط أو في النص. في عام 2002، طُوِّرت خوارزمية لهذه المسألة تعمل في $O(n\log m)$ تم تخصيص وقت من قبل ريتشارد كول وراميش هاريهاران ، لتحسين حل من عام 1973 من قبل فيشر وباترسون والذي يتسم بالتعقيد $O(n\log m\log k)$ حيث k هو حجم الأبجدية. ^{[ 14 ]} وقد اقترح كليفورد وكليفورد خوارزمية أخرى، يُزعم أنها أبسط . ^{[ 15 ]}

انظر أيضاً

مراجع

↑ كورتز، ستيفان؛ فيليبي، آدم؛ ديلشر، آرثر ل؛ سموت، مايكل؛ شومواي، مارتن؛ أنتونسكو، كورينا؛ سالزبيرغ، ستيفن ل (2004). "برنامج متعدد الاستخدامات ومفتوح المصدر لمقارنة الجينومات الكبيرة" . علم الأحياء الجينومي . 5 (2): R12. doi : 10.1186 / gb-2004-5-2-r12 . ISSN 1465-6906 . PMC 395750. PMID 14759262 .
↑ خان، ضياء؛ بلوم، جوشوا س.؛ كروغلياك، ليونيد؛ سينغ، منى (2009-07-01). "خوارزمية عملية لإيجاد أقصى تطابق تام في مجموعات بيانات تسلسلية كبيرة باستخدام مصفوفات اللواحق المتفرقة" . المعلوماتية الحيوية . 25 (13): 1609-1616 . doi : 10.1093/bioinformatics/btp275 . PMC 2732316. PMID 19389736 .
↑ كروشيمور، ماكسيم؛ بيرين، دومينيك (1 يوليو 1991). "مطابقة السلاسل ثنائية الاتجاه" ( ملف PDF) . مجلة ACM . 38 (3): 650-674 . doi : 10.1145/116825.116845 . S2CID 15055316. مؤرشف (ملف PDF) من الأصل في 24 نوفمبر 2021. تم الاطلاع عليه في 5 أبريل 2019 .
↑ نافارو، غونزالو؛ رافينو، ماثيو (1998). "نهج متوازي البتات لأتمتة اللواحق: مطابقة السلاسل الموسعة السريعة" (ملف PDF) . مطابقة الأنماط التوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 1448. سبرينغر برلين هايدلبرغ. الصفحات 14-33 . doi : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 2019-01-05 . تم الاطلاع عليه بتاريخ 2019-11-22 .
↑ فان، هـ.؛ ياو، ن.؛ ما، هـ. (ديسمبر 2009). "متغيرات سريعة لخوارزمية المسير العكسي للأوراكل" (ملف PDF) . المؤتمر الدولي الرابع للحوسبة عبر الإنترنت للعلوم والهندسة ، 2009. الصفحات 56-59 . doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9S2CID 6073627. مؤرشف من الأصل بتاريخ 10 مايو 2022. تم الاطلاع عليه بتاريخ 22 نوفمبر 2019 .
↑ "glibc/string/str-two-way.h" . مؤرشف من الأصل بتاريخ 2020-09-20 . تم الاطلاع عليه بتاريخ 2022-03-22 .
↑ "musl/src/string/memmem.c" . مؤرشف من الأصل في 1 أكتوبر 2020. تم الاطلاع عليه في 23 نوفمبر 2019 .
↑ هيوم؛ صنداي (1991). "البحث السريع عن السلاسل النصية". البرمجيات: الممارسة والخبرة . 21 (11): 1221-1248 . doi : 10.1002/spe.4380211105 . S2CID 5902579 .
↑ كومنتز-والتر، بيات (1979). خوارزمية مطابقة سلاسل نصية سريعة في المتوسط (ملف PDF) . الندوة الدولية حول الأوتوماتا واللغات والبرمجة . سلسلة محاضرات في علوم الحاسوب . المجلد 71. غراتس، النمسا: سبرينغر. الصفحات 118-132 . doi : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1تمت أرشفة النسخة الأصلية (PDF) بتاريخ 2017-10-10.
↑ ميليشار، بوريفوي، يان هولوب، وج. بولكار. خوارزميات البحث النصي. المجلد الأول: مطابقة السلاسل الأمامية. المجلد 1. مجلدان، 2005. http://stringology.org/athens/TextSearchingAlgorithms/ مؤرشف بتاريخ 4 مارس 2016 في أرشيف الإنترنت (Wayback Machine ).
↑ ليتوين، ويتولد؛ موكادم، رياض؛ ريغو، فيليب؛ شوارتز، توماس (2007)، بحث سريع عن السلاسل النصية باستخدام nGram في البيانات المشفرة باستخدام التوقيعات الجبرية (ملف PDF) ، المؤتمر الدولي لقواعد البيانات الضخمة جدًا
↑ غونزالو نافارو؛ ماثيو رافينو (2008)، سلاسل مطابقة الأنماط المرنة: خوارزميات بحث عملية عبر الإنترنت للنصوص والتسلسلات البيولوجية ، مطبعة جامعة كامبريدج، ISBN 978-0-521-03993-2
↑ جاليل، زفي (1981). "مطابقة السلاسل في الوقت الحقيقي". مجلة ACM . 28 (1): 134-149 . doi : 10.1145/322234.322244 .
↑ كول، ريتشارد؛ هاريهاران، راميش (2002). "التحقق من تطابقات المرشحين في المطابقة المتفرقة والمطابقة باستخدام الأحرف البديلة". وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 592-601 .
↑ كليفورد، بيتر؛ كليفورد، رافائيل (يناير 2007). "مطابقة الأحرف البديلة الحتمية البسيطة". رسائل معالجة المعلومات . 101 (2): 53-54 . doi : 10.1016/j.ipl.2006.08.002 .

للمزيد من القراءة

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

روابط خارجية

قائمة ضخمة من روابط مطابقة الأنماط. آخر تحديث: 27/12/2008 20:18:38
قائمة كبيرة (يتم تحديثها باستمرار) لخوارزميات مطابقة السلاسل النصية
قائمة خوارزميات مطابقة السلاسل النصية الصادرة عن المعهد الوطني للمعايير والتكنولوجيا (NIST).
StringSearch – خوارزميات مطابقة الأنماط عالية الأداء في جافا – تطبيقات للعديد من خوارزميات مطابقة السلاسل النصية في جافا (BNDM، Boyer-Moore-Horspool، Boyer-Moore-Horspool-Raita، Shift-Or)
StringsAndChars – تطبيقات للعديد من خوارزميات مطابقة السلاسل النصية (للأنماط المفردة والمتعددة) في لغة جافا
خوارزميات مطابقة السلاسل النصية الدقيقة - الرسوم المتحركة في جافا، وصف تفصيلي وتنفيذ بلغة C للعديد من الخوارزميات.
(ملف PDF) تحسين مطابقة السلاسل التقريبية المفردة والمتعددة، مؤرشف بتاريخ 11 مارس 2017 في أرشيف الإنترنت (Wayback Machine).
Kalign2: محاذاة متعددة عالية الأداء لتسلسلات البروتين والنيوكليوتيدات تسمح بالميزات الخارجية
نيوتينغو – خوارزمية مطابقة أنماط عالية الأداء بلغة سي – تطبيقات لخوارزميات مطابقة السلاسل المتجهة والعددية بلغة سي
Nathaniel K. Brown, et al.: "KeBaB: كسر قائم على k-mer لإيجاد MEMs طويلة"، arXiv:2502.20338v3 (09 يونيو 2025).

[1] كورتز، ستيفان؛ فيليبي، آدم؛ ديلشر، آرثر ل؛ سموت، مايكل؛ شومواي، مارتن؛ أنتونسكو، كورينا؛ سالزبيرغ، ستيفن ل (2004). "برنامج متعدد الاستخدامات ومفتوح المصدر لمقارنة الجينومات الكبيرة" . علم الأحياء الجينومي . 5 (2): R12. doi : 10.1186 / gb-2004-5-2-r12 . ISSN 1465-6906 . PMC 395750. PMID 14759262 .

[2] خان، ضياء؛ بلوم، جوشوا س.؛ كروغلياك، ليونيد؛ سينغ، منى (2009-07-01). "خوارزمية عملية لإيجاد أقصى تطابق تام في مجموعات بيانات تسلسلية كبيرة باستخدام مصفوفات اللواحق المتفرقة" . المعلوماتية الحيوية . 25 (13): 1609-1616 . doi : 10.1093/bioinformatics/btp275 . PMC 2732316. PMID 19389736 .

[3] كروشيمور، ماكسيم؛ بيرين، دومينيك (1 يوليو 1991). "مطابقة السلاسل ثنائية الاتجاه" ( ملف PDF) . مجلة ACM . 38 (3): 650-674 . doi : 10.1145/116825.116845 . S2CID 15055316. مؤرشف (ملف PDF) من الأصل في 24 نوفمبر 2021. تم الاطلاع عليه في 5 أبريل 2019 .

[4] نافارو، غونزالو؛ رافينو، ماثيو (1998). "نهج متوازي البتات لأتمتة اللواحق: مطابقة السلاسل الموسعة السريعة" (ملف PDF) . مطابقة الأنماط التوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 1448. سبرينغر برلين هايدلبرغ. الصفحات 14-33 . doi : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3تمت أرشفة الملف (PDF) من النسخة الأصلية بتاريخ 2019-01-05 . تم الاطلاع عليه بتاريخ 2019-11-22 .

[5] فان، هـ.؛ ياو، ن.؛ ما، هـ. (ديسمبر 2009). "متغيرات سريعة لخوارزمية المسير العكسي للأوراكل" (ملف PDF) . المؤتمر الدولي الرابع للحوسبة عبر الإنترنت للعلوم والهندسة ، 2009. الصفحات 56-59 . doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9S2CID 6073627. مؤرشف من الأصل بتاريخ 10 مايو 2022. تم الاطلاع عليه بتاريخ 22 نوفمبر 2019 .

[6] "glibc/string/str-two-way.h" . مؤرشف من الأصل بتاريخ 2020-09-20 . تم الاطلاع عليه بتاريخ 2022-03-22 .

[7] "musl/src/string/memmem.c" . مؤرشف من الأصل في 1 أكتوبر 2020. تم الاطلاع عليه في 23 نوفمبر 2019 .

[:0-8] هيوم؛ صنداي (1991). "البحث السريع عن السلاسل النصية". البرمجيات: الممارسة والخبرة . 21 (11): 1221-1248 . doi : 10.1002/spe.4380211105 . S2CID 5902579 .

[Commentz-Walter-9] كومنتز-والتر، بيات (1979). خوارزمية مطابقة سلاسل نصية سريعة في المتوسط (ملف PDF) . الندوة الدولية حول الأوتوماتا واللغات والبرمجة . سلسلة محاضرات في علوم الحاسوب . المجلد 71. غراتس، النمسا: سبرينغر. الصفحات 118-132 . doi : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1تمت أرشفة النسخة الأصلية (PDF) بتاريخ 2017-10-10.

[10] ميليشار، بوريفوي، يان هولوب، وج. بولكار. خوارزميات البحث النصي. المجلد الأول: مطابقة السلاسل الأمامية. المجلد 1. مجلدان، 2005. http://stringology.org/athens/TextSearchingAlgorithms/ مؤرشف بتاريخ 4 مارس 2016 في أرشيف الإنترنت (Wayback Machine ).

[11] ليتوين، ويتولد؛ موكادم، رياض؛ ريغو، فيليب؛ شوارتز، توماس (2007)، بحث سريع عن السلاسل النصية باستخدام nGram في البيانات المشفرة باستخدام التوقيعات الجبرية (ملف PDF) ، المؤتمر الدولي لقواعد البيانات الضخمة جدًا

[12] غونزالو نافارو؛ ماثيو رافينو (2008)، سلاسل مطابقة الأنماط المرنة: خوارزميات بحث عملية عبر الإنترنت للنصوص والتسلسلات البيولوجية ، مطبعة جامعة كامبريدج، ISBN 978-0-521-03993-2

[13] جاليل، زفي (1981). "مطابقة السلاسل في الوقت الحقيقي". مجلة ACM . 28 (1): 134-149 . doi : 10.1145/322234.322244 .

[14] كول، ريتشارد؛ هاريهاران، راميش (2002). "التحقق من تطابقات المرشحين في المطابقة المتفرقة والمطابقة باستخدام الأحرف البديلة". وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 592-601 .

[15] كليفورد، بيتر؛ كليفورد، رافائيل (يناير 2007). "مطابقة الأحرف البديلة الحتمية البسيطة". رسائل معالجة المعلومات . 101 (2): 53-54 . doi : 10.1016/j.ipl.2006.08.002 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]