Trie を使った検索サジェスト機能の話 | TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
単純なTrieを用いたprefix検索では、一致するノードに到達した後、配下の全単語をDFSで探索し、重みに基づいてソートする必要がある。このため、配下の単語数が増大すると検索レイテンシが悪化し、リアルタイムなサジェスト提供の妨げとなる。
// Approach
各Trieノードに、その配下にある単語のうち重み（frequency）が大きい上位K件をあらかじめ保持させるキャッシュ戦略を採用。構築時にボトムアップで再帰的にキャッシュを埋めることで、検索時はprefixのパスを辿るだけで即座に候補を返せるように設計する。
// Result
検索時の計算量を、配下の単語数に依存する状態から、入力文字列の長さに依存する状態へと改善。実用的なサジェスト機能の基盤となる。運用面では、検索ログに基づいた定期的なキャッシュ再構築や、Elasticsearch等の既存ツールの活用が示唆されている。
Senior Engineer Insight
> 本手法は典型的なSpace-Time Tradeoffの好例である。検索レイテンシを極限まで削るためにメモリを投じる設計は、大規模トラフィック環境では定石だが、ノード数とキャッシュ件数によるメモリ消費の爆発には注意が必要だ。実運用では、頻繁な更新を求めるのではなく、バッチによる再構築や、Discussionにあるような「直近クエリの高速パス」との組み合わせが、スケーラビリティと鮮度のバランスを取る鍵となるだろう。