c - C: 辞書で文字列を検索する

Question

文字列の巨大なセット(辞書)を作成したアルゴリズムがあります。これで、別の巨大な文字列ストリームが連続して到着し、辞書に存在するかどうかに関係なく検索する必要があります。私は今までこのシナリオを実装することができました。ここで、文字列が 2 回または複数回到着した場合は、再度検索せずに「既存」としてマークする必要があります。どうすればこれを達成できますか? すでに解析された文字列を何らかの方法で保存せずに、私は考えられません。すでに解析された文字列を保存してから、すべての文字列が以前に到着したかどうかを確認すると、最適化の意図を損なうオーバーヘッドになります。何か案は？

Answer 1

ここでは、ハッシュテーブルを使用するのが最善の解決策です。この作業を迅速に処理するために最適化された機能を備えています。各文字列をハッシュテーブルに追加するだけで、暗黙的にチェックが行われます。

Answer 2

文字列配列をソートしたままにします。検索は O(N) ではなく O(log N) になり、パフォーマンスが大幅に向上します。