Bài KMP so khớp chuỗi bằng cách so ký tự thông minh. Rabin-Karp đi hướng hoàn toàn khác: nó so bằng hash. Thay vì đối chiếu từng ký tự, nó băm mẫu ra một con số, băm mỗi đoạn văn bản ra một con số, và chỉ cần so hai con số. Ý tưởng đẹp, và Rabin-Karp được ghi là O(n+m) trung bình. Nhưng cái "O(n+m)" đó, tôi phát hiện khi đo, đứng trên hai cái chân mà người ta hay quên — và bỏ quên cái nào cũng khiến nó ngã về O(n·m), đúng bằng cách naive tệ nhất.
So khớp bằng hash, và cái bẫy va chạm
Cách làm của Rabin-Karp: tính hash của mẫu P (dài m) một lần. Rồi trượt một cửa sổ dài m dọc văn bản T, ở mỗi vị trí tính hash của cửa sổ và so với hash mẫu. Nếu hai hash khác nhau, chắc chắn không khớp — bỏ qua ngay, không cần đụng tới ký tự. Nếu hai hash bằng nhau, có thể khớp thật, nhưng cũng có thể chỉ là va chạm (hai chuỗi khác nhau tình cờ cùng hash), nên phải so ký tự để xác minh. Cái hay là phần lớn cửa sổ bị loại chỉ bằng một phép so số, rất rẻ.
Nhưng có hai chỗ dễ sập, và cả hai là chủ đề tôi đo. Thứ nhất: tính hash của mỗi cửa sổ từ đầu tốn O(m), làm n cửa sổ thành O(n·m) — mất hết cái lợi. Thứ hai: nếu hash tồi, va chạm xảy ra liên tục, mỗi va chạm buộc một lần xác minh tốn kém. Rabin-Karp giải quyết cái thứ nhất bằng một mẹo tên hash cuộn; cái thứ hai thì tùy bạn chọn hash. Tôi đo cả hai.
Đo thứ nhất: hash cuộn là linh hồn của thuật toán
Mẹo hash cuộn (rolling hash): thay vì tính lại hash cả cửa sổ mới, hãy cập nhật hash cửa sổ cũ trong O(1) — trừ đi đóng góp của ký tự vừa rời khỏi cửa sổ (ký tự đầu), rồi cộng đóng góp của ký tự vừa vào (ký tự cuối). Một phép trừ, một phép nhân, một phép cộng, xong. Tôi đo hai phiên bản trên văn bản ngẫu nhiên, n = 5 triệu, m = 64:
cập nhật hash cuộn (O(1)/cửa sổ) : 38 ms
tính lại hash mỗi cửa sổ (O(m)) : 963 ms -> chậm hơn 26 lần
Bản tính-lại chậm hơn 26 lần — gần đúng bằng m lần, vì nó làm lại m phép tính ở mỗi trong n cửa sổ, tức O(n·m). Đây là điều đầu tiên đáng nhớ: cái làm Rabin-Karp nhanh không phải "dùng hash", mà là hash cuộn. Bỏ chữ "cuộn" đi — tính hash mỗi cửa sổ từ đầu — và bạn có một thuật toán O(n·m) đội lốt thông minh, chậm bằng naive worst case. Rất dễ viết nhầm phiên bản tính-lại nếu không nắm được mẹo cuộn.
Đo thứ hai: hash tồi biến O(n+m) thành O(n·m)
Điều kiện thứ hai là chất lượng hash. Ý tưởng "hash khác nhau thì bỏ qua" chỉ tiết kiệm khi hash ít va chạm — tức khi hai chuỗi khác nhau gần như luôn có hash khác nhau. Nếu hash tồi (miền giá trị nhỏ), nhiều cửa sổ vô tội tình cờ trùng hash với mẫu, và mỗi lần trùng buộc một lần xác minh ký tự. Tôi dựng ca xấu: văn bản lặp T = "aaaa...a", mẫu P = "aaa...ab", n = 1 triệu, m = 1000, so hai lựa chọn modulus:
hash tốt (modulus ~ tỉ) : 0 va chạm giả, 7,5 ms -> O(n)
hash xấu (modulus = 1) : 999 001 va chạm giả, 250 ms -> O(n*m) (chậm 33 lần)
Với hash tốt, hash của "aaa...a" khác hash của "aaa...ab", nên không cửa sổ nào trùng — 0 va chạm, 0 lần xác minh, thuật toán chạy O(n), 7,5 mili giây. Với hash tồi (ở đây modulus bằng 1, cực đoan cho dễ thấy — mọi hash đều bằng 0), mọi cửa sổ đều "trùng" hash với mẫu, nên mỗi cửa sổ bị xác minh, và trên văn bản lặp việc xác minh khớp gần hết m ký tự mới lệch — gần một tỉ phép so, 250 mili giây, O(n·m). Cùng một thuật toán, chỉ đổi một hằng số hash, chậm đi 33 lần. Bài học đo lường: "O(n+m)" của Rabin-Karp là một lời hứa có điều kiện — nó đúng khi hash cuộn và hash tốt, và vi phạm điều kiện nào cũng đưa nó thẳng về O(n·m) mà không một dòng lỗi nào báo. Tôi vào bài nghĩ Rabin-Karp "chắc chắn nhanh"; đo ra nó nhanh nếu bạn làm đúng hai điều mà lý thuyết nói lướt qua.
Vậy khi nào dùng Rabin-Karp?
Nếu Rabin-Karp cùng độ phức tạp với KMP mà lại mong manh hơn (phụ thuộc chất lượng hash), sao còn dùng? Vì nó có một thế mạnh mà KMP và naive không có: tìm nhiều mẫu cùng một lúc. Nếu bạn cần dò xem văn bản chứa cái nào trong một nghìn mẫu (lọc từ cấm, phát hiện chữ ký virus, tìm nhiều chuỗi ADN), bạn băm cả nghìn mẫu vào một tập, rồi trượt một cửa sổ dọc văn bản và tra hash cửa sổ trong tập — một lượt quét bắt hết. KMP hay naive phải quét lại văn bản một lần cho mỗi mẫu. Đây là chỗ hash cuộn tỏa sáng thật sự, chứ không phải ở bài toán một-mẫu nơi KMP đơn giản hơn và không có rủi ro va chạm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: nếu cài Rabin-Karp, đừng bỏ mẹo cuộn và đừng dùng modulus nhỏ. Hai lỗi này biến một thuật toán O(n+m) thành O(n·m) một cách âm thầm — code vẫn đúng, chỉ chậm thảm hại trên dữ liệu lớn hoặc dữ liệu lặp. Dùng một số nguyên tố lớn làm modulus (hoặc dựa vào tràn số 64-bit tự nhiên), và luôn cập nhật hash bằng cách cuộn, không tính lại.
Hệ quả thứ hai, tổng quát hơn: một thuật toán "dựa trên hash" thừa hưởng mọi rủi ro của hàm hash bên trong nó. Bài về hàm băm và bảng băm đã đo cùng một sự thật: hash tốt cho O(1)/O(n+m), hash tồi cho O(n)/O(n·m), và khác biệt nằm ở phân bố va chạm. Khi một cấu trúc hay thuật toán hứa hẹn hiệu năng đẹp "nhờ hash", câu hỏi đầu tiên là: hash đó tốt tới đâu, và điều gì xảy ra khi nó va chạm nhiều?
Hệ quả thứ ba là con số mang theo: Rabin-Karp là O(n+m) chỉ khi (1) dùng hash cuộn — không cuộn thì tính lại mỗi cửa sổ O(m), chậm 26 lần; và (2) dùng hash tốt — hash xấu trên văn bản lặp cho 999 001 va chạm giả và O(n·m), chậm 33 lần; thế mạnh thật của nó là tìm nhiều mẫu cùng lúc. "O(n+m)" trên giấy che giấu hai điều kiện mà chỉ đo mới lộ ra — và biết chúng là biết cách viết một Rabin-Karp thật sự nhanh, thay vì một cái trông giống mà chậm như naive.
Thử ba mươi giây
Nếu bạn thấy một đoạn code Rabin-Karp, kiểm hai chỗ. Thứ nhất, trong vòng trượt cửa sổ: nó cập nhật hash bằng cách trừ ký tự đầu và cộng ký tự cuối (cuộn), hay gọi lại một hàm tính hash cả cửa sổ mỗi lần? Nếu là cái sau, đó là một bản O(n·m) trá hình. Thứ hai, modulus của hash là số gì — một số nguyên tố lớn (tốt) hay một số nhỏ tiện tay? Modulus nhỏ nghĩa là nhiều va chạm, nhiều xác minh, và thoái hóa trên dữ liệu lặp. Cả hai lỗi này không làm sai kết quả, chỉ làm chậm — nên chúng dễ lọt qua test nhỏ rồi bùng ra trên dữ liệu thật. Sửa cả hai mất vài phút, và bạn có thể tự đo con số 26 lần và 33 lần ngay trên máy mình.
