文字列のリストを使ってルックアップを行う方法は？

Question

私は、1から6までの任意のエントリを持つことができる文字列のリスト（List<String>）を持っています。私ができるようにしたいのは、その文字列のリストを使ってルックアップを行うことですが、2つ以上の文字列の組み合わせを使用してルックアップを行うことができるようにします。私は現在Dictionary<List<String>, String>を使っていました。

ex。 は私のリストがそれに次があるとし、「火」、「エアロ」、「雷」、「水」、「ブリザード」と、私は私の辞書に次のエントリを持っています。

List<String>(){"fire", "aero"}, "searing wind" 
List<String>(){"fire", "aero", "thunder"} "firestorm" 
List<String>(){"aero", "thunder"}, "storm" 
List<String>(){"aero", "water", "blizzard"}, "snowstorm" 
List<String>(){"aerora", "blizzara"}, "hailstorm" 

私は、ルックアップをしたいです私のベースリストには、それらを探すのに必要なすべての値が含まれているので、最初の4つのエントリを返す。後でベースリストからそれらの値をクリアする必要があるので、ルックアップを行うためにどの値が使用されたのかも知る必要があります。辞書のエントリ数は〜400になる可能性があります

この検索を行うには徹底的な方法が考えられますが、検索を行う際に順序が問題になることがあるため、時間がかかりますすべての順列を作り、それらを見上げる。辞書キーリストにアルファベット順を付けることができれば助かります。誰でもこれを行うためのよりよい方法、あるいはこれを行うためのもっと効果的な方法を知っていますか？私はすでにこのプログラムのいくつかの他のもののためにsqliteを使用しているので、私はそれを使用することができる私はより速い検索を与えるつもりなら。あなたが探検することをお勧めします

おかげ

Answer 1

1つのオプションは、decision treeを使用することです。アイデアはこのようなものになります。いくつかの任意の文字列を選択し、すべてのセットを2つのグループ、つまりその文字列を含むグループとその文字列を含まないグループに分割します。次に、この手順を両方のグループで再帰的に繰り返し、作成したすべての決定からツリーを構築します。たとえば、のは、あなたの表記の省略表現をご紹介しましょう：

A =エアロ

R = Aerora

F =火

T =サンダー

W =水

B =ブリーザード

このようなツリー：

start --> A? -- NO --> R? -- YES --> B? -- YES --> "hailstorm" 
      | 
      +--- YES --> F? -- YES --> T? -- YES --> "firestorm" 
          |    | 
          |    +----- NO --> "searing wind" 
          | 
          +----- NO --> T? -- YES --> "storm" 
             | 
             +----- B? -- YES --> "snowstorm" 

は、あなたがこのようなツリーを持っていたら、あなたは文字列の集合としてあなたの属性を格納することができ、その後、次のようにすべての一致を調べます。ツリーのルートから始めて、与えられたノードによって示された文字列を見てください。その文字列が文字列のセットに含まれている場合は、YESブランチを再帰的に続行し、ツリーのその部分のすべての一致を見つけます。次に、そのブランチを見下ろしているかどうかにかかわらず、NOブランチを探索して、クエリに一致する可能性のある他のすべての文字列を取得します。

キーワードとして文字列の数が少ないと仮定すると、ツリーの深さは非常に小さくなる可能性があります（kキーワードの場合は最大でもO（k））。検索にはO（k）時間ほどの時間がかかります。最悪の場合、木全体を探索するだけで時間がかかる（O）。さらに、機械学習のテクニックを使用することで、サイズとルックアップスピードとの間に確実なトレードオフを持つ非常に優れたツリー構造を構築することができます。

希望すると便利です。