ما خوارزمية يمكنك استخدامها للعثور على تكرار العبارات في سلسلة ؟

Question

نظرا التعسفي السلسلة ، ما هو وسيلة فعالة في العثور على تكرار العبارات ؟ يمكننا القول أن العبارات يجب أن تكون أطول من مدة معينة ليتم تضمينها.

من الناحية المثالية, كنت في نهاية المطاف مع عدد تكرارات لكل عبارة.

Answer 1

مثل في وقت سابق من الناس ذكر أن لاحقة الشجرة هو أفضل وسيلة للحصول على الوظيفة.موقعي المفضل بالنسبة لاحقة الأشجار http://www.allisons.org/ll/AlgDS/Tree/Suffix/.يعدد جميع أنيق يستخدم من لاحقة الأشجار على صفحة واحدة و اختبار js تطبيق مضمن إلى اختبار سلاسل والعمل من خلال الأمثلة.

Answer 2

في نظرية

• A لاحقة مجموعة هو 'أفضل' الجواب لأنه يمكن أن تنفذ إلى استخدام الفضاء الخطي و الوقت للكشف عن أي تكرار سلاسل فرعية.ومع ذلك - ساذجة تنفيذ في الواقع يستغرق وقتا O(n^2 log n) نوع من اللواحق و ليس واضحا تماما كيف للحد من هذه إلى O(n log n) ، ناهيك O(n) ، على الرغم من أن يمكنك قراءة الأوراق ذات الصلة إذا كنت ترغب في.
• A لاحقة شجرة يمكن أن يستغرق أكثر قليلا من الذاكرة (لا يزال الخطية ، على الرغم من) من لاحقة مجموعة ، ولكن من الأسهل لتنفيذ لبناء بسرعة حيث يمكنك استخدام ما يشبه الجذر نوع الفكرة كما يمكنك إضافة أشياء إلى شجرة (انظر ويكيبيديا الرابط من اسم لمزيد من التفاصيل).
• على KMP الخوارزمية هو أيضا جيد أن تكون على علم ، وهي متخصصة للبحث عن معين فرعية ضمن أطول سلسلة بسرعة جدا.إذا كنت بحاجة فقط هذه الحالة الخاصة, مجرد استخدام KMP و لا تحتاج إلى عناء بناء فهرس يكفي الأولى.

في الممارسة العملية

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

في هذه الحالة, قد تحتاج فقط إلى القيام سريعة ن-غرام تحليل لبعض الصغيرة n, مثل n=2 أو 3.على سبيل المثال ، يمكنك tokenize المستند إلى قائمة من الكلمات من قبل تجريد من علامات الترقيم ، الرسملة ، ووقف الكلمات (تشغيل يعمل على حد سواء - > "تشغيل") لزيادة الدلالي المباريات.ثم بناء تجزئة الخريطة (مثل hash_map في C++ ، القاموس في بيثون ، الخ) من كل المجاورة زوج من الكلمات إلى عدد من الحوادث حتى الآن.في النهاية يمكنك الحصول على بعض البيانات المفيدة التي كان سريع جدا إلى رمز و لا مجنون بطء تشغيل.

Answer 3

لاحقة الأشجار هي وسيلة جيدة لتنفيذ هذا.الجزء السفلي من هذه المادة روابط التطبيقات في لغات مختلفة.

Answer 4

مثل jmah قال ، يمكنك استخدام لاحقة الأشجار/لاحقة المصفوفات هذا.

هناك وصف خوارزمية يمكن استخدام هنا (انظر القسم 3.1).

يمكنك أن تجد أكثر في عمق الوصف في الكتاب يستشهدون (Gusfield, 1997) ، وهو في كتب google.

Answer 5

افترض أنك تعطى فرز مجموعة A n مداخل (i=1,2,3,...,n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

هذا algo يعمل في O(n) مرة.