20251130sat

1. トライ木検索が速い理由

• 単語ごとではなく、文字ごとに検索をするから
• 各ノードに次にどの文字があるかをDictionaryで管理しているため、次の文字の有無検索が早い。(Dicitonary自体が速い。）
• 通常の検索は、検索語の数だけ、文章の走査を繰り返す。検索語が1000語あれば、1000回文章を走査する。（正しくは、頭文字が一致するかをみて、一致すれば検索語の文字数分だけの文字を完全一致で探すらしい）
• trie検索は、文章を一文字ずつ、登録済みのDictionaryをつかって、一回の走査で一気に探す。
• 普通の検索は　文章の走査を検索語の数だけする。-
• trie検索は、文章の走査は一回だけ、一文字ずつ検索語の辞書をもって、検索する。 検索語の辞書は一文字ずつ調べて、ヒットしなければすぐ打ち切り、そもそも辞書はハッシュテーブルなので、検索が速い。

#TrieNode