次の操作に最適なデータ構造は何ですか :
データ構造は単語のリストを格納します
入力: 文字列 'pre' という名前を付け
ます 出力: pre をプレフィックスとして持つすべての文字列のリスト (格納された単語) であり、リスト内の単語は、優先度の高い順に並べる必要があります。
出力として返される文字列のリストから特定の文字列が使用された場合、その文字列の優先度が上がります。
これを単語予測に使用するため、ユーザーが特定の単語を選択するたびに (返された単語のリストから)、優先度が 1 ずつ増加します。
すでにトライを実装していますが、アルファベット順に出力 (リスト) が得られます。優先度順に並べたい。
4 に答える
0
他の回答が示したように、トライを使用して、特定のプレフィックスを持つすべての単語をすばやく取得し、優先度に従って単語を並べ替えることができます。トライから一致する単語を取得するためのアクセス時間を無視すると、一致する単語を取得kすると、優先順位に従ってソートするのにO(k log k)時間がかかります。これは理論的に最適なO(k)時間に非常に近いため、実際のアプリケーションのためにそれを改善しようとすることを気にしたくないでしょう。特に、並べ替え後に単語を出力すると、一致する単語の平均の長さであるk実行時間O(kl)が実際にかかるためです。lの乗数はl、通常、 とほぼ同じオーダーになりlog kます。ただし、使用するスペースの量をO(L_avg)どこに掛けても構わないと思っている場合は、L_avgはすべての単語の平均の長さです。次に、並べ替えられた順序で単語にアクセスし、優先度 +1 を更新して、優先度 +1 を取得する選択した単語の長さを更新する時間を得ることができます。単語O(k + L log n)のL総数nは次のとおりです。 .
このアイデアは最初は少し奇妙に聞こえるかもしれませんが、ご容赦くださいO(L_avg)。後で説明するように、メモリは実際には倍増するだけです。アイデアは、トライの各ノードで、対応する接頭辞を持つすべての単語をそれらの優先度とともに、自己均衡二分探索木 (優先度に従って順序付け) に格納するというものです。完全な単語ではなく、単語を格納する配列へのインデックスとして単語を表すことができるため、トライの各ノードでのストレージ要件は、対応するプレフィックスを持つ単語の数に比例します。単語の優先度が +1 になると、トライを上に移動して、その単語とそのすべての親ノードに対応するトライ ノードの平衡二分探索木を更新する必要があります。O(L log n)時間。ただし、クエリに応じて並べ替えられた順序で単語のインデックスを取得するには、二分木を前の順序でトラバースするだけで済みますが、これにはO(k)時間がかかります。次に収納について。長さの単語はバイナリ ツリーLに格納され Lます。単語のトライ ノードのツリーと、そのすべてのL-1親ノードのツリーです。したがって、トライのすべてのノードですべてのツリーの合計ストレージを合計すると、各単語がツリーで発生する回数を数えることによって、ツリーの合計ストレージはすべての単語の合計の長さで線形になります。O(n L_avg). ストレージでその乗数を処理できる場合、これがクエリと優先度の変更を処理するための理論的に最速の方法であると思います。log kクエリ結果を並べ替えて得られる乗数。
于 2013-08-03T16:29:40.653 に答える