trie の単純検索 (prefix マッチ)
10 万語を頭から突き合わせると間に合わない
検索ボックスに 1 文字入るたびに、候補の一覧から「その文字列で始まる単語があるか」を出したいとします。素直に書けば、候補を全部順に見ることになります。
JavaScript
words.some(word => word.startsWith(input));候補が 3 語なら何の問題もありません。10 万語あって、1 文字打つたびに全部を見るとなると、指の速さに追いつかなくなります。しかも無駄が多い。ほとんどの単語は 1 文字目で外れるのに、毎回 1 語ずつ取り出しては最初の文字から比べ直しています。
同じ書き出しを 1 本の枝にまとめる
sun sum sea の 3 語で考えます。sun と sum は su まで同じで、sea とも s を共有しています。この重なりを、あらかじめ 1 本の枝として持っておくのが trie です。
1 つの節が 1 文字を持ち、その先に「次に来られる文字」だけがぶら下がっています。入れ物は特別なものでなくてよく、次の文字をキーにした辞書を入れ子にすれば、この形がそのまま表せます。
JavaScript
{ s: { u: { n: {}, m: {} }, e: { a: {} } } }1 文字ずつ枝を降りる
su で始まる単語があるかを知りたいとき、やることは 2 手だけです。根の辞書に s のキーがあるか見て、あればその中へ移る。次に u のキーがあるか見て、あればその中へ移る。最後まで移れたなら、そこから先にぶら下がっているものはすべて su で始まる単語なので、答えは「ある」です。
途中でキーが無ければ、その場で答えが決まります。sun しか入っていないところに sunny を聞かれたら、n の先に次の n の枝が無いので、そこで打ち切ります。候補が 3 語でも 10 万語でも、見る回数は入力した文字数と同じです。増えるのは作るときの手間だけで、1 度作った枝は何度でも使い回せます。
検索窓の入力補完のほかに、郵便番号や電話番号の前方一致、IP アドレスの経路表のように、「先頭から一致する範囲を絞りたい」場面では同じ形が出てきます。共通の書き出しを 1 本にまとめてあるので、置き場所も単語をそのまま並べるより小さく済みます。
なお、入力が空文字列のときは 1 手も降りません。何も確かめないまま最後まで移れたことになるので、答えは「ある」になります。
今回は「始まるか」だけを答えるので、単語の終わりを示す印は要りません。sun と sunny の両方を入れて「sun という単語そのものがあるか」まで区別したくなったとき、初めて終わりの印が必要になります。
覚え方 ... 突き合わせるのは単語ではなく文字。降りられなくなった時点で答えが出る。
要件
- words の各文字を trie (辞書のネストなど) に挿入する処理を内部に書くこと
- プレフィックスをルートからたどれれば true、途中で枝がなくなれば false を返す
- 空文字列のプレフィックスは常に true を返す
入出力例
hasPrefix(["cat","car","dog"], "ca") → true
hasPrefix(["cat","car","dog"], "do") → true
hasPrefix(["cat","car","dog"], "ba") → false
hasPrefix(["cat","car"], "cat") → true
hasPrefix(["cat"], "cats") → false
hasPrefix(["cat"], "") → trueヒント
