Pythonで検索エンジンをゼロから作って学んだこと Part.2

シンプルな検索エンジンを作る

加藤遼 氏：ここからは実際に事例を踏まえながら、どういうものを作っていくかの実装の話をしていきます。

実際に作っていく検索エンジンは、これです。これは「PyconSearch」という、今年のPyConのセッションを検索できるもので、わりと便利なサイトです。これを実際に作っていきながらどういうことをやっていくかという話を進めていきます。

まずは要件から決めていきましょう。「PyConJPのトークを検索できる」ことが目的ですが、実は公式のタイムテーブルにはタイトルでフィルタリングできるのでそれ以上の機能がほしいです。なので詳細とかも含めて検索できるようにします。

本当はユーザの自己紹介などの部分も検索対象に入れていたんですけど、問題が1個ありました。プロフィールに「機械学習」と書いている人がけっこういらっしゃるんですが、その人たちは実際のトークで機械学習の話をしないんですよ。

（会場笑）

なので、「機械学習」で検索をするとまったく関係のないセッションが上がってくる。僕はそれを「機械学習問題」と呼んでいて。

（会場笑）

ちょっとこれは避けたいので、セッションはタイトルと詳細だけを検索できるようにしました。クエリは論理検索はほしいので、論理検索に対応します。結果はTF-IDF値を使ってスコア順に返します。ちょっと複雑になってくるのでフレーズ検索は対応しません。複数のフィールドも検索対象にしないです。ドキュメントの更新はしなくて、途中の追加もしません。インデックスは最初に一度やるだけなので、これだけでも考えることが減ってシンプルになります。

全体像はこんな感じですね。これを1つずつ見ていきます。

まずAnalyzerの実装ですが、Analyzerはこういう感じで日本語と英語を準備して、それぞれフィルターとTokenizerで実装していくかたちにします。

だいたいどのCharacter Filterも似たような実装になるので、Character FilterはベースとなるCharacterFilterクラスを作っておいて、そこにfilterというメソッドを準備しておきます。

実際にタグを除去したり、テキストに処理を行うようなフィルターは、このベースのCharacterFilterを継承して、そのフィルター部分を実装するかたちで作っていきます。

Tokenizerも同じですね。TokenizerはBaseTokenizerクラスを作って、tokenizeというメソッドを作っておきます。今回、日本語の形態素解析は「Janome」という形態素解析のライブラリを使いました。これはPython製のもので、別途に辞書を作らなくてもいいので、pipでインストールするだけで使える便利なものです。

Tokenfilterも似たような感じで、共通のメソッドを準備しています。ここはちょっと微妙だなと思っているんですけど、特定の品詞を除きたいみたいなフィルターを作るときに、Janomeで作ったトークンが持っているオブジェクトを使いたいので引数に文字列とJanomeのオブジェクトの両方を想定して作っています。

Tokenfilterに関しては、Stemmingの処理をやる場合は、nltk.stemパッケージを使うと楽になります。

POSFilterはJanomeのトークンオブジェクトが持っているpart_of_speechを見て、その判定で不要なものを除去していく処理を入れていきます。

ここでメソッドの形を揃えたのは、Analyzerの実装をこうしたかったというのが1つあります。Analyzerはベースのクラスに、クラス変数でtokenizerと、char_filer、token_filterを配列で指定できるようにしておきます。こうしておくと、AnalyzerのAnalyzerクラスでそれぞれを呼び出して、順次テキストにテキスト処理を加えていくことができます。

実際のAnalyzerはこうやって、そのフィルターやTokenizerを指定するだけでいいので、実装が楽になるのと、コードの見通しがよくなるかなと思って作っています。これでAnalyzerは完成なので、アナライズできるようになりましたね。

文章を受け取って転置インデックスを作成

次はインデックスを作っていきます。Indexerは、文章を受け取って転置インデックスを作成するものです。インデックスするときは、基本的にいきなりストレージに入れずに、一度転置インデックスをメモリ上に保持しておく必要があります。この話については後ほどお話します。

まずは、ポスティングリストを作ります。ポスティングリストはAnalyzerで作ったトークンからドキュメントIDを作って入れていけばできます。今回は基本的にフレーズ検索とかを使わないシンプルなものなので、最初に説明したレコード単位のインデックスで十分なんですが、後ほどソートでTF-IDF値を算出するときにトークンの数を計算したいので、ここで先に計算をしておきます。

その単語単位の転置インデックスを作って、最初の説明だと位置情報を持っていましたが、今回はドキュメントにそのトークンが何個含んでいるかを事前に持っておくようにします。

ちょっと話が戻りますが、転置インデックスをなぜメモリ上に保持しておく必要があるかの説明をしておきます。全文検索エンジンでだいたい性能や速度の面でボトルネックになるのがストレージのI/O部分が多いです。

なので、基本的にメモリにポスティングリストの情報を持っておいたほうが速くなります。速くなるんですけど、そこで調子に乗ってメモリに持ちすぎるとアプリが落ちたりするので、適宜ストレージに置くとか、そのへんのバランスを設定しておく必要があります。

これで転置インデックスの作成までは完成したので、今度はそれを一時的にストレージに保存します。ストレージは何でもいいと思います。NoSQLを使うほうが楽かなと思うので、お好きなものを使ってください。

今回は極力Pythonだけを使いたかったので、SQLiteを使いました。もっと効率的なものを作るんだったら、そのストレージ部分も実装したほうがいいですね。これでストレージの完成なので、ドキュメントの追加、インデクシングが完成です。

検索部分は逆ポーランド記法を使う

次は検索部分にいきます。検索部分はけっこう複雑です。やることが多い感じですね。検索はクエリを受け取って、それをパースして、検索のドキュメントIDを取得して、文章をストレージから取得して、スコア順に並び替える処理をしていきます。

これらを1個ずつ見ていきます。Parserはユーザの入力クエリをパースする役割です。これはAND、OR、NOTみたいな論理検索に使うオペレータを実装する場合は必要です。もしそういうのをやらないのであれば、やらなくてもOKです。直接Analyzerにユーザの入力クエリを渡しちゃってOKですね。

このパースの部分の実装はいろいろやり方はあるんですけど、今回は逆ポーランド記法を使って変換していきます。

逆ポーランド記法は演算子を被演算子の後ろに置く記法ですね。例えば「3＋4」とかの場合は「34＋」に置き換えるものです。これのメリットとしては式の評価がシンプルになるので、先頭から評価するだけで済むことにありあます。

この変換をするアルゴリズムに操車場アルゴリズムがあります。この詳細はWikipediaに載っているので、ぜひそこを見てください。

Parserではアルゴリズムを実装して変換するだけなんですけど、アルゴリズムは説明を見ながらがんばって実装してもらえればいいかなと思います。正規表現を使ってユーザの入力クエリを空白で分割した後に、利用するオペレータの優先度や結合方法を指定してあげます。

こういうので作ってあげると、例えばこのParserで、「A AND (B OR C)」というクエリが、['A','B','C','OR','AND']というかたちに変更されます。

ここで問題なのがAnalyzerですね。忘れないように、ここでいったんAnalyzerを書いておきましょう。Analyzerにも同じ処理書かないと普通にインデックスが異なり検索できません。

逆ポーランド記法の評価手順どおりにマージ処理

次にマージの処理ですね。論理演算で複数のクエリを作っているので、例えばクエリ2つをマージして逆ポーランド記法の前から評価していくみたいなかたちで実装していきます。逆ポーランド記法の評価は3パターンあって、基本的にスタックに積むか、スタックから取り出すか、計算するかの3つです。

計算をするということは、スタックに積んである2つの被演算子を取り出してきます。その演算子の形、例えばANDだったら足すといった処理を2つの被演算子に対して行います。ということは、スタックにはトークンから取得したポスティングリストを追加しておく必要があるので、そういうふうに実装していきます。

マージ処理も逆ポーランド記法の評価手順どおりに実装してもらえればOKです。ざっくり話していくと、先ほどの逆ポーランド記法で単語を分割して並び替えましたよね。それを前から順にトークンを取得していって、トークンが被演算子、要するにキーワードだった場合はいったんポスティングリストを取得して、取得したポスティングリストをスタックに追加します。

次にトークンが演算子だった場合や、ANDやORの場合は、スタックに溜まっている直近のトップ2つを取り出してマージ処理をします。例えばANDの場合はトップ2つをANDマージをしたり、ORの場合はトップ2つをORマージにしていくかたちです。必須ではないですが、ポスティングリストはスコア計算用にdictionaryで保持しておきます。

ここでトークンを持っておくと先頭から順に評価していって、最後まで問題なく終われば最終的にスタックに溜まっているのは1つの値だけになるので、それが最終的なdoc_idになります。

ただ、いくつか検索で対応しないといけないことがあります。「NOT ○○」のキーワードの対応です。基本的に演算子が逆ポーランド記法の評価の計算は、そのスタックに溜まっている直近2つを対象にするんですけど、NOT ○○の場合、演算子1つに付き被演算子が1つしかないので、それを別途対応する必要があります。

あとは、これは検索上の問題だったりするんですが、ユーザが「Python 機械学習」となったときに、これは「ANDなのかORなのかどっちを期待するのか」という問題がありますよね。ちょっと気になるのでアンケートを取ってみたいんですけど、「Python 機械学習」のときに「Python OR 機械学習」を期待する方はどれくらいいますか？

（会場挙手）

あ、少ない。じゃあ一応確認しますけど「Python AND 機械学習」だと言う人？

（会場挙手）

ありがとうございます。残念ながら今回はORを採用しました。

（会場笑）

OSSの全文検索エンジンはデフォルトがORの場合があるので、このへんは別途対応する必要があるので気を付けてくださいね。

最後にスコアリング

最終的にdoc_idを取得できたら順番にドキュメントを取得していって、最後に並べ替えます。並び替えはTF-IDF値を使いました。TF-IDFのTFは、文章中に含まれるその単語の割合で、IDFは、その単語を一度でも含んでいる文章が全体の文章の中のどれくらい含まれるか。なので、ざっくり言うと、文章中によく出てきて他の文章には出てこないものはスコアが高いかたちですね。

「検索においてのIDFって何だろう？」ということが気になったので考えたいんですが、例えば「Python」で検索をしたときに、母集団となる文章は全部Pythonを含んでいるので、1キーワードを検索すると全文章のIDFは同じ数値になるじゃないですか。そうするとTFだけでいいかな？　と思ったりするんですけど、これをよく調べていくとANDやORで検索したときに、意味が変わってくるのが個人的な発見でありました。

これは「A AND B」とかで検索をしたときに、Aというクエリに対する文章群の集合と、Bというクエリに対する文章群の集合に対してのAとBのそれぞれの重み付けを計算してあげることで、どのドキュメントが重要なのかがわかります。

なので、「A AND B」とかで検索したときの文章αのTF-IDF値はクエリAのTF-IDFとクエリBのTF-IDFを、その文章に対して算出して足したものと定義して、今回は実装をしています。

最初に話しましたが、インデックスに必要な値は入っているので、スコアの計算は値を取り出して計算するだけなので、それほどコストは掛からないですね。だいたいスッといくと思います。ここでDEMOをみなさんに触ってもらおうと思ったんですけど時間がないので飛ばします。

これでシンプルにAND検索やOR検索ができてTF-IDF値が返ってくる検索はできました。ただ。まだまだ改善したいところはいっぱいありますよね。これは今回時間がないので触れていないところとか、僕がまだやっているので発表していないことのリストです。このへんを気になる方は、ここにある資料を参考にして作ってもらうとうれしいです。

何か発見があったら、ブログとか書いてください。そうすると僕が読んでそれを参考にします。

（会場笑）

「使う」と「作る」の間には深い溝がある

最後、まとめですね。とりあえず検索エンジンの仕組みの説明から実装まで簡単に説明しました。単純に見えるところでも、実際に作ってみるといろいろと考えないといけないことがいっぱいあって、実際によく言われますが「単純に使うと作るとの間にはマリアナ海溝ぐらいの深い溝がある」というのが実感できます。やはり昨日のLTでもありましたが、車輪の再発明というのはとても重要で有意義ですね。

作って思ったのは、検索エンジンを作るのはやはりとても楽しいので、ぜひみなさん、「ぼくのかんがえたさいきょうのの検索エンジン」を作ってブログとかで教えてください。また、僕のほうでも進捗がありましたらどこかの機会で発表したいと思います。

ご清聴ありがとうございました。

（会場拍手）

司会者：はい、どうもありがとうございました。以上で終わりたいと思います。ではもう一度、加藤遼様に温かい拍手をお願いいたします。

（会場拍手）

司会者：まだ時間がちょっとあるので質問がある方はいますか？

質問者：貴重なご講演をありがとうございました。検索キーワードがたくさんあるとクエリをたくさん飛ばすようになっていたかと思うんですけど、例えばANDやORを1つのクエリでデータベース側でやってもらうふうにはできないんでしょうか？

加藤：一応、データベース側でやると言うか……そのトークンが別になるので、そのキーワードを全部まとめてデータベースから取ってくるというのは可能ですね。なのでマージはどちらかのタイミングでやる必要はあると思うので、そのへんは実装次第かな？　という気はします。それと、あまり長くなると面倒なので、一応クエリを受け取る段階で長いとINVALIDエラーを返すとか、そういう実装でやるといいとかはありますね。

質問者：ありがとうございます。

司会者：では時間になりましたので終わりたいと思います。どうもありがとうございました。

（会場拍手）