quick find all sets that are subset

Question

I have big dictionary with frozenset keys. I need to find all keys which are subset of given one. I see obvious way to do it:

dictionary = {
    frozenset([1]): 1,
    frozenset([2]): 2,
    frozenset([3]): 3,
    frozenset([3, 4]): 34
}
biglist= [3, 4, 5]
results = {k: v for k, v in dictionary.items() if k.issubset(biglist)}
assert results == {frozenset([3]): 3, frozenset([3, 4]): 34}

But it is very slow for millions keys. Question is: is there any structure for fast searches of this type?

UPD: Basically, I don't want to iterate over all keys executing issubset on each one. Instead I can generate all posible sets from biglist and check if it in dictionary:

results = {}
maxkey = max(dictionary, key=len)
maxlen = len(dictionary[maxkey])
for lenght in range(1, maxlen):
    for subset in itertools.combinations(biglist, lenght):
        key = frozenset(subset)
        if key in dictionary:
            results[key] = dictionary[key]

But this method is also very expensive for long biglist.

Answer 1

Depending on the size of your dictionary, and the length of your key, neither checking all the keys in the dict nor enumerating all the subsets and checking those is a good solution. Instead, you could restructure your "flat" dictionary to something like a Trie, or Prefix Tree. Here, each element in the set will point to another branch of the tree and/or an actual value:

dictionary = {
    frozenset([1]): 1,
    frozenset([2]): 2,
    frozenset([3]): 3,
    frozenset([3, 4]): 34
}

def totree(d):
    tree = {}
    for key in d:
        t = tree
        for x in sorted(key):
            t = t.setdefault(x, {})
        t["value"] = d[key]
    return tree

tree = totree(dictionary)
# {1: {'value': 1}, 2: {'value': 2}, 3: {'value': 3, 4: {'value': 34}}}

Now, you can recursively check those trees and yield each key that has a value. Other than enumerating all the subsets, this will only expand those branches where all the elements so far are in the tree.

def check_subsets(tree, key, prefix=[]):
    if "value" in tree:
        yield prefix, tree["value"]
    for i, x in enumerate(key):
        if x in tree:
            yield from check_subsets(tree[x], key[i+1:], prefix+[x])

biglist= [3, 4, 5]
res = list(check_subsets(tree, sorted(biglist)))
# [([3], 3), ([3, 4], 34)]

Note that it's important that both the keys in the tree and the key for lookup are added/checked in sorted order, otherwise relevant subtrees could be missed.

Addendum 1: This should be clear, but just to make sure: Of course this approach will not help if you construct the tree anew for each lookup, otherwise you can just as well do a linear scan of all the keys. Instead, you'd have to create the tree once, and then reuse it for multiple lookups, and possibly update it with new elements added to the set.

Addendum 2: Instead of "value", you can of course use any key for the actual value at that node in the prefix tree. You could use None, or a very long string or large random number guaranteed not to be an element in any of your key-sets. You could, with a few adaptions to the totree and check_subtree functions, also define a custom Tree class...

class Tree:
    def __init__(self, value=None, children=None):
        self.value = value
        self.children = children or {}
    def __repr__(self):
        return "Tree(%r, %r)" % (self.value, self.children)

... but IMHO just using nested dictionaries with some special value keys is simpler.

Answer 2

This answer is loosely based on the idea of prefix trees but it comes at the problem from a slightly different tact. Basically we want to figure out how we can avoid touching the entire search space when we enumerate all subsets by using some kind of early stoping.

If we arrange our data into a "SubsetTree" such that all the children of a node are supersets of that node, we can stop exploring tree whenever we reach a node that isn't a subset of our current query because we know all of it's children will also not be subsets. When we build the tree, we want to prefer long parents over short parents because that'll increase the amount of early stopping in our search.

If you put all this together it looks something like this:

class SubsetTree:
    def __init__(self, key):
        self.key = key
        self.children = []

    def longestSubset(self, query):
        if not self.key.issubset(query):
            return None
        more = (x.longestSubset(query) for x in self.children)
        more = filter(lambda i: i is not None, more)
        return max(more, key=lambda x: len(x.key), default=self)

    def allSubsets(self, query):
        if not self.key.issubset(query):
            return
        if len(self.key) > 0:
            yield self.key
        for c in self.children:
            yield from c.allSubsets(query)


def buildSubtree(sets):
    sets = sorted(sets, key=lambda x: len(x))
    tree = SubsetTree(frozenset())
    for s in sets:
        node = SubsetTree(s)
        tree.longestSubset(s).children.append(node)
    return tree

dictionary = {
    frozenset([1]): 1,
    frozenset([2]): 2,
    frozenset([3]): 3,
    frozenset([3, 4]): 34
}
biglist= [3, 4, 5]

subsetTree = buildSubtree(dictionary.keys())
allSubsets = subsetTree.allSubsets(set(biglist))
results = {k: dictionary[k] for k in allSubsets}
assert results == {frozenset([3]): 3, frozenset([3, 4]): 34}

Answer 3

How about encoding both the frozenset keys and the given set into binary code?

And then you can bit-and the codes of the frozenset keys and the given set, if this result is equal to the frozenset keys' binary code, then the key is the subset of the given set.

This way precomputed the given set, I think it will make it faster.

---

In this case:

dictionary = {
    frozenset([1]): 1, # a
    frozenset([2]): 2, # b
    frozenset([3]): 3, # c
    frozenset([3, 4]): 34 # d
}
biglist= [3, 4, 5] # z

a: 10000
b: 01000
c: 00100
d: 00110
z: 00111

a & z = 00000 != a = 10000, no
b & z = 00000 != b = 01000, no
c & z = 00100 == c = 00100, yes
d & z = 00110 == d = 00110, yes

Answer 4

Being a bit generic here I think you can use a data structure called Bloom Filter to quickly discard what is definitely not in the set. Later you can do a simple scan with the possible candidates, hopefully, this last step is just a small fraction of your set.

Here is a Python implementation for the bloom filter: https://github.com/axiak/pybloomfiltermmap

Quoting their example:

>>> fruit = pybloomfilter.BloomFilter(100000, 0.1, '/tmp/words.bloom')
>>> fruit.update(('apple', 'pear', 'orange', 'apple'))
>>> len(fruit)
3
>>> 'mike' in fruit
False
>>> 'apple' in fruit
True