Как я могу эффективно найти подмножества набора на карте?

Question

Считайте, что у меня есть карта наборов значений в значения, в Java тип этой карты будет:

Map<Set<Object>, Object> setToObjMap;

Учитывая новый набор объектов set, я хочу найти всезначения в setToObjMap, где связанный ключ является подмножеством"поискового набора".

Так, например, если моя карта была:

["telephone", "hat"] -> "book"
["laugh", "fry", "mouse"] -> "house"
["dog", "cat"] -> "monster"

ТогдаПри заданном поисковом наборе ["telephone", "hat", "book", "dog", "cat"] я бы извлек значения «книга» и «монстр».

На практике в setToObjectMap могут быть десятки тысяч записей с десятками тысяч возможных значенийв наборах.В поисковом наборе обычно содержится около 10 элементов.

Я надеюсь, что есть эффективный способ сделать это, не требующий перебора всех ключей на карте.Кто-нибудь может предложить какие-либо предложения?

Answer 1

Вы можете создать структуру данных поиска

Map<String,List<Finder>>

С Finder, имеющим int count и max и слово res.Обратите внимание, что список предназначен для того, чтобы позаботиться о случае, когда множество наборов в setToObjMap могут использовать одно и то же слово, чего нет в ваших примерах.

"telephone" -> [{res:"book",count=0,max=2}]
"hat" -> same object as above
"laugh" -> [{res:"house",count=0,max=3}]
...

Эта коллекция поиска быстро создается идаже быстрее сбрасывать после поиска.

Алгоритм поиска перебирает set для каждого слова, и каждый Finder для этого слова увеличивает переменную count.Второй проход, взять все значения карты поиска, если count==max, поставить res в результате.

Алгоритм инициализации:

for Entry e in setToObjMap
  Finder f = new Finder(e.value, 0, e.key.size) // res, count, max
  for String word in e.key
    lookup.get(word).add(f)

Алгоритм поиска:

for String word in set
  for Finder f in lookup.get(word)
    f.count ++
for Finder f in lookup.values()
  if (f.count==f.max)
    res.add(f.res)

Алгоритм сброса:

for Finder f in lookup.values()
    f.count = 0

Что касается сложности, если n равноколичество элементов в set и m количество значений в setToObjMap, сложность будет O (n + m)

Answer 2

Если рассматриваемые наборы малы, а карта велика, лучшим способом было бы сгенерировать все подмножества набора и просмотреть их на карте.

Если в вашем наборе есть k элементов и на карте есть n ассоциаций, это потребует 2^k поисков против n проверок подмножеств в обратном направлении. Вы видите, что для n = 1000 и k = 20 это было бы плохой идеей, но для n = 100000 и k = 10 это было бы победой.

Answer 3

Еще один вариант - построить индекс из одного элемента в наборы ключей:

"hat" -> ["telephone", "hat"]
"telephone" -> ["telephone", "hat"]
"laugh"->["laugh", "fry", "mouse"]
"fry"->["laugh", "fry", "mouse"]
"mouse"->["laugh", "fry", "mouse"]
"dog" -> ["dog", "cat"]
"cat" -> ["dog", "cat"]

Это позволит быстро запрашивать наборы ключей путем ввода.

Answer 4

Итерация по карте - один из вариантов. Для этого требуется время O ( n × m ), где n - количество записей на карте, а m - количество элементы в наборе запросов; коэффициент m возникает из-за проверки подмножества.

Другая опция генерирует все подмножества набора для поиска и поиска тех на карте. Это занимает O (2 ^ m ) время. Это может быть быстрее, чем первый вариант, если 2 ^ m мало по сравнению с n (поэтому m должно быть очень маленьким). В вашем примере использования 2 ^ m = 2 ^ 10 = 1024, что меньше десятков тысяч.

Если известно, что размер набора запросов может варьироваться, вы даже можете использовать гибридную стратегию: вычислите число 2 ^ m и проверьте, меньше ли оно n , затем выберите лучший из этих двух вариантов в зависимости от результата проверки.

Answer 5

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