Подтвердить что ты не робот

Быстрая структура данных для нахождения строгих подмножеств (из определенного списка)

У меня есть большой набор множеств, например. {{2,4,5} , {4,5}, ...}. Учитывая одно из этих подмножеств, я хотел бы повторить все остальные подмножества, которые являются строгими подмножествами этого подмножества. То есть, если меня интересует набор A, например. {2,4,5}, я хочу найти все наборы B, где относительное дополнение B / A = {}, пустое множество. Некоторые возможности могут быть {2,4}, {2,5}, но не {2,3}

Я мог бы, конечно, искать линейно и проверять каждый раз, но я ищу эффективную структуру данных как для большего набора, так и для подмножества (если это имеет значение). Количество подмножеств обычно составляет 10 тысяч, но если это имеет значение, меня будут интересовать случаи, когда это может быть в сотнях миллионов. Размер подмножеств обычно составляет 10 с.

Я программирую на С++

Спасибо

4b9b3361

ОТВЕТЫ

Ответ 1

Математически вы должны построить диаграмму Хассе для ваших наборов, которая будет частично упорядоченным множеством с вершинами ваших множеств и стрелками, заданными сдерживанием, По существу, вы хотите создать направленный ациклический график со стрелкой A --> B, если A строго содержит B, и нет C такое, что A строго содержит C и C строго содержит B.

На самом деле это будет ранжированный poset, означающий, что вы можете отслеживать "уровни" орграфа на основе мощности множеств. Это похоже на создание хеш-таблицы для перехода к правильному набору.

Из A просто выполните BFS по графику, чтобы найти все правильные подмножества A.

Как реализовать это: (в псевдокоде)

for (C in sets) {
    for (B in HasseDiagram at rank rank(C)+1) {
      if (C contains B)
        addArrow(C,B)
    }
    for (A in HasseDiagram at rank rank(C)+1) {
      if (C contains A)
        addArrow(A,C)
    }
    addToDiagram(C)
}

Чтобы сделать эту и все подпрограммы быстрыми, вы можете кодировать каждый набор двоичным кодом, где цифра i равна 1, если i находится в C и 0 в противном случае. Это делает тестовое сдерживание и определение ранга тривиальным.

Вышеуказанный метод работает , если у вас есть все возможные подмножества. Так как вы можете пропустить некоторые из них, вам придется проверять больше вещей. Для псевдокода вам нужно будет изменить rank(C)-1 на наибольшее целое число l < rank(C), чтобы какой-то элемент HasseDiagram имел ранг l и аналогично для rank(C)+1. Затем, когда вы добавляете набор C к диаграмме:

  • Если A охватывает C, вам нужно всего лишь проверить нижние ранговые множества B, которые также покрываются A.

  • Если C охватывает B, вам нужно только проверить более ранжированные множества A, которые также охватываются B.

В "X охватывает Y" Я имею в виду, что есть стрелка X -> Y, а не только путь.

Кроме того, когда вы вставляете C между A и B с помощью одной из вышеуказанных проверок, вам нужно будет удалить стрелку A --> B при добавлении A --> C и C --> B.

Ответ 2

Я бы предложил сохранить все наборы в дереве. Каждый node дерева будет представлять все наборы, содержащие указанный начальный список целых чисел. Я хотел бы, чтобы узлы содержали следующие фрагменты информации:

  • Число дополнительных элементов в самом маленьком наборе в этой точке или ниже в дереве. (0 означает, что этот node находится в дереве.)
  • Битовый набор, представляющий пересечение всех подмножеств ниже этого в дереве.
  • Указатель на массив, сопоставляющий большие целые числа с поддеревьями, которые содержат это как следующий элемент. В качестве специального случая, если в дереве есть только одно подмножество, этот указатель может быть нулевым. (Нет необходимости заполнять незаселенные части дерева.)

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

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

Теоретически обход этого дерева может быть временем O(n). Но на практике вы обрезаете ветки дерева довольно рано и не будете пересекать большинство других подмножеств. Задняя часть расчета конверта предполагает, что если у вас есть n случайный набор из k элемента с n << 2k, тогда поиск дерева будет O(n0.5k). (На каждом целое число, в половине случаев, когда оно находится в вашем наборе, вы ищете подмножества, и вы разделили ваш поиск на 2, а половину времени, когда он не находится в вашем наборе, и вы устраняете половину своего места. После j целые числа, которые у вас есть 2j/2, поиск наборов наборов размера 2-jn. Таким образом, к тому времени, когда вы получите поиск до одного другого подмножества, с которым можно сравнить, есть поиск O(n0.5). Окончательное сравнение растровые изображения O(k).)

Примечание. Я убежден в этом обратном вычислении конверта, что средняя производительность o(n0.5+epsilon) для каждого epsilon > 0, но конвергенция очень медленная. Точнее, я подозреваю, что среднее арифметическое производительности n0.5 + O(sqrt(log(n)))). Но эта часть sqrt(log(n)) занимает много времени, чтобы сходиться.

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

Ответ 3

Подход, предложенный PengOne, будет работать, но он не очень эффективен. Чтобы понять, почему это не удается, рассмотрите следующий патологический пример:

Предположим, что у вас есть юниверс U, у которого есть n различных элементов, и пусть множество всех найденных вами наборов состоит из всех подмножеств U с ровно k элементами. Тогда верно, что никакие пара множеств здесь строго не содержатся друг в друге; и поэтому в худшем случае вам придется искать по всем n выбранным k возможным наборам! Другими словами, использование предложенной структуры данных не лучше, чем наивный линейный поиск в худшем случае.

Ясно, что вы можете сделать гораздо лучше, чем это, и правильная структура данных для использования будет trie: http://en.wikipedia.org/wiki/Trie

Чтобы адаптировать trie для работы для наборов вместо простых строк, достаточно зафиксировать упорядочение на элементах универсального набора, а затем закодировать каждое из ваших подмножеств как двоичную строку конечной длины, где i-й символ равен 0 или 1 в зависимости от того, содержит ли набор i-й элемент. Вот реализация в python

import math

class SetTree:
    def __init__(self, index, key, left, right):
        self.index = index
        self.key = key
        self.left = left
        self.right = right

cached_trees = { }
cached_index = 2

def get_index(T):
    if isinstance(T, SetTree):
        return T.index
    if T:
        return 1
    return 0        

def make_set_tree(key, left, right):
    global cached_trees, cached_index
    code = (key, get_index(left), get_index(right))
    if not code in cached_trees:
        cached_trees[code] = SetTree(cached_index, key, left, right)
        cached_index += 1
    return cached_trees[code]

def compute_freqs(X):
    freqs, total = {}, 0
    for S in X:
        for a in S:
            if a in freqs:
                freqs[a] += 1
            else:
                freqs[a] = 1
            total += 1
    U = [ (-f, a) for a,f in freqs.items() ]
    U.sort()
    return U

#Constructs the tree recursively
def build_tree_rec(X, U):
    if len(X) == 0:
        return False
    if len(U) == 0:
        return True

    key = U[0][1]

    left_elems = [ S for S in X if key in S]

    if len(left_elems) > 0:
        return make_set_tree(key,
            build_tree_rec(left_elems, U[1:]),
            build_tree_rec([ S for S in X if not key in S ], U[1:]))

    return build_tree_rec(X, U[1:])

#Build a search tree recursively
def build_tree(X):
    U = compute_freqs(X)
    return build_tree_rec(X, U)


#Query a set tree to find all subsets contained in a given set
def query_tree(T, S):
    if not isinstance(T, SetTree):
        return [ [] ] if T else []
    if T.key in S:
        return [ U + [ T.key ] for U in query_tree(T.left, S) ] + query_tree(T.right, S)
    return query_tree(T.right, S)

#Debugging function: Converts a tree to a tuple for printing
def tree_to_tuple(T):
    if isinstance(T, SetTree):
        return (T.key, tree_to_tuple(T.left), tree_to_tuple(T.right))
    return T

Теперь вот пример использования:

In [15]: search_tree = set_search.build_tree(set_family)

In [16]: set_search.tree_to_tuple(search_tree)
Out[16]: 
(2,
 (4, (5, True, True), (5, True, (3, True, False))),
 (4, (5, True, False), (1, True, False)))

In [17]: set_search.query_tree(search_tree, set([2,3,4,5]))
Out[17]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4]]

In [18]: set_search.query_tree(search_tree, set([1,2,3,4,5]))
Out[18]: [[5, 4, 2], [4, 2], [5, 2], [3, 2], [5, 4], [1]]

In [19]: set_search.query_tree(search_tree, set([2,4,5]))
Out[19]: [[5, 4, 2], [4, 2], [5, 2], [5, 4]]

In [20]: set_search.query_tree(search_tree, set([2,5]))
Out[20]: [[5, 2]]

In [21]: set_search.query_tree(search_tree, set([1]))
Out[21]: [[1]]

In [22]: set_search.query_tree(search_tree, set([15]))
Out[22]: []

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

EDIT: сразу после того, как я это сделал, я увидел ответ btilly, который приходит к более или менее такому же выводу о проблеме (по модулю некоторых технических ниппеков, которые я переместил в комментарии на его пост.)

ИЗМЕНИТЬ 2: Понял, что это действительно просто частный случай бинарной диаграммы решений. На самом деле не хватает энергии, чтобы исправить запись прямо сейчас, так что оставим ее как есть. Возможно, исправить это завтра. http://en.wikipedia.org/wiki/Binary_decision_diagram

Ответ 4

Это интересно. Мне нравится диаграммный подход Хассе, который предлагает PengOne, но я думаю, что вы можете построить диаграмму Хассе очень быстро, используя трюк простого числа. Допустим, что объединение всех множеств приводит к натуральным числам от 1 до N. Сопоставьте каждое из этих чисел с соответствующими штрихами, например:

PrimeMap [1] = 2;
PrimeMap [2] = 3;
PrimeMap [3] = 5;

Затем определите "оценку" для каждого набора, умножив каждое из простых чисел, соответствующих числу в наборе. Например, набор {1,2,3} имел бы счет 2 * 3 * 5 = 30. Теперь для того, чтобы множество A являлось собственным подмножеством другого набора B score (A), необходимо разделить оценку (B) (оценки для {1,2}, {2,3} и {1,3} - 6, 15 и 10, каждый из которых делит 30). Используйте этот счет, чтобы построить диаграмму Хассе.

Изменить: это похоже на одно из хороших теоретических решений. Наверное, не путь. Биты, предложенные yi_H, также хороши и не страдают от больших целых проблем.

Ответ 5

Посмотрите на эту библиотеку python, которая реализует диаграммы Хассе python-решетки] 1