रोप (डेटा संरचना)

Hello_my_name_is_Simon की डोरी पर बनी एक साधारण रोप।

कंप्यूटर प्रोग्रामिंग में, रोप, या कॉर्ड, छोटी स्ट्रिंग (कंप्यूटर विज्ञान) से बनी एक डेटा स्ट्रक्चर है जिसका उपयोग बहुत लंबी स्ट्रिंग को एफ्फीशियेन्टली स्टोर करने और मैनिपुलेट करने के लिए किया जाता है। उदाहरण के लिए, एक टेक्स्ट एडिटिंग प्रोग्राम एडिट किए जा रहे टेक्स्ट को दर्शाने के लिए एक रोप का उपयोग कर सकता है, ताकि इंसर्शन, डिलीशन और रैंडम एक्सेस जैसे ऑपरेशन एफ्फीशियेन्टली किए जा सकें।

विवरण

रोप एक प्रकार का बाइनरी ट्री है जहां प्रत्येक लीफ (अंतिम नोड) एक स्ट्रिंग और लेंथ (जिसे वेट के रूप में भी जाना जाता है) रखती है, और ट्री के आगे प्रत्येक नोड अपने लेफ्ट सबट्री में सभी लीफ की लेंथ का सम रखता है। दो चिल्ड्रन वाला एक नोड इस प्रकार पूरी स्ट्रिंग को दो भागों में डिवाइड करता है: राइट उपट्री स्ट्रिंग के पहले भाग को स्टोर करता है, लेफ्ट उपट्री स्ट्रिंग के दूसरे भाग को स्टोर करता है, और एक नोड का वेट पहले भाग की लेंथ है।

रोप ऑपरेशन के लिए, नोड्स में स्टोर स्ट्रिंग्स को टिपिकल नॉनडिस्ट्रक्टिव केस में निरंतर इम्म्युटेबल ऑब्जेक्ट माना जाता है, जो कुछ कॉपी-ऑन-राइट बिहेवियर की अनुमति देता है। लीफ नोड्स को सामान्यतः स्ट्रिंग (कंप्यूटर विज्ञान) के रूप में कार्यान्वित किया जाता है। बेसिक फिक्स्ड-लेंथ स्ट्रिंग्स के साथ एक रिफरेन्स काउंट के साथ जब आवश्यकता नहीं होती है, तब डीएलोकेशन करने के लिए अटैच किया जाता है, हालांकि अन्य गार्बेज कलेक्शन (कंप्यूटर विज्ञान) विधियों का भी उपयोग किया जा सकता है।

ऑपरेशन

निम्नलिखित परिभाषाओं में, N रोप की लेंथ है।

कलेक्ट लीव्स

डेफिनिशन: एक स्टैक एस और एक सूची एल बनाएं। जब तक आप एक लीफ एल' तक नहीं पहुंच जाते, तब तक ट्री की लेफ्ट-मोस्ट स्पाइन को ट्रैवर्स करें, प्रत्येक नोड एन को एस में जोड़ें। एल में एल जोड़ें। एल का रूट' (पी) ) स्टैक के शीर्ष पर है। पी के राइट सबट्री के लिए प्रोसीजर दोहराएँ।

final class InOrderRopeIterator implements Iterator<RopeLike> {

  private final Deque<RopeLike> stack;

  InOrderRopeIterator(@NonNull RopeLike root) {
    stack = new ArrayDeque<>();
    var c = root;
    while (c != null) {
      stack.push(c);
      c = c.getLeft();
    }
  }

  @Override
  public boolean hasNext() {
    return stack.size() > 0;
  }

  @Override
  public RopeLike next() {
    val result = stack.pop();

    if (!stack.isEmpty()) {
      val parent = stack.pop();
      val right = parent.getRight();
      if (right != null) {
        stack.push(right);
        var cleft = right.getLeft();
        while (cleft != null) {
          stack.push(cleft);
          cleft = cleft.getLeft();
        }
      }
    }

    return result;
  }
}

रीबैलेंस

डेफिनिशन: लीफ के सेट L को इकट्ठा करें और नीचे से ऊपर तक ट्री को रीबिल्ट करें।

  static boolean isBalanced(RopeLike r) {
    val depth = r.depth();
    if (depth >= FIBONACCI_SEQUENCE.length - 2) {
      return false;
    }
    return FIBONACCI_SEQUENCE[depth + 2] <= r.weight();
  }

  static RopeLike rebalance(RopeLike r) {
    if (!isBalanced(r)) {
      val leaves = Ropes.collectLeaves(r);
      return merge(leaves, 0, leaves.size());
    }
    return r;
  }

  static RopeLike merge(List<RopeLike> leaves) {
    return merge(leaves, 0, leaves.size());
  }

  static RopeLike merge(List<RopeLike> leaves, int start, int end) {
    int range = end - start;
    if (range == 1) {
      return leaves.get(start);
    }
    if (range == 2) {
      return new RopeLikeTree(leaves.get(start), leaves.get(start + 1));
    }
    int mid = start + (range / 2);
    return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end));
  }

इन्सर्ट

डेफिनिशन: Insert(i, S’): एक नई स्ट्रिंग बनाने के लिए, स्ट्रिंग s में पोजीशन i से स्टार्ट होने वाली स्ट्रिंग C₁, ..., C_i, S', C_{i + 1}, ..., C_m है।

टाइम कम्प्लेक्सिटी: $O(\log N)$ है।

यह ऑपरेशन a Split() और दो Concat() ऑपरेशन द्वारा किया जा सकता है। कॉस्ट तीनों का सम है।

  public Rope insert(int idx, CharSequence sequence) {
    if (idx == 0) {
      return prepend(sequence);
    }
    if (idx == length()) {
      return append(sequence);
    }
    val lhs = base.split(idx);
    return new Rope(Ropes.concat(lhs.fst.append(sequence), lhs.snd));
  }

इंडेक्स

डेफिनिशन: Index(i): अक्षर को करैक्टर i पर रीटर्न करें

टाइम कम्प्लेक्सिटी: $O(\log N)$

i-वें वर्ण को पुनः प्राप्त करने के लिए, हम रूट नोड से एक रिकर्सिव सर्च स्टार्ट करते हैं:

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

उदाहरण के लिए, करैक्टर को खोजने के लिए i=10 राइट ओर दिखाए गए चित्र 2.1 में, रूट नोड (ए) से स्टार्ट करें, पता लगाएं कि 22, 10 से बड़ा है और एक राइट चाइल्ड है, इसलिए लेफ्ट चाइल्ड (बी) पर जाएं। 9, 10 से कम है, इसलिए 10 में से 9 घटाएं (छोड़कर)। i=1) और राइट चाइल्ड (डी) के पास जाएं। फिर क्योंकि 6, 1 से बड़ा है और एक राइट चाइल्ड है, लेफ्ट चाइल्ड (G) पर जाएँ। 2, 1 से बड़ा है और एक राइट चाइल्ड है, इसलिए फिर से लेफ्ट चाइल्ड (जे) पर जाएं। एन्ड में 2, 1 से बड़ा है लेकिन कोई लेफ्ट चाइल्ड नहीं है, इसलिए छोटी स्ट्रिंग na (यानी n) के इंडेक्स 1 पर वर्ण उत्तर (1-बेस्ड इंडेक्स) है।

कॉनकैट

डेफिनिशन: Concat(S1, S2): दो रोप्स को, S₁ और S₂, एक ही रोप में जोड़ें।

टाइम कम्प्लेक्सिटी: $O(1)$ (या $O(\log N)$ रुट वेट को कंप्यूट करने का टाइम)

एक नया रूट नोड बनाकर बस एक संयोजन left = S1 और right = S2 किया जा सकता है, जो कांस्टेंट टाइम है। रूट नोड का वेट लेफ्ट चाइल्ड S₁ की लेंथ पर सेट है, जो $O(\log N)$ टाइम लेगा, यदि ट्री बैलेंस्ड है।

चूंकि मोस्ट रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए संयोजन के बाद ट्री को री-बैलेंस करने की आवश्यकता हो सकती है।

स्प्लिट

डेफिनिशन: Split (i, S): स्ट्रिंग S को दो नए स्ट्रिंग S₁ और S₂ S₁ = C₁, ..., C_i और S₂ = C_{i + 1}, ..., C_m में स्प्लिट करें।

टाइम कम्प्लेक्सिटी: $O(\log N)$

ऐसे दो केस हैं जिनसे डील करना है:

1. स्प्लिट पॉइंट एक स्ट्रिंग के एन्ड में है (यानी लीफ नोड के अंतिम अक्षर के बाद)
2. स्प्लिट पॉइंट एक स्ट्रिंग के मध्य में है।

दूसरा केस दो नए लीफ नोड्स बनाने के लिए स्प्लिट पॉइंट पर स्ट्रिंग को स्प्लिट करके पहले को कम करता है, फिर एक नया नोड बनाता है जो दो कॉम्पोनेन्ट स्ट्रिंग्स का पैरेंट है।

उदाहरण के लिए, फिगर 2.3 में पिक्चर 22-करैक्टर की रोप को लेंथ 11 की दो समान घटक रोप्स में स्प्लिट करने के लिए, निचले स्तर पर नोड K का पता लगाने के लिए 12वें करैक्टर को क्वेरी करें। K और G के बीच के लिंक को हटा दें। G के पैरेंट के पास जाएं और K के वेट को D के वेट से घटा दें। ट्री के ऊपर जाएं और पोजीशन 11 से पहले वर्णों को कवर करने वाले सबट्री के किसी भी सही लिंक को हटा दें, K के वेट को उनके से घटा दें। रूट नोड्स (इस केस में केवल नोड डी और ए)। एन्ड में, नए ओर्फनेड नोड्स K और H को एक साथ जोड़कर और लेफ्ट नोड K की लेंथ के बैलेंस्ड वेट के साथ एक नया पैरेंट P बनाएं।

चूंकि अधिकांश रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए ट्री को स्प्लिट होने के बाद फिर से बैलेंस करने की आवश्यकता हो सकती है।

  public Pair<RopeLike, RopeLike> split(int index) {
    if (index < weight) {
      val split = left.split(index);
      return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right)));
    } else if (index > weight) {
      val split = right.split(index - weight);
      return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd));
    } else {
      return Pair.of(left, right);
    }
  }

डिलीट

डेफिनिशन: Delete(i, j): सबस्ट्रिंग डिलीट C_i, …, C_{i + j − 1}, s से एक नई स्ट्रिंग C₁, …, C_{i − 1}, C_{i + j}, …, C_m बनाने के लिए किया था।

टाइम कम्प्लेक्सिटी: $O(\log N)$.

यह ऑपरेशन दो Split() और एक Concat()ऑपरेशन द्वारा किया जा सकता है। सबसे पहले, रोप को तीन भागों में स्प्लिट करें, क्रमशः i-th और i+j-th करैक्टर से स्प्लिट करें, जो एक अलग नोड में हटाने के लिए स्ट्रिंग को निकालता है। फिर अन्य दो नोड्स को जोड़ें।

  @Override
  public RopeLike delete(int start, int length) {
    val lhs = split(start);
    val rhs = split(start + length);
    return rebalance(new RopeLikeTree(lhs.fst, rhs.snd));
  }

रिपोर्ट

डेफिनिशन: Report(i, j): स्ट्रिंग C_i, …, C_{i + j − 1} को आउटपुट करें।

टाइम कम्प्लेक्सिटी: $O(j+\log N)$

स्ट्रिंग C_i, …, C_{i + j − 1} की रिपोर्ट करने के लिए, वह नोड ढूंढें जिसमें C_i और weight(u) >= j सम्मिलित है, और फिर नोड u से स्टार्ट करके T को ट्रैवर्स करें। आउटपुट C_i, …, C_{i + j − 1} नोड यू से स्टार्ट करके टी का इन-ऑर्डर ट्रैवर्सल करके।

मोनोलिथिक ऐरे के साथ कमपैरीजन

परफॉरमेंस

ऑपरेशन	रोप	स्ट्रिंग
इंडेक्स	O(log n)	O(1)
स्प्लिट	O(log n)	O(1)
कॉनकेटनेट (डिस्ट्रक्टिव)	O(log n) without rebalancing / O(n) worst case	O(n)
कॉनकेटनेट (नॉनडिस्ट्रक्टिव)	O(n)	O(n)
प्रत्येक करैक्टर पर इटीरेट	O(n)	O(n)
इन्सर्ट	O(log n) without rebalancing / O(n) worst case	O(n)
अपेण्ड	O(log n) without rebalancing / O(n) worst case	O(1) amortized, O(n) worst case
डिलीट	O(log n)	O(n)
रिपोर्ट	O(j + log n)	O(j)
बिल्ड	O(n)	O(n)

एडवांटेज:

• रोप्स मोनोलिथिक स्ट्रिंग ऐरे की कमपैरीजन में बहुत तीव्रता से पाठ को सम्मिलित करने और हटाने में सक्षम बनाती हैं, जिन पर ऑपरेशन में टाइम कम्प्लेक्सिटी O (n) होती है।
• रोप्स को ऑपरेट होने पर O(n) एक्स्ट्रा मेमोरी की आवश्यकता नहीं होती है (ऐरे को प्रतिलिपि ऑपरेशन के लिए इसकी आवश्यकता होती है)।
• रोप्स को बड़े सन्निहित मेमोरी स्पेस की आवश्यकता नहीं होती है।
• यदि ऑपरेशन के केवल नॉन डिस्ट्रक्टिव वरजन का उपयोग किया जाता है, तो रोप एक परसिस्टेंट डेटा स्ट्रक्चर है। टेक्स्ट एडिटिंग प्रोग्राम उदाहरण के लिए, इससे कई पूर्ववत लेवल के लिए इजी समर्थन प्राप्त होता है।

डिसएडवांटेज:

• मुख्य रूप से रूट नोड्स को स्टोर करने के लिए ऑपरेट नहीं होने पर अधिक ओवरआल स्पेस का उपयोग है। कुल मेमोरी का कितना हिस्सा ओवरहेड है और डेटा के कितने लंबे पीस को स्ट्रिंग के रूप में संसाधित किया जा रहा है, इसके बीच एक ट्रेड-ऑफ है। ऊपर दिए गए उदाहरण के डाटा में स्ट्रिंग आधुनिक वास्तुकला के लिए अनरीयलिस्टिक रूप से छोटे हैं। ओवरहेड हमेशा O(n) होता है, लेकिन स्थिरांक को आरबिटरेरी ढंग से छोटा किया जा सकता है।
• अतिरिक्त स्टोरेज के प्रबंधन के लिए टाइम में वृद्धि
• सोर्स कोड की बढ़ी हुई कॉम्पलेक्सिटी; बग का अधिक रिस्क

यह टेबल स्ट्रिंग और रोप इम्प्लीमेंटेशन के एल्गोरिथम ट्रेट की कमपैरीजन करती है, न कि उनकी रॉ स्पीड की। ऐरे-बेस्ड स्ट्रिंग्स का ओवरहेड छोटा होता है, इसलिए (उदाहरण के लिए) छोटे डेटासेट पर कॉन्सटेनेशन और स्प्लिट ऑपरेशन तीव्र होते हैं। हालाँकि, जब लंबी स्ट्रिंग्स के लिए ऐरे-बेस्ड स्ट्रिंग्स का उपयोग किया जाता है, तो करैक्टर को सम्मिलित करने और हटाने के लिए टाइम कम्प्लेक्सिटी और मेमोरी का उपयोग अनएक्सेप्टबली बड़ा हो जाता है। इसके विपरीत, रोप डेटा स्ट्रक्चर में डेटा आकार रीगार्डलेस्स स्टेबल परफॉरमेंस होता है। इसके अतिरिक्त, रोप्स और ऐरे के लिए स्पेस कॉम्पलेक्सिटी O(n) दोनों हैं। संक्षेप में, जब डेटा बड़ा हो और प्रायः मॉडिफाइड हो तो रोप्स बेहतर होती हैं।

यह भी देखें

• सीडर (प्रोग्रामिंग भाषा) प्रोग्रामिंग वातावरण, जो अपनी स्थापना के टाइम से ही रोप्स का उपयोग करता था
• एनफिलेड (ज़ानाडु), 1970 के दशक की शुरुआत की एक समान डेटा स्ट्रक्चर
• गैप बफ़र , एक डेटा स्ट्रक्चर जो आमतौर पर टेक्स्ट संपादकों में उपयोग की जाती है जो एक ही स्थान के पास क्लस्टर किए गए कुशल सम्मिलन और विलोपन ऑपरेशन की अनुमति देती है
• टुकड़ा टेबल, एक अन्य डेटा स्ट्रक्चर जो आमतौर पर पाठ संपादकों में उपयोग की जाती है

बाहरी संबंध

• "absl::Cord" implementation of ropes within The Abseil library
• "C cords" implementation of ropes within the Boehm Garbage Collector library
• SGI C++ specification for ropes (supported by STLPort and libstdc++)
• Ropes for C#
• ropes for Common Lisp
• Ropes for Java
• String-Like Ropes for Java
• Ropes for JavaScript
• Ropes for Limbo
• ropes for Nim
• Ropes for OCaml
• pyropes for Python
• Ropes for Smalltalk
• SwiftRope for Swift
• "Ropey" for Rust