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

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’): एक नई स्ट्रिंग बनाने के लिए, स्ट्रिंग एस में स्थिति 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): दो रस्सियों को जोड़ें, एस₁ और एस₂, एक ही रस्सी में।

समय जटिलता: $O(1)$ (या $O(\log N)$ मूल वजन की गणना करने का समय)

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

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

विभाजन

: परिभाषा: Split (i, 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, और फिर नोड यू से शुरू करके टी को पार करें। उत्पादन C_i, …, C_{i + j − 1} नोड यू से शुरू करके टी का इन-ऑर्डर ट्रैवर्सल करके।

अखंड सरणियों के साथ तुलना

Performance

Operation	Rope	String
Index	O(log n)	O(1)
Split	O(log n)	O(1)
Concatenate (destructive)	O(log n) without rebalancing / O(n) worst case	O(n)
Concatenate (nondestructive)	O(n)	O(n)
Iterate over each character	O(n)	O(n)
Insert	O(log n) without rebalancing / O(n) worst case	O(n)
Append	O(log n) without rebalancing / O(n) worst case	O(1) amortized, O(n) worst case
Delete	O(log n)	O(n)
Report	O(j + log n)	O(j)
Build	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