خوارزمية أوكونين

في علم الحاسوب ، تُعدّ خوارزمية أوكونن خوارزمية خطية تعمل عبر الإنترنت لإنشاء أشجار اللواحق ، وقد اقترحها إيسكو أوكونن عام ١٩٩٥. ^{[ ١ ]} تبدأ الخوارزمية بشجرة لواحق ضمنية تحتوي على الحرف الأول من السلسلة النصية. ثم تتنقل عبر السلسلة، مضيفةً الأحرف تباعًا حتى تكتمل الشجرة. هذا الترتيب في إضافة الأحرف هو ما يمنح خوارزمية أوكونن خاصية "العمل عبر الإنترنت". أما الخوارزمية الأصلية التي قدمها بيتر واينر عام ١٩٧٣، فقد كانت تعمل بشكل عكسي من الحرف الأخير إلى الحرف الأول، بدءًا من أقصر لاحقة وصولًا إلى أطولها. ^{[ ٢ ]} وقد توصل إدوارد إم. مكريت عام ١٩٧٦ إلى خوارزمية أبسط، تبدأ من أطول لاحقة وصولًا إلى أقصرها. ^{[ ٣ ]}

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

تُنشئ خوارزمية أوكونين شجرة لاحقة ضمنية T_{_i} لكل بادئة S[1...i] من السلسلة S (حيث S هي سلسلة طولها n). تبدأ الخوارزمية بإنشاء T _₁ باستخدام الحرف ^الأول ، ثم T _₂ باستخدام الحرف ^الثاني ، ثم T _₃ باستخدام الحرف ^الثالث ، وهكذا حتى T _{_n} باستخدام الحرف ^النوني . يمكنك إيجاد الخصائص التالية في شجرة لاحقة تستخدم خوارزمية أوكونين:

• يتم بناء شجرة اللواحق الضمنية T _i+1 فوق شجرة اللواحق الضمنية T _i .
• في أي وقت معين، تقوم خوارزمية أوكونين ببناء شجرة اللواحق للأحرف التي تمت رؤيتها حتى الآن، وبالتالي فهي تتمتع بخاصية التشغيل عبر الإنترنت ، مما يسمح للخوارزمية بأن يكون وقت تنفيذها O(n).
• تنقسم خوارزمية أوكونين إلى n مرحلة (مرحلة واحدة لكل حرف في السلسلة بطول n).
• يتم تقسيم كل مرحلة i+1 إلى i+1 امتدادات، واحد لكل لاحقة من اللواحق i+1 لـ S[1...i+1].

تتمحور عملية إضافة اللاحقة حول إضافة الحرف التالي إلى شجرة اللواحق المبنية حتى الآن. في الإضافة j من المرحلة i+1، يحدد الخوارزمية نهاية S[j...i] (الموجودة بالفعل في الشجرة نتيجةً للمرحلة i السابقة)، ثم يضيف اللاحقة S[j...i] للتأكد من وجودها في الشجرة. توجد ثلاث قواعد للإضافة:

1. إذا انتهى المسار من الجذر المسمى S[j...i] عند حافة الورقة (أي أن S[i] هو الحرف الأخير على حافة الورقة)، فسيتم إضافة الحرف S[i+1] إلى نهاية التسمية على حافة الورقة تلك.
2. إذا انتهى المسار من الجذر المسمى S[j...i] عند حافة غير طرفية (أي، يوجد المزيد من الأحرف بعد S[i] على المسار) وكان الحرف التالي ليس S[i+1]، فسيتم إنشاء حافة طرفية جديدة تحمل التسمية S[i+1] والرقم j بدءًا من الحرف S[i+1]. كما سيتم إنشاء عقدة داخلية جديدة إذا انتهى المسار S[1...i] داخل (بين) حافة غير طرفية.
3. إذا انتهى المسار من الجذر المسمى S[j..i] عند حافة غير طرفية (أي أن هناك المزيد من الأحرف بعد S[i] على المسار) وكان الحرف التالي هو S[i+1] (موجود بالفعل في الشجرة)، فلا تفعل شيئًا.

من النقاط المهمة التي يجب ملاحظتها أنه من أي عقدة (جذرية أو داخلية)، سيكون هناك ضلع واحد فقط يبدأ من حرف واحد. ولن يكون هناك أكثر من ضلع واحد يخرج من أي عقدة تبدأ من نفس الحرف.

يتطلب التنفيذ البسيط لإنشاء شجرة اللواحق تعقيدًا زمنيًا قدره O(n²) أو حتى O(n³) في ^ترميز Big O ، حيث n هو طول السلسلة . وباستغلال عدد من التقنيات الخوارزمية ، تمكن أوكونين من تقليل هذا التعقيد إلى ^O ( n ) ( خطي) للأبجديات ذات الحجم الثابت، وإلى O ( n log n ) بشكل عام، مما يضاهي أداء وقت التشغيل للخوارزميتين السابقتين.

لتوضيح كيفية إنشاء شجرة اللواحق باستخدام خوارزمية أوكونين بشكل أفضل، يمكننا النظر في السلسلة S = xabxac.

1. ابدأ بعقدة جذر فارغة.
2. بناء${\displaystyle T_{1}}$وذلك S[1]بإضافة الحرف الأول من السلسلة. تنطبق القاعدة الثانية، مما يُنشئ عقدة طرفية جديدة.
3. بناء${\displaystyle T_{2}}$بإضافة S[1..2]اللاحقتين xa( xaو a). تُطبَّق القاعدة 1، التي تُوسِّع تسمية المسار في حافة الورقة الموجودة. تُطبَّق القاعدة 2، التي تُنشئ عقدة ورقة جديدة.
4. بناء${\displaystyle T_{3}}$بإضافة S[1..3]اللواحق xab( xabو abو b). تُطبَّق القاعدة 1، التي تُوسِّع تسمية المسار في حافة الورقة الموجودة. تُطبَّق القاعدة 2، التي تُنشئ عقدة ورقة جديدة.
5. بناء${\displaystyle T_{4}}$بإضافة S[1..4]اللواحق xabx( xabx، abxو، bxو x). تنطبق القاعدة 1، التي تمدد تسمية المسار في حافة الورقة الموجودة. تنطبق القاعدة 3، فلا تفعل شيئًا.
6. البنى${\displaystyle T_{5}}$بإضافة S[1..5]اللواحق xabxa( xabxa، abxa،، bxaو xa) a. تنطبق القاعدة 1، التي تمدد تسمية المسار في حافة الورقة الموجودة. تنطبق القاعدة 3، لا تفعل شيئًا.
7. البنى${\displaystyle T_{6}}$بإضافة S[1..6]اللواحق xabxac( xabxac، abxac، bxac، xac، acو c). تُطبَّق القاعدة 1، التي تُوسِّع تسمية المسار في حافة الورقة الموجودة. تُطبَّق القاعدة 2، التي تُنشئ عقدة ورقة جديدة (في هذه الحالة، يتم إنشاء ثلاث حواف ورقة جديدة وعقدتين داخليتين جديدتين).

• شرح مفصل بلغة إنجليزية بسيطة
• البحث السريع عن السلاسل النصية باستخدام أشجار اللواحق: درس تعليمي من إعداد مارك نيلسون. يتضمن مثالاً تطبيقياً مكتوباً بلغة C++.
• التنفيذ بلغة C مع شرح مفصل
• شرائح المحاضرة من إعداد غاي بليلوش
• الصفحة الرئيسية لـ Ukkonen
• مشروع فهرسة النصوص (بناء أوكونين الخطي لأشجار اللواحق)
• التنفيذ بلغة C الجزء 1 الجزء 2 الجزء 3 الجزء 4 الجزء 5 الجزء 6