8

次のように、値にマップされたキーで構成されるデータがあります。

---------------------
Key          | Value
---------------------
(0, 0, 0, 0) | a
(0, 0, 0, 1) | b
(0, 1, 0, 1) | c
(0, 1, 1, 0) | d
....

キーに対して検索クエリを効率的に実行できるデータ構造を探しています。クエリはキーを完全または部分的に指定できます。例えば：

(0, 0, 0, 1) -> a
(0, *, *, *) -> [a, b, c, d]
(0, 1, *, *) -> [c, d]

私が今持っているアイデアは、これに似た通常のツリーを使用してこれを実装することです: 木 葉ノードは値を表し、非葉ノードはキーの一部です (つまり、w、x、y、z ノードは最初、2 番目です) 、それぞれキーの 3 番目と 4 番目の部分)。シンプルな BFS アルゴリズムを使用して、任意のクエリに応答できます。しかし問題は、このツリーが鍵の新しい部分ごとに指数関数的に成長していることです。

この問題を解決するには、どのデータ構造/アルゴリズムがより適切ですか? キー部分は数値または文字列であることに注意してください。

4

3 に答える 3

2

キーの各部分にmaximum( ) 値が存在する場合、基数(または混合基数) でM書かれた数値としてキーを解釈することにより、単一のキー付きツリーを作成できます。M

  • ワイルドカードは1つのインデックスにのみ表示され、それ以降はすべてワイルドカードであると想定しています。この方法(x,*,*,*)は次のクエリになります(x*M^3,(x+1)*M^3-1)

文字列の場合:

  • 区切り文字とトークンを使用してキーを貼り付けることができます（次を使用|：

('ax','bc','a','x') -> 'ax|bc|a|x'

セパレーターは入力文字列に表示されるべきではありません（表示される場合がありますが、その場合、要求された結果へのアクセスを妨げる可能性があります）

しかし...あなたの状況がdifficultオブジェクトをとして使用できる場合keys、Javaclassではキーのを作成し、それらの間の比較演算子を定義します

例として引用します： 複数のフィールドでオブジェクトを比較する方法

于 2013-09-01T08:18:41.970 に答える