实体间关联关系发现：基于共享值的实体分组求解

给定如下数据集（Scala格式）：

List((X,Set(" 1", " 7")), (Z,Set(" 5")), (D,Set(" 2")), (E,Set(" 8")), ("F ",Set(" 5", " 9", " 108")), (G,Set(" 2", " 11")), (A,Set(" 7", " 5")), (M,Set(108)))

需按规则分组：若两个实体的集合存在共同元素则二者相关，关联关系可传递。最终将所有关联实体归为一组，输出类似((X,Z,A,F,M),(D,G),(E))的分组结果（组内、组间顺序无关）。

Scala 实现 #

核心思路是用**并查集(Union-Find)**处理传递性关联，先统一数据格式（解决空格、类型不一致问题），再通过元素映射完成实体合并：

import scala.collection.mutable

object EntityGrouping {
  def main(args: Array[String]): Unit = {
    // 原始数据集
    val rawData = List(
      ("X", Set(" 1", " 7")),
      ("Z", Set(" 5")),
      ("D", Set(" 2")),
      ("E", Set(" 8")),
      ("F ", Set(" 5", " 9", " 108")),
      ("G", Set(" 2", " 11")),
      ("A", Set(" 7", " 5")),
      ("M", Set(108))
    )

    // 数据预处理：实体名去空格，集合元素统一为去空格的字符串
    val cleanedData = rawData.map { case (entity, elements) =>
      val cleanEntity = entity.trim
      val cleanElements = elements.map(e => e.toString.trim)
      (cleanEntity, cleanElements)
    }

    // 构建元素到实体列表的映射：key=元素，value=关联实体集合
    val elementToEntities = mutable.HashMap[String, mutable.Set[String]]()
    cleanedData.foreach { case (entity, elements) =>
      elements.foreach { elem =>
        elementToEntities.getOrElseUpdate(elem, mutable.Set()) += entity
      }
    }

    // 并查集实现
    val parent = mutable.HashMap[String, String]()
    // 初始化：每个实体的父节点是自己
    cleanedData.foreach { case (entity, _) => parent(entity) = entity }

    // 查找根节点（带路径压缩）
    def find(entity: String): String = {
      if (parent(entity) != entity) {
        parent(entity) = find(parent(entity))
      }
      parent(entity)
    }

    // 合并两个实体的集合
    def union(a: String, b: String): Unit = {
      val rootA = find(a)
      val rootB = find(b)
      if (rootA != rootB) {
        parent(rootB) = rootA
      }
    }

    // 遍历每个元素对应的实体列表，合并所有关联实体
    elementToEntities.values.foreach { entities =>
      if (entities.size > 1) {
        val head = entities.head
        entities.tail.foreach(union(head, _))
      }
    }

    // 分组：按根节点聚合实体
    val groups = cleanedData.map(_._1).groupBy(find).values
    // 输出结果（转成Tuple格式，顺序无关）
    val result = groups.map(_.toList).toList
    println(result)
    // 输出示例：List(List(X, Z, A, F, M), List(D, G), List(E))
  }
}

Python 实现 #

同样基于并查集，步骤与Scala一致，语法更简洁：

def main():
    # 原始数据集
    raw_data = [
        ("X", {" 1", " 7"}),
        ("Z", {" 5"}),
        ("D", {" 2"}),
        ("E", {" 8"}),
        ("F ", {" 5", " 9", " 108"}),
        ("G", {" 2", " 11"}),
        ("A", {" 7", " 5"}),
        ("M", {108})
    ]

    # 数据预处理：统一格式
    cleaned_data = []
    for entity, elements in raw_data:
        clean_entity = entity.strip()
        clean_elements = {str(e).strip() for e in elements}
        cleaned_data.append((clean_entity, clean_elements))

    # 构建元素到实体的映射
    element_to_entities = {}
    for entity, elements in cleaned_data:
        for elem in elements:
            if elem not in element_to_entities:
                element_to_entities[elem] = set()
            element_to_entities[elem].add(entity)

    # 并查集初始化
    parent = {}
    for entity, _ in cleaned_data:
        parent[entity] = entity

    # 查找根节点（路径压缩）
    def find(entity):
        while parent[entity] != entity:
            parent[entity] = parent[parent[entity]]
            entity = parent[entity]
        return entity

    # 合并集合
    def union(a, b):
        root_a = find(a)
        root_b = find(b)
        if root_a != root_b:
            parent[root_b] = root_a

    # 合并所有关联实体
    for entities in element_to_entities.values():
        if len(entities) > 1:
            entities = list(entities)
            head = entities[0]
            for entity in entities[1:]:
                union(head, entity)

    # 分组
    groups = {}
    for entity, _ in cleaned_data:
        root = find(entity)
        if root not in groups:
            groups[root] = []
        groups[root].append(entity)

    # 输出结果
    result = tuple(tuple(group) for group in groups.values())
    print(result)
    # 输出示例：(('X', 'A', 'Z', 'F', 'M'), ('D', 'G'), ('E',))

if __name__ == "__main__":
    main()

伪代码 #

// 1. 数据预处理
FUNCTION preprocess(rawData):
    cleanedData = []
    FOR each (entity, elements) IN rawData:
        cleanEntity = trim(entity)
        cleanElements = { trim(str(elem)) FOR elem IN elements }
        ADD (cleanEntity, cleanElements) TO cleanedData
    RETURN cleanedData

// 2. 构建元素-实体映射
FUNCTION buildElementMap(cleanedData):
    elementMap = EMPTY MAP
    FOR each (entity, elements) IN cleanedData:
        FOR each elem IN elements:
            IF elem NOT IN elementMap:
                elementMap[elem] = EMPTY SET
            ADD entity TO elementMap[elem]
    RETURN elementMap

// 3. 并查集操作
INIT parent MAP: FOR each entity IN cleanedData, parent[entity] = entity

FUNCTION find(entity):
    IF parent[entity] != entity:
        parent[entity] = find(parent[entity])  // 路径压缩
    RETURN parent[entity]

FUNCTION union(a, b):
    rootA = find(a)
    rootB = find(b)
    IF rootA != rootB:
        parent[rootB] = rootA

// 4. 合并关联实体
elementMap = buildElementMap(cleanedData)
FOR each entities IN elementMap.values():
    IF size(entities) > 1:
        head = first element IN entities
        FOR each entity IN entities EXCEPT head:
            union(head, entity)

// 5. 生成分组
groups = EMPTY MAP
FOR each entity IN cleanedData:
    root = find(entity)
    IF root NOT IN groups:
        groups[root] = EMPTY LIST
    ADD entity TO groups[root]

// 输出分组结果
OUTPUT values of groups

内容的提问来源于stack exchange，提问作者soumya-kole