如何使用字符串列表進行查找？

我有一個字符串列表（一個List<String>），可以有1到6個條目的任何地方。我希望能夠做的就是使用該字符串列表進行查找，但是我希望可能的查找能夠使用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的一些其他的東西，所以如果這將讓我更快的查找我可以使用它。

感謝

來源

2011-02-28 Megatron

一種選擇你可能想探索將使用decision tree。這個想法會是這樣的。選擇一些任意字符串，然後將所有集合分成兩組 - 包含該字符串的組和不包含該字符串的組。然後，在這兩個組上遞歸地重複這個過程，並根據你所做的所有決定構建一棵樹。例如，下面我們來介紹一種簡寫爲您的符號：

A =航空

R = Aerora

F =火

T =雷霆

W =水

B = Blizzard

然後你可以建立一個樹是這樣的：

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（n）。而且，使用機器學習技術，可以構建一個非常好的樹形結構，在大小和查找速度之間進行權衡。

希望這會有所幫助！

來源

2011-02-28 01:58:32 templatetypedef

如何使用字符串列表進行查找？

回答

相關問題