الحبل (بنية البيانات)

الموسوعة الحرة
حبل بسيط مبني على سلسلة "مرحباً_اسمي_سيمون"

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

وصف

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

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

العمليات

في التعريفات التالية، يُمثل N طول الحبل، أي وزن العقدة الجذرية. هذه الأمثلة مُعرّفة بلغة برمجة جافا .

اجمع الأوراق

التعريف: أنشئ مكدسًا S وقائمة L. انتقل لأسفل العمود الفقري الأيسر للشجرة حتى تصل إلى ورقة l'، وأضف كل عقدة n إلى S. أضف l' إلى L. الأصل لـ l' ( p ) هو في أعلى المكدس. كرر الإجراء للشجرة الفرعية اليمنى لـ p.
package org.wikipedia.example ;استيراد java.util.ArrayDeque ; استيراد java.util.Deque ؛ استيراد java.util.Iterator ؛استيراد jakarta.annotation.NonNull ;class RopeLike { private RopeLike left ; private RopeLike right ;public RopeLike ( RopeLike left , RopeLike right ) { this . left = left ; this . right = right ; }public RopeLike getLeft () { return left ; }public RopeLike getRight () { return right ; } }public final class InOrderRopeIterator implements Iterator < RopeLike > { private final Deque < RopeLike > stack ;public InOrderRopeIterator ( @NonNull RopeLike root ) { stack = new ArrayDeque < > (); RopeLike c = root ; while ( c != null ) { stack.push ( c ) ; c = c.getLeft ( ) ; } }@Override public boolean hasNext () { return stack . size () > 0 ; }@Override public RopeLike next () { RopeLike result = stack . pop ();إذا لم تكن المكدسة فارغة ، فسيتم تنفيذ ما يلي : يتم استخراج العنصر الأب من المكدسة ، ثم يتم استخراج العنصر الأيمن من العنصر الأب . إذا كان العنصر الأيمن غير فارغ ، فسيتم إضافته إلى المكدسة ، ثم يتم استخراج العنصر الأيسر من العنصر الأيمن . طالما أن العنصر الأيسر غير فارغ ، فسيتم إضافته إلى المكدسة ، ثم يتم استخراج العنصر الأيسر من العنصر الأيسر .return result ; } }

إعادة التوازن

التعريف: اجمع مجموعة الأوراق L وأعد بناء الشجرة من الأسفل إلى الأعلى.
استيراد java.util.List ;دالة ثابتة منطقية isBalanced ( RopeLike r ) { int depth = r . depth (); if ( depth >= FIBONACCI_SEQUENCE . length - 2 ) { return false ; } return FIBONACCI_SEQUENCE [ depth + 2 ] <= r . weight (); }دالة ثابتة لإعادة توازن الحبال ( RopeLike rebalance ( RopeLike r ) { إذا لم تكن متوازنة ( r ) ) { قائمة <RopeLike> leaves = Ropes.collectLeaves ( r ) ; إرجاع دمج ( leaves , 0 , leaves.size ( ) ); } إرجاع r ; }دالة دمج ثابتة من نوع RopeLike ( قائمة <RopeLike> أوراق ) { إرجاع دمج ( أوراق ، 0 ، أوراق.الحجم ( ) ) ; }دالة ثابتة تُسمى `remerge` تأخذ قائمة من نوع ` RopeLike` تحتوي على ` leafs` و` start` و` end` . تقوم هذه الدالة بدمج عناصر شجرة ` RopeLike` باستخدام الدالة ` remerge` . يتم حساب نطاق الشجرة باستخدام ` range` ، حيث ` range` هو ` end` - ` start` . يتم تحديد النطاق بناءً على قيمة ` range` . في حالة ` range` ، يتم إنشاء شجرة `RopeLike` جديدة باستخدام ` leafs` و` start` و` end` . في حالة ` range` ، يتم إنشاء شجرة `RopeLike` جديدة باستخدام ` remerge` . يتم حساب متوسط ​​المسافة بين ` leafs` و` end` . يتم دمج ` leafs` و` end` . يتم إنشاء شجرة ` RopeLike` جديدة باستخدام ` remerge` .

أدخل

التعريف:Insert(i, S’) : أدخل السلسلة S' بدءًا من الموضع i في السلسلة s ، لتشكيل سلسلة جديدة C 1 ، ... ، C i ، S' ، C i + 1 ، ... ، C m .
التعقيد الزمني :يا(سجل⁡شمال){\displaystyle O(\log N)}⁠ .

يمكن إجراء هذه العملية من خلال Split()عمليتين Concat(). التكلفة هي مجموع التكاليف الثلاث.

استيراد javafx.util.Pair ؛public Rope insert ( int idx , CharSequence sequence ) { if ( idx == 0 ) { return prepend ( sequence ) ; } else if ( idx == length ()) { return append ( sequence ); } else { Pair < RopeLike , RopeLike > lhs = base.split ( idx ) ; return new Rope ( Ropes.concat ( lhs.getKey ( ). append ( sequence ) , lhs.getValue ( ) ) ) ; } }

فِهرِس

الشكل 2.1: مثال على البحث عن فهرس في سلسلة.
التعريف:Index(i) : إرجاع الحرف الموجود في الموضع i
التعقيد الزمني :يا(سجل⁡شمال){\displaystyle O(\log N)}⁠

لاستخراج الحرف رقم i ، نبدأ بحثًا متكررًا من العقدة الجذرية:

@Override public int indexOf ( char ch , int startIndex ) { if ( startIndex > weight ) { return right . indexOf ( ch , startIndex - weight ); } else { return left . indexOf ( ch , startIndex ); } }

على سبيل المثال، لإيجاد الحرف في i=10الشكل 2.1 الموضح على اليمين، نبدأ من العقدة الجذرية (A)، ونجد أن 22 أكبر من 10، وأن هناك ابنًا أيسر، لذا ننتقل إلى الابن الأيسر (B). 9 أصغر من 10، لذا نطرح 9 من 10 (ويتبقى لدينا 6 i=1)، ثم ننتقل إلى الابن الأيمن (D). بعد ذلك، ولأن 6 أكبر من 1، ولأن هناك ابنًا أيسر، ننتقل إلى الابن الأيسر (G). 2 أكبر من 1، ولأن هناك ابنًا أيسر، لذا ننتقل إلى الابن الأيسر مرة أخرى (J). أخيرًا، 2 أكبر من 1، ولكن لا يوجد ابن أيسر، لذا فإن الحرف الموجود في الفهرس 1 من السلسلة القصيرة "na" (أي "n") هو الإجابة. (فهرسة تبدأ من 1)

متصل

الشكل 2.2: ربط حبلين فرعيين في حبل واحد.
التعريف:Concat(S1, S2) : ربط حبلين، S 1 و S 2 ، في حبل واحد.
التعقيد الزمني :يا(1){\displaystyle O(1)}( أو​يا(سجل⁡شمال){\displaystyle O(\log N)}( الوقت اللازم لحساب وزن الجذر)

يمكن إجراء عملية دمج بسيطة عن طريق إنشاء عقدة جذرية جديدة يكون طولها الأيسر S1 وطولها الأيمن S2 ، وهو ما يستغرق وقتًا ثابتًا. يتم تعيين وزن العقدة الأبوية على طول الابن الأيسر S1 ، وهو ما يستغرق ⁠يا(سجل⁡شمال){\displaystyle O(\log N)}الوقت ، إذا كانت الشجرة متوازنة.

بما أن معظم عمليات الحبال تتطلب أشجارًا متوازنة، فقد يلزم إعادة موازنة الشجرة بعد عملية الربط.

ينقسم

الشكل 2.3: تقسيم حبل إلى نصفين.
التعريف:Split (i, S) : تقسيم السلسلة S إلى سلسلتين جديدتين S 1 و S 2 ، S 1 = C 1 ، ... ، C i و S 2 = C i + 1 ، ... ، C m .
التعقيد الزمني :يا(سجل⁡شمال){\displaystyle O(\log N)}⁠

هناك حالتان يجب التعامل معهما:

  1. تقع نقطة التقسيم في نهاية السلسلة (أي بعد الحرف الأخير من عقدة الورقة).
  2. تقع نقطة الانقسام في منتصف السلسلة.

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

على سبيل المثال، لتقسيم سلسلة الأحرف المكونة من 22 حرفًا والموضحة في الشكل 2.3 إلى سلسلتين متساويتين بطول 11 حرفًا، استعلم عن الحرف الثاني عشر لتحديد موقع العقدة K في المستوى السفلي. أزل الرابط بين K و G. انتقل إلى العقدة الأب لـ G واطرح وزن K من وزن D. صعد الشجرة وأزل أي روابط يمين إلى الأشجار الفرعية التي تغطي الأحرف بعد الموضع 11، واطرح وزن K من عقدها الأبوية (العقدتان D و A فقط في هذه الحالة). أخيرًا، أنشئ العقدتين K و H المنفصلتين حديثًا عن طريق دمجهما وإنشاء عقدة أب جديدة P بوزن يساوي طول العقدة اليسرى K.

بما أن معظم عمليات الرفع بالحبال تتطلب أشجارًا متوازنة، فقد يلزم إعادة موازنة الشجرة بعد تقسيمها.

استيراد javafx.util.Pair ؛public Pair < RopeLike , RopeLike > split ( int index ) { if ( index < weight ) { Pair < RopeLike , RopeLike > split = left.split ( index ) ; return Pair.of ( rebalance ( split.getKey ( ) ) , rebalance ( new RopeLikeTree ( split.getValue ( ) , right ) ) ) ; } else if ( index > weight ) { Pair < RopeLike , RopeLike > split = right.split ( index - weight ) ; return Pair.of ( rebalance ( new RopeLikeTree ( left , split.getKey ( ) ) , rebalance ( split.getValue ( ) ) ) ; } else { return Pair.of ( left , right ) ; } }

يزيل

التعريف:Remove(i, j) : إزالة السلسلة الفرعية C i ، …, C i + j − 1 ، من s لتشكيل سلسلة جديدة C 1 ، …, C i − 1 ، C i + j ، …, C m .
التعقيد الزمني :يا(سجل⁡شمال){\displaystyle O(\log N)}⁠ .

يمكن تنفيذ هذه العملية بخطوات بسيطة Split(). Concat()أولاً، يتم تقسيم السلسلة إلى ثلاثة أجزاء، كل جزء حسب الحرف i والحرف i+j على التوالي، مما يستخرج السلسلة المراد حذفها في عقدة منفصلة. ثم يتم دمج العقدتين المتبقيتين.

استيراد javafx.util.Pair ؛@Override public RopeLike remove ( int start , int length ) { Pair < RopeLike , RopeLike > lhs = split ( start ) ; Pair < RopeLike , RopeLike > rhs = split ( start + length ); return rebalance ( new RopeLikeTree ( lhs.getKey ( ), rhs.getValue ( ) )); }

تقرير

التعريف:Report(i, j) : إخراج السلسلة C i ، …, C i + j − 1 .
التعقيد الزمني :يا(ج+سجل⁡شمال){\displaystyle O(j+\log N)}⁠

للإبلاغ عن السلسلة C <sub>i</sub> , …, C<sub> i + j -1</sub> ، ابحث عن العقدة u التي تحتوي على C<sub> i </sub> و C<sub>i+j-1</sub> weight(u) >= j، ثم قم باجتياز T بدءًا من العقدة u . أخرج C <sub>i </sub>, …, C<sub> i + j -1</sub> عن طريق إجراء اجتياز ترتيبي لـ T بدءًا من العقدة u .

مقارنة مع المصفوفات المتجانسة

المزايا:

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

العيوب:

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

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

تعقيد
عمليةحبلخيط
الفهرس [ 1 ]O(log n)O(1)
الانقسام [ 1 ]O(log n)O(1)
سلسلO(1) مُستهلكة، O(log n) أسوأ حالةعلى)
قم بالتكرار على كل حرف [ 1 ]على)على)
أدخل [ 2 ]O(log n)على)
أضف [ 2 ]O(1) مُستهلكة، O(log n) أسوأ حالةO(1) مُستهلكة، O(n) أسوأ حالة
يزيلO(log n)على)
تقريرO(j + log n)O(j)
يبنيعلى)على)

انظر أيضاً

  • بيئة برمجة Cedar ، التي استخدمت الحبال "تقريبًا منذ بدايتها" [ 1 ]
  • نموذج T enfilade ، وهو بنية بيانات مماثلة من أوائل سبعينيات القرن العشرين
  • مخزن الفجوات ، وهو بنية بيانات شائعة الاستخدام في محررات النصوص، تسمح بعمليات إدراج وحذف فعالة مجمعة بالقرب من نفس الموقع.
  • جدول القطع ، وهو بنية بيانات أخرى شائعة الاستخدام في محررات النصوص

مراجع

  1. 1 2 3 4 5 بوهم، هانز-ج؛ أتكينسون، روس؛ بلاس، مايكل (ديسمبر 1995). "الحبال: بديل للخيوط" (ملف PDF) . البرمجيات: الممارسة والخبرة . 25 (12). نيويورك، نيويورك، الولايات المتحدة الأمريكية: جون وايلي وأولاده: 1315-1330 . doi : 10.1002/spe.4380251203 . مؤرشف من الأصل في 2020-03-08.
  2. 1 2 "نظرة عامة على تنفيذ الحبال" . www.sgi.com . مؤرشف من الأصل بتاريخ 19-12-2017 . تم الاطلاع عليه بتاريخ 01-03-2017 .