اتحاد المجموعات Union-Find: ممثل المجموعة والدمج بالحجم وضغط المسار

ما الذي تحفظه بنية اتحاد المجموعات؟

نريد تقسيم عناصر معلومة إلى مجموعات لا يشترك عنصر واحد في أكثر من واحدة منها، ثم دمج بعض هذه المجموعات عند وصول علاقات معلنة. تصف وثائق Linux بنية union-find من خلال التهيئة والبحث عن ممثل المجموعة والاتحاد الذي يدمج مجموعتين. سنطبق الفكرة بكود Python أصلي على حروف تعليمية، لا باستدعاء تنفيذ Linux أو التعامل مع بيانات نظام فعلي.

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

ما نحتاجه من البنية سؤال محدد: هل حرفان ضمن المجموعة نفسها بعد عمليات الدمج التي أجريناها؟ لا نطلب منها قائمة الحواف الأصلية أو أقصر طريق أو اتجاه انتقال. هذه أسئلة أخرى تحتاج معلومات مناسبة. يمكن أن نحفظ المجموعة التي وصلت إليها العناصر دون حفظ كل سبب جمعها، ولذلك سنفصل في التجربة بين العلاقات المدخلة وحالة البنية الداخلية.

[1] [2]

سبعة حروف وخمس عمليات دمج ناجحة

نبدأ بالحروف A وB وC وD وE وF وG، وكل منها منفرد. ندخل العلاقات غير الموجهة A مع B، ثم B مع C، ثم D مع E، ثم E مع F. بعد أول علاقتين تكون A وB وC في مجموعة، وبعد الأخريين تكون D وE وF في مجموعة أخرى، بينما G منفرد. عدد المجموعات الآن ثلاثة، لا عدد الحروف ولا عدد العلاقات.

ثم نضيف C مع D، فتصل العلاقة المجموعة الأولى بالثانية. تصبح A وB وC وD وE وF في مجموعة واحدة، وتبقى G في أخرى. عدد المجموعات اثنان. الأعداد والحروف والعلاقات من تأليف المثال؛ لا نمثل بها أشخاصًا أو شبكات اتصال فعلية، ولا نحتاج اكتشاف علاقة مخفية لأن قائمة الروابط معلنة بالكامل.

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

الاتصال داخل المجموعة ليس حافة مباشرة

بعد إدخال A مع B وB مع C، يسأل الكود هل A وC في المجموعة نفسها، فيجيب نعم. لكنه لم يتلق حافة مباشرة A مع C في هذه المرحلة؛ العلاقة بينهما تمر عبر B في الرسم المؤلف. إذا كان سؤال القارئ عن وجود الحافة نفسها، فعليه فحص سجل الحواف الذي حفظناه خارج البنية بدل الاكتفاء بمساواة الممثلين.

وبعد الجسر C مع D، تدخل F في مجموعة A رغم أن الرسم لا يحوي حافة مباشرة بينهما. يمكن أن نكتب مسارًا في بيانات المثال: A ثم B ثم C ثم D ثم E ثم F. هذا المسار يأتي من قائمة العلاقات التي احتفظنا بها للمراجعة. لا يستخرج الكود المعروض ذلك المسار من سلاسل الأب الداخلية، لأنها تمثيل للمجموعات وليس نسخة مطابقة من الرسم.

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

الممثل اسم داخلي قد يتغير

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

في سلسلة A مع B ثم B مع C، يحافظ كودنا على A جذرًا وفق قاعدة الحجم وفك التعادل المعلنة. لكن لو بدأنا B مع A في المجموعة الثنائية، قد يبقى B ممثلًا بدل A. المجموعة النهائية تحوي العنصرين نفسيهما. لذلك لا نستخدم اختلاف اسم الجذر وحده دليلًا أن العضوية تغيرت، ولا نطلب من كل ترتيب عمليات أن يعطي الاسم نفسه.

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

الدمج بالحجم يربط جذرًا بجذر

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

بعد دمج A مع B يصبح حجم جذر A اثنين، وبعد إدخال C في المجموعة يصبح ثلاثة. وفي الجانب الآخر تصير مجموعة D وE وF بحجم ثلاثة. عند استدعاء الاتحاد C مع D، يجد الكود الجذرين A وD بحجمين متساويين، فيبقي A بحسب ترتيب الاستدعاء. الحجم النهائي عند A ستة، وعند G واحد، ومجموعهما سبعة.

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

الحجم يختلف من ارتفاع شجرة الأب

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

وفي تجربة مستقلة، ندمج A مع B، وC مع D، ثم A مع C، وE مع F، ثم A مع E. يصبح F تابعًا لـE الذي يشير إلى A، بينما A جذر مجموعة من ستة أعضاء. سلسلته قبل الفحص F ثم E ثم A. يوضح ذلك فرقًا بين ثلاث هويات في مسار بحث وبين ستة أعضاء في المجموعة التي يصل إليها.

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

ضغط المسار يغير التمثيل دون تقسيم العضوية

نطلب find على F في التجربة المستقلة السابقة. نصل أولًا من F إلى E ثم A، ثم نوجه parent الخاص بالعناصر التي مررنا بها إلى A. يصير F يشير إلى A مباشرةً. لم نخرج F من مجموعة، ولم نضف عنصرًا جديدًا؛ تغير الطريق الداخلي الذي نستخدمه للوصول إلى الممثل نفسه.

يمكن مقارنة الحالة قبل الفحص وبعده: الجذر المعاد A في الاثنين، وعدد المجموعات لم يتغير، وحجم المجموعة ستة. الذي تغير أن سلسلة F الأقرب إلى الجذر قصرت في هذا المثال. لا ننسب تعديل parent إلى حذف حافة F مع E من الرسم الأصلي؛ العلاقة داخل شجرة الأب لم تكن سجلًا مستقلًا لكل حافة تلقيناها.

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

عرض الرسم بالحجم الكامل

اتحاد داخل المجموعة لا ينقص العداد

بعد الجسر C مع D نطلب اتحاد A مع C. يجد find الممثل نفسه للطرفين، فيرجع union القيمة False دون إنقاص عدد المجموعات أو زيادة حجمها. هذه القيمة تعني أن العملية لم تدمج مجموعتين مختلفتين، ولا تعني أن A وC غير متصلين. ينبغي أن يقرأ المستدعي معنى الناتج وفق عقد الدالة بدل تخمينه من كلمة false.

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

إذا أردت تسجيل تكرار حدث أو عدد حواف، احتفظ بعداد أو سجل مستقل. يمكن أن يظهر الرسم الجديد حافة إضافية داخل مكون قائم دون أن تتغير مجموعاته. مثلًا إضافة A مع C إلى الرسم الذي يحوي A مع B وB مع C تضيف حافة لكنها لا تنشئ مجموعة جديدة. نراجع الفرق بين تغير الرسم وتغير التقسيم قبل تفسير القيمة المنطقية المعادة.

كود أصلي بعقد إدخال معلن

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

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

تستعمل union الجذور الناتجة من find، ثم تقارن أحجام الجذور وتحدث الأب والحجم والعدد. وتفحص same مساواة الجذرين. لا توجد في الصنف قائمة حواف أو مسار مصدر، ولذلك لا نصف ناتجه بأنه يحتفظ بالرسم كاملًا. يمكن للمستدعي تخزين العلاقات خارج الصنف إذا كانت المراجعة تحتاج أسباب الاتصال أو حذفًا لاحقًا.

class MergeGroups:
    def __init__(self, labels):
        self.parent = {}
        self.size = {}
        for label in labels:
            if label in self.parent:
                raise ValueError("duplicate label")
            self.parent[label] = label
            self.size[label] = 1
        self.components = len(self.parent)

    def find(self, label):
        root = label
        while self.parent[root] != root:
            root = self.parent[root]
        while label != root:
            previous = self.parent[label]
            self.parent[label] = root
            label = previous
        return root

    def union(self, first, second):
        a, b = self.find(first), self.find(second)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size.pop(b)
        self.components -= 1
        return True

    def same(self, first, second):
        return self.find(first) == self.find(second)

حذف علاقة يحتاج معلومات لم نخزنها

لنحذف الجسر C مع D من قائمة العلاقات الأصلية، مع إبقاء A مع B وB مع C وD مع E وE مع F. الرسم المعدل يحتوي ثلاث مجموعات: A وB وC، ثم D وE وF، ثم G. لكن الكائن الذي سبق أن دمج المجموعتين عبر الجسر ما زال يحتفظ باتحادهما إذا لم نعد بناءه؛ إزالة الزوج من قائمة خارجية لا تفصل جذوره تلقائيًا.

في مثالنا المحدود نستطيع إنشاء كائن جديد من الحروف نفسها وإعادة إدخال العلاقات الباقية، ثم مقارنة النتيجة بالقديمة. هذه إعادة بناء صريحة من سجل نعرفه، لا عملية تراجع موجودة داخل union. لو لم نحفظ سجل العلاقات، فلن يخبرنا جدول parent وحده أي حافة بعينها كانت سبب الاتصال أو هل بقي طريق آخر بعد حذفها.

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

العلاقات الموجهة ليست هذا السؤال

نعلن جميع روابط مثالنا غير موجهة، ولذلك الانتماء للمجموعة نفسها متناظر. إذا كان A وF في المجموعة ذاتها، فإن F وA فيها أيضًا. هذا لا يخبرنا أن اتجاه انتقال من F إلى A مسموح في نظام له حواف موجهة؛ الاتجاه لم يدخل في عمليات الدمج التي استعملناها.

في تجربة صغيرة من سهم A إلى B وسهم B إلى C، يوجد مسار موجه من A إلى C ولا يوجد في هذا الرسم مسار من C إلى A. لو دمجنا طرفي كل سهم دون اتجاه، يصبح الثلاثة في مجموعة واحدة وتجيب same نعم في الاتجاهين. الناتج وصف لتجاهل الاتجاه، ولا يصلح وحده لاختبار الوصول الموجه الذي يفرق الحالتين.

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

فحوص تحفظ التغطية والأحجام

بعد كل اتحاد ناجح نراجع عدد الجذور، ونجمع أحجامها فيكون المجموع سبعة في مثالنا. يجب أن يصل كل حرف إلى جذر موجود يشير إلى نفسه، وأن يظهر في مجموعة واحدة عند جمع الحروف بحسب find. لا يكفي أن تتوافق إجابة A مع F وحدها؛ فقد يخطئ تنفيذ في عداد G أو حجم مجموعة أخرى دون أن تتغير تلك الإجابة.

نراجع أيضًا أن عدد الجذور يساوي components، وأن مفاتيح size هي الجذور الحالية، وأن كل حجم يساوي عدد الحروف التي تصل إلى جذره. ثم نكرر اتحادًا داخل مجموعة ونراجع ثبات العدد والحجم، ونجرب unknown لنتأكد أنه لم ينشئ حرفًا جديدًا. ونفحص التهيئة الفارغة فعدد مجموعاتها صفر، والمفردة فعددها واحد.

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

مرجع مستقل يعتمد المرور على الرسم

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

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

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

بطاقة نتيجة تفصل التقسيم من أسبابه

يمكن وصف النتيجة بعد الجسر ببطاقة واضحة: سبع هويات، علاقات غير موجهة معلنة، خمس عمليات دمج ناجحة، مجموعتان بحجم ستة وواحد، وحروف المجموعة الكبيرة A إلى F. نكتب أن الممثل الداخلي في ترتيبنا A، وأن G منفرد، وأن parent ليس سجل الحواف الأصلية. بهذه الحقول لا يتحول الاسم الداخلي إلى سبب اتصال مزعوم.

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

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