Location : Home > Languages > Perl > Package
Title : Algorithm::Tree::NCA
 		Toolbox Logo

名称

　Algorithm::Tree::NCA - 最近共通祖先（Nearest Common Ancestor）を求める

概要

use Algorithm::Tree::NCA;

my $tree = ...;
my $nca = new Algorithm::Tree::NCA(-tree => $tree);

my $x = $tree->get_node(...);
my $y = $tree->get_node(...);
my $z = $nca->nca($x,$y);

説明

　本パッケージはツリーにおけるノードの最近共通祖先（NCA; Nearest Common Ancestor）の定数時間取得を提供する。実装はハレル（Harel）によるアルゴリズムに基づいており、線形時間前処理の後、定数時間内に２つのノードの最近共通祖先を取得する。
　アルゴリズムを実装するためにはツリーの各ノードにいくつかのデータを格納しておくことが必要である。

　上述の全データは、ノード番号を除いて Algorithm::Tree::NCA オブジェクトの内部に配列で格納されている。
　ノードに対して set メソッド 及び get メソッドmethod を必要とする。方法で実際のツリーノードに格納されていなければならない（または遅くなるが定数時間内に取得する方法もある）。最もよくあるケースではノードを表すのにハッシュを用いるのでこれらのメソッドのデフォルトの実装としている。

　デフォルトの set メソッドは以下のようなものである。

sub _set_method {
   my($node,$value) = @_;

   $node->{'_nca_number'} = $value;
}

　デフォルトの get メソッドは以下のようなものである。

sub _get_method {
   my($node) = @_;

   return $node->{'_nca_number'};
}

　ノードに対して他の表現方法を選択した場合は、 Algorithm::Tree::NCA オブジェクトを生成する際に -set 及び -get オプションをつけることで他のメソッドを指定することができる。

クラスとオブジェクトメソッド

使用例

アルゴリズム

　このセクションでは、前処理及び最近共通祖先を取得するにあたり利用しているアルゴリズムについて記述する。なぜアルゴリズムが有効なのかについては一切説明せず、アルゴリズムがどのように機能するかについてのみ説明する。アルゴリズムの説明にあたっては、ノード自身に必要な情報が格納されていることを想定する。アルゴリズムは Pascal 風に記述している。詳しい説明については参照の [1] または [2] を見よ。
　height は非零の整数で、整数の右端のゼロの数を示す。LSSB（least significant set bit）は非零で最小有効ビットのみを示す数値である。つまりある数に対する LSSB と height は以下のようになる。

Number    LSSB       Height
--------  --------   ------
01001101  00000001   0
01001100  00000100   2

　LSSB(i) < LSSB(j) であれば、かつそのときに限り height(i) < height(j) となることは重要である。このことは height(i) < height(j) の確認を LSSB(i) < LSSB(j) で置き換えられることを意味する。LSSB(i) のほうが計算が容易なのでこのようにすれば計算は高速化するだろう。

ツリーの処理

　ツリーの前処理には３つの数値：ノード番号・ラン・マジックナンバーが必要である。各ランにはリーダの計算も必要である。これらの計算はツリーの２つの再帰的上昇・下降により計算される。

Procedure Preprocess(root:Node)
Var x,y : Integer;   (* ダミー変数 *)
Begin
   (x,y) := Enumerate(root,nil,1);
   ComputeMagic(root,root,0);
End;

　第１フェーズではツリーを列挙し、各ノードのランを計算し、サブツリーにおけるノードに与えられた最大値を計算し、各ノードの親ノードを求める。もし親ノードが他の方法で求められていたならこの処理は冗長である。ノードのランは最大の height を持つサブツリーにおけるノードの数である。

Function Enumerate(node,parent:Node; num:Integer) : (Integer,Integer)
Var run : Integer;
Begin
   node.parent := parent;
   node.number := num;
   node.run := num;

   run := num;
   num := num + 1;

   Foreach child in node.children Do
      (num,run) := Enumerate(child,node,num);
      If height(run) > height(node.run) Then
         node.run := run;
      Done
      node.max := num;
      Return (num,node.run)
End;

　第２でフェーズでは各ランにおけるリーダを計算し（各ノードに対しランを知ることができるのでこれを行うことができる）、マジックナンバーを求める。リーダはノード番号を通じてアクセスすることができるように格納されているため、配列に格納する。

VAR Leader : Array [1..NODE_COUNT] of NodePtr;

　各ランのリーダは各ノードに対し格納されているか（こちらを想定している）、 node.run == node.number を満たすノードにのみ格納されているかである。そのときはノードのリーダは Leader(node.run) を通して計算され、リーダが疎な配列として実装されていれば少ない容量しか必要としない。
　ノードのマジックナンバーはビットワイズか、ルートからそのノードまでのパスにおける全てのノードのランである。

Procedure ComputeMagic(node, current_leader:Node; magic:Integer)
Begin
   node.magic = magic | LSSB(node.run);
   If node.run != leader.run Then
      Leader(node.number) = node
   Else
      Leader(node.number) = current_leader

   Foreach child in node.children Do
      ComputeMagic(child, Leader(node.number), node.magic)
   Done
End;

　

最近共通祖先の取得

　２つのノードの最近共通祖先を探索するには２分木にノードをマッし、最近共通祖先 b を求める（これは簡単）。２つのノードのマジックナンバーが共通に 1 であり、height が b より大きくなるようなビット j を探索するというビットワイズ計算を行う。

Function NCA(x,y:Node) : Node;
Begin
   b  := BinNCA(x,y);          (* b = 10111000 *)
   m  := (NOT b) AND (b - 1);  (* m = 00000111 *)
   c  := x.magic AND y.magic;
   u  := c AND (NOT m);
   j  := LSSB(u);
   x1 := Closest(x,j);
   y1 := Closest(y,j);
   If x1.number < y1.number Then
      Return x1
   Else
      Return y1
End;

　２分木において最近共通祖先を取得するにはノード番号の簡単ではあるが特殊な付け方を想定する。ルートのノード番号を 10000000 として、ツリーを下るにつれて（例えば）左にいけば 0 、右に行けば 1 となりようにパス番号を各ノードに付与していくのである。ルートから各ノードへ名同一のパスにはなりえないので以下の処理すればよい。

  1. パス番号の XOR を計算する。
  2. XOR において最上位の 1 （そこでパスが異なる）を探索する。
  3. パスナンバーから最上位の 1 より前（すなわち高位の）部分をとる。（これらの部分は同等であるから他のものをとってもよい。）
  4. 1 を加える。
  5. 1 以降の低位に全て 0 を付与する。

　返り値は最近共通祖先であるノードのパス番号である。（今回の実装ではノード番号からランへのマッピングはランがパス番号である２分木へのマッピングである。）

Function BinNCA(x,y:Node) : Integer
Var k,m,r : Integer;
Begin
   (* Check that neither is the ancestor of the other *)
   If x.number <= y.number and y.number < x.max Then
      Return x.run
   If y.number <= x.number and x.number < y.max Then
      Return y.run

   (* Suppose x.run = 10110--- and y.run = 10111--- *)
   (* Then x.run XOR y.run = 00001---, and further: *)
   k := MSSB(x.run XOR y.run); (* k = 00001000 *)
   m := k XOR (k - 1);         (* m = 00001111 *)
   r := (NOT m) AND x.run;     (* r = 10110000 *)
   Return r OR k;          (* result: 10111000 *)
End;

　最近共通祖先 z と同じラン上にあるノード n に最も近いノードを探索するには、上記の NCA 関数で提供された j が必要である。

Function Closest(n:Node; j:Integer) : Node;
Begin
   l := LSSB(n.magic);
   If l = j Then Return x
   k := MSSB((j - 1) AND x.magic);
   u := ((NOT ((k - 1) OR k)) AND x.run) OR k
   w := Leader(u);
   Return w.parent;  (* z = w.parent *)
End;

参照

  1. Fast algorithms for finding nearest common ancestor by D. Harel and R. E. Tarjan.
  2. On finding lowest common ancestor: simplifications and parallelizations by B. Schieber and U. Vishkin.
  3. Algorithms on strings, trees, and sequences by Dan Gusfield.

著者

　Mats Kindahl, <matkin@acm.org>

参考資料

　Perl

Toolbox Logo
 Updated : 2007/07/20