データ構造におけるフィンガー探索とは？仕組みと主要な実装方法を徹底解説

フィンガー探索（finger search）とは、データ構造が本来サポートする探索操作を拡張した手法で、クエリとともに構造内の特定要素への参照（これを「フィンガー」と呼びます）を与えることができる探索です。通常の探索時間は構造内の要素数の関数として表されることが多いのに対し、フィンガー探索の所要時間は、対象要素とフィンガー（基準点）との距離の関数として扱われる点が大きな特徴です。

フィンガー探索の基本的な考え方

m個の要素からなる集合において、2つの要素aとbの距離 d(a, b) は、両者のランク（順位）の差として定義されます。たとえば要素aとbがそれぞれ構造内でi番目とj番目に大きい要素であれば、ランクの差は |i − j| となります。ある構造での通常の探索が O(f(m)) の時間を要するとき、フィンガーbから要素aへのフィンガー探索は、理想的には O(f(d)) の時間で完了すべきものです。

d ≤ m が常に成り立つため、最悪ケースでもフィンガー探索が通常の探索より遅くなることは理論上ありません。しかし実際には、こうした「退化した」フィンガー探索は通常の探索よりも多くの処理を行うことになります。たとえば f(n) = log(n) であり、フィンガー探索が最悪ケースで通常の探索の2倍の比較回数を要する場合、d > √n のときにはフィンガー探索のほうが遅くなります。したがって、フィンガー探索を実装すべきなのは、探索対象が実際にフィンガーの近くにあると合理的に期待できる場合に限られます。

実装方法の概要

広く使われているデータ構造の中には、構造自体に変更を加えることなくフィンガー探索をサポートできるものがあります。「要素aの探索を、aが存在しうる区間を絞り込む形で行う」タイプの構造では、要素bからのフィンガー探索は、探索区間が十分に大きくなって要素aを含むまで、bからの探索過程を逆方向に展開し、その後は通常どおり探索を進めることで実現できます。

ソート済み連結リストでの実装

連結リストでは、通常、片端からもう一方の端へ走査する線形探索を行います。連結リストがソートされており、要素bを含むノードへの参照を持っているならば、探索をbから開始することで、要素aを O(d) の時間で発見できます。

ソート済み配列での実装

ソート済み配列Bでは、通常は二分探索によって要素aを検索します。フィンガー探索は、B[j] = b を起点とする片側探索（one-sided search）として実装します。二分探索は各比較の後に探索空間を半分に縮小するのに対し、片側探索は各比較の後に探索空間を倍に拡大していきます。

具体的には、片側探索のk回目の反復（a > b と仮定）において、考慮される区間は B[j, j + 2^k−1] です。B[j + 2^k−1] ≥ a となった時点で拡張を停止し、その区間に対して二分探索で要素aを特定します。ここで、片側探索が要素aを含む区間を見つけるまでにk回の反復を要したならば、d > 2^k−2 が成り立ちます。さらに、この範囲の二分探索にも約k回の反復が必要です。したがって、bからaへのフィンガー探索には O(k) = O(log d) の時間がかかります。

スキップリストでの実装

スキップリストでは、要素bを含むノードからそのまま探索を続けることで、要素aへのフィンガー探索が可能です。a < b の場合は後ろ向きに、a > b の場合は前向きに探索が進む点に注意してください。後ろ向きのケースは通常のスキップリスト探索と対称的ですが、前向きのケースは実際にはより複雑になります。

通常、スキップリストの探索が高速に動作するのは、リスト先頭のセンチネル（番兵）が最も高いノードとして扱われているためです。しかし、フィンガーとなるノードの高さは1である可能性があり、その場合は探索中に「上へ登る」操作が必要になることがあります。これは通常の探索では決して発生しない状況です。それでも、この複雑さがあるにもかかわらず、期待値 O(log d) の探索時間を達成できます。

Treap（トレップ）での実装

トレップ（treap）は、ランダム化された二分探索木（BST）として定義されます。トレップ内の探索は、他のBSTと同じ要領で行えます。トレップには、距離dだけ離れた2つの要素間の期待経路長が O(log d) になるという優れた性質があります。

したがって、要素bを含むノードから要素aへのフィンガー探索を行うには、まずbから木を上方へ辿って要素aの祖先となるノードを見つけ、そこから先は通常どおりBSTの探索を進めます。あるノードが別のノードの祖先かどうかの判定は自明ではないため、木に補助情報を持たせてこの種の問い合わせをサポートできるよう拡張すれば、期待値 O(log d) のフィンガー探索時間が得られます。

ロープ（Rope）と木構造での応用

ロープ（rope）データ構造の実装では、一般的にコード位置イテレータを使って文字列を走査します。このイテレータは、文字列内の特定の文字を指す「フィンガー」とみなすことができます。ほとんどの平衡木と同様に、ロープは根ノードだけが与えられた状態では、木の葉のデータ取得に O(log m) の時間を要します。すべての葉を読み出すには、一見すると O(m log m) の時間が必要に思われます。

しかし、わずかな追加情報を保存しておくことで、イテレータが「次の」葉を O(1) の時間で読めるように実装でき、木全体のすべての葉を合計 O(m) の時間で読み出すことが可能になります。