この記事はRecruit Engineers Advent Calendar 2020の11日目の記事です。

TL;DR

対象読者は転置インデックスを少し知ってるくらいの検索初心者です
検索エンジンに興味が湧き、仕組みを知るためにGoで自作しています
自作検索エンジンのAnalyzerとIndexerとSearcherを紹介します

はじめに

ここ最近、以下の観点から情報検索への興味が強いです。

技術面: フリーワード検索機能を実装した際にElasticsearchの使いやすさと多機能さに圧倒されたこと。
プロダクト面: 検索がプロダクトに不可欠な機能かつ、非エンジニアにとって検索エンジンは未知であり知識の乖離が大きいため、エンジニアだからこその価値を提供しやすいこと。

検索エンジンの仕組みを知り情報検索分野に詳しくなるために自作し始めました。プログラミング言語Goを読んで学んでいるので、練習としてGoで実装します。また、検索初心者が参考にできるような簡単で教育的な検索エンジンの実装が見つからなかったので、検索初心者の力になれると嬉しいです。

現在進行形で実装中かつ検索初心者なため、アドバイスやIssue、PullRequestなど頂けると嬉しいです。ソースコードは以下で管理されています。

github.com

この本を参考にしている部分が多いです。

作者:山田浩之,末永匡
発売日: 2014/09/25
メディア: Kindle版

実装したものの概要

大きく以下の機能を実装しました。

Analyzer: 表記揺れを吸収するCharFilterとTokenFilter、英文を分かち書きするTokenizer
Indexer: ドキュメントのインデックスへの追加、転置インデックス
Searcher: 全マッチ検索、フレーズ検索
Storage: MySQLでの転置インデックス等の永続化

全体の構成は以下のようになっています。インデックス作成部分と検索部分に分かれています。

使用例は以下です。正しくフレーズ検索され、"Amazon Prime"と連続で出ている1,3番目のみヒットし、"Amazon"と"Prime"が離れている2番目はヒットされていないことが分かります。また、"amAzon PRime"のような表記揺れを吸収していることも分かります。

func main() {
    // DBと接続
    config := stalefish.NewDBConfig("root", "password", "127.0.0.1", "3306", "stalefish")
    db, _ := stalefish.NewDBClient(config) // エラーハンドリングは省略

    storage := stalefish.NewStorageRdbImpl(db) // 永続化を責務にするストレージ
    analyzer := stalefish.NewAnalyzer([]stalefish.CharFilter{}, stalefish.StandardTokenizer{}, []stalefish.TokenFilter{stalefish.StemmerFilter{}, stalefish.LowercaseFilter{}, stalefish.StopWordFilter{}}) // 文書を単語に分割するアナライザ
    indexer := stalefish.NewIndexer(storage, analyzer, make(stalefish.InvertedIndexMap)) // 転置インデックスを作成するインデクサ(アナライザーとストレージを注入する)

    // ドキュメントを追加
    indexer.AddDocument(stalefish.NewDocument("You can watch lots of interesting dramas on Amazon Prime."))　
    indexer.AddDocument(stalefish.NewDocument("Forest phenomena in the Amazon are a prime concern."))
    indexer.AddDocument(stalefish.NewDocument("I watched amazon prime until late at night yesterday."))
    indexer.AddDocument(stalefish.NewDocument("Breaking Bad is a very jarring drama."))

    // フレーズ検索を行う
    q := stalefish.NewPhraseQuery("amAzon PRime", analyzer)
    seacher := q.Searcher(storage)
    result, _ := seacher.Search() // エラーハンドリングは省略
    fmt.Println(result)
    // result: [{1 You can watch lots of interesting dramas on Amazon Prime.} {3 I watched amazon prime until late at night yesterday.}]
}

詳細

Analyzer, Indexer, Searcher, Storageを少し掘り下げます。

Analyzer

Analyzerは、0個以上のChar Filterと1個のTokenizerと0個以上のToken Filterから構成されます。 Analyzerによって、トークン分割をしてくれたり、クエリの表記揺れを吸収してくれたり、無駄なトークンのフィルタリングをしてくれたりします。

   analyzer := stalefish.Analyzer{
        []stalefish.CharFilter{stalefish.MappingCharFilter{map[string]string{":)": "_happy_", ":(": "_sad_"}}}, 
        stalefish.StandardTokenizer{},
        []stalefish.TokenFilter{stalefish.LowercaseFilter{}, stalefish.StopWordFilter{}, stalefish.StemmerFilter{}},
    }
    fmt.Println(analyzer.Analyze("I have a lot of TASKs. I am very sad :("))
    // output: ["lot", "task", "am", "very", "sad", "sad"]

以下の表のように左から右へ処理が進んでいきます。

Analyze前	MappingCharFilter後	StandardTokenizer後	LowercaseFilter後	StopWordFilter後	StemmerFilter後
I have a lot of TASKs. I am very sad :(	I have a lot of TASKs. I am very sad sad	I, have, a, lot, of, TASKs, I, am, very, sad, sad	I, have, a, lot, of, tasks,I, am, very, sad, sad	lot, tasks, am, very, sad, sad	lot, task, am, very, sad, sad

IndexerもSearcherもそれぞれ文書やクエリをAnalyzerに通してから、転置インデックスを処理しています。

Indexer

転置インデックスについて

検索エンジンでは高速な検索を実現するために本の目次のような転置インデックスを事前に作成します。 Indexerはまずメモリ上に転置インデックスを保持し、メモリ上の転置インデックスのサイズが大きくなってきたらストレージの転置インデックスとマージしてストレージに保存します。

転置インデックスには、どの単語に対してどのドキュメントが紐づいているかという情報だけでなく、どのドキュメントのどこにその単語が出現しているかの位置情報も保存されています。単語の位置情報は、"Amazon Prime"など順序が大切な場合にフレーズで検索をする場合に役立ちます。

以下が転置インデックスのデータ構造ですが、転置リストでは文書IDと出現位置だけではなくて、スコア計算のために単語出現数も保持しています。

// 転置インデックス
// TokenIDー>転置リストのマップ
type InvertedIndexMap map[TokenID]InvertedIndexValue

// 転置リスト
type InvertedIndexValue struct {
    Token          Token       `db:"token"`
    PostingList    PostingList `db:"posting_list"`    // トークンを含むポスティングスリスト
    DocsCount      int         `db:"docs_count"`      // トークンを含む文書数
    PositionsCount int         `db:"positions_count"` // 全文書内でのトークンの出現数
}

// ポスティングリスト。文書IDのリンクリスト
type PostingList []Posting

type Posting struct {
    DocumentID     DocumentID // 文書のID
    Positions      []int      // 文書中の位置情報
    PositionsCount int        // 文書中の位置情報の数
}

転置インデックス作成について

今回作ったIndexerによる転置インデックス作成処理の流れは以下です。

Analyzerで文章を分割しトークンを取り出す。
トークンごとにポスティングリストを作ってメモリ上の転置インデックスに追加する。
捜査する際にドキュメントIDを利用するので転置リストの全てのポスティングリストをドキュメントIDの昇順でソートする。
メモリ上の転置インデックスのサイズが閾値を超えたら、ストレージ上の転置インデックスにマージする。

ここで重要なのは、メモリ上の転置インデックスは閾値を超えなければストレージ上に永続化されないということです。閾値を大きくするとストレージアクセス回数が増加しますが、メモリ使用量は減少するトレードオフになります。 Elasticsearchでもドキュメント追加してすぐに永続化されるわけではなく、追加してしばらくしないと検索対象に含まれないラグがあります。

Searcher

Seacherは検索クエリを受けとり、永続化された転置インデックスからドキュメントを検索します。今回はトークンの出現順序を考慮するフレーズ検索を実装しました。チープで力任せな実装になっておりいつか改良したいです。

フレーズ検索の全体の流れは以下です。

検索クエリをトークン分割する。
それぞれのトークンのポスティングリストをストレージから取得し、文書IDとその出現位置のリストを取り出す。
全てのトークンで同一の文書IDが含まれ、かつ、各トークンの出現位置が連接していれば検索結果に追加する。

連接しているかどうかは、トークンの相対出現位置を計算し、同じ相対出現位置になるならフレーズになっていると判定します。 ”Amazon Prime"というフレーズを例に説明します。 "Amazon"は文書Kの位置[3,7]に出現し、"Prime"は文書Kの位置[8,18,32]に出現すると転置インデックスを走査して分かったとします。(7番目と8番目に出現しているので連接) "Amazon"は前から0番目のトークンであり"Prime"は1番目のトークンであるので、N番目であることを先程の位置情報から引いて相対位置を計算します。 "Amazon"はそのままの[3,7]となり、"Prime"は1引いて[7,17,31]になります。 "Amazon"も"Prime"も相対位置7に出現しているので、フレーズになっていると判定します。

Storage

MySQLをストレージとして利用し、転置インデックスやドキュメント、トークンを永続化しています。 MySQLは最適な選択肢はないと思っているので、あとから実装を取り替えやすいようにStorageインターフェースを定義し実装を分離しています。

ドキュメントやトークンのID振り分けはMySQLに任せていたり、転置インデックスをJSONとしてMySQLに保存していたりします。

おわりに

アドベントカレンダーに12月11日に記事投稿するとなり、その日までにできたところを記事にしようと考えていましたが、ドキュメントをインデキシングしてフレーズ検索をして結果を返すというキリが良いところまで実装できて良かったです。 Done is better than perfectの精神で実装しており、まだおもちゃでバグだらけ残念な実装になっている部分も多いですが誰かの役に立てば嬉しいです。

これからは以下の機能を実装していきます。

ポスティングリストのリンクリスト実装
転置インデックスの圧縮
MatchQueryの実装
TF/IDFでのスコアリング
検索結果のソート
任意のドキュメントフィールドを設定
MySQLを他にリプレイス
並行処理などパフォーマンスチューニング
形態素解析やNgramなどTokenizerの拡張

参考

logmi.jp

artem.krylysov.com

github.com