›

Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Bảng Băm - Lê Nguyên Khôi

pdf 19 trang huongle 7690
Download
Bạn đang xem tài liệu "Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Bảng Băm - Lê Nguyên Khôi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_thiet_ke_danh_gia_thuat_toan_bang_bam_le_nguyen_kh.pdf

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Bảng Băm - Lê Nguyên Khôi

  1. ế ế ậ ả ườ ạ ọ ệ
  2. ộ  Ph ươ ng pháp băm  Hàm băm  Gi ải quy ết va ch ạm 1
  3. ừ ể  Dùng tập độ ng cài đặ t từ điển  Mỗi ph ần tử là cặp (khóa, dữ li ệu)  Có th ể tìm theo khóa  Đượ c sắp xếp ho ặc không  Ch ỉ quan tâm tới  Tìm ki ếm SEARCH (, )  Chèn INSERT (, )  Xóa DELETE (, )  Tổ ch ức cấu trúc dữ li ệu nh ư th ế nào? 2
  4. ừ ể  Nếu khóa của dữ li ệu là số nguyên không âm trong kho ảng 0 − 1 , phân bi ệt  Có th ể sử dụng mảng cỡ  Dữ li ệu khóa lưu tại  Tìm ki ếm, chèn, xóa trong th ời gian (1)  Th ực tế không kh ả thi  Số ph ần tử dữ li ệu có th ể rất nh ỏ so với  số 64-bit th ể hi ện 2 (18 × 10 ) khóa khác nhau  Xâu ký tự th ậm chí còn lớn hơn  Khóa có th ể không ph ải số nguyên  Tận dụng phép truy cập tr ực ti ếp của mảng 3
  5. ươ  Lưu dữ li ệu trong mảng 0 − 1  Hàm băm ℎ: ánh xạ mỗi giá tr ị khóa của dữ li ệu tới một ch ỉ số (0 ≤ < )  Dữ li ệu sẽ đượ c lưu trong []  ℎ: →{0,1, ,−1} 0 1 Tính đị a ch ỉ i Hàm băm ℎ − 1 Tập các giá tr ị khoá Mảng 4
  6. ươ  Nếu có ≠ thì ℎ() ≠ ℎ(), và tính ch ỉ số ℎ() trong th ời gian (1)  thì các phép toán tìm ki ếm, chèn, xóa cũng trong th ời gian (1)  Tuy nhiên, th ườ ng xảy ra va ch ạm  Chèn khóa vào vị trí đã có khóa khác  Th ực tế ≠ có th ể cho ℎ = ℎ() 5
  7.  Khó xác đị nh ph ươ ng pháp băm đồ ng đề u đơ n gi ản.  Hàm băm tốt  Phân bố khóa đồ ng đề u vào các vị trí  Tính nhanh & dễ dàng  Đả m bảo ít va ch ạm  Khóa là số nguyên không âm  Ph ươ ng pháp chia  Ph ươ ng pháp nhân  Khóa là xâu ký tự  Đổ i xâu thành số nguyên không âm 6
  8. ươ a ℎ = mod  Nh ạy cảm với cỡ của bảng băm ()  Ch ọn để hạn ch ế xảy ra va ch ạm  Không ch ọn có ướ c số nh ỏ  Số nguyên tố có dạng đặ c bi ết, ví d ụ + 3  Ví dụ: nếu = 2, hàm băm không ph ụ thu ộc vào tất cả các bit của  = 1011000111 và = 6, thì ℎ = 7
  9. ươ = 2, với máy tính -bit. Hàm băm: ℎ()=( · mod2)rsh(– )  rsh là toán tử “bitwise right-shift”  Toán tử rsh nhanh  là số lẻ trong kho ảng 2 < < 2  Không ch ọn quá gần 2 ho ặc 2  Phép nhân và phép chia dư 2 nhanh hơn phép chia 8
  10. ươ ℎ()=( · mod2)rsh(– )  = 2 = 8 = 2 với máy tính = 7-bit 1011001 = 1101011 = 1001010 011 0011 ℎ = 011 9
  11. ự  Đổ i ký tự thành số nguyên (bảng ASCII)  Khi đó xâu ký tự là số trong hệ cơ số 128  Chuy ển sang hệ 10  Nh ượ c điểm: xâu dài cho kết qu ả vượ t quá kh ả năng bi ểu di ễn của máy tính  Cải ti ến:  Xâu ký tự th ườ ng đượ c tạo thành từ 26 ch ữ cái, 10 ch ữ số, và một số ký tự khác  Thay 128 thành 37 10
  12. ả ế a ạ  Nếu dữ li ệu với khóa đã đượ c lưu tại với ℎ = . Cần thêm dữ li ệu với khóa  Nếu ℎ = , x ảy ra va ch ạm, lưu ở đâu?  Các ph ươ ng pháp  Dây chuy ền Tạo một danh sách lưu tất cả dữ li ệu có cùng vị trí  Đị a ch ỉ mở Tìm vị trí khác còn tr ống trong bảng và cho dữ li ệu mới vào đó 11
  13. ả ế a ạ ề  Tại mỗi vị trí trong bảng băm là một danh sách liên kết các dữ li ệu có cùng giá tr ị băm Hàm băm  Ưu điểm:  Số dữ li ệu lưu không ph ụ thu ộc vào cỡ của mảng  Th ời gian các phép toán tìm ki ếm, chèn, xóa? 12
  14. ề ờ a  Tr ườ ng hợp xấu nh ất:  Tất cả các khóa đượ c băm vào cùng vị trí  Th ời gian tìm ki ếm  Tr ườ ng hợp trung bình:  Mỗi khóa có th ể đượ c băm vào bất cứ vị trí nào trong , độ c lập với vi ệc các khóa khác đượ c băm nh ư th ế nào 13
  15. ề  Tr ườ ng hợp trung bình: băm đồ ng đề u số lượ ng khóa trong bảng độ lớn của bảng Hệ số tải của bảng băm = = số lượ ng khóa trung bình tại mỗi vị trí trong bảng băm 14
  16. ề ế Th ời gian tìm ki ếm không thành công = 1 + Hàm băm Tìm ki ếm Truy cập vị trí danh sách Th ời gian tìm ki ếm là 1 nếu = 1 Th ời gian tìm ki ếm thành công có ti ệm cận tươ ng tự 15
  17. ả ế a ạ ịa ỉ ở  Khi xảy ra va ch ạm, tìm vị trí khác còn tr ống trong bảng và cho dữ li ệu mới vào đó  Dãy các vị trí đượ c tìm gọi là dãy th ăm dò  Bảng băm có th ể bị đầ y  Xác đị nh dãy th ăm dò  Tuy ến tính  Dãy th ăm dò: , + 1, + 2,  Bình ph ươ ng  Dãy th ăm dò: , + 1 , + 2 ,  Băm kép  Dãy th ăm dò: ℎ() + ℎ() với = 0,1,2, 16
  18. ậ = 11 , Ph ươ ng pháp chia, Th ăm dò tuy ến tính insert(388) search(47) insert(130) delete(926) insert(13) search(47) insert(14) delete(388) insert(926) search(926) insert(47) 17
  19. ậ  Tuy ến tính  Ưu điểm: xét tất cả các vị trí trong mảng  Phép chèn luôn th ực hi ện đượ c, tr ừ khi mảng đầ y  Nh ượ c điểm:  Dữ li ệu tập trung thành các đoạn  Tìm ki ếm tu ần tự trong từng đoạn  Bình ph ươ ng  Ưu điểm: tránh nh ượ c điểm th ăm dò tuy ến tính  Nh ượ c điểm: không xét tất cả các vị trí trong mảng  Phép chèn có th ể không th ực hi ện đượ c  Băm kép  Nếu cỡ của mảng và bướ c th ăm dò ℎ() nguyên tố cùng nhau thì cho phép tìm đế n tất cả các vị trí trong mảng 18