#20 Amazon CloudSearchで検索サジェスト機能を作った話

AdventCalendar2014 aws lobi

tech.kayac.com Advent Calendar 2014 20日目を担当する@ken39argです。

近況報告

お久しぶりです。

前回ブログを書いたのが、2012年のアドベントカレンダーでしたので、2年ぶりということになります。

前回のブログの出だしが、 「最近子供が産まれた」 でしたが、
4日前の 12/16の朝に2人目の男の子が産まれ、 本日嫁と子供が病院から帰ってました。とてもバタバタしております。

長年、特にFlashLiteの動的生成などを得意分野としてガラケーを始めとするケータイ向けブラウザゲームを作ってきましたが、
昨年末から心機一転 LobiチームにJoinして、主にLobi REC SDKのサーバーサイドの開発を担当しています。

今年も様々な人やサービスの助けを借りてオートスケールする動画変換サーバーやニコニコ動画へのアップロード、 プレイ動画を見るためのLobi Playなど様々なサービスや機能を作らせていただきました。

中でも今年一番知恵を絞ったのが、このエントリーで紹介するLobi Play 及びLobi REC SDKで利用している 「動画検索のキーワードサジェスト機能」 です。

サジェスト機能とは、検索キーワード入力時に入力したいキーワードを予測しキータイプ毎に候補を提案する機能のことです。

サジェストスクショ

サジェスト機能は、Google検索やSpotlightなどあまりに身近な場所に、あたりまえに存在するため、特に非エンジニアの方々にはとても簡単に作れるように思われがちです。

しかし、ホントはものすごく難しいということを僕は声を大にして言いたい。(そもそも検索機能ですら...)

正直実装は不可能だと思っていて「どうやって誤摩化すか？」そんなことを長いこと考えていました。 (愚痴や暴言を吐き散らかして嫌な思いをさせてしまった皆さん。ごめんなさい)

しかし不思議なもので、人間追い込まれるとなんとかなるようで、毎日少しずつ試行錯誤していくうちにそこそこに満足のいくものができてしまいました。

ですから、もし、軽い気持ちで「サジェスト機能作って」と言われ、逃げ出したくなったエンジニアが僕以外にもいたら、この記事を読んで少しでも心を落ち着かせていただければと思います。

Lobi REC SDK のサジェスト機能の要件定義

Lobi REC SDKにおけるサジェスト機能(検索機能)には、 動画検索であること と 様々なゲームに導入していただくSDKであること より下記の特徴的な要件が求められます。

  • 各SDKとLobi Playそれぞれに対して異なるサジェストをする
  • 動画データにはタイトルやタグ、投稿者、ゲーム名など複数のメタデータがありそれぞれサジェストしたい

前者については、各SDK毎にボス名やクエスト名など固有の名称での検索が多くなると予測出来ますが、異なるゲームのボス名などがサジェストされてしまっては意味が無いので、 それぞれのゲームで存在するワードだけをサジェストしなければなりません。
また、あらゆるゲームの動画を横断的に検索できる Lobi Play ではできるだけゲームのタイトル名を優先してサジェストしたいという思いがあります。

後者については、Lobi REC SDK ではとにかく「動画投稿の敷居を下げたい」「気軽にアップロードして欲しい」という思いでつくっておりますので、 どうしてもタイトル等を編集しないユーザーが多くなるため、ゲーム側が指定した同じようなタイトルが多く並んでしまいます。
また、攻略情報や面白い実況主など、検索したいシチュエーションも多様ですので、タグの情報でサジェストされることが求められます。

さらに、できれば、各SDKではそのゲームタイトルはサジェストされないようにしたいものです。

Lobi REC SDK の検索サジェスト機能の実装上の特徴

紆余曲折を経て、下記の様な特徴を持つサジェスト機能が出来上がりました。

  • Amazon CloudSearchを採用
  • 検索用とサジェスト用で2つのドキュメントを利用
  • MySQLも併用
  • ユーザーの検索キーワードを利用した学習型

Amazon CloudSearchを採用した理由

検索機能をつくるとなるとAmazon CloudSearchの他にもElasticsearchやSolr、 あるいはGoogleのカスタム検索エンジンなど様々な選択肢がありますが、 以下のような理由でAmazon CloudSearch を選択しました。

  • スケーラビリティが容易(というか不要)
  • Lobiでの採用実績(ユーザー検索やグループ検索で既に利用していた)
  • 導入が簡単(ただでさえ複雑なLobiのサーバーにこれ以上新たなものを入れたくない)
  • CloudSearchにはSuggest APIというそのものズバリの機能があった

新たなアーキテクチャを採用するという選択もアリだったのかもしれませんが、 新しいものを入れるとそれに伴ってやらなければならないこと(chef receipを作ったり、それを扱うモジュールを選んだり作ったり、そのテストを書いたり、未知の問題の対応方法を決めたり)があまりにも多いので、そういうのがとてもメンドクサイので開発速度を優先して見送りました。

Suggest APIのざっくりとした使い方

詳細は日本語ドキュメントもありますので割愛しますが、 下記のようなことをすれば導入することができます。

  1. Suggesterを登録
  2. Suggesterには下記を指定
  3. Name - 一意の名前
  4. Source Field - documentのどのフィールドをサジェストするか(1フィールドのみ指定)
  5. Fuzzy Matching - 曖昧検索(None=完全一致、Low=1文字違い、High=2文字違い)
  6. Sort Expression - 表示順を決める式
  7. Suggesterを指定してAPIにリクエスト
  8. 例 - /2013-01-01/suggest?suggester=mysuggester&q=ひめき

Source Field についての注意点

良識ある優秀なエンジニアの皆さんならそんな勘違いをしないと思いますが、僕は過度に期待しすぎてしまったために袋小路に何度か追い込まれてしまいました。

  1. 1つのtext型のフィールドしか選べない
  2. 形態素解析やN-Gramなどのワード抽出はしてくれない

1. 1つのtext型のフィールドしか選べない

例えば下記の様なCloudSearchドキュメントの場合

  • id - int
  • title - text
  • description - text
  • username - text
  • tag - text-array

titleもtagもusernameも全てサジェストするということはできないのです。

(たしかtext-arrayも指定出来なかった気がするんですが、もしかしたらできるかもしれません)

2. 形態素解析やN-Gramなどのワード抽出はしてくれない

1つのtextフィールドしかえらべないのなら、 1つのフィールドに複数の単語をいれておけば 、よしなになるんじゃないか？
という 幻想は通じない ということです。

たとえば、for_suggestというフィールドを用意して「モンスターストライク イザナギ クリア スピクリ ノーコン」という値を入れておいたとしても、 モンスターストライク、イザナギ、クリア、スピクリ、ノーコンがそれぞれサジェストされるなんてことはなく、 「もん」に対して「モンスターストライク イザナギ クリア スピクリ ノーコン」とサジェストされてしまいます。

つまり、1つのドキュメントで複数サジェストして欲しいフィールドがある場合は知恵を絞る必要が出てきます

Sort Expression に対する注意点

  1. Searchに対するExpressionsとは異なり_scoreは使えない
  2. Sort Expression毎にSuggesterを作ろうとしてもSuggesterは10個までしか作れない

1. Sort Expressionに_scoreは使えない

つまり並び順は自分で定義するかお任せか二者択一ということです。

Searchの場合は自分で定義した重みづけとCloudSearchが重み付けしたキーワードの関連度(_score)をバランス良く配合できるのですが、Suggesterでは合わせ技はできません。

とはいえ、自分で定義したSort Expressionが同じ場合は、CloudSearchが重み付けした順でサジェストされます。

2. Suggesterは10個までしか作れない

この制約を知らずに実装してしまい、僕は一度絶望の淵に落とされてしました。

その時は、SDK毎に異なる結果を返すためにドキュメントにappというフィールドを用意し、下記のようにSort Expressionを指定しました。

Sort Expression = app == 1 ? score : 0

このようにSDK導入ゲームの数だけSuggesterを作ろうとして実装したのですが、10アプリで登録したところで追加出来なくなり書いたコードは全て無駄になってしまいました。

つまり、Sort Expressionが無限に増える（もしくは10以上に増える) 仕様においては利用することができません。

それでも CloudSearchでSuggest APIを使う

さて、めちゃくちゃ地雷を踏みましたが（避けれた地雷も沢山ありますが）それでも CloudSearch で実装したかったので、工夫をして実装することにしました。
具体的には、上記の制約をそれぞれ解決する方法を実現しました。

  1. Source Fieldの制約による、検索対象:サジェスト対象=1:N 問題
  2. Sort Expressionの制約による、SDK毎に出し分けられない問題

検索対象:サジェスト対象=1:N 問題の解

「検索結果用とサジェスト用とドキュメントを２つ作る」

この問題に直面しそれでもCloudSearchを使うとなると、もはや他の選択肢は無い気がします。

Suggestのためだけに新たにドキュメントを作り、サジェストしたい単位に分割したキーワードをtext型のフィールドに持たせることになります。

Suggest専用ドキュメントを作る際の注意点

僕がハマって絶望の淵に追い込まれた事案です。

Suggest専用ですので実際にこのドキュメントに対して検索をすることはありまんが、
CloudSearchのサジェスト機能は、おそらく検索キーワードを使って学習しているため、 検索で使われないとサジェストされることは無いようです。

また、ドキュメントを削除してもIndexしないと消えないようです。
おそらくサジェストに求められるパフォーマンスを達成するための強いキャッシュなどをしているのでしょう。

以上より、定期的に下記を実行する必要がある気がします。

  • 一定期間に追加したキーワードを使ってsearch APIを使う
  • PostgreSQLのvacuumのように定期的なIndexingを実行する

searchもindexも費用が発生しますので頻度は慎重に行う必要があります。

※ この項の内容は、そこで発生した事実を元にした予測ですので誤りがある可能性があります。
　 有識者の方、もっと良い方法があったら是非教えてください！！！

SDK毎に出し分けられない問題の解

「MySQLを併用する」

例えば、ドキュメントを各ゲーム毎に用意するという案もありましたが(実際には10ゲーム毎に1ドキュメント)、正直Lobi REC SDKは無料で提供しているため費用的に現実的ではありませんでした。

そこで、MySQLと併用しSuggest用ドキュメントのコピーをMySQLのテーブルとして作成し、Suggest APIの結果をMySQLでフィルタリングするという手法を取りました。

  • スキーマ
CREATE TABLE suggest (
    id       BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
    app      INTEGER UNSIGNED NOT NULL DEFAULT 0,  -- 出しわけたい環境毎に異なる
    word     VARCHAR(255) NOT NULL,                -- サジェスト単位に分割したキーワード
    score    INTEGER UNSIGNED NOT NULL,            -- `Sort Expression`で利用するスコア
    PRIMARY KEY (id),
    UNIQUE app_word_uniq (app, word)
);
  • 処理の流れ(※このスクリプトはめちゃくちゃです)
# CloudSearchによるサジェスト
## sizeを大きめに指定
$res = $ua->get( 'https://foo.cloudsearch.amazonaws.com/2013-01-01/suggest?suggester=bar&size=50&q=あいう' );
my $cs_result = decode_json( $res->content )->{suggest}{suggestions};

# MySQLによってゲーム毎に必要なものだけに間引く
my $real_result = $dbh->selectall_arrayref( 'select word from suggest where app = ? and word in (?)' );

SDK毎に出し分ける工夫

上記の対応でSuggesterが不要になったような気がしましたが、そんなことはありません。

例えば、ゲーム数が100あった場合均等に動画がアップロードされていたとしても、Suggestで候補を100引いてきてもその中に含まれる期待値は1個です。

そこで、Suggesterを複数作り各SDK毎にいずれかのSuggesterに属するようにしました。 このようにすることで例えば5つSuggesterを作るとSuggest対象が1/5になりますので、1回のリクエストでヒットする期待値が高くなります。

Sort Expression = app % 5 == 1 ? score : 0

このようにすることで、不要なデータは結果の後ろに回ります。（0にしても結果には含まれますが並び順が最後尾になります）

また、もし特別にデータの多いゲームがあったとしても最大で5個まで専用のSuggesterを作ることができますのでしばらく凌ぐことができます。

サジェスト用のキーワードをどのように選んだか

さて、仕組みとしては要件を満たせるようになってきました。

しかし、意味のあるサジェストをするために、キーワードとscoreをどのようにするかが問題になります。

最初は各動画毎にsuggestされたい項目(title, tag, username, gamename)をキーワードとしscoreは一律としましたが、
あまりイケていなかったため、以下のような欲が出てきました。

  • descriptionに含まれる単語も使いたい
  • titleは単語毎にわけたい
  • ユーザーに求められているキーワードをサジェストしたい

もし、最後の欲が無かったら僕はMeCab等をつかって形態素解析をしようとやっきになっていたかもしれません。
しかし最後の欲があったからこそ今選んだ方法を取ることができました。

「ユーザーの使った検索ワードを学習する」

非常にシンプルな解ですが、キーワード登録とスコアリングのルールは以下のようになっています。

  1. ユーザーの検索ワードがヒットした場合にそのワードを登録
  2. 検索された数=scoreとする

※ 2014/12/20現在、検索数=scoreではありません。

このようにすることで、形態素解析の必要もなく、 検索で使われている全てのフィールド がサジェストの対象となり、よく使われるキーワードがサジェストされるようになりました。

精度向上のために

実はここからが本編なんじゃないかというくらいなのですが、既に十分に長くなってしまったので、さらりと書いて行きたいと思います。

あたりまえっぽいですが、ユーザー入力を利用した学習型のサジェスト機能の精度を上げるには、 以下のポイントをどのようにクリアするかという問題があります。

  • 価値の高いデータを強調する
  • 価値の低いデータを間引く

これは非常に難しいのですが、少し頑張れば目に見えて結果が向上します。

価値の高いデータを強調する方法

ただサジェストされるだけでは意味がありません。

入力したいキーワードをできるだけ早くサジェストすることで良い体験をしてもらうことができますし、そうでないとサジェスト自体が意味が無いものになってしまいます。

  1. 手動で強調
  2. 機械的に予測して強調

何言ってるんだ？当たり前だろ？というかんじですね。。。

1. 手動で強調

手動での強調は単純だけど最も難しく最も効果的です。

例えば、ゲーム等でイベントがあった場合、まだ使われている回数は少ないけど需要は高いはずです。そんなときは手動でscoreを上げる方法を用意しておくと良さそうです。

ただし、Lobi REC SDKでは、手動で強調する手段は用意していますが、後述の理由でほとんど使っていません。

2. 機械的に予測して強調

特にLobi REC SDKの場合は様々なゲームに導入していただくSDKですので、手動で強調する場合に必須となる「キーワードを把握する」ことが困難です。

そこで、価値が高い可能性のあるキーワードを機械的に予測し強調することにしました。

「頻繁に投稿されるキーワードは頻繁に検索もされるだろう」という仮定を立て、 投稿された動画のタイトルやタグなどのキーワードの出現回数を元に強調しています。

価値の低いデータを間引く方法

上記の強調よりはるかに重要なのがこの 間引く ことです。

  1. 手動で間引く
  2. 文字数の少なすぎるデータを間引く
  3. ほとんど使われないキーワードを間引く
  4. 特定のキーワードと同じ意味だが異なるものを間引く

良い方法が他にもあったら教えてもらえるととても嬉しく思います。

1. 手動で間引く

強調と同じく単純にして最強で最も難しい方法です。

いわゆるNGワードや、誹謗中傷に当たるキーワード、「あいう」など全く意味が無いけど入力されがちなキーワードなど、 自動的に間引くのが困難なキーワードは見つけ次第手動で間引けるようにする必要があります。

今回の方法だとMySQLからDELETEしてしまえばとりあえず表には出なくなるので即時性がありますが、CloudSearchからもdeleteするような仕組みも作りました。

これも運用が非常に難しく、意識的に検索機能を利用しておかしなキーワードを見つけたら逐次間引くという地道なことを僕がしているというのが現状です。
とても継続性の低い運用です...

2. 文字数の少なすぎるキーワードを間引く

「あ」や「い」など一文字のキーワードは検索に大量に引っかかりますし、キーワードとしてもよく使われますが、はっきり言って全く意味がありませんし、そんなものサジェストされてほしくありません。

従って、そもそも１文字のキーワードは登録しないようにしています。

ただし、最近になって１文字の漢字にそれだけで意味のあるものも多数あるため、サジェストして欲しいものも間引いてしまっているという問題点に気づいてしまいました。

3. ほとんど使われないキーワードを間引く

意味が無いのになぜか１週間に１回くらい使われるようなキーワードというものがあります。 例えば、謎の店名等ゲームとは一切関係ない固有名詞等があります。

こういったキーワードも放っておくと徐々にscoreが上がっていきサジェストされるようになってしまいます。

これらをサジェストしない用、定期的にバッチを回して利用回数がN回以下のキーワードは容赦なくdeleteするようにし、 バッチ実行間隔内にN回以上使われないとキーワードに追加されないようになっています。

4. 特定のキーワードと同じ意味だが異なるものを間引く

たとえば、「モンスターストライク」というキーワードに対して、下記のようなキーワードで検索されることがあります。

  1. 「もんすたーすとらいく」と 全てひらがな で検索
  2. 「モンスターすとらいく」と 一部ひらがな で検索
  3. 「モンスタースト」と全てを入力せずに 部分だけ で検索
  4. 「モンスタースロライク」と 一文字間違えて 検索
  5. 「モンスター ストライク」と 余分なスペースを含めて 検索

この中で4と5については正直上手く同一視する方法を見つけていませんが、1、2、3に対する解は見つけることができました。

結論から言うと 「MySQLの "COLLATE utf8_unicode_ci" is 神」

SELECT * FROM suggest WHERE word COLLATE utf8_unicode_ci LIKE 'モンスターストライク';

1,2については上記のSQLで簡単に見つけることができます。

MySQLのCOLLATE utf8_unicode_ci

検索時にCOLLATE utf8_unicode_ciを利用すると検索結果が下記のようになります。

  • 英数字の全角/半角/大文字/小文字の区別が無くなります
  • ひらがな/カタカナ/半角カタカナの区別が無くなります
  • 濁音/半濁音の区別が無くなります(例: は=ぱ=ば)
  • 「っ」や「ゃ」などの小書き文字が普通の仮名と同一になる(例: はっぱ=はつぱ)

その他にもなにかあるかもしれませんが、このような効果によって上記のSQLでは 「モンスターストライク」「もんすたーすとらいく」「モンスターすとらいく」が結果として返ってくるので、 正規の単語以外を間引くことで目的を達することができます。

また、3については例えば

SELECT * FROM suggest WHERE word COLLATE utf8_unicode_ci LIKE 'モンスタース';
SELECT * FROM suggest WHERE word COLLATE utf8_unicode_ci LIKE 'モンスタースト';
SELECT * FROM suggest WHERE word COLLATE utf8_unicode_ci LIKE 'モンスターストラ';
SELECT * FROM suggest WHERE word COLLATE utf8_unicode_ci LIKE 'モンスターストライ';

の用に末尾N文字を除いた単語が見つかれば間引くような処理をすればよいです。

最後に

さんざんサジェスト機能について書いてきましたが、実は検索機能もサジェスト機能もまだ一部のゲームとLobi Playでしか使えません。

理由は、検索機能自体が下記の要件を満たしていないとイケていないため、全てのゲームで取り入れるとマイナスになる可能性もあるのではと危惧しているためです。

  1. 十分な動画投稿数があること
  2. 動画に十分な情報が含まれていること（タイトル、タグ、説明文）

もちろん要望があれば検索機能（サジェスト機能）を有効化することはできますので、使いたい開発者様はご相談いただければと思います。

カヤックではエンジニアを募集しています！

カヤックには、サーバーサイド、iOS/Android/HTML5などのクライアントサイドなど様々な分野のとても優秀なエンジニアが沢山います。

特にLobiは、巨大とまではまだ言えませんが大サービスくらいの規模があり、モンスターストライクやブレイブフロンティアなどの大人気ゲームにSDKを採用していただいております。

そんな成長著しいサービスですが、びっくりするぐらいアグレッシブにgoやAWSの新サービスなど新しいアーキテクチャを採用していてエキサイティングな開発を体験出来ます。

というわけで、エンジニアを大募集中です！！！！！！！！！！！

明日は

PerlからPerlじゃなさそうなエラーが出たり、謎な事象がでてIRCに投げると、組長か彼かというくらい反応してくれる プログラミングモンスターの @shogo82148 くんです。