如何高效筛选与指定行共享至少一个标签的行？

问题描述 #

现有如下物品-标签数据：

需求：遍历每一行，筛选出与当前行共享至少一个标签的行。例如：

• 针对shirt行，需返回coat和shoes行
• 针对coat行，需返回shirt行
• 是否包含当前行本身不影响

当前标签以字符串存储，可更换为其他结构，求高效实现方案。

高效实现方案 #

第一步：优化数据结构（核心）

不要用字符串存储标签，换成集合存储每个物品的标签，同时建立标签到物品列表的反向索引字典。这是提升效率的关键，避免每次查找都遍历全表。

以Python为例，转换后的数据结构如下：

# 物品 -> 标签集合的映射
item_tags = {
    "shirt": {"tag", "tag1", "tag2", "tag3"},
    "coat": {"tag", "tag7", "tag8"},
    "shoes": {"tag1", "tag2", "tag5"},
    "jacket": {"tag4", "tag5"}
}

# 标签 -> 对应物品列表的反向索引
tag_to_items = {}
for item, tags in item_tags.items():
    for tag in tags:
        if tag not in tag_to_items:
            tag_to_items[tag] = []
        tag_to_items[tag].append(item)

第二步：实现快速查找

对任意目标物品，只需通过反向索引收集所有关联物品，再去重即可：

def get_related_items(target_item):
    target_tags = item_tags[target_item]
    related = set()
    # 批量收集所有关联物品
    for tag in target_tags:
        related.update(tag_to_items[tag])
    # 移除自身（可选，根据需求调整）
    related.discard(target_item)
    return related

# 测试验证
print(get_related_items("shirt"))  # 输出 {'coat', 'shoes'}
print(get_related_items("coat"))   # 输出 {'shirt'}
print(get_related_items("shoes"))  # 输出 {'shirt', 'jacket'}
print(get_related_items("jacket")) # 输出 {'shoes'}

效率说明

• 反向索引只需初始化一次，后续查找的时间复杂度为O(k)（k为目标物品的标签数量），而非遍历全表的O(n)
• 集合去重操作的效率远高于逐行判断，数据量越大优势越明显

兼容原始字符串格式的方案（不推荐） #

如果暂时无法修改存储结构，可先将字符串标签转为集合，再逐行判断交集，但这种方法效率较低，仅适合小数据量场景：

# 原始字符串格式的数据
raw_data = [
    ("shirt", "tag, tag1, tag2, tag3"),
    ("coat", "tag, tag7, tag8"),
    ("shoes", "tag1, tag2, tag5"),
    ("jacket", "tag4, tag5")
]

def get_related_raw(target_item):
    # 获取目标物品的标签集合
    target_tag_set = None
    for item, tags_str in raw_data:
        if item == target_item:
            target_tag_set = set(tags_str.split(", "))
            break
    if not target_tag_set:
        return []
    
    # 遍历全表筛选关联物品
    related = []
    for item, tags_str in raw_data:
        if item == target_item:
            continue
        current_tag_set = set(tags_str.split(", "))
        if current_tag_set & target_tag_set:
            related.append(item)
    return related

# 测试
print(get_related_raw("shirt"))  # 输出 ['coat', 'shoes']

内容的提问来源于stack exchange，提问作者thomascer