検索エンジン自作の入門編
加藤遼 氏：普段はサーバサイドの開発やAPI、検索まわりをやっています。技術的にはPythonやElasticsearchがメインです。このセッションにこんなに人が来ると思っていなかったので、これだけ集まってくれて大変ありがとうございます。
ここに来たということは、みなさん検索に多少なりとも興味がある方だと思います。なのでちょっとだけ宣伝させてください。検索技術勉強会という勉強会のスタッフをやってます。これは特定のライブラリに関わらず、検索や検索システムにまつわる技術や手法の勉強会です。だいたい3ヶ月に1回ぐらいの間隔で開催しているので、今年中にはやると思います。ぜひ興味がある方はご参加ください。スピーカーと、会場の懇親会スポンサーを募集中です。
改めまして、「入門 自作検索エンジン」や「検索エンジンを自作することに入門した話」をします。先ほど言われて気付いたんですけど、このスライドは25分ぐらいらしいんですが30分ギリギリぐらいで作っています。たぶん後ろのほうの人は見えないと思うので、さっきTwitterに資料を上げたのでそちらをぜひご確認ください。
このトークの対象は、全文検索のことを知らない人や何となく知っている人を対象にしています。あとは検索に興味がある人や、「検索エンジンを作ってみたいと、なんとなく思っているけどどうしよう」みたいな人を対象にしていて、その人たちを沼に沈めるためのトークです。
（会場笑）
検索エンジンを作ることなので、ElasticsearchやSolrといったOSSの全文検索エンジンをどう使うか、Pythonで使うtipsみたいな話。あとは検索エンジンを使うとどうしてもクローリングやスクレイピングをやると思うんですが、そのへんの話はしません。このへんに興味がある人は、ここに挙げている去年のPyConの資料やブログが参考になるので、そちらを見てください。
目次です。最初に基本的な全文検索エンジンのトピックや技術的なアイディアの話をちょっと説明して、具体的に作っていくところを触れていきます。全部を説明する時間はないので、実際に作るところはポイントをサンプルコードを使いながら説明していくかたちになります。最後に、それを改善するにはどうするかという資料を共有して、まとめに入りたいと思います。
「全文検索」の定義と種類
最初に「全文検索とは？」というところから始めていきます。全文検索とは名前のとおりで、文章の全部を検索することです。検索エンジンとは何かと言うと、文章の集合から要求に適合する文章を見つけるシステムやソフトウェアのことですね。
ちょっと簡単なクイズをみなさんに出します。今の定義に合わせた検索エンジンを、実は1分あればPythonで作れます。どうやって作るでしょう？
時間が限られているので答えを言いますね。テキストを受け取ってファイルに書き入れて、検索するときはキーワードを受け取ってファイルを1行ずつ見ながらテキストが合っているかチェックをして、合っていればテキストを返す。これだけで検索エンジンになります。
「おい！」と思った人がいるかもしれないですけど、これも全文検索エンジンです。全文検索にはいくつか種類があるんですね。これはGrep型と呼ばれているもので、単純に線形走査を行うもの。
もう1個はよく使われているインデックス型と呼ばれるもので、これは後ほど説明をしていきます。
あとはベクトル型は、僕が勝手にそう言っているだけで一般的に言われているかわからないんですが、文章をベクトル化して、そのベクトルの類似度で検索をするものですね。最近ディープラーニングが盛り上がってきているので、ここらへんが気になる人が多い気がしています。
転置インデックスの作り方
ここからはインデックス型について話を進めていきます。インデックス型は、あらかじめ検索対象の文章を作っておいてインデックスデータを準備していく方法です。インデックスファイルを作ることをインデクシングと言って、それから作られるデータをインデックスと言います。このインデックスの作り方はいろいろあるんですけど、一般的なのは転置インデックスと呼ばれるデータ構造です。
この転置インデックスというのはいろんな全文検索エンジンで採用されています。イメージとしては本の後ろについている索引で、キーワードとそのページ数が書いてあるやつです。例えば、Pythonというキーワードを含んでいるドキュメントが1、2、3、5、7、10とあったときに、このドキュメント1つをポスティングと言います。このポスティングを全部合わせたリストで持っているものをポスティングリストと言います。
例えば、このPythonというキーワードに対するポスティングリストは1、2、3、5、7、10が当てはまると。PythonやElasticsearchみたいなキーワードのことを辞書と言って、ポスティングリストでまとめたものをポスティングと呼びます。このへんの組み合わせを転置インデックスと呼んだりします。このへんはいろいろワードがあってややこしいんですけど、だいたい同じものだと思ってもらえればいいかなと思います。
この転置インデックスをどう作るか？ というところで、またいくつかの方法があります。1つがレコード単位の転置インデックスと呼ばれるもので、これは単語とその単語を含んでいる文章や文章IDとかをリストにして持っています。さっき挙げていた例はこれですね。
メリットとしては、シンプルなものなので実装しやすくて、他のものに比べるとディスク容量が少なく済みます。デメリットはシンプルなゆえに検索のときの機能性が若干乏しいです。
一方で単語単位の転置インデックスというものがあって、これは単語とそれを含んでいる文章＋αの情報、例えばその単語が文章中のどこに出現するかの位置情報を合わせて持たせるとか、そういうかたちで作ります。
こちらは位置情報など、いろんな情報をインデックスで持っているので、検索のときに機能性の高い検索を実装できたりします。例えば、位置情報があればつながっている単語同士を見ていけばフレーズ検索ができたりします。ただ、インデックスの容量が増えるという難点があります。
一般的な検索システムの流れ
ちょっと話を戻して、転置インデックスはPythonのdictionaryと同じような扱いなんですね。キーがトークンで、バリューがそのポスティングリストを持ちます。ということは、このキーが一致しないとこのポスティングリストを取れないので、どういう単位でインデックスを作るかがとても重要なポイントになります。
このインデックスをどう作っていくかはいろいろな方法があるんですが、一般的に使われているのがトークナイズと呼ばれる単語に分割する方法です。
英語のようにスペースで区切られている文章だとWhite spaceで区切ったり、日本語だと形態素解析して単語に区切ったりします。単語とはまた別で、2文字ずつとか3文字ずつみたいなN-gramを作る方法もあります。
もう1つ、インデックスを作るときにトークナイズで単語を区切るだけでなくて、その前後でテキストに処理を加える必要もあります。これはどういう検索エンジンを作るかによって依存してくるので、作りたいものの目的をよく考える必要があります。
そのテキストに対する処理をまとめたものをCharacter Filterと呼びます。これはHTMLタグを除いたり、英文字をすべて小文字に変える処理などをしています。Character Filterで変換したものをTokenizerと呼ばれるものがトークンに分割して、Tokenfilterがこのトークン一つずつに対して、ストップワードを除去したり、単語を原形に戻したりしていくという処理をします。
ここで一般的な検索システムの流れを見ていきます。文章を受け取って、その文章を分割して、単語を分割して文章やトークン情報を保存。そしてポスティングリストを作って転置インデックスを更新して保存する流れが、検索エンジンにドキュメントを追加する際の基本的な流れです。
一方で、検索をする流れは、また別でちょっと複雑な話になります。基本的には、まずユーザからクエリを受け取って、それをパースします。ここでインデックスしたときのトークンと同じように分割しないと、データベースからポスティングリストを取得できないので同じようにAnalyzerを通してアナライズします。ポスティングリストを取得して、複数の単語があった場合は、マージをして文章を並び替えて結果を返す流れになります。
これが検索エンジンのだいたいの基本的な流れになります。このへんは知っている方が多いかなという気がしています。
