ロープ（データ構造）

コンピュータプログラミングにおいて、ロープまたはコードは、より長い文字列またはテキスト全体を効率的に保存および操作するために使用される、より小さな文字列で構成されたデータ構造です。たとえば、テキスト編集プログラムでは、挿入、削除、ランダムアクセスなどの操作を効率的に実行できるように、編集中のテキストを表すためにロープを使用することがあります。^[1]

ロープはバイナリ ツリーの一種で、各リーフ (エンド ノード) には扱いやすいサイズと長さ (重みとも呼ばれる) の文字列が格納され、ツリーの上位の各ノードには、その左サブツリーにあるすべてのリーフの長さの合計が格納されます。2つの子を持つノードは、文字列全体を 2 つの部分に分割します。左サブツリーには文字列の最初の部分が、右サブツリーには文字列の 2 番目の部分がそれぞれ格納され、ノードの重みは最初の部分の長さになります。

ロープ操作の場合、ノードに格納されている文字列は、通常の非破壊的なケースでは不変の定数オブジェクトであると想定され、コピーオンライト動作が可能になります。リーフ ノードは通常、不要になったときに割り当てを解除するための参照カウントが添付された基本的な固定長文字列として実装されますが、他のガベージ コレクションメソッドも使用できます。

以下の定義では、N はロープの長さ、つまりルート ノードの重さです。

定義:スタックSとリストLを作成します。ツリーの左端の背骨に沿ってリーフ l' に到達するまで移動し、各ノードn をSに追加します。 l' をLに追加します。 l' の親 ( p ) はスタックの最上部にあります。 p の右側のサブツリーに対してこの手順を繰り返します。

最終クラスInOrderRopeIterator はIterator < RopeLike >を実装します{     

    プライベート最終Deque < RopeLike >スタック;   

    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 ( ) ) { var parent = stack.pop ( ) ; var right = parent.getRight ( ) ; if ( right ! = null ) { stack.push ( right ) ; var cleft = right.getLeft ( ) ; while ( cleft ! = null ) { stack.push ( cleft ) ; cleft = cleft.getLeft ( ) ; } } }  
               
               
                
                
                   
                    
                    
                      
                
            
        

        結果を返す; } } 
    

定義:葉のセット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 ; }    
      
           
           
    
     


静的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 )); }        
         
        
         
    
        
             
    
           
           

定義: 文字列sの位置iInsert(i, S’)から文字列S'を挿入し、新しい文字列C ₁、...、C _i、S'、C _{i + 1}、...、C _mを形成します。

時間計算量: ⁠ ⁠${\displaystyle O(\log N)}$ .

Split()この操作は 1 つの操作と 2 つの操作で実行できますConcat()。コストは 3 つの操作の合計です。

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 ) ); }      
        
         
    
        
         
    
       
       

定義: : 位置 iIndex(i)の文字を返す

時間計算量: ⁠ ⁠${\displaystyle O(\log N)}$

i番目の文字を取得するには、ルート ノードから 再帰検索を開始します。

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

たとえば、i=10右の図 2.1 の の文字を見つけるには、ルート ノード (A) から開始し、22 が 10 より大きく、左の子が存在するため、左の子 (B) に移動します。9 は 10 より小さいため、10 から 9 を減算し ( を残してi=1)、右の子 (D) に移動します。次に、6 が 1 より大きく、左の子が存在するため、左の子 (G) に移動します。2 が 1 より大きく、左の子が存在するため、再び左の子 (J) に移動します。最後に、2 は 1 より大きいが左の子が存在しないため、短い文字列 "na" (つまり "n") のインデックス 1 の文字が答えになります。(1 から始まるインデックス)

定義: Concat(S1, S2) 2 本のロープS ₁とS ₂を 1 本のロープに連結します。

時間計算量: ⁠ ⁠${\displaystyle O(1)}$ (または⁠ ⁠${\displaystyle O(\log N)}$ルートの重みを計算する時間)

連結は、 left = S1、right = S2の新しいルートノードを作成するだけで実行でき、これは定数時間です。親ノードの重みは、左の子S _{1の長さに設定され、ツリーがバランスが取れている場合は、} ⁠ ⁠時間がかかります。 ${\displaystyle O(\log N)}$

ほとんどのロープ操作ではバランスの取れたツリーが必要なので、連結後にツリーを再度バランス調整する必要がある場合があります。

定義: Split (i, S)文字列S を2 つの新しい文字列S ₁とS ₂に分割します。S ₁ = C ₁、...、C iおよびS ₂ = C _{i + 1}、...、C _mです。

時間計算量: ⁠ ⁠${\displaystyle O(\log N)}$

対処しなければならないケースが 2 つあります。

1. 分割ポイントは文字列の末尾（つまり、リーフノードの最後の文字の後）にあります。
2. 分割ポイントは文字列の中央にあります。

2 番目のケースは、分割ポイントで文字列を分割して 2 つの新しいリーフ ノードを作成し、次に 2 つのコンポーネント文字列の親となる新しいノードを作成することによって、最初のケースに簡略化されます。

たとえば、図 2.3 に示す 22 文字のロープを、長さが 11 の 2 つの等しいコンポーネント ロープに分割するには、12 番目の文字をクエリして、最下位レベルのノードKを見つけます。 KとG の間のリンクを削除します。 Gの親に移動して、 Kの重みをDの重みから減算します。ツリーを上に移動し、位置 11 より後の文字をカバーするサブツリーへの右側のリンクをすべて削除し、Kの重みをその親ノード (この場合はノードDとAのみ) から減算します。最後に、新たに孤立したノード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 ); } }     
        
           
            
          
             
            
      
          
    

定義: sからDelete(i, j)部分文字列C _i , …, C _{i + j − 1}を削除して、新しい文字列C ₁ , …, C _{i − 1} , C _{i + j} , …, C _mを作成します。

時間計算量: ⁠ ⁠${\displaystyle O(\log N)}$ .

Split()この操作は、2 つの操作と 1 つの操作で実行できますConcat()。まず、ロープを 3 つに分割し、それぞれi番目とi+j番目の文字で分割して、削除する文字列を別のノードに抽出します。次に、他の 2 つのノードを連結します。

@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}を出力します。

時間計算量: ⁠ ⁠${\displaystyle O(j+\log N)}$

文字列C _i、…、C _{i + j − 1}を報告するには、 C _iとを含むノードuを見つけ、ノードuからT をトラバースします。ノードuからTを順番にトラバースして、C _i、…、C _{i + j − 1 を}出力します。 weight(u) >= j

利点:

• ロープを使用すると、操作の時間計算量が O(n) であるモノリシックな文字列配列よりもはるかに高速なテキストの挿入と削除が可能になります。
• ロープは操作時に O(n) の追加メモリを必要としません (配列はコピー操作にそれを必要とします)。
• ロープには大きな連続したメモリ空間は必要ありません。
• 非破壊的な操作バージョンのみが使用される場合、rope は永続的なデータ構造になります。テキスト編集プログラムの例では、これにより複数の元に戻すレベルを簡単にサポートできます。

デメリット:

• 操作されていないときは、主に親ノードを格納するために、全体的なスペース使用量が大きくなります。このようなオーバーヘッドが合計メモリのどのくらいを占めるかと、文字列として処理されるデータの長さとの間にはトレードオフがあります。上記の例の図の文字列は、現代のアーキテクチャでは非現実的に短いです。オーバーヘッドは常に O(n) ですが、定数は任意に小さくすることができます。
• 追加ストレージの管理にかかる時間の増加
• ソースコードの複雑さが増し、バグのリスクが増大

この表は、文字列とロープの実装のアルゴリズム特性を比較したものであり、実際の速度を比較したものではありません。配列ベースの文字列はオーバーヘッドが小さいため、（たとえば）小さなデータセットでは連結や分割の操作が高速になります。ただし、配列ベースの文字列を長い文字列に使用すると、文字の挿入と削除にかかる時間計算量とメモリ使用量が許容できないほど大きくなります。対照的に、ロープ データ構造は、データ サイズに関係なく安定したパフォーマンスを発揮します。さらに、ロープと配列の空間計算量はどちらも O(n) です。まとめると、データが大きく、頻繁に変更される場合はロープが適しています。

• Cedarプログラミング環境は、その誕生以来ほぼ一貫してロープを使用していた^[1]
• モデルTのエンフィレード、1970年代初頭の同様のデータ構造
• ギャップバッファは、テキストエディタでよく使用されるデータ構造で、同じ場所の近くに集められた効率的な挿入および削除操作を可能にします。
• ピーステーブル、テキストエディタでよく使われる別のデータ構造

ウィキメディア・コモンズには、ロープ (データ構造)に関連するメディアがあります。

• Abseil ライブラリ内のロープの「absl::Cord」実装
• Boehm ガベージ コレクター ライブラリ内のロープの「C コード」実装
• ロープの SGI C++ 仕様 (STLPort および libstdc++ でサポート)
• C#用のロープ
• Common Lispのロープ
• Java 用ロープ
• Java 用の文字列のようなロープ
• JavaScript のロープ
• リンボのロープ
• ニムのためのロープ
• OCamlのロープ
• Pythonの pyropes
• 雑談のためのロープ
• Swift用 SwiftRope
• Rustの「Ropey」