6

データ構造とアルゴリズムに関する学部課程の学期プロジェクトとして辞書プログラムを作成する必要があり、問題に対する最適な解決策 (データ構造) を見つけることが期待されています。

ハッシュ テーブルまたはトライのいずれかを使用することを検討しました。誰かからTreapsの使用を勧められましたが、まだ調べていません。

私のデータベースには、約 10 万個の異なる単語とその意味が含まれています。プログラムが提供することが期待される基本的な機能は、単語/定義の挿入、更新、削除、および検索です。オートコンプリートとスペル修正をなんとか押し込むことができれば、それは追加のボーナスになります.

したがって、私の質問は、私の要件を念頭に置いて、どのデータ構造が私の目的に最も適しているかということです。私が「最高」と言うとき、実行時の複雑さと低コスト (メモリ要件) が最も優れたデータ構造を求めています。

また、指定された接頭辞で始まるすべての単語を返すアルゴリズムが必要でした。たとえば、関数呼び出しを行うと、、、などで始まるdictionary.getWordsStartingWith("fic")すべての単語のリストが返されるはずです。辞書をトライとして実装すれば、これを実行できることはわかっていますが、これは可能ですが、可能ですか?ハッシュテーブルでそれを行うには？ficfictionfictitiousfickle

4

1 に答える 1

3

自動補完/接頭辞の一致を行いたい場合は、ほぼ確実に試してください。ハッシュ テーブルは実際にはこれを可能にしません。実際、優れたハッシュ関数は、非常に類似したキー (たとえば、同じプレフィックス) でさえ、配列の完全に異なる部分にマップされるように設計されています。ハッシュの目的では、これは機能と見なされます。

Treap は基本的に、確率とヒープのプロパティを使用してバランスを取る二分探索木です。一般に、インターフェイスは標準の BST ツリー インターフェイスです。したがって、実際には、赤黒ツリーまたは AVL ツリーとはわずかに異なるプロパティにつながる実装の詳細にすぎません。

BST は、トライとして解決しようとしていると思われる問題にはほとんど適していません。BST はすべて不等号を下向きにたどる傾向がありますが、trie は等号を下向きにたどります。数値データを扱っている場合、等式は非常にまれであるため (可能性の空間が巨大であるため)、不等式の比較がすべてです。文字列では、各文字の可能性はほとんどないため、ほとんどのノードでキーを実際に格納しないなどの最適化につながる、等式を利用する方が理にかなっています。

要約すると、試行を続行することをお勧めします。それらはまさにこの種のものに非常に頻繁に使用されており、スペース/サイクルが貴重なモバイルでのテキスト入力に特に使用されるため、それらを最適化するためのリソース (特にスペース) を見つけることができます。また、私見を学ぶのは非常に興味深いデータ構造です.a）おそらく新入生のデータ構造でよく学んだBSTと比較して、b）データ構造はそれほど興味深いものではありません; バランシング スキーム以外はすべて自明であり、バランシング スキームは何よりも退屈です (RB ツリーには、バランシングのための 7 つの真に異なるケースなどがあるため、RB ツリーをコーディングしてすべてを正確に取得するのはかなり困難です)。

ウィキペディアのページには、いくつかの良い情報があります: https://en.wikipedia.org/wiki/Trie。ビット単位の試行は特に興味深いようです。

于 2015-12-26T19:57:48.290 に答える