読者です 読者をやめる 読者になる 読者になる

使えるアルゴリズムとデータ構造 1: Nearest Common Ancestor,Range Minimum Query

これまで様々なアルゴリズムとデータ構造が提案され,またより良い物へと改善されてきた.その中のいくつかは様々な問題に応用されるような汎用的なツールとなっている.そのようなアルゴリズムとデータ構造はとても頭の良い人が考えたもので,エレガントな技や時には泥臭い仕事を駆使して一見不可能に見えるようなことを可能にしている.ここで重要なのが,そのようなアルゴリズムやデータ構造を応用したい時に,その詳細な中身を必ずしも理解する必要はないということだ.重要なのはどのような入力と出力で,それにかかる計算時間と領域はどれくらいかかるのかということだ.それさえきちんと抑えておけばそのアルゴリズムブラックボックスとして中身について理解をすることなく,新しいアルゴリズムの中に組み込める. 

そうるすると,そのような汎用的なアルゴリズムとデータ構造の存在を知っているだけでも,新しいアルゴリズムを考える上で大きなアドバンテージとなり得る.

本記事ではそのような汎用的なアルゴリズムとデータ構造について説明したいと思う.

Nearest Common Ancestor

Least Common Ancestor,Lowest Common Ancestorとも呼ばれる.木構造の中で任意のノードu, vについてuとvの共通祖先の内最も根から遠いノード,uとvから最も近いノードの事をNearest Common Ancestor(nca)と呼び,nca(u, v)と表記する.

ncaの応用として文字列処理を考えてみる.例えば,文字列集合を表すtrieを考えると任意のノードu, vについてnca(u, v)はuとvが表す文字列の最長共通接頭辞と見ることが出来る.

ncaについては以下のsurveryが詳しい.木のサイズnについてO(n)時間の前処理で任意のncaクエリをO(1)時間で返すことが出来る.

 Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory Comput. Syst. 37, 441–456 (2004)

また,以下の論文では動的な木の上でもncaクエリを定数時間で行う方法を提案している.行える木の操作は葉と内部ノードの追加,葉もしくは子供が1つの内部ノードの削除を許している.

# 動的な木の上のクエリでO(log n)時間の操作を許す方法は様々あるが定数時間で行えるのはすごい結果だ.

Richard Cole, Ramesh Hariharan: Dynamic LCA Queries on Trees. SIAM J. Comput. 34(4): 894-923 (2005)

 Range Minimum Query

任意の整数配列AについてA[i..j]の中の最小値を格納しているインデックスを求める問題.実はこの問題,NCAクエリと深い関係性がある.というのは整数配列をCartesian Treeという木構造に変換すると,任意のA[i]とCartesian Treeのノードが一対一に対応し,任意のRMQクエリがCartesian Tree上の対応するノードのNCAクエリと等価になる.

ということでRMQクエリもO(n)時間の前処理でO(1)で計算可能.

参考: Cartesian tree - Wikipedia, the free encyclopedia