Python：数据结构用于索引集合以查找超集？

Question

在我的Python项目中，我有一组对象，每个对象都带有一组标签。我想生成所有包含标签子集的集合，将其映射到相关联的对象。这些子集应该不小于任何项目的完整标记集。例如，假设有这些带有标签的对象：

apple: fruit, green, nature
sometree: tree, green, wood, nature
banana: fruit, nature
someplant: green, wood, nature
otherplant: green, wood, nature

结果应该是：

(fruit, nature): banana, apple
(fruit, green, nature): apple
(green, wood, nature): sometree, someplant, otherplant
(green, wood, nature, tree): sometree

我不希望结果包含不存在于至少一个对象中的标签集。

为了实现这一点，我想出了一个 O(n²) 的算法，但想知道是否有更聪明的方法，例如某些基于树的索引或前缀树？我的对象不会太多，可能只有2000个。但是它应该很快。

我的当前解决方案遍历所有对象以创建将所有标签集映射到对象的字典。在第二次遍历中，我测试每个标签集是否是任何其他标签集的子集，如果是，则记住超集的对象。

更新：在上面的 O(n²) 中，n 指的是对象的数量。我的对象很多，每个对象大约有五个标签。

解决方案：感谢所有回复。最终我采用了 azorius 的方法，因为它既快速又可靠。这是一个完整的例子来列出所有组：

tagged = { 
    'apple': ['fruit', 'green', 'nature'],
    'sometree': ['tree', 'green', 'wood', 'nature'],
    'banana': ['fruit', 'nature'],
    'someplant': ['green', 'wood', 'nature'],
    'otherplant': ['green', 'wood', 'nature']
}   

tag_sets = set()
tags_to_objects = {}

for obj, tags in tagged.items():
    for tag in tags:
        try:
            tags_to_objects[tag].add(obj)
        except KeyError:
            tags_to_objects[tag] = set([obj])
    # Record all tag sets
    tag_set = frozenset(tags)
    tag_sets.add(tag_set)

groups = {}
for tag_set in tag_sets:
    objects = None
    for tag in tag_set:
        if objects:
            objects = objects.intersection(tags_to_objects[tag])
        else:
            objects = tags_to_objects[tag]
    groups[tag_set] = objects

for k,v in groups.items():
    print '(%s): %s' % (', '.join(k), ', '.join(v))

由于有多种解决方案，我对大约有五个标签的1035个对象进行了一些计时测试：

• azorius代码：127毫秒
• Bruce代码：115毫秒
• pillmuncher代码：137毫秒

在我看来，pillmuncher的代码最优雅。

- tomka

Answer 1

为什么不使用集合？根据http://wiki.python.org/moin/TimeComplexity，集合具有以下平均时间复杂度O(min(len(s), len(t))，也就是O(n)！

fruit = set(("apple", "banana"))
green = set(("apple", "sometree", "someplant", "otherplant"))
nature = set(("apple", "banana", "sometree", "someplant", "otherplant"))
tree = set (("sometree",))
wood = set (("sometree", "someplant", "otherplant"))

In [90]: fruit.intersection(nature)
Out[90]: set(['apple', 'banana'])

In [91]: fruit.intersection(nature).intersection(green)
Out[91]: set(['apple'])

In [92]: green.intersection(wood).intersection(nature)
Out[92]: set(['sometree', 'someplant', 'otherplant'])

In [93]: green.intersection(wood).intersection(nature).intersection(tree)
Out[93]: set(['sometree'])

回顾这段代码，使用reduce会更加优雅：

In [90]: reduce(set.intersection, [fruit, nature])
Out[90]: set(['apple', 'banana'])

In [91]: reduce(set.intersection, [fruit, nature, green])
Out[91]: set(['apple'])

In [92]: reduce(set.intersection, [green, wood, nature])
Out[92]: set(['sometree', 'someplant', 'otherplant'])

In [93]: reduce(set.intersection, [green, wood, nature, tree])
Out[93]: set(['sometree'])

- jcr

---

谢谢，我基于你的示例编写了代码。它不像Bruce的树那样快，但也没有慢多少。然而，它更加健壮和易读。 - tomka

Answer 2

嗯，不确定是否更好，但我写这个树的过程很有趣。

它使用节点字典（应该使用更好的东西，因为我使用了不干净的“data”标记）

根是树的根，通过解析初始数据进行填充。

关于复杂度，n不清楚：

• 如果您有大量项目（x），每个项目只有少量标签（y），则希望x的复杂度良好，而不关心y
• 如果您有少数项目但有大量标签，则想要相反的结果

我认为第一个解决方案更常见。

如果我没有错，我的解决方案在x.y.ln(y)（我需要按项目对标签进行排序）中运行以创建树。

显示树为y.y（但使用递归和临时列表，因此必须膨胀内存）。

d= {
"apple": ["fruit", "green", "nature"],
"sometree": ["tree", "green", "wood", "nature"],
"banana": ["fruit", "nature"],
"someplant": ["green", "wood", "nature"],
"otherplant": ["green", "wood", "nature"]
}


root=dict()
root['data']=[]
for k,v in d.iteritems():
   v.sort() # 
   r=root
   for c in v:
       try:
           r=r[c]
       except KeyError:
           r[c]=dict()
           r=r[c]
           r['data']=[]
   r['data']+=[k]

def dump(r,hist):
    result=r['data'][:]
    for x in r.keys():
        if x=='data':
            continue
        result+=dump(r[x],hist[:]+[x])
    if len(result)>0 and len(r['data'])>0:
        print (hist,result)
    return result

dump(root,[])

代码还远非完美（快速粗略模式），但看起来似乎可以工作：

$ c:\Python27\python.exe temp.py
(['green', 'nature', 'tree', 'wood'], ['sometree'])
(['green', 'nature', 'wood'], ['otherplant', 'someplant'])
(['fruit', 'green', 'nature'], ['apple'])
(['fruit', 'nature'], ['banana'])

- Bruce

---

感谢您提供这个简单而有创意的树形示例！这是发布的最快解决方案（请参见原始问题的编辑以获取时间）。然而，我发现它不如@azorius的代码可读性和健壮性。此外，它并没有完全产生我所寻找的结果标签集“['green'，'nature'，'wood']”也应该映射到“sometree”。 - tomka

很高兴能得到一些反馈，在这里并不常见 :-) 我输了，但我很开心。对我来说不清楚的是如何分组：你想要的是至少包含一个元素的所有集合。然而，（绿色，自然）（适用于绿色，自然+任何其他东西）不在你的列表中。一些微调应该可以解决它，但我同意我的代码不可读（单个字母变量没有帮助）。 - Bruce

Answer 3

Python标准库是您的朋友：

from collections import defaultdict
from itertools import combinations

tagged = {
    'apple': ['fruit', 'green', 'nature'],
    'sometree': ['tree', 'green', 'wood', 'nature'],
    'banana': ['fruit', 'nature'],
    'someplant': ['green', 'wood', 'nature'],
    'otherplant': ['green', 'wood', 'nature']
}

tag_sets = defaultdict(set)

for each, tags in tagged.items():
    tag_sets[frozenset(tags)].add(each)

for a, b in combinations(tag_sets, 2):
    if a < b:
        tag_sets[a].update(tag_sets[b])
    elif b < a:
        tag_sets[b].update(tag_sets[a])

for k, v in tag_sets.items():
    print '(%s): %s' % (', '.join(k), ', '.join(v))

结果：

(wood, green, nature): sometree, someplant, otherplant
(fruit, green, nature): apple
(fruit, nature): banana, apple
(green, wood, tree, nature): sometree

如何运作：首先，我们将映射 项 -> 标签集合 转换为 标签集合 -> 与该标签集合相关联的项集合。然后，我们遍历所有不同的标签集合的2-集合，用由对(a, b)表示的对表示，检查a或b是否是另一个的真子集。如果是，则将超集的映射项与适当子集的映射项连接起来。

[编辑]

这里有另一种解决方案：

from collections import defaultdict

tagged = {
    'apple': ['fruit', 'green', 'nature'],
    'sometree': ['tree', 'green', 'wood', 'nature'],
    'banana': ['fruit', 'nature'],
    'someplant': ['green', 'wood', 'nature'],
    'otherplant': ['green', 'wood', 'nature']
}

intersection = set(tagged).intersection
tag_sets = set()
items = defaultdict(set)

for item, tags in tagged.items():
    tag_sets.add(frozenset(tags))
    for tag in tags:
        items[tag].add(item)

for tag_set in tag_sets:
    result = intersection(*(items[tag] for tag in tag_set))
    print '(%s): %s' % (', '.join(tag_set), ', '.join(result))

我不知道它是否更快，因为我没有足够的数据进行有意义的比较。

- pillmuncher

---

感谢您提供这个示例和解释！代码简单而优雅，但在我的测试中，它相当缓慢（请参见原始问题的编辑以获取时间）。 - tomka

抱歉，我之前提供的您的解决方案的时间是错误的（是我的缩进错误）。实际上它并不那么慢。我已经在原问题中更正了时间。 - tomka

@tomka：感谢您的比较。请看我的新解决方案。 - pillmuncher

Answer 4

也许您可以使用二分图。 O 和 T 形成一个二分图。O 是对象，T 是标签。对象和标签之间的边表示该对象具有该标签。

您需要维护 T 的邻接列表和 O 的邻接矩阵以及标记顶点及其度数的哈希表。

现在输入一些标签。检查它们的度数并找出度数最小的标签。

现在从邻接列表中获取其邻居并迭代它。检查每个邻居是否在其他标签之间具有边缘。使用邻接矩阵进行检查。如果它与其他标签都有边缘，请存储它。否则，如果没有任何边缘与其他标签相连，则将其丢弃。

如果 t 是标签数量，o 是对象数量。建立邻接列表、矩阵和度数组将需要 O(t*o) 时间和 O(t*o) 空间。

之后，在每次 t' 标签查询时，将需要 O(t'*o) 时间。

希望这可以帮到您。

- rnbguy