Về Chương 2
Buồng Nén Dữ Liệu
Buồng Nén Ma Trận Đường Chéo (Tridiagonal Matrix)
O(N^2) Không Gian Rỗng ➔ O(3N) Mảng 1D
Ma Trận 2D Chứa Nhiều Số 0 Thừa (Mảng Thưa)
10
11
0
0
0
22
20
21
0
0
0
32
30
31
0
0
0
42
40
41
0
0
0
52
50
▼
Mảng 1D Nén O(3N)
0
A[0]
1
A[1]
2
A[2]
3
A[3]
4
A[4]
5
A[5]
6
A[6]
7
A[7]
8
A[8]
9
A[9]
10
A[10]
11
A[11]
12
A[12]
13
A[13]
14
A[14]
Bắt Đầu Nén
Rã nén
Delay
Chậm
Vừa
Nhanh
💾
Kích Cỡ Dữ Liệu
Ma Trận Gốc N = 5x5
2D (Uncompressed):
25
1D (Compressed):
3N = 15
Tiết kiệm được ~40% dung lượng.
Công thức ánh xạ (Mapping)
Mảng 2D:
A[r][c]
Cú pháp Nén:
Main
(r=c)
: K = 3r+1
Top
(c=r+1)
: K = 3r+2
Bot
(r=c+1)
: K = 3r
Lưu ý:
Một số ô nhỏ (như index 0 đầu tiên) có thể bị bỏ trống làm phần đệm (Padding) để công thức tính nhanh được áp dụng bằng phép nhân 3 đơn giản.