こんにちは!
Tech KAYAC Advent Calendar 2020 4日目を担当する荒賀(@ken39arg) です。
近況報告
毎年このアドベントカレンダーの場をかりて、趣味の長距離スポーツの結果を報告して承認欲求を満たしていたのですが、 昨年サブスリーを達成して今年はサブエガ1を目指していたフルマラソンの大会は中止となり、夏の趣味であるOWS2の大会も軒並み中止となってしまいました。 その代わりに今年は2018年に買って未クリアだったゼルダをプレイし、ハイラルの平和をなんとか今年中に取り戻せるように努力をしております。
Trie木が必要になった経緯
さて、アドベントカレンダーだからツリー → ツリーといえば我々の世界では木構造 → 木構造といえばトライ木ということではなく、 今年した仕事でTrie木を実装する機会があったので、その時の気づきを書いてみようかと思います。
今年ユーザーが 自由にテキストを投稿 できるとあるサービスを 某外国向け にGolangで作っていたのですが、 そこで投稿禁止ワードリストを用いて投稿内容をフィルタリングしたいという要求がありました。
この要件の特徴は下記です。
- 日本語でも英語でもないutf8で表現された言語3
- 日本語と異なりスペースで区切られておりわかち書きは必要ない
- ユーザー名等の一部は投稿を受け付けず、入力エラーとする
- それ以外のテキストは投稿は受け付け、表示の際に
*****等の伏字で置き換える - 禁止ワードリストにはスペースを含む フレーズが含まれる
この要件からmecabは使えず、全リクエストのレスポンスにフィルタを入れるために特殊なミドルウェアやSaaSなどは入れづらく、 fuzzy searchを読めない言語で取り入れる勇気はなく、リストに対して原則完全一致とすることになりました。
まず最初に検討した実装方法は正規表現を用いた方法で、perlのRegexp::Trieを利用して正規表現を作成し、
regexpパッケージでMatchあるいは ReplaceAll するという方法でした。
しかし、この方法だと、入力エラーにする分には問題ないが、レスポンス時にすべてのテキストに置換処理を入れる場合にはパフォーマンスに懸念がありました。
次に、goの正規表現が遅いときのセオリーに沿ってstrings パッケージのContains(Index)やReplacer などを検討しました。
この方法だと正規表現よりもパフォーマンスが良いのですが、元のテキストを壊さずにフレーズを含む置換に対応することがとても困難4で上手く実装する方法を思いつくことができませんでした。
このような経緯で、一旦時間を決めてTrie木
の実装をして、
正規表現以上の制度でstringsのパフォーマンスに近づくことに挑戦してみることにしました。5
テスト及び計測コード
Trie木を実装するにあたって、まずはテストコードとベンチマークコードを作成しました。
テストはワードリストとして、第一世代のポケモンの日本語、英語、ドイツ語を用いました。6 ベンチマーク用のテキストは、現在のポケモンアニメのエンディング曲であるポケモンしりとりの歌詞を扱い、ポケモンしりとりに出てくるポケモン第一世代を伏字にすることで測定しました。
【公式】「ポケモンしりとり（フルサイズVer.）」 アニメ「ポケットモンスター」エンディングテーマ
以下、出てくるベンチマーク結果のテストコードは下記になります。
なお、歌詞については上記コードに含んでいません。
素直な実装
まずは、フレーズのことは忘れて、ワードマッチと置換をするためにWikipediaの擬似コードを参考に単純な実装をしました。
nodeは下記のように定義し、各ワードをrune(Unicodeコードポイント)で分割しました。
type node struct {
children map[rune]*node
value string
}
例えば cat という文字は下記のような構造で表現されます。
root.children["c"].children["a"].children["t"].value = "cat"
実装したコード
ベンチマーク結果
goos: linux goarch: amd64 BenchmarkReplace_30/regexp-2 2618 385521 ns/op 5392 B/op 3 allocs/op BenchmarkReplace_30/Replacer-2 57013 20246 ns/op 5408 B/op 3 allocs/op BenchmarkReplace_30/Trie-2 23221 58154 ns/op 9600 B/op 3 allocs/op BenchmarkReplace_Many/regexp-2 481 2238582 ns/op 10081 B/op 10 allocs/op BenchmarkReplace_Many/Replacer-2 42528 31628 ns/op 5031 B/op 3 allocs/op BenchmarkReplace_Many/Trie-2 14562 72307 ns/op 16000 B/op 4 allocs/op
正規表現が飛び抜けて遅く、自前のTrieよりstrings.Replacerのほうが3倍くらい早いという結果になりました。
これを最適化しstrings.Replacerと同じ速度が出るようにしていきたいと思います。
strings.Replacer はなぜ早いのか
strings.Replacer と同じ速度を出したいということなので、手っ取り早くコードを読んで実装を取り入れたいと思います。
とはいえ、strings.Replacer も実装はTrieです。7
では、なぜこんなにもパフォーマンスに差が出たのかコードを見てみると大きな違いは下記であることがわかりました。
- パトリシア木(基数木)を用いてメモリ使用量を最適化している
- 文字列をruneで分割せずにbyte単位で分割している
- 子ノードをmapで持たず、sliceに対してindexアクセスしている
結論から言うと、2,3が強力で、1のパトリシア木に関しては今回の用途ではパフォーマンスを出せませんでした。8
この2,3はセットになっていて、runeにすると種類はとても多くなるがbyteにすると1byte分しかないため、 1nodeの子要素は多くても1byte分つまり256通りで済むようになります。
このためsliceのサイズも抑えることができます。また、常に256サイズを確保しないために [256]byte というarrayで各byteについて使用している場合のindexを表す辞書を作成しメモリを削減しています。
ベンチマーク
「map」「sort済みsliceをforで回す」「sliceのindexアクセス」の3つの方法で最大の要素数が255の場合のパフォーマンスを測定した結果が下記で、 mapよりも70%くらいsliceにindexアクセスしたほうが早いということがわかりました。
goos: linux goarch: amd64 BenchmarkMap/map-30_255-2 26184562 44.9 ns/op 0 B/op 0 allocs/op BenchmarkMap/slice-30_255-2 16338622 67.8 ns/op 0 B/op 0 allocs/op BenchmarkMap/sliceMap-30_255-2 38435748 31.0 ns/op 0 B/op 0 allocs/op BenchmarkMap/map-100_255-2 25903686 45.8 ns/op 0 B/op 0 allocs/op BenchmarkMap/slice-100_255-2 8872989 127 ns/op 0 B/op 0 allocs/op BenchmarkMap/sliceMap-100_255-2 38703240 31.4 ns/op 0 B/op 0 allocs/op BenchmarkMap/map-255_255-2 24418383 46.5 ns/op 0 B/op 0 allocs/op BenchmarkMap/slice-255_255-2 4521410 259 ns/op 0 B/op 0 allocs/op BenchmarkMap/sliceMap-255_255-2 34008592 31.9 ns/op 0 B/op 0 allocs/op
※ 計測コード: map_test.go · GitHub
strings.Builder による文字列構築の最適化
今回の件に限ったことではありませんが、文字列の構築時に string → []rune → string と変換をしていたため、メモリアロケーションが発生してしまっていました。
そこで、メモリコピーが最小限のstrings.Builderを使うことで改善できそうだと考えました。
ちなみに、strings.Builderを使ったほうが早いケースが多いですが、Grow()によってサイズを確保ができない場合などはそうでないこともあります。
実は、この初期実装では[]runeを扱っていたため、strings.Builderでは []runeを直接書き込むことができないので、strings.Builderのほうがパフォーマンスが出なかったのです。
最適化を取り入れた実装
上記の結果を元に下記の最適化をしました
[]runeではなく[]byteに分解mapではなくsliceにしindexアクセスstrings.Builderの利用
実装したコード
ベンチマーク結果
goos: linux goarch: amd64 BenchmarkReplace_30/regexp-2 2829 437092 ns/op 5392 B/op 3 allocs/op BenchmarkReplace_30/Replacer-2 49702 24842 ns/op 5408 B/op 3 allocs/op BenchmarkReplace_30/Trie-2 109918 13995 ns/op 2688 B/op 1 allocs/op BenchmarkReplace_Many/regexp-2 428 2870166 ns/op 11627 B/op 10 allocs/op BenchmarkReplace_Many/Replacer-2 40664 32979 ns/op 5031 B/op 3 allocs/op BenchmarkReplace_Many/Trie-2 47100 23681 ns/op 2688 B/op 1 allocs/op
allocsが1に減り、strings.Replacerより早くなりました。ただリストの数を30個から第1世代すべて(450個程度)をリストに含めたときを比較すると、strings.Replacerとの差が小さくなっているので、更に増えた場合にパトリシア木を取り入れているstrings.Replacerのほうが早くなる可能性があります。ただ、そもそもstrings.Replacerでフレーズが実現できないことと、リストの量的にもここで十分だと思い最適化は一旦終了しました。
最終的に作ったもの
ここまでで一旦パフォーマンスに満足ができたので、ここからフレーズに対応していきます。
フレーズについて機械学習を使わないで完璧に実装するのは困難なので、下記の仕様で実装することになりました。
- マッチする場合は単語の始まりからの前方一致である。
sexが禁止ワードならば、sexyはNG,unisexはOKとする
- スペースがいくつあろうと1つとみなす。
my sonが禁止フレーズならばmy sonもNG
- フレーズの場合最後以外は完全一致
my sonが禁止フレーズならばmy sonyはNGで,mysterious sonはOK
- 大文字小文字は区別しない
my sonが禁止フレーズならばMy SoNもNG
最後の単語が完全一致ではないのは、絵文字を含む区切り文字を全て判定するのが工数的にキツイということで交渉してこのような仕様になりました。
実装したコード
※ リポジトリ分けて公開するつもりでしたが間に合いませんでした。
ベンチマーク結果
goos: linux goarch: amd64 BenchmarkReplace_30/regexp-2 3352 364878 ns/op 5392 B/op 3 allocs/op BenchmarkReplace_30/Replacer-2 61447 19417 ns/op 5408 B/op 3 allocs/op BenchmarkReplace_30/Trie-2 19590 64318 ns/op 5376 B/op 2 allocs/op BenchmarkReplace_Many/regexp-2 439 2412237 ns/op 10081 B/op 10 allocs/op BenchmarkReplace_Many/Replacer-2 36723 27773 ns/op 5032 B/op 3 allocs/op BenchmarkReplace_Many/Trie-2 16647 73215 ns/op 5376 B/op 2 allocs/op
遅くなってしまいましたが、スペース判定や大文字小文字を区別しないなどが含まれるためしょうがないです。
終わりに
まとめると strings.Replacer のコードを読んでいて [256]byte というコードをみて「なんじゃこれ？」からの「うわーそういうことか！スゴい！！」という感動を120文字以内で表現したのがこちらです。
runeではなくてbyteにすることで、候補を最大256に絞りつつ、内部的にパトリシア木を入れることで、nodeの数を抑えているのか。凄いな。
— kensaku araga (@ken39arg) 2020年9月29日
さらにunexportedにする事でreplace処理にだけ限定して無駄な条件分岐などを排除しているのか。強い
車輪の再発明で巨人に立ち向かうのははこういった発見ができて最高に面白いですね！
明日も誰かがきっとかくと思います！ごきげんよう！！
-
フルマラソン2:50切りのことエガちゃんから来ている↩
-
プールではなく海や川などの自然で行う遠泳↩
-
合字(リガチャ)を使って文字を表現する言語で自分は読めない↩
-
大文字小文字の統一や複数の連続するスペースを1つにするなどの正規化がMatchでは問題ないが置換の際に元テキストを壊さず行うことが難しい↩
-
ECSで構築しているので最悪正規表現で実装してアプリのコンテナを増やせばなんとかなる目処が立ったので3日間挑戦することにした↩
-
goの標準ライブラリはほとんどgoによって書かれており、
strings.Replacerも同様です。 https://golang.org/src/strings/replace.go#L123↩ -
パトリシア木を使うとメモリが最適化される代わりに子ノードの検索が複雑し、コードの可読性と1ノードあたりのパフォーマンスが低下するため、独立した文字の並びが多くならない限りパフォーマンスは劣った。↩
