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

هذه المقالة تتمة للمقالة السابقة خوارزميات البحث وآلية عملها، إذ نستعرض فيها بعض خوارزميات البحث، لكننا سنركز هذه المرة على البحث داخل النصوص، وسنستعرض اثنتين من أشهر خوارزميات البحث في النصوص، وهما خوارزمية رابين-كارب وخوارزمية KMP.

خوارزمية KMP

لنفترض أن لدينا نصًّا ونمطًا (سلسلة نصية)، ونريد أن نعرف ما إذا كان النمط موجودًا في النص أم لا. انظر المثال التالي:

+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  b  |  c  |  g  |  l    |  x  |
+-------+----+----+----+----+----+----+----+----+

+----------+----+----+----+----+
| Index    | 0   |  1  |  2  |  3  | 
+----------+----+----+----+----+
| Pattern | b   | c   | g   |  l   |
+----------+----+----+----+----+

هذا النمط Pattern موجود فعلًا في النص Text، لذا يجب أن تعيد خوارزمية البحث العدد 3، وهو فهرس الموضع الذي يبدأ منه هذا النمط داخل النص.

الطريقة البدهية هي أن نبدأ من الفهرس 0 في النص والفهرس 0 في النمط، ونوازن Text[0]‎‎ وPattern[0]‎‎. وبما أنهما غير متساويين، سننتقل إلى الفهرس التالي في النص، ونوازن Text[1]‎‎ وPattern[0]‎‎. وبما أنهما متطابقين، فإنّنا نزيد قيمة الفهرس في النمط والنص معًا.

بعد ذلك نوازن Text[2]‎‎ وPattern[1]‎‎ فنجد أنّهما متطابقين، ثم نتابع ونوازن الآن Text[3]‎‎ وPattern[2]‎‎، واللذين نجد أنّهما غير متطابقين، فنبدأ الآن من الموضع حيث بدأ التطابق بين النص والنمط، أي الفهرس 2 في النص، ونوازن بين كل من Text[2]‎‎ وPattern[0]‎‎، وبما أنهما لا يتطابقان، فسنزيد الفهرس النصي، ونوازن بين كل من Text[3]‎‎ وPattern[0]‎‎. واللذان نجد أنهما متطابقان، كما يتطابق كل من:

• Text[4]‎‎.
• Pattern[1]‎‎.
• Text[5]‎‎.
• Pattern[2].
• Text[6]‎‎.
• Pattern[3]‎‎.

لقد استنفدنا حروف النمط، وهذا يعني أنه موجود في النص. نعيد الآن الفهرس الذي بدأ التطابق عنده، وهو 3.

إن لم يكن النمط موجودًا في النص (مثلا إن كان يساوي ‎bcgll‎)، فنتوقّع أن يُرفع اعتراض exception أو يُعاد -1 أو أيّ قيمة أخرى محدّدة مسبقًا.

تستغرق الخوارزمية في أسوأ الحالات ‎O(mn)‎، حيث يمثّل m طول النص، و n طول النمط. السؤال الآن هو: هل هناك خوارزمية أسرع؟ نعم، وهي خوارزمية KMP.

تبحث خوارزمية نوث-موريس-برات Knuth-Morris-Pratt أو KMP اختصارًا، عن ظهور نمط معيّن داخل سلسلة نصّية، وتستغل هذه الخوارزمية حقيقة أنّه عند حدوث عدم التطابق فإنّ الكلمة نفسها تقدّم معلومات كافية لتقدير المكان التالي الذي يمكن أن يبدأ التطابق عنده، وبالتالي تجاوز بعض الحروف التي تحقّقنا منها سابقًا.

صُمِّمت هذه الخوارزمية سنة 1970 على يد دونالد نوث Donuld Knuth وفوهان برات Vaughan Pratt، وبشكل مستقل على يد جيمس مورِس James H. Morris، وقد نَشر هذا الثلاثي بحثًا مشتركًا عنها سنة 1977.

لنوسّع مثالنا السابق كي نفهمه أكثر:

+-------+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0  |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+--------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  Text  |a  |b |c |x |a |b |c |d  |a |b | x | a | b | c |d  | a | b | c | d | a | b | c | y |
+--------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

+----------+---+---+---+---+---+---+---+---+
|  Index   | 0  | 1 | 2  | 3  | 4  | 5 | 6 | 7  |
+----------+---+---+---+---+---+---+---+---+
| Pattern | a  | b | c  | d  | a  | b  | c | y  |
+---------+---+---+---+---+---+---+---+---+

في البداية، يتطابق النص والنمط حتى الفهرسَ 2، ثمّ ينهار التطابق عند الفهرس 3، إذ لا تتطابق Text[3]‎‎ وPattern[3]‎‎. ونحن نهدف إلى عدم الرجوع للخلف في النص، إذ لا نريد أن نبدأ المطابقة مرةً أخرى من الموضع الذي بدأنا المطابقة عنده سابقًا في حالة عدم التطابق. ولتحقيق ذلك، نبحث عن لاحقةٍ suffix في الجزء الحالي من النمط قبل انهيار التطابق والتي تكون أيضًا سابقةً في النمط (السلسلة النصية الجزئية abc). على سبيل المثال، بما أنّ جميع الحروف فريدة غير مكرّرة، فلن يكون هناك أيّ سلسلة نصية تكون لاحقة وسابقة في الوقت نفسه في السلسلة النصية الجزئية التي طَابقناها للتو، هذا يعني أنّ الموازنة التالية ستبدأ من الفهرس 0.

سنوازن الآن بين كل من Text[3]‎‎ وPattern[0]‎‎، إلا أنّهما لا يتطابقان. بعد ذلك نجد تطابقًا ابتداءً من الفهرس 4 وحتى الفهرس 9 في النص، ومن الفهرس 0 إلى 5 في النمط. غير أنّ التطابق ينهار بعد ذلك في Text[10]‎‎ وPattern[6]‎‎. نأخذ الآن السلسلة النصية الجزئية المُطابِقة من النمط قبل نقطة الانهيار (أي abcdabc)، ونبحث عن لاحقة فيها تكون أيضًا سابقة للنمط. تستطيع ملاحظة أنّ ab هي لاحقة لهذه السلسلة النصية الجزئية وسابقة لها في الوقت نفسه. وبما أنّ المطابقة السابقة استمرت حتى Text[10]‎‎، فإنّ الحرفين اللذين يسبقان موضع عدم التطابق هما ab.

هنا نستنتج أنّه لما كانت ab أيضًا سابقة للسلسلة النصية الجزئية التي أخذناها، فلن يكون علينا التحقق من ab مرة أخرى، ويمكن أن يبدأ الفحص التالي من Text[10]‎‎ وPattern[2]‎‎، كذلك ليس علينا أن نعود حيث كنا إذ يمكننا أن نبدأ مباشرة من موضع انهيار التطابق.

علينا الآن التحقق من Text[10]‎‎ وPattern[2]‎‎، بما أنّهما غير متطابقتين وليس للجزء المطابَق من النمط أي لاحقة هي نفسها سابقة للنمط، فسيكون علينا أن نتحقق من Text[10]‎‎ وPattern[0]‎‎، ولكنّها لا يتطابقان أيضًا. بعد ذلك نجد تطابقًا ابتداءً من الفهرس 11 وحتى الفهرس 17 في النص، ومن الفهرس 0 إلى 6. لكن ينهار التطابق مجددًا في Text[18]‎‎ وPattern[7]‎‎.

مرّة أخرى علينا التحقق من السلسلة النصية الجزئية قبل انهيار التطابق (أي abcdabc) لنجد أنّ abc هي لاحقة وسابقة في الوقت نفسه، لذا ينبغي أن تكون abc قبل Text[18]‎‎ بما أنّ التطابق السابق استمر حتى الموضع Pattern[7]‎‎، وهذا يعني أننا لسنا بحاجة إلى الموازنة حتى الموضع Text[18]‎‎، إذ ستبدأ الموازنة من Text[18]‎‎ وPattern[3]‎‎. سنجد الآن تطابقًا، ونعيد 15، وهو الفهرس الذي يبدأ عنده التطابق. هذه هي طريقة عمل خوارزمية KMP.

والآن، كيف نتحقّق مما إذا كانت اللاحقة تساوي السابقة، وعند أي نقطة نبدأ التحقق مما إذا كان هناك عدم تطابق للحروف بين النص والنمط؟

لنلق نظرة على المثال التالي:

+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+

سننشئ مصفوفةً تحتوي المعلومات الضرورية وسنسميها المصفوفة S، حجم هذه المصفوفة يساوي طول النمط، ولا يمكن أن يكون الحرف الأول من النمط لاحقة لأيّ سابقة، لذا نضع S[0] = 0.

نأخذ i = 1 و j = 0 في البداية، نوازن في كل خطوة بين ‎Pattern[i‎]‎‎‎ وPattern[j]‎‎ ونزيد قيمة i بواحد، فإذا كان هناك تطابق نضع S[i‎] = j + 1 ونزيد قيمة j، وإن لم يكن فنتحقق من قيمة الموضع السابق لـ j -إن وُجد- ونضع j = S [j-1]‎‎ -إذا كانت j تخالف 0-، ونستمر في هذا إلى أن يحدث عدم تطابق بين S[i‎] [j]‎‎ و S ‎‎، أو تخالف j القيمة 0. في الحالة الأخيرة نضع S[i‎] = 0.

نعود إلى المثال السابق:

              j      i
+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+

لا يتطابق ‎Pattern[i‎]‎ وPattern[j]‎‎، لذا نزيد قيمة i بواحد، وبما أنّ j تساوي 0، فلن نتحقق من القيمة السابقة، وسنضع ‎Pattern[i‎] = 0‎. سنحصل على تطابق عند الموضع i = 4 إذا واصلنا زيادة i، لذلك نضع [i‎] = S[4] = j + 1 = 0 + 1 = 1 ثمّ نزيد قيمتي j و i. ستبدو المصفوفة هكذا:

                     j                           i
+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+
|    S    |  0 |  0   |  0  |  0 |  1  |      |       |      |
+-------+----+----+----+----+----+----+----+----+

بما أن ‎Pattern[5]‎ وPattern[1]‎‎ متطابقتين، فإننا نضع S[i‎] = S [5] = j + 1 = 1 + 1 = 2. إذا تابعنا سنجد عدم تطابق في الموضعين j = 3 و i = 7. وبما أنّ j لا تساوي 0، فإننا نضع j = S [j-1]‎‎ ونوازن الحرفين الموجودين عند الموضعين i و j، ولأنها متماثلان فإننا نضع S[i‎] = j + 1. ستبدو المصفوفة النهائية كما يلي:

+---------+---+---+---+---+---+---+---+---+
|    S      |  0 |  0 |  0 |  0 |  1 |  2 |  3 | 1 |
+---------+---+---+---+---+---+---+---+---+

هذه هي المصفوفة المطلوبة. إن كانت S[i‎]‎‎ تخالف الصفر فذلك يعني أنّ هناك سلسلة نصية طولها S[i‎]‎‎ هي لاحقة وسابقة في الوقت نفسه للسلسلة النصية الجزئية من النمط التي تبدأ من 0 وتنتهي عند i. نبدأ الموازنة التالية من الموضع S[i‎] + 1 في النمط.

هذه شيفرة عامة لخوارزمية توليد المصفوفة:

Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
   if Pattern[i] is equal to Pattern[j]
       S[i] := j + 1
       j := j + 1
       i := i + 1
   else
       if j is not equal to 0
           j := S[j-1]
       else
           S[i] := 0
           i := i + 1
       end if
   end if
end while

التعقيد الزمني لعملية بناء المصفوفة هو ‎O(n)‎، والتعقيد المساحي يساوي أيضًا ‎O(n)‎. للتأكد من أنك قد فهمت الخوارزمية، حاول إنشاء مصفوفة للنمط ‎aabaabaa‎، وتحقق مما إذا كانت النتيجة التي حصلت عليها تتطابق مع هذه النتيجة:

+---------+---+---+---+---+---+---+---+---+---+
|    S      |  0 |  1 |  0 |  1 |  2 | 3 | 4 | 5 | 2 |
+---------+---+---+---+---+---+---+---+---+---+

انظر إلى المثال التالي:

+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|  Index  |  0 |  1 |  2 |  3 | 4 | 5 |  6 |  7 | 8 |  9 |10 |11 | 
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|   Text  |  a |  b |  x |  a |  b |  c |  a |  b |  c |  a |  b |  y | 
+---------+---+---+---+---+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+---+----+
|  Index  |  0 |  1 |  2 |  3 |  4 |  5 | 
+---------+---+---+---+---+---+----+
| Pattern |  a |  b |  c |  a |  b |  y | 
+---------+---+---+---+---+---+----+
|    S      |  0 |  0 |  0 |  1 |  2 |  0 | 
+---------+---+---+---+---+---+----+

لدينا سلسلة نصية ونمط ومصفوفة S محسوبة قبليًا باستخدام الطريقة التي شرحناها سابقًا. سوف نوازن ‎Text[0]‎ وPattern[0]‎‎ وهما متطابقان، كما أنّ ‎Text[1]‎ وPattern[1]‎‎ متطابقان كذلك؛ أمّا ‎Text[2]‎ وPattern[2]‎‎، فهما غير متطابقين.

نتحقق من القيمة الموجودة عند الموضع الذي يسبق موضع عدم التطابق. ولمّا كانت ‎‎S [1] ‎‎ تساوي 0، فذلك يعني أنّه لا توجد لاحقة تطابق سابقة في السلسلة النصية الجزئية الحالية، لذا تبدأ الموازنة عند الموضع S [1]‎‎، وهو 0. وهكذا نجد أنّ ‎Text[2]‎ وPattern[0]‎‎ غير متطابقتين، لذا نستمر لنجد أنّ ‎Text[3]‎ وPattern[0]‎‎ متطابقتان، ويستمر التطابق حتى ‎Text[8]‎ وPattern[5]‎‎.

نعود الآن خطوةً واحدةً إلى الوراء في المصفوفة S لنجد القيمة 2، هذا يعني أنّ هناك سابقة طولها 2 وهي أيضًا لاحقة في السلسلة النصية الجزئية الحالية abcab، وهي ab. هذا يعني أنّ السلسلة النصية ab موجودة قبل ‎Text[8]‎.
وعلى ذلك نستطيع تجاهلPattern[1]‎‎ وPattern[0]‎‎ وبدء الموازنة التالية من الموضعين ‎Text[8]‎ وPattern[2]‎‎.

إذا تابعنا بذلك النسق فسنجد النمط داخل النص، وستبدو الشيفرة لتلك الإجراءات كما يلي:

Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
   if Pattern[j] is equal to Text[i]
       j := j + 1
       i := i + 1
   if j is equal to n
       Return (j-i)
   else if i < m and Pattern[j] is not equal t Text[i]
       if j is not equal to 0
           j = S[j-1]
       else
           i := i + 1
       end if
   end if
end while
Return -1

التعقيد الزمني لهذه الخوارزمية -بصرف النظر عن العمليات الحسابية المتعلقة بحساب مصفوفة اللاحقات- هو ‎O(m)‎، وبما أنّ دالة GenerateSuffixArray تستغرق وقتًا قدره O ‎(n)‎، فإن التعقيد الزمني الإجمالي لخوارزمية KMP هو: O ‎(m+n)‎.

اقتباس

ملاحظة: إذا أردت العثور على كل مواضع ظهور نمط معيّن في النص، يمكنك أن تطبعها أو تحفظها وتعيّن ‎j := S[j-1]‎، وذلك بدلًا من أن إعادة القيمة. كذللك يجب أن تحفظ رايةً ‎flag‎ لتعرف ما إذا كنت قد وجدت أيّ ظهور سابق للنمط أم لا.

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

خوارزمية رابين-كارب‏ Rabin-Karp هي خوارزمية بحث في السلاسل النصية أُنشِئت على يد ريتشارد كارب Richard M. Karp ومايكل رابِن Michael Rabin، وتستخدم هذه الخوارزمية دالة التعمية hashing للتحقق من وجود مجموعة من الأنماط في نص ما.

ونقول أنّ s سلسلة نصية جزئية من S إذا كانت s مُتضمّنة في S. على سبيل المثال، ver هي سلسلة نصية جزئية من stackoverflow. لكن لا ينبغي الخلط بين هذا المفهوم، وبين مفهوم التتابع الجزئئ subsequence الذي لا يشترط أن تكون حروفه متلاصقةً في النص، فمثلًا، تُعَد cover تتابعًا جزئيًا في stackoverflow، لكنها ليست سلسلةً نصيةً جزئيةً منها.

في خوارزمية Rabin-Karp، سنحسب تجزئة النمط الذي نبحث عنه، ثمّ نتحقق مما إذا كانت هناك تعمية تداولية rolling hash في النص تتوافق مع النمط أم لا، وإذا لم تتطابق فذلك يضمن لنا أنّ النمط غير موجود في النص، أما في حال كان هناك تطابق فربّما يكون النمط موجودًا في النص. دعنا نلقي نظرةً على المثال التالي:

لنفترض أنّ النص يساوي yeminsajid، وأننا نريد أن نعرف إن كان هذا النص يحتوي النمط nsa. لكي نحسب التجزئة والتجزئة التداولية سنحتاج إلى استخدام عدد أولي، ويمكنك هنا اختيار أيّ عدد أولي وليكن العدد Prime = 11.

نحسب قيمة التجزئة باستخدام هذه الصيغة:

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......

لكل حرف رقم يميزه في قائمة الحروف الهجائية:

a -> 1    g -> 7    m -> 13  s -> 19  y -> 25
b -> 2    h -> 8    n -> 14   t -> 20   z -> 26
c -> 3    i -> 9     o -> 15   u -> 21
d -> 4    j -> 10   p -> 16   v -> 22
e -> 5    k -> 11  q -> 17   w -> 23
f -> 6     l -> 12    r -> 18   x -> 24

قيمة تجزئة nsa هي:

 14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344

الآن نحسب التجزئة التداولية للنص، أي نحسب تجزئة كل سلسلة نصية جزئية مؤلفة من 3 حروف في النص، فإذا تطابقت التجزئة التداولية مع قيمة تجزئة النمط، نتحقق مما إذا كانت السلسلتان النصيّتان متطابقتان أم لا، وبما أنّ النمط يحتوي على 3 أحرف، فإننا نأخذ أوّل ثلاثة أحرف من النص yem ونحسب قيمة تجزئتها، فنحصل على:

25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653

لا تتطابق هذه القيمة مع قيمة تجزئة النمط، لذا فإنّ السلسلة النصية غير موجودة هنا، وسننتقل الآن إلى الخطوة التالية ونحسب قيمة التجزئة الخاصة بالسلسلة النصية emi التالية باستخدام الصيغة أعلاه.

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

1. نطرح قيمة الحرف الأول من السلسلة النصية السابقة (التي حسبنا تجزئتها قبيل قليل) من قيمة التجزئة الحالية، والتي هي فـي هـذه الحالـة y. وسنحصل على ‎1653 - 25 = 1628‎.
2. نقسّم الناتج على العدد الأولي 11 الذي اخترناه سابقًا، وسنحصل على ‎1628 / 11 = 148‎.
3. نضيف ناتج العملية (ترتيب الحرف الجديد) X‏ 11^m-y، حيث يمثّل m طول النمط، أما ترتيب الحرف الجديد فيساوي ترتيب i، وهو 9. نحصل على 112 = 1237‎

قيمة التجزئة الجديدة لا تساوي قيمة التجزئة الخاصة بالنمط، لذا نستمر بالبحث على المنوال نفسه، وبالنسبة للحرف n نحصل على:

Previous String: emi // السلسلة النصية السابقة
First Letter of Previous String: e(5)  // الحرف الأول من السلسلة النصية السابقة
New Letter: n(14)     // الحرف الجديد 
New String: "min"     // السلسلة النصية الجديدة
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806

ليس هناك تطابق أيضًا، لذا سنأخذ الآن الحرف s:

Previous String: min  // السلسلة النصية السابقة
First Letter of Previous String: m(13)  // الحرف الأول من السلسلة النصية السابقة
New Letter: s(19)   // الحرف الجديد 
New String: "ins"    // السلسلة النصية الجديدة
1806 - 13 = 1793  
1793 / 11 = 163
163 + 19 X 11² = 2462

ليس هناك تطابق أيضًا. بعد ذلك، نأخذ a فنحصل على:

Previous String: ins   // السلسلة النصية السابقة
First Letter of Previous String: i(9)  // الحرف الأول من السلسلة النصية السابقة
New Letter: a(1)  // الحرف الجديد
New String: "nsa"  // السلسلة النصية الجديدة
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344

هنا حصل تطابق، لذا سنوازن الآن النمط بالسلسلة النصية الحالية، وبما أنّ كلا السلسلتين متطابقتين نستنج أنّ السلسلة النصية الجزئية موجودة في النص، ونعيد موضع بداية السلسلة النصية الجزئية. انظر المثال التوضيحي التالي:

• حساب التجزئة:

Procedure Calculate-Hash(String, Prime, x):
hash := 0               // ‫هنا، تمثل x الطول
for m from 1 to x                      // البحث عن قيمة التجزئة
   hash := hash + (Value of String[m])⁻¹
end for
Return hash

• إعادة حساب التجزئة، ستمثل Curr هنا الحرف الأول من السلسلة النصية السابقة:

Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] 
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])⁻¹
Return Hash

• مطابقة السلسلة النصية:

Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
    if Text[i] is not equal to Pattern[i]
        Return false
    end if
end for
Return true

• منظور رابين كارب:

Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
   if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
       Return i
   end if
   CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1

ستعيد الخوارزمية -1 إذا لم تعثر على أي تطابق.

تُستخدم هذه الخوارزمية للكشف عن الانتحال، إذ نعطيها مادةً نصيةً مصدريةً، فتبحث بسرعة في مقالة عما إذا كانت المقالة تحتوي جملًا أو عبارات من المادة المصدرية متجاهلةً تفاصيلًا معينةً من قبيل علامات الترقيم وحالة الحروف (أو تشكيلها). عادةً ما تكون هناك الكثير من السلاسل النصية (الجمل) التي ينبغي أن نبحث عنها، لذا فإنّ خوارزميات البحث التقليدية التي تبحث عن سلسلة نصية واحدة مثل خوارزمية Knuth- Morris-Pratt أو خوارزمية Boyer-Moore String، لن تكون عمليّةً هنا، لهذا يُفضّل استخدام خوارزمية Rabin-Karp. لكن من المهم أن تنتبه إلى أنّ خوارزمية Knuth- Morris-Pratt وخوارزمية Boyer-Moore String أسرع من خوارزمية Rabin-Karp.

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

بالنسبة لنص طوله n، و p نمط مجموع أطوالها يساوي m، فإنّ حالتي التعقيد المتوسطة والفضلى تساويانO (n + m) ‎‎، كما تحتاج الخوازمية إلى مساحة O (p)‎‎؛ أما حالة التعقيد الأسوأ فتُساوي O (nm)‎‎.

هذا تطبيق بلغة بايثون على خوارزمية KMP:

• Haystack: السلسلة النصية التي سنبحث فيها.
• Needle: النمط المراد البحث عنه.
• التعقيد الزمني: التعقيد الزمني للجزء الذي يُجري عمليات البحث (التابع strstr) هو O (n)‎‎، حيث يمثّل ‎n‎ طول الوسيط haystack، ولكن لمّا كان الوسيط needle يُحلَّل قبليا لأجل بناء جدول السوابق prefix table، فسنحتاج مدة O (m)‎‎، وهي المدة المطلوب لبناء الجدول، حيث يمثل ‎m‎ طول needle، وهكذا فإنّ التعقيد الزمني الكلي لخوارزمية KMP يساوي O (n + m)‎‎.
• تعقيد المساحة: تحتاج الخوارزمية إلى مساحة بحجم O (m)‎‎ لأجل بناء جدول السوابق.

اقتباس

ملاحظة: يعيد التقديم التالي موضع بدء التطابق في النص haystack (إذا كان هناك تطابق أصلًا)، أو يعيد العدد -1 في حالة لم يكن needle موجودًا في النص haystack، أو كان أحدهُما فارغًا.

def get_prefix_table(needle):
   prefix_set = set()
   n = len(needle)
   prefix_table = [0]*n
   delimeter = 1
   while(delimeter<n):
       prefix_set.add(needle[:delimeter])
       j = 1
       while(j<delimeter+1):
           if needle[j:delimeter+1] in prefix_set:
               prefix_table[delimeter] = delimeter - j + 1
               break
           j += 1
       delimeter += 1
   return prefix_table
def strstr(haystack, needle):
   # ‫يمثل ‫m الموضع في S حيث يبدأ التطابق القادم لـ W
   # ‫يمثل i فهرس المحرف الحالي W
   haystack_len = len(haystack)
   needle_len = len(needle)
   if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
       return -1
   prefix_table = get_prefix_table(needle)
   m = i = 0
   while((i<needle_len) and (m<haystack_len)):
       if haystack[m] == needle[i]:
           i += 1
           m += 1
       else:
           if i != 0:
               i = prefix_table[i-1]
           else:
               m += 1
   if i==needle_len and haystack[m-1] == needle[i-1]:
       return m - needle_len
   else:
       return -1
if __name__ == '__main__':
   needle = 'abcaby'
   haystack = 'abxabcabcaby'
   print strstr(haystack, needle)

هذا تطبيق على خوارزمية KMP في لغة C، الوسيط txt يمثل النص، فيما يمثل الوسيط pat النمط، يطبع هذا البرنامج كل ظهور للنمط pat في النص txt. مثلا، إن كان الدخل يساوي:

  txt[] = "THIS IS A TEST TEXT"
  pat[] = "TEST"

فسيطبع البرنامج الخرج التالي:

Pattern found at index 10

بالنسبة للدخل:

  txt[] = "AABAACAADAABAAABAA"
  pat[] = "AABA"

يطبع البرنامج الخرج التالي:

   Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 13

هذا هو المثال التطبيقي على استخدام خورازمية KMP في لغة C:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
   int M = strlen(pat);
   int N = strlen(txt);

هنا ستنشئ []lps لتخزين أطول قيم سابقة لاحقة للنمط، نتابع …

   int *lps = (int *)malloc(sizeof(int)*M);
   int j  = 0;  // pat[] فهرس لـ

الحساب القبلي للنمط، أي حساب مصفوفة []lps، نتابع …

   computeLPSArray(pat, M, lps);
   int i = 0;  // txt[] فهرس
   while (i < N)
   {
     if (pat[j] == txt[i])
     {
       j++;
       i++;
     }
     if (j == M)
     {
       printf("Found pattern at index %d \n", i-j);
       j = lps[j-1];
     }
     // تطابق j العثور على عدم تطابق بعد
     else if (i < N && pat[j] != txt[i])
     {
       // lps[0..lps[j-1]] لا تحاول التحقق من مطابقة الحروف
       // لأننا نعلم أنها مطابقة
       if (j != 0)
        j = lps[j-1];
       else
        i = i+1;
     }
   }
   free(lps); // لتجنب تسرب الذاكرة
}
void computeLPSArray(char *pat, int M, int *lps)
{
   int len = 0;  //  حجم أطول سابقة-لاحقة حالية
   int i;
   lps[0] = 0; // يساوي 0 دائما lps[0]
   i = 1;
   while (i < M)
   {
      if (pat[i] == pat[len])
      {
        len++;
        lps[i] = len;
        i++;
      }
      else // (pat[i] != pat[len])
      {
        if (len != 0)
        {
          // هنا فخ، انظر المثال التالي
          // AAACAAAA و i = 7.
          len = lps[len-1];
          // هنا i لاحظ أيضا أننا لم نزد قيمة
        }
        else // if (len == 0)
        {
          lps[i] = 0;
          i++;
        }
      }
   }
}

الخرج الناتج هو الآتي:

Found pattern at index 10

ترجمة -بتصرّف- للفصل 40 من الكتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• خوارزميات الترتيب وأشهرها
• أمثلة عن أنواع الخوارزميات
• خوارزميات تحليل المسارات في الأشجار
• خوارزمية ديكسترا Dijkstra’s Algorithm