在我的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的代码最优雅。