辞書のすべての単語を格納するのに最適なデータ構造は何ですか? 私が考えることができる最善の方法はHashMap、 にマップされる を使用することでしたHashTable。基本的に、最初の文字に応じて関連付けを取得し、HashTableこれを使用して、その文字から始まる単語を追加できます。次に、文字列に基づいて適切なハッシュ関数を選択します。
より良いアプローチはありますか？
73992 次
1 に答える
148
やりたいことに応じて、優れたデータ構造がたくさんあります。
単語を保存して「この単語はここにあるかどうか」を確認したいだけの場合は、他に派手な機構を持たない標準的なハッシュ テーブルが合理的なアプローチです。その単語が事前にリスト固定されている場合は、完全なハッシュ テーブルを使用して、優れたパフォーマンスとスペースの使用を実現することを検討してください。
高速ルックアップをサポートしながら、特定のプレフィックスが存在するかどうかを確認できるようにしたい場合は、トライが適切なオプションですが、スペースの効率が少し悪い場合があります。また、高速な挿入または削除もサポートしています。また、ハッシュでは提供されないアルファベット順の反復も可能です。これは基本的に、回答で説明した構造ですが、ユースケースによっては、試行の他の表現の方が良い場合があります。
上記に加えて、単語リストが固定されていることがわかっている場合は、基本的に言語の最小状態 DFA であるDAWG (有向非巡回単語グラフ) の使用を検討してください。trie よりも大幅にコンパクトですが、同じ操作の多くをサポートしています。
トライのような動作が必要であるが、大きなスペース ペナルティを支払いたくない場合は、基数ツリーと同様に、三分探索ツリーも実行可能なオプションです。これらは非常に異なる構造ですが、さまざまな状況でトライよりもはるかに優れている場合があります。
スペースが問題であるがトライが必要な場合は、簡潔なトライ表現を調べてください。ルックアップは遅くなりますが、理論的にはほぼ最適なスペース使用量です。このリンクでは、大量のデータを送信する簡単な方法として JavaScript でどのように使用されているかについて説明しています。別のコンパクトな表現はdouble-array trieですが、確かに私はそれについてほとんど知りません。
他の単語に類似した単語を検索する必要があるスペル チェックなどの操作に辞書を使用する場合、BK ツリーは検討すべき優れたデータ構造です。
お役に立てれば！
于 2012-04-04T19:21:16.570 に答える