Tài liệu Ti29

CHUYÊN ĐÊỀ HỘI THẢO KHOA HỌC CÁC TRƯỜNG THPT CHUYÊN KHU VỰC DUYÊN HẢI & ĐỒỀNG BẰỀNG BẰẮC BỘ NẰM 2016 CHUYÊN ĐỀ . MẢNG BĂM A, MỞ ĐẦU 1. Lý do chọn đề tài Các thuật toán tìm kiếm trên các cấu trúc dữ liệu như: danh sách, cây nhị phân, … phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh ( O(n), O(logn), …) và phụ thuộc vào kích thước của cấu trúc. Vậy có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không (độ phức tạp hằng số)? Các phép toán trên mảng băm sẽ giúp hạn chế số lần so sánh, giảm thiếu thời gian truy xuất. Độ phức tạp các phép toán trên mảng băm thường là O(1) và không phụ thuộc vào kích thước của mảng băm. Ví dụ, nếu chúng ta có một mảng nhiều nhất 100 phần tử. Nếu chúng ta biết vị trí mà một phần tử cụ thể được lưu trữ trong mảng, sau đó chúng ta có thể nhanh chóng truy cập vào nó. Chẳng hạn, chúng ta biết rằng các phần tử chúng ta muốn tìm là ở vị trí 3. Ta có thể áp dụng: myItem = myarray [3]. Với điều này, chúng ta không cần phải tìm kiếm thông qua từng phần tử trong mảng, chúng ta chỉ cần truy cập vị trí 3. Câu hỏi đặt ra là, làm thế nào chúng ta biết vị trí 3 chứa dữ liệu mà chúng ta quan tâm? Chúng ta có thể áp dụng một hàm băm để tìm một chỉ số hoặc vị trí mà chúng ta muốn truy cập. Mảng băm thường được sử dụng khi xử lý các bài toán có kích thước dữ liệu lớn. Tuy nhiên trong quá trình giảng dạy tôi thấy học sinh vẫn còn khó khăn trong việc hiểu và cài đặt mảng băm để giải quyết bài toán. Vì vậy trong chuyên đề này tôi mong muốn giúp học sinh có cái nhìn tổng quan hơn về mảng băm và ứng dụng của mảng băm trong giải một số bài toán cụ thể. 2. Mục đích của đề tài Về nội dung kiến thức mảng băm còn chưa được trình bày nhiều trong các tài liệu, trong chuyên đề này tôi sẽ tổng hợp lại các nội dung kiến thức về mảng băm và áp dụng để giải một số bài toán cụ thế, để làm tài liệu tham khảo cho học sinh và giáo viên trong quá trình học tập và giảng dạy các đội tuyển học sinh giỏi. B. NỘI DUNG I. Lý thuyết 1. Hàm băm (tiếng Anh: Hash function) Hàm được dùng để ánh xạ một khoá (key) vào một dãy các số nguyên và dùng các giá trị nguyên này để truy xuất dữ liệu được gọi là hàm băm. Khóa có thể là dạng số hay dạng chuỗi. Có nhiều hàm băm khác nhau. Một số hàm băm biến đổi một khóa số nguyên thành một chỉ số của mảng. Một trong những phương pháp băm phổ biến nhất là phương pháp chia (Division). 2. Mảng băm Mảng băm là một cấu trúc dữ liệu sử dụng hàm băm để ánh xạ từ giá trị xác định, được gọi là khóa, đến giá trị tương ứng. Hàm băm được sử dụng để chuyển đổi từ khóa thành chỉ số (giá trị băm) trong mảng lưu trữ các giá trị tìm kiếm. Hàm băm thường được dùng trong mảng băm nhằm giảm chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh các giá trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thước lớn). a. Mô tả dữ liệu Giả sử • K: tập các khoá (set of keys) • A: tập các địa chỉ (set of addresses) • H(k): hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập A. b. Một số phép toán trên mảng băm • Khởi tạo (Initialize) val new : int -> hashtable (* New(N) tạo ra một bảng băm với n phần tử *) • Lấy kích thước của mảng băm (Size) val sizetable : hashtab • Tìm kiếm (Search) val Search : hashtable * key -> value option (* Search(ht,key) trả về tương ứng một số giá trị nếu được tìm thấy trong hashtable, nếu không trả về NONE *) • Thêm mới phần tử (Insert) val insert : hashtable * key * value -> unit • Loại bỏ (remove) val remove : hashtable * key -> unit (* remove(ht,key) loại bỏ khóa và giá trị của nó nếu có, Nếu không thì không có tác dụng *) c. Phân loại mảng băm • Mảng băm đóng : mỗi khóa ứng với một địa chỉ, thời gian truy xuất là hằng số • Mảng băm mở : một số khóa có cùng địa chỉ, lúc này mỗi mục địa chỉ sẽ là một danh sách liên kết các phần tử có cùng địa chỉ, thời gian truy xuất có thể bị suy giảm đôi chút. 3. Phương pháp chia (một phương pháp băm cho các số nguyên) Giả sử ta có các khóa sau cần ánh xạ vào một mảng có 10 phần tử 123456 123467 123450 Để áp dụng các phương pháp chia, có thể chia cho 10 (hoặc số tối đa các phần tử trong mảng) và sử dụng phần dư (modulo) là một chỉ số. Sau đây là kết quả: 123456 % 10 = 6 (phần dư là 6) 123.467 % 10 = 7 (phần dư là 7) 123.450 % 10 = 0 (phần dư là 0) Những con số này sẽ được chèn vào mảng tại vị trí 6, 7, và 0 tương ứng.  Điều quan trọng với phương pháp chia là các khóa là các số nguyên. Thường chọn kích thước mảng M là số nguyên tố. Hàm này rất dễ để tính, và có hiệu quả trong phân tán các khóa đều giữa 0 và M-1. Đối với các số không là số nguyên. Ta phải áp dụng một hàm băm để biến chúng thành các số nguyên. Vậy có hai hàm băm: 1. Hàm để có được một số nguyên 2. Hàm để áp dụng một hàm băm từ trên để có được một chỉ số trong một mảng   Số dấu chấm động. Nếu các khóa số thực giữa 0 và 1, chúng ta có thể nhân với M và làm tròn đến số nguyên gần nhất để có được một chỉ số giữa 0 và M-1. Mặc dù trực quan, nhưng phương pháp này là chưa hiệu quả. Một cách khác để giải quyết tình trạng này là sử dụng băm modular trên biểu diễn nhị phân của khóa Strings Chúng ta chỉ đơn giản tính thành số nguyên lớn. Hàm băm biến đổi khoá dạng chuỗi gồm n kí tự thành 1 địa chỉ (số nguyên) có thể được viết như sau: 1. int hashfunc( char *s, int n ) 2. { 3. int sum = 0; 4. while( n-- ) sum = sum + *s++; 5. return sum % 256; 6. } Địa chỉ của khoá "AB" : hashfunc("AB",2) là 131 Địa chỉ của khoá "BA" : hashfunc("BA",2) là 131 Khi hàm băm hai khoá vào cùng một địa chỉ thì gọi là đụng độ (Collision) Hàm băm tốt thỏa mãn các điều kiện sau: • Tính toán nhanh. • Các khoá được phân bố đều trong bảng. • Ít xảy ra đụng độ Ví dụ Khóa là tên của một số người sau: Sarah Jones Tony Balognie Tom Katz Các hàm băm phải làm hai việc:  Chuyển đổi tên thành các số nguyên Ví dụ, chúng ta có một hàm mà biến một chuỗi thành một số nguyên. Kết quả sẽ như sau: Sarah Jones -> 1038 Tony Balognie -> 1259 Tom Katz -> 746  Áp dụng một hàm băm để có được một chỉ số Bây giờ chúng ta có thể áp dụng phương pháp chia để có được một chỉ số cho một mảng có 10 phần tử Sarah Jones -> 1038% 10 -> 8 Tony Balognie -> 1259% 10 -> 9 Tom Katz -> 746% 10 -> 6 Mảng được biết đến như một mảng băm. Nó lưu trữ khóa (được sử dụng để tìm index) cùng với các giá trị liên quan. Một vấn đề xảy ra khi hai khóa mang chỉ số giống nhau. Ví dụ: John Smith -> 948% 10 -> 8 Chúng ta có một sự đụng độ (collision) vì Sarah Jones đã được lưu trữ tại chỉ số 8. Chúng ta cần một phương pháp để giải quyết điều này. Các cách tiếp cận chính là 1. Phương pháp nối kết (chaining) tạo ra một cấu trúc dữ liệu lưu giữ tất cả các dữ liệu có cùng vị trí i và “gắn” cấu trúc dữ liệu này vào vị trí đó trong mảng 2. Phương pháp định địa chỉ mở (open addressing/probing): mỗi khi xảy ra va chạm, tiến hành thăm dò để tìm một vị trí còn trống trong mảng và đặt dữ liệu mới vào đó. Giả sử vị trí ứng với khoá k là i, i=h(k). Từ vị trí này chúng ta lần lượt xem xét các vị trí i0 , i1 , i2 ,…, im ,… Trong đó i0 = i, im (m=0,1,2, …) là vị trí thăm dò ở lần thứ m. Dãy các vị trí này sẽ được gọi là dãy thăm dò. Phương pháp này có các phương pháp cụ thể sau:  Phương pháp dò tuyến tính (Linear Probing)  Phương pháp dò bậc hai (Quadratic Probing Method)  Phương pháp băm đôi (Double hashing)  Phương pháp nối kết Chaining là một cách để giải quyết đụng độ. Mỗi ô của mảng có chứa một liên kết đến một danh sách liên kết có chứa cặp khóa-giá trị. Cặp khóa-giá trị mới được thêm vào cuối danh sách. Thuật toán tìm kiếm thông qua danh sách để tìm khóa phù hợp. Ban đầu mỗi ô của mảng được khởi tạo null. Danh sách được tạo ra khi giá trị băm nào đó được thêm vào lần đầu tiên. Xem sơ đồ của ví dụ trên (hình bên). Có một sự đụng độ giữa Sarah Jones và John Smith. Chú ý rằng John Smith là "liên kết" sau Sarah Jones. Ưu điểm : Số dữ liệu được lưu không phụ thuộc vào cỡ của mảng Nhược điểm: Chèn chậm Cài đặt mảng băm dùng phương pháp nối kết:  Khai báo cấu trúc mảng băm: define M 100 struct nodes { int key; struct nodes *next }; //khai bao kieu con tro chi nut typedef struct nodes *NODEPTR /* khai bao mang bucket chua M con tro dau cua M bucket */ NODEPTR bucket[M];  Các phép toán Giả sử ta chọn hàm băm: h(key) = key % M int hashfunc (int key) { return (key % M); } Phép toán khởi tạo void initbuckets( ) { int b; for (b=0;bkey !=k) { q=p; p=p->next; } if (p == NULL) printf("\n khong co nut co khoa %d" ,k); else if (p == bucket [b]) pop(b); //Tac vu pop cua danh sach lien ket else delafter(q); /*tac vu delafter cua danh sach lien ket*/ } Phép toán traversebucket: Duyệt các phần tử trong bucket b. void traversebucket (int b) { NODEPTR p; p= bucket[b]; while (p !=NULL) { printf("%3d", p->key); p= p->next; } } Phép toán traverse: Duyệt toàn bộ bảng băm. void traverse( ) { int b; for (b = 0;n p->key && p !=NULL) p=p->next; if (p == NULL | | k !=p->key)// khong tim thay return(NULL); else//tim thay // else //tim thay return(p); }  Phương pháp định địa chỉ mở  Linear Probing là cấu trúc dữ liệu chứa một tập các cặp khóa-giá trị . Mỗi ô của mảng băm lưu trữ một cặp khóa-giá trị duy nhất. Khi hàm băm gây ra một vụ đụng độ bằng cách ánh xạ một khóa mới cho một ô của mảng băm đã được chiếm giữ bởi một khóa, Linear Probing tìm kiếm mảng cho vị trí trống tiếp theo gần nhất và chèn khóa mới tại đó. Thuật toán tìm kiếm được thực hiện tương tự, bằng cách tìm kiếm mảng tuần tự bắt đầu tại vị trí nhất định bởi hàm băm, cho đến khi tìm ra một ô với một khóa khớp hoặc một ô trống. F(i) = i, F(i) là hàm tuyến tính của i hoặc ta có thể viết: hi(k) = (h(k) + i) mod size. Cụ thể: h(k) mod size h(k)+1 mod size h(k)+2 mod size …. Đoạn chương trình tìm ô trống tiếp theo gần nhất Bool findEntry(const Key &k, Entry *& entry) { int probePoint = hash1(k); do { entry = &table[probePoint]; probePoint = (probePoint+1) % size; } while (!entry->isEmpty() && entry->key !=k); return !entry->isEmpty(); } Ví dụ: Vẽ quá trình hiển thị các giá trị: 76, 93, 40, 47, 10, 55 được đưa vào một mảng băm với 7 vị trí. Sử dụng phương pháp chia của băm và phương pháp Linear Probing giải quyết va chạm.  Ưu điểm: đơn giản, cho phép xét tất cả các vị trí trong mảng, phép insert luôn được thực hiện trừ khi mảng đầy.  Nhược điểm: phần tử tụm lại không phân đều tập trung thành các đoạn, sử dụng Θ (m) hoán vị của chuỗi chỉ số địa chỉ, tìm kiếm tuần tự trong từng đoạn  Bảng băm với phương pháp dò bậc hai (Quadratic Probing Method) Phương pháp dò bậc hai hoạt động bằng cách lấy chỉ số băm gốc và truy xuất các chỉ số kế tiếp bằng một đa thức bậc hai cho đến khi tìm thấy một chỉ số của ô trống. Nếu dò đến cuối mảng thì trở lại dò từ đầu mảng. Giả sử h(k) là một hàm băm mà ánh xạ một phần tử k vào một tập số nguyên [0,m-1], m là kích thước của mảng. Dò vị trí thứ i cho giá trị k bởi hàm: h i(k) = (h(k)+i2) mod m. m nên chọn là số nguyên tố Đối với một giá trị băm cho trước, các chỉ số được tạo ra bởi dò tuyến tính như sau: h, h+1, h+2, h+3, …, h+k. Việc tìm kiếm những giá trị băm trở nên kém hiệu quả Các chỉ số được tạo ra bởi phương pháp dò bậc hai: h, h+1 2, h+22, h+32, …, h+k2. Ví dụ chuỗi dò: +0, +1, +4, +9, +16, … Đoạn mã tìm ô trống tiếp theo bằng cách sử dụng phương pháp Quadratic probing: bool findEntry(const Key & k, Entry *& entry) { int probePoint = hash1(k), numProbes = 0; do { entry = &table[probePoint]; numProbes++; probePoint = (probePoint+2*numProbes - 1) % size; } while (!entry->isEmpty() && entry->key !=k); return !entry->isEmpty(); } Ví dụ 1: Vẽ quá trình các giá trị: 76, 40, 48, 5, 55 được đưa vào một mảng băm với 7 vị trí. Sử dụng phương pháp chia của băm và phương pháp Quadratic Probing giải quyết va chạm. Ví dụ 2: Vẽ quá trình các giá trị: 76, 93, 40, 35, 47 được đưa vào một mảng băm với 7 vị trí. Sử dụng phương pháp chia của băm và phương pháp Quadratic Probing giải quyết va chạm.  Ưu điểm: tránh được nhược điểm của dò tuyến tính.  Nhược điểm: không cho phép tìm đến tất cả các vị trí trong mảng, phép insert có thể không được thực hiện, nếu cỡ của mảng là số nguyên tố thì dò bình phương tìm đến một nửa số vị trí trong mảng.  Phương pháp băm đôi (Double hasing method) Phương pháp băm đôi được sử dụng trong mảng băm để giải quyết va chạm băm. Băm đôi được thực hiện ở nhiều thư viện. Giống như dò tuyến tính, nó sử dụng một giá trị băm là điểm khởi đầu và sau đó liên tục truy xuất các chỉ số kế tiếp cho đến khi giá trị mong muốn nằm tại vị trí trống được đạt tới, hoặc toàn mảng đã được tìm kiếm, nhưng chỉ số kế tiếp này được tính bởi một hàm băm độc lập thứ hai (do đó tên là băm đôi). Chọn hai hàm băm h1 và h2 độc lập, vị trí thứ i trong chuỗi ô chèn giá trị k trong một mảng băm kích thước m là: h(i,k) = (h1(k) + i.h2(k)) mod m. Cụ thể: h1(k) mod m (h1(k)+1.h2(x)) mod m (h1(k)+2.h2(x)) mod m … m nên chọn là số nguyên tố. Hàm băm thứ hai nên chọn là hàm dễ dàng tính toán, khác so với hàm thứ nhất và không được bằng 0. Một cách chọn tốt là chọn số nguyên tố R < m và h2(x) = R – (x mod R). Đoạn mã tìm ô trống tiếp theo bằng Double hasing: bool findEntry(const Key & k, Entry *& entry) { int probePoint = hash1(k), hashIncr = hash2(k); do { entry = &table[probePoint]; probePoint = (probePoint + hashIncr) % size; } while (!entry->isEmpty() && entry->key != k); return !entry->isEmpty(); } Ví dụ: Vẽ quá trình các giá trị: 76, 93, 40, 47, 10, 55 được đưa vào một mảng băm với 7 vị trí. Sử dụng phương pháp chia của băm và phương pháp Double hasing giải quyết va chạm. Với h1(key) = key mod m, h2(key) = 5- (key mod 5), h(k,i) = (h1(k) + ih2(k)) mod m.  Ưu điểm: phân bố đều hơn, nếu cỡ của mảng và bước thăm dò h2(k) nguyên tố cùng nhau thì phương pháp băm kép cho phép tìm đến tất cả các vị trí trong mảng Chọn kích thước mảng băm Các kích thước tốt nhất để lựa chọn cho mảng băm sẽ phụ thuộc vào số lượng dự kiến của các giá trị đó sẽ được lưu trữ và quan trọng như thế nào sử dụng hết không gian. Ta có thể sử dụng một mảng mà lớn hơn một chút so với số lượng dự kiến của các phần tử (1,25 lần so với số lượng dự kiến). 4. Các ứng dụng của một mảng băm Mảng băm thường được sử dụng trong trường hợp có một lượng lớn dữ liệu mà từ đó ta muốn nhanh chóng tìm kiếm và lấy thông tin. Một vài ứng dụng mảng băm điển hình sau đây: Đối với hồ sơ cấp giấy phép lái xe. Với một mảng băm, bạn có thể nhanh chóng có được thông tin về lái xe (tên, địa chỉ, tuổi.) cho các số giấy phép.  Đối với các bảng biểu tượng trình biên dịch. Trình biên dịch sử dụng một bảng ký hiệu để theo dõi những biểu tượng người dùng định nghĩa trong một chương trình C ++. Điều này cho phép trình biên dịch nhanh chóng tìm kiếm các thuộc tính liên quan với các biểu tượng (ví dụ, tên biến)  Đối với cơ sở dữ liệu danh bạ điện thoại. Bạn có thể sử dụng một mảng băm để nhanh chóng tìm số điện thoại của John Smith.  Đối với danh mục thư viện điện tử. Triển khai mảng băm cho phép tìm kiếm nhanh trong số hàng triệu tài liệu được lưu trữ trong thư viện.  Đối với việc thực hiện mật khẩu cho hệ thống với nhiều người sử dụng. Mảng băm cho phép tìm kiếm nhanh chóng các mật khẩu tương ứng với một tên người dùng nhất định.  Mảng băm dùng để giải các bài toán so khớp xâu.  Giả sử chúng ta có một ứng dụng mà các khóa là số an sinh xã hội Mỹ. Một số an sinh xã hội như 123-45-6789 là một số gồm 9 chữ số chia thành ba trường. Trường đầu tiên xác định các khu vực địa lý mà số được cấp (đối với số trường đầu tiên là 035 đến từ đảo Rhode và số trường đầu tiên là 214 đến từ Maryland) và hai trường khác xác định thông tin cá nhân. Có một tỉ số an sinh xã hội khác nhau, nhưng giả sử rằng ứng dụng của chúng ta cần phải xử lý chỉ là một vài trăm khóa, vì vậy mà chúng ta có thể sử dụng một mảng băm có kích thước M = 1000. Sử dụng tất cả chín chữ số để làm cho một giá trị int, sau đó xem xét các hàm băm cho các số nguyên. 5. Nhận xét thời gian tìm kiếm, chèn và xóa Để tìm một khóa k trong một mảng băm, ta tính toán giá trị hàm băm (v = hash (k)), sau đó xem nếu k là trong mảng. Thời gian tìm kiếm sẽ được tỷ lệ thuận với thời gian cho các hàm băm, cộng thêm thời gian để tìm kiếm k trong cấu trúc dữ liệu mảng. Trong trường hợp tốt nhất, khi nhiều nhất một giá trị băm để mỗi vị trí trong mảng, tra cứu trong mảng [v] sẽ là O(1). Trong trường hợp xấu nhất, tất cả khóa sẽ băm đến cùng một nơi. Trong trường hợp đó, nếu danh sách  liên kết được sử dụng, thời gian tồi tệ nhất để tra cứu sẽ là O (N), trong đó N là số các giá trị được lưu trữ trong mảng băm. Chèn một khóa k trong một mảng băm là tương tự như tìm kiếm: đầu tiên, v = hash (k) được tính toán, sau đó k được thêm vào mảng [v]. Nếu danh sách liên kết được sử dụng, k nên được thêm vào ở phía trước của danh sách (vì có thể được thực hiện trong thời gian hằng). Thời gian chèn là tương tự như thời gian tìm kiếm: tổng các thời gian cho các hàm băm và thời gian để chèn k vào mảng. Nếu danh sách liên kết được sử dụng, thời gian để chèn k vào mảng sẽ luôn là O(1) và O(N) trong trường hợp xấu nhất. Để xóa một khóa k từ một mảng băm, v = hash (k) được tính toán, sau đó k được xóa khỏi danh sách liên kết. Trường hợp xấu nhất là giống như tìm kiếm, vì giá trị được tìm thấy trước khi nó có thể được xóa. Tóm lại: - Mảng băm mở: Tìm kiếm không thành công: O(1+1/(1-α)) Tìm kiếm thành công: O(1+ (1/α)ln( 1/(1-α))) - Chaining: Tìm kiếm không thành công: O(1 + α) Tìm kiếm thành công: O(1 + α/2) = O(1 + α)   n/m , mảng băm với m ô để lưu trữ n phần tử (khóa) II. Bài tập Bài 1. Cho các giá trị sau: 67 46 88 91 123 141 152 155 178 288 390 399 465 572 621 734  Vẽ một sơ đồ để hiển thị các giá trị được đưa vào một mảng băm với 20 vị trí. Sử dụng phương pháp chia của băm và phương pháp Linear Probing giải quyết va chạm.  Vẽ một sơ đồ để hiển thị các giá trị được chèn vào một mảng băm mà sử dụng hàm băm h(key) = key % 10 sử dụng phương pháp chaining để lưu các giá trị. Hướng dẫn  Bước 1: Áp dụng phương pháp Division lấy Index 67% 20 = 7 46% 20 = 6 88% 20 = 8 91% 20 = 11 ... 734% 20 = 14 Bước 2: Tạo mảng sử dụng Phương pháp linear probing (hình bên)  Bước 1: Áp dụng phương pháp Division Lấy Index 67% 10 = 7 46% 10 = 6 88% 10 = 8 91% 10 = 1 ... 734% 10 = 4 Bước 2: Tạo mảng sử dụng phương pháp Chaining (hình dưới) Bài 2 Cho một mảng băm với kích thước m = 11và hai hàm băm h1 và h2: h1(key) = key mod m h2(key) = {key mod (m-1)} + 1 Chèn các khóa {22, 1, 13, 11, 24, 33, 18, 42, 31} theo thứ tự nhất định (từ trái sang phải) đến mảng băm sử dụng mỗi phương pháp băm sau đây: a. Chaining với h1  h(k) = h1(k) b. Linear-Probing với h1  h(k,i) = (h1(k)+i) mod m