はじめに

この記事ではElasticsearch、というかLuceneのAnalyzerの挙動のうち、特にトークングラフという概念について紹介したいと思います。これについてきちんと理解すると、例えば検索時に表記揺れを許容するのか、あるいは厳密に一致したもののみにマッチさせるのかといったチューニングができるようになります。

トークン

Elasticsearchに限らず、検索エンジンは通常内部のデータ構造として転置インデックス(Inverted index)というものを作成します。これは基本的に書籍の最後にある索引と全く同じで、どの単語がドキュメントのどこに記載されていたのかを単語から逆引きできるようにしたデータ構造です。

ここでよく考えるとわかりますが、この転置インデックスは入力したテキストを「単語」に分割した上でないと作成できません。この全体のテキストから単語の列に分解する操作のことをトークナイズ(tokenize)、分割された個々の文字列のことをトークン(token)と言います。また分割されてできたトークンはLucene/Elasticsearchの文脈ではfilter処理をされて最終的にターム(term)というデータになってインデックスに保存されます。ただ本稿ではtokenとtermはほぼ同じ意味として扱います（厳密性に欠けるところがあるかもしれません）。

Analyzerによるテキスト解析

Elasticsearchなど検索エンジンがテキスト解析を行う場面は二つあります。一つはもちろん検索対象のドキュメントをインデックスする時です。先ほど説明したように、読み込んだテキストをトークンに分割して転置インデックスを作成します。

もう一つは検索実行時です。検索エンジンはクエリーとして与えられたテキストをトークナイズし、それぞれのトークンがテキストに含まれるドキュメントを転置インデックスを走査することによって高速に見つけ出します。

ここがポイントで、インデックスに記録されているタームと、クエリーを分析して得られたタームが一致しない場合は検索にヒットしません。そのため検索では、元のドキュメントを読み込んでインデックスを作成するときと、クエリーを分解して検索を実行するとき、どちらも同じAnalyzerを適用することがほとんどです。(ちなみに有名な例外はクエリーサジェストのためにEdge n-gram tokenizerを利用する場合です。)

Elasticsearchで日本語の検索を実装する場合、トークナイザーとしてはKuromoji tokenizerかN-gram tokenizerを利用することになることが多いでしょう。

トークングラフ

前置きが長くなりましたが、ここからが本題。テキストを解析して得られたトークン列は一見すると単なる１次元の配列に見えますが、実はトークンの位置をノード、トークンのテキストをエッジとする有向非巡回グラフです。

例えば"quick brown fox"という文字列をトークナイズして得られるトークングラフは以下のようになります。

これだけだと何の面白みもないですね。しかしここで"quick"に対して"fast"をシノニムとして適用した場合、どうなるでしょうか。

ポジション0から1へのパスとして、"quick"と"fast"の二つが存在する形になりました。グラフっぽいですね。そのほかにもDNSのシノニムとして"domain name system"を適用するケースでは以下のようになります。

このようにトークングラフを用いると、一つの文章を意味や構造を保存しながら複数の言い換えを表現できます。こうすることで、シノニムの定義されているトークンがクエリーとして入力された場合などに、それぞれの言い換えでも検索でヒットさせるようにすることができるのです。

Let's 検索

それでは具体的にElasticsearchで検索をして動作を確認していきましょう。

シノニム

最初はこれまでの説明にもあったシノニムによるトークングラフの動作を確認しましょう。以下のような定義でtokengraph_testインデックスを作成します。

PUT tokengraph_test
{
  "settings": {
    "index": {
      "analysis": {
        "analyzer": {
          "synonym_analyzer": {
            "filter": [
              "synonyms_filter"
            ],
            "tokenizer": "japanese_tokenizer"
          },
          "plain_analyzer": {
            "tokenizer": "japanese_tokenizer"
          }
        },
        "filter": {
          "synonyms_filter": {
            "type": "synonym_graph",
            "synonyms": [
              "サッカー, フットボール",
              "密林, ジャングル"
            ]
          }
        },
        "tokenizer": {
          "japanese_tokenizer": {
            "mode": "search",
            "type": "kuromoji_tokenizer"
          }
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "message": {
        "type": "text",
        "analyzer": "plain_analyzer"
      }
    }
  }
}

ここで、以下の二つのAnalyzerを定義しています。どちらも日本語のトークナイズにKuromojiを使っています。

synonym_analyzer: Synonym Graph Token Filterを適用するアナライザー（"サッカー, フットボール",　"密林, ジャングル"）
plain_analyzer: 特に何のフィルターもないアナライザーでインデックス時に利用

ではこのインデックスに以下のドキュメントを書き込んでみます。デフォルトの動作なのでplain_analyzerが使われます。

PUT tokengraph_test/_doc/1
{
  "message": "ジャングルでフットボール"
}

plain_analyzerはシノニムフィルターを入れていないので、以下の検索ではヒットしません。

GET tokengraph_test/_search
{
  "query": {
    "match": { "message": "サッカーを密林にて" }
  }
}

しかし、Analyzerはクエリー時にも指定できます。以下のsynonym_analyzerを使ったクエリーを発行してみましょう。

GET tokengraph_test/_search
{
  "query": {
    "match": {
      "message": {
        "query": "サッカーを密林にて",
        "analyzer": "synonym_analyzer"
      }
    }
  },
  "highlight": { "fields": { "message": {} } }
}

すると以下のようにヒットします。

{
  "took": 2,
  "timed_out": false,
  "_shards": {
    "total": 1,
    "successful": 1,
    "skipped": 0,
    "failed": 0
  },
  "hits": {
    "total": {
      "value": 1,
      "relation": "eq"
    },
    "max_score": 0.5753642,
    "hits": [
      {
        "_index": "tokengraph_test",
        "_id": "1",
        "_score": 0.5753642,
        "_source": {
          "message": "ジャングルでフットボール"
        },
        "highlight": {
          "message": [
            "<em>ジャングル</em>で<em>フットボール</em>"
          ]
        }
      }
    ]
  }
}

想像通りではあると思いますが、ここで何が起こっているかを詳しく見るためにAnalize APIでクエリーがどのように分解されているか確認します。

POST tokengraph_test/_analyze
{
  "text": "サッカーを密林にて",
  "analyzer": "synonym_analyzer"
}

レスポンスは以下のようになります。

{
  "tokens": [
    {
      "token": "フットボール",
      "start_offset": 0,
      "end_offset": 4,
      "type": "SYNONYM",
      "position": 0
    },
    {
      "token": "サッカー",
      "start_offset": 0,
      "end_offset": 4,
      "type": "word",
      "position": 0
    },
    {
      "token": "を",
      "start_offset": 4,
      "end_offset": 5,
      "type": "word",
      "position": 1
    },
    {
      "token": "ジャングル",
      "start_offset": 5,
      "end_offset": 7,
      "type": "SYNONYM",
      "position": 2
    },
    {
      "token": "密林",
      "start_offset": 5,
      "end_offset": 7,
      "type": "word",
      "position": 2
    },
    {
      "token": "にて",
      "start_offset": 7,
      "end_offset": 9,
      "type": "word",
      "position": 3
    }
  ]
}

はい、フットボールとサッカーがどちらもトークンとして含まれています。だから文書にあるフットボールではないサッカーでもヒットしているんですね。それがSynonymを使う意義なので当然ですが。

ここでこの記事の関心ごととして、サッカーとフットボールのどちらも同じpositionの値を取っていることに注意してください。synonym_graphフィルターを使うことで、ポジション0から1に向けて複数のパスを持つトークングラフが生成されていることがわかります。ジャングルと密林も同様です。クエリーのトークングラフを図にすると以下のようになります。

このように検索時にAnalyzerを切り替えて使うことで、クエリーに対してどの程度検索結果の揺れを許容するのかを制御できます。フットボールに対してサッカーを許容したくない場合は、（インデックス作成時ではなく）検索実行時にSynonymを使わないAnalyzerで検索をかけることを決めることができます。

Kuromoji

複数のパスを持つトークングラフを作る典型的な例はSynonymですが、実はKuromojiもそのような動きをしています。

POST tokengraph_test/_analyze
{
  "text": "関西国際空港に到着した",
  "analyzer": "plain_analyzer"
}

このAnalyzeの結果は以下のようになります。

{
  "tokens": [
    {
      "token": "関西",
      "start_offset": 0,
      "end_offset": 2,
      "type": "word",
      "position": 0
    },
    {
      "token": "関西国際空港",
      "start_offset": 0,
      "end_offset": 6,
      "type": "word",
      "position": 0,
      "positionLength": 3
    },
    {
      "token": "国際",
      "start_offset": 2,
      "end_offset": 4,
      "type": "word",
      "position": 1
    },
    {
      "token": "空港",
      "start_offset": 4,
      "end_offset": 6,
      "type": "word",
      "position": 2
    },
    {
      "token": "に",
      "start_offset": 6,
      "end_offset": 7,
      "type": "word",
      "position": 3
    },
    {
      "token": "到着",
      "start_offset": 7,
      "end_offset": 9,
      "type": "word",
      "position": 4
    },
    {
      "token": "し",
      "start_offset": 9,
      "end_offset": 10,
      "type": "word",
      "position": 5
    },
    {
      "token": "た",
      "start_offset": 10,
      "end_offset": 11,
      "type": "word",
      "position": 6
    }
  ]
}

グラフにするとこんな感じですね。

この結果を見ると、別に「関西国際空港」のトークンはなくても検索はヒットしそうです。ただこのようにトークナイズされていると「関西国際空港」で検索にヒットした時に個別の「関西」「国際」「空港」にヒットした時よりもTF-IDF（実際はBM25）のスコアが高くなると思われるので、適合率の観点で良い検索結果になることが期待できます。

Multiplexer

このように利用するToken Filterが適切なトークングラフを作成してくれる場合は良いのですが、全てのフィルターがこのような動作をするわけではありませんし、何でもかんでもファジーにマッチしていたら適合率はダダ下がりです。必要フィルターだけ組み合わせてトークングラフを作ってくれる、そんなフィルターがあったらなーと思ったあなた。あります、Multiplexer token Filter。

Multiplexerフィルターは、トークンに対して与えられたフィルター（列）を適用したタームと、適用しないそのままのタームをそれぞれ使ってトークングラフを作ってくれる、いわばメタフィルターです。

具体的な例で考えてみましょう。Kuromojiのkuromoji_readingform token filterは、漢字を含む日本語表現について読み方を出力してくれるすごいフィルターです。例えば「吾輩は猫である」をこのフィルターに通すと以下のようになります。

{
  "tokens": [
    {
      "token": "ワガハイ",
      "start_offset": 0,
      "end_offset": 2,
      "type": "word",
      "position": 0
    },
    {
      "token": "ハ",
      "start_offset": 2,
      "end_offset": 3,
      "type": "word",
      "position": 1
    },
    {
      "token": "ネコ",
      "start_offset": 3,
      "end_offset": 4,
      "type": "word",
      "position": 2
    },
    {
      "token": "デ",
      "start_offset": 4,
      "end_offset": 5,
      "type": "word",
      "position": 3
    },
    {
      "token": "アル",
      "start_offset": 5,
      "end_offset": 7,
      "type": "word",
      "position": 4
    }
  ]
}

とすると、漢字と仮名の揺らぎを吸収するような検索もできそうな気がしますね。やってみましょう。

Multiplexer token Filterを使って、漢字表現とひらがな表現を同時に含むトークングラフを作成します。まずは以下のようなインデックスを作成しましょう。

PUT tokengraph_test2
{
 "settings": {
   "index": {
     "analysis": {
       "analyzer": {
         "kana_analyzer": {
           "filter": [
             "kana_multiplexer"
           ],
           "tokenizer": "japanese_tokenizer"
         },
         "plain_analyzer": {
           "tokenizer": "japanese_tokenizer"
         }
       },
       "filter": {
         "katakana_readingform": {
           "type": "kuromoji_readingform",
           "use_romaji": false
         },
         "katakana_to_hiragana": {
           "type": "icu_transform",
           "id": "Katakana-Hiragana"
         },
         "kana_multiplexer": {
           "type": "multiplexer",
           "filters": [
             "katakana_readingform, katakana_to_hiragana"
           ]
         }
       },
       "tokenizer": {
         "japanese_tokenizer": {
           "mode": "search",
           "type": "kuromoji_tokenizer"
         }
       }
     }
   }
 },
 "mappings": {
   "properties": {
     "message": {
       "type": "text",
       "term_vector": "with_positions_offsets",
       "analyzer": "kana_analyzer"
     }
   }
 }
}

注目するべきは以下のfilterのパートです。

       "filter": {
         "katakana_readingform": {
           "type": "kuromoji_readingform",
           "use_romaji": false
         },
         "katakana_to_hiragana": {
           "type": "icu_transform",
           "id": "Katakana-Hiragana"
         },
         "kana_multiplexer": {
           "type": "multiplexer",
           "filters": [
             "katakana_readingform, katakana_to_hiragana"
           ]
         }
       },

パーツとしてのkatakana_readingformとkatakana_to_hiraganaのフィルターをkana_multiplexerがラップする形になっています。kuromoji_readingformの出力はカタカナですが、ICU transform token filterを使うとひらがなに変換することができます。

このkana_multiplexerフィルターを使って分析をかけると次のようになります。

{
  "tokens": [
    {
      "token": "吾輩",
      "start_offset": 0,
      "end_offset": 2,
      "type": "word",
      "position": 0
    },
    {
      "token": "わがはい",
      "start_offset": 0,
      "end_offset": 2,
      "type": "word",
      "position": 0
    },
    {
      "token": "は",
      "start_offset": 2,
      "end_offset": 3,
      "type": "word",
      "position": 1
    },
    {
      "token": "猫",
      "start_offset": 3,
      "end_offset": 4,
      "type": "word",
      "position": 2
    },
    {
      "token": "ねこ",
      "start_offset": 3,
      "end_offset": 4,
      "type": "word",
      "position": 2
    },
    {
      "token": "で",
      "start_offset": 4,
      "end_offset": 5,
      "type": "word",
      "position": 3
    },
    {
      "token": "ある",
      "start_offset": 5,
      "end_offset": 7,
      "type": "word",
      "position": 4
    }
  ]
}

おお、素晴らしいですね。期待通りに漢字表現に対して読み方がひらがなとしてもトークングラフに含まれています。実際検索してみましょう。まずは漢字を主に使ったドキュメントをインデックスします。

PUT tokengraph_test2/_doc/1
{
  "message": "吾輩は猫である"
}

そうしたらひらがなで検索。

GET tokengraph_test2/_search
{
  "query": {
    "match": {
      "message": {
        "query": "わがはい",
        "analyzer": "kana_analyzer"
      }
    }
  },
  "highlight": { "fields": { "message": {} } }
}

結果は次のとおり。

{
  "took": 2,
  "timed_out": false,
  "_shards": {
    "total": 1,
    "successful": 1,
    "skipped": 0,
    "failed": 0
  },
  "hits": {
    "total": {
      "value": 1,
      "relation": "eq"
    },
    "max_score": 0.32575765,
    "hits": [
      {
        "_index": "tokengraph_test3",
        "_id": "1",
        "_score": 0.32575765,
        "_source": {
          "message": "吾輩は猫である"
        },
        "highlight": {
          "message": [
            "<em>吾輩</em>は猫である"
          ]
        }
      }
    ]
  }
}

ちゃんと漢字の表現でヒットしてますね。このようにフィルターとトークングラフ構造をうまく組み合わせることで、適合率と再現性をさまざまな形でコントロールすることができるようになります。

ところでここで注意ですが、上記の例では、multiplexer filterを使って自作したkana_analyzerを、ドキュメントをインデックスする際にも使用しています。つまりインデックス上では「吾輩」「わがはい」どちらもタームとして登録されています。Term vectors APIを利用してどのようにインデックスが作成されているか確認してみましょう。

GET tokengraph_test3/_termvectors/1

レスポンスは以下のようになります。

{
  "_index": "tokengraph_test3",
  "_id": "1",
  "_version": 1,
  "found": true,
  "took": 0,
  "term_vectors": {
    "message": {
      "field_statistics": {
        "sum_doc_freq": 7,
        "doc_count": 1,
        "sum_ttf": 7
      },
      "terms": {
        "ある": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 4,
              "start_offset": 5,
              "end_offset": 7
            }
          ]
        },
        "で": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 3,
              "start_offset": 4,
              "end_offset": 5
            }
          ]
        },
        "ねこ": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 2,
              "start_offset": 3,
              "end_offset": 4
            }
          ]
        },
        "は": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 1,
              "start_offset": 2,
              "end_offset": 3
            }
          ]
        },
        "わがはい": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 0,
              "start_offset": 0,
              "end_offset": 2
            }
          ]
        },
        "吾輩": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 0,
              "start_offset": 0,
              "end_offset": 2
            }
          ]
        },
        "猫": {
          "term_freq": 1,
          "tokens": [
            {
              "position": 2,
              "start_offset": 3,
              "end_offset": 4
            }
          ]
        }
      }
    }
  }
}

確かにインデックス上も漢字がひらがなに展開されたタームも保存されていますね。したがってこの構成だとひらがなで検索しても常にヒットしてしまうため、検索時に場合によっては「吾輩」でしかヒットして欲しくない、という要求には応えられません。もしもそのようなコントロールが必須の場合は、検索の仕方ごとにAnalyzerを別にしたフィールドをもつなどの工夫が必要になってきます。この辺りは要求を理解するのも時に難しいというか、頭が混乱しがちなので、きちんと表などを作ってどんなクエリーがどんな文書にマッチするべきなのかを整理して設計を進めたいところです。

おわりに

見てきたように、トークグラフがどのように検索の際に利用されているかがわかると、「このテキスト表現でこういうドキュメントにヒットさせたい／させたくない」といったコントロールができるようになります。ぜひ使いこなしてナイスな検索システムを構築してください。