最近傍探索のあれこれ 主にk-d tree: 御手洗特急途中下車
メモ書き． 全探索 (線形探索) 最も単純な方法は全探索である．注目点から空間中の全点の距離を測り， その距離が最小になる点を最近傍点とする．なお，計算量はO(n) k-d tree (k-dimensional tree) 上手に二分木をつくることで探索空間を二分探索することが可能．最も有名なのがk-d tree． どうやって木をつくるか 簡単のため2次元で考えると手順は以下のようになる． 1. x軸に平行(別に垂直でもよい)に空間を二分割する．上下でノードをつくる 2. y軸に平行に空間を二分割する．左右でノードをつくる 3. x軸に平行に空間を二分割する．上下でノードをつくる 4. ・・・ これを再帰的に繰り返す． 分割とk-d tree どうやって空間を二分割するか 図では簡単のために単純にど真ん中で空間を分割しているが， 点の座標値の中央値で分割するとk-d treeは平衡木にな
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
