解説: 曖昧検索アルゴリズム

(expanded from 曖昧検索asearch このページは編集しないでください)

(2018/7/28)

曖昧検索は便利なものである。「ピテカントロプス」の綴りは難しいが、最近のGoogle検索は曖昧検索対応しているようで、「 pitekantoropusu 」で検索してもちゃんと直立猿人(Pithecanthropus)がみつかる。しかし「 musogurusuki- 」でムソルグスキーを検索できないようなので、改良の余地はあるのかもしれない。

Unix系の計算機システムやプログラミング言語では曖昧な検索を行なうために正規表現を使えるものが多い。正規表現とは検索パタンとして文字列の繰り返しや文字列の選択を指定できるもので、 a* という表現で「0回以上のaの繰り返し」というパタンを指定したり、 (abc|def) という表現で「abcまたはdef」を指定したり、 a.c という表現で「aac, abc, acc, ...」を指定したりできる。たとえば pi.*ca.*pu のような曖昧なパタンを指定すれば辞書からPithecanthropusをみつけることができる。しかしPithecanthropusには k が含まれていないので、 pi.*ka.*pu からPithecanthropusをみつけることはできない。

正規表現は強力なパタンマッチ手法なのだが、 pitekantoropusu からPithecanthropusをみつけるような曖昧検索を行なうにはあまり便利ではないので、多少スペルミスがあっても検索に成功するような曖昧検索手法の方が良い。たとえば parallel に対するスペルミスとしては、

のようなものが一般的なので、このようなものに対応する曖昧検索アルゴリズムを使うと便利である。具体的には、以下のような非決定性状態遷移機械(非決定性有限オートマトン, NDFA)を使えばよい。

これは abac を曖昧検索する状態遷移機械である。左下の初期状態からはじめて、 a という入力文字があればひとつ右に遷移し、 b という入力文字あれば1行目の左からみっつ目の状態に遷移し、どんな文字であっても * が示されている状態に遷移するという具合である。これを利用すると、 aac , axbac , axac のような文字列に対しても右上の ◎ の状態への遷移が発生するので、1文字誤りのパタンを検出できることになる。

このような状態遷移機械はビットマップ演算で簡単に実装することができる。ふたつの整数変数を利用して初期状態を

と表現し、 a という入力文字があったときは

のように変化させるといった具合である。このような計算はビットシフト演算と論理演算だけで実行できるので高速に曖昧マッチングを行なうことができる。

このアルゴリズムはBitapアルゴリズムと呼ばれており、Ricardo Baeza-Yates氏が考案したものをもとにしてUdi Manber氏が曖昧検索に対応させたものらしい。Manber氏はこのアルゴリズムにもとづいた「agrep」というコマンドや「Glimpse」という検索エンジンを配布していた。Baeza-Yates氏は2016年までYahoo! LabsのVice Presidentだったようだし、Manber氏はYahoo!、Amazon、Googleで要職を務めてきたようだ。彼等はもともと大学教員だったわけだが、その後ネット検索ビジネス界で活躍してきたというのが面白い。

このアルゴリズムは便利なので、RubyやJavaScriptで簡単に使えるようにしてある。JavaScript版はScrapboxのタイトル検索で利用されており、曖昧な指定でもページがみつかるようになっている。Enjoy!

#正規表現 #曖昧検索 #検索 #ブログ #アルゴリズム #技術情報

2018/7/28