Go製の全文検索エンジンOmochiを作った.

1.はじめに

膨大な量の電子データから目的となるデータを取得・抽出する情報検索。その技術は広く普及し、多くの人々が、様々な場面でその恩恵を受けています。GoogleやBingをはじめとした、世の中に大きなインパクトを与えるWeb検索がその代表例ですが、物件検索や論文検索、メール検索などその応用は様々です。

さて、今回取り組んだのは、Goによる転置インデックスを用いた全文検索エンジンのスクラッチ実装です。研究で自然言語処理を学んだことをきっかけに、情報検索や転置インデックスといったトピックに強い興味が湧いたので、Elasticsearch等には頼らず、ゼロから実装を行いました。以下、リポジトリになります。

https://github.com/YadaYuki/omochi/

本記事では、Omochiの設計・実装に関する説明を行なっていきます。

2.転置インデックス型・全文検索エンジンOmochi

リポジトリのREADME.mdにも記載がありますが、今回実装した全文検索エンジンOmochiは以下のような特徴を持ちます。

• 転置インデックスを用いた全文検索エンジン.
• RESTful API 経由で、事前に登録した文書群を対象に検索が可能
• 複数単語を用いた検索は、AND検索・OR検索に対応
• 登録可能な言語：日本語, 英語

ここで、全文検索エンジンOmochiの内部構造を概観するために、概要図を見てみましょう.

Omochiは事前登録された文書の中から、検索ワードが含まれる文書のみ抽出し、検索ワードの関連度に応じて並び替えた結果を返すという非常にシンプルな全文検索エンジンです。

概要図にあるように、

• "Toy Story"
• "The Wolf of Wall Street"
• "The NeverEnding Story"

という3つの映画タイトルが文書として事前に登録されていた場合、["toy"]という検索ワードで検索を行うと"toy"という単語を含む["Toy Story"]という検索結果を得ることが可能です。(大文字・小文字は区別しない)

更に、概要図からわかる通り、検索エンジンOmochiは

• 文書の登録(転置インデックスの作成等も含む)を行うインデクサ(Indexer)
• 情報要求に対する文書の検索処理を行うサーチャー(Searcher)

という大きく分けて2つのパーツから構成されていることがわかります。

次章以降では、Omochiの全体的な設計に加え、それぞれのパーツに対する実装の詳細(インデクサ・サーチャ)を見ていきましょう.

3 Omochiの技術選定

タイトルにもある通り、検索エンジンOmochiは開発言語としてはGoを用いています。個人開発なので、使ってみたかったという背景も大きいですが、検索エンジンのように、形態素解析や関連性のスコアリングなど、実行するロジックが複雑であり、速度が求められるアプリケーションとGoの持つ高速性はなかなか相性が良いのではないのでしょうか。

また、後の章でも触れますが、デモで用いるテストデータ(数千 ~ 数万件程度の文書データ)を検索エンジンに登録する処理(seed.go)では、ゴルーチンによる並行処理を用いています。そのため、Goの新たなスレッド(ゴルーチン)の作成と作成した複数のゴルーチンの管理をシンプルに記述することができる点も非常に魅力的であると感じました。

そして、周辺ツールとしては以下を用いています。

• net/http + chi (Web application server)
• Docker
• Mariadb(MySQL)

なお、今回OmochiではORMとして、Facebook製のentを採用しました。entには

• goのコードによるスキーマ(テーブル)の定義が可能
• 自動生成される静的型付けされた関数によって、SQL等を一切書かず、DBに対する操作ができる

等のメリットがあり、DBに対する操作を以下のようなコードで記述することが可能で、とても便利です。(公式Documentより)

func CreateUser(ctx context.Context, client *ent.Client) (*ent.User, error) {
    u, err := client.User.
        Create().
        SetAge(30).
        SetName("a8m").
        Save(ctx)
    ... 

以上がOmochiを構成する技術スタックの紹介になります

4.フォルダ構成概観(アプリケーション設計)

ここでは、Omochiのアプリケーション設計に関する説明を行います。アプリケーションの全体像を把握するために、フォルダ構成を概観してみましょう

├── LICENSE
├── README.md
├── cmd 
│   ├── api/ # サーバ起動のためのコード
│   │   └── main.go
│   ├── migrate/
│   └── seeds/
├── docker
│   ├── api/
│   └── db/
├── docker-compose.yml
├── docs
├── go.mod
├── go.sum
├── pkg # レイヤードアーキテクチャによるアプリケーションの実装
│   ├── common/ # 全体共通の処理・定数等の定義
│   │   ├── constant
│   │   └── slices
│   ├── config/ 
│   ├── domain
│   │   ├── entities
│   │   │   ├── document.go
│   │   │   ├── invert_index.go
│   │   │   ├── posting.go
│   │   │   ├── query.go
│   │   │   └── term.go
│   │   ├── repository
│   │   │   ├── document_repository.go
│   │   │   └── term_repository.go
│   │   └── service
│   │       ├── document_ranker.go
│   │       ├── indexer.go
│   │       ├── invert_index_compresser.go
│   │       ├── searcher.go
│   │       └── tokenizer.go
│   ├── ent/ # go(ent)によるDBのスキーマの定義・entにより自動生成されるコード
│   ├── errors/ 
│   ├── infrastructure
│   │   ├── compresser
│   │   │   ├── zlib_invert_index_compresser.go
│   │   │   └── zlib_invert_index_compresser_test.go
│   │   ├── documentranker
│   │   │   └── tfidfranker
│   │   ├── indexer
│   │   │   ├── indexer.go
│   │   │   └── indexer_test.go
│   │   ├── persistence
│   │   ├── searcher
│   │   │   ├── searcher.go
│   │   │   └── searcher_test.go
│   │   ├── tokenizer
│   │   │   ├── eng
│   │   │   └── ja
│   │   ...
│   ├── interface/ 
│   └── usecase/ 
└── scripts
...

フォルダ構成からわかる通り、今回は以下の4つのレイヤを持つレイヤードアーキテクチャを採用しました。

• インターフェース層(pkg/interface)
• アプリケーション層 (pkg/usecase)
• ドメイン層(pkg/domain)
• インフラストラクチャ層(pkg/infrastructure)

観測した限り、GoによるOSSでレイヤードアーキテクチャを採用しているものは少ないように感じられます。そんな中、Omochiでレイヤードアーキテクチャを採用した理由としては、各レイヤーの外側からレイヤー内部の実装が見えないように抽象化を施すことによって、検索エンジンを構成する具体的な技術を剥がしやすくしたかったことが挙げられます。

ここでいう検索エンジンを構成する具体的な技術とは、例えば以下が挙げられます。

• 形態素解析・分かち書きのツール・ライブラリ(kagome,prose,nltk)
• 転置インデックス・文書を永続化するためのツール(RDB,NoSQL)
• データ操作のためのライブラリ(ent,gorm)
• スコアリングアルゴリズム(TfIdf,BM25)

以上の背景から、アプリケーションの設計として、レイヤードアーキテクチャを採用し、実装を行いました。

5.インデクサの実装(Indexer)

さて、技術選定や設計といったアプリケーションの全体像が掴めたところで、本章からは、具体的な実装レベルの説明を行っていきます。

本章では、検索対象となる文書(Document)の検索エンジンへの登録を行うインデクサのGoによる実装を説明します。OmochiにおけるインデクサはIndexerというGoの構造体で実装されており、Indexer.IndexingDocument関数を実行することによって、文書の登録が可能です。

文書の登録を実行するIndexer.IndexingDocument関数では、登録される文書であるDocumentCreateという型のデータを引数として

• 文書を単語(ターム)に分割し、索引対象となる単語を抽出する
• 文書(ドキュメント)の新規作成(永続化)
• 転置インデックスの作成
• 作成した転置インデックスを圧縮する
• 転置インデックスの新規登録 もしくは 更新(永続化)

という5つの処理を実行します。

5.1 転置インデックスとは？

さて、IndexingDocumentの具体的な実装を見ていく前にOmochi(と多くの検索エンジン)を支えるデータ構造である転置インデックスに関する説明をしていきます。

転置インデックスは、文書群内に登場する「単語$w$」と「単語wが登場する文書iに関する情報$D_i$(文書id、文書内で$w$が登場する位置や回数..etc)」を紐付けた以下のようなデータ構造を指します。

$$\{w_1: [D_1,D_2...],w_2: [D_2,D_5...],... \}$$

ここでは、文書郡内に登場し、索引対象となる単語$w$をターム、タームに紐づいた文書情報の配列($[D_i,...]$)をポスティングリストと呼びます。

それでは例として、以下の3つの文書(映画タイトル)が検索対象となるような検索エンジンを想定して、転置インデックスを作成してみましょう。

1. "Toy Story"
2. "The Wolf of Wall Street"
3. "The NeverEnding Story"

ポスティングリストの各アイテムには、「文書id」と「各文書における単語の登場位置」を格納するとして、以下のような転置インデックスが得られます。

{
    "NeverEnding":[
        {"document_id": 3, "positions_in_document": [1]} // 文書id=3の文書("The NeverEnding Story")の1単語目(0から数える)に登場
    ],
    "Story":[
        {"document_id": 1, "positions_in_document": [1]},
        {"document_id": 3, "positions_in_document": [1]}, 
    ],
    "Street":[
        {"document_id": 2, "positions_in_document": [4]}
    ],
    "The":[
        {"document_id": 2, "positions_in_document": [0]}
        {"document_id": 3, "positions_in_document": [0]}
    ]
    ...
}

多くの検索エンジンでは、このように、転置インデックスという非常にシンプルでわかりやすいデータ構造を事前に作成・保存します。これによって、ユーザが要求する単語の含まれる文書群への高速なアクセスを実現しています。

5.2 Indexer・IndexingDocument関数

転置インデックスについて理解が深まったところで、インデクサの実装を見ていきましょう。実装をみていく前に

• 文書をターム(単語)に分割し、索引対象となるタームを抽出する手法
• 転置インデックスの圧縮手法
• 転置インデックス・文書の永続化

という3点について補足で説明を行います

文書をターム(単語)に分割し、索引対象となるタームを抽出する手法

転置インデックスを作成する際に重要となる文書をターム(単語)に分割し、索引対象となるタームを抽出する手法には、

• n-gram
• Mecab等のソフトウェアを用いた分かち書き

など様々な手法が存在します。その中でも、Omochiは、日本語・英語のそれぞれに対して、Goで分かち書きや形態素解析を容易に実装することができる

• 日本語: Kagomeによる分かち書き・形態素解析
• 英語: Proseによる単語への分割・形態素解析

というツールを活用し、文書の単語への分割および索引対象となる単語を抽出を実現しています。

転置インデックスの圧縮手法

検索エンジンに登録される文書のデータ量が増えると、転置インデックスのサイズが非常に大きくなることがあります。そのため、Omochiを含む、多くの検索エンジンでは転置インデックスを圧縮して永続化しています。

Omochiでは、転置インデックスに含まれるデータの大部分を占めるポスティングリストを圧縮することで、保存時における転置インデックスのデータ量を削減しています。

ポスティングリストの圧縮は以下の2つの手順で実行されます

1. ポスティングリストを格納する配列をgobによりシリアライズ化(バイト型の配列に変換)
2. 「1」により得られたバイト型の配列をzlibによって圧縮。

なお、2つの手順は、いずれもgoの標準パッケージのみで実装が可能です。

転置インデックス(圧縮済み)・文書の永続化

すでに述べた通り、永続化のためのツールとORMにはそれぞれMySQLとentを用いています。

しかし、Indexer・IndexingDocument関数は、「具体ではなく抽象に依存する」というDIPのルールを守るべく、domainレイヤで定義された抽象(DocumentRepositoryインターフェース)に依存するように実装されています。

そのため、MySQLやentといったツール群の知識はIndexerの実装に含んでいません。Indexerを初期化する際に、MySQLと接続するEntクライアントを関数の引数として与えています(Dependency Injection)

以上の3点を踏まえて、IndexerおよびIndexingDocument関数の実装を見てみましょう。

package indexer

import (
	"context"

	"github.com/YadaYuki/omochi/pkg/domain/entities"
	"github.com/YadaYuki/omochi/pkg/domain/repository"
	"github.com/YadaYuki/omochi/pkg/domain/service"
	"github.com/YadaYuki/omochi/pkg/errors"
	"github.com/YadaYuki/omochi/pkg/errors/code"
)

type Indexer struct {
	documentRepository    repository.DocumentRepository
	termRepository        repository.TermRepository
	tokenizer             service.Tokenizer
	invertIndexCompresser service.InvertIndexCompresser
}

func NewIndexer(documentRepository repository.DocumentRepository, termRepository repository.TermRepository, tokenizer service.Tokenizer, invertIndexCompresser service.InvertIndexCompresser) service.Indexer {
	return &Indexer{documentRepository, termRepository, tokenizer, invertIndexCompresser}
}

func (indexer *Indexer) IndexingDocument(ctx context.Context, document *entities.DocumentCreate) *errors.Error {

	// 文書を単語に分割し、索引対象となる単語を抽出する
	tokenizedContent, tokenizeErr := indexer.tokenizer.Tokenize(ctx, document.Content)
	if tokenizeErr != nil {
		return errors.NewError(tokenizeErr.Code, tokenizeErr.Error())
	}

        // 文書(ドキュメント)の新規作成(永続化)
	document.TokenizedContent = make([]string, len(*tokenizedContent))
	for i, term := range *tokenizedContent {
		document.TokenizedContent[i] = term.Word
	}
    
	documentDetail, documentCreateErr := indexer.documentRepository.CreateDocument(ctx, document)
	if documentCreateErr != nil {
		return errors.NewError(documentCreateErr.Code, documentCreateErr.Error())
	}

        // 転置インデックスの作成
	wordToPostingMap := make(map[string]*entities.Posting)
	for position, word := range document.TokenizedContent {
		if _, ok := wordToPostingMap[word]; ok {
			wordToPostingMap[word].PositionsInDocument = append(wordToPostingMap[word].PositionsInDocument, position)
		} else {
			positionsInDocument := []int{position}
			wordToPostingMap[word] = entities.NewPosting(documentDetail.Id, positionsInDocument)
		}
	}

	termCompresseds, termErr := indexer.termRepository.FindTermCompressedsByWords(ctx, &document.TokenizedContent)
	if termErr != nil {
		return errors.NewError(documentCreateErr.Code, termErr.Error())
	}
	terms := make([]entities.TermCreate, len(*termCompresseds))
	wordToTermsMap := make(map[string]*entities.TermCreate)
	for i, termCompressed := range *termCompresseds {
		invertIndex, decompressErr := indexer.invertIndexCompresser.Decompress(ctx, termCompressed.InvertIndexCompressed)
		if decompressErr != nil {
			panic(decompressErr)
		}
		terms[i].Word = termCompressed.Word
		terms[i].InvertIndex = invertIndex
		wordToTermsMap[termCompressed.Word] = &terms[i]
	}

	for wordInDocument, posting := range wordToPostingMap {
		if _, ok := wordToTermsMap[wordInDocument]; ok {
			*wordToTermsMap[wordInDocument].InvertIndex.PostingList = append(*wordToTermsMap[wordInDocument].InvertIndex.PostingList, *posting)
		} else {
			invertIndex := entities.NewInvertIndex(&[]entities.Posting{*posting})
			wordToTermsMap[wordInDocument] = entities.NewTermCreate(wordInDocument, invertIndex)
		}
	}

	upsertTermCompresseds := &[]entities.TermCompressedCreate{}
	for wordInDocument := range wordToTermsMap {
		invertIndexCompressed, compressErr := indexer.invertIndexCompresser.Compress(ctx, wordToTermsMap[wordInDocument].InvertIndex) // 転置インデックスの圧縮
		if compressErr != nil { 
			panic(compressErr)
		}
		termCompressed := entities.NewTermCompressedCreate(wordInDocument, invertIndexCompressed)
		*upsertTermCompresseds = append(*upsertTermCompresseds, *termCompressed)
	}

	// 転置インデックスの新規登録 もしくは 更新(永続化)
	upsertErr := indexer.termRepository.BulkUpsertTerm(ctx, upsertTermCompresseds)
	if upsertErr != nil {
		return errors.NewError(code.Unknown, upsertErr)
	}

	return nil
}

以上がインデクサの実装(Indexer)の説明になります。

6.サーチャの実装(Searcher)

次にユーザからの情報要求(検索ワード)から該当する文書を関連度が高い方から降順にソートして取得する、すなわち、全文検索エンジンの肝である検索機能が実装されたサーチャに関する説明です。サーチャはSearcherというGoの構造体で実装されています。Searcher.Search関数を実行することによって検索を実行することが可能です。

Searcher.Searchは以下のようなQuery型のデータを引数として受け取ります。

type SearchModeType string

const (
	And SearchModeType = "And"
	Or  SearchModeType = "Or"
)

type Query struct {
	Keywords   *[]string      `json:"keywords"`
	SearchMode SearchModeType `json:"mode"` // And,Or
}

フィールドであるSearchModeにはAndもしくはOrを指定することが可能です。これによりkeywords配列内の単語を全て含む文書を検索するか(And検索)、少なくともkeywords配列内の単語のいずれか一つを含む文書を検索するか(Or検索)を切り替えています。

Searcher.Search関数内では、

• 圧縮済み転置インデックス(InvertIndexCompressed)の取得
• 転置インデックスの解凍
• 転置インデックスに登録されている文書IDに該当する文書群のデータ取得
• 取得した文書群の関連度に応じた並び替え(検索ワードが1語であった場合のみ)

という4つの処理を内部的に実装行っています。

Searcher.Search関数の内部処理が概観できたところで、

• インメモリ転置インデックス
• 文書のスコアリング

という2点について補足説明を行なっていきます。

インメモリ転置インデックス

検索エンジンでは、検索処理の高速化のための工夫として、「文書内で頻出するターム」や「よく検索されるターム」を中心に転置インデックスの一部をストレージ(RDB等)ではなく、インメモリにキャッシュしておくことが一般的です。

Omochiでは、Searcher構造体にinvertIndexCachedというmap型(key:ターム(単語),value:転置インデックス)のフィールドを用意することでそれを実現しました。

package searcher

...

type Searcher struct {
	invertIndexCached  map[string]*entities.InvertIndex // 転置インデックスの一部をインメモリで格納するための辞書型変数
	...
}

Searcher.Search関数では、検索ワードに該当する転置インデックスを取得する際、いきなりストレージには問い合わせず、まず、invertIndexCached内に、該当する転置インデックスが存在しないかをチェックしています。

文書のスコアリング

Googleをはじめとする検索エンジンでは、独自のアルゴリズムにより、検索ワードに対する文書の関連度を算出し、関連度が高いものから順番に検索結果を提示しています。

現時点の、Omochiは検索ワードが1語であった場合のみ、関連度に応じて検索結果となる文書が並び替えられるように実装されています。関連度の算出には、TF-IDFを採用しました。

$$TF_i(t) = freq(t,d_i)$$

$$IDF(t) = log((1+n)/(1+df_t))$$

$$TF\verb|-|IDF_i(t) = TF_i(t) * (IDF(t) + 1)$$

TF-IDFによる文書の並び替えは、TfIdfDocumentRankerという構造体で実装されています。長くなるためここには掲載しませんが、興味がある方はぜひ見てみてください。

以上の2点を踏まえて、Searcherの実装を見てみましょう。

package searcher

import (
	"context"
	"fmt"
	"log"

	"github.com/YadaYuki/omochi/pkg/domain/entities"
	"github.com/YadaYuki/omochi/pkg/domain/repository"
	"github.com/YadaYuki/omochi/pkg/domain/service"
	"github.com/YadaYuki/omochi/pkg/errors"
	"github.com/YadaYuki/omochi/pkg/errors/code"
)

type Searcher struct {
	invertIndexCached  map[string]*entities.InvertIndex
	termRepository     repository.TermRepository
	documentRepository repository.DocumentRepository
	compresser         service.InvertIndexCompresser
	documentRanker     service.DocumentRanker
}

func NewSearcher(invertIndexCached map[string]*entities.InvertIndex, termRepository repository.TermRepository, documentRepository repository.DocumentRepository, compresser service.InvertIndexCompresser, documentRanker service.DocumentRanker) service.Searcher {
	return &Searcher{invertIndexCached, termRepository, documentRepository, compresser, documentRanker}
}

func (s *Searcher) Search(ctx context.Context, query *entities.Query) ([]*entities.Document, *errors.Error) {

	if len(*query.Keywords) == 1 {
		return s.searchBySingleKeyword(ctx, query)
	}
	switch query.SearchMode { // SearchModeによる条件分岐
	case entities.Or:
		return s.searchOr(ctx, query)

	case entities.And:
		return s.searchAnd(ctx, query)

	default:
		return nil, errors.NewError(code.Unknown, fmt.Sprintf("unsupported search mode: %s", query.SearchMode))
	}
}

func (s *Searcher) searchBySingleKeyword(ctx context.Context, query *entities.Query) ([]*entities.Document, *errors.Error) {
	invertIndex, ok := s.invertIndexCached[(*query.Keywords)[0]] // インメモリの転置インデックスをチェック
	if !ok {
		termCompressed, err := s.termRepository.FindTermCompressedByWord(ctx, (*query.Keywords)[0]) // 圧縮済み転置インデックス(InvertIndexCompressed)の取得
		if err != nil {
			return nil, errors.NewError(err.Code, err)
		}
		invertIndexCompressed := termCompressed.InvertIndexCompressed
		invertIndex, err = s.compresser.Decompress(ctx, invertIndexCompressed) // 転置インデックスの解凍
		if err != nil {
			return nil, errors.NewError(err.Code, err)
		}
	}

	documentIds := []int64{}
	for _, postingList := range *invertIndex.PostingList {
		documentIds = append(documentIds, postingList.DocumentRelatedId)
	}

	documents, documentErr := s.documentRepository.FindDocumentsByIds(ctx, &documentIds) // 転置インデックスに登録されている文書IDに該当する文書群のデータ取得
	if documentErr != nil {
		return nil, errors.NewError(documentErr.Code, documentErr)
	}
	sortedDocument, sortErr := s.documentRanker.SortDocumentByScore(ctx, (*query.Keywords)[0], documents) // 取得した文書群の関連度に応じた並び替え
	if sortErr != nil {
		return nil, errors.NewError(sortErr.Code, sortErr)
	}
	return sortedDocument, nil
}

func (s *Searcher) searchOr(ctx context.Context, query *entities.Query) ([]*entities.Document, *errors.Error) {
	...{OR検索の実装}
}

func (s *Searcher) searchAnd(ctx context.Context, query *entities.Query) ([]*entities.Document, *errors.Error) {
	....{AND検索の実装}
}

以上がサーチャの実装(Searcher)の説明になります。

7.動作確認・デモ

7.1 事前準備

本章では、数千件〜数万件程度のテストデータを用いて、実際にOmochiによる全文検索を試していきます。リポジトリ内には、Omochiが対応する言語である日本語と英語のそれぞれに対して、テストデータを用意しました。

日本語のテストデータとしては、本記事の筆者が最も愛する漫画の一つである「ドラえもん」のコミックタイトル(1,316件)を使用させていただきます。(英語のテストデータには45,466件の映画タイトルのデータセットを使用させていただきました。)

ここでは、例として、日本語のデータセットを用いた検索の動作確認を行います。

検索を実行していく前に事前準備として、TSVファイルで用意されている文書のテストデータ(ドラえもんのコミックタイトル)をインデクサにより、検索エンジンに登録します。

README.mdの「Setup」の章に書かれた手順により、Dockerのネットワーク作成やDBのマイグレーション等は終えている想定で、apiコンテナ内部で以下を実行します。

$ go run ./cmd/seeds/ja/seed.go

上のコマンドを実行すると、検索エンジンにTSV上のドラえもんコミックタイトルが、検索対象の文書として並行に登録されていきます。

上手く検索エンジンへの登録が実行できた場合、以下のような出力が得られます。

$ go run ./cmd/seeds/ja/seed.go 
2022/07/23 19:50:57 start indexing documents
2022/07/23 19:50:57 indexed: 「真実の旗印」はつねに正しい
2022/07/23 19:50:57 indexed: 石ころぼうし
2022/07/23 19:50:57 indexed: ドラえもんあげる
2022/07/23 19:50:57 indexed: 空とぶ荷ふだ
2022/07/23 19:50:57 indexed: メモリーディスク
2022/07/23 19:50:57 indexed: 動物指キャップ
2022/07/23 19:50:57 indexed: ドラえもんがやってきた
....

以上で、デモのための事前準備は完了です！

7.2 ドラえもんのコミックタイトルを検索する

さて、長い道のりでしたが、いよいよ検索エンジンを試していきます。

既に述べた通り、OmochiはRESTful API経由でキーワード検索を実行することが可能です。/v1/document/search に以下の2つのパラメータを付与して、HTTP GETリクエストを送信します。

• "keywords": 検索ワード. 検索ワードが複数の場合は"hoge,fuga,piyo"のように","(カンマ)区切りで指定する
• "mode": 検索モード. "And" もしくは "Or" が指定可能(Optional)

curlコマンドにより、検索機能の動作確認を行います。まずは、"keywords"="ドラえもん","mode"=nullとして、”ドラえもん”という単語が含まれる文書を検索してみましょう。

$ curl "http://localhost:8081/v1/document/search?keywords=ドラえもん" | jq .
{
  "documents": [
    {
      "id": 3492,
      "content": "ドラえもんの歌",
      "tokenized_content": [
        "ドラえもん",
        "歌"
      ],
      "created_at": "2022-07-23T19:56:22+09:00",
      "updated_at": "2022-07-23T19:56:22+09:00"
    },
    {
      "id": 3250,
      "content": "ドラえもんだらけ",
      "tokenized_content": [
        "ドラえもん",
        "だらけ"
      ],
      "created_at": "2022-07-23T19:56:21+09:00",
      "updated_at": "2022-07-23T19:56:21+09:00"
    },
    {
      "id": 2691,
      "content": "ドラえもん登場！",
      "tokenized_content": [
        "ドラえもん",
        "登場"
      ],
      "created_at": "2022-07-23T19:56:18+09:00",
      "updated_at": "2022-07-23T19:56:18+09:00"
    },
    ....

「ドラえもんの歌」,「ドラえもんだらけ」...など、"ドラえもん"という単語を含む文書のみを正しく検索できていることがわかります。

次に、And検索を試してみます。"keywords"="のび太,ジャイアン","mode"=Andとして、”のび太”と”ジャイアン”という単語が両方含まれる文書を検索してみましょう。

$ curl "http://localhost:8081/v1/document/search?keywords=ジャイアン,のび太&mode=And" | jq . 
{
  "documents": [
    {
      "id": 3336,
      "content": "ジャイアン反省・のび太はめいわく　",
      "tokenized_content": [
        "ジャイアン",
        "反省",
        "のび太",
        "めいわく"
      ],
      "created_at": "2022-07-23T19:56:21+09:00",
      "updated_at": "2022-07-23T19:56:21+09:00"
    }
  ]
}

検索結果としては、一つのみですが、”のび太”と”ジャイアン”の両方を含む文書を正しく検索できていることがわかります。

最後に、Or検索です。"keywords"="のび太,ジャイアン"(Andと同じ),"mode"=Orとして、”のび太”か”ジャイアン”という単語のいずれかが含まれる文書を検索してみましょう。

$ curl "http://localhost:8081/v1/document/search?keywords=ジャイアン,のび太&mode=Or" | jq . 
{
  "documents": [
    {
      "id": 2707,
      "content": "ジャイアンよい子だねんねしな",
      "tokenized_content": [
        "ジャイアン",
        "よい",
        "子",
        "ねんね",
        "しな"
      ],
      "created_at": "2022-07-23T19:56:18+09:00",
      "updated_at": "2022-07-23T19:56:18+09:00"
    },
    {
      "id": 2720,
      "content": "のび太のブラックホール",
      "tokenized_content": [
        "のび太",
        "ブラックホール"
      ],
      "created_at": "2022-07-23T19:56:18+09:00",
      "updated_at": "2022-07-23T19:56:18+09:00"
    },
    {
      "id": 2729,
      "content": "のび太が消えちゃう？",
      "tokenized_content": [
        "のび太",
        "消え",
        "ちゃう"
      ],
      "created_at": "2022-07-23T19:56:18+09:00",
      "updated_at": "2022-07-23T19:56:18+09:00"
    },
    ... 

「ジャイアンよい子だねんねしな」,「のび太のブラックホール」... など、”のび太”か”ジャイアン”のいずれかが含まれる文書が正しく検索できていることが確認できます。

8.まとめ

長くなりましたが、以上が実装の説明になります。

今回実装した検索エンジンOmochiはリポジトリにJust a toyと書かれている通り、Elasticsearch等の既存のツールを活用した検索エンジンと比較するとパフォーマンスや機能性の面で実用性は低いです。

しかし、Omochiようなの最小限の機能のみを持つ検索エンジンを実装する作業は、転置インデックスをはじめとする情報検索の基礎知識を理解する上で大きな助けとなりました。

本記事を読んだ方の中で、Omochiを気に入ってもらえれば、リポジトリにstarをつけてもらえると励みになります。

9.参考文献

• Information Retrieval: Implementing and Evaluating Search Engines
• 情報検索アルゴリズム
• Pythonではじめる 情報検索プログラミング
• WEB+DB PRESS Vol.126. 特集 Goで作って学ぶ検索エンジン
• 検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏