基于Python实现通过直接/间接关联生成数据唯一标识方案

This problem is about identifying connected components in a bipartite graph where nodes represent products and references. Two products belong to the same component if they share a direct reference, or are linked through a chain of shared references (indirect connection). Each component needs a unique identifier. Key constraints:

• Scale: Millions of rows demand efficient, near-linear time operations.
• Iterative updates: New associations must trigger incremental processing without re-computing the entire dataset from scratch.

The optimal data structure for this task is the Union-Find (Disjoint Set Union, DSU) structure, optimized with two critical enhancements:

• Path Compression: Flattens the tree structure during find operations to speed up future queries.
• Union by Rank/Size: Attaches smaller trees to larger ones to keep the tree depth minimal.
  These optimizations bring each find and union operation to nearly constant time (amortized O(α(n)), where α is the inverse Ackermann function—effectively constant for practical dataset sizes).

For iterative updates, maintain two auxiliary maps:

1. product_to_root: Maps each product to its component root.
2. ref_to_root: Maps each reference to the root of the component it belongs to.
   When new data arrives:

• If the reference exists in ref_to_root, union the product with the root from the map.
• If the product exists in product_to_root, update ref_to_root to point to the product's root if the reference wasn't mapped before.
• If neither exists, initialize the product as its own root and map the reference to this root.

Python Implementation (DSU with Iterative Support) #

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        # Union by rank
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 1

# Initialize core structures
uf = UnionFind()
ref_to_root = {}
product_to_key = {}

def process_entry(product, ref):
    uf.add(product)
    product_root = uf.find(product)
    
    if ref in ref_to_root:
        ref_root = ref_to_root[ref]
        uf.union(product_root, ref_root)
        new_root = uf.find(product)
        product_to_key[product] = new_root
        ref_to_root[ref] = new_root
    else:
        ref_to_root[ref] = product_root
        product_to_key[product] = product_root

# Process sample data
sample_data = [
    ("A", "1"), ("A", "2"), ("A", "3"), ("A", "a"), ("A", "b"), ("A", "c"),
    ("B", "1"), ("B", "4"), ("B", "5"), ("B", "x"), ("B", "y"), ("B", "z"),
    ("C", "6"), ("C", "7"), ("C", "8"), ("C", "x"), ("C", "f"), ("C", "h"),
    ("D", "12"), ("D", "13"), ("D", "14"), ("D", "15"), ("D", "16"), ("D", "17"), ("D", "18"),
    ("F", "13"), ("F", "AB"), ("F", "FF"), ("F", "NB"), ("F", "45"), ("F", "63"), ("F", "100"), ("F", "98"), ("F", "FGA"), ("F", "CA")
]

for product, ref in sample_data:
    process_entry(product, ref)

# Assign human-readable unique keys
root_to_human_key = {root: f"A{i+1}" for i, root in enumerate(set(uf.find(p) for p in product_to_key))}
final_results = [(p, ref, root_to_human_key[uf.find(p)]) for p, ref in sample_data]

# Print sample output
for row in final_results[:10]:
    print(row)

Libraries for Large-Scale Data #

• PySpark: For distributed processing of millions of rows. Use RDD or DataFrame operations to implement DSU, leveraging Spark's distributed shuffle capabilities.
• Pandas: For in-memory processing if the dataset fits into RAM. Use groupby on references to collect associated products, then apply union operations.
• NetworkX: Suitable for small to medium datasets, but not ideal for millions of rows due to higher overhead.

1. Initialization:

   • Create a DSU instance to manage product components.
   • Initialize ref_to_root to track reference-component mappings.
   • Initialize product_to_key to store the final unique key for each product.

2. Batch Processing:

   • For each (product, reference) pair:
     a. Add the product to DSU if it doesn't exist.
     b. If the reference is already mapped to a root, union the product's root with the reference's root.
     c. If the reference is new, map it to the product's current root.

3. Iterative Update Handling:

   • When new entries arrive, repeat step 2 for each new pair. The DSU structure automatically merges existing components as new connections are discovered.

4. Key Assignment:

   • After processing, map each unique root in DSU to a human-readable key (e.g., A1, A2) and assign it to all products in the component.

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