Bài giảng môn Cấu trúc dữ liệu và giải thuật| Bài giảng môn Cấu trúc dữ liệu và giải thuật| Trường Đại học Bách Khoa Hà Nội

Cây quyết định là cây:
+ Mỗi nút trong tương ứng với một câu hỏi trên dữ liệu
+ Mỗi nhánh của cây tương ứng với một khả năng trả lời cho một câu hỏi
+ Mỗi nút lá của cây tương ứng với một kết luận

36 18 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

8 trang 1 tháng trước

Tác giả:

Profile Trịnh Thảo Anh
1
Cây quyết định
– Cây quyết định là cây:
z Mỗi nút trong tương ứng vớimộtcâuhỏitrêndữ liệu
z Mỗi nhánh củacâytương ứng vớimộtkhả năng trả lời
cho mộtcâuhỏi
z Mỗi nút lá củacâytương ứng vớimộtkếtluận
– Khi tính toán trên cây quyết định
z Xác định mộtkếtluậnbằng việcbắt đầutừ nút gốc, xác
định một đường đi đếnmột nút lá
z Tại các nút trung gian, việcchọnkhả năng trả lờivớidữ
liệusẽ dẫntađếnmột nút ở mứctiếptheo
Cây quyết định
– Ví dụ : Bài toán tìm kiếm
z Cho mộtmảng A gồmn sốđượcsắpxếp. Xác định xem
mộtgiátrị X có xuấthiện trong A không, nếucóchobiết
vị trí trong mảng A củaX
– Cây quyết định để giải bài toán
z Là cây nhị phân
z Mỗi nút trong biểudiễnmộtcâuhỏidạng X < k ?
z Mỗi nút sát lá biểudiễncâuhỏidạng X = A[i] ?
– Mỗi nút lá tương ứng là mộtgiátrị về vị trí i hoặcgiátrị 0
thể hiệnsự không xuấthiện
2
Cây quyết định – Bài toán tìm kiếm
z A = { 2, 4, 5, 7, 9, 12}
x<7 ?
x< 4 ?
x< 9 ?
x =2?
x<5 ?
x= 4 ? x=5 ?
1
0
2
0
3
0
x =7 ?
x<12?
x =9 ? x =12?
4
0
5
0
6
0
Mã hóa vănbản
z Bài toán mã hóa vănbản:
– Cho mộtvănbản D trên bảng chữ cái C. Cầnmã
hóa vănbản đãcho
z Mã hóa vănbảnvới ASCII
z Mã hóa vănbảnvới độ dài cốđịnh
z Mã hóa vănbảnvới mã phi tiềntố
3
Mã hóa với độ dài cốđịnh
– Ví dụ: Bảng chữ cái tiếng Anh gồm 26 chữ cái,
mã hóa sử dụng mã nhị phân độ dài cốđịnh
z Mã hóa mộtchữ cái sử dụng 5 bit, không phân biệtchữ
hoa chữ thường
– A Æ 00001
– B Æ 00010
– C Æ 00011
– D Æ 00100
– E Æ 00101
– F Æ 00110
– G Æ 00111
– …
z 000110000110100 ÅÆ CAT
Mã Huffman
– Thuộcdạng mã phi tiềntố
z Mã hóa mỗikýtự c sao cho mã củamộtkýtự bấtkỳ
không phảilàđoạn đầucủamãcủamộtkýtự nào trong
số cáckýtự còn lại
– Mã hóa các ký tự sử dụng đoạnmãcóđộ dài
khác nhau
z Ký tự có tầnsuấtxuấthiệnlớnhơnthìđược mã hóa sử
dụng đoạnmãngắnhơn
4
Mã Huffman
– Một mã phi tiềntốđượcbiểudiễnbằng mộtcây
nhị phân
z Các nút lá biểudiễncáckýtự và tầnsuấtxuấthiệncủa
ký tự trong vănbản
z Các nút trong có 2 nhánh tương ứng với : 0 – nhánh
bên trái và 1 – nhánh bên phải. Các nút này chứatổng
tầnsuấtxuấthiệncủa các nút trong các nhánh con của
nó
z Một đường đitừ nút gốc đếnnútláchínhlàmộtmãnhị
phân biểudiễnkýtựởnút lá
z Ký tự có tầnsuấtlớnsẽ xuấthiện ở mứcthấphơn, ký
tự có tầnsuấtnhỏ sẽ xuấthiện ở mứccaohơntrong
cây mã Huffman
Mã Huffman
a: 45
c:
12
b:
13
1
25
0
d:
16
e: 9
f : 5
1
14
0
1
30
0
1
55
0
1
100
0
0
100 101
1100
1101
111
5
Thiếtlập mã Huffman
– Đầu vào: Bảng chữ cái C. Tầnsuấtxuấthiệncủa
các ký tự trong C
– Đầu ra: Cây mã hóa Huffman
– Ý tưởng:
z Dựng cây từ dưới lên, xuất phát với các nút lá
z Tạolậpmột nút nhánh (nút trong) bằng cách nhóm hai
nhánh đãcósẵnmàtầnsuấtcủa hai nhánh đólànhỏ
nhất
ThiếtlậpmãHuffman –Vídụ
a: 45b: 13c: 12 d: 16f: 5 e : 9
Bắt đầu
:
a: 45b: 13c: 12 d: 16
14
f: 5 e : 9
1
0
Bước1
a: 45d: 16
e: 9f: 5
1
14
0
Bước2
c: 12
b: 13
1
25
0
6
ThiếtlậpmãHuffman –Vídụ
a: 45
Bước3
c: 12 b: 13
1
25
0
d: 16
e: 9f : 5
1
14
0
1
30
0
ThiếtlậpmãHuffman –Vídụ
a: 45
Bước4
c: 12 b: 13
1
25
0
d: 16
e: 9f : 5
1
14
0
1
30
0
1
55
0
7
ThiếtlậpmãHuffman –Vídụ
a: 45
Bước5:
c:
12
b:
13
1
25
0
d:
16
e: 9
f : 5
1
14
0
1
30
0
1
55
0
1
100
0
0
100 101
1100
1101
111
Giải mã Huffman
– Xuất phát từ gốccủa cây mã hóa
– Đọclầnlượttừng ký tự trong xâu mã hóa
z Nếulà0 : đi sang trái
z Nếulà1: đi sang phải
– Nếuchạmtớimột nút lá ghi ký tự chứatạinútlá
ra, sau đó quay lạinútgốccủa cây mã hóa.
8
Giải mã Huffman
Xâu ký tự cầngiảimãtheocây
ở bên
111110101100 Æ deaf
a: 45
c:
12
b:
13
1
25
0
d:
16
e: 9
f : 5
1
14
0
1
30
0
1
55
0
1
100
0
0
100 101
1100
1101
111
| 1/8
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Cây quyết định
– Cây quyết định là cây:
z Mỗi nút trong tương ứng với một câu hỏi trên dữ liệu
z Mỗi nhánh của cây tương ứng với một khả năng trả lời cho một câu hỏi
z Mỗi nút lá của cây tương ứng với một kết luận
– Khi tính toán trên cây quyết định
z Xác định một kết luận bằng việc bắt đầu từ nút gốc, xác
định một đường đi đến một nút lá
z Tại các nút trung gian, việc chọn khả năng trả lời với dữ
liệu sẽ dẫn ta đến một nút ở mức tiếp theo Cây quyết định
– Ví dụ : Bài toán tìm kiếm
z Cho một mảng A gồm n số được sắp xếp. Xác định xem
một giá trị X có xuất hiện trong A không, nếu có cho biết
vị trí trong mảng A của X
– Cây quyết định để giải bài toán z Là cây nhị phân
z Mỗi nút trong biểu diễn một câu hỏi dạng X < k ?
z Mỗi nút sát lá biểu diễn câu hỏi dạng X = A[i] ?
– Mỗi nút lá tương ứng là một giá trị về vị trí i hoặc giá trị 0
thể hiện sự không xuất hiện 1
Cây quyết định – Bài toán tìm kiếm
z A = { 2, 4, 5, 7, 9, 12} x<7 ? x<4 ? x<9? x =7 ? x<12? x =2? x<5 ? x=4 ? x=5 ? x =9 ? x =12? 1 0 4 0 2 0 3 0 5 0 6 0 Mã hóa văn bản
z Bài toán mã hóa văn bản :
– Cho một văn bản D trên bảng chữ cái C. Cần mã hóa văn bản đã cho
z Mã hóa văn bản với ASCII
z Mã hóa văn bản với độ dài cố định
z Mã hóa văn bản với mã phi tiền tố 2
Mã hóa với độ dài cố định
– Ví dụ: Bảng chữ cái tiếng Anh gồm 26 chữ cái,
mã hóa sử dụng mã nhị phân độ dài cố định
z Mã hóa một chữ cái sử dụng 5 bit, không phân biệt chữ hoa chữ thường – A Æ 00001 – B Æ 00010 – C Æ 00011 – D Æ 00100 – E Æ 00101 – F Æ 00110 – G Æ 00111 – … z 000110000110100 ÅÆ CAT Mã Huffman
– Thuộc dạng mã phi tiền tố
z Mã hóa mỗi ký tự c sao cho mã của một ký tự bất kỳ
không phải là đoạn đầu của mã của một ký tự nào trong số các ký tự còn lại
– Mã hóa các ký tự sử dụng đoạn mã có độ dài khác nhau
z Ký tự có tần suất xuất hiện lớn hơn thì được mã hóa sử dụng đoạn mã ngắn hơn 3 Mã Huffman
– Một mã phi tiền tố được biểu diễn bằng một cây nhị phân
z Các nút lá biểu diễn các ký tự và tần suất xuất hiện của ký tự trong văn bản
z Các nút trong có 2 nhánh tương ứng với : 0 – nhánh
bên trái và 1 – nhánh bên phải. Các nút này chứa tổng
tần suất xuất hiện của các nút trong các nhánh con của nó
z Một đường đi từ nút gốc đến nút lá chính là một mã nhị
phân biểu diễn ký tự ở nút lá
z Ký tự có tần suất lớn sẽ xuất hiện ở mức thấp hơn, ký
tự có tần suất nhỏ sẽ xuất hiện ở mức cao hơn trong cây mã Huffman Mã Huffman 100 0 1 a: 45 55 0 1 0 25 30 0 0 1 1 c: b: 14 d: 12 13 0 1 16 111 100 101 f :5 e: 9 1100 1101 4
Thiết lập mã Huffman
– Đầu vào: Bảng chữ cái C. Tần suất xuất hiện của các ký tự trong C
– Đầu ra: Cây mã hóa Huffman – Ý tưởng:
z Dựng cây từ dưới lên, xuất phát với các nút lá
z Tạo lập một nút nhánh (nút trong) bằng cách nhóm hai
nhánh đã có sẵn mà tần suất của hai nhánh đó là nhỏ nhất
Thiết lập mã Huffman – Ví dụ Bắt đầu: f: 5 e :9 c: 12 b: 13 d: 16 a: 45 Bước 1 c: 12 b: 13 14 d: 16 a: 45 0 1 f: 5 e :9 Bước 2 14 d: 16 25 a: 45 0 1 0 1 f: 5 e: 9 c: 12 b: 13 5
Thiết lập mã Huffman – Ví dụ Bước 3 25 30 a: 45 0 0 1 1 c: 12 b: 13 14 d: 16 0 1 f :5 e: 9
Thiết lập mã Huffman – Ví dụ Bước 4 a: 45 55 0 1 25 30 0 0 1 1 c: 12 b: 13 14 d: 16 0 1 f :5 e: 9 6
Thiết lập mã Huffman – Ví dụ Bước 5: 100 0 1 a: 45 55 0 1 0 25 30 0 0 1 1 c: b: 14 d: 12 13 0 1 16 111 100 101 f :5 e: 9 1100 1101 Giải mã Huffman
– Xuất phát từ gốc của cây mã hóa
– Đọc lần lượt từng ký tự trong xâu mã hóa z Nếu là 0 : đi sang trái z Nếu là 1: đi sang phải
– Nếu chạm tới một nút lá ghi ký tự chứa tại nút lá
ra, sau đó quay lại nút gốc của cây mã hóa. 7 Giải mã Huffman 100
Xâu ký tự cần giải mã theo cây 0 ở bên 1 111110101100 Æ deaf a: 45 55 0 1 0 25 30 0 0 1 1 c: b: 14 d: 12 13 0 1 16 111 100 101 f :5 e: 9 1100 1101 8