Link tải luận văn miễn phí cho ae Kết Nối
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 29
Data Compression
Giới thiệu
Giải thuật nén RLE
Giải thuật nén Huffman
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 30
Giải thuật nén Huffman
Giới thiệu
Huffman tĩnh (Static Huffman)
Huffman động (Adaptive Huffman)
16
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 31
Giải thuật nén Huffman – Giới thiệu
Hình thành
Vấn đề:
Một giải thuật nén bảo toàn thông tin;
Không phụ thuộc vào tính chất của dữ liệu;
Ứng dụng rộng rãi trên bất kỳ dữ liệu nào, với hiệu suất tốt
Tư tưởng chính:
Phương pháp cũ: dùng 1 dãy cố định (8 bits) để biểu diễn 1 ký tự
Huffman:
Sử dụng vài bits để biểu diễn 1 ký tự (gọi là “mã bit” – bits code)
Độ dài “mã bit” cho các ký tự không giống nhau:
Ký tự xuất hiện nhiều lần biểu diễn bằng mã ngắn;
Ký tự xuất hiện ít biểu diễn bằng mã dài
Mã hóa bằng mã có độ dài thay đổi (Variable Length Encoding)
David Huffman – 1952: tìm ra phương pháp xác định mã tối ưu
trên dữ liệu tĩnh
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 32
Giải thuật nén Huffman – Giới thiệu (tt)
Giả sử có dữ liệu như sau:
f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA”
Biểu diễn bình thường (8 bits/ký tự):
Sizeof(f) = 10*8 + 8*8 + 6*8 + 5*8 + 2*8
= 248 bits
2E
5D
6C
8B
10 A
Số lần xuất hiện
trong file f
Ký tự
17
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 33
Giải thuật nén Huffman – Giới thiệu (tt)
Biểu diễn bằng mã có độ dài thay đổi (theo
bảng):
Sizeof(f) = 10*2 + 8*2 + 6*2 + 5*3 + 2*3
= 69 bits
010 E
011D
00C
10B
11A
MãKý tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 34
Static Huffman
Thuật toán nén
Tạo cây Huffman
Phát sinh bảng mã bit
Lưu trữ thông tin dùng để giải nén
Thuật toán giải nén
18
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 35
Static Huffman (tt)
Thuật toán nén:
[b1] Duyệt file Lập bảng thống kê số lần xuất hiện của mỗi
loại ký tự
[b2] Phát sinh cây Huffman dựa vào bảng thống kê
[b3] Từ cây Huffman phát sinh bảng mã bit cho các ký tự
[b4] Duyệt file Thay thế các ký tự bằng mã bit tương ứng
[b5] Lưu lại thông tin của cây Huffman dùng để giải nén
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 36
Static Huffman (tt)
f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA”
2E
5D
6C
8B
10 A
Số lần xuất
hiện
Ký
tự
010 E
011D
00C
10B
11A
Mã bitKý
tự
[b1]
[b2]
[b3]
fnén = 11011011111110100000101111111010000000
1010100001111110110110100101111
[b4]
19
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 37
Static Huffman (tt)
Tạo cây Huffman:
Mô tả cây Huffman: mã Huffman được biểu diễn bằng
1 cây nhị phân
Mỗi nút lá chứa 1 ký tự
Nút cha sẽ chứa các ký tự
của những nút con
Mỗi nút được gán một trọng
số:
Nút lá có trọng số bằng số
lần xuất hiện của ký tự
trong file
Nút cha có trọng số bằng
tổng trọng số của các nút
con
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 38
Static Huffman (tt)
Tạo cây Huffman: (tt)
Tính chất cây Huffman:
Nhánh trái tương ứng với mã hoá bit ‘0’; nhánh phải tương
ứng với mã hoá bit ‘1’
Các nút có tần số thấp nằm ở xa gốc mã bit dài
Các nút có tần số cao nằm ở gần gốc mã bit ngắn
Số nút của cây: (2n-1)
20
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 39
Static Huffman (tt)
// Cấu trúc dữ liệu lưu trữ cây Huffman
#define MAX_NODES 511 // 2*256 - 1
typedef struct {
char c; // ký tự
long nFreq; // trọng số
int nLeft; // cây con trái
int nRight; // cây con phải
} HUFFNode;
HUFFNode HuffTree[MAX_NODES];
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 40
Static Huffman (tt)
Tạo cây Huffman: (tt)
Thuật toán phát sinh cây:
[b1] Chọn trong bảng thống kê 2 phần tử x,y có trọng số thấp nhất
tạo thành nút cha z:
z.c = min(x.c + y.c);
z.nFreq = x.nFreq + y.nFreq;
z.nLeft = x (*)
z.nRight = y (*)
[b2] Loại bỏ nút x và y khỏi bảng;
[b3] Thêm nút z vào bảng;
[b4] Lặp lại bước [b1] - [b3] cho đến khi chỉ còn lại 1 nút duy
nhất trong bảng
(*) Qui ước:
- nút có trọng số nhỏ nằm bên nhánh trái; nút có trọng số lớn nằm bên nhánh phải;
- nếu trọng số bằng nhau, nút có ký tự nhỏ nằm bên nhánh trái; nút có ký tự lớn nằm
bên nhánh phải
- nếu có các node có trọng số bằng nhau ưu tiên xử lý các node có ký tự ASCII
nhỏ trước
21
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 41
Static Huffman (tt)
Minh họa quá trình tạo cây
2E
5D
6C
8B
10 A
SLXHKý
tự
6C
7ED
8B
10 A
SLXHKý
tự
8B
10A
13CED
SLXHKý
tự
13CED
18BA
SLXHKý
tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 42
Static Huffman (tt)
Cây Huffman sau khi tạo
22
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 43
Static Huffman (tt)
Phát sinh mã bit cho các ký tự:
Mã của mỗi ký tự được tạo bằng cách duyệt từ nút gốc đến nút
lá chứa ký tự đó;
Khi duyệt sang trái, tạo ra 1 bit 0;
Khi duyệt sang phải, tạo ra 1 bit 1;
010 E
011D
00C
10B
11A
MãKý
tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 44
Static Huffman (tt)
Lưu trữ thông tin dùng để giải nén:
P.Pháp 1: lưu bảng mã bit P.Pháp 2: lưu số lần xuất hiện
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 29
Data Compression
Giới thiệu
Giải thuật nén RLE
Giải thuật nén Huffman
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 30
Giải thuật nén Huffman
Giới thiệu
Huffman tĩnh (Static Huffman)
Huffman động (Adaptive Huffman)
16
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 31
Giải thuật nén Huffman – Giới thiệu
Hình thành
Vấn đề:
Một giải thuật nén bảo toàn thông tin;
Không phụ thuộc vào tính chất của dữ liệu;
Ứng dụng rộng rãi trên bất kỳ dữ liệu nào, với hiệu suất tốt
Tư tưởng chính:
Phương pháp cũ: dùng 1 dãy cố định (8 bits) để biểu diễn 1 ký tự
Huffman:
Sử dụng vài bits để biểu diễn 1 ký tự (gọi là “mã bit” – bits code)
Độ dài “mã bit” cho các ký tự không giống nhau:
Ký tự xuất hiện nhiều lần biểu diễn bằng mã ngắn;
Ký tự xuất hiện ít biểu diễn bằng mã dài
Mã hóa bằng mã có độ dài thay đổi (Variable Length Encoding)
David Huffman – 1952: tìm ra phương pháp xác định mã tối ưu
trên dữ liệu tĩnh
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 32
Giải thuật nén Huffman – Giới thiệu (tt)
Giả sử có dữ liệu như sau:
f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA”
Biểu diễn bình thường (8 bits/ký tự):
Sizeof(f) = 10*8 + 8*8 + 6*8 + 5*8 + 2*8
= 248 bits
2E
5D
6C
8B
10 A
Số lần xuất hiện
trong file f
Ký tự
17
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 33
Giải thuật nén Huffman – Giới thiệu (tt)
Biểu diễn bằng mã có độ dài thay đổi (theo
bảng):
Sizeof(f) = 10*2 + 8*2 + 6*2 + 5*3 + 2*3
= 69 bits
010 E
011D
00C
10B
11A
MãKý tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 34
Static Huffman
Thuật toán nén
Tạo cây Huffman
Phát sinh bảng mã bit
Lưu trữ thông tin dùng để giải nén
Thuật toán giải nén
18
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 35
Static Huffman (tt)
Thuật toán nén:
[b1] Duyệt file Lập bảng thống kê số lần xuất hiện của mỗi
loại ký tự
[b2] Phát sinh cây Huffman dựa vào bảng thống kê
[b3] Từ cây Huffman phát sinh bảng mã bit cho các ký tự
[b4] Duyệt file Thay thế các ký tự bằng mã bit tương ứng
[b5] Lưu lại thông tin của cây Huffman dùng để giải nén
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 36
Static Huffman (tt)
f = “ADDAABBCCBAAABBCCCBBBCDAADDEEAA”
2E
5D
6C
8B
10 A
Số lần xuất
hiện
Ký
tự
010 E
011D
00C
10B
11A
Mã bitKý
tự
[b1]
[b2]
[b3]
fnén = 11011011111110100000101111111010000000
1010100001111110110110100101111
[b4]
19
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 37
Static Huffman (tt)
Tạo cây Huffman:
Mô tả cây Huffman: mã Huffman được biểu diễn bằng
1 cây nhị phân
Mỗi nút lá chứa 1 ký tự
Nút cha sẽ chứa các ký tự
của những nút con
Mỗi nút được gán một trọng
số:
Nút lá có trọng số bằng số
lần xuất hiện của ký tự
trong file
Nút cha có trọng số bằng
tổng trọng số của các nút
con
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 38
Static Huffman (tt)
Tạo cây Huffman: (tt)
Tính chất cây Huffman:
Nhánh trái tương ứng với mã hoá bit ‘0’; nhánh phải tương
ứng với mã hoá bit ‘1’
Các nút có tần số thấp nằm ở xa gốc mã bit dài
Các nút có tần số cao nằm ở gần gốc mã bit ngắn
Số nút của cây: (2n-1)
20
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 39
Static Huffman (tt)
// Cấu trúc dữ liệu lưu trữ cây Huffman
#define MAX_NODES 511 // 2*256 - 1
typedef struct {
char c; // ký tự
long nFreq; // trọng số
int nLeft; // cây con trái
int nRight; // cây con phải
} HUFFNode;
HUFFNode HuffTree[MAX_NODES];
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 40
Static Huffman (tt)
Tạo cây Huffman: (tt)
Thuật toán phát sinh cây:
[b1] Chọn trong bảng thống kê 2 phần tử x,y có trọng số thấp nhất
tạo thành nút cha z:
z.c = min(x.c + y.c);
z.nFreq = x.nFreq + y.nFreq;
z.nLeft = x (*)
z.nRight = y (*)
[b2] Loại bỏ nút x và y khỏi bảng;
[b3] Thêm nút z vào bảng;
[b4] Lặp lại bước [b1] - [b3] cho đến khi chỉ còn lại 1 nút duy
nhất trong bảng
(*) Qui ước:
- nút có trọng số nhỏ nằm bên nhánh trái; nút có trọng số lớn nằm bên nhánh phải;
- nếu trọng số bằng nhau, nút có ký tự nhỏ nằm bên nhánh trái; nút có ký tự lớn nằm
bên nhánh phải
- nếu có các node có trọng số bằng nhau ưu tiên xử lý các node có ký tự ASCII
nhỏ trước
21
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 41
Static Huffman (tt)
Minh họa quá trình tạo cây
2E
5D
6C
8B
10 A
SLXHKý
tự
6C
7ED
8B
10 A
SLXHKý
tự
8B
10A
13CED
SLXHKý
tự
13CED
18BA
SLXHKý
tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 42
Static Huffman (tt)
Cây Huffman sau khi tạo
22
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 43
Static Huffman (tt)
Phát sinh mã bit cho các ký tự:
Mã của mỗi ký tự được tạo bằng cách duyệt từ nút gốc đến nút
lá chứa ký tự đó;
Khi duyệt sang trái, tạo ra 1 bit 0;
Khi duyệt sang phải, tạo ra 1 bit 1;
010 E
011D
00C
10B
11A
MãKý
tự
Winter 2006 Data Structure & Algorithm - Data Compression - Nguyen Tri Tuan, DH.KHTN Tp.HCM 44
Static Huffman (tt)
Lưu trữ thông tin dùng để giải nén:
P.Pháp 1: lưu bảng mã bit P.Pháp 2: lưu số lần xuất hiện
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: