Nén dữ liệu
Burrows-Wheeler Transform
ID: #85
Xem trên trang chủ
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
ID: #86
Xem trên trang chủ
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)
ID: #87
Xem trên trang chủ
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;
}