اكتشف ما إذا كانت الشجرة عبارة عن شجرة فرعية لأخرى

Question

توجد شجرتان ثنائيتان T1 وT2 تقومان بتخزين بيانات الأحرف، ويُسمح بالتكرارات.
كيف يمكنني معرفة ما إذا كانت T2 عبارة عن شجرة فرعية من T1؟.
يحتوي T1 على ملايين العقد بينما يحتوي T2 على مئات العقد.

Answer 1

وترافيرس T1. إذا كانت العقدة الحالية تساوي عقدة الجذر من T2، اجتياز كل من أشجار (T2 والشجرة الفرعية الحالية T1) في نفس الوقت. مقارنة العقدة الحالية. إذا هم دائما على قدم المساواة، T2 هو شجرة فرعية من T1.

Answer 2

وأقترح خوارزمية، يستخدم تجهيزها:

1) ما قبل عملية الشجرة T1، والحفاظ على قائمة بجميع جذور الشجرة الفرعية الممكنة (قائمة مخبأ سيكون له الملايين من مقالات)؛

2) فرز القائمة مؤقتا من الجذور من قبل الترتيب التنازلي للبيانات، وأبقى في الجذر. يمكنك اختيار وظيفة الفرز أكثر أناقة، على سبيل المثال، تحليل شجرة حرف في السلسلة.

و3) استخدام البحث الثنائي لتحديد ما يلزم من دون شجرة. تستطيع رفض بسرعة الأشجار الفرعية، مع عدد من العقد، وليس مساويا لعدد T2 من العقد (أو مع عمق مختلف).

لاحظ أن الخطوات من 1) ويجب 2) أن يتم مرة واحدة فقط، ثم يمكنك اختبار العديد من المرشحين دون شجرة، وذلك باستخدام نتيجة preprocessed نفسها.

Answer 3

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

إذا كنت تعرف عمق كل عقدة واحدة من T1 (من ورقة إلى عقدة)، هل يمكن تخطي أي العقد التي هي ليست عميقة مثل الشجرة كنت تبحث عنه. هذا يمكن أن تساعدك على القضاء على الكثير من المقارنات التي لا داعي لها. القول بأن T1 وT2 تكون متوازنة بشكل جيد، ثم شجرة T1 سيكون له عمق إجمالي قدره 20 (2**20> 1,000,000)، وسوف شجرة T2 يكون عمق 7 (2**7> 100). سيكون لديك لمجرد المشي 13 الأولى <م> الطبقات من T1 (8192 العقد - أو هو أن 14 طبقات و16384 العقد)، وسوف تكون قادرة على تخطي حوالي 90٪ من T1 ...

ولكن، إذا كان عن طريق <م> الشجرة تقصد أن العقد رقة من T2 أيضا رقة العقد من T1، ثم هل يمكن أن تفعل اجتياز الأول من T1 وحساب عمق كل عقدة (المسافة من ورقة ل عقدة) ثم تحقق سوى الأشجار الفرعية والتي لها نفس العمق كما T2.

Answer 4

إذا كنت الذاكرة / التخزين ملزمة (أي لا يمكن التلاعب قبل وتخزين الأشجار في أشكال بديلة)، وربما لن تكون قادرة على فعل أي شيء أفضل من بحث شامل اقترح بعض الإجابات الأخرى (اجتياز P1 تبحث عن مطابقة الجذرية للP2، اجتياز حد سواء لتحديد ما إذا كانت العقدة هي في الواقع جذر مطابقة شبه شجرة، تواصل مع اجتياز الأصلي إذا لم تكن مباراة). هذا البحث يعمل في O (ن * م) حيث n هو حجم P1 و m هو حجم P2. مع الشيكات عمق وغيرها من التحسينات المحتملة اعتمادا على البيانات شجرة المتاحة لديك، وهذا الرجل أن يكون الأمثل قليلا، لكنه ما زال عموما O (ن * م). اعتمادا على الظروف الخاصة بك، قد يكون هذا النهج المنطقي الوحيد.

إذا كنت لا ذاكرة / تخزين ملزمة ولا مانع قليلا من التعقيد، وأعتقد أن هذا يمكن أن تحسن إلى O (ن + م) عن طريق خفض ل<لأ href = "HTTP: // داخلي. wikipedia.org/wiki/Longest_common_substring_problem "يختلط =" نوفولو noreferrer "> فرعية أطول المشتركة مشكلة مع مساعدة من <لأ href =" http://en.wikipedia.org/wiki/Generalised_suffix_tree "يختلط =" نوفولو noreferrer "> احقة المعمم شجرة . بعض المناقشات حول هذا لمشكلة مماثلة يمكن العثور على هنا . ربما عندما يكون لدي المزيد من الوقت، وأنا سوف أعود وتعديل مع المزيد من التفاصيل على التنفيذ.

Answer 5

إذا أعطيت جذور كل من الأشجار، ونظرا إلى أن العقد هي من نفس النوع، لماذا فقط ثم التأكد من أن جذور T2 في T1 لا يكفي؟

وأنا على افتراض أن "إعطاء T شجرة" يعني إعطاء مؤشر إلى جذر T ونوع البيانات من العقدة.

والتحيات.

Answer 6

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

1. قم بإجراء جولة ما بعد الطلب في الشجرة 1 والشجرة 2، وأطلق عليها اسم P1 وP2.
2. قارن بين P1 وP2.إذا كانوا مختلفين.الشجرة ليست شجرة فرعية.مخرج.
3. إذا كانت هي نفسها، أو P1 الواردة في P2.يمكنك أن تقرر أي شجرة فرعية.

Answer 7

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

وانت تعطي أشجار T1 و T2، مؤشرات، وليس القيم.

إذا عقدة T2 (وهو مؤشر)، موجود في شجرة T1.

وثم T2 شجرة هي شجرة فرعية من T1.

---

وتحرير:

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

وبعد هذا العمل متعود.

وليس لدينا أي خيار آخر سوى الذهاب للحلول نوقشت هنا.

Answer 8

ودعونا نقول لدينا T1 كما الشجرة الأم وT2 مثل شجرة التي قد تكون شجرة فرعية من T1. القيام بما يلي. الافتراض الوارد هو T1 و T2 نشعر شجرة ثنائية دون أي عامل توازن.

1) البحث في جذور T2 في T1. إذا لم يتم العثور T2 ليس الشجرة الفرعية. سيتم البحث في عنصر في BT اتخاذ O (ن) وقت.

2) إذا تم العثور على العنصر، لا قبل النظام اجتياز T1 من عنصر عقدة الجذر من T2 يتم العثور عليها. وهذا سوف يستغرق س (ن) وقت. هل قبل النظام اجتياز T2 أيضا. سيستغرق O (ن) وقت. نتيجة لمرحلة ما قبل النظام اجتياز يمكن تخزينها في كومة. سوف الإدراج في كومة يستغرق سوى O (1).

و3) إذا كان حجم اثنين من مداخن ليست على قدم المساواة، T2 ليس الشجرة الفرعية.

و4) بوب عنصر واحد من كل كومة والتحقق من وجود المساواة. إذا حدث عدم توافق، T2 ليس الشجرة الفرعية.

و5) إذا كان كل elments الملائمة T2 هو الشجرة الفرعية.

Answer 9

أفترض أن شجرتك هي أشجار غير قابلة للتغيير لذلك لا تقوم أبدًا بتغيير أي شجرة فرعية (لا تفعل ذلك set-car! في لغة المخطط)، ولكنك تقوم فقط ببناء أشجار جديدة من الأوراق أو من الأشجار الموجودة.

ثم أنصح بذلك تبقي في كل عقدة (أو الشجرة الفرعية) رمز التجزئة من تلك العقدة.في لغة C، قم بتعريف الشجرة

 struct tree_st {
   const unsigned hash;
   const bool isleaf;
   union {
     const char*leafstring; // when isleaf is true
     struct { // when isleaf is false
        const struct tree_st* left;
        const struct tree_st* right;
     };
   };
 };

ثم قم بحساب التجزئة في وقت الإنشاء، وعند مقارنة العقد من أجل المساواة، قم أولاً بمقارنة التجزئة من أجل المساواة؛في معظم الأحيان، سيكون رمز التجزئة مختلفًا (ولن تكلف نفسك عناء مقارنة المحتوى).

فيما يلي وظيفة بناء الأوراق المحتملة:

struct tree_st* make_leaf (const char*string) {
   assert (string != NULL);
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   t->hash = hash_of_string(string);
   t->isleaf = true;
   t->leafstring = string;
   return t;
}

وظيفة حساب رمز التجزئة هي

unsigned tree_hash(const struct tree_st *t) {
  return (t==NULL)?0:t->hash;
}

وظيفة بناء عقدة من شجرتين فرعيتين sleft & sright يكون

struct tree_st*make_node (const struct tree_st* sleft,
                          const struct tree_st* sright) {
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   /// some hashing composition, e.g.
   unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
   t->hash = h;
   t->left = sleft;
   t->right = sright;
   return t;
 }

دالة المقارنة (لشجرتين tx & ty) استفد من أنه إذا كانت رموز التجزئة مختلفة فإن المقارنة تكون مختلفة

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
  if (tx==ty) return true;
  if (tree_hash(tx) != tree_hash(ty)) return false;
  if (!tx || !ty) return false;
  if (tx->isleaf != ty->isleaf) return false;
  if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
  else return equal_tree(tx->left, ty->left) 
              && equal_tree(tx->right, ty->right); 

}

في معظم الأحيان tree_hash(tx) != tree_hash(ty) سينجح الاختبار ولن تضطر إلى التكرار.

أقرأ عن سلبيات التجزئة.

بمجرد حصولك على مثل هذا النوع الفعال من التجزئة equal_tree يمكنك استخدام التقنيات المذكورة في الإجابات الأخرى (أو في الكتيبات).

Answer 10

إحدى الطرق البسيطة هي كتابة طريقة is_equal() للشجرة والقيام بما يلي،

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}

لاحظ أنه يمكن تحسين is_equal() باستخدام رمز التجزئة للشجرة.يمكن القيام بذلك بطريقة بسيطة عن طريق أخذ ارتفاع الشجرة أو عدد الأطفال أو نطاق القيم كرمز تجزئة.

bool is_equal(TNode*other) {
    if(x != other->x) return false;
    if(height != other->height) return false;
    if(nchildren != other->nchildren) return false;
    if(hashcode() != other->hashcode()) return false;
    // do other checking for example check if the children are equal ..
}

عندما تكون الشجرة مشابهة لقائمة مرتبطة، فسوف يستغرق الأمر وقتًا O(n).يمكننا أيضًا استخدام بعض الأساليب الإرشادية أثناء اختيار الأطفال للمقارنة.

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    if(is_equal(other)) return true;
    if(left == NULL || right == NULL) {
          return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
    }
    if(left->nchildren < right->nchildren) { // find in smaller child tree first
          return (left->contains_subtree(other)) || right->contains_subtree(other);
    } else {
          return (right->contains_subtree(other)) || left->contains_subtree(other);
    }
}

هناك طريقة أخرى وهي إجراء تسلسل لكلا الشجرتين كسلسلة ومعرفة ما إذا كانت السلسلة الثانية (متسلسلة من T2) هي سلسلة فرعية من السلسلة الأولى (متسلسلة من T1).

الكود التالي يتسلسل في الطلب المسبق.

   void serialize(ostream&strm) {
            strm << x << '(';
            if(left)
                    left->serialize(strm);
            strm << ',';
            if(right)
                    right->serialize(strm);
            strm << ')';
    }

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

مرة أخرى، يمكن ضغط السلسلة بكفاءة باستخدام Burrows–Wheeler_transform.ومن الممكن أن com.bzgrep للبحث عن سلسلة فرعية في البيانات المضغوطة.

هناك طريقة أخرى وهي فرز الأشجار الفرعية في الشجرة حسب الطول وعدد الأطفال.

bool compare(TNode*other) {
    if(height != other->height)
        return height < other->height;

    return nchildren < other->nchildren;
}

لاحظ أنه سيكون هناك أشجار فرعية O(n^2).لتقليل العدد يمكننا استخدام بعض النطاق بناءً على الارتفاع.على سبيل المثال، يمكننا أن نهتم فقط بالأشجار الفرعية التي يتراوح ارتفاعها من 1000 إلى 1500.

عندما يتم إنشاء البيانات التي تم فرزها، من الممكن إجراء بحث ثنائي فيها ومعرفة ما إذا كانت مجموعة فرعية في وقت O(lg n) (مع الأخذ في الاعتبار عدم وجود تكرار في البيانات التي تم فرزها).