LINE株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。 LINEヤフー Tech Blog

Blog


NAVER まとめ サジェスト検索のしくみ

こんにちは、NAVER Japan 検索サービス開発1チームで開発を担当している金森です。
先日「NAVER まとめ」にトピック機能を追加しましたが、そのタイミングでまとめサービス内で使用しているサジェスト検索機能のリプレイスを行いました。
今回このブログでは、実装したサジェスト検索の仕組みと、日本語入力ならではの諸々の面倒くさい問題とその対応について紹介したいと思います。

目次

  1. まとめにおけるサジェスト検索
  2. 使用した技術
  3. 全体的な検索の流れ
  4. サジェストのためのローマ字変換
    1. 拗音のローマ字変換
    2. 入力途中の文字
    3. 「いんてrねt」の対応
    4. ローマ字変換のまとめ
  5. その他注釈など
  6. まとめ
  7. 今後の課題

1. まとめにおけるサジェスト検索

サジェスト検索は皆さんお馴染みのとおりの機能で、簡単に言うと「検索語の入力中に検索候補が表示されるもの」と言えるかと思います。

まとめサービスでは、Web版の画面上部の検索窓や、iPhoneAndroidなどのスマートフォン向けアプリの検索画面などでサジェスト検索を提供しています。また、「トピック」と呼ばれる、まとめを自由にカテゴライズできるメタタグ情報の入力画面でも、既に登録済みのトピックをサジェストするために使用しています。
ユーザーの方々が自分の趣味関心に応じて色々なまとめを横断的に見る事ができる環境を提供することが、トピック機能開発の目的のひとつです。そのためトピックが付与されているまとめは検索結果の見え方が変わるようになっていますし、検索の段階から「どんなワードに関連するまとめが存在するか」を分かりやすくするためにトピックとして登録されたワードのみをサジェストするようにしています。

一般的なサービスでは、最近のトレンドワードや検索頻度の多いワードなど、特徴的な語彙を学習したりして、いろいろな要因からサジェスト候補を表示するのですが、まとめサービスではトピックという限られたデータの中から候補を表示するため、とてもシンプルに実装されています。

※ NAVER検索やNAVER画像検索でも、似た機能が提供されていますが、今回紹介するシステムは、このNAVERサジェストとは、別のシステムで構築されています。

2. 使用した技術

まず、日本語のサジェスト検索に必要なことは、入力された文字列の読み仮名を作ることです。これが英語などの表音文字なら入力された文字列を入力としてそのまま検索してしまえばいいのですが、漢字などの表意文字では読み仮名を推察する必要があります。
とくに日本語入力環境は特殊で、入力方法にもローマ字入力やかな入力などがあり、また入力した文字の漢字への変換もあり、文字を入力し終えるまでのプロセスがとても複雑です。
そのため検索側のデータと、入力された文字をマッチングさせるために、打鍵された内容に近い形で保持しておく必要があります。

また中国語などでは一つの漢字はだいたい同じ発音ですが(例外はあります)、日本語の場合は漢字・かなの組み合わせによって同じ漢字でも音読み、訓読みなどの複数の読み方があるため、どうしても文脈に応じて読み仮名の推察をする必要があります。
幸い多くの形態素解析器では読みの推定機能が付いているものが多いため、今回はこちらを使用しました。

日本語には、英語混じりの単語も少なくありません。もっと言えば、英語とローマ字が混在してしまった場合、英単語辞書を駆使してもなかなか判別が難しいです。今回は、ただ検索がしたいだけですので、英語もローマ字のひとつとして統一して考えてしまいます。こうすることで、一部外字を除いて、全ての単語は英数字記号のみで表現できるようになります。

さて、長文で疲れましたね。今回のサジェスト検索で必要な技術は、

  1. 形態素解析(読み仮名推察)
  2. ローマ字変換

の、たった二つだけになります。
形態素解析エンジンにはいろいろありますが、今回はIgoというJavaで実装された形態素解析エンジンを使用します。またローマ字変換はICU4Jなどのライブラリを使ってもいいのですが、この後説明する問題や、速度の問題があり今回は自作しました。

3.全体的な検索の流れ

図で示すと以下のようになります。

検索候補のデータと入力文字、それぞれ同じ形式に変換する必要があるため、検索対象のトピックの追加や更新時と、検索窓への文字入力時に同じ処理をしてローマ字に変換します。
サジェスト処理としては、入力されたワードを変換したローマ字を使って検索候補データ群を前方一致で検索し、見つかったものを一覧へ出力します。

・ 検索のためのデータ登録手順

検索候補のワードとして登録されているデータは、図の青矢印の手順で登録されています。

トピック名が「手紙の書き方」の場合、「手紙の書き方」「tegaminokakikata」の2種類が登録されます。

変換前の入力文字も登録している理由は、漢字には同じ漢字で複数の読み方がある場合があり、Igoを使った形態素解析では複数の読み候補を取得できないため、逃げ道としてもともとの入力をそのまま検索候補のワードとして登録しています。

例えば、「上手(じょうず)」「上手(うわて)」のような、前後の文脈がなければ読み方がわからない漢字の場合などがそれです。

・ 登録されたデータと入力文字のマッチング

登録されたワードを検索する場合には、図の赤矢印の手順で検索します。

まず、検索リクエストを検索ワードの登録時と同じ処理をして、ローマ字に変換します。例えば、「てが」という入力を検索したい場合、「てが」「tega」という2つのキーワードに変換してデータベースから検索します。
先ほどの「手紙の書き方」は、単純に前方一致検索をした場合は「てが」では見つかりませんが、「tegaminokakikata」にしておけば、「tega」が一致しているので見つかります。こうして、「てが」で検索したら、「手紙の書き方」が検索できるわけです。仕組はとても簡単です。

4.サジェストのためのローマ字変換

サジェスト検索の仕組は説明したとおり簡単ですが、ローマ字変換の処理が一般的なローマ字変換とは違い、表記揺れを吸収するように変換を行わなければならないため、とても複雑になります。

1.拗音のローマ字変換

例えば、「jyoyuu」と入力された場合を考えます。
入力したユーザーは、「女優」を検索したいのだろうと推測できますが、「じょ」というローマ字は、入力方法が「jo」、「jyo」、「jixyo」、「zyo」、「zixyo」など複数あります。データベースに「jo」と登録されていると「jyo」が検索できませんし、「jyo」と登録されていると「jo」と入力された場合に検索できません。

このように複数の書き方があるローマ字については、1回で検索できるようにどれか1つに統一する必要があります。本音を言えば、データベースのサイズを減らすために、できるだけ文字数の少ないほうへ変換・統一したいところです。一番文字数が少ないのは、明らかに「jo」ですが、「jo」で統一した場合は次のような問題に遭遇します。
「女優」を検索したいユーザーが、「じ」と入力したとします。この場合、

「じ」->「zi」

とローマ字変換して検索しますが、この状態で「女優」を見つけるには、「zixyoyuu」とローマ字で登録されている必要があります。このため、拗音の場合2つのカタカナ(例えば「ジョ」の場合「ジ」と「ョ」)に分離して登録しておく必要があるので、結果として一番長い「zixyoyuu」で登録します。

2.入力途中の文字

では、もしユーザーが「j」だけ入力した状態だとどうでしょう。これはとても困ったことになります。「j」だけ入力した状態で、「zixyoyuu」を候補に入れるには、「j」を「z」に変換しないといけません。しかし、「z」に変換すると、「za」や、「zu」など、関係のない文字まで候補になってしまいます。そこでよく観察すると、「j」と入力された場合、次に来る母音が何であろうと、「じ」という文字が出現することがわかります。(「じゃ」「じ」「じゅ」「じぇ」「じょ」)そこで、最終入力文字が「j」の場合、

「j」->「zi」

に変換することでこの問題を回避しています。

「f」や「q」の場合も同じで、

「f」->「hu」
「q」->「ku」

この3種類以外にも「ky」->「ki」、「gy」->「gi」などたくさんあります。これらを変換すると、下図のように「j」でも「z」でもほぼ同じ結果になります。期待どおり「z」の場合は、「ざ」のような結果も入ってきていますね。

最終入力が「j」なので、「jr」と入力されても大丈夫ですね。

※検索結果に「ネタ」が入っているのは、ネタの別名に「冗談」が登録されているためです。同様に「ニュース」には「時事」が別名登録されています。

3.「いんてrねt」の対応

ローマ字入力は、普通IMEの全角入力モードで入力すると思いますが、この状態で英単語を入力した場合はどうでしょうか。例えば「internet」を全角入力で入力したらWindows IMEの場合、「いんてrねt」と入力できると思います。こう入力された場合にも「internet」を検索できると素敵です。

さて、「いんてrねt」をそのままローマ字に変換すると「innternet」になります。検索したいのは「internet」ですが、どうも「n」がひとつ多いためデータベースから検索しても見つかりません。
ローマ字変換後に「n」が2個並んだ場合に、1つにしてしまえば、なんとか検索できそうですが、それでは「ん」という情報を削ることになります。例えば、「原因」を検索する場合、

「げんいん」->「genninn」->「genin」

となり、「下人」と区別がつかなくなります。

では、逆に、ローマ字変換後に「n」の後ろに「n」以外の子音が続いた場合、「nn」に変換してしまうとどうでしょうか。

「原因」->「げんいん」->「genninn」->「genninn」

で、問題なさそうです。

「下人」->「げにん」->「geninn」->「geninn」
「internet」->「innternet」

です。

これは、「n」の後が「n」以外の子音だった場合に「ん」に変換してしまうという、Windows IMEの動作と同じことをやっているに過ぎません。もともと、Windows IMEで入力した場合に、「いんてrねt」になってしまうのを検索したいのですから、Windows IMEと同じように「n」を「nn (ん)」にして検索すればよいことになります。

というわけで、「いんてrねt」を検索するために、検索対象の「internet」をカタカナにしてからデータベースに入れておきます。変換の順番は、

「internet」->「イテrネt」->「innternet」

のように、英語を1度カタカナにしてさらに、ローマ字にします。

4.ローマ字変換のまとめ

これで、晴れてサジェスト検索ができるようになります。ここまでのローマ字変換の手順をまとめると

  1. Igoで入力文字の読み仮名を取得する
  2. 拗音は2文字としてローマ字に変換する 「じょ」->「zixyo」
  3. 「j」や「f」などで入力が終わった場合は「j」->「zi」、「f」->「hu」に変換する
  4. 「n」の後が「n」以外の子音の場合「ン」に変換する
  5. 残ったひらがな、カタカナをローマ字にする
  6. 変換前の入力文字と変換後のローマ字を使って、データベースから検索する

となります。とてもシンプルだと言っておきながら、ローマ字変換に関しては少々面倒ですね。データベースへの登録時も同じ手順で、最後の検索部分が登録処理になるだけです。

5.その他注釈など

全角英数字について
全角英数字について特に記述しませんでしたが、全て半角英数字へ変換しています。

辞書について
Igoを使った形態素解析には辞書が必要なのですが、今回はNAIST-jdicを使用しています。
IgoはIPAdicはそのまま使えますが、NAIST-jdicはIPAdicとは少し形式が違うので、mecab-naist-jdicをダウンロードしたらCSVファイルの後ろ2項目(表記ゆれと複合語)を削除してIgoに読み込ませる必要があります。

NAIST辞書にも限界があり、人名など固有名詞はどうしても読み方の精度が落ちるので、地道に固有名詞や、最近使われ始めた単語などを登録していくことで精度を上げていきましょう。

ローマ字に統一したことについて
今回は「ローマ字」に統一しましたが、「カタカナ」や「ひらがな」など他の表音文字へ統一してもいいと思います。

6.まとめ

サジェスト検索は入力の手間を少し省けるだけですが、使ってみるととても便利な機能です。
今回紹介した方法の良いところは、入力を学習する必要が無いので、入力パターンデータの蓄積がなくても一定水準の機能を提供できるところです。さらに数万~数十万件ほどのデータならそれほど検索速度が落ちることもありません。もしもWEBサイトを作る機会があれば、ぜひサジェスト検索を提供してください。利用者の使い勝手が格段に向上すると思います。今回は単語が中心の構成でしたが、形態素解析器は少し長い文章のほうがその機能を存分に発揮できるので、説明文のようなデータからサジェスト表示するような仕組にすると、よりおもしろいWEBサイトになると思います。

7.今後の課題

この仕組の欠点は、Windows IMEの動きにあわせた実装になっているため、IMEの変換処理によってはうまく検索できないところです。WindowsとMacでは、IMEが違うので、同じ手順で文字を入力しても変換される文字が違ったりします。

パソコンなら入力デバイスがキーボードなので、まだ違いは少ないようなのですが、携帯電話やスマートフォンなどいろいろなデバイスが世の中に浸透してきていて、それぞれIMEの実装も違うため、全てのデバイスでうまく動作するようにはなかなかできません。
デバイス間の違いをカバーするには、入力された文字のパターンを学習して推測する仕組や、編集距離から近い単語を探す仕組など、もう少し別な仕組みを組み合わせることが必要になると思います。