Go言語でフレーズ検索を実装してみる

この記事はただの集団 AdventCalendar PtW.2019の6日目の記事です。 昨日はumeneriさんのGKE上にElasticsearchとcerebro環境を構築するでした。

本記事では、Golangを使って検索エンジンのフレーズ検索機能を実装してみます。

フレーズ検索とは

文章の集合からダブルクォートでくくった文字に合致する部分を見つける検索です。 例えば、"エンジニア 東京"で検索するとエンジニア 東京というフレーズに合致するものだけを取得します。 エンジニア東京だけに合致するものは結果に含みません。 検索エンジンはフレーズ検索を実現するだけでなく、効率的に処理する必要があります。 本記事では、フレーズ検索を行うためのアルゴリズムの実装を行います。

転置インデックス

一般的に、時間がかかるテキストの線形走査を避けるためには、事前に文書をインデックス付します。 ほとんどすべての情報検索エンジンでは、インデックスに転置インデックスを用います。

転置インデックスとは、簡単に言うと「用語とその用語の文書集合内の出現位置のマッピング」です。 転置インデックスは、文書集合内に含まれる用語のリストである辞書と各用語に紐づく出現位置のリストであるポスティングリストから構成されます。

今回は簡単のため、ポスティングリストにはその用語のテキスト集合内での出現位置の配列を持つようにします。 このようにポスティングリストに構造を持たないものをschema-independent-indexと呼びます。

package index

// schema independent index
type Index struct {
    Dictionary map[string][]int
}

また、Indexを作成するメソッドも追加しておきます。

func NewIndex(dictionary map[string][]int) *Index {
    index := new(Index)
    index.Dictionary = dictionary
    return index
}

準備

まず、今回実装する関数の説明をしておきます。 今回は以下の4つの関数を実装します。

  • next(t string, current int) int
    • 現在の位置(current)より後ろにある最初の用語tの場所を返す。
  • prev(t string, current int) int
    • 現在の位置(current)より前にある最初の用語tの場所を返す。
  • nextPhrase(phrase []string, current) (int, int)
    • 現在の位置(current)より後ろにある最初のフレーズ(phrase)の開始位置と終了位置を返す。
  • allPhrase(phrase []string, current) [][2]int
    • 現在の位置(current)より後ろにある全てのフレーズの開始位置と終了位置を返す。

アルゴリズムの実装の前にまずテストを書きましょう。

func TestNext(t *testing.T) {

    index := NewIndex(map[string][]int{
        "大阪": {316669, 745434},
        "営業":    {36898, 137236, 745397, 745419, 1247139},
        "エンジニア":      {1598, 27555, 745407, 745429, 745451, 745467, 1245276},
        "事務":   {265197},
    })

    type test struct {
        t        string
        current  int
        expected int
    }

    testCases := []test{
        {"エンジニア", 745429, 745451},
        {"大阪", 345678, 745434},
        {"エンジニア", 1245276, END_OF_FILE},
        {"エンジニア", BEGINNING_OF_FILE, 1598},
        {"エンジニア", END_OF_FILE, END_OF_FILE},
    }

    for _, testCase := range testCases {
        actual := index.next(testCase.t, testCase.current)
        if actual != testCase.expected {
            t.Errorf("\n got: %v\n want: %v", actual, testCase.expected)
        }
    }

}

func TestPrev(t *testing.T) {

    index := NewIndex(map[string][]int{
        "大阪": {316669, 745434},
        "営業":    {36898, 137236, 745397, 745419, 1247139},
        "エンジニア":      {1598, 27555, 745407, 745429, 745451, 745467, 1245276},
        "事務":   {265197},
    })

    type test struct {
        t        string
        current  int
        expected int
    }

    testCases := []test{
        {"エンジニア", 745451, 745429},
        {"大阪", 456789, 316669},
        {"エンジニア", 1598, BEGINNING_OF_FILE},
        {"エンジニア", END_OF_FILE, 1245276},
        {"エンジニア", BEGINNING_OF_FILE, BEGINNING_OF_FILE},
    }

    for _, testCase := range testCases {
        actual := index.prev(testCase.t, testCase.current)
        if actual != testCase.expected {
            t.Errorf("\n got: %v\n want: %v", actual, testCase.expected)
        }
    }

}

func TestNextPhrase(t *testing.T) {

    index := NewIndex(map[string][]int{
        "東京": {2205, 2268, 745406, 745466, 745501, 1271487},
        "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276},
    })

    type test struct {
        t             []string
        current       int
        expectedStart int
        expectedEnd   int
    }

    testCases := []test{
        {[]string{"東京", "エンジニア"}, BEGINNING_OF_FILE, 745406, 745407},
        {[]string{"東京", "エンジニア"}, 745500, 745501, 745502},
    }

    for _, testCase := range testCases {
        u, v := index.nextPhrase(testCase.t, testCase.current)
        if u != testCase.expectedStart || v != testCase.expectedEnd {
            t.Errorf("\n got: [%v, %v]\n want: [%v, %v]", u, v, testCase.expectedStart, testCase.expectedEnd)
        }
    }

}

func TestAllPhrase(t *testing.T) {

    index := NewIndex(map[string][]int{
        "東京": {2205, 2268, 745406, 745466, 745501, 1271487},
        "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276},
    })

    type test struct {
        t        []string
        current  int
        expected [][]int
    }

    testCases := []test{
        {[]string{"東京", "エンジニア"},
            BEGINNING_OF_FILE,
            [][]int{
                {745406, 745407},
                {745466, 745467},
                {745501, 745502},
            },
        },
    }
    for _, testCase := range testCases {
        results := index.allPhrase(testCase.t, testCase.current)
        for i, result := range results {
            if result[0] != testCase.expected[i][0] || result[1] != testCase.expected[i][1] {
                t.Errorf("\n got: %v\n want: %v", result, testCase.expected[i])
            }
        }
    }
}

実装

まず、現在位置の前後に最初に用語が出現する位置を返すnextとprevを実装します。

// next(t, current) returns the position of t's first occurrence after the current position
func (index *Index) next(t string, current int) int {

    if postingList, ok := index.Dictionary[t]; !ok {
        return END_OF_FILE
    } else {
        for _, p := range postingList {
            if p > current {
                return p
            }
        }
        return END_OF_FILE
    }
}

// prev(t, current) returns the position of t's last occurrence before the current position
func (index *Index) prev(t string, current int) int {

    if postingList, ok := index.Dictionary[t]; !ok {
        return BEGINNING_OF_FILE
    } else {
        for i := len(postingList) - 1; i >= 0; i-- {
            p := postingList[i]
            if p < current {
                return p
            }
        }
        return BEGINNING_OF_FILE
    }

}

単に引数で渡された用語のポスティングリストをたどり、条件に合致するものを返します。 見つからない場合は、ファイルの開始や終了を表す定数(BEGINNING_OF_FILE, END_OF_FILE)を返しています。 簡単のため以下のように定義しておきます。

const (
    BEGINNING_OF_FILE = -math.MaxInt32
    END_OF_FILE       = math.MaxInt32
)

それでは、実際にフレーズ検索を行う部分を実装します。

nextPhraseは現在の位置より後ろにあるフレーズを見つけ、その開始位置uと終了位置vを返す関数です。

func (index *Index) nextPhrase(phrase []string, current int) (int, int) {

    length := len(phrase)

    v := current
    for _, t := range phrase {
        v = index.next(t, v)
    }
    if v == END_OF_FILE {
        return END_OF_FILE, END_OF_FILE
    }
    u := v
    for i := length - 2; i >= 0; i-- {
        u = index.prev(phrase[i], u)
    }
    if v-u == length-1 {
        return u, v
    } else {
        return index.nextPhrase(phrase, u)
    }
}

この関数は大まかに2つの処理に分けることができます。 まず、はじめに引数で渡された用語のリスト(phrase)の順に用語が出現している箇所を探索します。

   v := current
    for _, t := range phrase {
        v = index.next(t, v)
    }
    if v == END_OF_FILE {
        return END_OF_FILE, END_OF_FILE
    }

現在の位置からフレーズに含まれる用語の順にnextを呼び出し、フレーズの最後尾の用語の位置を割り出します。 これにより、フレーズに含まれる用語(t1,t2....,tn)が文書中にこの順で出現していることが明らかになりました。 ここで、文書内にフレーズ内の用語が文書中に順番通り含まれていなければ、そのフレーズは見つからなかったとして探索を終了します。

次に、それらの用語の出現箇所が隣接しているかをチェックします。

   u := v
    for i := length - 2; i >= 0; i-- {
        u = index.prev(phrase[i], u)
    }
    if v-u == length-1 {
        return u, v
    } else {
        return index.nextPhrase(phrase, u)
    }

フレーズ最後尾の用語の位置からフレーズに含まれる用語の逆順にprevを呼び出し、フレーズの開始位置uを特定します。 uが特定できたらu,vの距離を計算し、その長さがフレーズの長さと一致していれば、検索できたのでその位置を返します。 長さが異なっていれば、現在位置を更新して再度nextPhraseを呼び出します。このようにしてフレーズが見つかるまで探索します。

すべてのフレーズを検索するには単にnextPhraseを文書集合の末尾に到達するまで開始位置uを更新しながらforでまわします。

func (index *Index) allPhrase(phrase []string, current int) [][2]int {

    var results [][2]int
    var u,v int

    u = current

    for u < END_OF_FILE {
        u, v = index.nextPhrase(phrase, u)
        if u != END_OF_FILE {
            results = append(results, [2]int{u, v})
        }
    }
    return results
}

以上が、フレーズ検索の実装になります。

まとめ

全文検索エンジンのフレーズ検索機能をGo言語で実装してみました。 今回実装したnextやprevメソッドはポスティングリストをたどるのに単にループしてしまっていますが、 キャッシュやbinary searchなどを使用して計算量を改善することができます。

参考