Nén dữ liệu

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 3)

Nén dữ liệu

Burrows-Wheeler Transform

Thời gian (Time) O(n log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Phép biến đổi chuỗi chuẩn bị cho thuật toán nén dữ liệu hiệu quả.

Cài đặt mẫu (Implementation)

// Sắp xếp các hoán vị xoay vòng và lấy cột cuối.
Nén dữ liệu

Huffman Coding

Thời gian (Time) O(n log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Thuật toán mã hóa nén không mất mát dựa trên tần suất xuất hiện.

Cài đặt mẫu (Implementation)

// Xây dựng cây nhị phân từ hàng đợi ưu tiên (min heap).
Nén dữ liệu

Run-Length Encoding (RLE)

Thời gian (Time) O(n)
Không gian (Space) O(1)

Mô tả nguyên lý

Nén đơn giản bằng cách thay thế chuỗi ký tự lặp liên tiếp bằng số lượng.

Cài đặt mẫu (Implementation)

function rleEncode($str) {
    $res = ""; $n = strlen($str);
    for ($i = 0; $i < $n; $i++) {
        $c = 1;
        while ($i + 1 < $n && $str[$i] == $str[$i+1]) { $c++; $i++; }
        $res .= $str[$i] . $c;
    }
    return $res;
}