作成2012年12月21日
改訂2012年12月28日
改訂2013年1月10日
インクリメンタルサーチの実装
インクリメンタルサーチとは
インクリメンタルサーチ(incremental search)とは、入力のたびごとに即座に候補を表示させる検索方式で、逐語検索、逐次検索とも言われている。多くの検索エンジンは、インクリメンタルサーチ機能を提供している。我々は検索語をすべて入力しなくても、入力の度に候補語が表示され、候補語を選ぶと検索ができるため、大変重宝している。
インクリメンタルサーチは登録されている語彙を対象とする。従って、登録されていない語彙は候補語として挙がってこない。一方で”揺らぎ”が多い日本語には大変向いた検索方式と考える。日本語の揺らぎとして、例えば、”インターフェース”、”インタフェイス”などで登録されていた場合、インクリメンタルサーチでは、入力した”インタ”の候補語として、前述の語彙が候補と挙がってきて、”揺らぎ”に対応できる。
今回、インクリメンタルサーチの実装を行い、インクリメンタルサーチの有用性を検討する。
ベースとした資料
Succinct
Data Structures: Cramming 80,000 words into a Javascript
file.
（Trie木をコンパクトにメモリ格納、高速検索に対する解説、Javascriptサンプルを掲載）
http://stevehanov.ca/blog/index.php?id=120
Trie implementation in Javascript
（Trie木コードの簡単解説）
http://odhyan.com/blog/2010/11/trie-implementation-in-javascript/
日本語入力時に発生するキーイベントのテスト
http://freefielder.jp/lab/javascript/im.html
HTMl5
LocalStorageの容量や動作を調べるページ
http://www.yoheim.net/labo/html5/localstorage/checkLocalStorage.html
インクリメンタルサーチの実装概要
”Succinct Data Structures: Cramming
80,000 words into a Javascript file.”では、アルファベット26文字を5ビット及び終端情報1ビットで現わした圧縮trie木で、80,612ワード（テキストファイルで611KB）を216KBに圧縮格納でき、かつ高速検索ができる。検索データはエンコード、デコード機能もあり、JSONデータとしてデータベースに登録もできる。大変優れたコードであるが、trie木を用いたワード検索に留まり、インクリメンタルサーチには対応していない。
このコードをベースに、日本語によるインクリメンタルサーチを実装した。
・ベースとなるコードは完全一致検索もので、配下のノード情報を列挙するようにする。
・インクリメンタルサーチでキーを求め、このキーから対応するバリューを求める。
・バリュー部は、JSON記述に従い、多様なデータに対応する。
・データの永続化について、今回、ブラザーのローカルストレージを利用する。
・ローマ字入力、ひらがな入力に対応し、"tu"・"tsu"、"si"・"shi"などの揺らぎに対処する。
トライ木について
トライ木（Trie）とは、順序付き木構造 (データ構造)の一種で、プレフィックス木（Prefix Tree）とも呼ばれる。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応していることが特徴である。下図はその特徴を示し、8個の語彙がトライ木の13個のノードに展開されている様子が理解できる。語彙サーチについて、ワード長分の走査を行うことで、語彙がサーチできることも示唆している。
データの永続化と利用データ
HTML5の登場によりWeb Storageが利用できる。Web StorageにはsessionStorageとlocalStorageがあり、sessionStorageはブラウザーが閉じると保存内容も消滅するが、localStorageは、ブラウザー内に永続的に内容の保存ができる。Web Storageのデータ構造は、Key-Value型で、Valueの中にいろいろな情報を記述するため、JSON形式で利用することが多い。気になる保存容量は5MB（W3Cの仕様）である。
今回、”日本全国駅名一覧”の9,155件（636KB）のデータ（駅名、読み、所在地、路線名）を利用する。
データ永続化のためlocalStorageを用い、keyは駅名の読みをローマ字変換したもの、valueは駅名、読み、所在地、路線名をJSONで記述したデータとし、読みローマ字に従いトライ木を構築し、このトライ木もまたlocalStorageに保存する。
データサンプル
key : "aioi"
value : "{\"station"\:[{\"name\":\"相老(あいおい)\", \"location\":\"群馬県桐生市\", \"rail\":\"東武桐生線, わたらせ渓谷鐵道わたらせ渓谷線\"}]}"
localStorageのデータの読み書き
ローカルストレージへの書き込み、読み出しは、次の通り、大変簡単である。
//データを保存する
localStorage.setItem(key, value);
//データを取り出す
var data=localStorage.getItem(key);
//キー（key）ごとに削除
localStorage.removeItem(key);
//全データを削除
localStorage.clear();
日本語の揺らぎ
ローマ字で"tu"、"tsu"を入力すれば、共に"つ"を示す。他にも、”し”、”ふ”などがある。今回利用するトライ木はアルファベットによる木構造を構築するため、"tu"、"tsu"は異なるデータとなる（これが”揺らぎ”である）。この揺らぎを解消するため、ローマ字→ひらがな→ヘボン式ローマ字の段階を経て、入力データの正規化を図った。
プログラムの動き
”Trie木の初期化” ： ローカルストレージにTrie木データがなければ、サーバーから駅名一覧を読み込み、Trie木の作成、駅名データのローカルストレージへの保存を行う。
ローカルストレージにTrie木データがあれば、データを読み込み、メモリ上にTrie木を展開する。
”ローカルストレージ表示” ： ローカルストレージの登録件数と先頭から10件のデータを表示する。
”ローカルストレージ全削除”： ローカルストレージの登録内容をすべて削除する。
”前方一致検索” ： 半角アルファベット入力による駅名の前方一致検索を行う。
”インクリメンタルサーチ” ： 駅名のインクリメンタルサーチを行う。
アルファベット入力で、半角でも、全角でもOK。
”日本全国駅名一覧”には、9,155駅があり、ユニークな読み（key）は8,483件であった。keyデータは87.7KB 、これらをtrie木に57.2KBで格納できた。駅名の重複情報は、ローカルストレージのvalueのJSON配列に格納し、9,155駅の情報（636KB）をローカルストレージに保存した。インクリメンタルサーチの検討が終わったら、ローカルストレージの内容削除を勧める。
制限
・数字、記号に対応していない。
動作確認
IE9
、
GoogleChrome
、
FireFox
、
FireFoxでは、ひらがな入力に対応できていない。
IE9では、なぜか、ブラウザーを閉じると、ローカルストレージが消えてしまう。
結果
今回、ベースとしたトライ検索プログラムでは、トライオブジェクトをエンコード、デコードする機能があり、トライ木情報の永続性が可能となり、KVSの利用、インクリメンタルサーチの検討へとなった。
いくつかのプログラムを組み合わせ、インクリメンタルサーチが実装でき、今回採用した駅名のインクリメンタルサーチにおいて、僅かなキータッチで求めたい駅名にたどり着けた。インクリメンタルサーチは有用で、アプリケーションへの組み込みで、利用者への利便性をもたらすものと感じた。
KeyValue型データベース（KVS）は高速検索を特徴とする。この高速検索を生かすためには、キーを工夫することが必須となる。今回の例では、検索のインデックスとなる部分にtrieオブジェクトを利用し、KVSと合わせ、高速検索が実現できた。
今回の実装はブラウザー上で行った。1万件程度で、更新が頻繁でないデータは、ローカルでも十分であろう。今回のコードを、node.js、CouchDBなどのKVSを利用すれば、そのままサーバーに移行することもできる。
GoogleMap表示
検索結果の駅名をクリックすると、右側に駅周辺の地図、緯度経度、東京駅からの直線距離が表示される。地図表示は、Google Maps JavaScript API V3 サービスを利用。
作成 大坂哲司