BK-tree とは

BK-treeはWalter Austin BurkhardとRobert M. Keller d ( x , y ) {\displaystyle d(x,y)} によって提案されたメトリクスツリーで、離散的なメトリック空間に特化しています。単純化のために、整数離散メトリック d ( x , y ) {\displaystyle d(x,y)} を考えてみましょう。そして、BK-treeは以下のように定義される。任意の要素aがルートノードとして選択される。ルートノードは、0個以上のサブツリーを有することができる。 k番目のサブツリーは d ( a , b ) = k {\displaystyle d(a,b)=k} のようにすべての要素bの再帰的に構築されます。 BK木は、辞書「2」のおおよその文字列照合に使用できます。