شجرة الاندماج

في علم الحاسوب ، تُعدّ شجرة الاندماج نوعًا من هياكل بيانات الأشجار التي تُنفّذ مصفوفة ترابطية على أعداد صحيحة مكونة من $w بت في فضاء محدود، حيث يكون حجم كل عدد صحيح مُدخل أقل من$ ^2w ويكون غير سالب. عند العمل على مجموعة من $n$ زوجًا من المفاتيح والقيم ، فإنها تستخدم مساحة $O (n)$ وتُجري عمليات البحث في زمن $O (log wn) ،$ وهو أسرع تقاربًا من شجرة البحث الثنائية التقليدية ذاتية التوازن ، وأفضل أيضًا من ^شجرة فان إمده بواس للقيم الكبيرة لـ $w$ . وتحقق هذه السرعة باستخدام عمليات زمنية ثابتة يمكن إجراؤها على كلمة الآلة . ابتكر أشجار الاندماج مايكل فريدمان ودان ويلارد عام 1990. ^[¹ ]

لقد تحققت عدة تطورات منذ ورقة فريدمان وويلارد الأصلية عام 1990. ففي عام 1999 ^{[ 2 ]} ، تم توضيح كيفية تطبيق أشجار الدمج ضمن نموذج حسابي تنتمي فيه جميع العمليات الأساسية للخوارزمية إلى AC0 ^، وهو نموذج لتعقيد الدوائر يسمح بعمليات الجمع والعمليات المنطقية الثنائية، ولكنه لا يسمح بعمليات الضرب المستخدمة في خوارزمية شجرة الدمج الأصلية. وفي عام 1996 ^[³^] ، تم اقتراح نسخة ديناميكية من أشجار الدمج باستخدام جداول التجزئة ، والتي تطابقت مع زمن التشغيل المتوقع للبنية الأصلية $O$ $(log$ $w$ $n$ $) . وفي عام 2007$ ^[⁴^]، تم اقتراح نسخة ديناميكية أخرى باستخدام الشجرة الأسية ، والتي تُنتج أزمنة تشغيل في أسوأ الحالات تبلغ $O$ $(log$ $w$ $n$ $+ log log$ $n$ $)$ لكل عملية. وأخيرًا، تم إثبات أن أشجار الدمج الديناميكية يمكنها تنفيذ كل عملية في زمن $O$ $(log$ $w$ $n$ $)$ بشكل حتمي. ^[⁵^]

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

كيف يعمل؟

شجرة الدمج هي في الأساس شجرة B بمعامل تفرع $w 1/5$ (يمكن استخدام أي أس صغير لأنه لن يؤثر بشكل كبير على ارتفاع الشجرة)، مما يعطيها ارتفاعًا قدره $O (log w n)$ . ولتحقيق أوقات التشغيل المطلوبة للتحديثات والاستعلامات، يجب أن تكون شجرة الدمج قادرة على البحث في عقدة تحتوي على ما يصل إلى $w 1/5$ مفتاحًا في وقت ثابت. ويتم ذلك عن طريق ضغط المفاتيح ("رسمها") بحيث يمكن وضعها جميعًا في كلمة واحدة من كلمات الآلة، مما يسمح بدوره بإجراء المقارنات بالتوازي. لذا، فإن سلسلة من العمليات الحسابية التي تتضمن الرسم والمقارنة المتوازية ومحدد موقع فهرس البت الأكثر أهمية، تساعد في الوصول إلى الحل المطلوب.

الرسم التخطيطي

التخطيط هو أسلوب يتم من خلاله ضغط كل مفتاح مكون $من w$ بت في عقدة تحتوي على $k مفتاحًا إلى$ $k - 1$ بت فقط. يمكن اعتبار كل مفتاح $x مسارًا في الشجرة الثنائية الكاملة ذات الارتفاع$ $w،$ يبدأ من الجذر وينتهي عند الورقة المقابلة لـ $x$ . يمكن معالجة هذا المسار بالبحث بشكل متكرر في الابن الأيسر للعقدة i إذا كان البت i يساوي 0، وفي الابن الأيمن إذا كان يساوي 1، بشكل عام، حتى يتم مسح جميع البتات. لتمييز مسارين، يكفي النظر إلى نقطة تفرعهما (أول بت يختلف فيه أي مفتاحين). بما أن الحد الأقصى للمفاتيح هو k ، فلن يكون هناك أكثر من k - 1 نقطة تفرع، مما يعني أنه لا يلزم أكثر من k - 1 بت لتحديد مفتاح. وبالتالي، لن يحتوي أي تخطيط على أكثر من k - 1 بت.

من الخصائص المهمة لدالة الرسم التخطيطي أنها تحافظ على ترتيب المفاتيح. أي أن $sketch(x) < sketch(y)$ لأي مفتاحين $x < y$ . لذا، بالنسبة لنطاق المفاتيح الكامل، فإن sketch(x0 ₎ < sketch(x1 ₎ < ... < sketch( _xk-1 ) لأنه إذا تم اتباع المسار الشبيه بالشجرة الثنائية، فسيتم ترتيب العقد بطريقة x0 _< x1 _< ... < _xk-1 .

تقريب الرسم التخطيطي

إذا كانت مواقع بتات الرسم التخطيطي هي _b1< _b2< ... < br ، _فإن رسم المفتاح xw _-₁ ... x1x0 هو عدد _صحيحمكون _منr بت $x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}$ .

باستخدام عمليات الكلمات القياسية فقط، كتلك المستخدمة في لغة البرمجة C ، يصعب حساب الرسم التخطيطي المثالي للمفتاح مباشرةً في وقت ثابت. بدلاً من ذلك، يمكن تجميع بتات الرسم التخطيطي في نطاق لا يتجاوز حجمه r ≥ ⁴ ، باستخدام عملية AND المنطقية والضرب، وهو ما يُسمى الرسم التخطيطي التقريبي، الذي يحتوي على جميع البتات المهمة، بالإضافة إلى بعض البتات الإضافية غير الضرورية موزعة بنمط يمكن التنبؤ به. تعمل عملية AND المنطقية كقناع لإزالة جميع هذه البتات غير التخطيطية من المفتاح، بينما ينقل الضرب بتات الرسم التخطيطي إلى نطاق صغير. ومثل الرسم التخطيطي "المثالي"، يحافظ الرسم التخطيطي التقريبي أيضًا على ترتيب المفاتيح، مما يعني أن sketch(x₀ ₎ < sketch(x₁ ₎ < ... < sketch( _xₖ₋₁ ).

يلزم إجراء بعض المعالجة المسبقة لتحديد ثابت الضرب الصحيح. سيتم إزاحة كل بت من بتات الرسم التخطيطي في الموقع b _i إلى b _i + m _i من خلال عملية ضرب في m = $\textstyle \sum _{i=1}^{r}$ ٢ ^{م _i} . لكي ينجح الرسم التخطيطي التقريبي، يجب أن تتحقق الخصائص الثلاث التالية:

تكون قيم b _i + m _j مختلفة لجميع الأزواج ( i , j ). وهذا يضمن عدم تلف بتات الرسم التخطيطي بسبب عملية الضرب.
b _i + m _i هي دالة متزايدة تمامًا لـ i . أي أن ترتيب بتات الرسم التخطيطي محفوظ حتى في x'.m.
( b _r + m _r ) - ( b ₁ + m ₁ ) ≤ r ⁴ . أي أن أجزاء الرسم يتم تجميعها في نطاق حجم لا يتجاوز r ⁴ ، حيث r ≤ O(w ^1/5 ).

يُبين الاستدلال الاستقرائي كيفية بناء mᵢ _. ليكن m₁ = w - b₁ _. لنفترض أن 1 < t ≤ r وأن m₁ _,m₂ , _..._,mₜ₋₁ قد تم اختيارها مسبقًا. عندئذٍ ، اختر أصغر عدد صحيح _mₜ بحيث تتحقق الخاصيتان (1) و(2). تتطلب الخاصية (1) أن _mₜ ≠ _bᵢ - bⱼ + mₜ _لجميع قيم i ≤ i ، j ≤ r و 1 ≤ ^l≤ tₜ₋₁ . بالتالي، يوجد أقل من tr₂ ≤ r₃ ^قيمة يجب _{على mₜ} تجنبها . بما أن mₜ مختارة لتكون أصغر ما يمكن، فإن ( _bₜ + _mₜ ) _≤ ( _bₜ₋₁₊ mₜ₋₁ ) ₊ r₃ . وهذا _يستلزم_{الخاصية}₍³ ).

وبالتالي، يتم حساب الرسم التخطيطي التقريبي على النحو التالي:

قم بإخفاء جميع الأجزاء باستثناء أجزاء الرسم التخطيطي باستخدام عملية AND المنطقية بين x و $\sum _{i=0}^{r-1}2^{b_{i}}$ .
اضرب المفتاح بالثابت المحدد مسبقًا m كما حُسب أعلاه. تتطلب هذه العملية فعليًا كلمتين آليتين، ولكن يمكن إنجازها في وقت ثابت.
قم بإخفاء جميع البتات باستثناء بتات الرسم التخطيطي المُزاحة. هذه البتات موجودة الآن في كتلة متجاورة لا تتجاوز r ⁴< w ^4/5 بت.

مقارنة متوازية

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

1 sketch( x ₁ )1 sketch( x ₂ )...1 sketch( x _k )

هنا، تُجمع جميع كلمات الرسم التخطيطي في سلسلة واحدة بإضافة بت مُفعّل لكل منها. يمكننا افتراض أن دالة الرسم التخطيطي تستخدم بالضبط b ≤ r ≤ ⁴ بتات. بالتالي، تستخدم كل كتلة 1 + b ≤ w ^{≤ 4/5} بتات، وبما أن k ≤ w ≤ ^1/5 ، فإن العدد الإجمالي للبتات في رسم العقدة التخطيطي هو w على الأكثر .

ملاحظة توضيحية موجزة: بالنسبة لسلسلة بتات s وعدد صحيح غير سالب m ، نرمز بـ s ^m إلى دمج s مع نفسها m مرة. إذا كانت t أيضًا سلسلة بتات، فإن st يرمز إلى دمج t مع s .

يُمكّن رسم العقدة من البحث عن المفاتيح لأي عدد صحيح y مكون من b بت . لنفترض أن z = (0 y ) ^k ، والذي يمكن حسابه في وقت ثابت (بضرب y في الثابت (0 ^b 1) ^k )، لجعله بنفس طول رسم العقدة بحيث يمكن مقارنة كل كلمة في رسم العقدة مع العدد الصحيح y في عملية واحدة، مما يُظهر التوازي على مستوى الكلمة. إذا كان طول y خمسة بتات، فسيتم ضربه في 000001....000001 للحصول على sketch(y) ^k . ينتج عن الفرق بين sketch(x _i ) و 0y أن يكون البت الرئيسي لكل كتلة 1، إذا وفقط إذا كان sketch(y) $\leq$ sketch(x _i ). وبالتالي يمكننا حساب أصغر فهرس i بحيث يكون sketch( x _i ) ≥ y كما يلي:

اطرح قيمة z من رسم العقدة.
قم بإجراء عملية AND المنطقية للفرق والثابت (10 ^b ) ^k . هذا يمسح كل شيء ما عدا البت الأول من كل كتلة.
ابحث عن الجزء الأكثر أهمية في النتيجة، لتحديد الفهرس الدقيق للانتقال من العناصر ذات الرسم التخطيطي الأصغر من الرسم التخطيطي للاستعلام إلى تلك الأكبر من الرسم التخطيطي للاستعلام.
احسب i، رتبة الرسم التخطيطي، باستخدام حقيقة أن البت الرائد للكتلة i له فهرس i ( b +1 ).

رسم المكتب

بالنسبة لأي استعلام q ، تحسب المقارنة المتوازية الفهرس i بحيث

sketch( x _{i -1} ) ≤ sketch( q ) ≤ sketch( x _i )

لسوء الحظ، لا يُحدد هذا العنصر السلف أو اللاحق الدقيق للقيمة q ، لأن موقع رسم q بين رسومات جميع القيم قد لا يتطابق مع موقع q في جميع القيم الفعلية. لكن الصحيح هو أنه من بين جميع المفاتيح، إما x _{i -1} أو x _i له أطول بادئة مشتركة مع q . وذلك لأن أي مفتاح y ذي بادئة مشتركة أطول مع q سيكون له أيضًا عدد أكبر من بتات الرسم المشتركة مع q ، وبالتالي سيكون sketch( y ) أقرب إلى sketch( q ) من أي sketch( x _j ).

يمكن حساب أطول بادئة مشتركة بين عددين صحيحين a و b، كل منهما مكون من w بت ، في وقت ثابت عن طريق إيجاد البت الأكثر أهمية في عملية XOR الثنائية بين a و b . ويمكن استخدام هذه القيمة لإخفاء جميع البادئات المشتركة باستثناء أطولها.

لاحظ أن p يُحدد بدقة مكان تفرع q من مجموعة المفاتيح. إذا كانت البتة التالية لـ q تساوي 0، فإن العنصر التالي لـ q موجود في الشجرة الفرعية p1 ، وإذا كانت البتة التالية لـ q تساوي 1، فإن العنصر السابق لـ q موجود في الشجرة الفرعية p0 . هذا يُشير إلى الخوارزمية التالية لتحديد الموقع الدقيق لـ q :

استخدم المقارنة المتوازية لإيجاد الدليل i بحيث يكون sketch( x _{i -1} ) ≤ sketch( q ) ≤ sketch( x _i ).
احسب أطول بادئة مشتركة p لـ q و إما x _{i -1} أو x _i (مع أخذ الأطول من الاثنين).
ليكن l -1 هو طول أطول بادئة مشتركة p .
1. إذا كانت البتة رقم l من q تساوي صفرًا، فليكن e = p 10 ^{w - l} . استخدم المقارنة المتوازية للبحث عن البتة التالية لـ sketche . هذه البتة هي البتة السابقة الفعلية لـ q .
2. إذا كانت البتة رقم l من q تساوي 1، فليكن e = p 01 ^{w - l} . استخدم المقارنة المتوازية للبحث عن البتة السابقة لـ sketche . هذه البتة هي البتة اللاحقة لـ q .
بمجرد العثور على العنصر السابق أو اللاحق لـ q ، يتم تحديد الموضع الدقيق لـ q بين مجموعة المفاتيح.

التجزئة المدمجة

قدّم ويلارد تطبيقًا لأشجار الدمج على جداول التجزئة ، حيث وصف بنية بيانات للتجزئة تجمع بين جدول تجزئة خارجي مع تسلسل التجزئة وشجرة دمج تمثل كل سلسلة تجزئة. في تسلسل التجزئة، يكون متوسط حجم السلسلة ثابتًا في جدول التجزئة ذي عامل التحميل الثابت، بالإضافة إلى أن جميع السلاسل، باحتمالية عالية، يكون حجمها $O (log n / log log n)$ ، حيث $n$ هو عدد العناصر المُجزأة. حجم السلسلة صغير بما يكفي لتمكين شجرة الدمج من معالجة عمليات البحث والتحديث داخلها في وقت ثابت لكل عملية. لذلك، يكون وقت جميع العمليات في بنية البيانات ثابتًا باحتمالية عالية. بتعبير أدق، مع بنية البيانات هذه، لكل احتمال شبه متعدد الحدود العكسي $p (n) = exp((log n) O (1))$ ، يوجد ثابت $C$ بحيث يكون احتمال وجود عملية تتجاوز الوقت $C$ على الأكثر $p (n)$ . ^{[ 6 ]}

النموذج الحسابي والافتراضات اللازمة

يعتمد النموذج الحسابي لخوارزمية شجرة الاندماج على ذاكرة وصول عشوائي للكلمات ( $Word$ RAM) مزودة بمجموعة تعليمات محددة، تشمل تعليمات حسابية - الجمع والطرح والضرب (جميعها تُنفذ بتردد $2w$ ) - وعمليات منطقية - مثل AND وNOT على مستوى البتات. كما تتضمن تعليمات ضرب مزدوجة الدقة. وقد ثبت ^{[ 7 ]} أن حذف هذه التعليمات الأخيرة يجعل من المستحيل فرز البيانات بسرعة تتجاوز $O (n log n)$ ، إلا إذا سُمح باستخدام مساحة ذاكرة تقارب $2w كلمة$ (على عكس المساحة الخطية التي تستخدمها أشجار الاندماج)، أو تضمين تعليمات أخرى بدلاً منها ^{[ 2 ]} .

مراجع

↑ فريدمان، إم إل ؛ ويلارد، دي إي (1990)، "اختراق حاجز نظرية المعلومات باستخدام أشجار الاندماج"، وقائع الندوة السنوية الثانية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '90) ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة، الصفحات 1-7 ، doi : 10.1145/100216.100217 ، ISBN 0-89791-361-2، S2CID 16367160 .
1 2 أندرسون، آرني؛ ميلترسن، بيتر برو؛ ثورب، ميكيل (1999)، "يمكن تنفيذ أشجار الدمج باستخدام تعليمات $AC$ $0$ فقط"، علوم الحاسوب النظرية ، 215 ( 1-2 ): 337-344 ، doi : 10.1016/S0304-3975(98)00172-8 ، MR 1678804 .
↑ رامان، راجيف (1996)، "طوابير الأولوية: الصغيرة، والرتيبة، والمتشعبة"، الخوارزميات - ESA '96 ، سلسلة محاضرات في علوم الحاسوب، المجلد 1136، برلين: سبرينغر-فيرلاغ، الصفحات 121-137 ، doi : 10.1007/3-540-61680-2_51 ، ISBN 978-3-540-61680-1MR 1469229 .
↑ أندرسون، آرني؛ ثورب، ميكيل (2007)، "المجموعات المرتبة الديناميكية مع أشجار البحث الأسية"، مجلة ACM ، 54 (3): A13، arXiv : cs/0210006 ، doi : 10.1145/1236457.1236460 ، MR 2314255 ، S2CID 8175703 .
↑ باتراسكو، ميهاي؛ ثورب، ميكيل (2014). "مجموعات الأعداد الصحيحة الديناميكية مع الترتيب الأمثل، والاختيار، والبحث عن السلف" . المؤتمر السنوي الخامس والخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، 2014. ص 166-175. arXiv : 1408.3045 . doi : 10.1109/FOCS.2014.26 . ISBN 978-1-4799-6517-5. S2CID 8943659 .
↑ ويلارد، دان إي. (2000)، "دراسة الهندسة الحسابية، وأشجار فان إمدي بواس، والتجزئة من منظور شجرة الاندماج"، مجلة SIAM للحوسبة ، 29 (3): 1030-1049 ، doi : 10.1137/S0097539797322425 ، MR 1740562 .
↑ بن عمرام، أمير م.؛ جليل، تسفي (1997)، "متى يمكننا الفرز في زمن قدره o ( n log n )؟"، مجلة علوم الحاسوب والنظم ، 54 (2): 345-370 ، doi : 10.1006/jcss.1997.1474.

روابط خارجية

MIT CS 6.897: هياكل البيانات المتقدمة: المحاضرة 4، أشجار الاندماج ، الأستاذ إريك ديمين (ربيع 2003)
MIT CS 6.897: هياكل البيانات المتقدمة: المحاضرة 5، المزيد عن أشجار الاندماج؛ هياكل البيانات ذاتية التنظيم، الانتقال إلى المقدمة، الأمثلية الثابتة ، الأستاذ إريك ديمين (ربيع 2003)
MIT CS 6.851: هياكل البيانات المتقدمة: المحاضرة 13، ملاحظات شجرة الاندماج ، البروفيسور إريك ديمين (ربيع 2007)
MIT CS 6.851: هياكل البيانات المتقدمة: المحاضرة 12، ملاحظات شجرة الاندماج ، البروفيسور إريك ديمين (ربيع 2012)

[1] فريدمان، إم إل ؛ ويلارد، دي إي (1990)، "اختراق حاجز نظرية المعلومات باستخدام أشجار الاندماج"، وقائع الندوة السنوية الثانية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '90) ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة، الصفحات 1-7 ، doi : 10.1145/100216.100217 ، ISBN 0-89791-361-2، S2CID 16367160 .

[AMT1999-2] 1 2 أندرسون، آرني؛ ميلترسن، بيتر برو؛ ثورب، ميكيل (1999)، "يمكن تنفيذ أشجار الدمج باستخدام تعليمات $AC$ $0$ فقط"، علوم الحاسوب النظرية ، 215 ( 1-2 ): 337-344 ، doi : 10.1016/S0304-3975(98)00172-8 ، MR 1678804 .

[3] رامان، راجيف (1996)، "طوابير الأولوية: الصغيرة، والرتيبة، والمتشعبة"، الخوارزميات - ESA '96 ، سلسلة محاضرات في علوم الحاسوب، المجلد 1136، برلين: سبرينغر-فيرلاغ، الصفحات 121-137 ، doi : 10.1007/3-540-61680-2_51 ، ISBN 978-3-540-61680-1MR 1469229 .

[4] أندرسون، آرني؛ ثورب، ميكيل (2007)، "المجموعات المرتبة الديناميكية مع أشجار البحث الأسية"، مجلة ACM ، 54 (3): A13، arXiv : cs/0210006 ، doi : 10.1145/1236457.1236460 ، MR 2314255 ، S2CID 8175703 .

[5] باتراسكو، ميهاي؛ ثورب، ميكيل (2014). "مجموعات الأعداد الصحيحة الديناميكية مع الترتيب الأمثل، والاختيار، والبحث عن السلف" . المؤتمر السنوي الخامس والخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، 2014. ص 166-175. arXiv : 1408.3045 . doi : 10.1109/FOCS.2014.26 . ISBN 978-1-4799-6517-5. S2CID 8943659 .

[6] ويلارد، دان إي. (2000)، "دراسة الهندسة الحسابية، وأشجار فان إمدي بواس، والتجزئة من منظور شجرة الاندماج"، مجلة SIAM للحوسبة ، 29 (3): 1030-1049 ، doi : 10.1137/S0097539797322425 ، MR 1740562 .

[7] بن عمرام، أمير م.؛ جليل، تسفي (1997)، "متى يمكننا الفرز في زمن قدره o ( n log n )؟"، مجلة علوم الحاسوب والنظم ، 54 (2): 345-370 ، doi : 10.1006/jcss.1997.1474.

شجرة

[ 2 ]

[

[

[

[ 6 ]

[ 7 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗