CSD201 - Phần 8: Xử lý văn bản và nén dữ liệu

Ứng với CLO8, buổi 53-56, phần cuối của môn. Tương ứng Chương 13 của Goodrich ấn bản 6. Phần mở đầu nêu bối cảnh khối lượng văn bản số khổng lồ và các bài toán phát sinh từ đó. Phần so khớp mẫu trình bày thuật toán vét cạn với cách hoạt động và độ phức tạp trong trường hợp xấu nhất, rồi tới thuật toán Knuth-Morris-Pratt với ý tưởng cốt lõi là tận dụng thông tin đã so khớp được để không lùi con trỏ trên văn bản, cùng bảng tiền tố và cách xây dựng nó. Phần nén văn bản trình bày ba thuật toán: mã Huffman với cây mã tiền tố xây từ tần suất ký tự và các bước nén một tệp văn bản; thuật toán LZW dựa trên từ điển xây dựng động trong lúc mã hoá; và mã hoá độ dài loạt phù hợp với dữ liệu có nhiều ký tự lặp liên tiếp, kèm so sánh phạm vi áp dụng của từng thuật toán.