Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 6: Tìm kiếm nâng cao

4/7/2011

Nội dung

Chương 6

 Bảng băm

Tìm kiếm

(phần 2)

 Một số phương pháp xây dựng hàm băm

 Đụng độ và khắc phục

 Bài tập

Hiepnd@it-hut.edu.vn

Băm

 Các phương pháp tìm kiếm :

 Tìm kiếm tuần tự: O(n)

 Ý tưởng bảng băm:

 Dùng mảng lưu trữ các phần tử (bảng)

 Tìm kiếm nhị phân O(logn)

 Mỗi phần tử sẽ được lưu tại một ô duy nhất trong

bảng căn cứ vào giá trị khóa của nó,

 Khi tìm kiếm thì căn cứ vào khóa cần tìm ta tìm đến ô

tương ứng

 Phương pháp tổ chức dữ liệu để tìm kiếm nào tốt hơn ?

 Nếu ô đó có chứa phần tử thì tìm thấy, ngược lại là

không tìm thấy

Bảng băm

1

4/7/2011

Băm

 VD. Sinhvien(1222, ‘Nguyễn văn A’, ‘Hà Nội’)

Sinhvien(1101,’Trần văn C’,’Thái Bình’)

Sinhvien(0097, ‘Nguyễn văn A’, ‘Hà Nội’)

Sinhvien(1331,’Trần văn C’,’Thái Bình’)

Sinhvien(1345, ‘Nguyễn văn A’, ‘Hà Nội’)

 Tốt hơn tìm kiếm tuần tự khi mà dữ liệu được lưu trữ không

có thứ tự.

 Không dựa trên so sánh giá trị các khóa của bản ghi mà dựa

trên chính bản thân giá trị các khóa.

 Sử dụng bảng kích thước 100 để lưu các phần tử

 Từ giá trị khóa ta tính ra một địa chỉ(địa chỉ tương đối) theo

một quy tắc nào đó. Địa chỉ này sẽ dùng để lưu trữ bản ghi

và cũng để tìm kiếm bản ghi đó.

1

Sinhvien(1101,’Trần văn C’,’Thái Bình’)

Sinhvien(1222, ‘Nguyễn văn A’, ‘Hà Nội’)

Sinhvien(1331,’Trần văn C’,’Thái Bình’)

Sinhvien(1345, ‘Nguyễn văn A’, ‘Hà Nội’)

Sinhvien(0097, ‘Nguyễn văn A’, ‘Hà Nội’)

…

Chỉ

số

mảng

22

…

hash function: key  an index

Địa chỉ lưu trữ

31

…

 Hàm băm hoàn hảo: mỗi khóa ứng với một giá trị nguyên

duy nhất

35

…

 Thời gian tìm kiếm O(1) ???

97

Băm

 Hàm băm:

 Tính toán dễ và nhanh

 Gấp (folding): chia khóa thành nhiều phần sau đó kết

hợp các phần lại (thường dùng cộng hoặc nhân)

 Phân phối đều các khóa

VD. 21296876 chia thành 3 phần 212, 968 và 76

kết hợp 212+968+76 = 1256, cắt bỏ được 256

Một số phương pháp thông dụng:

 Cắt bỏ (Truncation) : dùng một phần của khóa làm chỉ

số

Giá trị các thành phần trong khóa đều ảnh hưởng tới chỉ

số. Cho phân phối tốt hơn phương pháp cắt bỏ

VD: khóa có 8 chữ số và bảng băm kích thước 1000

lấy chữ số thứ 4, 7 và 8 làm chỉ số

21296876 976

Nhanh nhưng phân bố khóa không đều!

2

4/7/2011

Băm

 Phương pháp chia module: lấy số dư của phép chia giá

trị khóa cho kích thước của bảng băm để làm đị chỉ

 Phương pháp nhân: giá trị khóa được nhân với chính

nó, sau đó lấy một phần kết quả để làm địa chỉ băm

h(k) = k % m

Giá trị khóa k

k*k

địa chỉ

 Thường chọn m là số nguyên tố nhỏ hơn, gần với kích

thước bảng băm.

5402

367

1246

2983

29181604

00134689

01552516

08898289

181

134

552

898

 Bảng băm kích thước 1000 thì chọn m=997

Giá trị khóa

5402

địa chỉ

417

367

1246

249

2983

989

Băm

Phương pháp đánh địa chỉ mở

Phương pháp đánh địa chỉ mở - Open Addressing

 Đụng độ: hai khóa khác nhau có cùng

giá trị chỉ số

 Dò tuyến tính(Linear Probing): tại vị trí đụng độ, thực

hiện tìm kiếm tuần tự để tìm ra khóa (khi tìm kiếm) hoặc

vị trí trống (khi thêm mới)

VD: hai khóa 21296876, 11391176

Trong hàm băm dùng phương pháp cắt bỏ

VD: hàm băm

 Giải pháp xử lý đụng độ:

i=k%10

 Phương pháp đánh địa chỉ mở (Open Addressing)

 Phương pháp xích ngăn cách (Separate Chaining)

Các khóa {89, 18, 49, 58, 69} được thêm lần lượt vào

bảng băm ban đầu rỗng

3

4/7/2011

Phương pháp đánh địa chỉ mở

stt Ban đầu Thêm 89 Thêm 18 Thêm 49 Thêm 58 Thêm 69

 Dò tuyến tính

0

1

2

3

4

5

6

7

8

9

49

49(*) 49(*)

 Xu hướng tạo thành các cụm khi bảng bắt đầu gần

đầy nửa

58

58(*)

69

 Vị trí lưu trữ của khóa trong bảng và giá trị chỉ số

ngày càng cách nhau xa, chi phí thực hiện tìm kiếm

tuần tự ngày càng lớn

 Khắc phục: sử dụng các phương pháp lựa chọn vị trí

phức tạp khi xảy ra đụng độ

VD. Phương pháp băm lại (rehashing) sử dụng hàm băm

thứ 2 để tạo chỉ số khi xảy ra đụng độ, nếu lại đụng độ thì

sử dụng hàm băm thứ 3 ….

18

89

18

18(*) 18

89

89(*) 89(*) 89(*)

Phương pháp đánh địa chỉ mở

stt Ban đầu Thêm 89 Thêm 18 Thêm 49 Thêm 58 Thêm 69

 Dò bậc hai, dò toàn phương (Quadratic Probing): nếu

xảy ra đụng độ tại địa chỉ h, thì ta sẽ tìm kiếm tiếp theo tại

các địa chỉ h+1, h+4, h+9,.. ; là các địa chỉ h+i²

0

1

2

49

58

49(*)

58

69

3

4

5

6

7

8

9

VD: hàm băm

i=k%10

Các khóa {89, 18, 49, 58, 69} được thêm lần lượt vào

bảng băm ban đầu rỗng

18

89

18

18(*) 18

89

89(*) 89(*) 89(*)

4

4/7/2011

Phương pháp đánh địa chỉ mở

 Dò toàn phương:

 Dò theo khóa: trong trường hợp đụng độ tại h thì dò tiếp

tại vị trí cách vị trí đó khoảng cách bằng giá trị phần tử

tiên trong khóa (là số hoặc là mã ASCII).

 Giảm được sự phân nhóm

 Không phải tất cả các vị trí trong bảng đều được dò

 Ví dụ: nếu khóa 2918160 xảy ra đụng độ thì dò tại ô tiếp

theo cách ô đụng độ 2 vị trí

VD. Khi kích thước bảng là mũ của 2 thì 1/6 vị trí

được dò, là số nguyên tố thì 1/2 được dò

Phương pháp đánh địa chỉ mở

 Dò ngẫu nhiên (Random Probing): sử dụng cách sinh số

giả “ngẫu nhiên” để tạo ra vị trí dò tiếp. Cách sinh này phải

là duy nhất với 1 giá trị khóa.

 Chú ý: không thể xóa phần tử trong bảng băm sử dụng

phương pháp đánh địa chỉ mở theo cách thông thường!

 đánh dấu là xóa, nhưng vẫn được xét đến khi dò!

 Ví dụ: khóa 123245 thì sinh ra số ngẫu nhiên duy nhất là 5

5

4/7/2011

Giải pháp xử lý đụng độ

Băm

Phương pháp xích ngăn cách (Separate Chaining)

 Dùng mảng của danh sách

móc nối

 Hàm băm tương ứng của số có 3 chữ số ( a1 a2 a3 ) là

mod (a1 + a2 + a3 , 5 ). Với các tổ hợp số dưới đây, giá

trị băm bị xung đột là trường hợp nào?

 Ưu điểm:

A. 881 và 509

B. 913 và 426

C. 731 và 429

D. 102 và 297

E. 677 và 388

 không bị giới hạn số

phần tử,

 Dễ thêm và xóa

 xử lý đụng độ tốt

 Nhược điểm :

 Phải lưu nhiều con trỏ NULL

 Thực hiện tìm kiếm tuyến tính nên thời gian tìm kiếm

chậm

mod: chia lấy phần dư

mod(5,3) = 2

Băm

Bài 2. Cho bảng băm với kích thước 13, chỉ số các phần

tử từ 0 đến 12, và dãy khóa

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

a) Sử dụng hàm băm i=k%13, vẽ các bước khi thêm

các khóa vào bảng sử dụng phương pháp xử lý

đụng độ là dò tuyến tính và dò bậc hai.

b) Sử dụng hàm băm là tổng của các chữ số trong

khóa chia lấy dư cho 13, vẽ lại bảng băm với hai

phương pháp xử lý đụng độ như phần a

c) Tìm một hàm băm mà không xảy ra đụng độ cho

dãy khóa trên

6

Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 6: Tìm kiếm nâng cao - Nguyễn Duy Hiệp