ハッシュについて知る「なっとくアルゴリズム」

なっとく！アルゴリズム

ある高次元ベクトルと要素数が数十万くらいの配列から似ているベクトルを探したいときに時間がかかってしまい困っていた。いろいろやり方を調べると、LSH(Locality Sensitive Hashing)というアルゴリズムを使って素早く計算できるようになった。これはハッシュを使ったアルゴリズムである。アルゴリズムの内容は難しそうだったので、あまり考えずに利用していた。

書店で「なっとくアルゴリズム」という本を見つけた。これはアルゴリズムをイラストを用いてざっくりと解説している本。深い知識を得るには向いていないが、ざっくり理解したいという人には向いている本だろう。ハッシュについてあまりよくわかっていなかったので買って、興味のあるところだけ読んだ。ハッシュの基本的な仕組み、ハッシュ衝突、O(1)で探索できるというメリットがあるということがわかった。またLSハッシュ(SimHash)という近い値には似たようなハッシュ値を返すアルゴリズムもあることがわかった。(LSHとSimHashが同じなのかは知らないw)

他にも巡回セールスマン問題、幅優先探索といったテーマについても書かれてあり面白かった。