3

在我的 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 个对象进行了一些计时测试，每个对象大约有五个标签：

  • 俄佐立的代码：127ms
  • 布鲁斯代码：115ms
  • Pillmuncher的代码：137ms

Pillmuncher 的代码在我看来是最优雅的。

4

4 回答 4

1

好吧，不确定它是否更好，但我写这棵树很有趣。

它对节点使用字典（应该使用更好的东西，因为我使用不干净的标签“数据”）

根是树的根，通过解析初始数据来填充

关于复杂性，不清楚什么是 n ：

  • 如果您有很多项目 (x)，每个项目 (y) 的标签很少，那么您希望 x 具有良好的复杂性并且您不关心 y
  • 如果您有一些带有很多标签的项目，那么您想要相反

我想第一个解决方案很常见。

我没记错，我的解决方案在 xyln(y) 中运行（我需要对每个项目的标签进行排序）来创建树。

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

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'])
于 2013-07-18T12:18:56.317 回答
1

可能你可以使用二分图。让 O 和 T 形成一个二分图。O 是对象，T 是标签。一个对象和一个标签有边缘意味着，那个对象有那个标签。

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

现在输入是一些标签。检查他们的学位，找出哪个学位最小。

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

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

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

希望这可以帮助。

于 2013-07-18T13:21:54.793 回答
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'])
于 2013-07-18T11:51:40.140 回答
1

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))

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

[/编辑]

于 2013-07-18T16:31:02.347 回答