Поддержание набора наименьших подмножеств

Question

Вот операции, которые я хотел бы выполнить с гипотетической структурой данных сбора, которая содержит наборы в качестве своих элементов:

1. Вставить набор в структуру данных, но: (1) если новый набор является надмножеством любого из существующих наборов, не добавляйте его (2), если новый набор является подмножеством любых существующих наборов, удали их.
2. Перечислите все наборы, которые в настоящее время находятся в коллекции

Все рассматриваемые множества являются подмножествами известного конечного множества, скажем, {0..10 ^ 4}.

Есть ли способ сделать это эффективно?

Answer 1

Вот недавняя статья по этой проблеме: http://research.google.com/pubs/pub36974.html

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

Answer 2

Все рассматриваемые множества являются подмножествами известного конечного множества, скажем, {0..10 ^ 4}.

Давайте назовем это N = 10 ^ 4. Это достаточно мало, и это окажется полезным. Допустим, у вас есть наборы S.

«Логически» это означает, что у вас есть матрица N * S.

У вас уже будет набор наборов. В этой первичной структуре есть S наборов.

10 ^ 4 достаточно мал, чтобы вы могли поддерживать вторичную структуру данных, в которой для каждого значения N хранится список наборов , в котором она находится. Эта структура вроде как транспонирование первичной структуры. Это может быть вектор длины N, позволяющий искать в постоянном времени список наборов, в которых находится конкретное значение.

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

new_set = {2,5,10}

Вторичная структура сообщает нам, в каких наборах они находятся:

 2 : {A,B,D}
 5 : {B,D}
10 : {B}

Мы можем объединить и отсортировать эти три списка, чтобы получить ABBBDD, который говорит нам не только о том, какие наборы перекрываются, но и о размере перекрытий. Три узла совместно используются с B, что означает, что наш новый набор является подмножеством или равен B. Мы совместно используем 1 узел с A и два узла с D. Если окажется, что общий размер A равен 1, тогда мы теперь знаем, что A является подмножеством нашего нового набора.

Answer 3

Используйте какую-то древовидную структуру.

Например. Сохраните отсортированные существующие наборы в Trie. На каждом узле поддерживать флаг, если путь, ведущий к этому узлу, является существующим набором

1 Чтобы проверить, является ли данный набор надмножеством уже существующего набора:

def issuperset(node, set[N], setc, N):
    if node.is_set:
        return True
    for j = setc:N
        if set[j] is a child of node:
            if issuperset(node.child[set[j]], set, j+1, N):
                return True
    return False

2 Удалить все надмножества данного набора

def remsuperset(node, set[N], setc, N):
    if setc == N+1:
        remove_all_sets_on_or_below_this_node(node)
        return
    for ch in node.child:
        if ch< set[setc]:
            remsuperset(node.child[ch], set, setc, N)
        elif ch == set[setc]:
            remsuperset(node.child[ch], set, setc+1, N)

3 Для перечисления множеств просто пройти по дереву и путь печати is_set, флаг True -

Answer 4

Для эффективности использования пространства вы можете использовать набор битов для представления каждого подмножества известного конечного набора.Существуют также методы для представления разреженных наборов битов (см., Например, этот пример Java ) для получения дополнительной экономии места.

Общая структура может представлять собой набор наборов битов.В Java BitSet не имеет метода тестирования подмножества, но я не думаю, что было бы слишком сложно расширить BitSet, чтобы включить эффективный метод тестирования подмножества.(Это позволило бы избежать неприятной задачи проверки того, равен ли добавляемый кандидат его пересечению с любым из существующих подмножеств.)

Answer 5

Поддерживать фильтр Блума для всех сохраненных наборов. Создайте фильтр Блума для набора, который будет вставлен. Если вы поразрядно И фильтр для набора, который будет вставлен (вызовите это X) с помощью фильтра Блума другого набора, и вернете значение X обратно, то ваш набор для вставки МОЖЕТ быть подмножеством (возможно, ложноположительным, вам нужно проверить медленный путь в этой точке). В противном случае это определенно не так, и вы можете попробовать с другим.

Существует множество настраиваемых параметров при создании фильтра Блума, которые позволяют вам находить компромисс между эффективностью пространства и вероятностью ложных срабатываний.

http://en.wikipedia.org/wiki/Bloom_filter

Answer 6

Перечислять наборы в коллекции просто, O (n).Однако проверка нового кандидата на предмет подмножества всех существующих наборов будет несколько дорогостоящей.Есть хорошо известные алгоритмы тестирования, если один набор является подмножеством другого, так просто

for each subset s in S
    for each candidate set C
        test of C is a subset of s
        if it is, break
if never found, add C to S.

Это будет что-то вроде O (n ^ 2 lg n).Это считается "эффективным"?