10.2 抄襲偵測與指紋比對#

import re
from collections import defaultdict

def toks_of(text):
    """中文切成單字、英文切成詞（無分詞器的通用做法）"""
    toks = []
    for run in re.findall(r"[\u4e00-\u9fff]+|[A-Za-z0-9]+", text.lower()):
        toks.extend(run if "\u4e00" <= run[0] <= "\u9fff" else [run])
    return toks

def shingles(text, k=5):
    toks = toks_of(text)
    return {" ".join(toks[i:i + k]) for i in range(len(toks) - k + 1)}

def jaccard(a, b):
    return len(a & b) / len(a | b) if a | b else 0.0

FINGER = defaultdict(list)          # 指紋倒排：hash -> 文件
DOC_FP = {}                         # 文件 -> 指紋集

def add_doc(doc_id, text):
    fps = {hash(s) for s in shingles(text)}
    DOC_FP[doc_id] = fps
    for f in fps:
        FINGER[f].append(doc_id)

def candidates(threshold=0.1):
    pair_count = defaultdict(int)   # 粗篩：只數共同指紋
    for f, docs in FINGER.items():
        if len(docs) > 20:          # 超高頻指紋（樣板句）略過
            continue
        for i in range(len(docs)):
            for j in range(i + 1, len(docs)):
                pair_count[tuple(sorted((docs[i], docs[j])))] += 1
    out = []
    for (d1, d2), c in pair_count.items():
        j = c / (len(DOC_FP[d1]) + len(DOC_FP[d2]) - c)
        if j >= threshold:
            out.append((d1, d2, round(j, 3)))
    return sorted(out, key=lambda x: -x[2])

docs = {
    "論文A": "本研究提出一個新的演算法用於處理大規模文字資料，實驗結果顯示方法有效。",
    "論文B": "本研究提出一個新的演算法用於處理大規模文字資料，我們的實驗證明性能優異。",
    "論文C": "深度學習在自然語言處理的應用已經非常廣泛，改變了許多傳統方法。",
}
for d, t in docs.items():
    add_doc(d, t)
print("可疑對（Jaccard）:", candidates(0.2))

# 精查：對候選對找雷同片段（直接用共同 shingle 合併）
def common_spans(d1, d2, k=5):
    toks1, toks2 = toks_of(docs[d1]), toks_of(docs[d2])
    s2 = {" ".join(toks2[i:i + k]) for i in range(len(toks2) - k + 1)}
    spans, cur = [], []
    for i in range(len(toks1) - k + 1):
        sh = " ".join(toks1[i:i + k])
        if sh in s2:
            cur.append(i)
        elif cur:
            spans.append((cur[0], cur[-1] + k)); cur = []
    if cur: spans.append((cur[0], cur[-1] + k))
    return ["".join(toks1[a:b]) for a, b in spans]

print("A 與 B 的雷同片段:", common_spans("論文A", "論文B"))