قهر البحث عن سلسلة باستخدام خوارزمية Aho-Corasick

يعد التعامل مع السلاسل والبحث عن الأنماط فيها من المهام الأساسية في علم البيانات ، ومهمة نموذجية لأي مبرمج.

تلعب خوارزميات السلسلة الفعالة دورًا مهمًا في العديد من عمليات علم البيانات. غالبًا ما تجعل هذه العمليات مجدية بدرجة كافية للاستخدام العملي.

في هذه المقالة ، ستتعرف على واحدة من أقوى الخوارزميات للبحث عن الأنماط في كمية كبيرة من النص: خوارزمية Aho-Corasick. تستخدم هذه الخوارزمية بنية بيانات ثلاثية (تُنطق "try") لتتبع أنماط البحث وتستخدم طريقة بسيطة للعثور بكفاءة على جميع تكرارات مجموعة معينة من الأنماط في أي فقاعة نصية.

أظهرت مقالة سابقة على مدونة Toptal Engineering Blog خوارزمية بحث سلسلة لنفس المشكلة. يوفر النهج المتبع في هذه المقالة تعقيدًا حسابيًا محسنًا.

خوارزمية كنوث موريس برات (KMP)

لفهم كيف يمكننا البحث عن أنماط متعددة في النص بكفاءة ، نحتاج أولاً إلى معالجة مشكلة أسهل: البحث عن نمط واحد في نص معين.

لنفترض أن لدينا كتلة كبيرة من النص بطول N ونمط (نريد البحث عنه في النص) بطول M. سواء كنا نريد البحث عن تكرار واحد لهذا النمط ، أو كل التكرارات ، يمكننا تحقيق التعقيد الحسابي لـ O (N + M) باستخدام خوارزمية KMP.

وظيفة البادئة

تعمل خوارزمية KMP عن طريق حساب دالة البادئة للنمط الذي نبحث عنه. تقوم وظيفة البادئة بحساب موضع احتياطي مسبقًا لكل بادئة من النموذج.

دعنا نحدد نمط البحث الخاص بنا كسلسلة ، تسمى S لكل سلسلة فرعية S[0..i] ، حيث i >= 1 ، سنجد البادئة القصوى لهذه السلسلة التي تصادف أيضًا أن تكون لاحقة هذه السلسلة. سنقوم بتسمية طول هذه البادئة P[i] .

بالنسبة للنمط "abracadabra" ، ستنتج وظيفة البادئة المواضع الاحتياطية التالية:

تحدد وظيفة البادئة خاصية مثيرة للاهتمام للنمط.

لنأخذ بادئة معينة للنمط كمثال: "abracadab". قيمة وظيفة البادئة لهذه البادئة هي اثنان. يشير هذا إلى أنه بالنسبة إلى هذه البادئة "abracadab" ، توجد لاحقة بطول اثنين تتطابق تمامًا مع بادئة الطول اثنين (على سبيل المثال ، يبدأ النمط بـ "ab" وتنتهي البادئة بـ "ab.") علاوة على ذلك ، هذا هو الأطول تطابقًا لهذه البادئة.

تطبيق

فيما يلي وظيفة C # التي يمكن استخدامها لحساب وظيفة البادئة لأي سلسلة:

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

ينتج عن تشغيل هذه الوظيفة على نمط أطول قليلاً "abcdabcabcdabcdab" ما يلي:

التعقيد الحسابي

على الرغم من وجود حلقتين متداخلتين ، فإن تعقيد وظيفة البادئة هو فقط O (M) ، حيث M هو طول النمط S.

يمكن تفسير ذلك بسهولة من خلال ملاحظة كيفية عمل الحلقات.

يمكن تقسيم جميع تكرارات الحلقة الخارجية عبر i إلى ثلاث حالات:

1. يزيد k بواحد. الحلقة تكمل تكرار واحد.

2. لا يغير القيمة الصفرية لـ k . الحلقة تكمل تكرار واحد.

3. لا يغير أو ينقص قيمة موجبة لـ k .

يمكن تشغيل الحالتين الأوليين في معظم الأوقات M.

للحالة الثالثة ، دعنا نحدد P(s, i) = k1 و P(s, i + 1) = k2, k2 <= k1 . يجب أن يسبق كل حالة من هذه الحالات حدوث k1 - k2 للحالة الأولى. لا يتجاوز عدد النقصان k1 - k2 + 1 . وفي المجموع ، ليس لدينا أكثر من 2 * M تكرار.

شرح المثال الثاني

لنلقِ نظرة على نموذج المثال الثاني "abcdabcabcdabcdab". إليك كيفية معالجة وظيفة البادئة ، خطوة بخطوة:

1. بالنسبة للسلسلة الفرعية الفارغة والسلسلة الفرعية "أ" بطول واحد ، يتم تعيين قيمة وظيفة البادئة على صفر. ( k = 0 )

2. انظر إلى السلسلة الفرعية "ab". القيمة الحالية لـ k هي صفر والحرف "b" لا يساوي الحرف "a". هنا ، لدينا الحالة الثانية من القسم السابق. تظل قيمة k عند الصفر وقيمة دالة البادئة للسلسلة الفرعية "ab" تساوي صفرًا أيضًا.

3. إنها نفس حالة السلاسل الفرعية "abc" و "abcd". لا توجد بادئات تمثل أيضًا لاحقات هذه السلاسل الفرعية. تبقى القيمة بالنسبة لهم عند الصفر.

4. الآن دعونا نلقي نظرة على حالة مثيرة للاهتمام ، السلسلة الفرعية "abcda". لا تزال القيمة الحالية لـ k صفرًا ، لكن الحرف الأخير من السلسلة الفرعية لدينا يتطابق مع الحرف الأول. يؤدي هذا إلى تشغيل حالة s[k] == s[i] ، حيث k == 0 و i == 4 . المصفوفة مفهرسة بصفر ، و k هو فهرس الحرف التالي لبادئة الطول الأقصى. هذا يعني أننا وجدنا بادئة الحد الأقصى لطول السلسلة الفرعية لدينا والتي هي أيضًا لاحقة. لدينا الحالة الأولى ، حيث القيمة الجديدة لـ k تساوي واحدًا ، وبالتالي فإن قيمة وظيفة البادئة P ("abcda") هي واحدة.

5. تحدث نفس الحالة أيضًا مع السلسلتين الفرعيتين التاليتين ، P (“abcdab”) = 2 و P (“abcdabc”) = 3 . هنا ، نحن نبحث عن النمط الخاص بنا في النص ، ومقارنة السلاسل حرفًا بحرف. لنفترض أن الأحرف السبعة الأولى من النمط متطابقة مع حوالي سبعة أحرف متتالية من النص المعالج ، ولكن في الحرف الثامن لا يتطابق. ماذا يجب أن يحدث بعد ذلك؟ في حالة المطابقة الساذجة للسلسلة ، يجب أن نعيد سبعة أحرف إلى الوراء ونبدأ عملية المقارنة مرة أخرى من الحرف الأول في نمطنا. باستخدام قيمة وظيفة البادئة (هنا P (“abcdabc”) = 3 ) نعلم أن لاحقة المكونة من ثلاثة أحرف تتطابق بالفعل مع ثلاثة أحرف من النص. وإذا كان الحرف التالي في النص هو "d" ، فسيتم زيادة طول السلسلة الفرعية المتطابقة للنمط والسلسلة الفرعية في النص إلى أربعة ("abcd"). خلاف ذلك ، P ("abc") = 0 وسنبدأ عملية المقارنة من الحرف الأول للنمط. لكن المهم هو أننا لا نعود أثناء معالجة النص.

6. السلسلة الفرعية التالية هي "abcdabca". في السلسلة الفرعية السابقة ، كانت وظيفة البادئة تساوي ثلاثة. هذا يعني أن k = 3 أكبر من الصفر ، وفي نفس الوقت لدينا عدم تطابق بين الحرف التالي في البادئة ( s[k] = s[3] = "d" ) والحرف التالي في اللاحقة ( s[i] = s[7] = "a" ). هذا يعني أننا قمنا بتشغيل شرط s[k] != s[i] ، وأن البادئة "abcd" لا يمكن أن تكون لاحقة السلسلة. يجب أن نخفض قيمة k ونأخذ البادئة السابقة للمقارنة ، حيثما أمكن ذلك. كما وصفنا أعلاه ، المصفوفة مفهرسة بصفر ، و k هو فهرس الحرف التالي الذي نتحقق منه من البادئة. الفهرس الأخير للبادئة المطابقة حاليًا هو k - 1 . نأخذ قيمة وظيفة البادئة للبادئة المطابقة حاليًا k = result[k - 1] . في حالتنا (الحالة الثالثة) ، سيتم تقليل طول الحد الأقصى للبادئة إلى الصفر ثم في السطر التالي سيتم زيادته حتى واحد ، لأن "أ" هي البادئة القصوى وهي أيضًا لاحقة السلسلة الفرعية.

7. (هنا نواصل عملية الحساب الخاصة بنا حتى نصل إلى حالة أكثر إثارة للاهتمام.)

8. نبدأ في معالجة السلسلة الفرعية التالية: "abcdabcabcdabcd." القيمة الحالية لـ k هي سبعة. كما هو الحال مع "abcdabca" أعلاه ، فقد وصلنا إلى قيمة غير متطابقة: نظرًا لأن الحرف "a" (الحرف السابع) لا يساوي الحرف "d" ، لا يمكن أن تكون السلسلة الفرعية "abcdabca" هي لاحقة السلسلة. الآن نحصل على القيمة المحسوبة بالفعل لوظيفة البادئة لـ "abcdabc" (ثلاثة) والآن لدينا تطابق: البادئة "abcd" هي أيضًا لاحقة السلسلة. البادئة القصوى وقيمة دالة البادئة للسلسلة الفرعية لدينا هي أربعة ، لأن هذا هو ما أصبحت عليه القيمة الحالية لـ k .

9. نواصل هذه العملية حتى نهاية النمط.

باختصار: لا تستغرق كلتا الدورتين أكثر من 3 M تكرارات ، مما يثبت أن التعقيد هو O (M). استخدام الذاكرة هو أيضا O (M).

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

 public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

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

تعقيد هذه الوظيفة هو نفسه بالنسبة لوظيفة البادئة ، مما يجعل التعقيد الحسابي الكلي O (N + M) مع ذاكرة O (M) .

التوافه: الطرق String.IndexOf() و String.Contains() في إطار عمل .NET لها خوارزمية بنفس التعقيد تحت الغطاء.

خوارزمية Aho-Corasick

الآن نريد أن نفعل الشيء نفسه لأنماط متعددة.

افترض أن هناك أنماط M للأطوال L1 ، L2 ،…، Lm . نحتاج إلى العثور على جميع تطابقات الأنماط من قاموس في نص بطول N.

سيكون الحل البسيط هو أخذ أي خوارزمية من الجزء الأول وتشغيلها M مرات. لدينا تعقيد O (N + L1 + N + L2 + ... + N + Lm) ، أي O (M * N + L) .

أي اختبار جاد بما فيه الكفاية يقتل هذه الخوارزمية.

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

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

هذا هو المكان الذي تقوم فيه خوارزمية Aho-Corasick بسحرها.

تعقيد خوارزمية Aho-Corasick هو O (N + L + Z) ، حيث Z هو عدد المطابقات. اخترع ألفريد ف.آهو ومارغريت جيه كوراسيك هذه الخوارزمية في عام 1975.

تطبيق

هنا ، نحتاج إلى trie ، ونضيف إلى خوارزميتنا فكرة مشابهة لوظائف البادئة الموضحة أعلاه. سنقوم بحساب قيم دالة البادئة للقاموس بأكمله.

سيخزن كل رأس في المثلث المعلومات التالية:

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

هناك طرق متعددة لتنفيذ الروابط الفرعية. سيكون للخوارزمية تعقيد O (N + L + Z) في حالة المصفوفة ، ولكن هذا سيكون له متطلبات ذاكرة إضافية لـ O (L * q) ، حيث q هو طول الأبجدية ، لأن هذا هو الحد الأقصى لعدد الأطفال التي يمكن أن تمتلكها العقدة.

إذا استخدمنا بعض الهياكل مع وصول O (log (q)) إلى عناصرها ، فلدينا متطلبات ذاكرة إضافية لـ O (L) ، لكن تعقيد الخوارزمية بأكملها سيكون O ((N + L) * log (q) + ض) .

في حالة جدول التجزئة ، لدينا ذاكرة إضافية O (L) ، وسيكون تعقيد الخوارزمية بأكملها O (N + L + Z) .

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

لدينا بالفعل هيكل للرأس. بعد ذلك ، سنحدد قائمة الرؤوس ونبدأ العقدة الجذرية للمثلث.

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

ثم نضيف كل الأنماط إلى المثلث. لهذا ، نحتاج إلى طريقة لإضافة كلمات إلى trie:

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

في هذه المرحلة ، توجد جميع كلمات النمط في بنية البيانات. يتطلب هذا ذاكرة إضافية لـ O (L) .

بعد ذلك ، نحتاج إلى حساب جميع روابط اللاحقة وروابط إدخال القاموس.

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

سأقوم بمعالجة القمم حسب المستويات. لذلك ، سأستخدم خوارزمية البحث الأول (BFS):

وفيما يلي تنفيذ هذا الاجتياز:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

وفيما يلي طريقة CalcSuffLink لحساب ارتباط اللاحقة لكل رأس (أي قيمة وظيفة البادئة لكل سلسلة فرعية في trie):

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

تعقيد هذه الطريقة هو O (L) ؛ اعتمادًا على تنفيذ المجموعة الفرعية ، قد يكون التعقيد O (L * log (q)) .

إثبات التعقيد مشابه لإثبات وظيفة بادئة التعقيد في خوارزمية KMP.

دعونا نلقي نظرة على الصورة التالية. هذا هو تصور ثلاثي للقاموس { abba, cab, baba, caab, ac, abac, bac } بجميع معلوماته المحسوبة:

حواف Trie باللون الأزرق الغامق ، وارتباطات اللاحقة باللون الأزرق الفاتح ، وروابط لاحقة القاموس باللون الأخضر. يتم تمييز العقد المقابلة لإدخالات القاموس باللون الأزرق.

والآن نحتاج فقط إلى طريقة أخرى - معالجة كتلة نصية ننوي البحث من خلالها:

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

والآن هذا جاهز للاستخدام:

عند الإدخال ، لدينا قائمة بالأنماط:

 List<string> patterns;

ونص البحث:

 string text;

وإليك كيفية لصقها معًا:

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

وهذا كل شيء! أنت تعرف الآن كيف تعمل هذه الخوارزمية البسيطة والقوية!

Aho-Corasick مرن حقًا. لا يجب أن تكون أنماط البحث كلمات فقط ، ولكن يمكننا استخدام جمل كاملة أو سلاسل عشوائية من الأحرف.

أداء

تم اختبار الخوارزمية على معالج Intel Core i7-4702MQ.

للاختبارات ، أخذت قواميسين: 1000 كلمة إنجليزية شائعة ، و 10000 كلمة إنجليزية شائعة.

لإضافة كل هذه الكلمات إلى القاموس وتجهيز بنية البيانات للعمل مع كل من القواميس ، تطلبت الخوارزمية 55 مللي ثانية و 135 مللي ثانية على التوالي.

عالجت الخوارزمية كتبًا حقيقية مكونة من 3-4 ملايين حرف في غضون 1.0-1.3 ثانية ، بينما استغرقت 9.6 ثانية لكتاب به حوالي 30 مليون حرف.

موازاة خوارزمية Aho-Corasick

الموازاة مع خوارزمية Aho-Corasick ليست مشكلة على الإطلاق:

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

ماذا عن الكلمات التي يتم تقسيمها عند الحد الفاصل بين الأجزاء؟ يمكن حل هذه المشكلة بسهولة.

لنفترض أن N هو طول نصنا الكبير ، ويكون S بحجم مقطع ، ويكون L هو طول أكبر نمط في القاموس.

الآن يمكننا استخدام خدعة بسيطة. نقسم القطع مع بعض التداخل في النهاية ، على سبيل المثال أخذ [S * (i - 1), S * i + L - 1] ، حيث i هو فهرس القطعة. عندما نحصل على تطابق نمط ، يمكننا بسهولة الحصول على فهرس البداية للمطابقة الحالية والتحقق فقط من أن هذا الفهرس ضمن نطاق القطع بدون تداخل ، [S * (i - 1), S * i - 1] .

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

تعد خوارزمية Aho-Corasick خوارزمية قوية لمطابقة السلسلة تقدم أفضل تعقيد لأي إدخال ولا تتطلب ذاكرة إضافية كبيرة.

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

تعد وظيفة البادئة من خوارزمية KMP في حد ذاتها أداة مثيرة للاهتمام تعمل على جلب تعقيد مطابقة النمط الفردي إلى الوقت الخطي. تتبع خوارزمية Aho-Corasick نهجًا مشابهًا وتستخدم بنية بيانات ثلاثية لفعل الشيء نفسه لأنماط متعددة.

آمل أن تكون قد وجدت هذا البرنامج التعليمي حول خوارزمية Aho-Corasick مفيدًا.