オートコンプリート事始め～「なんとなく当たる」の裏側～
自己紹介
こんにちは、サファイアです。
ナビタイムジャパンで全文検索エンジンの研究開発を担当しています。最近の悩みは頻度が上がってきたギックリ腰です。
今回のお話と対象読者
今回は「途中までの入力だけで、ユーザーが期待している入力値を先んじて表示できるようにする」機能である「オートコンプリート」について入門的なお話をすることを通じて、全文検索エンジンの奥深さの一端をお見せしたいと思っています（下図）。
STEP１：まずは候補となるスポット名の一部分を含む結果を返してみよう
早速、オートコンプリート機能が備えた全文検索エンジンを作ってみましょう。まず、図１にように「スカイ」と入力されたら「東京スカイツリー」や「梅田スカイビル」が返せるようになるものとします。
プログラムを書いたことがある方ならピンと来るかと思うのですが、コンピュータというものは基本的に融通が利きません。「スカイ」という入力に対して「東京スカイツリー」や「梅田スカイビル」を返せるようにするためには、「スカイ」と「東京スカイツリー」とを紐づけるという操作や、「スカイ」と「梅田スカイビル」とを紐づける操作をプログラマーの側でしてやる必要があります（図２）。
この紐づけ処理の実装については、「東京スカイツリー」のスポットに「スカイ」という文字列を紐づけて登録するとか、あるいはスポットの名称を形態素解析する処理を全文検索エンジンの側に入れることで「東京スカイツリー」に「東京」「スカイ」「ツリー」が紐づくようにするなどといった様々な方法が考えられます。
ですが、今回の記事では、そうした実装の詳細には踏み込まず、単に「スカイ」という文字列と「東京スカイツリー」や「梅田スカイビル」のスポットを何かしらの方法によって紐づける必要があるのだなということがお分かりいただければ十分です。
さて、これで満足のいくオートコンプリート機能が実現できたでしょうか？
STEP２：候補となるスポット名の一部分を全部紐づけてみよう
実際に全文検索エンジンを作ってみると簡単に分かることですが、実はSTEP１のような紐づけだけを行っただけではオートコンプリート機能としてはそれほど良い感じに動作しません。
というのも、ユーザーはキーボードを叩いて「スカイ」という文字列を入力した後で、そのまま「スカイツ」などの中途半端な文字列まで入力するケースも考えられるわけですが、「スカイ」という文字列だけを紐づけていた場合では、「スカイ」という入力が検索窓に入っている間は「東京スカイツリー」を返せるものの、検索窓に入る文字列が「スカイツ」になった途端に「東京スカイツリー」との紐づけが切れて、「東京スカイツリー」を返せなくなってしまうからです。
なお、『NAVITIME』のPCサイト上で動いている全文検索エンジンでは、「スカイツ」と入力しても「東京スカイツリー」との紐づけは切れなくなっています（下図）。
このような挙動を実現するにはどのようにすればいいでしょうか？そうです、「スカイツ」も「東京スカイツリー」に紐づけておけば良いのです（下図）。
ついでに「東」「東京」「東京ス」「東京スカ」「東京スカイ」「東京スカイツ」「東京スカイツリ」「東京スカイツリー」や「ス」「スカ」「スカイ」「スカイツ」「スカイツリ」「スカイツリー」なども紐づけておきましょう。『NAVITIME』のPCサイトでは、それが実現できています（下図）。
もちろん、裏側は以下のようになっています（下図）。
STEP３：候補となるスポット名の一部分をひらがなでも紐づけてみよう
これでもう十分でしょうか？いいえ、まだ現状ではイマイチ微妙な挙動となります。というのも、ユーザーはキーボードを叩きながら入力を作る際、ひらがなから漢字やカタカナへの変換を（通常は）行う以上、ひらがな入力に対応していなければ、例えば「とうきょうすかい」まで入力してもらえても「東京スカイツリー」を返却できないという事態になってしまうからです。なお、『NAVITIME』のPCサイトでは、それも実現できています（下図）。
裏側は、もう言うまでもありませんね（下図）。
STEP４：ユーザーの入力方式を意識しよう
これで流石に十分でしょうか？そろそろ満足のいくできあがりになってきたのではないでしょうか。しかし、まだ突き詰める余地はあります。キーボード入力に立ち戻って考えてみましょう。ユーザーはかな入力でひらがなを打つこともあるでしょうが、昨今はローマ字入力でひらがなを打つユーザーが多いように思われます。そうした場合、例えば「とうきょうｓ」という途中入力も考えられます（下図）
このように、ユーザーがどのように検索窓に入力を行うかを考えて、データと入力との間の関連を考え、それを全文検索エンジン内で紐づけていく……。そうした果てしない努力によって快適なオートコンプリートが実現しているのです。
忘れてはいけないあの要素
これでまとめに入れるでしょうか？いいえ、実はまだこれだけでは「快適」なオートコンプリートの実現には至りません。そうです、「レスポンスタイム」です。
例えば「東京スカイ」と入力された場合に、「東京スカイツリー」という候補を返却するのに10秒かかってしまったと仮定しましょう。その場合、ユーザーはどのように行動しているでしょうか。打鍵速度は個人差も大きいので一概には言い切れませんが、少なくないユーザーが「東京スカイツリー」という入力をし終わってしまっていそうです……。これでは、せっかくオートコンプリート機能を実装したありがたみがあまり感じられません。
データと入力との紐づけを丁寧に行いつつも、可能な限り速やかに返却を行う。そうすることで、はじめて「快適なオートコンプリート機能」の提供が可能になるのです。
まとめ
今回の記事では、全文検索エンジンの奥深さの一端をお見せするべく、オートコンプリート機能の実現について、入門的なお話をしました。ユーザーがどのように入力を行うのかを考えながらデータと入力として考えられる文字列との紐づけを丁寧に行うことと、可能な限り素早いレスポンスとの両立を実現することで、快適なオートコンプリート体験をユーザーに提供できるのだということがお分かりいただけたのではないかなと思います。
これからも様々なサイトでオートコンプリート機能に触れることが皆様おありになるのではないかと思いますが、その際にはこの小話を思い出していただけると得られる気付きもあるかもしれません。