javascript - خوارزمية شجرة لاحقة Ukkonen في سهل الانجليزية





c# algorithm search suffix-tree (6)


حدسي هو كما يلي:

بعد التكرار k للحلقة الرئيسية قمت ببناء شجرة لاحقة تحتوي على كل لاحقات السلسلة الكاملة التي تبدأ بحرف k الأول.

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

بعد len (string) تكرار لديك شجرة لاحقة تحتوي على كل اللواحق.

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

على سبيل المثال ، لنفترض أنك رأيت أحرف abcabc '. تمثل النقطة النشطة النقطة في الشجرة المقابلة لللاحقة 'abc'.

يتم تمثيل النقطة النشطة (الأصل ، الأول ، الأخير). هذا يعني أنك حالياً في نقطة في الشجرة التي تحصل عليها عن طريق البدء في أصل عقدة ومن ثم إطعام الأحرف في السلسلة [الأول: الأخير]

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

ملاحظة 1: تعطي المؤشرات اللاحقة ارتباطًا لأقصر تطابق في المرة التالية لكل عقدة.

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

ملاحظة 3: جزء التقديس يوفر ببساطة الوقت في التحقق من النقطة النشطة. على سبيل المثال ، لنفترض أنك استخدمت دائمًا الأصل = 0 ، وتغيرت أولاً والأخير. وللتحقق من النقطة النشطة ، يجب أن تتبع شجرة اللواحق في كل مرة على طول العقد الوسيطة. من المنطقي تخزين نتيجة اتباع هذا المسار من خلال تسجيل المسافة فقط من العقدة الأخيرة.

هل يمكنك إعطاء مثال الكود على ما تعنيه بمتغيرات "الإصلاح" الإلزامية؟

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

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

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

للرجوع إليها ، إليك ورقة Ukkonen حول الخوارزمية: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

فهمي الأساسي ، حتى الآن:

  • أحتاج إلى التكرار من خلال كل بادئة P لسلسلة معينة T
  • أحتاج إلى التكرار من خلال كل لاحقة S في البادئة P وإضافة ذلك إلى الشجرة
  • لإضافة لاحقة S إلى الشجرة ، أحتاج إلى التكرار من خلال كل حرف في S ، مع التكرارات التي تتكون إما من السير إلى أسفل فرع موجود يبدأ بنفس مجموعة الأحرف C في S ويحتمل أن تقسم الحافة إلى العقد التابعة عندما أكون الوصول إلى حرف مختلف في اللاحقة ، أو إذا لم يكن هناك حافة مطابقة للمشي. عندما لا يتم العثور على حافة مطابقة للمشي على C ، يتم إنشاء حافة أوراق جديدة لـ C.

يبدو أن الخوارزمية الأساسية هي O (n 2 ) ، كما هو موضح في معظم التفسيرات ، حيث أننا نحتاج إلى تخطي كل البادئات ، ثم نحتاج إلى المرور بكل اللواحق لكل بادئة. يبدو أن خوارزمية ukkonen فريدة من نوعها بسبب تقنية مؤشر اللاحقة التي يستخدمها ، على الرغم من أنني أعتقد أن هذا هو ما أواجه مشكلة في الفهم.

أواجه أيضًا مشكلة في الفهم:

  • بالضبط متى وكيف يتم تعيين "نقطة نشطة" واستخدامها وتغييرها
  • ما يجري مع جانب تقديس الخوارزمية
  • لماذا تحتاج عمليات التنفيذ التي رأيتها إلى "إصلاح" المتغيرات المحيطة التي يستخدمونها

هنا هو أكمل شفرة المصدر C # . لا يعمل فقط بشكل صحيح ، ولكنه يدعم التقسيم التلقائي ويعرض رسمًا نصيًا أجمل للإخراج. شفرة المصدر وناتج العينة في:

https://gist.github.com/2373868

التحديث 2017-11-04

بعد سنوات عديدة ، وجدت استخدامًا جديدًا لأشجار لاحقة ، ونفذت الخوارزمية في جافا سكريبت . جست هو أدناه. يجب أن يكون خالية من الأخطاء. npm install chalk إلى ملف js ، npm install chalk من نفس الموقع ، ثم قم بتشغيل مع node.js لمشاهدة بعض الإخراج الملونة. هناك نسخة مخففة في نفس Gist ، دون أي رمز التصحيح.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6




حاولت تنفيذ Suffix Tree بالطريقة المذكورة في إجابة jogojapan ، ولكنها لم تنجح في بعض الحالات بسبب الصياغة المستخدمة للقواعد. علاوة على ذلك ، لقد ذكرت أنه لم يتمكن أحد من تنفيذ شجرة لاحقة صحيحة تمامًا باستخدام هذا الأسلوب. أدناه سأكتب "نظرة عامة" على إجابة jogojapan مع بعض التعديلات على القواعد. سوف أصف أيضًا الحالة عندما ننسى إنشاء روابط لاحقة مهمة .

المتغيرات الإضافية المستخدمة

  1. نقطة نشطة - ثلاثية (active_node ؛ active_edge ؛ active_length) ، تظهر من حيث يجب أن نبدأ في إدخال لاحقة جديدة.
  2. الباقي - يعرض عدد اللواحق التي يجب إضافتها بشكل صريح . على سبيل المثال ، إذا كانت كلمتنا هي "abcaabca" ، والباقي = 3 ، فهذا يعني أنه يجب علينا معالجة 3 لاحقات أخيرة : bca ، ca و a .

دعونا نستخدم مفهوم عقدة داخلية - جميع العقد ، باستثناء الجذر والأوراق هي العقد الداخلية .

الملاحظة 1

عندما تكون اللاحقة النهائية التي نحتاج لإدخالها موجودة في الشجرة بالفعل ، فإن الشجرة نفسها لم تتغير على الإطلاق (نقوم فقط بتحديث active point remainder ).

الملاحظة 2

إذا كان active_length نقطة ما أكبر أو مساوياً لطول الحافة الحالية ( edge_length ) ، فإننا نقوم بنقل edge_length active point لأسفل حتى تكون edge_length أكبر من active_length .

الآن ، دعنا نعيد تعريف القواعد:

المادة 1

إذا كان بعد الإدراج من العقدة النشطة = الجذر ، يكون الطول النشط أكبر من 0 ، ثم:

  1. العقدة النشطة لا تتغير
  2. طول نشط هو decremented
  3. يتم إزاحة الحافة النشطة (إلى الحرف الأول لللاحقة التالية التي يجب إدراجها)

القاعدة 2

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

هذا التعريف Rule 2 يختلف عن jogojapan ، حيث أننا لا نأخذ بعين الاعتبار العقد الداخلية التي تم إنشاؤها حديثًا فحسب ، بل أيضًا العقد الداخلية ، التي ندخل منها.

القاعدة 3

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

في هذا التعريف Rule 3 نأخذ بعين الاعتبار أيضًا إدراجات العقد الورقية (وليس فقط العقد المقسمة).

وأخيرًا ، الملاحظة 3:

عندما يكون الرمز الذي نريد إضافته إلى الشجرة موجودًا بالفعل على الحافة ، نقوم ، وفقًا Observation 1 ، بتحديث active point remainder ، تاركًا الشجرة دون تغيير. ولكن إذا كانت هناك عقدة داخلية تم تحديدها بأنها تحتاج إلى وصلة لاحقة ، فيجب أن نربط تلك العقدة مع active node الحالية من خلال وصلة لاحقة.

دعنا ننظر إلى مثال شجرة لاحقة لـ cdddcdc إذا قمنا بإضافة ارتباط لاحقة في مثل هذه الحالة وإذا لم نفعل ذلك:

  1. إذا لم نقم بتوصيل العقد من خلال رابط لاحقة:

    • قبل إضافة الحرف الأخير c :

    • بعد إضافة الحرف الأخير c :

  2. إذا قمنا بتوصيل العقد من خلال وصلة لاحقة:

    • قبل إضافة الحرف الأخير c :

    • بعد إضافة الحرف الأخير c :

يبدو أنه لا يوجد فرق كبير: في الحالة الثانية هناك رابطان لاحقتان إضافيتان. لكن هذه الروابط لاحقة صحيحة ، وواحد منها - من العقدة الزرقاء إلى اللون الأحمر - مهم جدا لنهجنا مع نقطة نشطة . المشكلة هي أنه إذا لم نقم بوضع رابط لاحقة هنا ، لاحقًا ، عندما نضيف بعض الأحرف الجديدة إلى الشجرة ، قد نلغي إضافة بعض العقد إلى الشجرة بسبب Rule 3 ، لأنه ، وفقًا لذلك ، لا رابط لاحقة ، ثم يجب علينا وضع active_node على الجذر.

عندما كنا نضيف الحرف الأخير إلى الشجرة ، كانت العقدة الحمراء موجودة بالفعل قبل أن نقوم بإدخال جزء من العقدة الزرقاء (الحافة المسجلة "c" ). نظرًا لوجود إدراج من العقدة الزرقاء ، فإننا نضع علامة على أنه يحتاج إلى وصلة لاحقة . بعد ذلك ، بالاعتماد على نهج النقطة النشطة ، تم تعيين active node إلى العقدة الحمراء. ولكننا لا نقوم بإدخال جزء من العقدة الحمراء ، حيث أن الحرف 'c' موجود بالفعل على الحافة. هل هذا يعني أنه يجب ترك العقدة الزرقاء بدون رابط لاحقة؟ لا ، يجب أن نربط العقدة الزرقاء باللون الأحمر من خلال وصلة لاحقة. لماذا هذا صحيح؟ لأن نهج النقطة النشطة يضمن وصولنا إلى المكان المناسب ، أي إلى المكان التالي حيث يجب علينا معالجة إدخال لاحقة أقصر .

أخيرًا ، إليك تطبيقاتي الخاصة بـ Suffix Tree:

  1. Java
  2. C++

نأمل أن تساعد هذه "النظرة العامة" جنبا إلى جنب مع الإجابة المفصلة لجوجوجابان شخصًا ما على تنفيذ شجرة لاحقة خاصة به.




فيما يلي محاولة لوصف خوارزمية Ukkonen من خلال إظهار ما تقوم به أولاً عندما تكون السلسلة بسيطة (أي لا تحتوي على أي أحرف متكررة) ، ثم توسيعها إلى الخوارزمية الكاملة.

أولا ، بعض البيانات الأولية.

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

  2. ولكن : على عكس تراويح البحث ، فإن تصنيفات الحواف ليست أحرفًا مفردة. بدلاً من ذلك ، يتم تصنيف كل حافة باستخدام زوج من الأعداد الصحيحة [from,to] . هذه مؤشرات في النص. بهذا المعنى ، تحمل كل حافة علامة سلسلة من الطول التعسفي ، ولكنها تأخذ مساحة O (1) فقط (مؤشرين).

المبدأ الأساسي

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

abc

تعمل الخوارزمية في خطوات ، من اليسار إلى اليمين . هناك خطوة واحدة لكل حرف في السلسلة . قد تشتمل كل خطوة على أكثر من عملية فردية ، لكننا سنرى (انظر الملاحظات النهائية في النهاية) أن إجمالي عدد العمليات هو O (n).

لذا ، نبدأ من اليسار ، ونقوم أولاً بإدخال حرف واحد فقط عن طريق إنشاء حافة من العقدة الجذرية (على اليسار) إلى ورقة ، ووضع علامة عليها كـ [0,#] ، مما يعني أن الحافة تمثل السلسلة الفرعية تبدأ من الموضع 0 وتنتهي في النهاية الحالية . يمكنني استخدام الرمز # ليعني النهاية الحالية ، والتي هي في الموضع 1 (اليمين بعد a ).

لدينا شجرة أولية تبدو كالتالي:

وما يعنيه هذا هو:

الآن نتقدم إلى الموضع 2 (بعد b ) مباشرةً. هدفنا في كل خطوة هو إدخال كل اللواحق حتى الوضع الحالي . نفعل هذا من قبل

  • توسيع aedge الحالي إلى ab
  • إدخال حافة جديدة ل b

في تمثيلنا هذا يبدو

وما يعنيه هو:

نلاحظ شيئين:

  • تمثيل الحواف لـ ab هو نفسه كما اعتاد أن يكون في الشجرة الأولية: [0,#] . تغير معناها تلقائيًا لأننا قمنا بتحديث الموضع الحالي من 1 إلى 2.
  • تستهلك كل حافة مساحة (1) O ، لأنها تتكون من مؤشرين فقط في النص ، بغض النظر عن عدد الأحرف التي تمثلها.

بعد ذلك نقوم بزيادة الموضع مرة أخرى وتحديث الشجرة بإلحاق c بكل حافة موجودة وإدراج حافة جديدة لللاحقة الجديدة c .

في تمثيلنا هذا يبدو

وما يعنيه هو:

نلاحظ:

  • الشجرة هي شجرة اللاحقة الصحيحة تصل إلى الموضع الحالي بعد كل خطوة
  • هناك العديد من الخطوات حيث توجد أحرف في النص
  • مقدار العمل في كل خطوة هو O (1) ، لأنه يتم تحديث جميع الحواف الموجودة تلقائيًا عن طريق زيادة # ، ويمكن إدراج الحافة الجديدة الواحدة للحرف النهائي في زمن O (1). ومن ثم لسلسلة الطول n ، لا يلزم سوى زمن O (n).

التمديد الأول: تكرار بسيط

بالطبع هذا يعمل بشكل جيد فقط لأن السلسلة لا تحتوي على أي تكرار. نحن ننظر الآن إلى سلسلة أكثر واقعية:

abcabxabcd

يبدأ بـ abc كما في المثال السابق ، ثم يتم تكرار ab ويتبعه x ، ثم يتم تكرار abc متبوعاً بـ d .

الخطوات من 1 إلى 3: بعد الخطوات الثلاث الأولى ، يكون لدينا الشجرة من المثال السابق:

الخطوة 4: ننتقل # إلى الموضع 4. هذا ينطوي ضمنيًا على تحديث جميع الحواف الموجودة إلى هذا:

ونحتاج إلى إدراج لاحقة نهائية للخطوة الحالية ، a ، في الجذر.

قبل القيام بذلك ، نقدم اثنين من المتغيرات الأخرى (بالإضافة إلى # ) ، والتي بالطبع كانت موجودة طوال الوقت لكننا لم نستخدمها حتى الآن:

  • النقطة النشطة ، وهي ثلاثية (active_node,active_edge,active_length)
  • remainder ، وهو عدد صحيح يشير إلى عدد اللواحق الجديدة التي نحتاج لإدخالها

سيصبح المعنى الدقيق لهذين الاثنين واضحًا ، لكن دعنا نقول الآن:

  • في مثال abc البسيط ، كانت النقطة النشطة دائما (root,'\0x',0) ، أي active_node كانت العقدة الجذرية ، تم تحديد active_edge null '\0x' ، وكان active_length صفر. كان تأثير ذلك هو إدراج الحافة الجديدة التي أدخلناها في كل خطوة في عقدة الجذر كحافة تم إنشاؤها حديثًا. سنرى قريبًا سبب ضرورة وجود ثلاثة أضعاف لتمثيل هذه المعلومات.
  • تم ضبط remainder على 1 في بداية كل خطوة. كان معنى هذا أن عدد اللواحق التي كان علينا إدخالها بفعالية في نهاية كل خطوة كان 1 (دائماً الحرف النهائي فقط).

الآن سوف يتغير هذا. عندما ندخل الحرف النهائي الحالي a في الجذر ، نلاحظ أن هناك بالفعل حافة صادرة تبدأ بـ ، على وجه التحديد: abca . هذا ما نفعله في مثل هذه الحالة:

  • لا نقوم بإدراج حافة جديدة [4,#] في عقدة الجذر. بدلاً من ذلك ، نلاحظ ببساطة أن اللاحقة موجودة بالفعل في شجرتنا. ينتهي في وسط حافة أطول ، لكننا لا نهتم بذلك. نحن فقط نترك الأشياء كما هي.
  • قمنا بتعيين نقطة النشط إلى (root,'a',1) . وهذا يعني أن النقطة النشطة هي الآن في منتصف الحافة الخارجية للعقدة الجذرية التي تبدأ بـ ، على وجه التحديد ، بعد الموضع 1 على تلك الحافة. نلاحظ أن يتم تحديد الحافة ببساطة من خلال أول حرف لها a . هذا يكفي لأنه لا يمكن أن يكون هناك سوى حافة واحدة تبدأ بأي حرف معين (تأكد من أن هذا صحيح بعد قراءة الوصف بأكمله).
  • نحن أيضا زيادة remainder ، لذلك في بداية الخطوة التالية سيكون 2.

ملاحظة: عندما تكون اللاحقة النهائية التي نحتاج لإدخالها موجودة في الشجرة بالفعل ، فإن الشجرة نفسها لم تتغير على الإطلاق (نقوم فقط بتحديث النقطة النشطة remainder ). الشجرة إذن ليست تمثيل دقيق لشجرة اللاحقة حتى الوضع الحالي أكثر من ذلك ، ولكنها تحتوي على كل اللواحق (لأن اللاحقة النهائية مضمنة ضمنا ). وبالتالي ، وبصرف النظر عن تحديث المتغيرات (التي هي كل طول ثابت ، لذلك هذا هو O (1)) ، لم يكن هناك عمل في هذه الخطوة.

الخطوة 5: نقوم بتحديث الوضع الحالي # إلى 5. يقوم هذا تلقائيًا بتحديث الشجرة إلى هذا:

ولأن remainder هو 2 ، نحتاج إلى إدخال اللواحق النهائية للموضع الحالي: ab و b . هذا في الأساس بسبب:

  • اللاحقة من الخطوة السابقة لم يتم إدخالها بشكل صحيح. لذا فقد بقي ، وبما أننا قد تقدمنا ​​خطوة واحدة ، فقد نمت الآن من a إلى.
  • ونحن بحاجة إلى إدخال الحافة النهائية الجديدة b .

في الواقع العملي هذا يعني أننا نذهب إلى النقطة النشطة (التي تشير إلى ما هو على حافة الآن abcab ) ، وإدخال الحرف الأخير الحالي b . ولكن: مرة أخرى ، تبين أن b موجود بالفعل على نفس الحافة.

لذا ، مرة أخرى ، نحن لا نغير الشجرة. نحن ببساطة:

  • قم بتحديث النقطة النشطة إلى (root,'a',2) (نفس العقدة والحافة كما كان من قبل ، ولكن الآن نشير إلى خلف b )
  • قم بزيادة remainder إلى 3 لأننا لم نقم بإدخال الحافة النهائية من الخطوة السابقة بشكل صحيح ، ولم نقم بإدخال الحافة النهائية الحالية أيضًا.

لكي نكون واضحين: كان علينا إدخال ab و b في الخطوة الحالية ، ولكن بسبب العثور على ab بالفعل ، قمنا بتحديث النقطة النشطة ولم نحاول حتى إدراج b . لماذا ا؟ لأنه إذا كان ab في الشجرة ، فيجب أن تكون كل لاحقة (بما في ذلك b ) في الشجرة أيضًا. ربما فقط ضمنيًا ، لكن يجب أن يكون هناك ، بسبب الطريقة التي بنينا بها الشجرة حتى الآن.

ننتقل إلى الخطوة 6 عن طريق زيادة # . يتم تحديث الشجرة تلقائيًا إلى:

لأن remainder هو 3 ، يجب علينا إدخال abx و bx و x . تخبرنا النقطة النشطة أين تنتهي ab ، لذا نحتاج فقط للقفز هناك وإدراج x . في الواقع ، x ليس هناك حتى الآن ، لذلك قمنا بتقسيم حافة abcabx وإدخال عقدة داخلية:

لا تزال تمثيلات الحافة تشير إلى النص ، لذلك يمكن تقسيم وإدراج عقدة داخلية في زمن O (1).

لذلك فقد تعاملنا مع abx remainder decrement إلى 2. الآن نحن بحاجة إلى إدراج لاحقة المتبقية bx . ولكن قبل أن نفعل ذلك ، نحتاج إلى تحديث النقطة النشطة. القاعدة الخاصة بهذا ، بعد تقسيم وإدراج إحدى الحواف ، ستسمى القاعدة 1 أدناه ، وتطبق عندما يكون active_node جذرًا ( active_node القاعدة 3 للحالات الأخرى active_node أدناه). هنا القاعدة 1:

بعد الإدراج من الجذر ،

  • يبقى active_node الجذر
  • يتم تعيين active_edge على أول حرف active_edge الجديدة التي نحتاج لإدخالها ، أي b
  • يتم تقليل active_length بمقدار 1

ومن ثم ، فإن النقطة الثلاثية النشطة الجديدة (root,'b',1) تشير إلى أنه يجب إجراء bcabx حافة bcabx ، خلف حرف واحد ، أي خلف b . يمكننا تحديد نقطة الإدراج في زمن O (1) والتحقق مما إذا كانت x موجودة بالفعل أم لا. لو كان موجودًا ، سننهي الخطوة الحالية ونترك كل شيء كما هو. لكن x غير موجود ، لذلك نقوم بإدخاله عن طريق تقسيم الحافة:

مرة أخرى ، استغرق هذا وقت O (1) ونقوم بتحديث remainder إلى 1 والنقطة النشطة إلى (root,'x',0) كما تنص القاعدة 1.

ولكن هناك شيء آخر يتعين علينا القيام به. سنسمي هذه القاعدة 2:

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

ما زلنا بحاجة إلى إدراج لاحقة نهائية من الخطوة الحالية ، x . نظرًا لأن مكون active_length للعقدة النشطة قد انخفض إلى 0 ، يتم إجراء active_length النهائي عند الجذر مباشرةً. نظرًا لعدم وجود حافة صادرة في عقدة الجذر تبدأ بـ x ، فإننا نضيف حافة جديدة:

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

ننتقل إلى الخطوة 7 من خلال تعيين # = 7 ، الذي يلحق تلقائيًا الحرف التالي ، a ، بجميع حواف الأوراق ، كما هو الحال دائمًا. ثم نحاول إدخال الحرف النهائي الجديد إلى النقطة النشطة (الجذر) ، ونكتشف أنه موجود بالفعل. لذلك ننتهي من الخطوة الحالية دون إدخال أي شيء وتحديث النقطة النشطة إلى (root,'a',1) .

في الخطوة 8 ، # = 8 ، نضيف b ، وكما رأينا من قبل ، فإن هذا يعني فقط أننا نقوم بتحديث النقطة النشطة (root,'a',2) remainder الزيادة بدون القيام بأي شيء آخر ، لأن b موجود بالفعل. ومع ذلك ، نلاحظ (في وقت O (1)) أن النقطة النشطة هي الآن في نهاية الحافة. نعكس هذا من خلال إعادة (node1,'\0x',0) . أستخدم هنا node1 للإشارة إلى العقدة الداخلية التي تنتهي بها حافة ab .

بعد ذلك ، في الخطوة # = 9 ، نحتاج إلى إدراج "c" وهذا سيساعدنا على فهم الحيلة النهائية:

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

كما هو الحال دائمًا ، يُلحق التحديث # c تلقائيًا بحواف الأوراق ونذهب إلى النقطة النشطة لمعرفة ما إذا كان بإمكاننا إدراج 'c'. يتضح أن (node1,'c',1) "c" موجود بالفعل عند هذه الحافة ، لذا قمنا بتعيين النقطة النشطة (node1,'c',1) ، remainder الزيادة ولا نقوم بشيء آخر.

الآن في الخطوة # = 10 ، remainder is 4 ، ولذا نحتاج أولاً إلى إدخال abcd (الذي يبقى من 3 خطوات مضت) عن طريق إدخال d في النقطة النشطة.

تؤدي محاولة إدراج d عند النقطة النشطة إلى حدوث انقسام في الحافة في وقت O (1):

تم وضع active_node ، والتي تم بدء التقسيم عليها ، باللون الأحمر أعلاه. هنا القاعدة النهائية ، القاعدة 3:

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

إذاً النقطة النشطة هي الآن (node2,'c',1) ، ووضع علامة node2 باللون الأحمر أدناه:

منذ اكتمال إدخال abcd ، نقوم بتقليل remainder إلى 3 والنظر في اللاحقة المتبقية التالية من الخطوة الحالية ، bcd . حددت القاعدة 3 النقطة النشطة إلى العقدة والحافة اليمنى بحيث يمكن إدخال bcd بمجرد إدخال حرفها النهائي d عند النقطة النشطة.

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

نلاحظ: تتيح لنا روابط لاحقة إعادة ضبط النقطة النشطة حتى يمكننا إدخال الجزء المتبقي التالي في جهد O (1). انظر إلى الرسم البياني أعلاه لتأكيد أن العقدة في العلامة ab ترتبط بالعقدة عند b (لاحقة) ، وترتبط العقدة في abc بـ bc .

الخطوة الحالية لم تنته بعد. remainder الآن 2 ، ونحن بحاجة إلى اتباع القاعدة 3 لإعادة تعيين النقطة النشطة مرة أخرى. نظرًا لأن active_node الحالي (اللون الأحمر أعلاه) لا active_node أي رابط لاحقة ، تتم إعادة تعيين الجذر. النقطة النشطة هي الآن (root,'c',1) .

ومن ثم فإن cabxabcd التالي يحدث عند الحافة الصادرة من العقدة الجذرية التي يبدأ تصنيفها بـ c : cabxabcd ، خلف الحرف الأول ، أي خلف c . هذا يسبب انقسام آخر:

وبما أن هذا ينطوي على إنشاء عقدة داخلية جديدة ، فإننا نتبع القاعدة 2 ونعين وصلة لاحقة جديدة من العقدة الداخلية التي تم إنشاؤها سابقًا:

(أنا أستخدم Graphviz Dot لهذه الرسوم البيانية الصغيرة. تسبب رابط اللاحقة الجديد في إعادة ترتيب الحواف الحالية ، لذا تحقق بعناية للتأكد من أن الشيء الوحيد الذي تم إدراجه أعلاه هو رابط لاحقة جديد).

مع هذا ، يمكن تعيين remainder إلى 1 وحيث أن active_node جذر ، نستخدم القاعدة 1 لتحديث النقطة النشطة إلى (root,'d',0) . هذا يعني أن الإدخال النهائي للخطوة الحالية هو إدخال d واحد على الجذر:

كانت تلك هي الخطوة النهائية وقد انتهينا. هناك عدد من الملاحظات النهائية ، على الرغم من:

  • في كل خطوة ننتقل # إلى الأمام بنسبة 1 موقف. هذا تلقائيا بتحديث كل العقد الورقية في O (1) مرة.

  • لكنه لا يتعامل مع أ) أي لاحقات متبقية من الخطوات السابقة ، و ب) مع الحرف النهائي الوحيد للخطوة الحالية.

  • يخبرنا remainder كم عدد الإضافات الإضافية التي نحتاجها. تتطابق هذه الإدخالات واحد لواحد مع اللواحق النهائية للسلسلة التي تنتهي عند الموضع الحالي # . نعتبر واحدا تلو الآخر ، وجعل إدراج. هام: يتم كل إدخال في وقت O (1) نظرًا لأن النقطة النشطة تخبرنا بالضبط إلى أين نذهب ، ونحتاج إلى إضافة حرف واحد فقط في النقطة النشطة. لماذا ا؟ لأنه يتم تضمين الأحرف الأخرى ضمنيًا (وإلا لن تكون النقطة النشطة مكانها).

  • بعد كل إدراج من هذا النوع ، نقوم بتقليص remainder واتباع ارتباط اللاحقة إذا كان هناك أي رابط. إذا لم نذهب إلى الجذر (القاعدة 3). إذا كنا في الجذر بالفعل ، نقوم بتعديل النقطة النشطة باستخدام القاعدة 1. في أي حال ، يستغرق الأمر وقت O (1) فقط.

  • إذا وجدنا ، خلال أحد هذه الإدخالات ، أن الحرف الذي نرغب في إدراجه موجود بالفعل ، فإننا لا نفعل أي شيء وننهي الخطوة الحالية ، حتى إذا كان remainder > 0. والسبب هو أن أي إدخالات تبقى سوف تكون لاحقة للذي حاولناه فقط. ومن ثم فهي كلها ضمنية في الشجرة الحالية. حقيقة أن remainder > 0 يتأكد من أننا نتعامل مع اللواحق المتبقية في وقت لاحق.

  • ماذا لو كان في نهاية الخوارزمية remainder > 0؟ ستكون هذه الحالة عندما تكون نهاية النص عبارة عن سلسلة فرعية حدثت في مكان ما من قبل. في هذه الحالة ، يجب أن نضيف حرفًا إضافيًا في نهاية السلسلة لم يحدث من قبل. في الأدب ، عادة ما يتم استخدام الدولار $ كرمز لذلك. لماذا هذا مهم؟ -> إذا استخدمنا لاحقًا شجرة اللاحقة المكتملة للبحث عن اللواحق ، يجب أن نقبل المطابقات فقط إذا كانت النهاية في ورقة . وإلا سنحصل على الكثير من التطابقات الزائفة ، لأن هناك العديد من السلاسل المضمنة ضمنيًا في الشجرة التي ليست لاحقات فعلية للسلسلة الرئيسية. إجبار remainder على أن يكون 0 في النهاية هو في الأساس طريقة لضمان أن جميع اللواحق تنتهي عند عقدة أوراق. ومع ذلك ، إذا أردنا استخدام الشجرة للبحث عن سلاسل فرعية عامة ، وليس فقط لواحق السلسلة الرئيسية ، فإن هذه الخطوة النهائية ليست مطلوبة في الواقع ، كما هو مقترح في تعليق OP أدناه.

  • فما هو تعقيد الخوارزمية برمتها؟ إذا كان النص بطول n حرفًا ، فمن الواضح أن n من الخطوات (أو n + 1 إذا أضفنا علامة الدولار). في كل خطوة ، نحن لا نفعل شيئًا (بخلاف تحديث المتغيرات) ، أو نقوم بإدخال remainder ، كل منها يأخذ وقت O (1). بما أن remainder يشير إلى عدد المرات التي لم نفعل فيها شيئًا في الخطوات السابقة ، وهو يتناقص بالنسبة لكل إدخال نقوم به الآن ، فإن إجمالي عدد المرات التي نقوم فيها بشيء ما هو بالضبط n (أو n + 1). وبالتالي ، فإن التعقيد الكلي هو O (n).

  • ومع ذلك ، هناك شيء واحد صغير لم active_length بشكل صحيح: يمكن أن يحدث أننا نتبع ارتباط لاحقة ، active_length النقطة النشطة ، ثم نجد أن مكون active_length الخاص به لا يعمل بشكل جيد مع active_node الجديد. على سبيل المثال ، ضع في اعتبارك موقفًا كالتالي:

(تشير الخطوط المتقطعة إلى بقية الشجرة. إن الخط المنقط هو ارتباط لاحقة.)

الآن دع النقطة النشطة تكون (red,'d',3) ، لذلك يشير إلى المكان خلف f على حافة defg . الآن نفترض أننا قمنا بالتحديثات الضرورية ونتبع الآن وصلة اللاحقة لتحديث النقطة النشطة وفقا للقاعدة 3. النقطة النشطة الجديدة هي (green,'d',3) . ومع ذلك ، فإن d -edge الخروج من العقدة الخضراء هو de ، لذلك فهو يحتوي على حرفين فقط. من أجل العثور على النقطة النشطة الصحيحة ، من الواضح أننا نحتاج إلى اتباع هذه الحافة إلى العقدة الزرقاء وإعادة التعيين إلى (blue,'f',1) .

في حالة سيئة بشكل خاص ، يمكن أن يكون active_length كبيرًا مثل remainder ، والتي يمكن أن تكون كبيرة مثل n. وقد يحدث ذلك جيدًا للعثور على النقطة النشطة الصحيحة ، فنحن لا نحتاج فقط إلى القفز فوق عقدة داخلية واحدة ، ولكن ربما كثيرًا ، حتى n في أسوأ الحالات. هل هذا يعني أن الخوارزمية لها تعقيد خفي O (n 2 ) ، لأنه في كل خطوة remainder يكون O (n) بشكل عام ، وما بعد التعديلات على العقدة النشطة بعد اتباع وصلة لاحقة يمكن أن تكون O (n) أيضًا؟

لا. السبب هو أنه إذا كان علينا بالفعل ضبط النقطة النشطة (على سبيل المثال ، من الأخضر إلى الأزرق على النحو الوارد أعلاه) ، فإن ذلك يقودنا إلى عقدة جديدة لها وصلة لاحقة خاصة بها ، وسيتم تقليل active_length . بينما نتابع سلسلة روابط لاحقة ، active_length الباقية ، يمكن أن active_length فقط ، active_length يمكن أن يكون عدد تعديلات النقطة النشطة التي يمكن أن نجعلها على الطريق أكبر من active_length في أي وقت. وبما أن active_length لا يمكن أبداً أن يكون أكبر من remainder ، remainder هو O (n) ليس فقط في كل خطوة واحدة ، ولكن مجموع مجموع الزيادات التي تمت على remainder خلال العملية بأكملها هو O (n) أيضًا ، كما يتم تقييد تعديلات النقطة النشطة بـ O (n).




Hi i have tried to implement the above explained implementation in ruby , please check it out. it seems to work fine.

the only difference in the implementation is that , i have tried to use the edge object instead of just using symbols.

its also present at https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[[email protected]_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @[email protected]_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry



شكرا لشرح تعليمي بشكل جيد من قبل @ jogojapan ، نفذت الخوارزمية في بايثون.

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

  1. End with Remainder > 0 وتبين أن هذا الموقف يمكن أن يحدث أيضًا أثناء خطوة التكشف ، وليس فقط نهاية الخوارزمية بأكملها. عندما يحدث ذلك ، يمكننا ترك الباقي ، actnode ، actedge ، و actlength دون تغيير ، إنهاء الخطوة الحالية تتكشف ، وبدء خطوة أخرى إما من خلال الحفاظ على طي أو تتكشف اعتمادا على ما إذا كان شار القادم في السلسلة الأصلية في المسار الحالي أو ليس.

  2. نقاط قفزة فوق: عندما نتبع وصلة لاحقة ، قم بتحديث النقطة النشطة ، ثم ابحث عن أن مكون active_length الخاص بها لا يعمل بشكل جيد مع active_node الجديد. يجب أن نتقدم إلى المكان الصحيح لتقسيم ، أو إدراج ورقة. This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node , the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

The other two problems have somehow been pointed out by @managonov

  1. Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly.

  2. Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2 . Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

Finally, my implementation in Python is as follows:

Tips: It includes a naive tree printing function in the code above, which is very important while debugging . It saved me a lot of time and is convenient for locating special cases.




هذا هو حل javascript (مع Mootools) التي من شأنها تقليل حجم الخط لتتناسب مع حدود elHeader.

while (elHeader.clientWidth < elHeader.scrollWidth || elHeader.clientHeight < elHeader.scrollHeight) {
  var f = parseInt(elHeader.getStyle('font-size'), 10);
  f--;
  elHeader.setStyle('font-size', f + 'px');
}

CSS من elHeader:

    width:100%;
    font-size:40px;
    line-height:36px;
    font-family:Arial;
    text-align:center;
    max-height:36px;
    overflow:hidden;

لاحظ أن غلاف elHeader يحدد عرض elHeader.





javascript c# algorithm search suffix-tree