辞書を格納するのに最適なデータ構造はどれですか? ハッシュテーブルかトライか? 後で辞書に単語を追加できる可能性を考慮してください。
5002 次
2 に答える
4
std::unordered_maporstd::mapは、ディクショナリに最適なデータ構造です。std::unordered_mapハッシュ テーブルに相当する C++11 です。Whilestd::mapは通常の連想コンテナーです。
于 2012-12-24T21:40:22.183 に答える
2
これらのデータ構造はどちらも、互いに「優れている」わけではありません。それはあなたのニーズが何であるかに完全に依存します.
「ハッシュ テーブルに文字列 X は存在しますか?」という質問に答えることに主な関心がある場合は、文字列のハッシュ テーブルが適しています。(通常) 高速なルックアップをサポートし、メモリ フットプリントが小さくなっています。各文字列は 1 回だけ格納されます。ただし、優れたハッシュ関数の存在に依存しており、異常な入力のハッシュ衝突の影響を受けやすく、「私の文字列に最も近い文字列はどれですか?」などの検索を行うことはできません。
トライは、文字列を格納するための優れたデータ構造であり、最悪の場合のルックアップが適切に行われます (入力文字列の各文字を 1 回確認するだけで済みます)。また、類似したプレフィックスを持つ文字列をコンパクトに格納できるという利点もあります。さらに、トライを使用すると、特定のプレフィックスを持つ文字列を検索したり、正規表現検索を効率的に実行したり、近くの単語を効率的に検索したりできます。格納されるポインタの数が原因で、トライのメモリ使用量がハッシュ テーブルのメモリ使用量よりもはるかに高くなる傾向があるという欠点があります。
これら以外にも、検討できるデータ構造があります。基数トライとパトリシア ツリーは、トライのより凝縮された表現を提供しますが、プログラミングの複雑さが増します。 BK ツリーは、最初の文字列に「近い」すべての文字列を効率的に検索することに主に関心がある場合に使用できます。
要するに、メモリが貴重な場合、または「文字列を閉じる」検索を行う必要がない場合は、ハッシュ テーブルが適しています。近くの文字列を探す必要がある場合や、他の文字列操作を行う必要がある場合は、おそらくトライの方が適しています。
お役に立てれば！
于 2012-12-24T21:42:43.310 に答える