検索結果の疑問を解消するための基礎知識

こんにちは、買物情報事業部の荒引 (@a_bicky) です。 業務ではクックパッド特売情報のサーバーサイドや商品検索周りを担当しています。

突然ですが、とある商品検索の機能を使っていて次のようなことが起きたら不思議ですよね。

  • 「ねぎ」で検索したら「たまねぎ」がヒットした!
  • 「ドレッシング」で検索したのに「たまねぎドレッシング」がヒットしない!
  • 「豚 薄切り」で検索したのに「豚ロース肉薄切り」がヒットしない!
  • 「たまご」と「卵」の検索結果が違う!

今回は上記の疑問を解消するために検索の基礎的な内容について説明します。 以下、特売情報の商品を検索することを例に説明しますが、一般的な内容なので「商品」を「レシピ」等に読み替えることも可能です。

大量のページから目的のページを探すための索引

たいていの本の巻末には索引が載っていますよね。特定の内容が載っているページを探す場合、1ページ目から順番に探すととても時間がかかりますが、索引を使えば一瞬で所望のページを探し出すことができます。

商品検索機能を実現する場合も同様に、毎回対象となる全商品の内容を確認して目的の文字列があるかどうか探す方式と、索引を利用する方式があります。 ある程度の規模のサービスになってくると、毎回全商品の内容を確認していると遅いので、索引を利用するのが一般的です。

以降、索引を利用する前提でお話します。

どのようにして索引を作るか?

大量の商品がある場合、商品内容を 1 つ 1 つ人手で確認して索引語を選定することは無理なので、機械的に索引語を抽出して索引を作成する必要があります。 特売情報の各商品には商品名だけでなく商品に対するコメントなどもありますが、商品名のみから索引語を抽出することにします。

例えば、次の 4 つの商品から索引を作ることを考えます。

商品 ID 商品名
1 たまねぎ
2 たまねぎドレッシング
3 千葉産ねぎ
4 たまご千葉産

索引語としては単語か文字 N-gram がよく使われます。文字 N-gram とは連続する N 文字のことで、N = 2 の場合は 2-gram (bigram) です。

f:id:a_bicky:20151027155152p:plain

上記右側の表が索引です。いわゆる本の巻末の索引のようなデータですが、このようなデータ構造のことを転置インデックスと呼びます。

なお、クックパッド特売情報では索引語として固有表現を使用しています。商品名の中から「商品」、「産地」、「数量」等の固有表現を抽出し、検索に使用したい表現のみを索引語として採用しています。

f:id:a_bicky:20151027155330p:plain

詳細は「クックパッド特売情報 における自然言語処理 〜固有表現抽出を利用した検索システム〜」をご参照ください。

検索キーワードにヒットする商品を探す

検索キーワードにヒットする商品を探す際には、商品名から索引語を抽出した時と同じようにキーワードから索引語を抽出し、全ての索引語が含まれている商品を探します。

それでは、先ほど作成した索引から、「ねぎ」で検索する場合と「たまねぎドレッシング」で検索する場合を考えてみます。

まず、索引語として単語を使う場合です。

f:id:a_bicky:20151027155346p:plain

「ねぎ」で検索すると「千葉産ねぎ」がヒットし、「たまねぎドレッシング」で検索すると「たまねぎドレッシング」がヒットしていることがわかります。

次に、索引語として 2-gram を使う場合です。

f:id:a_bicky:20151027155357p:plain

「ねぎ」で検索すると「千葉産ねぎ」だけでなく「たまねぎ」や「たまねぎドレッシング」までヒットしてしまっています。

このように、索引語として N-gram を使うと意図しないものにヒットする可能性があるので、正確性(精度)を重視する場合は単語を索引語として使用することが好まれます。 一方で、単語を索引語として使用する場合は単語の分割結果に強く依存するため、網羅性(再現率)を重視する場合は N-gram が使われます。

単語分割の曖昧性

ここまで単語の分割に関しては適切に行われる前提で説明してきましたが、単語を適切に分割するのは難しいことです。例えば次のような問題があります。

  • 単語分割単位の曖昧性
  • 単語境界の曖昧性

単語分割単位の曖昧性は「たまねぎドレッシング」を「たまねぎ」と「ドレッシング」の 2 語として扱うか「たまねぎドレッシング」の 1 語として扱うかの曖昧性です。 単語境界の曖昧性は「ロース肉薄切り」を「ロース / 肉 / 薄切り」と「ロース / 肉薄 / 切り」のどちらで分割するかの曖昧性です。

もし「たまねぎドレッシング」を 1 語とした場合、「たまねぎ ドレッシング」で検索しても「たまねぎドレッシング」はヒットしません。

f:id:a_bicky:20151027155419p:plain

もし「ロース肉薄切り」を「ロース / 肉薄 / 切り」と分割した場合、「ロース 薄切り」で検索しても「ロース肉薄切り」はヒットしません。

f:id:a_bicky:20151027155433p:plain

このように、単語分割結果の違いが検索結果にも大きな影響を与えます。

単語分割単位の問題は絶対的な基準を設けることの難しい問題ですが、個人的には分割するかどうか迷ったら分割し、検索結果を表示する際の順位でより適切なものが上位に来るようにするのが良いと思っています。 単語を分割する技術の詳細について興味のある方は次のエントリーもご覧ください。

日本語形態素解析の初歩

名寄せの必要性

例えば「たまご」と「卵」は同じものを表しているので、商品検索の観点では多くの場合どちらで検索しても同じ結果になってほしいものです。 しかし、機械には「たまご」と「卵」が同じものであるという知識がないので全く別のものとして扱われてしまいます。 よって、表記の違い(表記揺れ)などを統一する作業が必要です。これを名寄せと呼びます。

f:id:a_bicky:20151027155449p:plain

名寄せが必要なパターンには次のようなものがあります。どのパターンに対応すべきかはサービスの特性によります。

  • 漢字と平仮名の違い
    • e.g. 「卵」と「たまご」
  • 送り仮名の違い
    • e.g. 「薄切」と「薄切り」
  • 別名
    • e.g. 「パクチー」と「コリアンダー」
  • 略称
    • e.g. 「産地直送」と「産直」

ここでちょっとした豆知識ですが、ほとんどの検索システムでは英数字の全角と半角、大文字と小文字をどちらかに統一していると思います。また、平仮名も片仮名に寄せることが多いです。 よって、多くのサービスの検索機能では、検索キーワードの表記を全角から半角に変えたり、平仮名から片仮名に変えたりしても検索結果は変わらないことでしょう。

まとめ

  • 高速に検索するためには索引が使われる
  • 検索結果は索引語として何を使うかに依存する
  • 索引語として単語を使う場合は単語分割の精度が問題になる
  • 所望の検索結果にするには名寄せが必要

というわけで、冒頭の検索結果の原因には次の可能性が考えられます。

  • 「ねぎ」で検索したら「たまねぎ」がヒットした!
    • → 索引語として 2-gram を使っているのかも
  • 「ドレッシング」で検索したのに「たまねぎドレッシング」がヒットしない!
    • → 索引語として単語を使っていて「たまねぎドレッシング」が 1 語になっているのかも
  • 「豚 薄切り」で検索したのに「豚ロース肉薄切り」がヒットしない!
    • → 索引語として単語を使っていて、分割がうまくいっていないのかも
  • 「たまご」と「卵」の検索結果が違う!
    • → 適切に名寄せされていないのかも

以上、検索の基礎的な内容について説明しました。今回の記事で検索結果に対する疑問が少しでも解消されれば幸いです。

/* */ @import "/css/theme/report/report.css"; /* */ /* */ body{ background-image: url('http://cdn-ak.f.st-hatena.com/images/fotolife/c/cookpadtech/20140527/20140527163350.png'); background-repeat: repeat-x; background-color:transparent; background-attachment: scroll; background-position: left top;} /* */ body{ border-top: 3px solid orange; color: #3c3c3c; font-family: 'Helvetica Neue', Helvetica, 'ヒラギノ角ゴ Pro W3', 'Hiragino Kaku Gothic Pro', Meiryo, Osaka, 'MS Pゴシック', sans-serif; line-height: 1.8; font-size: 16px; } a { text-decoration: underline; color: #693e1c; } a:hover { color: #80400e; text-decoration: underline; } .entry-title a{ color: rgb(176, 108, 28); cursor: auto; display: inline; font-family: 'Helvetica Neue', Helvetica, 'ヒラギノ角ゴ Pro W3', 'Hiragino Kaku Gothic Pro', Meiryo, Osaka, 'MS Pゴシック', sans-serif; font-size: 30px; font-weight: bold; height: auto; line-height: 40.5px; text-decoration: underline solid rgb(176, 108, 28); width: auto; line-height: 1.35; } .date a { color: #9b8b6c; font-size: 14px; text-decoration: none; font-weight: normal; } .urllist-title-link { font-size: 14px; } /* Recent Entries */ .recent-entries a{ color: #693e1c; } .recent-entries a:visited { color: #4d2200; text-decoration: none; } .hatena-module-recent-entries li { padding-bottom: 8px; border-bottom-width: 0px; } /*Widget*/ .hatena-module-body li { list-style-type: circle; } .hatena-module-body a{ text-decoration: none; } .hatena-module-body a:hover{ text-decoration: underline; } /* Widget name */ .hatena-module-title, .hatena-module-title a{ color: #b06c1c; margin-top: 20px; margin-bottom: 7px; } /* work frame*/ #container { width: 970px; text-align: center; margin: 0 auto; background: transparent; padding: 0 30px; } #wrapper { float: left; overflow: hidden; width: 660px; } #box2 { width: 240px; float: right; font-size: 14px; word-wrap: break-word; } /*#blog-title-inner{*/ /*margin-top: 3px;*/ /*height: 125px;*/ /*background-position: left 0px;*/ /*}*/ /*.header-image-only #blog-title-inner {*/ /*background-repeat: no-repeat;*/ /*position: relative;*/ /*height: 200px;*/ /*display: none;*/ /*}*/ /*#blog-title {*/ /*margin-top: 3px;*/ /*height: 125px;*/ /*background-image: url('http://cdn-ak.f.st-hatena.com/images/fotolife/c/cookpadtech/20140527/20140527172848.png');*/ /*background-repeat: no-repeat;*/ /*background-position: left 0px;*/ /*}*/