'Chắc chắn O(n+m)' — bỏ quên một trong hai điều, Rabin-Karp chậm 33 lần

Muốn biết hai trang sách có giống nhau không, bạn không cần đọc so từng chữ — chỉ cần liếc số từ, hay một "dấu vân tay" tóm tắt: khác vân tay thì chắc chắn khác, khỏi đọc; trùng vân tay thì mới ngồi đọc kỹ để chắc. Bài KMP so khớp chuỗi bằng cách so ký tự thông minh; Rabin-Karp đi hướng khác hẳn — nó so bằng dấu vân tay, tức hash. 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ỉ 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ỏ 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.

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.

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. Điều rút ra: "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ề đến code hằng ngày

Điều đầ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.

Điều 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?

Và bản thân hash cuộn là một công cụ bạn gặp nhiều hơn tưởng, dưới những cái tên khác. git dùng một rolling hash (thuật toán kiểu Rabin) để chia file thành các khối khi đóng gói và dò đoạn trùng; rsync cũng dùng rolling hash để tìm phần dữ liệu đã đổi giữa hai bên mà không gửi cả file — đó là lý do đồng bộ một file lớn vừa sửa vài dòng lại nhanh. Trong ứng dụng, thư viện chống trùng nội dung, dò đạo văn, hay các hệ "content-defined chunking" (nhiều hệ backup, Dropbox) đều đứng trên hash cuộn. Còn ở tầng cơ sở dữ liệu, cùng bài học "hiệu năng dựa trên hash phụ thuộc phân bố" lặp lại: một hash join hay GROUP BY trên cột phân bố lệch sẽ dồn quá nhiều dòng vào một bucket và thoái hóa, đúng như modulus nhỏ ở trên. Mẫu số chung: "O(n+m)" trên giấy che giấu hai điều kiện mà chỉ đo mới lộ — 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.

Muốn tự thấy thì nếu gặp 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.