🤖

🤖

:gijutsu_burogu:

任意のバージョンのElasticsearchでSudachiプラグインを使う

Elasticsearch用の形態素解析器にKuromojiとは別にSudachiがあります。 こちらは外部プラグインとして提供されています。 詳しくは以下をご覧ください。

qiita.com

以下のリポジトリでElasticsearch用のSudachiプラグインが管理されています。

github.com

問題

直接ダウンロードできるように配布されているプラグインは、Elasticsearch 7.8 までしかありません。 そのため、Elasticsearch 7.13用のSudachiプラグインを取得できませんでした。

解決策

READMEにも書かれている通り、自前でプラグインをビルドする必要があります。 ./gradlew -PelasticsearchVersion=7.13.0 buildとすると、/build/distributions/配下にプラグインが生成されます。

▶ gradle -v

------------------------------------------------------------
Gradle 7.1
------------------------------------------------------------

Build time:   2021-06-14 14:47:26 UTC
Revision:     989ccc9952b140ee6ab88870e8a12f1b2998369e

Kotlin:       1.4.31
Groovy:       3.0.7
Ant:          Apache Ant(TM) version 1.10.9 compiled on September 27 2020
JVM:          11.0.3 (Amazon.com Inc. 11.0.3+7-LTS)
OS:           Mac OS X 10.15.6 x86_64

ハマりどころ

バージョンXを指定しビルドした後に、バージョンYを指定してビルドすると、2回目のビルドではバージョンX用のSudachiプラグインが生成されてしまうということがありました。 1回目のビルドのキャッシュが残っていることが原因と考えられ、/build配下を削除してから再ビルドする必要があります。

DynamoDBでmap型を更新する(AWS SDK for Go)

はじめに

Users テーブル

Id Weapons
0 {"sord": "Normal", "hammer" : "Failure"}
1 {"hammer":"Normal"}

以上のようなテーブルがある時、Id:0のユーザーが新しく武器bowを取得した場合はどのようにクエリを発行すれば良いでしょうか。

問題点

上記のように既にWeaponsのmapが存在している場合は、更新することができます。 しかし、ユーザーはまだ何も武器を持ってない状態(Weaponsはnullの場合)もあり得ます。 この場合はエラーが発生してしまいます。

解決策

DBへ1リクエストでは、この問題点は解決することができないので3リクエストによって解決します。

func main() {
    ctx := context.Background()
    config := aws.NewConfig().
        WithRegion("ap-northeast-1").
        WithEndpoint("http://127.0.0.1:8000").
        WithCredentials(credentials.NewStaticCredentials("dummy", "dummy", "dummy"))

    client := client{
        dynamodb.New(session.Must(session.NewSession(config))),
    }
    if err := client.update(ctx); err != nil {
        log.Fatalln(err)
    }
}

type client struct {
    dynamodb *dynamodb.DynamoDB
}

func (c *client) update(ctx context.Context) error {
    err := c.updateWithWeapons(ctx) // 1.Weaponsが存在しなければ、ErrCodeConditionalCheckFailedExceptionを返却
    if err != nil {
        if aerr, ok := err.(awserr.Error); ok {
            if aerr.Code() == dynamodb.ErrCodeConditionalCheckFailedException {
                err = c.updateNoWeapon(ctx) // 2.Weaponsが存在すれば,ErrCodeConditionalCheckFailedExceptionを返却
                if err != nil {
                    if aerr, ok := err.(awserr.Error); ok {
                        if aerr.Code() == dynamodb.ErrCodeConditionalCheckFailedException { // 1と2の間で別プロセスでWeaponsが追加されていた場合
                            err = c.updateWithWeapons(ctx) // 再びupdateする
                        }
                    }
                }
            }
        }
    }
    return err
}

func (c *client) updateWithWeapons(ctx context.Context) error {
    updateItemInput := &dynamodb.UpdateItemInput{
        TableName: aws.String("Users"),
        Key: map[string]*dynamodb.AttributeValue{
            "Id": {N: aws.String("0")},
        },
        ExpressionAttributeNames: map[string]*string{
            "#WEAPONS": aws.String("Weapons"),
            "#WEAPON":  aws.String("bow"),
        },
        ExpressionAttributeValues: map[string]*dynamodb.AttributeValue{
            ":st": {S: aws.String("normal")},
        },
        UpdateExpression:    aws.String("set #WEAPONS.#WEAPON = :st"),
        ConditionExpression: aws.String("attribute_exists(Id) and attribute_exists(Weapons)"), // WeaponsがなければConditionalCheckFailedExceptionを発生させる
    }
    _, err := c.dynamodb.UpdateItemWithContext(ctx, updateItemInput)
    return err
}

func (c *client) updateNoWeapon(ctx context.Context) error {
    updateItemInput := &dynamodb.UpdateItemInput{
        TableName: aws.String("Users"),
        Key: map[string]*dynamodb.AttributeValue{
            "Id": {N: aws.String("0")},
        },
        ExpressionAttributeNames: map[string]*string{
            "#WEAPONS": aws.String("Weapons"),
        },
        ExpressionAttributeValues: map[string]*dynamodb.AttributeValue{
            ":map": {M: map[string]*dynamodb.AttributeValue{
                "bow": {S: aws.String("normal")},
            }},
        },
        UpdateExpression:    aws.String("set #WEAPONS = :map"),
        ConditionExpression: aws.String("attribute_exists(Id) and attribute_not_exists(Weapons)"), // WeaponsがあればConditionalCheckFailedExceptionを発生させる
    }
    _, err := c.dynamodb.UpdateItemWithContext(ctx, updateItemInput)
    return err
}

ソースコード: https://github.com/kotaroooo0/for_output/blob/master/dynamodb/main.go

Go Conference 2021 Springに登壇したメモ

資料

4500PV, 270ブクマで良い反応があったとポジティブに捉えています。

資料作成

こちらの書籍を参考にしました。

この本では「人を動かす」「一人歩きする」資料を「早く作る」ことが重要と述べられています。 今回は提案資料ではないので「人を動かす」の部分は注力せず、「一人歩きする」資料の作成に注力しました。

情報検索に興味が沸いたのでGoで検索エンジンを自作している

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

TL;DR

はじめに

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

  • 技術面: フリーワード検索機能を実装した際にElasticsearchの使いやすさと多機能さに圧倒されたこと。

  • プロダクト面: 検索がプロダクトに不可欠な機能かつ、 非エンジニアにとって検索エンジンは未知であり知識の乖離が大きいため、エンジニアだからこその価値を提供しやすいこと。

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

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

github.com

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

実装したものの概要

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

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

f:id:kotaroooo0:20201210214726p:plain

使用例は以下です。 正しくフレーズ検索され、"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による転置インデックス作成処理の流れは以下です。

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

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

Searcher

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

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

  1. 検索クエリをトークン分割する。
  2. それぞれのトークンのポスティングリストをストレージから取得し、文書IDとその出現位置のリストを取り出す。
  3. 全てのトークンで同一の文書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

Goでビットベクトルを利用してSetを実装する

はじめに

プログラミング言語Goを読んでいて、ビットベクトルを利用してSetを実装するところがありました。 シンプルかつ思いつきもしない方法だったので紹介します。

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

過去に以下の記事でGoでのSetの実装について触れましたが、ビットベクトルを扱う方法には触れていませんでした。

kotaroooo0-dev.hatenablog.com

ビットベクトル

プログラミング言語Goではuint型のSetが実装されていました。 構造体としては、[]uint64がSetを表します。 indexが0の場合は0~63がSetに含まれているか、indexが1の場合は64~127がSetに含まれているかを表します。 ビットが1であれば、その数値はSetに含まれていることを表します。 以下の表は、集合{0,1,2,3,64,65,68,69}を表します(表中の・・・が全て0の場合)。

index uint64(ビット表記)
0 00000・・・001111
1 00000・・・110011

セットの要素が負でない小さな整数で、セットが多数の要素を持ち、和集合や共通集合など集合操作がよく行われる場合では、ビットベクトルによるSetは効果的です。

実装

type IntSet struct {
    words []uint64
}

func (s *IntSet) Has(x int) bool {
    word, bit := x/64, uint(x%64)
    return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

func (s *IntSet) Add(x int) {
    word, bit := x/64, uint(x%64)
    for word >= len(s.words) {
        s.words = append(s.words, 0)
    }
    s.words[word] |= 1 << bit
}

func (s *IntSet) Remove(x int) {
    word, bit := x/64, uint(x%64)
    if word > len(s.words) {
        return
    }
    s.words[word] &= ^(1 << bit)
}

func (s *IntSet) UnionWith(t *IntSet) {
    for i, tword := range t.words {
        if i < len(s.words) {
            s.words[i] |= tword
        } else {
            s.words = append(s.words, tword)
        }
    }
}

func (s *IntSet) IntersectWith(t *IntSet) {
    for i, sword := range s.words {
        sword &= t.words[i]
    }
    s.words = s.words[:len(t.words)]
}

正の整数以外の場合

負の数を含む場合やstring型の場合でも、正の整数へマッピングすることでビットベクトル形式のSetを表現できるのではないかと思います。 負の数の場合は、負の数にならないように足せば解決できそうです。 string型の場合は、何らかの関数で数値に変換して正の整数へマッピングすることが可能です。 しかし、uint64型で全ての文字列を表現することが不可能なのは自明です。 そのため、集合に含まれていないが含まれていると判断してしまう偽陽性が発生します。 2年前に記事にした確率的データ構造であるブルームフィルタと似ているなと思いました。

kotaroooo0-dev.hatenablog.com

Goでトライ木を実装して共通接頭辞を可視化する

作ったもの

トライ木をGraphvizで可視化するものを作りました。

github.com

$ brew install graphviz
$ go get github.com/kotaroooo0/mute

$ vi data.txt
$ mute -s data.txt | dot -T png -o sample.png

# data.txt
keynote
keycase
king
kingdom
macbook

keynotekeycasekeyまで一致しているのが分かります。

遊び方

Trie木を可視化を行う事で、Slackの共通接頭辞大会などしてみてください。 あいつとあいつのidいつも間違えそうになるんだよなと再認識したりできます。 Slackのチャンネルで/whoと入力するとメンバーが取得でき、data.txtにコピーしてください。 mute -s data.txt | dot -T png -o sample.pngとすれば、画像が出力されます。

トライ木とは

トライ木は順序付き木の一種です。 trieの名称は"retrieval"が語源です。 形態素解析に使われる辞書などに用いられています。

共通接頭辞検索に適したデータ構造であり、時間計算量、空間計算量共に優れています。 空間計算量に関しては様々なデータ構造が提案されています。

実装

github.com

主にアルゴリズムの要素があるのは以下の2点です。

トライ木を作成する部分

挿入したい単語長分のループを回し、挿入を行います。 すでに接頭辞が一致している場合はさらに一個深いノードへ進んでいくだけで、一致しなくなったら一個深い段階に新しいノードを作成します。

func (n *Node) insert(w string) error {
    runes := []rune(w)
    currentNode := n
    for i, r := range runes {
        if nextNode, ok := currentNode.Children[r]; ok {
            currentNode = nextNode
        } else {
            currentNode.Children[r] = newNode(string(r), make(map[rune]*Node), false)
            currentNode = currentNode.Children[r]
        }

        // 終端にチェック
        if i == len(runes)-1 {
            currentNode.End = true
        }
    }
    return nil
}

トライ木を探索しdotfileを生成する部分

DFSで探索を行いながら、dotfileを生成していきます。 visitAll再帰的に処理する事でDFSを実現しています。

無名関数で実装することにより、generateDotfile関数で全て完結することができます。 無名関数で再帰を行うには、var visitAll func(n *Node)のように宣言することが必須であり、これがないとvisitAllが未定義とコンパイルエラーになります。

例えばに、無名関数で実装せずにグローバルにvisitAll関数を宣言しようとすると、g := gographviz.NewGraph()をグローバル宣言する必要がでてきます。

func generateDotfile(trie *Node, output string) (string, error) {
    g := gographviz.NewGraph()
    g.SetName("G")
    g.SetDir(true)

    var fontSize = "35"
    var visitAll func(n *Node)
    visitAll = func(n *Node) {
        for _, v := range n.Children {
            g.AddNode("G", strconv.Itoa(n.ID), map[string]string{"label": n.getLabel(), "shape": n.getShape(), "fontsize": fontSize})
            g.AddNode("G", strconv.Itoa(v.ID), map[string]string{"label": v.getLabel(), "shape": v.getShape(), "fontsize": fontSize})
            g.AddEdge(strconv.Itoa(n.ID), strconv.Itoa(v.ID), true, nil)
            visitAll(v)
        }
    }
    visitAll(trie)

        // 略    

    return g.String(), nil
}

おわりに

今回はシンプルな木のデータ構造としてトライ木を実装しました。 しかし、トライ木を実装する際のデータ構造やアルゴリズムには多くの種類があります。 ダブル配列やLOUDSが有名どころのようです。

takeda25.hatenablog.jp