استخدام Rabin-Karp للبحث عن أنماط متعددة في سلسلة

Question

بحسب ال دخول ويكيبيديا في خوارزمية مطابقة سلسلة Rabin-Karp، يمكن استخدامه للبحث عن عدة أنماط مختلفة في سلسلة في نفس الوقت مع الحفاظ على التعقيد الخطي.من الواضح أن هذا يتم بسهولة عندما تكون جميع الأنماط بنفس الطول، لكنني ما زلت لا أفهم كيف يمكننا الحفاظ على تعقيد O(n) عند البحث عن أنماط ذات أطوال مختلفة في وقت واحد.يمكن للشخص يرجى تسليط بعض الضوء على هذا؟

تحرير (ديسمبر 2011):

تم تحديث مقالة ويكيبيديا منذ ذلك الحين ولم تعد تدعي أنها تطابق أنماطًا متعددة ذات أطوال مختلفة في O(n).

Answer 1

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

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

وبطبيعة الحال، يجب علينا أن نختار m للحصول على الحد الأقصى لطول السلسلة من مجموعة السلاسل.

تحديث: من ويكيبيديا،

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

نحن نحسب حاضِر التجزئة في m خطوات.في كل خطوة هناك مؤقت قيمة التجزئة التي يمكننا البحث عنها (O(1) التعقيد) في مجموعة التجزئة.جميع التجزئة سيكون لها نفس الحجم، أي 32 بت.

التحديث 2: التعقيد الزمني المطفأ (المتوسط) O(n)؟

أعلاه قلت ذلك m يجب أن يكون الحد الأقصى لطول السلسلة.اتضح أنه يمكننا استغلال العكس.
مع التجزئة لتحويل البحث عن سلسلة فرعية وثابت m الحجم يمكننا تحقيق تعقيد O(n).

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

ستعمل هذه التقنية على زيادة الإنذارات الكاذبة ولكن في المتوسط ​​لها تعقيد زمني O(n).

Answer 2

ذلك لأن قيم التجزئة لدراسات السابعة مرتبطة رياضيا. حساب التجزئة H (S، J) (تجزئة الأحرف التي تبدأ من موقع سلسلة JTH س) يأخذ س (م) الوقت على سلسلة من الطول م. وبعد ولكن بمجرد أن يكون لديك ذلك، الحوسبة H (S، J + 1) يمكن القيام به في وقت ثابت، ل H (S، J + 1) يمكن التعبير عنها كدالة H (S، J).

o (m) + o (1) => o (m), ، أي الوقت الخطي.

إليك رابط حيث يتم وصف هذا بمزيد من التفاصيل (انظر على سبيل المثال القسم "ما الذي يجعل Rabin-Karp سريعا؟")