辞書アプリの改良:高速化(3)
対策2:余計な検索片は使わない
次の高速化のターゲットはこれ。
あいしてるとくりかえしていう
meta search(日英) | 272 |
meta search(日タイ) | 3632 |
これまでの検索では、検索キーを1文字ずつ横にずらしながら2文字に切り取っていた。
「あいしてるとくりかえしていう」であれば「あい、いし、して、てる、ると、とく、くり、りか、かえ、えし、して、てい、いう」。
頭の3片(「あい」「いし」「して」)に注目。
実は「あい」の2文字後ろに「して」があれば、必ず「いし」が「あい」の1文字後ろにできる。
つまり「いし」は検索する必要のない余計な検索片である。
余計な検索片を作らないようにするには1文字ずつずらしているところを2文字ずつずらすようにすればいい。
ちょっと気をつけなくてはいけないのは、語末の部分。検索キーの文字数が奇数の場合は最後に1文字あまってしまう。
普通のN-gramだと、インデックスの方も文末の最後の部分は1文字の見出し語になるようにしているが、今回の辞書アプリでは文末も2文字切り出せるところまでしかメタインデックス化をしていない。
これは1文字のメタインデックスが1文字の辞書インデックスを表すようにすることを意図している(実はここもまだバグがある)。
そこで、今回は検索キーの文字数が奇数だった場合は最後から2文字も検索片として使うことにする。
ソース
今回は変更部分だけ。
Dictionary.groovy
def cut(string) { if (string.length() < MetaIndex.KEY_CHAR_LENGTH) return [new MetaIndex(string, 0, 0, 0)] def list = [] int i=0 while (i <string.length()-MetaIndex.KEY_CHAR_LENGTH +1) { list << new MetaIndex(string.substring(i, i+MetaIndex.KEY_CHAR_LENGTH), 0, 0, i) i += 2 } if (string.length() % 2 != 0) list << new MetaIndex( string.substring(string.length()-MetaIndex.KEY_CHAR_LENGTH, string.length()), 0, 0, string.length()-MetaIndex.KEY_CHAR_LENGTH) return list }
結果
ああああああああああ
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 278 | 287 | 490 |
weak intersection(日英) | 72 | 113 | 108 |
filter(日英) | 88 | 81 | 106 |
meta search(日タイ) | 170 | 213 | 577 |
weak intersection(日タイ) | 11 | 12 | 91 |
filter(日タイ) | 47 | 46 | 290 |
All | 841 | 891 | 2185 |
い
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 216 | 217 | 301 |
weak intersection(日英) | 27 | 28 | 52 |
filter(日英) | 88 | 90 | 104 |
meta search(日タイ) | 62 | 63 | 93 |
weak intersection(日タイ) | 1 | 1 | 0 |
filter(日タイ) | 4 | 4 | 24 |
All | 636 | 697 | 882 |
おた
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 221 | 214 | 86 |
weak intersection(日英) | 29 | 28 | 51 |
filter(日英) | 92 | 83 | 13 |
meta search(日タイ) | 55 | 57 | 101 |
weak intersection(日タイ) | 3 | 2 | 0 |
filter(日タイ) | 8 | 10 | 121 |
All | 677 | 661 | 871 |
あいし
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 260 | 273 | 351 |
weak intersection(日英) | 69 | 73 | 143 |
filter(日英) | 89 | 93 | 78 |
meta search(日タイ) | 663 | 658 | 761 |
weak intersection(日タイ) | 36 | 35 | 25 |
filter(日タイ) | 116 | 104 | 73 |
All | 1536 | 1730 | 2079 |
あいして
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 324 | 271 | 444 |
weak intersection(日英) | 74 | 72 | 104 |
filter(日英) | 92 | 96 | 52 |
meta search(日タイ) | 805 | 1404 | 1213 |
weak intersection(日タイ) | 42 | 105 | 159 |
filter(日タイ) | 98 | 155 | 112 |
All | 1731 | 2392 | 2373 |
あいしてるとくりかえしていう
ロジック | 今回 | 対策1 | 最初 |
meta search(日英) | 320 | 272 | 855 |
weak intersection(日英) | 78 | 72 | 117 |
filter(日英) | 89 | 91 | 51 |
meta search(日タイ) | 1918 | 3632 | 3620 |
weak intersection(日タイ) | 185 | 214 | 247 |
filter(日タイ) | 162 | 171 | 76 |
All | 3024 | 4731 | 5119 |