Cơ sở toán học của phép băm III: băm địa chỉ mở và băm hoàn hảo-- Mathematical foundation of hashing III

Bài này là bài cuối cũng nằm trong chuỗi bài về phép băm và các phân tích. Trước khi đọc bài này, mình khuyến khích bạn đọc xem lại bài viết trước về bảng băm, phương pháp địa chỉ mở và băm hoàn hảo.

Nhắc lại các khái niệm cơ bản: Gọi n là số phần tử ta muốn lưu trữ trong bảng băm; các phần tử này xuất phát từ một tập gốc \mathcal{U}. Bảng băm của chúng ta có kích thước m. Để băm vào bảng, ta sử dụng một hàm h(x); hàm băm này được chọn ngẫu nhiên từ một họ hàm băm \mathcal{H}. Bằng cách chọn ngẫu nhiên như vậy, h(x) thỏa mãn:

 \mathrm{Pr}_{h \in \mathcal{H}}[h(x) = h(y) ] \sim \frac{1}{m} \quad \forall x \not= y \qquad (1)

Dấu \sim ở đây có nghĩa là "tỉ lệ với",i.e, \mathrm{Pr}_{h \in \mathcal{H}}[h(x) = h(y) ] = \frac{c}{m} với một hằng số c nào đó.

Điểm quan trọng nhất mà bạn đọc cần nhớ ở đây: chúng ta không có bất kì giả sử nào về dữ liệu (i.e chúng ta sẽ không giả sử dữ liệu đầu vào là ngẫu nhiên). Tất cả các phân tích ngẫu nhiên ở đây đến từ việc chọn hàm băm ngẫu nhiên. Do đó, nếu ta có định sẵn một hàm băm thì tất cả các phân tích dưới đây đều vô nghĩa.

Băm địa chỉ mở

Trong băm địa chỉ mở, ta giải quyết xung đột bằng cách sử dụng m hàm băm ngẫu nhiên h_0(x), \ldots, h_{m-1}(x) thỏa mãn:

Tính ngẫu nhiên đồng đều: Với bất kì khóa x nào thuộc U, tập \{h_0(x), \ldots, h_{m-1}(x)\} là một hoán vị ngẫu nhiên của \{0,1,\ldots,m-1\}

 

Từ tính chất trên của m hàm băm, ta suy ra h_i(x), với mỗi i cho trước, đều có thể nhận một trong các giá trị \{0,1,\ldots,m-1\} với xác suất \frac{1}{m}. Hai câu hỏi mà ta quan tâm khi sử dụng băm địa chỉ mở là:

  1. Cần bao nhiêu phép dò bảng khi ta tìm kiếm một khóa không nằm trong bảng?
  2. Cần bao nhiêu phép dò bảng khi ta tìm kiếm một khóa nằm trong bảng?

 

Câu hỏi đầu tiên cho chúng ta biết thời gian của phép dò không thành công (unsuccessful search) và câu hỏi thứ hai cho chúng ta biết thời gian của một phép dò thành công (successful search).

Dò không thành công

Khi ta tìm kiếm một khóa x không nằm trong bảng, ta lần lượt dò các vị trí T[h_0(x)],T[h_1(x)],\ldots cho đến khi: (i) ta gặp một ô trống đầu tiên hoặc (ii) dò đến hết bảng, i.e, dò T[h_{m-1}(x)].

Gọi P(n,m) là biến ngẫu nhiên mà giá trị của biến này là số lần dò thực hiện khi tìm kiếm một khóa x không nằm trong bảng. Ta sẽ tính kì vọng E[P(m,n)].

Ta thấy: bất kể T[h_0(x)] có phải là ô trống hay không, ta đều phải sử dụng một phép dò. Nếu T[h_0(x)] trống thì ta dừng lại. Nếu T[h_0(x)] không trống, ta phải dò tiếp. Xác suất để ô T[h_0(x)] không trống là \frac{n}{m}. Khi ta dò tiếp, ta sẽ dò với tập hàm băm \{h_1(x),h_2(x) , \ldots, h_{m-1}(x)\}. Một điểm chú ý là do tính ngẫu nhiên đồng đều, các ô ta dò tiếp theo sẽ không bao giờ trùng với các ô đã dò trước đó. Do đó, ta có thể coi bước dò tiếp theo như dò bảng băm kích thước m-1, trong bảng sẵn có n-1 ô không trống. Từ đó ta suy ra công thức đệ quy:

E[P(m,n)] = 1 + \frac{n}{m}E[P(m-1,n-1)] \qquad (2)

 

Do E[P[m][0]] = 1 (khi bảng rỗng thì ta luôn kết thúc sau 1 phép dò) với mọi m > 0, bằng phương pháp quy nạp (coi như bài tập cho bạn đọc), ta có thể chứng minh được (giả sử m > n):

E[P(m,n)] \leq \frac{m}{m-n} = \frac{1}{1-\alpha}\qquad (3)

 
Trong đó \alpha = \frac{n}{m} là hệ số tải. Nếu ta khải triển:

\frac{1}{1-\alpha} = 1 + \alpha + \alpha^2 + \ldots \qquad (4)

 

Công thức (4) có ý nghĩa rất hay: ta luôn phải trả một phép dò đầu tiên; với xác suất \alpha, ta phải dò lần thứ 2; với xác suất \alpha^2, ta phải dò lần thứ 3, ....

Công thức (3) cho chúng ta biết khi sử dụng băm địa chỉ mở, ta không nên để hệ số tải quá gần 1, nếu không số phép dò sẽ rất lớn. Trong thực tế, hệ số tải ta nên để ở tầm \alpha \sim 0.8; khi đó số phéo dò trung bình là 5.

Dò thành công

Khi chèn một khóa vào bảng băm theo phương pháp địa chỉ mở, ta sẽ lần lượt dò bảng cho đến khi tìm được một ô trống và đặt khóa cần chền vào ô trống đó. Ở đây ta dễ dàng nhận thấy sự liên hệ giữa số phép dò cần thiết để chèn một khóa vào bảng và số phép dò tìm kiếm không thành công một khóa. Cụ thể, số phép dò cần để chèn khóa thứ k vào bảng sẽ tương đương với số phép dò trong kiếm không thành công trong trường hợp bảng băm có k-1 phần tử. Đương nhiên, số phép dò để tìm kiếm thành công một khóa bằng số phép dò để chèn khóa đó. Do đó, số phép dò kì vọng cần thiết để tìm kiếm khóa k, kí hiệu X(k), là:

X(k) \sim \frac{1}{1-\frac{k-1}{m}} = \frac{m}{m-k+1} \qquad (5)

 

Từ đó suy ra, số phép dò cần thiết để tìm kiếm khóa cuối cùng là xấp xỉ thời gian tìm kiếm không thành công và là \frac{1}{1-\alpha}.

Giả sử khả năng tìm kiếm các khóa là như nhau, ta suy ra thời gian tìm kiếm trung bình là:

\begin{array} {l} \frac{1}{n}\sum_{k=1}^n \frac{m}{m-k+1} & =  \frac{m}{n}\sum_{k=1}^n \frac{1}{m-k+1} \\ & =\frac{m}{n}\sum_{k=m-n+1}^m \frac{1}{k} \\ &= \frac{m}{n}(H(m) - H(m-n)) \end{array} \qquad (6)

 

Trong đó H(n) = 1+\frac{1}{2} + \ldots + \frac{1}{n}số đồng điều thứ n. Do \ln n \leq H(n)\leq  \ln n + 1, ta suy ra:

\begin{array} {l} \frac{1}{n}\sum_{k=1}^n \frac{m}{m-k+1} & \leq \frac{m}{n}(\ln (m) + 1 - \ln (m-n)) = \frac{1}{\alpha}\ln \frac{1}{1-\alpha} + \frac{1}{\alpha}\end{array} \qquad (7)

 

Các bạn có thể xem đặc tính biến đổi của số phép dò trong phương trình (7) theo \alpha tại đây.

Ví dụ nếu ta lấy \alpha = 0.8, từ (7) ta suy ra số phép dò trong một tìm kiếm thành công, giả sử khả năng tìm kiếm các khóa là như nhau, là khoảng 4 phép dò.

Remark: Từ thảo luận ở trên, ta có thể nhận ra một điểm là các khóa càng sớm được băm vào bảng thì có số phép dò tìm kiếm (thành công) càng ít. Do đó, trong thực tế, nếu chúng ta biết thêm thông tin về tần suất tìm kiếm khóa thì chúng ta có thể sắp xếp các khóa theo giảm dần của tần suất và băm theo thứ tự đó vào bảng. Mẹo này sẽ giúp chúng ta giảm được thời gian tìm kiếm (thành công) trung bình.

Băm hoàn hảo

Trong băm hoàn hảo, ta sẽ thực hiện băm hai pha. Sau pha đầu tiên, ta sẽ đếm xem, với mỗi i, có bao nhiêu phần tử được băm vào cùng một vị trí T[i]. Gọi C[i] là số phần tử được băm vào cùng T[i]. Trong pha 2, ta tạo ra một bảng phụ có kích thước C[i]^2 và sử dụng hàm băm khác để băm các phần tử có cùng mã băm i trong pha 1 vào bảng phụ này. Giả sử hệ số tải \alpha = 1

Tổng kích thước bộ nhớ là:

M = \sum_{i=0}^{n-1} C[i]^2 \qquad (8)

 

Ta sẽ tính kì vọng E[M]. Trước khi đi sâu vào chi tiết, mình khuyến khích bạn đọc xem lại một số tính chất của biến ngẫu nhiên 0/1 (phần cuối cùng của bài này). Đặc biệt định lý 8 sẽ là định lý mà chúng ta hay sử dụng ở đây.

Kí hiệu [A] là biến ngẫu nhiên 0/1 cho sự kiện A, i.e, [A] = 1 nếu sự kiện A xảy ra và [A] = 0 nếu ngược lại. Ví dụ, [h(x) = i] là biến ngẫu nhiên 0/1 cho sự kiện h(x) = i. Nếu h(x) = i thì [h(x) = i] = 1h(x) \not= i thì [h(x) = i] = 0.

Do \alpha = 1, ta suy ra \mathrm{Pr}[h(x) = i] \sim \frac{1}{n}\mathrm{Pr}[h(x) = h(y)] = \frac{1}{n}. Do đó, ta có:

E[\sum_{i=1}^n[h(x) = i]] = \sum_{i=1}^n E[[h(x) = i]] \sim \sum_{i=1}^n \frac{1}{n} = 1  \qquad (9)

và:

E[\sum_{i=1}^n[h(x) = i]*[h(y) = i]] = E[[h(x) = h(y)]] \sim \frac{1}{n}  \qquad (10)

Do C[i] là số phần tử được băm vào cùng vị trí i, ta suy ra:

C[i] = \sum_{x} [h(x) = i]  \qquad (11)

Do đó:

\begin{array} {l} E[M] & =  E[\sum_{i=1}^n C[i]^2] \\ & =  E[\sum_{i=1}^n (\sum_{x} [h(x) = i])^2] \\ & = E[\sum_{i=1}^n (\sum_{x} [h(x) = i]^2 + \sum_{x,y}[h(x) = i][h(y) = i])] \\ &=  E[\sum_{i=1}^n \sum_{x} [h(x) = i]^2] + E[\sum_{i=1}^n \sum_{x,y}[h(x) = i][h(y) = i]] \\ &= \sum_{x} E[\sum_{i=1}^n [h(x) = i]^2] + \sum_{x,y}  E[\sum_{i=1}^n[h(x) = i][h(y) = i]] \\ &=  \sum_{x} E[\sum_{i=1}^n [h(x) = i]]  +  \sum_{x,y}  E[\sum_{i=1}^n[h(x) = i][h(y) = i]] \\ & \sim \sum_{x} 1 + \sum_{x,y} \frac{1}{n} \\&= 2n  \end{array}

Từ dòng thứ 2 xuống dòng thứ 3, ta khai triển bình phương của tổng. Từ dòng thứ 3 xuống dòng thứ 4, ta áp dụng tính tuyến tính của kì vọng. Từ dòng thứ 4 xuống dòng thứ 5, ta áp dụng tính tuyến tính của kì vọng và đổi thứ tự tổng. Từ dòng thứ 5 xuống dòng thứ 6, ta áp dụng tính chất E[X^2] = E[X] nếu X là biến ngẫu nhiên 0/1. Từ dòng thứ 6 xuống dòng 7, ta áp dụng (9)(10).

Tham khảo

[1] Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[2] Jeff Erickson. Lecture Notes on Hashing. UIUC, 2013.
[3] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms (2nd ed.). Chapter 12. McGraw-Hill Higher Education, 2001.

Tags: , , , , ,

Reply

Your email address will not be published. Required fields are marked *