辞書アプリの改良：部分一致（３）
関連エントリ
StarDictの辞書アプリ - Random Note
辞書アプリの改良 - Random Note
辞書アプリの改良：初期化処理の高速化(1) - Random Note
辞書アプリの改良：初期化処理の高速化（２） - Random Note
辞書アプリの改良：コマンド化 - Random Note
辞書アプリの改良：部分一致（１） - Random Note
辞書アプリの改良：部分一致（２） - Random Note
検索アルゴリズムの概略
前提
メタインデックスの形式は下記の通り。
| 1~12バイト | 見出し語 |
| 13~16バイト | 辞書インデックスoffset |
| 17~20バイト | 辞書インデックスlength |
| 21~24バイト | 見出し語offset |
ここでは以下のような辞書インデックスの集合Aを考える。
- a：あいしだしてる
- b：あいしてるとくりかえしていう
- c：あいしてるよ、ちゅっちゅっ
- d：あいしゃどう
- e：あいしゃどうをぬる
ここで、13~20バイトを簡単のため辞書インデックスID（a, b, c･･･）で表し、21~24バイトは省略すると、メタインデックスの集合Xは下記のようになる。
| あい | a |
| あい | b |
| あい | c |
| あい | d |
| あい | e |
| いう | b |
| いし | a |
| ･･･ | ･･･ |
簡単のため、同一の見出し語を持つメタインデックスを、まとめて表す。
メタインデックスの集合Xは下記のようになる。
| あい | {a, b, c, d, e} |
| いう | {b} |
| いし | {a, b, c, d, e} |
| うを | {e} |
| えし | {b} |
| くり | {b} |
| して | {a, b, b, c} |
| しだ | {a} |
| しゃ | {d, e} |
| し、 | {a} |
| ちゅ | {c, c} |
| てい | {b} |
| てる | {a, b, c} |
| とく | {b} |
| ぬる | {e} |
| よ、 | {c} |
| りか | {b} |
| ると | {b} |
| るよ | {c} |
| をぬ | {e} |
| だし | {a} |
| どう | {d, e} |
| っち | {c} |
| ゃど | {d, e} |
| ゅっ | {c, c} |
| 、ち | {c} |
例として検索キーを「いしてる」とする。
検索キーもメタインデックスと同様にバイグラム方式で2文字の連なり（検索文字とする）の集合Yに変換する。
検索文字の集合Yは{いし, して, てる}となる。
1stステップ
メタインデックスの集合Xから、検索文字の集合Yの各要素と同じ見出し語を持つメタインデックスの辞書インデックスID集合を抜き出し、検索文字の集合Yの要素と対応するメタインデックスの辞書ID集合のペアを要素とする集合Zを作成する。
結果は下記の通り。
| いし | {a, b, c, d, e} |
| して | {a, b, b, c} |
| てる | {a, b, c} |
ここでは集合Yの全要素に対応するメタインデックスがあるが、対応するメタインデックスがない場合、辞書IDインデックス集合の部分は空集合とする。
例えば「してるわ」を検索キーとした場合は下記のようになる。
| して | {a, b, b, c} |
| てる | {a, b, c} |
| して | {a, b, b, c} |
| るわ | {} |
2ndステップ
部分一致検索では、検索対象となる辞書インデックスの文字列中の一部に検索キーが完全に一致する。
そのため、検索対象の辞書インデックスは、必ず検索文字の集合Yの全ての要素と対応するメタインデックスを持つ。
検索文字の集合Yの全ての要素と対応するメタインデックスを持つ辞書インデックスを探すためには、1stステップの結果作成された集合Zの中の辞書インデックスIDの部分に注目すればよい。
{a, b, c, d, e}
{a, b, b, c}
{a, b, c}
これらの辞書インデックスID集合について、各集合内の重複をのぞいた上でANDをとれば、検索文字の集合Yの全ての要素と対応するメタインデックスを持つ辞書インデックスIDが特定できる。
{a, b, c, d, e} AND {a, b, c} AND {a, b, c} = {a, b, c}
3rdステップ
2ndステップで、a、b、cの辞書インデックスは{いし, して, てる}をすべて含むことは分かったが、まだこれでは不十分。
aは{いし, して, てる}を全て含んでいるが、{いしてる}は含んでいない。
「いしてる」を含んでいることを保証するためには、{いし, して, てる}の位置に注目する。ここでは各要素の相対的な位置が同一であれば、「いしてる」を含むことを保証することができる。
検索キー「いしてる」をバイグラム方式で分割する際に、文字の出現位置も記録し、見出し語と位置のペアを要素とする集合Y'とすると下記のようになる。これはすでに「いし」を基準とした相対位置である。
{(いし, 0), (して, 1), (てる, 2)}
辞書インデックスa、b、cのメタインデックスのうち、1stステップの結果集合Zに含まれるものを見出し語offsetを省略せずに表すと下記のようになる。
a：あいしだしてる
| いし | a | 1 |
| して | a | 4 |
| てる | a | 5 |
b：あいしてるとくりかえしていう
| いし | b | 1 |
| して | b | 2 |
| して | b | 10 |
| てる | b | 3 |
c：あいしてるよ、ちゅっちゅっ
| いし | c | 1 |
| して | c | 2 |
| てる | c | 3 |
aを「いし」に対する相対位置を計算し、見出し語と相対位置のペアを要素とする集合にすると
「いし」の相対位置＝「いし」の位置(1)ー「いし」の位置(1)＝0
「して」の相対位置＝「して」の位置(4)ー「いし」の位置(1)＝3
「てる」の相対位置＝「てる」の位置(5)ー「いし」の位置(1)＝4
なので
- a：あいしだしてる
- {(いし, 0), (して, 3), (てる, 4)}
同様にして、
- b：あいしてるとくりかえしていう
- {(いし, 0), (して, 1), (して, 9), (てる, 2)}
- c：あいしてるよ、ちゅっちゅっ
- {(いし, 0), (して, 1), (てる, 2)}
これらの集合と検索キーから作成した集合Y'の論理積(AND)がY'と同一の集合を持つ辞書インデックスが、求める辞書インデックスとなる。
- a：あいしだしてる
- {(いし, 0), (して, 3), (てる, 4)} AND {(いし, 0), (して, 1), (てる, 2)} = {(いし, 0), (てる, 2)} != Y'
- b：あいしてるとくりかえしていう
- {(いし, 0), (して, 1), (して, 9), (てる, 2)} AND {(いし, 0), (して, 1), (てる, 2)} = {(いし, 0), (して, 1), (てる, 2)} = Y'
- c：あいしてるよ、ちゅっちゅっ
- {(いし, 0), (して, 1), (てる, 2)} AND {(いし, 0), (して, 1), (てる, 2)} = {(いし, 0), (して, 1), (てる, 2)} = Y'
したがって、「いしてる」と部分一致する辞書インデックスは
b：あいしてるとくりかえしていう
c：あいしてるよ、ちゅっちゅっ
となる。
