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

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

تبحث خوارزمية البحث البسيط Naive Pattern Searching عن نمط معين (نفترض أنّه pat[0..m-1]‎) في سلسلة نصية معينة (نفترض أنها tex[0..n-1]‎).

خطوات الخوارزمية

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

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية البحث البسيط في عدد من لغات البرمجة:

C++‎:

#include<bits/stdc++.h> 
using namespace std; 

void search(char* pat, char* txt) 
{ 
	int M = strlen(pat); 
	int N = strlen(txt); 

	/* تمرّر هذه الحلقة النمط المعطى حرفًا تلو الآخر */
	for (int i = 0; i <= N - M; i++) { 
		int j; 

		/* نتحقق من تطابق النمط المعطى في الموقع الحالي */
		for (j = 0; j < M; j++) 
			if (txt[i + j] != pat[j]) 
				break; 

		if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
			cout << "Pattern found at index "
				<< i << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	char txt[] = "AABAACAADAABAAABAA"; 
	char pat[] = "AABA"; 
	search(pat, txt); 
	return 0; 
}

بايثون:

def search(pat, txt): 
	M = len(pat) 
	N = len(txt) 

	# تمرّر هذه الحلقة النمط المعطى حرفًا تلو الآخر 
	for i in range(N - M + 1): 
		j = 0
		
		# نتحقق من تطابق النمط المعطى في الموقع الحالي
		for j in range(0, M): 
			if (txt[i + j] != pat[j]): 
				break

		if (j == M - 1): 
			print("Pattern found at index ", i) 

# اختبار الدالة السابقة
if __name__ == '__main__': 
	txt = "AABAACAADAABAAABAA"
	pat = "AABA"
	search(pat, txt)

جافا:

public class NaiveSearch { 

	public static void search(String txt, String pat) 
	{ 
		int M = pat.length(); 
		int N = txt.length(); 

		/* تمرّر هذه الحلقة النمط المعطى حرفًا تلو الآخر */
		for (int i = 0; i <= N - M; i++) { 

			int j; 

			/* نتحقق من تطابق النمط المعطى في الموقع الحالي */
			for (j = 0; j < M; j++) 
				if (txt.charAt(i + j) != pat.charAt(j)) 
					break; 

			if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
				System.out.println("Pattern found at index " + i); 
		} 
	} 

	public static void main(String[] args) 
	{ 
		String txt = "AABAACAADAABAAABAA"; 
		String pat = "AABA"; 
		search(txt, pat); 
	} 
}

التعقيد الزمني

يعتمد التعقيد الزمني لهذه الخوارزمية على طبيعة الحالة:

الحالة المثلى: تحدث الحالة المثلى عندما يكون الحرف الأول في النمط المعطى غير موجود في النص بأكمله، وفي مثل هذه الحالة يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n)‎.

txt[] = "AABCCAADDEE"; 
pat[] = "FAA";

الحالة الأسوأ: تحدث الحالة الأسوأ في خوارزمية البحث البسيط في حالتين:

1- تكون جميع الحروف في النص وفي النمط متطابقة.

txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

2- عندما تكون الحروف كلها متطابقة عدا الحرف الأخير.

txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

في مثل هذه الحالة يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(m*(n-m+1))‎. صحيح أنّ تكرار الحروف بهذه الطريقة أمر غير وارد في النصوص المكتوبة، ولكنّه أمر شائع في تطبيقات أخرى مثل النصوص المكتوبة بالنظام الثنائي Binary Texts.

مصادر

صفحة Naive algorithm for Pattern Searching في توثيق الخوارزميات في موقع GeeksforGeeks.