BK木

距離空間のツリーデータ構造

BK木（ Burkhard-Keller木の略）は、Walter Austin BurkhardとRobert M. Keller ^{[1]によって提案された、離散}計量空間に特化して適応された計量木です。簡単に言えば、集合の任意の2つの要素間の距離を測定する方法が与えられれば、BK木は単一のルートノードと、それぞれがルートに子として接続された複数のサブツリーで構築されます。サブツリー内のすべてのノードはルートノードから等距離であり、サブツリーをルートに接続するエッジのエッジ重みは距離に等しくなります。図に示すように。また、BK木の各サブツリーはBK木です。

BK木の構造は図に示されている。部分木のすべてのノードはルートから等距離にある。

BK木は辞書内の文字列の近似マッチングに利用できる^[2]。問題は次のように定式化される。パターン文字列とテキスト文字列が与えられたとき、文字列のすべての部分文字列の中で、パターンとの編集距離が最小となる文字列を見つける必要がある。 ${\displaystyle P=p_{1}p_{2}...p_{m}}$ ${\displaystyle T=t_{1}t_{2}\dots t_{n}}$ ${\displaystyle T_{j',j}=t_{j'}\dots t_{j}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle P}$

BK木を用いる一般的な方法は、のすべての部分文字列とパターン文字列をBK木に挿入し、ルートからの距離が最小のノードを含む部分木を検索するというものです。この方法では、 の時間計算量が発生します。しかし、このアルゴリズムは非常に正確で、 への編集距離が最小となるすべての部分文字列を見つけることができます。 ${\displaystyle \Theta (n^{2})}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle \Theta (n^{2}\log n)}$ ${\displaystyle P}$

例

BK木の例

この図は、レーベンシュタイン距離を用いて得られた単語集合{"book", "books", "cake", "boo", "boon", "cook", "cape", "cart"}のBK木を示しています。 ${\displaystyle W}$

• 各ノードは文字列でラベル付けされます。 ${\displaystyle u}$ ${\displaystyle w_{u}\in W}$
• 各弧 には というラベルが付けられます。はに割り当てられた単語を表します。 ${\displaystyle (u,v)}$ ${\displaystyle d_{uv}=d(w_{u},w_{v})}$ ${\displaystyle w_{u}}$ ${\displaystyle u}$

BK ツリーは次のように構築されます。

• BKツリーのすべてのノードについて、その出口アークに割り当てられた重みは異なります。 ${\displaystyle u}$
• によってラベル付けされたすべての弧について、の各子孫は次の式を満たします。 ${\displaystyle e=(u,v)}$ ${\displaystyle k}$ ${\displaystyle v'}$ ${\displaystyle v}$ ${\displaystyle d(w_{u},w_{v'})=k}$
  • 例1：「book」から「books」への弧を考えてみましょう。「book」と{「books」、「boo」、「boon」、「cook」}内の任意の単語との間の距離は1です。
  • 例2：「books」から「boo」への弧を考えてみましょう。「books」と{「boo」、「boon」、「cook」}内の任意の単語との間の距離は2です。

挿入

挿入プリミティブは、離散メトリックに従ってBK ツリーを作成するために使用されます。 ${\displaystyle t}$ ${\displaystyle d}$

入力：

• ${\displaystyle t}$: BKツリー;
  • ${\displaystyle d_{uv}}$弧に割り当てられた重みを表します。 ${\displaystyle (u,v)}$
  • ${\displaystyle w_{u}}$ノードに割り当てられた単語を示します。 ${\displaystyle u}$
• ${\displaystyle d}$: で使用される離散メトリック （例：レーベンシュタイン距離） ${\displaystyle t}$
• ${\displaystyle w}$: 挿入する要素; ${\displaystyle t}$

出力：

• 対応するノード ${\displaystyle t}$ ${\displaystyle w}$

アルゴリズム：

• が空の場合: ${\displaystyle t}$
  • ルートノードを作成する ${\displaystyle r}$ ${\displaystyle t}$
  • ${\displaystyle w_{r}\leftarrow w}$
  • 戻る ${\displaystyle r}$
• ルートに設定 ${\displaystyle u}$ ${\displaystyle t}$
• 存在する間 : ${\displaystyle u}$
  • ${\displaystyle k\leftarrow d(w_{u},w)}$
  • もし ： ${\displaystyle k=0}$
    • 戻る ${\displaystyle u}$
  • の子を見つける ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle d_{uv}=k}$
  • 見つからない場合: ${\displaystyle v}$
    • ノードを作成する ${\displaystyle v}$
    • ${\displaystyle w_{v}\leftarrow w}$
    • 弧を描く ${\displaystyle (u,v)}$
    • ${\displaystyle d_{uv}\leftarrow k}$
    • 戻る ${\displaystyle v}$
  • ${\displaystyle u\leftarrow v}$

見上げる

検索対象要素 が与えられた場合、検索プリミティブはBK木を走査して の最も近い要素を見つけます。鍵となる考え方は、BK木構造と三角不等式（カットオフ基準）を利用して、 の探索を、これまでに見つかった最良の候補を改良できるだけのノードに限定することです。 ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle t}$

入力：

• ${\displaystyle t}$: BKツリー;
• ${\displaystyle d}$: 対応する離散メトリック（例：レーベンシュタイン距離）
• ${\displaystyle w}$: 検索された要素。
• ${\displaystyle d_{max}}$: 最適な一致と の間の最大許容距離。デフォルトは です。 ${\displaystyle w}$ ${\displaystyle +\infty }$

出力：

• ${\displaystyle w_{best}}$:に格納されている最も近い要素を検索します。見つからない場合は検索します。 ${\displaystyle w}$ ${\displaystyle t}$ ${\displaystyle d}$ ${\displaystyle \perp }$

アルゴリズム：

• 空の場合: ${\displaystyle t}$
  • 戻る ${\displaystyle \perp }$
• 処理するノードのセットを作成し、 のルートを に挿入します。 ${\displaystyle S}$ ${\displaystyle t}$ ${\displaystyle S}$
• ${\displaystyle (w_{best},d_{best})\leftarrow (\perp ,d_{max})}$
• その間 ： ${\displaystyle S\neq \emptyset }$
  • 任意のノードをポップする ${\displaystyle u}$ ${\displaystyle S}$
  • ${\displaystyle d_{u}\leftarrow d(w,w_{u})}$
  • もし ： ${\displaystyle d_{u}<d_{best}}$
    • ${\displaystyle (w_{best},d_{best})\leftarrow (w_{u},d_{u})}$
  • 各出口アークについて： ${\displaystyle (u,v)}$
    • もし ：（カットオフ基準） ${\displaystyle |d_{uv}-d_{u}|<d_{best}}$
      • に挿入します。 ${\displaystyle v}$ ${\displaystyle S}$
• 戻る ${\displaystyle w_{best}}$

ルックアップアルゴリズムの例

上記の 8 ノードの BK ツリーの例を考えてみます。はツリーのルートを含むように初期化され、その後、 ="book"での最初の値としてポップされます。さらに、 "book" から "cool" までの距離は 2 であり、これがこれまでに見つかった最良（つまり最小）の距離であるため、 となります。次に、ルートからの各出力アークが順に検討されます。 "book" から "books" へのアークの重みは 1 であり、 はより小さいため、 "books" を含むノードが に挿入され、さらに処理されます。 "book" から "cake" への次のアークの重みは 4 であり、は より小さくないため、 "cake" を含むノードは に挿入されません。したがって、 "cool" に最も近い単語はそのサブツリーには出現できないため、 "cake" をルートとするサブツリーは検索から除外されます。この枝刈りが正しい理由を理解するには、「cake」のサブツリーに出現する候補語のうち、「cool」までの距離が2未満の場合、三角不等式に違反する点に注意してください。三角不等式では、この3つの数値（三角形の辺）の集合において、2つの数値の合計が3つ目の数値より小さくなることはありませんが、ここでは「cool」から「book」までの距離（2）と「cool」からの距離（2未満）を足しても、「book」から「cake」までの距離（4）に達することも、それを超えることもできません。したがって、「cake」をルートとするサブツリー全体を無視しても安全です。 ${\displaystyle w=}$ ${\displaystyle S}$ ${\displaystyle u}$ ${\displaystyle w_{u}}$ ${\displaystyle d_{u}=2}$ ${\displaystyle d_{best}=2}$ ${\displaystyle |1-2|=1}$ ${\displaystyle d_{best}=2}$ ${\displaystyle S}$ ${\displaystyle |4-2|=2}$ ${\displaystyle d_{best}=2}$ ${\displaystyle S}$ ${\displaystyle c}$ ${\displaystyle c}$

次に、「books」を含むノードが からポップされ、今度は「cool」から「books」までの距離が になります。 は2のままで、「books」を含むノードからの単一の出力アークが考慮されます。次に、「boo」を含むノードが からポップされ、今度は「cool」から「boo」までの距離が になります。これも を改善しません。今度は「boo」からの各出力アークが考慮されます。「boo」から「boon」へのアークの重みは1で、 なので、「boon」が に追加されます。同様に、 なので、「cook」も に追加されます。 ${\displaystyle S}$ ${\displaystyle d_{u}=3}$ ${\displaystyle d_{u}>d_{best}}$ ${\displaystyle d_{best}}$ ${\displaystyle S}$ ${\displaystyle d_{u}=2}$ ${\displaystyle d_{best}=2}$ ${\displaystyle |2-1|=1<d_{best}=2}$ ${\displaystyle S}$ ${\displaystyle |2-2|=0<d_{best}}$ ${\displaystyle S}$

最後に、 の最後の2つの要素がそれぞれ任意の順序で考慮されます。「cook」を含むノードが最初にポップされ、距離が1に改善されたとします。次に、「boon」を含むノードが最後にポップされますが、「cool」からの距離は2であるため、最良の結果は改善されません。最終的に、「cook」が で答えとして返されます。 ${\displaystyle S}$ ${\displaystyle d_{best}}$ ${\displaystyle w_{best}}$ ${\displaystyle d_{best}=1}$

時間計算量

BK ツリーの効率は、ツリーの構造と、格納された要素間の距離の分布に大きく依存します。

平均的なケースでは、ツリーが比較的バランスが取れており、距離メトリックが要素を均等に分散していると仮定すると、挿入操作と検索操作の両方に時間がかかります。 ^{[3] [4]} ${\displaystyle \Theta (\log n)}$

最悪の場合、データや距離関数によってツリーのバランスが著しく崩れると（例えば、多くの要素が同じような距離にある場合）、挿入と検索の両方が に低下する可能性があります。^{[5] [6]} ${\displaystyle \Theta (n)}$

実際のアプリケーションでは、実際のパフォーマンスは距離メトリック（例えば、レーベンシュタイン距離）の選択と近似マッチング中に許容される検索半径に依存します。^[7]

参照

• レーベンシュタイン距離– BK木を構築する際によく使われる距離指標
• ダメラウ・レーベンシュタイン距離- 転置を許容するレーベンシュタイン距離の修正形

参考文献

• ^ W. BurkhardとR. Keller. ベストマッチファイル検索へのいくつかのアプローチ、CACM、1973
• ^ R. Baeza-Yates, W. Cunto, U. Manber, S. Wu. 固定クエリツリーを用いた近接マッチング．M. CrochemoreとD. Gusfield編，第5回コンビナトリアルパターンマッチング，LNCS 807，198～212ページ，カリフォルニア州アシロマ，1994年6月．
• ^ Ricardo Baeza-Yates、Gonzalo Navarro. 辞書における高速近似文字列マッチング. Proc. SPIRE'98

• ^ WA BurkhardとRM Keller. ベストマッチファイル検索へのいくつかのアプローチ. Communications of the ACM, 16(4):230–236, 1973.
• ^ R. Baeza-Yates、G. Navarro. 辞書における高速近似文字列マッチング. SPIRE'98 Proceedings, 1998.
• ^ H. Hyyro.高速文字列検索のためのBurkhard–Keller木の説明と拡張.第7回文字列処理および情報検索シンポジウム(SPIRE)の議事録,1–10ページ, 2003年.
• ^ S. MihovとK. Schulz.大規模辞書における高速近似検索. 計算言語学, 30(4):451–477, 2004.

外部リンク

• テスト結果とパフォーマンス グラフを備えた Common Lisp での BK ツリー実装。
• BK木と距離空間との関係の説明[8]
• C#での実装によるBK木の説明[9]
• LuaによるBK木の実装[10]
• PythonでのBK木の実装[11]

「https://en.wikipedia.org/w/index.php?title=BK-tree&oldid=1317722293」から取得