خوارزمية أهو-كوراسيك

في علم الحاسوب ، تُعدّ خوارزمية أهو-كوراسيك خوارزمية بحث عن السلاسل النصية، ابتكرها ألفريد ف. أهو ومارغريت ج. كوراسيك عام ١٩٧٥. ^{[ ١ ]} وهي نوع من خوارزميات مطابقة القواميس ، حيث تحدد عناصر مجموعة محدودة من السلاسل النصية (القاموس) ضمن نص مُدخل. تُطابق هذه الخوارزمية جميع السلاسل النصية في آنٍ واحد. يتناسب تعقيد الخوارزمية خطيًا مع مجموع طول السلاسل النصية وطول النص المُراد البحث فيه وعدد التطابقات الناتجة. ولأنها تجد جميع التطابقات، فسيتم إرجاع عدة تطابقات لموقع سلسلة نصية واحد إذا تطابقت عدة سلاسل نصية من القاموس مع ذلك الموقع (على سبيل المثال، القاموس = a ، aa ، aaa، aaaa ، وسلسلة الإدخال هي aaaa ).

بشكل غير رسمي، تُنشئ الخوارزمية شجرة بحث باستخدام السلاسل النصية في القاموس، ثم تُنشئ آلة حالة محدودة من شجرة البحث بإضافة روابط إضافية بين العقد. تُتيح هذه الروابط الإضافية انتقالات سريعة بين حالات فشل مطابقة السلاسل النصية (مثل البحث عن كلمة " cart" في شجرة بحث لا تحتوي على "cart" ، ولكنها تحتوي على "art" ، وبالتالي ستفشل عند العقدة التي تبدأ بـ "car ")، إلى فروع أخرى من شجرة البحث تشترك في لاحقة مشتركة (مثل، في الحالة السابقة، قد يكون فرع " attribute " هو أفضل انتقال جانبي). يسمح هذا للآلة بالانتقال بين حالات مطابقة السلاسل النصية دون الحاجة إلى التراجع.

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

شكلت خوارزمية مطابقة السلاسل Aho-Corasick أساس أمر Unix الأصلي fgrep .

كما هو الحال مع العديد من الاختراعات في مختبرات بيل آنذاك، وُلدت خوارزمية أهو-كوراسيك صدفةً من خلال محادثة بينهما بعد ندوةٍ ألقاها أهو. كانت كوراسيك عالمة معلومات، وقد حصلت على درجة الدكتوراه قبل عام من جامعة ليهاي . هناك، تناولت أطروحتها تأمين البيانات الخاصة ضمن الأنظمة المفتوحة، من منظور الهياكل التجارية والقانونية والحكومية، والأدوات التقنية التي كانت ناشئة في ذلك الوقت. ^{[ 2 ]} وفي سياقٍ مماثل، كانت في مختبرات بيل تعمل على تطوير أداةٍ تُمكّن الباحثين من الاطلاع على الأعمال الجارية التي يُنجزها المتعاقدون مع الحكومة، وذلك من خلال البحث في التسجيلات الصوتية للمنشورات التي تُقدّمها الحكومة.

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

انتهى بها الأمر بحضور ندوة حول تصميم الخوارزميات قدمها أهو، وبعدها دار بينهما حديث حول عملها وهذه المشكلة. اقترح أهو تحسين كفاءة البرنامج باستخدام منهج خوارزمية أهو-كوراسيك الحالية، وصمم كوراسيك برنامجًا بناءً على تلك الأفكار. وقد أدى ذلك إلى خفض تكلفة تشغيل بحث تلك الباحثة في مجال المراجع من أكثر من 600 دولار إلى 25 دولارًا فقط. ^{[ 3 ]}

في هذا المثال، سنعتبر قاموسًا يتكون من الكلمات التالية: {a, ab, bab, bc, bca, c, caa}.

الرسم البياني أدناه هو بنية بيانات Aho–Corasick التي تم إنشاؤها من القاموس المحدد، حيث يمثل كل صف في الجدول عقدة في شجرة البحث، ويشير عمود المسار إلى التسلسل (الفريد) للأحرف من الجذر إلى العقدة.

تحتوي بنية البيانات على عقدة واحدة لكل بادئة من بادئات كل سلسلة نصية في القاموس. فإذا كانت (bca) موجودة في القاموس، فستكون هناك عقد لكل من (bca) و(bc) و(b) و(). إذا كانت العقدة موجودة في القاموس، فستكون زرقاء اللون، وإلا فستكون رمادية.

يوجد قوس أسود موجه "تابع" من كل عقدة إلى عقدة يُحدد اسمها بإضافة حرف واحد. لذا يوجد قوس أسود من (bc) إلى (bca).

يوجد قوس أزرق موجه يُسمى "لاحقة" من كل عقدة إلى العقدة التي تُمثل أطول لاحقة ممكنة لها في الرسم البياني. على سبيل المثال، بالنسبة للعقدة (caa)، فإن لواحقها هي (aa) و(a) و(). أطول هذه اللواحق الموجودة في الرسم البياني هي (a). لذا، يوجد قوس أزرق من (caa) إلى (a). يمكن حساب الأقواس الزرقاء في وقت خطي عن طريق إجراء بحث بالعرض أولاً [ستكون عقدة اللاحقة المحتملة دائمًا في مستوى أدنى] بدءًا من الجذر. يمكن العثور على هدف القوس الأزرق لعقدة تمت زيارتها عن طريق تتبع القوس الأزرق للعقدة الأب إلى أطول عقدة لاحقة لها والبحث عن ابن لعقدة اللاحقة التي يتطابق حرفها مع حرف العقدة التي تمت زيارتها. إذا لم يكن الحرف موجودًا كابن، فيمكننا العثور على أطول لاحقة تالية (باتباع القوس الأزرق مرة أخرى) ثم البحث عن الحرف. يمكننا القيام بذلك حتى نجد الحرف (كعنصر فرعي لعقدة) أو نصل إلى الجذر (والذي سيكون دائمًا لاحقة لكل سلسلة نصية).

يوجد قوس أخضر يُسمى "لاحقة القاموس" يمتد من كل عقدة إلى العقدة التالية في القاموس، ويمكن الوصول إليه باتباع الأقواس الزرقاء. على سبيل المثال، يوجد قوس أخضر من (bca) إلى (a) لأن (a) هي أول عقدة في القاموس (أي عقدة زرقاء) يتم الوصول إليها عند اتباع الأقواس الزرقاء إلى (ca) ثم إلى (a). يمكن حساب الأقواس الخضراء في وقت خطي من خلال اجتياز الأقواس الزرقاء بشكل متكرر حتى يتم العثور على عقدة زرقاء، وتخزين هذه المعلومات.

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

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

يؤدي تنفيذ الأمر على سلسلة الإدخال abccab إلى الخطوات التالية:

تفترض خوارزمية أهو-كوراسيك الأصلية أن مجموعة سلاسل البحث ثابتة. ولا تنطبق مباشرةً على التطبيقات التي تُضاف فيها سلاسل بحث جديدة أثناء تطبيق الخوارزمية. ومن الأمثلة على ذلك برنامج فهرسة تفاعلي، حيث يتصفح المستخدم النص ويُظلل الكلمات أو العبارات الجديدة لفهرستها عند رؤيتها. وقدّم برتراند ماير نسخةً تزايديةً من الخوارزمية، حيث يمكن توسيع مجموعة سلاسل البحث تدريجيًا أثناء البحث، مع الحفاظ على التعقيد الخوارزمي للنسخة الأصلية. ^{[ 4 ]}

• خوارزمية كومنتز-والتر

• Aho—Corasick في قاموس الخوارزميات وهياكل البيانات التابع للمعهد الوطني للمعايير والتكنولوجيا (2019-07-15)