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

من موسوعة حسوب
اذهب إلى: تصفح، ابحث

تعدّ خوارزميات البحث عن النصوص (وتسمّى كذلك بخوارزميات البحث عن الأنماط Pattern Searching) جزءًا من خوارزميات النصوص String Algorithms، وتساعد هذه الخوارزميات في البحث عن سلسلة نصية معيّنة في سلسلة نصية أخرى.

الخوارزمية البسيطة

تنتقل الخوارزمية عبر جميع الحروف في السلسلة النصية واحدًا تلو الآخر بحثًا عن التسلسل الذي يطابق النمط المعطى.

خوارزمية KMP

تعالج الخوارزمية النمط المراد البحث عنه لتجنّب تكرار البحث عن أنماط جرى البحث عنها في الخطوات السابقة.

خوارزمية رابين-كارب

تحرّك خوارزمية رابين-كارب Rabin-Karp النمط الذي تبحث عنه عبر السلسلة النصية موقعًا تلو الآخر وتطابق قيمة التقطيع Hash value للنمط المعطى مع قيمة التقطيع لجزء السلسلة الذي تجري معه المقارنة

خوارزمية بوير-مور

تعتمد خوارزمية بوير-مور Boyer-Moore على الأسلوبين: استكشاف الحروف السيئة، واستكشاف اللاحقة الجيدة.

خوارزمية Z

تستعين الخوارزمية بمصفوفة Z في البحث عن النمط المعطى، ويخزّن العنصر Z[i]‎ طول أطول سلسلة نصية فرعية تبدأ من الموقع str[i]‎ والتي تكون في الوقت نفسه سابقة للسلسة النصية str[0..n-1]‎.