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

Tài liệu học thuật "Các Thuật Toán Nén Dữ Liệu" do Bùi Tiến Lên biên soạn (ngày 01/01/2017) là tài liệu bài giảng chuyên đề thuộc học phần Cấu trúc dữ liệu và Giải thuật (Data structure & Algorithm - Spring 2017) trong chương trình đào tạo bậc đại học khối ngành Khoa học máy tính và Công nghệ thông tin.

Về mặt mục tiêu học tập, tài liệu trang bị cho người học:

  • Khái niệm nền tảng và mục đích của nén dữ liệu: giảm kích thước lưu trữ dữ liệu và tăng tính bảo mật trong quá trình truyền tải.
  • Hệ thống phân loại hai trường phái nén dữ liệu chính: 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).
  • Phương pháp định lượng hiệu suất nén thông qua công thức toán học xác định.
  • Cơ chế vận hành, mã giả (pseudocode), cấu trúc dữ liệu biểu diễn và các bước thực thi chi tiết của ba thuật toán nén bảo toàn thông tin tiêu chuẩn: Run-Length Encoding (RLE), Lempel-Ziv-Welch (LZW) và Mã hóa Huffman.

Tài liệu được thiết kế theo cấu trúc diễn tiến sư phạm trực quan: bắt đầu từ các định nghĩa lý thuyết, thiết lập công thức toán học, trình bày mã giả thuật toán, phân tích bảng chuyển trạng thái (trace table) từng bước qua chuỗi dữ liệu cụ thể, và trực quan hóa cấu trúc dữ liệu dạng cây (tree/trie structure).

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

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

Nội dung tài liệu được tổ chức thành các chủ đề lý thuyết và giải thuật có tính liên kết chặt chẽ:

  1. Tổng quan về nén dữ liệu và phân loại:

    • Xác định hai mục đích cốt lõi của nén dữ liệu: giảm kích thước dữ liệu và tăng tính bảo mật.
    • Phân loại kỹ thuật nén thành hai nhóm:
      • Nén bảo toàn thông tin (Lossless compression): Bao gồm thuật toán nén RLE, thuật toán nén LZW và thuật toán nén Huffman.
      • Nén không bảo toàn thông tin (Lossy compression): Giới thiệu các phương pháp sử dụng biến đổi Fourier rời rạc (DFT) và biến đổi Wavelet.
    • Thiết lập Định nghĩa 1 (Hiệu suất nén): Tỉ lệ kích thước giảm được sau khi áp dụng thuật toán nén, biểu diễn theo công thức: $$D = \frac{N - M}{N} \times 100$$ Trong đó:
      • $D$: Hiệu suất nén (đơn vị %).
      • $N$: Kích thước dữ liệu trước khi nén.
      • $M$: Kích thước dữ liệu sau khi nén. Tài liệu chỉ rõ hiệu suất nén phụ thuộc trực tiếp vào phương pháp nén và đặc trưng cấu trúc của tập dữ liệu đầu vào.

  2. Thuật toán nén Run-Length Encoding (RLE):

    • Nguyên lý: Mã hóa dữ liệu dựa trên sự lặp lại liên tiếp của các ký tự.
    • Khái niệm: Một dãy các ký tự lặp lại liên tiếp được định nghĩa là một "đường chạy" (run).
    • Quy tắc mã hóa: Mỗi đường chạy được biểu diễn dưới dạng cú pháp [số ký tự][ký tự]. Khi độ dài đường chạy càng lớn thì tỉ lệ nén càng tăng.
    • Minh họa qua Ví dụ 1: Chuỗi ký tự AAABBCCAAADE qua xử lý RLE được mã hóa thành 3A2B2C3A1D1E.
    • Đánh giá kỹ thuật: Thuật toán có cấu trúc đơn giản, dễ cài đặt; tối ưu cho các tập dữ liệu có nhiều đoạn lặp lại liên tục (như dữ liệu ảnh); tuy nhiên hiệu suất nén tổng quát không cao đối với dữ liệu phân tán.

  3. Thuật toán nén Lempel-Ziv-Welch (LZW):

    • Lịch sử và phân loại: Thuật toán được đề xuất bởi Abraham Lempel, Jacob Ziv và được Terry Welch cải tiến [Lempel, 1978]. Đây là thuật toán nén từ điển dựa trên tần suất xuất hiện chuỗi ký tự, được ứng dụng thực tế trong định dạng ảnh GIF.
    • Cung cấp mã giả thuật toán nén LZW: Sử dụng biến tiền tố $w$ (khởi tạo null), duyệt từng ký tự $k$ trong luồng dữ liệu; kiểm tra chuỗi kết hợp $wk$ trong từ điển: nếu tồn tại thì gán $w = wk$, ngược lại xuất mã định danh $c \leftarrow \text{Code}(w)$, bổ sung chuỗi $wk$ vào từ điển và đặt lại $w \leftarrow k$.
    • Bảng lần vết quá trình nén chuỗi ký tự abracadabarabra: Khởi tạo từ điển cơ sở với các ký tự đơn lẻ (a: 0, b: 1, c: 2, d: 3, r: 4), chuỗi mã hóa đầu ra thu được gồm dãy số 0 1 4 0 2 0 3 5 0 7 6 0, đồng thời phát sinh các từ mới trong từ điển từ mã 5 đến 15.
    • Biểu diễn Cây từ điển LZW (Hình 1) mô tả mối quan hệ phân nhánh giữa các ký tự và chỉ số mã hóa tương ứng.
    • Thuật toán giải nén LZW: Không yêu cầu truyền kèm toàn bộ từ điển mà sử dụng kỹ thuật đọc mã định danh $c$, tra cứu từ $w \leftarrow \text{Word}(c)$ và chủ động tái tạo lại từ điển trong quá trình giải mã. Minh họa qua việc giải mã chuỗi 0 1 2 4 3 6 thành chuỗi ký tự ban đầu abababababab.

  4. Kỹ thuật mã hóa độ dài thay đổi và Thuật toán Huffman:

    • So sánh các phương pháp mã hóa dữ liệu: Mã hóa sử dụng dãy bit có chiều dài cố định (ASCII sử dụng 8 bits) so với mã hóa sử dụng dãy bit có chiều dài thay đổi theo tần suất (Bảng mã Morse - Bảng 1, Mã Huffman).
    • Ý tưởng giải thuật Huffman: Dữ liệu có tần suất xuất hiện cao sẽ được biểu diễn bằng ít bit, dữ liệu có tần suất xuất hiện thấp sẽ được biểu diễn bằng nhiều bit.
    • Định nghĩa 2 (Cây Huffman [Huffman, 1952]): Là một cây nhị phân đầy đủ:
      • Nút lá chứa ký tự và có trọng số bằng số lần xuất hiện của ký tự trong dữ liệu.
      • Nút cha chứa chuỗi ký tự của các nút con và có trọng số bằng tổng trọng số của hai nút con.
      • Nút con trái có thứ tự từ điển trước nút con phải và có trọng số nhỏ hơn hoặc bằng nút con phải.
      • Cung nối: Nhánh trái được gán giá trị bit 0, nhánh phải được gán giá trị bit 1.
    • Định lý 1 (Tính chất cây Huffman): Cây Huffman là cây nhị phân đầy đủ; các nút có tần suất cao nằm gần gốc, các nút có tần suất thấp nằm xa gốc; tổng số nút trên cây là $2n - 1$ (với $n$ là số ký tự phân biệt).
    • Quy trình nén Huffman chuẩn gồm 5 bước:
      • Bước 1: Duyệt dữ liệu để lập bảng thống kê số lần xuất hiện của mỗi ký tự.
      • Bước 2: Tạo cây Huffman từ bảng thống kê tần suất.
      • Bước 3: Phát sinh bảng mã bit cho các ký tự từ cây Huffman.
      • Bước 4: Duyệt dữ liệu để thay thế các ký tự bằng chuỗi mã bit tương ứng.
      • Bước 5: Lưu lại thông tin cấu trúc cây Huffman dùng cho quá trình giải nén.
    • Minh họa Ví dụ 2: Xử lý chuỗi ADDAABBCCBAAABBCCCBBBCDAADDEEAA (31 ký tự) với bảng tần suất (Bảng 2: A: 10, B: 8, C: 6, D: 5, E: 2). Quá trình xây dựng cây được thực hiện qua các giai đoạn ghép cặp nút có trọng số nhỏ nhất (Hình 4, 5, 6, 7), hình thành Cây Huffman hoàn chỉnh (Hình 2, Hình 3) và tạo ra Bảng 3 (Bảng mã bit: A: 11, B: 10, C: 00, D: 011, E: 010).

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

  • Lý thuyết thông tin và nén dữ liệu: Mô hình hóa việc tối ưu dung lượng lưu trữ dựa trên tần suất xuất hiện và quy luật lặp lại của dữ liệu.
  • Cấu trúc dữ liệu nâng cao:
    • Cấu trúc cây từ điển (Trie/Tree structure) ứng dụng trong thuật toán LZW.
    • Cấu trúc cây nhị phân đầy đủ (Full Binary Tree) và tính chất hình học cây trong thuật toán Huffman.
  • Kỹ thuật mã hóa tiền tố (Prefix-free code): Đảm bảo không có từ mã nào là tiền tố của từ mã khác, cho phép giải mã chuỗi bit liên tục một cách tất định.

Kỹ năng phát triển

  • Kỹ năng phân tích và mô hình hóa: Thống kê phân bố tần suất ký tự, tính toán hiệu suất nén $D$ theo công thức định lượng.
  • Kỹ năng lần vết giải thuật (Algorithm Tracing): Theo dõi sự biến thiên của các biến cục bộ ($w, k, c$), bảng từ điển động và dòng xuất mã qua từng bước lặp.
  • Kỹ năng hiện thực hóa cấu trúc dữ liệu: Xây dựng, cập nhật và duyệt cây nhị phân, xử lý các thao tác ghép nút tối ưu theo nguyên lý tham lam (Greedy approach).

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

Tài liệu sử dụng phương pháp sư phạm cấu trúc giải thuật trực quan (step-by-step algorithmic presentation), kết hợp chặt chẽ giữa lý thuyết định nghĩa và bài tập trace trạng thái thực tế:

  • Phương pháp tiếp cận: Mỗi thuật toán được triển khai tuần tự theo 4 giai đoạn: Định nghĩa nguyên lý $\rightarrow$ Mã giả thuật toán $\rightarrow$ Bảng phân tích trạng thái qua chuỗi ký tự mẫu $\rightarrow$ Sơ đồ cấu trúc cây dữ liệu.
  • Bài tập và dữ liệu mẫu có sẵn:
    • Thuật toán RLE: Khảo sát chuỗi lặp AAABBCCAAADE để kiểm chứng quy tắc đường chạy.
    • Thuật toán LZW: Khảo sát chuỗi abracadabarabra với bảng chạy thử chi tiết gồm 16 bước duyệt ký tự, cột từ điển cập nhật và chỉ số mã xuất ra. Bài toán giải nén chuỗi mã 0 1 2 4 3 6 thành chuỗi abababababab.
    • Thuật toán Huffman: Bài toán xử lý chuỗi 31 ký tự ADDAABBCCBAAABBCCCBBBCDAADDEEAA với chuỗi hình vẽ từng bước (Hình 4 đến Hình 7) mô tả việc loại bỏ 2 phần tử có trọng số thấp nhất, tạo nút tổng và tái sắp xếp bảng tần suất.
  • Phương pháp đánh giá: Đánh giá khả năng hiểu thuật toán của người học thông qua việc tính toán hiệu suất nén $D$, khả năng giải mã chính xác chuỗi mã hóa mà không cần nhìn trước kết quả, và kỹ năng vẽ cây cấu trúc tương ứng.
  • Hướng dẫn tự học: Người học cần tự viết lại bảng trace từng bước đối với chuỗi ký tự mới, tự cài đặt thuật toán giải nén LZW và giải mã cây Huffman bằng cách duyệt từ gốc đến lá theo các bit 0 và 1.

Điểm nổi bật và cập nhật

  • Tính học thuật và trích dẫn chuẩn mực: Tài liệu trích dẫn chính xác các công trình khoa học nền tảng, bao gồm thuật toán nén từ điển LZW của Ziv, Lempel và Welch [Lempel, 1978] cùng công trình cây nhị phân tối ưu của David Huffman [Huffman, 1952].
  • Phân loại toàn diện: Hệ thống hóa rõ ràng ranh giới giữa hai nhánh nén dữ liệu: nén bảo toàn thông tin (Lossless) và nén không bảo toàn thông tin (Lossy - giới thiệu phương pháp biến đổi DFT và Wavelet).
  • Hệ thống sơ đồ trực quan hóa cao: Sử dụng nhiều hình vẽ minh họa cấu trúc dữ liệu chi tiết:
    • Cây từ điển LZW (Hình 1).
    • Cây Huffman tổng quát và cây phát sinh bảng mã bit (Hình 2, Hình 3).
    • Chuỗi hình vẽ trạng thái tạo cây từng bước (Hình 4, 5, 6, 7).
  • Liên hệ kỹ thuật thực tiễn: Nêu rõ các ứng dụng công nghệ thực tế của giải thuật, cụ thể là ứng dụng của thuật toán LZW trong chuẩn nén định dạng ảnh GIF, ứng dụng RLE trong dữ liệu hình ảnh, và đối chiếu mã Huffman với chuẩn mã hóa ASCII 8-bit và mã Morse (Bảng 1).

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

  • Sinh viên chuyên ngành: Sinh viên năm thứ hai hoặc năm thứ ba theo học các ngành Khoa học máy tính, Kỹ thuật phần mềm, Công nghệ thông tin và Hệ thống thông tin trong học phần Cấu trúc dữ liệu và Giải thuật.
  • Kiến thức tiên quyết (Prerequisites):
    • Kiến thức lập trình căn bản (kiểu dữ liệu chuỗi, mảng, con trỏ).
    • Cấu trúc dữ liệu cơ bản: Cây nhị phân (Binary Tree), danh sách, bảng tra từ điển.
    • Khái niệm cơ bản về hệ thống nhị phân, bit và byte.
  • Giảng viên: Sử dụng tài liệu làm khung bài giảng lý thuyết và bài tập trên lớp, tận dụng hệ thống bảng trace và sơ đồ cây để giải thích cơ chế giải thuật.
  • Người tự học và nghiên cứu: Phục vụ các lập trình viên cần tài liệu tham khảo chính xác để hiện thực hóa các thư viện nén dữ liệu lossless hoặc tìm hiểu cơ chế nén tập tin.

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 biên soạn cho sinh viên ngành Công nghệ thông tin học môn Cấu trúc dữ liệu và Giải thuật, cũng như các kỹ sư phần mềm cần nắm vững nguyên lý và cơ chế cài đặt các thuật toán nén dữ liệu không mất thông tin.

2. Cần kiến thức nền nào để học?

Người học cần nắm vững kỹ thuật lập trình cơ bản, thao tác xử lý chuỗi ký tự, các phép toán logic trên bit, và đặc biệt là kiến thức về cấu trúc dữ liệu cây nhị phân.

3. Điểm khác biệt với giáo trình khác?

Tài liệu không chỉ dừng lại ở mặt lý thuyết mà phân tích chi tiết từng bước chuyển trạng thái biến thông qua bảng trace mẫu cho cả hai chiều nén và giải nén (như ví dụ nén chuỗi abracadabarabra và giải nén chuỗi 0 1 2 4 3 6 trong LZW), đi kèm sơ đồ phát triển cây Huffman qua từng vòng lặp.

4. Làm sao để tự học hiệu quả?

Người học nên đọc kỹ phần mã giả, sau đó tự tay vẽ bảng trace từng bước và dựng cây từ điển/cây nhị phân cho các chuỗi ký tự tự chọn, đối chiếu kết quả với các ví dụ mẫu có trong tài liệu.

5. Có tài liệu bổ trợ nào kèm theo?

Tài liệu tích hợp sẵn mã giả chuẩn cho thuật toán nén và giải nén LZW, bảng mã Morse tham khảo (Bảng 1), công thức toán học tính hiệu suất nén $D$, bảng thống kê tần suất (Bảng 2), bảng mã bit hoàn chỉnh (Bảng 3) và hệ thống sơ đồ cây từ Hình 1 đến Hình 7.

Kết luận

Tài liệu bài giảng "Các Thuật Toán Nén Dữ Liệu" của Bùi Tiến Lên (Spring 2017) cung cấp hệ thống kiến thức hoàn chỉnh về các phương pháp nén dữ liệu bảo toàn thông tin cốt lõi trong khoa học máy tính.

Lộ trình tiếp thu khuyến nghị cho người học bao gồm:

  1. Nắm vững định nghĩa và công thức tính hiệu suất nén $D = \frac{N - M}{N} \times 100$.
  2. Nghiên cứu thuật toán nén dựa trên tính lặp lại Run-Length Encoding (RLE).
  3. Làm chủ thuật toán nén và tự tái tạo từ điển động Lempel-Ziv-Welch (LZW).
  4. Phân tích cấu trúc cây nhị phân đầy đủ và kỹ thuật mã hóa độ dài thay đổi tối ưu của Huffman.

Tài liệu là nguồn tư liệu học thuật chuẩn mực, phục vụ trực tiếp cho việc học tập, giảng dạy và cài đặt giải thuật trong môn học Cấu trúc dữ liệu và Giải thuật.