File size: 3,434 Bytes
1cd137c
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
from __future__ import annotations

import hashlib
from collections.abc import Collection

from reference_db.phase_3.grouping.models import (
    GroupDecision,
    ResolutionResult,
    ResolvedGroup,
)


class UnionFind:
    def __init__(self, items: list[str]) -> None:
        self.parent = {item: item for item in items}
        self.rank = {item: 0 for item in items}

    def find(self, item: str) -> str:
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])
        return self.parent[item]

    def union(self, item_a: str, item_b: str) -> None:
        root_a = self.find(item_a)
        root_b = self.find(item_b)

        if root_a == root_b:
            return

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1


def generate_group_id(external_ids: tuple[str, ...]) -> str:
    identity = "|".join(sorted(external_ids))
    return hashlib.sha256(identity.encode("utf-8")).hexdigest()[:16]


def resolve_groups(
    external_ids: list[str],
    decisions: list[GroupDecision],
    isolated_ids: Collection[str] = (),
) -> ResolutionResult:
    """Resolve groups, keeping isolated ids as singleton groups.

    An isolated id is never unioned with another product, so each one
    forms its own single-member group. Used for taxonomy-AMBIGUOUS
    products, which must not be merged on similarity alone.
    """
    union_find = UnionFind(external_ids)
    isolated = {str(item) for item in isolated_ids}

    different_pairs: list[GroupDecision] = []
    review_queue: list[GroupDecision] = []

    for decision in decisions:
        if decision.decision == "SAME":
            if (
                decision.external_id_a in isolated
                or decision.external_id_b in isolated
            ):
                continue
            union_find.union(
                decision.external_id_a,
                decision.external_id_b,
            )
        elif decision.decision == "DIFFERENT":
            different_pairs.append(decision)
        elif decision.decision == "AMBIGUOUS":
            review_queue.append(decision)

    components: dict[str, list[str]] = {}

    for external_id in external_ids:
        root = union_find.find(external_id)
        components.setdefault(root, []).append(external_id)

    resolved_groups: list[ResolvedGroup] = []
    assignments: dict[str, str] = {}
    contradictions: list[GroupDecision] = []

    for members in components.values():
        member_ids = tuple(sorted(members))
        group_id = generate_group_id(member_ids)

        resolved_groups.append(
            ResolvedGroup(
                group_id=group_id,
                external_ids=member_ids,
            )
        )

        for external_id in member_ids:
            assignments[external_id] = group_id

    for decision in different_pairs:
        group_a = assignments[decision.external_id_a]
        group_b = assignments[decision.external_id_b]

        if group_a == group_b:
            contradictions.append(decision)

    resolved_groups.sort(key=lambda group: group.group_id)

    return ResolutionResult(
        groups=tuple(resolved_groups),
        assignments=assignments,
        review_queue=tuple(review_queue),
        contradictions=tuple(contradictions),
    )