フィンガーツリー
純粋関数型データ構造

コンピュータサイエンスにおいて、フィンガーツリーは純粋に関数的なデータ構造であり、他の関数型データ構造を効率的に実装するために使用できます。フィンガーツリーは、データが格納されるツリーの「フィンガー」（葉）へのアクセスを償却定数時間で実現し、連結と分割は小さなピースのサイズに対して対数時間で行えます。また、各内部ノードには、子孫ノードに何らかの連想演算を適用した結果が格納されます。内部ノードに格納されるこの「要約」データは、ツリー以外のデータ構造の機能を提供するために使用できます。

概要

フィンガーツリーは、償却O(1)のputおよびget操作を伴う単純なキューとして使用されます。1から21までの整数が右側に挿入され、左側から抽出されます。四角いブロックは値を表し、「数字」（水色）は1～4個の子を持つことができ、「ノード」（濃青）は2～3個の子を持つことができます。白い円は「空」、赤いノードは「単一」値、緑のノードは「深い」値を表します。スパインを下るごとに、単一値と数字の子が新しいレベルのノードにネストされることに注意してください。

ラルフ・ヒンゼとロス・パターソンは、フィンガーツリーは永続的なシーケンスの機能的表現であり、その両端に償却定数時間でアクセスできると述べています。連結と分割は、小さなピースのサイズに応じて対数時間で実行できます。また、この構造は、分割操作を一般的な形式で定義することで汎用データ構造にすることができ、シーケンス、優先キュー、検索木、優先検索キューなど、様々な抽象データ型として動作させることができます。[1]

フィンガーとは、データ構造の一部にアクセスできるポイントのことです。命令型言語では、これはポインタと呼ばれます。[2]フィンガーツリーにおいて、フィンガーはシーケンスの終端、つまりリーフノードを指す構造です。フィンガーは元のツリーに追加され、フィンガーへの定数時間アクセスを可能にします。以下の図では、フィンガーはスパインからノードへと伸びる線です。

フィンガーツリーは、背骨に沿ったノードによって識別される異なる層で構成されています。木の背骨は、木に葉と根があるのと同じように、幹と考えることができます。フィンガーツリーは、背骨と側面から枝が伸びているように描かれることが多いですが、実際には、背骨の各レベルには2つのノードがあり、それらがペアになって中心の背骨を形成しています。接頭辞は背骨の左側、接尾辞は右側にあります。これらのノードはそれぞれ、根に到達するまで、背骨の次のレベルへのリンクを持っています。[2]

2～3本の木が指の木に変身しました
2～3 本のツリー(上)を引き上げるとフィンガー ツリー (下) になることがわかります

ツリーの最初のレベルは、ツリーのリーフノードである値のみを含み、深さは0です。2番目のレベルは深さ1です。3番目のレベルは深さ2、以下同様です。ルートに近いほど、ノードが指す元のツリー（フィンガーツリーになる前のツリー）のサブツリーの深さが深くなります。このように、ツリーを下っていくと、リーフからルートへと進みます。これは、典型的なツリーデータ構造とは逆です。この見栄えの良い、そして珍しい構造を得るには、元のツリーの深さが均一であることを確認する必要があります。深さが均一であることを保証するために、ノードオブジェクトを宣言する際に、子の型によってパラメータ化する必要があります。深さ1以上のスパイン上のノードはツリーを指しており、このパラメータ化によって、ネストされたノードによって表現することができます。[3]

木をフィンガーツリーに変える

このプロセスは、バランスの取れた2-3ツリーから始めます。フィンガーツリーが機能するには、すべてのリーフノードも水平である必要があります。

フィンガーとは、「特定の位置に近いツリーのノードへの効率的なアクセスを提供する構造」です。[1]フィンガーツリーを作成するには、ツリーの右端と左端にフィンガーを配置し、ジッパーのように変形する必要があります。これにより、シーケンスの両端への一定の償却時間アクセスが可能になります。

変換するには、バランスの取れた 2 ～ 3 ツリーから始めます。

ツリーの左端と右端の内部ノードを上に引き上げて、右側の図に示すように、ツリーの残りの部分がその間に垂れ下がるようにします。

スパインを組み合わせて標準的な 2 ～ 3 本の指のツリーを作成します。

これは次のように説明できる: [1] 

データFingerTree a =空|単一a |ディープ(数字a ) ( FingerTree (ノードa )) (数字a )   
    
     
          

データノードa =ノード2 a a |ノード3 a a a

示されている例の数字は、文字を持つノードです。各リストは、スパイン上の各ノードの接頭辞または接尾辞によって分割されます。変換された2-3ツリーでは、最上位レベルの数字リストの長さは2または3である一方、下位レベルの長さは1または2であるように見えます。フィンガーツリーのいくつかのアプリケーションを効率的に動作させるために、フィンガーツリーでは各レベルで1～4個のサブツリーを許容します。

ランダム2-3-4ツリーのフィンガーツリーバージョン

指木の数字は次のようなリストに変換できる: [1] 

 
数字を入力してくださいa = 1 a | 2 a a | 3 a a a | 4 a a a a

図では、最上位レベルにはa型の要素があり、次のレベルにはNode a型の要素があります。これは、ノードが背骨と葉の間にあるためです。これは一般的に、ツリーのnレベル目にはa型の要素、つまり深さ n のツリーが 2～3 本あることを意味します。つまり、 n個の要素からなるシーケンスは、深さ Θ(log n )のツリーで表現されます。さらに、最も近い端からd番目にある要素は、ツリーの深さ Θ(log d) に格納されます。[1] 北 o d e n {\displaystyle ノード^{n}}

このプロセスは、右の2-3-4ツリーのような他のツリーでも実行できます。これにより、数字は実際にはツリー内に含まれていた注釈であり、各数字は概念的に空である可能性のあるサブツリーに関連付けられていることがわかります。

削減

私 n s t 1つの n c e   R e d あなた c e   北 o d e   わ h e r e r e d あなた c e r   （ ≺ ）   （ 北 o d e 2   1つの   b ）   z ＝   1つの   ≺ （ b   ≺   z ） r e d あなた c e r   （ ≺ ）   （ 北 o d e 3   1つの   b   c ）   z ＝   1つの   ≺ （   b ≺ （ c   ≺   z ） ） r e d あなた c e l   （ ≻ ）   z   （ 北 o d e 2   b   1つの ）   ＝   （ z   ≻   b ）   ≻   1つの r e d あなた c e l   （ ≻ ）   z   （ 北 o d e 3   c   b   1つの ）   ＝   （ （ z   ≻   c ） ≻   b ） ≻   1つの {\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}}

私 n s t 1つの n c e   R e d あなた c e   F 私 n グラム e r T r e e   わ h e r e r e d あなた c e r   （ ≺ ）   （ E メートル p t y ）   z   ＝   z r e d あなた c e r   （ ≺ ）   （ S 私 n グラム l e   × ）   z ＝   ×   ≺   z r e d あなた c e r   （ ≺ ）   （ D e e p   p r   メートル   s f ）   z ＝   p r   ≺ ′   （ メートル   ≺ ″   （ s f   ≺ ′   z ） ）         わ h e r e                 （ ≺ ′ ）   ＝ r e d あなた c e r   （ ≺ ）                 （ ≺ ″ ）   ＝ r e d あなた c e r   （ r e d あなた c e r   （ ≺ ） ） r e d あなた c e l   （ ≻ ）   z   （ E メートル p t y ）   ＝   z r e d あなた c e l   （ ≻ ）   z   （ S 私 n グラム l e     × ）   ＝   z   ≻   × r e d あなた c e l   （ ≻ ）   z   （ D e e p     p r   メートル   s f ）   ＝   （ （ z   ≻ ′   p r ）   ≻ ″   メートル ）   ≻ ′   s f ）         わ h e r e                 （ ≻ ′ ）   ＝ r e d あなた c e l   （ ≻ ）                 （ ≻ ″ ）   ＝ r e d あなた c e l   （ r e d あなた c e l   （ ≻ ） ） {\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ (\prec )\ (空)\ z\ &=&\ z\\&reducer\ (\prec )\ (単一\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ (深層\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ where\\&\ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\\\&reducel\ (\succ )\ z\ (空)\ &=&\ z\\&reducel\ (\succ )\ z\ (単一\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (ディープ\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ ここで\\&\ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}}

デキュー操作

フィンガーツリーは効率的なデキューも実現します。構造が永続的であるかどうかに関わらず、すべての操作はΘ(1)の償却時間で実行されます。この解析は岡崎の暗黙的デキューと比較できますが、唯一の違いはフィンガーツリー型がペアではなくノードを格納する点です。[1]

応用

フィンガーツリーは他のツリーの構築にも使用できます。[4]例えば、優先度付きキューは、ツリー内の子ノードの最小優先度で内部ノードにラベルを付けることによって実装できます。また、インデックス付きリスト/配列は、子ノードの葉の数でノードにラベルを付けることによって実装できます。その他の応用としては、後述するランダムアクセスシーケンス、順序付きシーケンス、区間木などがあります。[1]

フィンガーツリーは、O(1) のプッシュ、リバース、ポップ、O(log n) の追加と分割といった償却処理を実行でき、インデックス付きまたは順序付きシーケンスにも適応できます。また、他の関数型データ構造と同様に、フィンガーツリーは本質的に永続的であり、つまり、ツリーの古いバージョンは常に保存されます。

ランダムアクセスシーケンス

フィンガーツリーはランダムアクセスシーケンスを効率的に実装できます。これにより、n番目の要素へのアクセスや特定の位置でのシーケンスの分割といった高速な位置操作がサポートされます。これを実現するために、フィンガーツリーにサイズをアノテーションします。[1]

newtype Size = Size { getSize :: N }の派生( Eq 、Ord )       
    

インスタンスモノイドサイズ∅ =サイズ0サイズm ⊕サイズn =サイズ( m + n )​

Nは自然数を表します。この型は異なるモノイドを運ぶため、新しい型が必要になります。また、以下に示すシーケンスの要素にも、さらに新しい型が必要です。 

newtype Elem a = Elem { getElem :: a } newtype Seq a = Seq ( FingerTree Size ( Elem a ))        
        

インスタンスMeasured ( Elem a ) Sizeここで|| Elem || = Size 1

これらのコード行は、インスタンスがサイズを測定するための基本ケースとして機能し、要素のサイズが1であることを示しています。Haskellでは、ライブラリ内ではSize型とElem型がラッパー関数によってユーザーから隠蔽される ため、 newtypeの使用は実行時ペナルティを引き起こしません。

これらの変更により、シーケンスの長さを定数時間で計算できるようになりました。

初版

フィンガーツリーは1977年にレオニダス・J・ギバスによって初めて公開され、[5] 、その後定期的に改良されてきました（例えば、 AVLツリーを使用したバージョン、[6]、非遅延フィンガーツリー、ここに示したより単純な2～3フィンガーツリー、[1]、 Bツリーなど）。

実装

フィンガーツリーはHaskellコアライブラリ（ Data.Sequenceの実装）で使用され、 OCamlでの実装も存在します[7]。これは正しいことが証明されたRocq実装から派生したものです[8] 。また、 Isabelle（証明支援系）にも検証済みの実装があり、そこからHaskellや他の（関数型）言語のプログラムを生成できます[ 9]。フィンガーツリーは遅延評価の有無にかかわらず実装できますが[10]、遅延評価によってより単純な実装が可能になります。

参照

参考文献

  1. ^ abcdefghi Hinze, Ralf; Paterson, Ross (2006)、「フィンガーツリー：シンプルな汎用データ構造」（PDF）、Journal of Functional Programming、16 (2): 197– 217、doi :10.1017/S0956796805005769、S2CID  6881581。
  2. ^ ab Gibiansky, Andrew. 「Finger Trees - Andrew Gibiansky」. andrew.gibiansky.com . 2017年10月26日閲覧。
  3. ^ 「Finger Trees Done Right (I hope)」。Good Math, Bad Math 。 2017年10月26日閲覧。
  4. ^ Sarkar, Abhiroop. 「Finger Tree - 究極のデータ構造？」abhiroop.github.io . 2017年10月26日時点のオリジナルよりアーカイブ。 2017年10月26日閲覧。
  5. ^ Guibas, LJ ; McCreight, EM; Plass, MF; Roberts, JR (1977)、「線形リストの新しい表現」、第9回ACMコンピューティング理論シンポジウム会議記録、pp.  49– 60。
  6. ^ Tsakalidis, AK (1985)、「局所探索のためのAVLツリー」、情報制御、67 ( 1–3 ): 173– 194、doi : 10.1016/S0019-9958(85)80034-6。
  7. ^ Camlウィークリーニュース
  8. ^ Matthieu Sozeau :: Coq の依存フィンガーツリー
  9. ^ ノードホフ、ベネディクト;ケルナー、ステファン。ピーター・ラミッヒ（2010年10月28日）。 「フィンガーツリー」。正式な証拠のアーカイブ。2021 年11 月 26 日に取得。
  10. ^ Kaplan, H.; Tarjan, RE (1995)、「再帰的スローダウンによる連鎖化を伴う永続リスト」、第27回ACMコンピューティング理論シンポジウム論文集、 93～ 102ページ 。
  • http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
  • http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
  • C# の 2～3 個のツリーの例
  • ジャワ島におけるヒンゼ/パターソンフィンガーツリーの例
  • C# における Hinze/Paterson フィンガーツリーの例
  • Haskellにおけるモノイドとフィンガーツリー
  • Clojure 用のフィンガーツリーライブラリ
  • Scalazのフィンガーツリー
「https://en.wikipedia.org/w/index.php?title=Finger_tree&oldid=1311884107」から取得