Chúng tôi muốn giải quyết vấn đề so sánh các chuỗi một cách hiệu quả. Cách mạnh mẽ để làm như vậy chỉ là so sánh các chữ cái của cả hai chuỗi, có độ phức tạp về thời gian là O[min[n1,n2]] nếu n1 và n2 là kích thước của hai chuỗi. Chúng tôi muốn làm tốt hơn. Ý tưởng đằng sau chuỗi là như sau. chúng tôi chuyển đổi từng chuỗi thành một số nguyên và so sánh các chuỗi đó thay vì các chuỗi. So sánh hai chuỗi sau đó là phép toán O[1]
Để chuyển đổi, chúng ta cần một cái gọi là hàm băm. Mục tiêu của nó là chuyển đổi một chuỗi thành một số nguyên, được gọi là hàm băm của chuỗi. Điều kiện sau đây phải giữ. nếu hai chuỗi s và t bằng nhau [s=t]. thì giá trị băm của chúng cũng phải bằng giá trị băm [s] = hash[t]. Nếu không, chúng ta sẽ không thể so sánh các chuỗi. Chú ý, chiều ngược lại không phải giữ.
TÍNH TOÁN Băm CỦA CHUỖI. -
Cách tốt và được sử dụng rộng rãi để xác định hàm băm của một chuỗi s có độ dài n là. -
[các] hàm băm = [s[0] + s[1]*p + s[2]*p2 +. +s[n-1]*p[n-1]] mod m
trong đó p và m là một số được chọn, số dương. Nó được gọi là hàm băm cuộn đa thức
Dưới đây là một ví dụ về cách tính hàm băm của một chuỗi s, chuỗi chỉ chứa các chữ cái viết thường. Chúng tôi chuyển đổi từng ký tự của s thành một số nguyên. Ở đây chúng tôi sử dụng chuyển đổi a->1, b->2,. z->26. Chuyển đổi a->0 không phải là một ý tưởng hay, bởi vì khi đó giá trị băm của a,aa,aaa,. tất cả đánh giá là 0
hash_value = [hash_value + [ord[i]-ord['a']+1]*p_pow] % m
print['Hash cho cppsecrets là. -',compute_hash[s]]
# sức mạnh tiền điện toán của p có thể giúp tăng hiệu suất
Băm cho cppsecrets là. - 266349268
TÌM KIẾM CÁC CHUỖI Trùng lặp TRONG MỘT MẢNG. -
Vấn đề. Cho danh sách n xâu si, mỗi xâu không quá m ký tự, hãy tìm tất cả các xâu trùng nhau và chia chúng thành các nhóm
Từ thuật toán rõ ràng liên quan đến việc sắp xếp các chuỗi, chúng ta sẽ nhận được độ phức tạp về thời gian là O[n*m*log[n]] trong đó việc sắp xếp yêu cầu phép so sánh O[n*log[n]] và mỗi phép so sánh mất thời gian O[m]. Tuy nhiên, bằng cách sử dụng hàm băm, chúng tôi giảm thời gian so sánh xuống O[1], cho chúng tôi một thuật toán chạy trong thời gian O[n*m+n*log[n]]
Chúng tôi tính toán giá trị băm cho mỗi chuỗi, sắp xếp các giá trị băm cùng với các chỉ số, sau đó nhóm các chỉ số theo các giá trị băm giống hệt nhau
hash_value = [hash_value + [ord[i]-ord['a']+1]*p_pow] % m
def grp_identical_strings[arr]
giá trị băm = [[0, 0] cho i trong phạm vi[n]]
hash[i] = [compute_hash[arr[i]], i]
nếu i == 0 hoặc băm[i][0]. = băm[i-1][0]
các nhóm. nối thêm [[mảng [ind]]]
nhóm[-1]. nối thêm [mảng [ind]]
arr = ['khác biệt', 'khác biệt', 'có thể phân biệt được', 'không tương đương', 'khác biệt','biến số', 'khác biệt','khác nhau', 'khác nhau','không chính xác','không chính xác', 'không chính xác'
kết quả = nhóm [là] chuỗi giống hệt nhau
print['Nhóm có cùng giá trị băm. -']
Các nhóm có cùng giá trị băm. -
ỨNG DỤNG CỦA Băm. -
Dưới đây là một số ứng dụng tiêu biểu của Hashing
1. Thuật toán Rabin-Karp để khớp mẫu trong một chuỗi trong thời gian O[n]
2. Tính số chuỗi con khác nhau của một chuỗi trong O[n2logn] [xem bên dưới]
3. Tính số chuỗi con palindromic trong một chuỗi
CẢI THIỆN KHẢ NĂNG KHÔNG ĐỔI. -
Khá thường xuyên, hàm băm đa thức được đề cập ở trên là đủ tốt và sẽ không có xung đột nào xảy ra trong quá trình thử nghiệm. Hãy nhớ rằng, xác suất va chạm xảy ra chỉ là 1/m. Với m=109+9 xác suất là 10-9, khá thấp. Nhưng lưu ý rằng chúng tôi chỉ thực hiện một so sánh. Điều gì sẽ xảy ra nếu chúng ta so sánh một chuỗi s với 106 chuỗi khác nhau. Xác suất để có ít nhất một vụ va chạm xảy ra bây giờ là 10-3. Và nếu chúng ta muốn so sánh 106 chuỗi khác nhau với nhau [e. g. bằng cách đếm xem có bao nhiêu chuỗi duy nhất tồn tại], thì xác suất xảy ra ít nhất một xung đột đã là 1. Khá chắc chắn rằng tác vụ này sẽ kết thúc bằng một xung đột và trả về kết quả sai
Có một mẹo thực sự dễ dàng để có xác suất tốt hơn. Chúng ta chỉ có thể tính toán hai giá trị băm khác nhau cho mỗi chuỗi [bằng cách sử dụng hai p khác nhau và/hoặc m khác nhau và thay vào đó so sánh các cặp này. Nếu m là khoảng 109 cho mỗi trong hai hàm băm thì điều này ít nhiều tương đương với việc có một hàm băm với 1018. Khi so sánh 106 chuỗi với nhau, xác suất xảy ra ít nhất một va chạm hiện giảm xuống còn 10-6