شباهت سند با MinHash؛ شینگل، جایگشت و خطای امضای کوچک در پایتون

برابری دقیقِ دو متن با شباهتِ بخش‌های مشترک آن‌ها فرق دارد. اگر تنها آخرین واژهٔ یک راهنمای کوتاه عوض شود، هشِ محتوای کامل تغییر می‌کند، ولی بخش‌هایی از متن همچنان مشترک‌اند. این درس با شینگلِ دوواژه‌ای، جاکارد دقیق و یک امضای کوچکِ MinHash این تفاوت را آشکار می‌کند. همهٔ سندها ساختگی‌اند؛ هیچ فایل واقعی حذف، ادغام یا دوباره نمایه‌گذاری نمی‌شود.

۱. شینگلِ دوواژه‌ای را مجموعه بگیریم، نه شمارنده

سند اول چهار توکن موتور، حسگر، سیگنال و آزمون دارد؛ در کد با motor/sensor/signal/test آمده‌اند. سند دوم سه توکن اول را حفظ می‌کند و آخرین واژه را هشدار می‌گذارد. برای نمایش قراردادیِ هشدار از alarm استفاده می‌کنیم. این‌ها جملهٔ استخراج‌شده از دستگاه یا گزارشِ خطا نیستند.

پنجرهٔ دوواژه‌ای روی سند اول، سه جفتِ مجاور می‌سازد: موتور و حسگر، حسگر و سیگنال، سیگنال و آزمون. سند دوم دو جفت اول را دارد، اما جفت آخرش سیگنال و هشدار است. طبق تعریف شینگل در کتاب بازیابی اطلاعات Stanford، این جفت‌ها را مجموعه می‌گیریم؛ وقوعِ تکراری یک جفت، عضو تازه یا وزن بیشتر نمی‌سازد.

ورودی از ابتدا فهرست توکن است. جداسازی جمله، تغییر بزرگی حروف، نرمال‌سازی فارسی یا گسترش مترادف انجام نمی‌دهیم. دو سند دیگر، پایتون و کد، سپس رله و کنترل هستند تا جهان مشترک بزرگ‌تر از اجتماعِ دو سند اول باشد. نمایهٔ معکوس واژگانی مسئلهٔ عضویت واژه در سند را بررسی می‌کرد؛ اینجا همسایگیِ دو توکن وارد تعریف شباهت شده است.

۲. جهان مشترک و ترتیب جایگشت را ثابت نگه داریم

تمام شینگل‌های چهار سند را یکتا و مرتب می‌کنیم. شش شناسه، از صفر تا پنج، داریم: موتورـحسگر، پایتونـکد، رلهـکنترل، حسگرـسیگنال، سیگنالـهشدار و سیگنالـآزمون. در این نگاشت، سند اول مجموعهٔ شناسه‌های صفر، سه و پنج و سند دوم صفر، سه و چهار است. دو عضوِ مربوط به سندهای دیگر در هیچ‌کدام از این دو مجموعه نیستند.

هر جایگشت، ترتیبِ بازدیدِ همهٔ شش شناسه را مشخص می‌کند. برای ساخت یک مؤلفهٔ امضا، ترتیب را از ابتدا می‌خوانیم و نخستین شناسهٔ موجود در سند را برمی‌داریم. کد همین کار را با رتبهٔ جایگاه‌ها انجام می‌دهد. منظور از کمینه، نخستین عضو تحت آن ترتیب است؛ کوچک‌ترین عددِ شناسه بدون توجه به جایگشت نیست.

سه ترتیب را عمداً با دست انتخاب کرده‌ایم: [0,1,2,3,4,5]، [5,4,3,2,1,0] و [3,5,4,0,1,2]. این انتخاب‌ها نمونه‌برداری تصادفی معرفی نمی‌شوند. جهان، نگاشت شناسه و ترتیبِ مؤلفه‌ها باید برای هر دو سند یکسان باشد؛ کد، مقایسهٔ خانواده‌های متفاوت را با خطا متوقف می‌کند.

۳. سه امضای کوچک را با جاکارد دقیق مقایسه کنیم

اشتراکِ دو مجموعه دو عضو و اجتماعشان چهار عضو دارد؛ بنابراین جاکارد دقیق، دو تقسیم بر چهار، یعنی یک‌دوم است. این عدد فقط همپوشانی مجموعهٔ جفت‌ها را می‌سنجد. عوض شدن واژهٔ پایانی ممکن است از نظر معنای فنی بسیار مهم باشد؛ جاکارد، اهمیت تغییر یا درست‌بودن ادعای سند را تعیین نمی‌کند.

امضای سند اول در سه ترتیب، صفر، پنج و سه است؛ امضای سند دوم صفر، چهار و سه می‌شود. مؤلفهٔ اول و سوم برابرند، پس تخمین کوتاه دو‌سوم است. فقط جایگاه‌های متناظر را مقایسه می‌کنیم؛ تبدیل امضاها به مجموعه و گرفتنِ اشتراکِ مقادیر، تعریف این تخمین نیست و هویتِ جایگشت را از بین می‌برد.

مستندات اصلی datasketch نیز امضای MinHash را برای تخمین شباهت مجموعه‌ها معرفی می‌کند. ما کتابخانه را اجرا نکرده‌ایم و طرح‌های هش آن را بازنویسی نمی‌کنیم. این مثال، جهان متناهی با جایگشت‌های صریح دارد؛ برخوردِ هشِ ورودی، طرح فشرده‌سازی، نمایهٔ نامزدها و هزینهٔ مجموعه‌های بزرگ در آن آزمایش نشده‌اند.

۴. کد و همهٔ ترتیب‌های جهان کوچک را بررسی کنیم

فایل minhash_shingle_signatures.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. هر سند صفر تا شانزده توکن و هر توکن یک تا بیست‌وچهار حرف کوچک لاتین دارد. جهانِ آموزشی یک تا هشت جفتِ مرتب و یکتا می‌گیرد؛ خانوادهٔ امضا یک تا شانزده جایگشتِ متمایز و کامل می‌پذیرد.

"""Finite ideal MinHash permutations on original tiny token-pair sets."""
from dataclasses import dataclass
from fractions import Fraction
from itertools import permutations
import json
import platform
import re


def word(value):
    if type(value) is not str or re.fullmatch(r"[a-z]{1,24}", value) is None:
        raise ValueError("expected 1..24 lowercase ASCII letters")
    return value


def shingles(tokens):
    if type(tokens) not in (list, tuple) or not 0 <= len(tokens) <= 16:
        raise ValueError("expected at most 16 tokens")
    tokens = tuple(word(token) for token in tokens)
    return frozenset(zip(tokens, tokens[1:]))


@dataclass(frozen=True)
class PermutationFamily:
    universe: tuple
    orders: tuple


@dataclass(frozen=True)
class Signature:
    family: PermutationFamily
    minima: tuple | None


def make_family(universe, orders):
    if type(universe) not in (list, tuple) or not 1 <= len(universe) <= 8:
        raise ValueError("expected 1..8 universe shingles")
    checked = []
    for shingle in universe:
        if type(shingle) not in (list, tuple) or len(shingle) != 2:
            raise ValueError("expected a pair of words")
        checked.append(tuple(word(token) for token in shingle))
    universe = tuple(checked)
    if universe != tuple(sorted(set(universe))):
        raise ValueError("universe must be sorted and unique")
    if type(orders) not in (list, tuple) or not 1 <= len(orders) <= 16:
        raise ValueError("expected 1..16 permutation orders")
    checked_orders = []
    expected = set(range(len(universe)))
    for order in orders:
        if type(order) not in (list, tuple) or len(order) != len(universe):
            raise ValueError("order must cover the entire universe")
        if any(type(index) is not int for index in order) or set(order) != expected:
            raise ValueError("order must contain each actual integer ID once")
        checked_orders.append(tuple(order))
    if len(set(checked_orders)) != len(checked_orders):
        raise ValueError("repeated permutation order is not allowed")
    return PermutationFamily(universe, tuple(checked_orders))


def signature(family, tokens):
    # family must be the immutable output of make_family, not an untrusted object.
    if type(family) is not PermutationFamily:
        raise ValueError("expected a constructed permutation family")
    present = shingles(tokens)
    lookup = {shingle: index for index, shingle in enumerate(family.universe)}
    if not present.issubset(lookup):
        raise ValueError("document includes a shingle outside the fixed universe")
    if not present:
        return Signature(family, None)
    ids = {lookup[shingle] for shingle in present}
    minima = []
    for order in family.orders:
        ranks = {element: position for position, element in enumerate(order)}
        minima.append(min(ids, key=ranks.__getitem__))
    return Signature(family, tuple(minima))


def estimate(left, right):
    if type(left) is not Signature or type(right) is not Signature:
        raise ValueError("expected constructed signatures")
    if left.family != right.family:
        raise ValueError("signature families differ")
    if left.minima is None or right.minima is None:
        return None
    return Fraction(sum(a == b for a, b in zip(left.minima, right.minima)), len(left.minima))


def exact_jaccard(left_tokens, right_tokens):
    left, right = shingles(left_tokens), shingles(right_tokens)
    union = left | right
    return Fraction(len(left & right), len(union)) if union else None


def rejected(function, *args):
    try:
        function(*args)
    except ValueError:
        return True
    return False


def fraction_json(value):
    return None if value is None else {"numerator": value.numerator, "denominator": value.denominator}


def run_example():
    documents = [["motor", "sensor", "signal", "test"],
                 ["motor", "sensor", "signal", "alarm"],
                 ["python", "code"], ["relay", "control"]]
    universe = tuple(sorted(set().union(*(shingles(tokens) for tokens in documents))))
    orders = [(0, 1, 2, 3, 4, 5), (5, 4, 3, 2, 1, 0), (3, 5, 4, 0, 1, 2)]
    family = make_family(universe, orders)
    left, right = [signature(family, tokens) for tokens in documents[:2]]
    checks = {}
    checks["literal_adjacent_pair_sets_and_duplicate_occurrences"] = (
        shingles(documents[0]) == {("motor", "sensor"), ("sensor", "signal"), ("signal", "test")}
        and shingles(["a", "b", "a", "b"]) == {("a", "b"), ("b", "a")})
    checks["literal_shared_universe_and_ids"] = universe == (
        ("motor", "sensor"), ("python", "code"), ("relay", "control"),
        ("sensor", "signal"), ("signal", "alarm"), ("signal", "test"))
    checks["hand_exact_jaccard_two_shared_out_of_four"] = exact_jaccard(*documents[:2]) == Fraction(1, 2)
    checks["minimum_follows_order_not_numeric_id"] = left.minima == (0, 5, 3) and right.minima == (0, 4, 3)
    checks["hand_three_coordinate_estimate_is_two_thirds_not_exact"] = (
        estimate(left, right) == Fraction(2, 3) and estimate(left, right) != exact_jaccard(*documents[:2]))
    checks["identity_and_disjoint_shingle_cases"] = (
        estimate(left, signature(family, documents[0])) == 1
        and estimate(left, signature(family, documents[2])) == 0
        and exact_jaccard(documents[0], documents[2]) == 0)
    checks["empty_sets_have_explicit_no_signature_policy"] = (
        signature(family, []).minima is None and signature(family, ["motor"]).minima is None
        and estimate(signature(family, []), signature(family, [])) is None
        and estimate(left, signature(family, [])) is None
        and exact_jaccard([], []) is None and exact_jaccard(documents[0], []) == 0)
    checks["outside_universe_shingle_is_rejected"] = rejected(signature, family, ["new", "pair"])
    changed_order = make_family(universe, list(reversed(orders)))
    changed_universe = make_family(universe[:-1], [(0, 1, 2, 3, 4)])
    checks["comparison_rejects_order_or_universe_mismatch"] = (
        rejected(estimate, left, signature(changed_order, documents[0]))
        and rejected(estimate, right, signature(changed_universe, documents[1])))
    checks["invalid_tokens_types_and_size_rejected"] = all(
        rejected(shingles, value) for value in (None, "motor", [True], [1], [""], ["Motor"],
                                               ["two words"], ["a" * 25], ["motor"] * 17))
    checks["universe_shape_order_duplicates_and_bounds_rejected"] = all(
        rejected(make_family, value, [(0,)]) for value in
        ([], ["motor"], [("a",)], [("a", True)], [("a", "b"), ("a", "b")],
         list(reversed(universe)), [("a", chr(97 + i)) for i in range(9)]))
    checks["permutation_shapes_types_duplicate_and_range_rejected"] = all(
        rejected(make_family, universe, value) for value in
        ([], [tuple(range(5))], [(0, 1, 2, 3, 4, 4)], [(False, 1, 2, 3, 4, 5)],
         [(0.0, 1, 2, 3, 4, 5)], [(0, 1, 2, 3, 4, 6)], [orders[0], orders[0]],
         [tuple(p) for p in list(permutations(range(6)))[:17]]))
    mutable_universe = [list(pair) for pair in universe]
    mutable_orders = [list(order) for order in orders]
    detached = make_family(mutable_universe, mutable_orders)
    mutable_universe[0][0] = "changed"
    mutable_orders[0].reverse()
    checks["immutable_family_detaches_from_mutable_constructor_inputs"] = detached == family
    before = repr(documents)
    signature(family, documents[0])
    checks["signature_does_not_modify_document_and_estimate_is_symmetric"] = (
        repr(documents) == before and estimate(left, right) == estimate(right, left))
    # Independent theorem reference: the first member of the union lies in the intersection.
    # It does not construct a Signature, rank lookup or call estimate for its expected value.
    a_ids, b_ids = {0, 3, 5}, {0, 3, 4}
    union, common = a_ids | b_ids, a_ids & b_ids
    matches = 0
    expected_matches = 0
    cases = 0
    oracle_ok = True
    for order in permutations(range(6)):
        first_union = next(element for element in order if element in union)
        expected = first_union in common
        one = make_family(universe, [order])
        actual = estimate(signature(one, documents[0]), signature(one, documents[1])) == 1
        matches += int(actual)
        expected_matches += int(expected)
        oracle_ok &= actual == expected
        cases += 1
    checks["all_720_uniform_orders_match_independent_first_union_oracle_one_group"] = bool(
        oracle_ok and cases == 720 and matches == expected_matches == 360
        and Fraction(matches, cases) == Fraction(len(common), len(union)) == Fraction(1, 2))
    # Reordering both signatures' coordinates together preserves the estimate.
    checks["common_coordinate_reordering_preserves_estimate"] = estimate(
        signature(changed_order, documents[0]), signature(changed_order, documents[1])) == Fraction(2, 3)
    assert all(type(value) is bool and value for value in checks.values()), checks
    return dict(python=platform.python_version(), dependencies={"standard_library_only": True,
                "datasketch_executed": False}, documents=documents,
                universe=[list(pair) for pair in universe], explicit_orders=[list(order) for order in orders],
                signatures={"first": list(left.minima), "second": list(right.minima)},
                exact_jaccard=fraction_json(exact_jaccard(*documents[:2])),
                selected_three_order_estimate=fraction_json(estimate(left, right)),
                exhaustive_oracle={"orders": cases, "matching_minima": matches,
                                   "fraction": fraction_json(Fraction(matches, cases))}, checks=checks,
                limitations=["Three orders are selected by hand, not random samples or a confidence guarantee.",
                             "Finite ideal permutations, not datasketch hashes, LSH or a scalable production implementation.",
                             "Lexical shingle overlap does not prove semantic equivalence, truth or permission to delete."])


if __name__ == "__main__":
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

شناسهٔ هر جایگشت باید عدد صحیح واقعی باشد؛ بولی و شناور پذیرفته نمی‌شوند. شناسهٔ تکراری، عضوِ جاافتاده، ترتیبِ تکراری یا شینگلِ خارج از جهان رد می‌شود. سازنده، نسخه‌ای از تاپل‌های تغییرناپذیر نگه می‌دارد؛ تغییر فهرست‌های ورودی، خانوادهٔ ساخته‌شده را عوض نمی‌کند. توابع، خروجیِ سازندهٔ خودمان را می‌گیرند، نه شیء سریال‌شدهٔ ناشناخته.

برای جهان شش‌عضوی، تمام ۷۲۰ ترتیب را جدا بررسی کرده‌ایم. مرجع مستقل از امضای تولیدشده استفاده نمی‌کند: در هر ترتیب، نخستین عضوِ اجتماعِ دو مجموعه را پیدا می‌کند و می‌پرسد آیا عضو اشتراک هم هست. دقیقاً ۳۶۰ ترتیب پاسخ مثبت دارند. احتمالِ برابری کمینه‌ها زیر انتخاب یکنواخت از همهٔ این ترتیب‌ها، یک‌دوم می‌شود.

{
  "python": "3.14.5",
  "dependencies": {
    "standard_library_only": true,
    "datasketch_executed": false
  },
  "documents": [
    [
      "motor",
      "sensor",
      "signal",
      "test"
    ],
    [
      "motor",
      "sensor",
      "signal",
      "alarm"
    ],
    [
      "python",
      "code"
    ],
    [
      "relay",
      "control"
    ]
  ],
  "universe": [
    [
      "motor",
      "sensor"
    ],
    [
      "python",
      "code"
    ],
    [
      "relay",
      "control"
    ],
    [
      "sensor",
      "signal"
    ],
    [
      "signal",
      "alarm"
    ],
    [
      "signal",
      "test"
    ]
  ],
  "explicit_orders": [
    [
      0,
      1,
      2,
      3,
      4,
      5
    ],
    [
      5,
      4,
      3,
      2,
      1,
      0
    ],
    [
      3,
      5,
      4,
      0,
      1,
      2
    ]
  ],
  "signatures": {
    "first": [
      0,
      5,
      3
    ],
    "second": [
      0,
      4,
      3
    ]
  },
  "exact_jaccard": {
    "numerator": 1,
    "denominator": 2
  },
  "selected_three_order_estimate": {
    "numerator": 2,
    "denominator": 3
  },
  "exhaustive_oracle": {
    "orders": 720,
    "matching_minima": 360,
    "fraction": {
      "numerator": 1,
      "denominator": 2
    }
  },
  "checks": {
    "literal_adjacent_pair_sets_and_duplicate_occurrences": true,
    "literal_shared_universe_and_ids": true,
    "hand_exact_jaccard_two_shared_out_of_four": true,
    "minimum_follows_order_not_numeric_id": true,
    "hand_three_coordinate_estimate_is_two_thirds_not_exact": true,
    "identity_and_disjoint_shingle_cases": true,
    "empty_sets_have_explicit_no_signature_policy": true,
    "outside_universe_shingle_is_rejected": true,
    "comparison_rejects_order_or_universe_mismatch": true,
    "invalid_tokens_types_and_size_rejected": true,
    "universe_shape_order_duplicates_and_bounds_rejected": true,
    "permutation_shapes_types_duplicate_and_range_rejected": true,
    "immutable_family_detaches_from_mutable_constructor_inputs": true,
    "signature_does_not_modify_document_and_estimate_is_symmetric": true,
    "all_720_uniform_orders_match_independent_first_union_oracle_one_group": true,
    "common_coordinate_reordering_preserves_estimate": true
  },
  "limitations": [
    "Three orders are selected by hand, not random samples or a confidence guarantee.",
    "Finite ideal permutations, not datasketch hashes, LSH or a scalable production implementation.",
    "Lexical shingle overlap does not prove semantic equivalence, truth or permission to delete."
  ]
}

این شمارش، یک گروه مرجع در میان شانزده گروه اجرایی است؛ ۷۲۰ گروه مستقل ادعا نشده است. پاسخ دستی، ترتیبِ غیرعددی، سند یکسان، سندهای جدا، جهان ناسازگار و تغییر ترتیب مشترکِ مؤلفه‌ها نیز بررسی می‌شوند. قضیهٔ منبع، جایگشت تصادفیِ یکنواخت را فرض می‌کند؛ سه ترتیبِ دست‌چین‌شدهٔ ما چنین فرضی را تأمین نمی‌کنند.

۵. نامزد شباهت را سند قابل‌حذف ننامیم

سندِ کمتر از دو توکن، شینگل ندارد و امضای آن تهی است. در تخمین ما، اگر یکی از امضاها تهی باشد، نتیجه تهی می‌ماند؛ صفرِ سنجیده‌شده نمی‌نویسیم. در حساب دقیقِ مجموعه‌ها، تهی در برابر غیرتهی جاکارد صفر دارد، ولی برای دو مجموعهٔ تهی، اجتماع هم تهی است و نسبت را تعریف‌نشده نگه می‌داریم.

تشخیص برابری دقیق با هش و مقایسهٔ بایت تعریف دیگری داشت. تغییر آزمون به هشدار در قرارداد آن درس، متن را متفاوت می‌کند؛ نزدیک بودنِ شینگل‌ها آن تصمیم را نقض نمی‌کند. اینجا فقط نامزدِ بررسیِ همپوشانی داریم. منشأ، نسخه، مجوز، معنای تغییر و سیاست نگهداری باید مستقل باقی بمانند.

بزرگ‌تر شدن امضا لزوماً هر تخمینِ خاصِ دست‌نویس را به مقدار دقیق نزدیک‌تر نمی‌کند. در این درس نه خطای آماریِ محصول برآورد شده و نه سند واقعی حذف شده است. منابع در ۲۵ مهر ۱۴۰۵ خوانده شدند؛ کتاب متعلق به ۲۰۰۸ و تولید صفحه‌اش ۲۰۰۹ است. نسخهٔ نمایش‌داده‌شدهٔ مستندات datasketch برابر 2.0.0 است؛ تاریخ انتشار همان صفحه معلوم نیست و آموزش، خبر تازه نیست.

پرسش اول: چرا جاکارد یک‌دوم است؟ پاسخ: دو جفت مشترک و چهار جفت در اجتماع داریم؛ دو شینگلِ سندهای دیگر وارد مخرجِ این مقایسهٔ دوتایی نمی‌شوند.

پرسش دوم: چرا تخمین دو‌سوم شد؟ پاسخ: دو جایگاه از سه جایگاه امضا برابرند؛ این سه ترتیبِ منتخب الزاماً نسبت دقیق تمام ترتیب‌ها را بازنمایی نمی‌کنند.

پرسش سوم: تکرار یک جفت در متن چه می‌کند؟ پاسخ: اگر جفت تازه‌ای نسازد، مجموعهٔ شینگل و امضا تغییر نمی‌کنند؛ فراوانی جزو تعریف شباهت ما نیست.

پرسش چهارم: آیا شباهت بالا اجازهٔ حذف می‌دهد؟ پاسخ: خیر؛ همپوشانی واژگانی، برابری فنی یا بی‌نیازی از منشأ را ثابت نمی‌کند. برنامه صرفاً عدد و امضا می‌سازد و هیچ عملیات نگهداری انجام نمی‌دهد.

منابع و مطالعهٔ بیشتر

• Stanford؛ شینگل، جاکارد و قضیهٔ کمینهٔ جایگشت
• datasketch؛ امضای MinHash و مقایسهٔ مؤلفه‌های متناظر

بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.