Как сделать поиск, используя список строк?

Question

У меня есть список строк (a 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 для некоторых других вещей в этой программе, так что если это даст мне более быстрый поиск, я мог бы использовать это.

Спасибо

Answer 1

Один из вариантов, который вы, возможно, захотите изучить, - это использовать дерево решений . Идея была бы что-то вроде этого. Выберите произвольную строку, затем разбейте все свои наборы на две группы - группы, содержащие эту строку, и группы, не содержащие эту строку. Затем, рекурсивно повторите эту процедуру для обеих групп и создайте дерево из всех решений, которые вы приняли. Например, давайте введем сокращение для вашей записи:

A = Aero

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, чтобы получить все остальные строки, которые могут соответствовать вашему запросу.

Преимущество этого подхода состоит в том, что, если у вас есть небольшое количество строк в качестве ключевых слов, глубина дерева может быть очень мала - не более O (k) для k ключевых слов - и поэтому в лучшем случае ваш поиск займет всего O (K) время. В худшем случае вы просто исследуете все дерево, что занимает время O (n). Более того, используя методы машинного обучения, можно построить очень хорошую древовидную структуру, которая будет иметь солидный компромисс между размером и скоростью поиска.

Надеюсь, это поможет!