Select Near-Duplicate Pairs

Task

Write select_near_duplicates(groups_by_document, threshold). The input is a dictionary whose values are sets of token-group tuples. Dictionary insertion order is the source document order. threshold is a number from 0 through 1.

Consider every unordered pair of distinct documents exactly once, with the earlier-inserted document first. Its similarity is

size of intersection / size of union

If both sets are empty, define similarity to be 1.0. Keep pairs whose similarity is at least threshold. Return a list of four-item tuples (doc_a, doc_b, similarity, shared_groups), where shared_groups is the set intersection. Sort the returned list by decreasing similarity; pairs tied at a similarity retain the order in which their document pair was generated.

Do not modify the input dictionary or any of its sets.

Example

The pair is reported once, not once in each direction. A threshold of zero keeps zero-similarity pairs too; a threshold of one keeps only exact matches (including two empty sets).

Your implementation

Edit solution.py and keep this function name and signature:

Use the exact tuple shape and a set for shared_groups. Return a new list and leave all input collections unchanged. Token-group tuples are hashable.