Tối ưu hóa thuật toán gộp BPE (Fast Linked-List / Priority Queue BPE)
Trong cài đặt ngây thơ của BPE:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: bpe-inference-tokenization-algorithm.
Nội dung đề bài
Mô tả bài toán
Trong cài đặt ngây thơ của BPE: Sau mỗi lần gộp, việc tạo lại mảng mới và quét lại từ đầu tốn thời gian O(L) cho mỗi phép gộp, dẫn tới tổng thời gian O(L2) với L là độ dài chuỗi. Thư viện siêu tốc tiktoken (OpenAI) và Hugging Face Tokenizers tối ưu hóa bài toán này.
Hãy viết hàm fast_bpe_merge(symbols: list[str], bpe_ranks: dict[tuple[str, str], int]) -> list[str]:
- Nhận danh sách các ký hiệu ban đầu
symbols. - Sử dụng cấu trúc danh sách liên kết (Double-Linked List) hoặc chỉ mục lân cận (
prevvànextpointers) để thực hiện gộp: - Khi một cặp tại vị trí i và j được gộp:
- Chỉ cập nhật liên kết của phần tử đứng trước i và phần tử đứng sau j.
- Chỉ cần kiểm tra lại rank của 2 cặp mới tạo thành tại ranh giới xung quanh nút vừa gộp.
- Trả về danh sách các subword sau khi không còn cặp nào có thể gộp được nữa.
Input
- Hàm
fast_bpe_merge(symbols,bpe_ranks): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Output
- Hàm
fast_bpe_merge: Trả về kết quả kiểulist[str]theo đúng đặc tả kỹ thuật và kích thước quy định.
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ả.
Ví dụ 1
Input
symbols = ['u', 'n', 'r', 'e', 'l', 'a', 't', 'e', 'd']
bpe_ranks = {('u', 'n'): 0, ('r', 'e'): 1, ('l', 'a'): 2, ('t', 'e'): 3, ('te', 'd'): 4, ('re', 'la'): 5}
merged = fast_bpe_merge(symbols, bpe_ranks)Output
['un', 'rela', 'ted']Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Ví dụ 2
Input
fast_bpe_merge([], {})Output
[]Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.