كيفية تسريع حساب طول أطول فرعية شائعة؟

Question

لدي اثنين سلاسل كبيرة جدا وأنا أحاول معرفة ذلك أطول فرعية شائعة.

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

باستخدام البرمجة الديناميكية

المشكلة هي أن طريقة البرمجة الديناميكية لها وقت تشغيل كبير (التعقيد O(n*m), ، أين n و m هي أطوال السلاسل).

ما أريد أن أعرفه (قبل القفز لتنفيذ أشجار لاحقة): هل من الممكن تسريع الخوارزمية إذا كنت أرغب فقط في معرفة طول السلسلة الفرعية المشتركة (وليس السلسلة المشتركة نفسها)؟

Answer 1

هل سيكون أسرع في الممارسة؟ نعم. هل سيكون أسرع فيما يتعلق ببيج-أوه؟ لا. إن حل البرمجة الديناميكي هو دائمًا O (n*m).

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

حظا طيبا وفقك الله :)

Answer 2

هذه ستجعلها تعمل بشكل أسرع ، على الرغم من أنها ستظل كذلك O(nm).

التحسين الوحيد في الفضاء (والذي قد يوفر لك وقت تخصيص صغير) هو ملاحظة ذلك LCSuff يعتمد فقط على الصف السابق - لذلك إذا كنت تهتم فقط بالطول ، يمكنك تحسين O(nm) الفضاء وصولاً إلى O(min(n,m)).

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

Answer 3

فيما يلي خوارزمية بسيطة يمكن أن تنتهي في سجل O (M+N)*(M+N)) ، وأسهل بكثير في التنفيذ مقارنة بخوارزمية شجرة اللاحقة التي هي وقت تشغيل O (M+N).

لنبدأ بطول دقيقة مشتركة (minl) = 0 ، وطول الحد الأقصى الشائع (maxl) = min (m+n) +1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

المشكلة المتبقية هي كيفية تجزئة كل سلسلة من الطول L في الوقت O (N). يمكنك استخدام صيغة متعددة الحدود على النحو التالي:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

خوارزمية ناقلات Myer Bit يستطيع مساعدتك. إنه يعمل باستخدام معالجة بت وهو نهج أسرع بكثير.