Tổng quan về giáo trình

Tài liệu bài giảng Data Structures & Algorithms: Các thuật toán nén dữ liệu (Data Compression Algorithms) do giảng viên Nguyễn Tri Tuấn thuộc Khoa Công nghệ Thông tin, Đại học Quốc gia TP.HCM biên soạn (ấn bản Winter 2015). Trong chương trình đào tạo ngành Công nghệ Thông tin và Khoa học Máy tính, tài liệu này đóng vai trò là một chuyên đề chuyên sâu thuộc học phần Cấu trúc Dữ liệu và Giải thuật, kết nối kiến thức cấu trúc dữ liệu nền tảng với các kỹ thuật tối ưu hóa lưu trữ và truyền tải thông tin.

Mục tiêu học tập của tài liệu tập trung vào việc trang bị cho người học hệ thống khái niệm chuẩn xác về nén dữ liệu, phân biệt ranh giới giữa nén bảo toàn thông tin (Lossless Compression) và nén không bảo toàn thông tin (Lossy Compression). Người học được yêu cầu nắm vững cơ chế mã hóa (Encoding), giải mã (Decoding), tính toán định lượng hiệu suất nén $D(%)$, đồng thời cài đặt thành thạo các giải thuật nén kinh điển như Run-Length Encoding (RLE), Huffman tĩnh (Static Huffman) và nắm bắt nguyên lý của Huffman động (Adaptive Huffman).

Về mặt cấu trúc, tài liệu được tổ chức theo phương pháp đi từ khái niệm lý thuyết tổng quát, tiếp cận các giải thuật nén cơ bản trên chuỗi dữ liệu lặp, và phát triển dần lên các giải thuật mã hóa tối ưu trên cấu trúc cây nhị phân. Điểm đặc sắc của bài giảng là sự tích hợp chặt chẽ giữa lý thuyết thuật toán với định dạng tệp thực tế trong hệ điều hành (như tệp đồ họa .PCX và .BMP), kèm theo mã nguồn cài đặt mẫu bằng ngôn ngữ C/C++ ở mức thao tác nhị phân (bit/byte).

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Tài liệu được phân chia thành các chủ đề học thuật nối tiếp nhau theo tiến trình nâng cao:

  • Chủ đề 1: Tổng quan về nén dữ liệu (Data Compression Overview): Thiết lập hệ thống thuật ngữ chuyên ngành gồm Lossless Compression, Lossy Compression, Encoding, Decoding, Run / Run Length. Phân tích mục đích nén dữ liệu nhằm giảm kích thước khi lưu trữ, tối ưu hóa tốc độ truyền tải trên mạng và hỗ trợ nâng cao tính bảo mật. Phân loại hai hình thức nén:

    • Nén bảo toàn thông tin (Lossless): Không làm mất dữ liệu gốc, hiệu suất nén đạt từ 10% đến 60%, ứng dụng trong nén tập tin và sao lưu phục hồi (backup/restore) với các đại diện như RLE, Arithmetic, Huffman, LZ77, LZ78, LZW (tích hợp trong PKZip, WinZip, WinRar).
    • Nén không bảo toàn thông tin (Lossy): Dữ liệu nguyên thủy bị mất mát một phần, hiệu suất nén đạt từ 40% đến 90%, tiêu biểu như JPEG, MP3, MP4.
    • Công thức tính hiệu suất nén: $D (%) = \frac{N - M}{N} \times 100$, trong đó $N$ là kích thước dữ liệu gốc trước nén và $M$ là kích thước sau khi nén.

  • Chủ đề 2: Giải thuật nén RLE (Run-Length Encoding): Trình bày nguyên lý biểu diễn thông tin dư thừa dựa trên "đường chạy" (run) – tức dãy ký tự lặp lại liên tiếp dưới dạng bộ đôi <Số lần lặp><Ký tự>. Tài liệu phân tích hiện tượng "phản tác dụng" khi gặp các ký tự đơn lẻ ($X \to 1X$, làm tăng kích thước từ 1 byte lên 2 bytes) và đưa ra hai mô hình ứng dụng cụ thể:

    • RLE trong định dạng tệp .PCX: Cơ chế dùng 2 bit cao (11 tương ứng 0xC0) làm cờ hiệu nhận biết số lần lặp, 6 bit thấp còn lại biểu diễn chiều dài đường chạy ($n \le 63$). Xử lý trường hợp ký tự đơn có mã ASCII $< 192$ (lưu 1 byte) và $\ge 192$ (lưu 2 bytes).
    • RLE trong định dạng tệp .BMP: Chuẩn tệp Windows Bitmap phân chia dữ liệu thành hai dạng: Dạng 1 (Run lặp lại $> 1$) lưu dạng <Số lần lặp><Ký tự> và Dạng 2 (Dãy ký tự đơn lẻ không lặp) lưu dạng <ESCAPE 0x00><n><Dãy ký tự>.

  • Chủ đề 3: Giải thuật nén Huffman tĩnh (Static Huffman): Dựa trên công trình năm 1952 của David Huffman về mã hóa độ dài thay đổi (Variable Length Encoding). Thay vì cố định 8 bits/ký tự, các ký tự xuất hiện nhiều được gán mã bit ngắn, ký tự xuất hiện ít được gán mã bit dài.

    • Mô hình cây Huffman: Cây nhị phân gồm $2n - 1$ nút (với $n \le 256$, MAX_NODES = 511). Nút lá chứa ký tự và trọng số xuất hiện; nút cha chứa tổng trọng số của hai nút con. Nhánh trái tương ứng bit 0, nhánh phải tương ứng bit 1.
    • Thuật toán nén 5 bước: (1) Thống kê tần số ký tự; (2) Xây dựng cây Huffman nhị phân; (3) Phát sinh bảng mã bit duyệt từ gốc đến lá; (4) Thay thế chuỗi gốc bằng chuỗi bit; (5) Lưu thông tin cây phục vụ giải nén (lưu bảng mã hoặc bảng tần số).
    • Thuật toán giải nén: Đọc từng bit từ luồng nhị phân, duyệt từ gốc cây (pRoot) rẽ trái/phải theo bit nhận được cho đến khi chạm nút lá để khôi phục ký tự.

  • Chủ đề 4: Giải thuật nén Huffman động (Adaptive Huffman): Phân tích các nhược điểm của Huffman tĩnh (đòi hỏi quét tệp 2 lượt, phải lưu kèm bảng thông tin giải nén, không áp dụng được cho dữ liệu thời gian thực). Giới thiệu mô hình Huffman động cho phép nén trực tuyến (on-line) chỉ qua 1 lượt duyệt file, tự động cập nhật cây nén trong quá trình truyền nhận. Điểm qua các dấu mốc phát triển: Faller (1973), Gallager (1978), Knuth (1985 – thuật toán FGK) và Vitter (1987).

Kiến thức nền tảng được xây dựng

  1. Lý thuyết thông tin và tối ưu hóa biểu diễn dữ liệu: Nhận diện sự dư thừa dữ liệu (redundancy) dưới dạng các chuỗi lặp liên tiếp hoặc chênh lệch tần số xuất hiện của các ký tự trong tệp.
  2. Cấu trúc dữ liệu nâng cao: Ứng dụng cấu trúc mảng để lưu trữ cây nhị phân có tối đa 511 phần tử: 
    #define MAX_NODES 511 // 2*256 - 1
typedef struct {
    char c;          // Ký tự
    bool used;       // Trạng thái đã sử dụng
    long nFreq;      // Trọng số / tần số xuất hiện
    int nLeft;       // Chỉ số cây con trái
    int nRight;      // Chỉ số cây con phải
} HUFFNode;
HUFFNode HuffTree[MAX_NODES];
  3. Kỹ thuật thao tác dữ liệu mức bit (Bitwise Operations): Rèn luyện việc sử dụng các toán tử bitmasking (& 0xC0, & 0x3F, | 0xC0) để đóng gói thông tin cờ hiệu và độ dài trực tiếp vào từng byte dữ liệu.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Cài đặt thuật toán mã hóa và giải mã bằng ngôn ngữ C/C++ trực tiếp trên luồng tệp tin nhị phân qua các hàm getc(), putc(), feof(), thao tác con trỏ chuỗi char *aString.
  • Kỹ năng phân tích thuật toán: Tính toán chi phí không gian bộ nhớ của cây nhị phân, so sánh độ phức tạp tính toán giữa mô hình quét 2 lượt (Huffman tĩnh) và 1 lượt (Huffman động).
  • Kỹ năng xử lý trường hợp biên (Corner Cases): Xử lý sự cố phình to dữ liệu (phản tác dụng) của RLE khi xử lý chuỗi ký tự không lặp hoặc các byte có giá trị ASCII nằm trong vùng cờ hiệu nhị phân ($\ge 192$).

Phương pháp giảng dạy và học tập

Tài liệu thể hiện phương pháp sư phạm quy nạp: đi từ các ví dụ trực quan về chuỗi ký tự đơn giản đến việc mô hình hóa toán học, biểu diễn cấu trúc dữ liệu và chuyển đổi thành mã nguồn hoàn chỉnh.

Bài tập và phân tích ca điển hình (Case Studies)

Tài liệu cung cấp các ca nghiên cứu thực tế về định dạng tệp:

  1. Ca nghiên cứu tệp đồ họa .PCX: Minh họa chuỗi 13 ký tự 'A' liên tiếp được nén thành 2 bytes nhị phân 0xCD 0x41 (trong đó 0xCD gồm cờ 11 và giá trị 13 = 001101b). Đồng thời phân tích chuỗi đặc biệt 0xD9 (giá trị 217) phải mã hóa thành 2 bytes 0xC1 0xD9 để tránh xung đột với bit cờ hiệu.
  2. Ca nghiên cứu tệp .BMP của Windows: So sánh cơ chế dùng mã ESCAPE 0x00 để chuyển đổi linh hoạt giữa việc nén lặp (ví dụ 255 ký tự 'A' thành 0xFF 'A') và việc giữ nguyên chuỗi không lặp (ví dụ chuỗi "BCDEFG" thành 0x00 0x06 'B''C''D''E''F''G').
  3. Ca tính toán kích thước chuỗi trong Huffman: Phân tích tập mẫu $f =$ "ADDAABBCCBAAABBCCCBBBCDAADDEEAA" gồm 31 ký tự:
    • Biểu diễn chuẩn (8 bits/ký tự): $10\times 8 + 8\times 8 + 6\times 8 + 5\times 8 + 2\times 8 = 248\text{ bits}$.
    • Biểu diễn mã Huffman: 'A' (11, 2 bits), 'B' (10, 2 bits), 'C' (00, 2 bits), 'D' (011, 3 bits), 'E' (010, 3 bits) $\to$ Tổng dung lượng sau nén giảm xuống còn: $$10\times 2 + 8\times 2 + 6\times 2 + 5\times 3 + 2\times 3 = 69\text{ bits}.$$

Mã nguồn mẫu và thực hành

Bài giảng cung cấp các đoạn mã nguồn C hoàn chỉnh cho các khâu then chốt:

  • int PCXEncode_a_String(char *aString, int nLen, FILE *fEncode);
  • int PCXEncode_a_Run(unsigned char c, int nRunCount, FILE *fEncode);
  • int PCXDecode_a_File(FILE *fEncode, FILE *fDecode);
  • int BMPDecode_a_File(FILE *fEncode, FILE *fDecode);

Hướng dẫn tự học và đánh giá

Người học cần tự giải quyết các bài toán tư duy được đặt ra trong bài giảng, tiêu biểu như:

  • Phân tích lý do vì sao định dạng .PCX sử dụng 2 bits làm cờ hiệu thay vì 1 bit.
  • So sánh ưu và nhược điểm giữa cơ chế cờ hiệu nhị phân của .PCX và cơ chế byte chuyển đổi ESCAPE của .BMP.
  • Truy vết quy trình giải nén chuỗi nhị phân mẫu "1000110" trên cây Huffman đã xây dựng để tìm chuỗi ký tự ban đầu.

Điểm nổi bật và tính hệ thống

Tài liệu kết hợp chặt chẽ giữa tính học thuật hàn lâm và ứng dụng kỹ thuật:

  1. Hệ thống hóa tiến trình lịch sử thuật toán: Tài liệu không chỉ giới thiệu giải thuật mà còn phác thảo cây phả hệ phát triển của lý thuyết nén dữ liệu: từ phát minh của David Huffman (1952), các đóng góp nền tảng cho nén thích ứng của Faller (1973) và Gallager (1978), đến các công trình hoàn thiện thuật toán FGK của Donald Knuth (1985) và tối ưu hóa cây của Jeffrey Vitter (1987).
  2. Gắn liền thuật toán với định dạng tệp chuẩn: Không sử dụng các mô hình giả định trừu tượng, bài giảng đưa người học tiếp cận trực tiếp cấu trúc nhị phân của các tệp đồ họa phổ biến trong hệ điều hành Windows và DOS (.PCX, .BMP), giúp người học hiểu rõ cách công nghiệp phần mềm áp dụng giải thuật nén vào thực tế.
  3. Chi tiết hóa thuật toán dựng cây nhị phân: Đưa ra các quy ước thứ tự duyệt tường minh để đảm bảo tính tất định (deterministic) khi sinh cây Huffman:
    • Nút có trọng số nhỏ nằm bên trái, nút trọng số lớn nằm bên phải.
    • Nếu hai nút có cùng trọng số, nút chứa ký tự có mã ASCII nhỏ hơn được ưu tiên đặt bên nhánh trái hoặc xử lý trước.

Đối tượng sử dụng giáo trình

  • Sinh viên đại học: Phục vụ sinh viên năm thứ hai hoặc năm thứ ba ngành Công nghệ Thông tin, Khoa học Máy tính, Kỹ thuật Phần mềm đang học môn Cấu trúc Dữ liệu và Giải thuật hoặc môn Xử lý Đa phương tiện.
  • Kiến thức tiên quyết (Prerequisites): Người học cần nắm vững kỹ thuật lập trình C/C++, các cấu trúc dữ liệu cơ bản (mảng, cấu trúc struct, cây nhị phân), thao tác nhập/xuất tệp tin ở mức byte và các phép toán thao tác bit (AND, OR, dịch bit <<, >>).
  • Giảng viên: Sử dụng làm tài liệu giảng dạy chuyên đề nén dữ liệu lossless, cung cấp sẵn khung sườn lý thuyết, sơ đồ khối thuật toán, bài toán tính toán dung lượng và mã nguồn mẫu phục vụ cho các giờ thực hành trên máy.
  • Kỹ sư phần mềm và người tự học: Tài liệu tham khảo cho người phát triển phần mềm cần hiểu sâu về cơ chế lưu trữ nhị phân, tối ưu hóa giao thức truyền tải hoặc xây dựng các công cụ trích xuất dữ liệu.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế cho sinh viên đại học ngành Công nghệ Thông tin, giảng viên chuyên ngành Khoa học Máy tính và lập trình viên cần tài liệu tra cứu chuẩn xác về các giải thuật nén bảo toàn thông tin.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận tài liệu?

Người học cần có nền tảng vững chắc về ngôn ngữ lập trình C/C++, cấu trúc dữ liệu cây nhị phân (Binary Tree), kỹ thuật thao tác con trỏ, thao tác tệp nhị phân (FILE*, getc, putc) và các phép toán logic trên bit.

3. Sự khác biệt cơ bản giữa nén RLE trong file .PCX và .BMP là gì?

Định dạng .PCX sử dụng 2 bit cao (11) của byte dữ liệu làm cờ hiệu để quy định số lần lặp ($n \le 63$), trong khi định dạng .BMP sử dụng byte mã nhận dạng đặc biệt ESCAPE (0x00) để phân tách rõ ràng giữa chế độ nén lặp (Run) và chế độ lưu trữ dãy ký tự đơn lẻ.

4. Tại sao thuật toán Huffman động (Adaptive Huffman) được phát triển để thay thế Huffman tĩnh?

Huffman tĩnh yêu cầu phải quét toàn bộ dữ liệu 2 lượt (lượt 1 đếm tần số để dựng cây, lượt 2 thực hiện nén) và bắt buộc phải lưu kèm bảng mã/cây vào tệp nén. Huffman động khắc phục các hạn chế này bằng cách chỉ quét dữ liệu 1 lượt duy nhất, tự cập nhật cây trong quá trình xử lý, không cần lưu thông tin giải nén và hỗ trợ nén trực tiếp luồng dữ liệu thời gian thực.

5. Hiệu suất nén dữ liệu được định nghĩa và tính toán như thế nào?

Hiệu suất nén $D(%)$ là tỷ lệ phần trăm kích thước dữ liệu giảm được sau khi nén, tính theo công thức $D = \frac{N - M}{N} \times 100$, trong đó $N$ là kích thước dữ liệu gốc và $M$ là kích thước dữ liệu sau khi nén. Tỷ lệ này phụ thuộc vào phương pháp nén và đặc trưng phân bố của dữ liệu đầu vào.

Kết luận

Bài giảng Data Structures & Algorithms: Các thuật toán nén dữ liệu của tác giả Nguyễn Tri Tuấn cung cấp một cấu trúc học thuật chặt chẽ về các phương pháp nén dữ liệu bảo toàn thông tin cơ bản và nâng cao. Tài liệu kết nối hiệu quả giữa lý thuyết cấu trúc dữ liệu cây nhị phân với việc hiện thực hóa mã nguồn trong các bài toán định dạng tệp thực tế.

Lộ trình học tập đề xuất: Bắt đầu từ việc nắm vững định nghĩa phân loại nén (Lossless vs Lossy) $\to$ Thực hành cài đặt các biến thể RLE trên tệp .PCX và .BMP $\to$ Nắm vững quy trình 5 bước dựng cây và sinh mã của Static Huffman $\to$ Nghiên cứu các thuật toán nâng cao như Huffman động (FGK, Vitter) và các phương pháp nén từ điển (LZ77, LZ78, LZW).