Thuật toán Nén Dữ liệu (Data Compression)
1. Giới thiệu
Nén dữ liệu là quá trình mã hóa thông tin sử dụng ít bits hơn biểu diễn gốc. Có hai loại nén chính: - Nén không mất dữ liệu (Lossless) - Nén có mất dữ liệu (Lossy)
2. Thuật toán Huffman
public class HuffmanCoding {
private class Node implements Comparable<Node> {
char ch;
int freq;
Node left, right;
Node(char ch, int freq) {
this.ch = ch;
this.freq = freq;
}
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
@Override
public int compareTo(Node other) {
return this.freq - other.freq;
}
}
public Map<Character, String> buildHuffmanCodes(String text) {
// Tính tần suất
Map<Character, Integer> freq = new HashMap<>();
for (char c : text.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// Tạo priority queue
PriorityQueue<Node> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.offer(new Node(entry.getKey(), entry.getValue()));
}
// Xây dựng cây Huffman
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
pq.offer(new Node('\0', left.freq + right.freq, left, right));
}
// Tạo mã Huffman
Map<Character, String> huffmanCode = new HashMap<>();
generateCodes(pq.peek(), "", huffmanCode);
return huffmanCode;
}
private void generateCodes(Node root, String code,
Map<Character, String> huffmanCode) {
if (root == null) return;
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, code);
}
generateCodes(root.left, code + "0", huffmanCode);
generateCodes(root.right, code + "1", huffmanCode);
}
public String compress(String text) {
Map<Character, String> huffmanCode = buildHuffmanCodes(text);
StringBuilder compressed = new StringBuilder();
for (char c : text.toCharArray()) {
compressed.append(huffmanCode.get(c));
}
return compressed.toString();
}
}
3. Thuật toán Run-Length Encoding (RLE)
public class RunLengthEncoding {
public static String encode(String text) {
if (text == null || text.isEmpty()) return "";
StringBuilder encoded = new StringBuilder();
int count = 1;
char current = text.charAt(0);
for (int i = 1; i < text.length(); i++) {
if (text.charAt(i) == current) {
count++;
} else {
encoded.append(count).append(current);
current = text.charAt(i);
count = 1;
}
}
encoded.append(count).append(current);
return encoded.toString();
}
public static String decode(String text) {
StringBuilder decoded = new StringBuilder();
for (int i = 0; i < text.length(); i += 2) {
int count = Character.getNumericValue(text.charAt(i));
char ch = text.charAt(i + 1);
for (int j = 0; j < count; j++) {
decoded.append(ch);
}
}
return decoded.toString();
}
}
4. Thuật toán LZW (Lempel-Ziv-Welch)
public class LZW {
public static List<Integer> compress(String text) {
Map<String, Integer> dictionary = new HashMap<>();
int dictSize = 256;
// Khởi tạo dictionary với các ký tự ASCII
for (int i = 0; i < 256; i++) {
dictionary.put(String.valueOf((char)i), i);
}
String current = "";
List<Integer> result = new ArrayList<>();
for (char c : text.toCharArray()) {
String combined = current + c;
if (dictionary.containsKey(combined)) {
current = combined;
} else {
result.add(dictionary.get(current));
dictionary.put(combined, dictSize++);
current = String.valueOf(c);
}
}
if (!current.isEmpty()) {
result.add(dictionary.get(current));
}
return result;
}
public static String decompress(List<Integer> compressed) {
Map<Integer, String> dictionary = new HashMap<>();
int dictSize = 256;
// Khởi tạo dictionary với các ký tự ASCII
for (int i = 0; i < 256; i++) {
dictionary.put(i, String.valueOf((char)i));
}
String current = String.valueOf((char)(int)compressed.get(0));
StringBuilder result = new StringBuilder(current);
for (int i = 1; i < compressed.size(); i++) {
int code = compressed.get(i);
String entry;
if (dictionary.containsKey(code)) {
entry = dictionary.get(code);
} else {
entry = current + current.charAt(0);
}
result.append(entry);
dictionary.put(dictSize++, current + entry.charAt(0));
current = entry;
}
return result.toString();
}
}
5. So sánh các thuật toán
5.1. Huffman Coding
- Ưu điểm:
- Tối ưu cho dữ liệu có phân bố tần suất không đều
- Không mất dữ liệu
- Nhược điểm:
- Cần lưu trữ bảng mã
- Không hiệu quả với dữ liệu nhỏ
5.2. Run-Length Encoding
- Ưu điểm:
- Đơn giản, dễ implement
- Hiệu quả với dữ liệu có nhiều ký tự lặp
- Nhược điểm:
- Có thể làm tăng kích thước với dữ liệu ngẫu nhiên
- Không hiệu quả với dữ liệu đa dạng
5.3. LZW
- Ưu điểm:
- Không cần lưu trữ bảng mã
- Hiệu quả với dữ liệu có mẫu lặp lại
- Nhược điểm:
- Tốn bộ nhớ cho dictionary
- Hiệu suất phụ thuộc vào kích thước dictionary
6. Ứng dụng thực tế
- Nén file (ZIP, RAR, 7z)
- Nén ảnh (PNG, JPEG)
- Nén âm thanh (MP3, AAC)
- Nén video (H.264, H.265)
- Network data transmission
- Database compression
7. Bài tập thực hành
- Implement các thuật toán cơ bản:
- Huffman coding
- RLE
-
LZW
-
Bài tập nâng cao:
- So sánh tỷ lệ nén của các thuật toán
- Tối ưu hóa bộ nhớ sử dụng
-
Xử lý file lớn
-
Ứng dụng thực tế:
- Tạo utility nén/giải nén file
- Nén dữ liệu real-time
- Tối ưu hóa truyền dữ liệu qua mạng