Hệ thống Đối soát Dấu vân tay Văn bản Bằng Thuật toán Winnowing

Mục tiêu kiến thức

• Hiểu và cài đặt giải thuật Tạo dấu vân tay văn bản (Document Fingerprinting) của Schleimer, Wilkerson và Aiken (Thuật toán Winnowing).
• Cài đặt thuật toán Băm cuốn Karp-Rabin (Rolling Hash) để tính toán mã băm cho chuỗi k-gram trong thời gian O(1) mỗi bước trượt.
• Áp dụng kỹ thuật Cửa sổ trượt (Sliding Window) để chọn mã băm đại diện (Robust Fingerprints) với quy tắc phá vỡ thế hòa (Tie-breaking rule) chuẩn xác.
• Đánh giá mức độ tương đồng giữa hai tài liệu thông qua chỉ số Jaccard Similarity trên tập dấu vân tay.

Mô tả bài toán

Hệ thống kiểm tra đạo văn và chống gian lận học thuật của AI Empire Academy cần đối soát mã nguồn và bài nộp của học viên. Nếu lưu trữ toàn bộ các đoạn văn bản hoặc mã băm của mọi k-gram, dung lượng cơ sở dữ liệu sẽ bùng nổ. Thuật toán Winnowing giải quyết bài toán này bằng cách chỉ giữ lại một tập con nhỏ các mã băm đại diện đảm bảo rằng: Mọi đoạn trùng lặp có độ dài tối thiểu (w + k - 1) ký tự đều chắc chắn bị phát hiện.

Hãy xây dựng lớp:

class DocumentFingerprinter:
    def __init__(self, k_gram: int = 5, window_size: int = 4, base: int = 257, prime: int = 1000003):
        ...
    def normalize(self, text: str) -> str:
        ...
    def compute_hashes(self, clean_text: str) -> list[int]:
        ...
    def fingerprint(self, text: str) -> set[int]:
        ...
    def similarity(self, text_a: str, text_b: str) -> float:
        ...

Quy trình thuật toán:

• Chuẩn hóa (normalize):
• Chuyển thành chữ thường (lower()).
• Loại bỏ toàn bộ ký tự không phải chữ cái và số (re.sub(r'[^a-z0-9]', '', text.lower())).
• Băm k-gram (compute_hashes):
• Với văn bản chuẩn hóa có độ dài L < k_gram, trả về danh sách rỗng [].
• Sử dụng đa thức băm modulo prime:

H(c₀ c₁ … c_k-1) = ( ∑_i=0^k-1 ord(c_i) × base^{k - 1 - i} ) mod prime

• Áp dụng kỹ thuật Rolling Hash để tính H_i+1 từ H_i trong O(1):

H_i+1 = ( (H_i - ord(c_i) × base^k-1) × base + ord(c_i+k) ) mod prime

• Đảm bảo kết quả modulo luôn không âm: hash = (hash % prime + prime) % prime.
• Tạo dấu vân tay Winnowing (fingerprint):
• Gọi H = [h₀, h₁, …, h_m-1] là danh sách mã băm thu được.
• Nếu m < window_size: chọn phần tử nhỏ nhất trong H (nếu có nhiều phần tử bằng nhau, chọn phần tử xuất hiện sau cùng bên phải), trả về tập hợp {min_val}.
• Với mỗi cửa sổ W liên tiếp [h_i, h_i+1, …, h_{i + window_size - 1}]:
• Tìm giá trị nhỏ nhất trong cửa sổ.
• Quy tắc phá vỡ thế hòa (Tie-breaking rule): Nếu trong cửa sổ hiện tại có nhiều vị trí cùng đạt giá trị nhỏ nhất, CHỌN VỊ TRÍ XA NHẤT VỀ PHÍA BÊN PHẢI (vị trí có chỉ số lớn nhất).
• Thêm giá trị mã băm tại vị trí được chọn vào tập hợp fingerprints: set[int].
• Trả về tập hợp set[int].
• Tính độ tương đồng (similarity):
• Lấy tập dấu vân tay S_A = fingerprint(text_a) và S_B = fingerprint(text_b).
• Tính độ tương đồng Jaccard: J(S_A, S_B) = |S_A ∩ S_B||S_A ∪ S_B|.
• Nếu cả hai tập đều rỗng, trả về 1.0. Nếu một tập rỗng, trả về 0.0.
• Làm tròn 4 chữ số thập phân (round(..., 4)).

Ràng buộc

• k_gram ≥ 2, window_size ≥ 1.
• Độ dài văn bản: 0 ≤ |T| ≤ 50,000.
• Phải đảm bảo thời gian chạy O(L) tuyến tính nhờ Rolling Hash.