مصفوفة لاحقة كاملة

Question

ستقوم مصفوفة اللواحق بفهرسة جميع اللواحق لقائمة سلاسل معينة ، ولكن ماذا لو كنت تحاول فهرسة كل السلاسل الفرعية الفريدة الممكنة؟أنا جديد قليلاً في هذا الأمر ، لذا إليك مثال على ما أعنيه:

إعطاء السلسلة Genacodicetagpre

فهارس مصفوفة لاحقة (على الأقل حسب فهمي) Genacodicetagpre

أود فهرسة (كل السلاسل الفرعية) Genacodicetagpre

هل مصفوفة لاحقة ما أبحث عنه؟إذا كان الأمر كذلك ، فماذا أفعل لفهرسة جميع السلاسل الفرعية؟إذا لم يكن كذلك ، فأين أبحث؟ما الذي سأبحث عنه أيضًا لمقارنة "كل السلاسل الفرعية" مقابل "سلاسل اللاحقة"؟

Answer 1

صفيف لاحقة يفعل ما تحتاجه بالفعل، لأن كل فرعية هي بادئة واحدة من اللواحق. على وجه التحديد، بالنظر إلى صفيف لاحقة

abcd BCD. CD. د

ويفترض أنك تبحث عن فرعية "BC"، ثم يمكنك العثور على أنه من خلال البحث عن جميع اللواحق التي تبدأ ب "BC" (هناك واحد فقط في هذه الحالة، "BCD"). نظرا لأن صفيف لاحقة يتم فرزها معجميا، فإن العثور على جميع اللواحق التي تشارك بادئة معينة تتوافق مع بحث ثنائي عبر صفيف لاحقة، وسوف تكون النتيجة مجموعة واحدة مستمرة من مداخل صفيف لاحقة.

ومع ذلك، هناك طرق بحث محسنة تستخدم صفيف لاحقة جنبا إلى جنب مع هياكل البيانات المساعدة، مثل صفيف LCP (أطول البادئة المشتركة)، أو أشجار المويجات. انظر مسح Navarro لعام 2007 للحصول على وصف لهذه الطرق (DOI 10.1145 / 1216370.1216372).

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

لأنه، على سبيل المثال، تمثل أول لاحقة "ABCD" السلاح الأربعة "A"، "AB"، "ABC"، "ABCD". ومع ذلك، في مثال أكثر تعقيدا، قل لسلسلة "ABCABXDABE"، فإن أول إدخادين من صفيف لاحقة سيكون giveacodicetagpre.

لأن الإدخال الثاني يمثل السلاحيات "A"، "AB" و "ABE"، ولكن "A" و "AB" تمثل أيضا الإدخال الأول.

كيفية حساب عدد Substings تمثل إدخال؟ -> طول اللاحقة ناقص طول أطول بادئة لها مشترك مع اللاحقة السابقة. على سبيل المثال في مثال "ABE"، هذا هو 3 (طوله) ناقص 2 (طول "AB"، أطول تقاسم تكنولوجيا المعلومات الأطول مع الإدخال السابق). لذلك يمكن إنشاء هذه الأرقام في مرحلة واحدة على صفيف لاحقة، وحتى أسرع إذا قمت أيضا بتوجيه صفيف LCP (أطول البادئة).

ستكون الخطوة التالية لتوليد التهم المتراكمة: giveacodicetagpre.

ثم لإيجاد طريقة فعالة للاستفادة من التهم المتراكمة. على سبيل المثال إذا كنت ترغب في الحصول على السلسلة الفرعية الثالثة عشرة بسعر معجميا، فمن الضروري أن تجد الإدخال الأول الذي يحتوي على عدد متراكم أكبر من أو يساوي 13. سيكون ذلك "16 AbxDabe" أعلاه. ثم قم بإزالة أسهم IEMIX IT مع الإدخال السابق (عوائد "XDABE")، ثم اقفز إلى الموضع بعد الحرف الثاني (لأن الإدخال السابق قد تراكمت عدد 11، و 13-11== 2)، لذلك تحصل " ABXD "باعتبارها فرعية 13th معجميا.

Answer 2

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

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

Answer 3

يجب استخدام صيغة مختلفة لـ "Trie".بشكل أساسي ، إذا كان لديك ABCD ، فقم بإنشاء شجرة عبارة عن دمج للمسارات: الجذر-> A-> B-> C-> D ، الجذر-> B-> C-> D ، الجذر-> C-> D والجذر-> د.الآن ، في كل عقدة ، احتفظ بقائمة بالمواقع التي تمت فيها ملاحظة جذر السلسلة -> .-> .-> العقدة.