blog.foresta.meこんにちは、 @kz_morita です。
今回は，検索システムにおいてインデックスを構築する際の辞書と用語についてまとめます．
辞書と用語
検索システムは，検索クエリに合致する文書を探すことが目的のシステムです． 効率的に探すために，インデックスを事前に構築します．
上記の以前書いた記事にもありますが，インデックスには用語集である辞書と，その用語が出現する文書IDを記した，ポスティングリストがあります．
文書の取得からこの辞書を構築するまでについて手順を説明します．
辞書作成の手順
辞書を作成するには，おおまかに以下のような手順が必要になります．
- 文字列の取得
- 語彙の決定
- 語彙の正規化
これらについてまとめます．
文字列の取得
検索システムの検索対象である文書ですが，データある以上もとのデータは byte 列になります． これを文字列として認識するためにはいくつかの懸念点があります．
文字コード
byte 列を文字列として認識するためにはその文書がどの文字コードで書かれているかということを知る必要があります．
文字コード判別の手段として以下のようなものがあります．
- 機械学習分類
- ヒューリスティック
- ユーザー選択
- 文書メタデータ
多くは，下３つが使われているようです．
ちなみに文書メタデータは，HTML の meta 属性のようなものと考えると良さそうです．
ファイルタイプ
ファイルのタイプにより特別な復号化が必要な場合があります．
- zip
- docx
- xml
たとえば，zip であれば解凍する必要がありますし，xml などでも，& など特別なエンコードをもとに戻したりする必要があります．
言語
アラビア語など文書の読む方向が違うような言語についても，必要があれば考慮する必要があります．
語彙の決定
文字列が取得できたら，そこから語彙を決定します．語彙を決定するために文字列から Token 列を得る必要があります．
Token 化は文書の言語に依存するため，分類器などを用いて言語を推定します．
たとえば，英語などは単語がスペースで区切られているため分割は比較的簡単ですが，日本語などでは区切られてないため形態素解析などで語分割を行います．
とはいえ，英語などでも，アポストロフィの扱いなど考えなければならない点があります．
Token 列が取得できたら，語彙として使用しないワードをストップワードとして登録して辞書から除外することがあります．
たとえば，日本語の助詞などをストップワードに登録することが多いです． ストップワードをつくることのメリットしては，助詞などはとても頻度が多いため辞書とポスティングりすとの個数を大幅に減らせることにあります．
ただし，歌のタイトルや，格言など，ストップワードが大きく影響をうけるような分野もあるため，Web検索などでは使用されない傾向にあるそうです．
その代わりとして，言語統計などを用いて，頻出語をどのように扱い削減するかに焦点が当てられています．
語彙の正規化
語彙が決定したら，正規化を行います．
表記が異なっていても，等価として扱いたいものを一つに正規化をします．
たとえば，USA と U.S.A といった具合です．
正規化の方法として，クエリ時に拡張する方法と，インデックス時に拡張する方法があります．
クエリ時の拡張
たとえば，USA と検索されたときに，USA の辞書と，U.S.A の辞書を両方検索するというのが，クエリ時の拡張になります．
インデックス時の拡張
対して，USA というワードが含まれた文書が与えられたときに，USA と U.S.A の両方のポスティングリストに，文書IDを追加するのが，インデックス時の拡張になります．
よく用いられる正規化
その他によく用いられる正規化として以下のようなものがあります．
- アクセント記号や特殊記号
- 大文字化 / 大文字小文字平準化
- 言語特有の問題
- ステミング, レンマ処理
大文字，小文字の統一や，英語の color と colour ，日本語のひらがなとカタカナと漢字， 言語学的に同一のものを処理するステミング，レンマ処理など，検索結果を改善するためにさまざまな正規化が施されます．
まとめ
今回は，検索システムの辞書を作るときの概要について簡単にまとめました．
さらっと，まとめたそれぞれに更に深い議論があるとおもうので引き続きキャッチアップしていきます．