Hàm mất mát và Phân rã Viterbi trong Mô hình Unigram (SentencePiece Unigram LM)

Mô tả bài toán

Trong khi BPE và WordPiece sử dụng các quy tắc ghép/tách có tính heuristic cứng, Unigram Language Model (Kudo, 2018 - cốt lõi của Google SentencePiece) xem việc phân đoạn từ như một bài toán tối ưu hóa xác suất:

Giả sử từ điển subword cung cấp log-xác suất log P(s) cho mỗi chuỗi con s. Một từ W có thể được phân đoạn theo nhiều cách khác nhau x = (s₁, s₂, …, s_m). Tổng log-xác suất của một cách phân đoạn: log P(x) = ∑_k=1^m log P(s_k)

Hãy viết hàm unigram_viterbi_segmentation(word: str, subword_log_probs: dict[str, float]) -> tuple[list[str] | None, float]:

• Sử dụng quy hoạch động (thuật toán Viterbi) để tìm cách phân đoạn từ W thành các subword trong subword_log_probs sao cho tổng log-xác suất đạt giá trị lớn nhất.
• Trả về tuple (best_segmentation, best_log_prob):
• best_segmentation: danh sách các subword tối ưu list[str]. Nếu không tồn tại bất kỳ cách phân đoạn hợp lệ nào, trả về (None, -float('inf')).
• best_log_prob: tổng log-xác suất tương ứng (kiểu float).

Ràng buộc

• Thời gian chạy tối đa: 6000ms.
• Giới hạn bộ nhớ: 512MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.