日本語でのオートコンプリート検索

これは [NAVITIME JAPAN Advent Calendar 2019][adventcalendar] 23日目の記事です。
昨日は [22日目 SonarのDeveloperEditionで出来るようになること][adventcalendar_22nd_day] でした。

## はじめに
こんにちは。
NAVITIME JAPAN の [lasta][github] です。

[NAVITIME JAPAN Advent Calendar 2019][adventcalendar] 1日目ではNAVITIME のサービスの入り口の1つである[地点検索の工夫][adventcalendar_1st_day]ついて書きました。
この記事では、通常の検索の更に前段にあるオートコンプリート検索について書きます。

## TL;DR
日本語でのオートコンプリート検索は [Apache Solr][solr] の機能だけでは不十分だったので、
データ投入の前処理で検索用文字列を生成して検索対象にするようにしました。

## Goal / Not Goal
### Goal
* オートコンプリート検索とは
* 英語でのオートコンプリート検索
* 日本語でのオートコンプリート検索

### Not Goal
* ユーザ属性を加味したサジェスト

## オートコンプリート検索とは
オートコンプリート検索と似たキーワードとして、下記のようなものがあります。

* 入力補完
* 予測変換
* オートコンプリート (検索)
* サジェスト (検索)
* インスタント検索
* もしかして検索 (Did you mean ...? 検索)
* ...

また、これらの機能は下記のいずれか、またはその組み合わせであることが多いです。

* UI
    * ユーザが入力している最中に (ほぼ) リアルタイムで検索結果を提示
    * ユーザが入力する前から検索キーワード候補を提案
    * 提案したキーワードを選択すると
        * IME の変換機能のように、検索ボックスに選択したキーワード候補が入力される
        * 選択されたドキュメントに対応する画面へ遷移する
    * ...
* 検索対象
    * ユーザの入力履歴
    * ユーザの検索履歴
    * 検索対象に含まれる単語
    * 通常の検索と同等
    * 通常の検索の一部
    * ...
* ソート
    * 全ユーザの行動ログを加味
    * ユーザ属性を加味
    * 新着
    * 急上昇キーワード
    * 距離
    * なんらかの人気度
    * ...

本記事における「オートコンプリート検索」の定義と具体例は下記の通りです。

| カテゴリ   | 要件定義                                                                       | 具体的な機能                                           |
|------------|--------------------------------------------------------------------------------|--------------------------------------------------------|
| UI         | **ユーザが入力している最中に (ほぼ) リアルタイムで検索結果を提示**             | キーワードに対応する地点等を (ほぼ) リアルタイムで表示 |
| UI         | 提案したキーワードを選択すると、選択されたドキュメントに対応するページ等へ遷移 | 検索結果に紐付いている地点IDを元に地点詳細画面へ遷移   |
| 検索対象   | 通常の検索の一部                                                               | 地点データの一部                                       |
| ランキング | なんらかの人気度                                                               | 独自集計した地点の人気度                               |
| ランキング | 距離                                                                           | ユーザの現在地からの距離                               |

![NAVITIMEの地点オートコンプリート検索](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/901153ea-c62f-d119-9046-32f32edaf682.png)

上記のうち「ユーザが入力している最中に (ほぼ) リアルタイムで検索結果を提示」について考えていきます。
[Apache Solr][solr] (以下 Solr) や [Elasticsearch][elasticsearch] に限らず多くの全文検索エンジンに応用可能ですが、 [Solr][solr] を例に解説します。

## 英語でのオートコンプリート検索
日本語はひらがな、カタカナ、漢字を用います。
一方で英語はアルファベットのみでシンプルなため、まずは英語のオートコンプリート検索について考えます。

### ユーザが入力している最中の再現
「ユーザが入力している最中」とはどのような状態でしょうか?
ユーザが "tokyo tower" という文字列を入力する場合は

1. `t` を入力
1. `o` を入力
1. `k` を入力
1. `y` を入力
1. `o` を入力
1. ` ` を入力
1. `t` を入力
1. `o` を入力
1. `w` を入力
1. `e` を入力
1. `r` を入力

となります。
当たり前といえば当たり前です。 (IME 等の予測変換は特に気にしないこととします)

このような入力している途中でも "tokyo tower" がヒットするためには、どのような文字列をインデックスするべきでしょうか?

```plaintext:tokyo␣towerの部分文字列
t
to
tok
toky
tokyo
tokyo␣
tokyo␣t
tokyo␣to
tokyo␣tow
tokyo␣towe
tokyo␣tower
```

便宜上、半角スペース ` ` を空白記号 `␣` で表現しています。

このような解析ができれば、入力中でも "tokyo tower" をヒットさせることができます。

### Solr でユーザが入力している最中を表現する
Solr では [Edge NGram Filter][solr_edge_ngram] 、 Elasticsearch では [Edge n-gram token filter][elasticsearch_edge_ngram] を用いることで、「ユーザが入力している最中」を表現できます。
入力キーワードを分割してしまわないよう気をつけてください。
キーワードと一致していないドキュメントもヒットしてしまいます。

```xml:managed-schema
<fieldType name="text_edge_ngram_en_prefix" class="solr.TextField">
  <analyzer type="index">
    <tokenizer class="solr.KeywordTokenizerFactory"/>
    <filter class="solr.EdgeNGramFilterFactory" maxGramSize="20" minGramSize="1"/>
  </analyzer>
  <analyzer type="query">
    <tokenizer class="solr.KeywordTokenizerFactory"/>
  </analyzer>
</fieldType>
```

[Schema API][schema_api] (V1 API) を利用する場合は下記のとおりです。

```json:add_text_edge_ngram_en_prefix.json
{
  "add-field-type": {
    "name": "text_edge_ngram_en_prefix",
    "class": "solr.TextField",
    "indexAnalyzer": {
      "tokenizer": {
        "class": "solr.KeywordTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.EdgeNGramFilterFactory",
          "minGramSize": 1,
          "maxGramSize": 20
        }
      ]
    },
    "queryAnalyzer": {
      "tokenizer": {
        "class": "solr.KeywordTokenizerFactory"
      }
    }
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @add_text_edge_ngram_en_prefix.json http://localhost:8983/solr/autocomplete/schema
```

![英語の前方一致オートコンプリート検索](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/b49d831f-20eb-93a4-7132-4030e676a0c9.png)

### 途中の単語から入力されることも考慮する
"toky" などで "tokyo tower" がヒットするようになりました。
これに加えて "towe" のように "tower" の入力中にもヒットさせるためにはどうしたら良いでしょうか?

Shingle Filter ([Solr Shingle Filter][solr_shingle_filter], [Elasticsearch Shingle Token Filter][elasticsearch_shingle_filter]) を利用します。
これは token 版の Edge NGram です。
"tokyo tower" を "tokyo" と "tower" の2つの token に分割した場合は、 "tokyo" 、 "tokyo tower" 、 "tower" の3つの token を生成します。
この token それぞれを元に Edge NGram を生成することで、 "toky" (前方一致)、 "tokyo tow" (前方一致かつフレーズ考慮) 、 "towe" (中間一致) の3つに対応できます。
ついでに大文字と小文字の同一視もしてしまいましょう。

```xml:managed-schema
<fieldType name="text_edge_ngram_en_partial" class="solr.TextField">
  <analyzer type="index">
    <tokenizer class="solr.StandardTokenizerFactory"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ShingleFilterFactory" minShingleSize="2" outputUnigrams="true" maxShingleSize="20" tokenSeparator=" "/>
    <filter class="solr.EdgeNGramFilterFactory" maxGramSize="20" minGramSize="1"/>
  </analyzer>
  <analyzer type="query">
    <tokenizer class="solr.KeywordTokenizerFactory"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>
```

```json:add_text_edge_ngram_en_partial.son
{
  "add-field-type": {
    "name": "text_edge_ngram_en_partial",
    "class": "solr.TextField",
    "indexAnalyzer": {
      "tokenizer": {
        "class": "solr.StandardTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.LowerCaseFilterFactory"
        },
        {
          "class": "solr.ShingleFilterFactory",
          "minShingleSize": 2,
          "maxShingleSize": 20,
          "outputUnigrams": "true",
          "tokenSeparator": " "
        },
        {
          "class": "solr.EdgeNGramFilterFactory",
          "minGramSize": 1,
          "maxGramSize": 20
        }
      ]
    },
    "queryAnalyzer": {
      "tokenizer": {
        "class": "solr.KeywordTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.LowerCaseFilterFactory"
        }
      ]
    }
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @add_text_edge_ngram_en_partial.json http://localhost:8983/solr/autocomplete/schema
```

![英語の中間一致オートコンプリート検索](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/6207a061-92f2-5bc5-3179-9fde5be72583.png)


## 日本語でのオートコンプリート
英語でのオートコンプリートの設計をもとに、日本語のオートコンプリートを設計していきます。
`text_edge_ngram_en_partial` をもとに日本語用の解析器を考えます。

まずは単語の区切り方をの違いを考慮しましょう。
英語は空白区切り、日本語は形態素ごとになります。
そのため、 `text_edge_ngram_en_partial` をコピーして `text_edge_ngram_ja_partial` を作成し、下記のとおり Tokenizer 自体と Shingle Filter の設定を差し替えましよう。

|                             | 英語                                                | 日本語                                                |
|-----------------------------|-----------------------------------------------------|-------------------------------------------------------|
| 単語の区切り方              | 空白                                                | 形態素                                                |
| Tokenizer (Solr)            | [`KeywordTokenizerFactory`][solr_keyword_tokenizer] | [`JapaneseTokenizerFactory`][solr_japanese_tokenizer] |
| Shingle Filter でのデリミタ | 空白                                                | 空文字                                                |

```xml:managed-schema
<fieldType name="text_edge_ngram_ja_partial" class="solr.TextField">
  <analyzer type="index">
    <tokenizer class="solr.JapaneseTokenizerFactory"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ShingleFilterFactory" minShingleSize="2" outputUnigrams="true" maxShingleSize="20" tokenSeparator=""/>
    <filter class="solr.EdgeNGramFilterFactory" maxGramSize="20" minGramSize="1"/>
  </analyzer>
  <analyzer type="query">
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>
```

```json:text_edge_ngram_ja_partial.json
{
  "add-field-type": {
    "name": "text_edge_ngram_ja_partial",
    "class": "solr.TextField",
    "indexAnalyzer": {
      "tokenizer": {
        "class": "solr.JapaneseTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.LowerCaseFilterFactory"
        },
        {
          "class": "solr.ShingleFilterFactory",
          "minShingleSize": 2,
          "maxShingleSize": 20,
          "outputUnigrams": "true",
          "tokenSeparator": ""
        },
        {
          "class": "solr.EdgeNGramFilterFactory",
          "minGramSize": 1,
          "maxGramSize": 20
        }
      ]
    },
    "queryAnalyzer": {
      "tokenizer": {
        "class": "solr.WhitespaceTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.LowerCaseFilterFactory"
        }
      ]
    }
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @text_edge_ngram_ja_partial.json http://localhost:8983/solr/autocomplete/schema
```

この解析器の動作を見ていきましょう。
「東京」というキーワードで検索した場合、「東京タワー」はヒットします。

![日本語の中間一致オートコンプリート検索1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/b694aacf-5052-0b26-3c80-5a1b083e6325.png)


図では 2 つの token にヒットしています。
何個の token にヒットしたかどうかは本質ではないため、文書内の単語の出現数は考慮しない (ノルム値を考慮しない; `omitNorms=true`) ようにします。

これで、非常に素朴な日本語でのオートコンプリート検索を実現できました。

### 日本語を入力している最中とは
コンピュータで日本語を入力する際は、必ず何らかの IME を利用します。
文字を入力し、 IME が変換候補を提示し、変換先を選択して確定します。

また入力方式も複数あり、主に「ローマ字入力」と「かな入力」、「フリック入力」 の3つが挙げられます。
かな入力とフリック入力はほぼ同等 (拗音と促音の扱い以外同じ) なため、この2つはまとめて1つのものとして考えることにします。
「東京タワー」という文字列を例に、それぞれの入力途中の文字列を並べると、下記のようになります。

* ローマ字入力
  1. t
  1. と
  1. とう
  1. とうk
  1. とうky
  1. とうきょ
  1. とうきょう
  1. とうきょうt
  1. とうきょうた
  1. とうきょうたw
  1. とうきょうたわ
  1. とうきょうたわー
  1. (変換)
  1.  東京タワー
* かな入力 / フリック入力
  1. と
  1. とう
  1. とうき
  1. とうきよ
        * フリック入力のみ
  1. とうきょ
        * フリック入力 : 小文字変換
        * かな入力 : Shift + 「よ」
  1. とうきょう
  1. とうきょうた
  1. とうきょうたわ
  1. とうきょうたわー
  1. (変換)
  1.  東京タワー

以上から、日本語を入力している最中を考慮するためには、入力手法 (ローマ字入力, かな入力 / フリック入力) と変換の考慮が必要になります。

### ローマ字入力での入力途中を考慮する
まずはローマ字入力を考慮します。
下記の手順で入力途中の考慮を行います。

* インデックス作成
  1. 検索対象文字列を形態素解析
  1. 形態素から読みを取り出しローマ字に変換
  1. 形態素解析できなかった文字列をできるだけローマ字に変換
  1. ASCII 文字に正規化
* 検索
  1. 検索文字列をローマ字に変換
  1. ASCII 文字に正規化

それぞれ見ていきます。

#### 検索文字列を形態素解析, 形態素から読みを取り出しローマ字に変換
Solr および Elasticsearch のコアである Lucene は [`JapaneseReadingFormFilterFactory`][lucene_japanese_reading_form_filter] を持ちます。
これを用いるためには、予め `JapaneseTokenizerFactory` で形態素解析を行い、読み (reading) を取り出せる状態にする必要があります。

検索文字列は入力途中のため日本語として成立しない場合があります。
そのため、検索文字列の形態素解析は行いません。

#### 形態素解析できなかった文字列をできるだけローマ字に変換
日本語の形態素解析器を用いる都合上、未知語の読みを取り出すことはできません。
未知語を可能な限り拾うため、 [`ICUTransformFilterFactory`][lucene_icu4j_transform_filter] を用いて、残っているひらがな及びカタカナもラテン文字へ転記 (ローマ字化) します。

#### ASCII 文字に正規化
また `JapaneseReadingFormFilterFactory` の仕様で、長音はマクロン付き母音 (タワー : tawā) に変換されます。
このマクロンを外すために、 [`ASCIIFoldingFilterFactory`][lucene_ascii_folding_filter] を用いて ASCII 文字へ正規化します。

#### 動作確認
以上をまとめると、下記のような型定義になります。

```xml:managed-schema
<fieldType name="text_edge_ngram_ja_roman" class="solr.TextField">
  <analyzer type="index">
    <tokenizer class="solr.JapaneseTokenizerFactory"/>
    <filter class="solr.JapaneseReadingFormFilterFactory" useRomaji="true"/>
    <filter class="solr.ICUTransformFilterFactory" id="Hiragana-Katakana"/>
    <filter class="solr.ICUTransformFilterFactory" id="Katakana-Latin"/>
    <filter class="solr.ASCIIFoldingFilterFactory" preserveOriginal="false"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ShingleFilterFactory" minShingleSize="2" outputUnigrams="true" maxShingleSize="20" tokenSeparator=""/>
    <filter class="solr.EdgeNGramFilterFactory" maxGramSize="20" minGramSize="1"/>
  </analyzer>
  <analyzer type="query">
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>
    <filter class="solr.JapaneseReadingFormFilterFactory" useRomaji="true"/>
    <filter class="solr.ICUTransformFilterFactory" id="Hiragana-Katakana"/>
    <filter class="solr.ICUTransformFilterFactory" id="Katakana-Latin"/>
    <filter class="solr.ASCIIFoldingFilterFactory" preserveOriginal="false"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>
```

```json:text_edge_ngram_ja_roman.json
{
  "add-field-type": {
    "name": "text_edge_ngram_ja_roman",
    "class": "solr.TextField",
    "indexAnalyzer": {
      "tokenizer": {
        "class": "solr.JapaneseTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.JapaneseReadingFormFilterFactory",
          "useRomaji": "true"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Hiragana-Katakana"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Katakana-Latin"
        },
        {
          "class": "solr.ASCIIFoldingFilterFactory",
          "preserveOriginal": "false"
        },
        {
          "class": "solr.LowerCaseFilterFactory"
        },
        {
          "class": "solr.ShingleFilterFactory",
          "minShingleSize": 2,
          "maxShingleSize": 20,
          "outputUnigrams": "true",
          "tokenSeparator": ""
        },
        {
          "class": "solr.EdgeNGramFilterFactory",
          "minGramSize": 1,
          "maxGramSize": 20
        }
      ]
    },
    "queryAnalyzer": {
      "tokenizer": {
        "class": "solr.WhitespaceTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.JapaneseReadingFormFilterFactory",
          "useRomaji": "true"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Hiragana-Katakana"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Katakana-Latin"
        },
        {
          "class": "solr.ASCIIFoldingFilterFactory",
          "preserveOriginal": "false"
        },
        {
          "class": "solr.LowerCaseFilterFactory"
        }
      ]
    }
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @text_edge_ngram_ja_roman.json http://localhost:8983/solr/autocomplete/schema
```

ICU4J を用いたフィルターを使用するため、 `solrconfig.xml` にて `libexec/contrib/analysis-extras/lucene-libs` と `libexec/contrib/analysis-extras/lib` にパスを通す必要があります。
ライブラリの絶対パスは Solr のバージョンやインストール方法によって異なるため、適宜読み替えてください。

```xml:solrconfig.xml
<lib dir="${path.to.libexec.dir}/libexec/contrib/analysis-extras/lib" regex=".*\.jar" />
<lib dir="${path.to.libexec.dir}/libexec/contrib/analysis-extras/lucene-libs" regex=".*\.jar" />
```

![「と」で「東京タワー」がヒット](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/3fcd3a27-5a2b-305b-73e6-c1af5a7a370c.png)


上図のように、「と」で「東京タワー」がヒットします。

#### ローマ字入力における課題
では、「とうk」ではどうでしょうか?

![「とうk」で「東京タワー」がヒットしない](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/63e06530-6979-7eef-dd16-7371054cb820.png)


ヒットしませんでした。

ヒットしない理由は下記の2つです。

* `JapaneseReadingFormFilterFactory` で読みを取り出す際に、長音はマクロン付き母音に変換される
* `ASCIIFoldingFilterFactory` で正規する際に、単純にマクロンを取り外している

この2つの課題を解決する必要があります。

### かな入力 / フリック入力での入力途中を考慮する
ローマ字入力のときとほぼ同等です。

* インデックス作成
  1. 検索対象文字列を形態素解析
  1. 形態素から読みを取り出し **カタカナ** に変換
  1. 形態素解析できなかった文字列をできるだけカタカナに変換
* 検索
  1. 検索文字列を **カタカナ** に変換

`JapaneseReadingFormFilterFactory` のオプションに `useRomaji` があります。
こちらを `true` にするとローマ字に変換されますが、これを `false` にすることでカタカナに変換されます。

この設定および ASCII 文字への正規化を削除したこと以外はローマ字入力と同じです。

```xml:managed-schema
<fieldType name="text_edge_ngram_ja_kana" class="solr.TextField">
  <analyzer type="index">
    <tokenizer class="solr.JapaneseTokenizerFactory"/>
    <filter class="solr.JapaneseReadingFormFilterFactory" useRomaji="false"/>
    <filter class="solr.ICUTransformFilterFactory" id="Hiragana-Katakana"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.ShingleFilterFactory" minShingleSize="2" outputUnigrams="true" maxShingleSize="20" tokenSeparator=""/>
    <filter class="solr.EdgeNGramFilterFactory" maxGramSize="20" minGramSize="1"/>
  </analyzer>
  <analyzer type="query">
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>
    <filter class="solr.JapaneseReadingFormFilterFactory" useRomaji="false"/>
    <filter class="solr.ICUTransformFilterFactory" id="Hiragana-Katakana"/>
    <filter class="solr.ASCIIFoldingFilterFactory" preserveOriginal="false"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>
```

```json:text_edge_ngram_ja_kana.json
{
  "add-field-type": {
    "name": "text_edge_ngram_ja_kana",
    "class": "solr.TextField",
    "indexAnalyzer": {
      "tokenizer": {
        "class": "solr.JapaneseTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.JapaneseReadingFormFilterFactory",
          "useRomaji": "false"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Hiragana-Katakana"
        },
        {
          "class": "solr.LowerCaseFilterFactory"
        },
        {
          "class": "solr.ShingleFilterFactory",
          "minShingleSize": 2,
          "maxShingleSize": 20,
          "outputUnigrams": "true",
          "tokenSeparator": ""
        },
        {
          "class": "solr.EdgeNGramFilterFactory",
          "minGramSize": 1,
          "maxGramSize": 20
        }
      ]
    },
    "queryAnalyzer": {
      "tokenizer": {
        "class": "solr.WhitespaceTokenizerFactory"
      },
      "filters": [
        {
          "class": "solr.JapaneseReadingFormFilterFactory",
          "useRomaji": "false"
        },
        {
          "class": "solr.ICUTransformFilterFactory",
          "id": "Hiragana-Katakana"
        },
        {
          "class": "solr.ASCIIFoldingFilterFactory",
          "preserveOriginal": "false"
        },
        {
          "class": "solr.LowerCaseFilterFactory"
        }
      ]
    }
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @text_edge_ngram_ja_kana.json http://localhost:8983/solr/autocomplete/schema
```

![「とうきょ」で「東京タワー」がヒット](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/8a94c06b-1d63-20a4-6bc5-9f6ae01a95e5.png)


入力中文字列「とうきょ」で「東京タワー」がヒットしました。
ローマ字入力のものと比べると良さそうに見えますね。

かな入力かつ「東京タワー」という検索対象であれば、この方法でも問題ありません。
ですが、この方法にも2つの課題があります。

#### 濁音 / 半濁音の考慮
かな入力では、PC用キーボードでもフリック入力でも **濁音 / 半濁音はあとから入力** します。
例えば、「ドーム」は下記の順に入力されます。

1. と
1. ど
    * かな入力 : 「゛」キー
    * フリック入力 : 「゛゜小」キー
1. どー
1. どーむ
1. (変換)

すなわち、濁音 / 半濁音を入力する前に清音 (濁音、半濁音、拗音 (小さい「ぁ」など)、促音(「っ」) でもない音) を入力されることを考慮する必要があります。

![「とうきょうと」で「東京ドーム」がヒットしない](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315364/a9b46bad-7faf-6ccb-b0c6-70d8875b4c04.png)


#### フリック入力の考慮
かな入力において清音が入力されることを考慮する必要がある場合は濁音 / 半濁音の場合のみでしたが、
フリック入力の場合は拗音および促音の場合も考慮が必要です。
例えば、「東京」は下記の順に入力されます。

1. と
1. とう
1. とうき
1. とうきよ
1. とうきょ (「゛゜小」キー で拗音化)
1. とうきょう
1. (変換)

#### かな入力における課題
これまでをまとめると、かな入力における課題は以下の2つです。

* 濁音 / 半濁音が入力される前に、清音が入力されることを考慮する必要がある (「た」 + 「゛」 → 「だ」)
* (フリック入力のみ) 拗音 / 促音が入力される前に、直音 (小文字ではない文字) が入力されることを考慮する必要がある (「よ」 + 「゛゜小」キー → 「ょ」)

### 変換済の文字を考慮する
日本語の入力において欠かせない要素が「変換」です。
iOS 標準の IME や Google 日本語入力をはじめ、昨今の IME は賢いため長文を変換しても高速かつおおよそ期待通りに変換してくれます。

変換を行うタイミングは、下記のとおりです。

* すべてを入力した後
    * 「とうきょうたわー」 → 変換 → 「東京タワー」
* 少なくとも1単語入力した後
    * 「とうきょう」 → 変換 → 「東京」 → 「東京 *たわー* 」(「東京」は確定済) → 「東京タワー」
* 1文字分の読みを入力した後
    * 「ひがし」 → 変換 → 「東」 → 「東 *きょう* 」 → 変換 → ...

1つ目の「すべてを入力した後」はこれまでの解析方法で考慮できています。
3つ目の「1文字分の読みを入力した後」は読み方がわからない漢字等を入力する際に行われ、かつ考慮が難しいため割愛します。

変換という操作を求められる言語である以上、2つ目の考慮は欠かせません。

つまり、前述した「東京タワー」の入力文字列に加え、下記も考慮する必要があります。

* 「東京」を変換した後に「タワー」を入力
  1. 東京t
  1. 東京た
  1. 東京たw
  1. 東京たわ
  1. 東京たわー
  1. (変換)
  1. 東京タワー

### これまでの課題
* ローマ字入力
    * 「きょう」が「kyo」になる
        * 長母音がうまく扱えない
            * `JapaneseReadingFormFilterFactory` で読みを取り出す際に、長音はマクロン付き母音に変換される (「とうきょう」 → 「tōkyō」)
            * `ASCIIFoldingFilterFactory` で正規する際に、単純にマクロンを取り外している (「tōkyō」 → 「tokyo」)
* かな入力 / フリック入力
    * 濁音 / 半濁音が入力される前に、清音が入力される
    * (フリック入力のみ) 拗音 / 促音が入力される前に、直音が入力されることを考慮する必要がある (「よ」 + 「゛゜小」キー → 「ょ」)
* 共通の課題
    * 変換済の文字列の後にさらに入力されることがある (「東京たw」)

### 課題への対処
課題を Solr の機能で解決することが難しかったため、入力途中の文字列を予め作成してインデックス作成することにしました。
予め入力途中の文字列を生成するため、型は String (`solr.StrField`) になります。
そのため、フィールド定義は下記になります。

```xml:managed-schema
<field name="autocomplete_ja" type="string" omitNorms="true" multiValued="true" indexed="true" stored="false"/>
```

```json:autocomplete_ja.json
{
  "add-field": {
    "name": "autocomplete_ja",
    "type": "string",
    "indexed": true,
    "stored": false,
    "multiValued": true,
    "omitNorms": true
  }
}
```

```console:schema_api
$ curl -X POST -H 'Content-type:application/json' --data-binary @autocomplete_ja.json http://localhost:8983/solr/autocomplete/schema
```

このフィールドに対し、各課題を解消したデータを投入します。

#### ローマ字入力で長母音をうまく扱えない
長母音をうまく扱えない最大の原因は `solr.JapaneseReadingFormFilterFactory` がローマ字に変換する際にマクロン付きの母音 (ō など) を生成するためです。
([ソースコード](https://github.com/apache/lucene-solr/blob/master/lucene/analysis/kuromoji/src/java/org/apache/lucene/analysis/ja/util/ToStringUtil.java#L257))

[ICU4J][icu4j] の [`Transliterator`][icu4j_transliterator] を用いると、長音の場合を除きあまりマクロン付き母音を返却しないようです。

```kotlin
import com.ibm.icu.text.Transliterator

val katakanaToRoman: Transliterator = Transliterator.getInstance("Katakana-Latin")
katakanaToRoman.transliterate("トウキョウ") // toukyou
katakanaToRoman.transliterate("スキー") // skī
```

長音の場合のみマクロン付き母音を返却するのであれば、マクロン付き母音を「母音 + 長音」に変換することで解決します。
これは簡単な置換で対応できます。

```kotlin
val MACRON_DELETION_MAP = mapOf(
    "ā" to "a-", "ē" to "e-", "ī" to "i-", "ō" to "o-", "ū" to "u-",
    "Ā" to "A-", "Ē" to "E-", "Ī" to "I-", "Ō" to "O-", "Ū" to "U-"
)
katakanaToRoman.transliterate("スキー")
    .splitToSequence("")
    .map { letter -> MACRON_DELETION_MAP[letter] ?: letter }
    .joinToString("") // suki-
```

#### かな入力 / フリック入力にて、濁音(゛) / 半濁音(゜) / 拗音(ぁ) / 促音(っ) の前に清音 / 直音が入力される
濁音などに変換されうる清音 / 直音が入力されるのは、必ず検索キーワードの最後です。
そのため、生成した入力途中文字列のうち濁音等で終わる場合は、清音に置き換えたものも追加することで解決します。

変換用マップはマクロンのときと同様に作成しました。

#### 変換済の文字列の後にさらに入力されることがある (「東京たw」)
形態素のリストと、形態素ごとの入力途中文字列のリストを1つずらして結合することで生成できます。

* 形態素
    1. 東京
    1. タワー
* 形態素ごとの入力途中文字列
    1. 東京
        * t
        * と
        * とう
        * とうk
        * とうky
        * とうきょ
        * とうきょう
        * とうき
        * とうきよ
        * とうきょう
    1. タワー
        * t
        * た
        * たw
        * たわ
        * たわー

* 「東京」と「「タワー」の入力途中文字列」を結合したもの
      * 東京t
      * 東京た
      * 東京たw
      * 東京たわ
      * 東京たわー

```kotlin:実装例
// 形態素の表層文字
val surfaces = listOf("東京", "タワー")
// 入力途中文字列
val readingEdges = listOf(
    listOf(/* 「東京」の入力途中文字列 */),
    listOf(/* 「タワー」の入力途中文字列 */)
)

// shingle : ShingleFilterFactory と同等の操作
// 東京,タワー --> 東京, 東京タワー --> "", 東京, 東京タワー
val shingledSurfaces = listOf("") + shingle(surfaces)

// 変換済文字列と後続の入力途中文字列を結合する
shingledSurfaces.zip(readingEdges)
    .map { (surface, edges) -> edges.map { edge -> surface + edge } }
    .flatten()
```

## まとめ
日本語でのオートコンプリート検索について、簡易的な方法と発生し得る課題、そしてその課題への対処について解説しました。
データ更新を行うコンバータが計算量を要求するようになるためリアルタイム性を求められるシステムには向かないですが、Solr の機能だけで実装した場合と比べてより高い検索 UX を提供できます。

明日は NAVITIME JAPAN Advent Calendar 2019 24日目 検索エンジンサーバをオートスケールできるようにした話 です。

[adventcalendar]: https://qiita.com/advent-calendar/2019/navitime_japan
[adventcalendar_1st_day]: https://qiita.com/navitime_tech/items/1b392167a7454d4b15a0
[adventcalendar_22nd_day]: https://qiita.com/navitime_tech/items/401bae42ccfc63d515e0
[github]: https://github.com/lasta
[solr]: https://lucene.apache.org/solr/
[elasticsearch]: https://www.elastic.co/jp/what-is/elasticsearch
[google_autocomplete_article]: http://www.index-chronicle.com/chronicle/google/search-engine-box/
[schema_api]: https://lucene.apache.org/solr/guide/8_3/schema-api.html
[solr_edge_ngram]: https://lucene.apache.org/solr/guide/8_3/filter-descriptions.html#edge-n-gram-filter
[elasticsearch_edge_ngram]: https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-edgengram-tokenfilter.html
[solr_shingle_filter]: https://lucene.apache.org/solr/guide/8_3/filter-descriptions.html#shingle-filter
[elasticsearch_shingle_filter]: https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-shingle-tokenfilter.html
[solr_keyword_tokenizer]: https://lucene.apache.org/solr/guide/6_6/tokenizers.html#Tokenizers-KeywordTokenizer
[solr_japanese_tokenizer]: https://lucene.apache.org/solr/guide/6_6/language-analysis.html#LanguageAnalysis-Japanese
[lucene_japanese_reading_form_filter]: https://lucene.apache.org/core/8_3_0/analyzers-kuromoji/org/apache/lucene/analysis/ja/JapaneseReadingFormFilterFactory.html
[lucene_icu4j_transform_filter]: https://lucene.apache.org/core/8_3_1/analyzers-icu/org/apache/lucene/analysis/icu/ICUTransformFilterFactory.html
[lucene_ascii_folding_filter]: https://lucene.apache.org/core/8_3_0/analyzers-common/org/apache/lucene/analysis/miscellaneous/ASCIIFoldingFilter.html
[http://site.icu-project.org/homelucene_ascii_folding_filter]: https://lucene.apache.org/core/8_3_0//analyzers-common/org/apache/lucene/analysis/miscellaneous/ASCIIFoldingFilterFactory.html
[icu4j]: http://site.icu-project.org/home
[icu4j_transliterator]: https://unicode-org.github.io/icu-docs/apidoc/released/icu4j/com/ibm/icu/text/Transliterator.html