先日はてぶに 興味深いデータ構造:BK木 | プログラミング | POSTD という翻訳記事 ( 元記事 http://signal-to-noise.xyz/post/bk-tree/) があがっているのをみて初めて BK-tree というものを知ったので,golang で実装してみました. github.com BK-tree とは 先程の記事に全部書いてあるのですが… BK-tree は,ある距離空間内で近傍点探索を効率的に行えるデータ構造です.利用例としてはスペルチェックや類似画像検索などがあります. 距離空間とは,なにかしらの距離を計算することができる空間のことで,距離としてハミング距離やマンハッタン距離,レーベンシュタイン距離,ユークリッド距離などなどが挙げられます. 例えば,いわゆる普通の 3 次元の空間は,ユークリッド距離を距離関数に持つ距離空間と考えられます. 近傍点探索
![BK-tree を golang で実装した - 右上➚](https://cdn-ak-scissors.b.st-hatena.com/image/square/8d8c39bbd93a0a2ae1c31ff0d21917d6faec9ce1/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fa%2Fagtn%2F20170513%2F20170513183241.png)