Băm cuộn và thuật toán Rabin-Karp
Băm cuộn và thuật toán Rabin-Karp
Thay vì so từng ký tự, hãy so một con số. Ý tưởng đó rẻ tới mức đáng ngờ, và nó đáng ngờ thật: một con số không thể thay được cả chuỗi. Bài này cho bạn nhìn thấy đúng chỗ nó hụt, đếm cái giá của lần hụt đó, và tìm mốc mà chính phép cuộn hết lãi.
Bài trước so quét thẳng với KMP: cả hai đều đi tới đáp án bằng cách so ký tự, chỉ khác nhau ở chỗ được phép nhảy bao xa sau một lần lệch. Bài này đổi hẳn cách nghĩ: nén mỗi cửa sổ của văn bản thành một con số, rồi so số với số. So hai số nguyên là một phép, dù cửa sổ dài 5 hay 500 đơn vị.
Chỗ hay là nén không cần nén lại từ đầu. Khi cửa sổ trượt sang phải một bước, nó mất đúng một đơn vị ở đầu và nhận đúng một đơn vị ở cuối, nên mã băm mới tính được từ mã băm cũ trong thời gian hằng số: trừ đơn vị đi ra, nhân cơ số một lần, cộng đơn vị đi vào, tất cả theo modulo. Cái đó gọi là băm cuộn, và thuật toán dựng trên nó gọi là Rabin-Karp.
Chỗ dở thì lớn hơn vẻ ngoài của nó, và đó là toàn bộ lý do bài này tồn tại. Nén là mất mát: nhiều chuỗi khác nhau chắc chắn cùng ra một mã băm, vì số chuỗi thì vô hạn còn số mã băm thì chỉ có modulo cái. Nên băm khớp không có nghĩa là chuỗi khớp, và Rabin-Karp bắt buộc phải so ký tự để xác nhận. Sim dưới đây mở bài bằng một va chạm thật để bạn không phải tin điều đó bằng lời.
Mọi tham số đều sửa được: gõ chuỗi khác, kéo cơ số, kéo modulo, và mọi con số tính lại. Nếu bạn thấy bài đang dẫn bạn tới một kết luận, hãy vặn núm cho tới khi kết luận đó sai. Hai mục giữa bài chính là chỗ tôi làm việc đó với kết luận của chính mình.
1 · Mã băm của khuôn mẫu, tính từng bước ✎ sửa được
Mã băm là tổng mã(đơn vị) × cơ số^(vị trí từ phải) rồi lấy dư theo modulo. Tính từ trái sang phải theo lối Horner thì mỗi bước chỉ là h = (h × cơ số + mã) mod modulo, nên không bao giờ phải giữ một con số khổng lồ.
| bước | đơn vị | mã điểm | h = (h × 31 + mã) mod 11 |
|---|---|---|---|
| 1 | a | 97 | 9 |
| 2 | b | 98 | 3 |
| 3 | c | 99 | 5 |
| 4 | a | 97 | 10 |
| 5 | b | 98 | 1 |
31^4 mod 11, dùng để trừ đơn vị đi ran - m + 12 · Từng cửa sổ: băm, rồi kiểm
Cửa sổ đầu tiên được băm lại từ đầu, tốn 5 bước. Mỗi cửa sổ sau chỉ tốn một bước cuộn: h ← ((h - mã(ra) × 5) × 31 + mã(vào)) mod 11. Hai cột cuối là điểm dạy chính của bài: băm khớp thì bắt buộc phải so ký tự, và cột khớp được mấy đơn vị cho thấy phép so đó hụt ở đâu. Một va chạm chết ngay ở đơn vị đầu chỉ tốn 1 phép, nên va chạm không đương nhiên tốn m phép.
| vị trí | cửa sổ | cách tính | mã băm | kết quả | khớp được mấy đơn vị | phép so ký tự |
|---|---|---|---|---|---|---|
| 0 | abcab | băm lại từ đầu | 1 | ✓ khớp thật | 5/5 | 5 |
| 1 | bcabd | cuộn một bước | 1 | ⚠ va chạm, băm khớp mà chuỗi khác | 0/5 | 1 |
| 2 | cabda | cuộn một bước | 8 | · bỏ qua, băm khác | – | 0 |
| 3 | abdab | cuộn một bước | 5 | · bỏ qua, băm khác | – | 0 |
| 4 | bdabc | cuộn một bước | 3 | · bỏ qua, băm khác | – | 0 |
| 5 | dabca | cuộn một bước | 4 | · bỏ qua, băm khác | – | 0 |
| 6 | abcab | cuộn một bước | 1 | ✓ khớp thật | 5/5 | 5 |
| 7 | bcabc | cuộn một bước | 0 | · bỏ qua, băm khác | – | 0 |
| 8 | cabca | cuộn một bước | 10 | · bỏ qua, băm khác | – | 0 |
| 9 | abcab | cuộn một bước | 1 | ✓ khớp thật | 5/5 | 5 |
3 · Cuộn so với băm lại từng cửa sổ
Đơn vị kế toán ở đây là phép nhân theo modulo. Một bước Horner tính một phép nhân. Một bước cuộn tính hai phép: một cho trọng số của đơn vị đi ra, một cho phép dịch. Cách tính giá đó là quy ước, và chính nó quyết định mốc lật kèo bên dưới, nên đừng mang riêng nó đi so với chỗ khác.
| n = 14, m = 5, 10 cửa sổ | băm cuộn | băm lại từng cửa sổ | tỉ lệ |
|---|---|---|---|
| bước băm | 14 | 50 | 3,57 lần |
| phép nhân theo modulo | 23 | 50 | 2,17 lần |
| chuẩn bị (trọng số + băm khuôn mẫu) | 9 | 9 | bằng nhau |
n: cửa sổ đầu tốn m bước, còn lại n - m bước cuộn. Đó là toàn bộ ý tưởng băm cuộn, và nó không phụ thuộc vào m.| m (giữ n = 14) | nhân, khi cuộn | nhân, khi băm lại | bên nào ít hơn |
|---|---|---|---|
| 1 | 27 | 14 | băm lại |
| 2 | 26 | 26 | bằng nhau đúng từng phép |
| 3 | 25 | 36 | cuộn |
| 4 | 24 | 44 | cuộn |
| 5 | 23 | 50 | cuộn |
| 6 | 22 | 54 | cuộn |
| 7 | 21 | 56 | cuộn |
| 8 | 20 | 56 | cuộn |
4 · Modulo quyết định hoá đơn
Cùng văn bản, cùng khuôn mẫu, cùng cơ số 31. Chỉ modulo đổi. Số lần khớp thật không bao giờ đổi vì phép kiểm ký tự dọn sạch mọi va chạm, nhưng số phép so ký tự thì đổi, và đó chính là chỗ O(n + m) trung bình biến thành O(n·m) xấu nhất.
| modulo | băm khuôn mẫu | băm khớp | va chạm | khớp thật | so ký tự | trong đó phí |
|---|---|---|---|---|---|---|
| 1 | 0 | 10 | 7 | 3 | 24 | 9 |
| 2 | 1 | 6 | 3 | 3 | 18 | 3 |
| 5 | 4 | 3 | 0 | 3 | 15 | 0 |
| 11 | 1 | 4 | 1 | 3 | 16 | 1 |
| 101 | 75 | 3 | 0 | 3 | 15 | 0 |
| 1.009 | 342 | 3 | 0 | 3 | 15 | 0 |
| 100.003 | 96.524 | 3 | 0 | 3 | 15 | 0 |
| 1.000.000.007 | 92.599.299 | 3 | 0 | 3 | 15 | 0 |
5 · Chọn cơ số và modulo thế nào
Đơn vị ở vị trí j của cửa sổ mang trọng số cơ số^(m-1-j) mod modulo. Nếu trọng số đó bằng 0 thì đổi đơn vị ở vị trí đó không bao giờ làm mã băm đổi: mã băm mù hẳn với vị trí ấy. Chuyện đó xảy ra đúng khi cơ số và modulo chia hết cho nhau đủ nhiều, và đó là lý do modulo nên là số nguyên tố lớn hơn cơ số.
| vị trí j trong cửa sổ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| trọng số mod 11 | 5 | 3 | 4 | 9 | 1 |
6 · Chỗ Rabin-Karp thắng thật: nhiều khuôn mẫu một lượt ✎ sửa được
Một mã băm cuộn có đúng một bề rộng cửa sổ, nên mọi khuôn mẫu trong lượt phải dài bằng nhau. Băm cả 4 khuôn mẫu vào một bảng tra, rồi đi một lượt qua văn bản: mỗi cửa sổ tính mã băm một lần rồi tra bảng. Chạy riêng từng khuôn mẫu thì phải đi 4 lượt.
| khuôn mẫu | mã băm | tìm được ở |
|---|---|---|
abcab | 1 | 0, 6, 9 |
bcabc | 0 | 7 |
cabca | 10 | 8 |
xyzzy | 8 | không có |
- Nó đếm phép so ký tự và phép nhân theo modulo. Nó không đo giây. Một phép nhân kèm lấy dư không cùng giá với một phép so ký tự, nên đừng cộng hai cột lại rồi so.
- Giá một bước cuộn được tính là hai phép nhân, và giá đó là quy ước. Đổi quy ước thì mốc lật kèo ở mục 3 dịch theo. Một cài đặt tránh được phép nhân trọng số (chẳng hạn tính sẵn bảng tra) sẽ cho mốc khác.
- Đơn vị là điểm mã của dạng dựng sẵn NFC. Đó là một lựa chọn, và nó đổi cả
nlẫnmtrên chữ tiếng Việt. Bài trước đo đúng chuyện đó. - Modulo tối đa là 1.000.000.007 vì trên mức đó phép nhân của JavaScript vượt 253 và sai âm thầm. Con số ngưỡng đã đo bằng cách so với số nguyên lớn, và ghi trong đầu tệp
engine.ts. - Bài này không chọn cơ số hay modulo ngẫu nhiên. Rabin-Karp thật hay chọn modulo ngẫu nhiên để kẻ tấn công không dựng được văn bản làm mọi cửa sổ va chạm. Ở đây mọi thứ tiền định để con số lặp lại được, nên phần chống đối kháng của thuật toán không hề hiện ra.
Ở trạng thái mở bài, sim đang nói gì
Văn bản là abcabdabcabcab, dài 14 đơn vị. Khuôn mẫu là abcab, dài 5 đơn vị. Đúng cặp chuỗi của bài trước, chọn có chủ ý để bạn so được hai trang. Cơ số là 31, modulo là 11.
Mã băm của khuôn mẫu là 1. Con số đó dựng bằng năm bước Horner, mỗi bước là h = (h × 31 + mã) mod 11, và chuỗi giá trị đi qua là 9, 3, 5, 10, 1. Trọng số của đơn vị đi ra là 31^4 mod 11, tức 5.
Có 10 cửa sổ, tức 14 - 5 + 1. Trong đó:
- 4 cửa sổ có mã băm bằng 1, tức bằng mã băm khuôn mẫu, nên buộc phải kiểm ký tự;
- 3 lần kiểm đó thành công, ở vị trí 0, 6 và 9. Con số 9 đáng để ý:
9 = 14 - 5, tức lần khớp cuối chạm đúng đơn vị cuối của văn bản; - 1 lần kiểm hụt. Đó là va chạm, và nó nằm ở cửa sổ vị trí 1;
- 6 cửa sổ còn lại bị bỏ qua vì mã băm đã khác, và chúng tốn 0 phép so ký tự. Đó chính là khoản Rabin-Karp đang bán.
Tổng cộng 16 phép so ký tự. Trên cùng cặp chuỗi này, quét thẳng tốn 24 phép, và cận trên nếu cửa sổ nào cũng phải kiểm hết là 50 phép.
Va chạm: nhìn nó một lần rồi sẽ không quên
Cửa sổ ở vị trí 1 là bcabd. Mã băm của nó là 1, đúng bằng mã băm của abcab. Hai chuỗi không giống nhau một đơn vị nào ở vị trí đầu, mà con số thì y hệt.
Đây không phải chuyện dựng lên cho vui: nó là hệ quả bắt buộc của việc nhét mọi chuỗi 5 đơn vị vào 11 giá trị. Bạn có thể làm nó hiếm đi, nhưng không thể làm nó biến mất.
Rabin-Karp xử lý bằng cách luôn xác nhận: hễ băm khớp thì so ký tự từ trái sang phải, lệch ở đâu thì dừng ở đó. Ở đây b gặp a ngay đơn vị đầu, nên lần xác nhận này tốn đúng 1 phép so sánh rồi bỏ. Nhớ chi tiết đó, vì nó chữa một suy nghĩ sai rất dễ mắc: một va chạm không đương nhiên tốn m phép. Nó tốn từ 1 tới m phép, tuỳ chỗ hai chuỗi rẽ nhau. Bấm preset Cơ số và modulo cùng chia hết thì va chạm ở cửa sổ 3 là abdab, chia sẻ ab với khuôn mẫu, nên nó tốn 3 phép chứ không phải 1.
Cột khớp được mấy đơn vị trong bảng cửa sổ hiện đúng con số đó, và cổng kiểm số đối chiếu nó với một phép tính tiền tố chung dài nhất viết độc lập, trên 10.380 dòng bảng.
Nói thẳng một chuyện: nếu phép xác nhận bị bỏ đi thì thuật toán sẽ báo sai, không phải chậm. Nó sẽ trả về vị trí 1 như một lần khớp. Đó là lỗi mà mã băm càng tốt thì càng khó bắt trong lúc thử, vì với modulo lớn bạn phải rất kiên nhẫn mới gặp một va chạm.
Băm cuộn: một bước thay cho m bước
Cửa sổ đầu tiên phải băm lại từ đầu, tốn m bước. Mỗi cửa sổ sau chỉ tốn một bước cuộn. Vậy tổng số bước băm là m + (n - m), tức đúng n, không phụ thuộc m chút nào. Ở trạng thái mở bài con số đó là 14. Nếu băm lại từng cửa sổ thì tốn (n - m + 1) × m = 50 bước, gấp hơn ba lần.
Bất biến số bước băm khi cuộn = n đã được cổng kiểm trên 15.220 cặp (n, m) trong toàn dải cho phép, không cặp nào lệch.
Còn một chuyện khó hơn: bước cuộn không rẻ bằng bước Horner. Một bước Horner có một phép nhân theo modulo. Một bước cuộn có hai: một để tính trọng số của đơn vị đi ra, một cho phép dịch. Đếm theo phép nhân thì hoá đơn ở trạng thái mở bài là 23 phép khi cuộn so với 50 phép khi băm lại, tức rẻ hơn 2,17 lần. Cả hai cách còn phải trả 9 phép nhân chuẩn bị như nhau: 4 phép cho trọng số 31^4 và 5 phép cho mã băm khuôn mẫu.
Cuộn không phải lúc nào cũng rẻ hơn, và mốc thấp hơn bạn tưởng
Tôi bắt tay vào bài này với niềm tin rằng cuộn luôn thắng. Đếm ra thì không, và mốc lật kèo thấp tới mức tôi phải kiểm lại ba lần.
Với n đơn vị văn bản và khuôn mẫu m đơn vị, số phép nhân khi cuộn là m + 2(n - m) = 2n - m, còn khi băm lại từng cửa sổ là (n - m + 1)m. Giữ n = 14, bảng thứ hai của mục 3 trong sim cho:
| m | nhân, khi cuộn | nhân, khi băm lại | bên nào ít hơn |
|---|---|---|---|
| 1 | 27 | 14 | băm lại |
| 2 | 26 | 26 | bằng nhau đúng từng phép |
| 3 | 25 | 36 | cuộn |
| 5 | 23 | 50 | cuộn |
Mốc là m = 3. Cổng khoá cả hai phía, và phía dưới mốc mới là chỗ đáng nhớ: ở m = 2 hai cột bằng nhau đúng từng phép nhân, và điều đó đúng với mọi n, không riêng 14. Thay m = 2 vào hai công thức thì cả hai đều ra 2n - 2. Cổng đã kiểm từ n = 2 tới n = 400: không n nào phá vỡ thế cân bằng đó. Ở m = 1 thì băm lại rẻ hơn hẳn, vì băm lại một cửa sổ dài 1 đơn vị chỉ tốn 1 phép nhân trong khi cuộn tốn 2.
Nói cho đúng thì phải là: băm cuộn thắng nhờ m lớn, không phải nhờ ý tưởng cuộn. Khi m bằng 1 hay 2 thì cái mẹo hay đó không mua được gì cả.
Và đây là chỗ tôi phải nói rõ một quy ước. Con số "hai phép nhân mỗi bước cuộn" là cách tôi chọn tính giá, không phải chân lý. Một cài đặt tính sẵn bảng trọng số, hoặc chọn cơ số là luỹ thừa của 2 để thay phép nhân bằng phép dịch bit, sẽ có giá khác và mốc sẽ dịch theo. Cái không dịch là hình dạng: một bên tăng theo m, một bên giảm theo m, nên luôn có một mốc.
Modulo quyết định hoá đơn, và ca xấu nhất chạm đúng cận trên
Đổi modulo mà giữ nguyên mọi thứ khác thì số lần khớp không bao giờ đổi, vì phép xác nhận dọn sạch mọi va chạm. Nhưng hoá đơn thì đổi hẳn. Mục 4 của sim giữ abcabdabcabcab với abcab và cơ số 31, chỉ kéo modulo:
| modulo | băm khớp | va chạm | khớp thật | so ký tự | trong đó phí |
|---|---|---|---|---|---|
| 1 | 10 | 7 | 3 | 24 | 9 |
| 2 | 6 | 3 | 3 | 18 | 3 |
| 5 | 3 | 0 | 3 | 15 | 0 |
| 11 | 4 | 1 | 3 | 16 | 1 |
| 101 | 3 | 0 | 3 | 15 | 0 |
| 1.000.000.007 | 3 | 0 | 3 | 15 | 0 |
Đọc cột cuối: với modulo tốt, hoá đơn tụt về 15, tức đúng sàn 3 × 5, không một phép nào tiêu vô ích. Với modulo 1 thì hoá đơn là 24, và 24 chính là con số của quét thẳng.
Không phải trùng hợp, và đây là chỗ mệnh đề "xấu nhất O(n·m)" trở thành một phép tính chứ không phải một lời hứa. Với modulo = 1 mọi mã băm đều bằng 0, nên cửa sổ nào cũng khớp băm, nên cửa sổ nào cũng phải chạy đúng cái vòng lặp xác nhận mà quét thẳng chạy. Hai bên bằng nhau đúng từng phép, không phải xấp xỉ. Cổng đã kiểm mệnh đề đó trên toàn bộ cặp chuỗi thử của bài.
Bấm preset Ca xấu nhất: mọi cửa sổ va chạm để thấy nó ở quy mô dễ nhớ. Văn bản là 60 chữ a, khuôn mẫu là 9 chữ a rồi một chữ b, modulo 1. Có 51 cửa sổ, cả 51 va chạm, không lần nào khớp thật, và hoá đơn là 510 phép so ký tự. Con số 510 đúng bằng (60 - 10 + 1) × 10, tức 100% cận trên chặt. Quét thẳng trên cùng cặp chuỗi cũng tốn đúng 510.
Rồi đổi modulo về 11 mà giữ nguyên hai chuỗi: hoá đơn xuống 0 phép so ký tự, vì không cửa sổ nào khớp băm. Từ 510 xuống 0, chỉ vì một con số. Đó là điều cần nhớ về Rabin-Karp: chi phí của nó là tính chất của modulo và của dữ liệu, không phải tính chất của thuật toán.
Một cảnh báo về cách phát biểu. Rất dễ viết thành "chi phí bằng số va chạm nhân m", và câu đó sai: mỗi va chạm tốn từ 1 tới m phép. Ở trạng thái mở bài, một va chạm tốn 1 phép chứ không phải 5.
Modulo lớn hơn không đương nhiên va chạm ít hơn
Trong bảng trên có một cặp dòng tôi đã định bỏ đi cho gọn, nhưng nó phá đúng một trực giác đáng phá: modulo 5 cho 0 va chạm, còn modulo 11 cho 1 va chạm. Modulo lớn hơn mà lại tệ hơn.
Không có gì thần bí, chỉ là số học của đúng cặp chuỗi này: bcabd tình cờ đồng dư với abcab theo modulo 11 mà không đồng dư theo modulo 5. Điều đúng là xu hướng: modulo càng lớn thì xác suất va chạm càng nhỏ. Điều không đúng là mệnh đề đơn điệu "cứ tăng modulo là va chạm giảm". Cổng khoá cả phản ví dụ này, đúng ở trạng thái mở bài chứ không giấu ở đâu xa, để không ai lặng lẽ viết bản đơn điệu vào bài.
Cũng phải nói thẳng chỗ sim này không làm được: nó không đo được "trung bình O(n + m)". Trung bình đó là một phát biểu về modulo chọn ngẫu nhiên, còn ở đây mọi thứ tiền định để con số lặp lại được. Bài này cho bạn thấy hai đầu của dải, và nói rằng phần giữa là chuyện xác suất mà trang này không đo.
Chọn cơ số và modulo, và vì sao nên dùng số nguyên tố
Đơn vị ở vị trí j của cửa sổ mang trọng số cơ số^(m-1-j) mod modulo. Ở trạng thái mở bài, năm trọng số là 5, 3, 4, 9, 1, tức 31^4, 31^3, 31^2, 31, 1 rút gọn theo modulo 11. Không có số 0 nào trong đó, và đây là điều kiện phải để ý.
Nếu một trọng số bằng 0 thì đổi đơn vị ở vị trí đó không bao giờ làm mã băm đổi, vì phần đóng góp của nó luôn là delta × 0 = 0. Mã băm mù hẳn với vị trí ấy. Bấm preset Cơ số và modulo cùng chia hết: cơ số 256, modulo 256, khuôn mẫu 5 đơn vị. Trọng số là 0, 0, 0, 0, 1, tức 4 trong 5 vị trí bị mù, và mã băm chỉ còn đọc đúng đơn vị cuối cửa sổ.
Hậu quả thì đo được và rất khó quên: theo cơ số 256 với modulo 256, mã băm của abcab là 98, và mã băm của zzzzb cũng là 98. Hai chuỗi không giống nhau ở đâu cả. Với modulo 257, chỉ hơn một đơn vị, hai chuỗi đó tách ra ngay.
Cổng không chỉ khoá con số 98. Nó chứng minh cả nghĩa của chữ "mù", theo hai chiều: không phép thay thế nào ở một vị trí mù làm mã băm nhúc nhích, và mọi vị trí không mù đều bị ít nhất một phép thay thế làm đổi. Thiếu nửa sau thì chữ "mù" chỉ là nhãn dán.
Từ đó ra quy tắc chọn, và nó là quy tắc có lý do chứ không phải mê tín:
- modulo nên là số nguyên tố và lớn hơn cơ số, để không trọng số nào rút về 0 và để lớp đồng dư trải đều;
- cơ số nên ít nhất bằng số ký tự khác nhau bạn có thể gặp. Kéo cơ số về 1 thì mã băm thành tổng mã các đơn vị, nên mọi phép đảo chỗ đều va chạm:
abcvàcbacùng một mã băm. Cổng khoá cả ca đó; - modulo càng lớn càng ít va chạm, theo xu hướng, nhưng có một trần rất cụ thể ở mục sau.
Chỗ này khác với va chạm trong bảng băm ở một điểm đáng phân biệt. Bảng băm gặp va chạm thì giải quyết nó, bằng dây chuyền hoặc bằng dò ô khác, và khoá vẫn nằm trong bảng. Rabin-Karp gặp va chạm thì loại bỏ nó, bằng cách so ký tự, và cái mất là công đã tiêu. Cùng chữ "va chạm", hai bài toán khác nhau.
Một chuyện về số học của JavaScript, đo chứ không đoán
Modulo lớn thì ít va chạm hơn, nên tại sao sim không cho kéo modulo lên thật cao? Vì số của JavaScript chỉ giữ chính xác các số nguyên tới 2^53, tức 9.007.199.254.740.992. Vượt mức đó thì phép nhân sai âm thầm: không báo lỗi, không tràn, chỉ trả về một số gần đúng, và mã băm cuộn sẽ lệch khỏi mã băm tính lại từ đầu mà chẳng có gì kêu lên.
Nên tôi đo, chứ không đoán. So mã băm cuộn với một bản dựng bằng số nguyên lớn của JavaScript, trên một văn bản dựng riêng để làm phép nhân to nhất có thể (toàn điểm mã cao nhất, U+10FFFF, tức 1.114.111), rồi chia đôi dần để tìm ngưỡng, với cơ số ở mức tối đa 1.024:
- modulo lớn nhất còn chính xác: 8.585.739.520
- modulo đầu tiên đo được là sai: 8.585.739.521
Trần của sim đặt ở 1.000.000.007, tức thấp hơn điểm sai đo được 8,58 lần. Ở góc xấu nhất của dải cho phép, phép nhân lớn nhất có thể sinh ra là 1.114.111.006.684.666, bằng 12,37% của 2^53. Toàn bộ lưới đã đối chiếu với số nguyên lớn: 134.784 mã băm cửa sổ, không cái nào lệch.
Điều đáng học ở đây không phải hai con số kia. Nó là: cổng kiểm số chứng minh nguy hiểm là thật trước khi chứng minh mình an toàn. Có một khẳng định bắt buộc engine phải sai ở modulo 8.585.739.521, và một khẳng định khác đòi nó đúng ở 8.585.739.520. Một giới hạn mà không ai biểu diễn được cảnh nó bị vượt là một giới hạn không ai kiểm được.
Chỗ Rabin-Karp thắng thật: nhiều khuôn mẫu một lượt
Trên một khuôn mẫu, Rabin-Karp không có gì để khoe trước KMP. Chỗ nó thắng là khi bạn có nhiều khuôn mẫu cùng độ dài và muốn tìm hết trong một lượt.
Lý do rất gọn: mã băm của cửa sổ không phụ thuộc vào khuôn mẫu nào cả. Băm tất cả khuôn mẫu vào một bảng tra trước, rồi đi một lượt qua văn bản, mỗi cửa sổ tính mã băm một lần rồi tra bảng. KMP thì phải dựng một bảng tiền tố cho mỗi khuôn mẫu và đi một lượt cho mỗi khuôn mẫu.
Mục 6 của sim làm sẵn với bốn khuôn mẫu abcab, bcabc, cabca, xyzzy trên văn bản mở bài:
- một lượt gộp tốn 23 phép nhân, còn bốn lượt riêng tốn 92 phép, đúng 4 lần;
- bảng tra giữ 4 mã băm khác nhau, và lượt gộp tra trúng 7 lần, trong đó 2 lần kiểm hụt, tổng 27 phép so ký tự;
abcabtìm thấy ở 0, 6, 9;bcabcở 7;cabcaở 8;xyzzykhông có. Khuôn mẫu vắng mặt không tốn thêm lượt nào, đó chính là chỗ ăn tiền.
Có một chi tiết cài đặt mà bài dễ bỏ qua, nên tôi đưa vào cổng: hai khuôn mẫu có thể trùng mã băm với nhau. Bấm preset Đoạn tiếng Việt thì bốn khuôn mẫu băm, cửa, tại, kìa chỉ cho 3 mã băm khác nhau theo modulo 29. Nếu mỗi ô của bảng tra chỉ giữ được một khuôn mẫu thì một khuôn mẫu sẽ biến mất khỏi kết quả. Ô phải giữ một danh sách, và cổng khoá đúng chuyện đó bằng cách đòi cả bốn khuôn mẫu vẫn ra đúng đáp án.
Cùng ý tưởng đó mở rộng lên hai chiều: để tìm một khuôn mẫu ảnh a × b trong ảnh lớn, băm cuộn từng hàng rồi băm cuộn theo cột trên dãy mã băm hàng. Bài này không dựng phần đó, nên tôi chỉ nêu tên chứ không đưa con số nào.
Còn một giới hạn thật của mẹo gộp: một mã băm cuộn có đúng một bề rộng cửa sổ, nên mọi khuôn mẫu trong một lượt phải dài bằng nhau. Gõ vào sim một khuôn mẫu dài khác thì nó bị bỏ ra và sim nói ra, không lặng lẽ dùng. Cài đặt thật xử lý nhiều bề rộng bằng cách chạy một mã băm cuộn cho mỗi bề rộng, tức thêm một vòng lặp bọc ngoài.
So với KMP: cái được đánh đổi
Trên văn bản tiếng Việt thật, preset Đoạn tiếng Việt cho thấy Rabin-Karp làm việc rất gọn: đoạn 62 đơn vị, khuôn mẫu mã băm dài 6 đơn vị, 57 cửa sổ, 6 lần khớp băm, 4 lần kiểm hụt, 2 lần khớp thật ở vị trí 14 và 39, tổng 16 phép so ký tự. Quét thẳng trên cùng cặp chuỗi tốn 70 phép, còn cận trên là 342.
Nhưng đừng đọc bảng đó thành "Rabin-Karp nhanh gấp bốn". Hai cột đếm hai đơn vị khác nhau: 16 phép so ký tự cộng 62 bước cuộn cộng 11 phép nhân chuẩn bị, so với 70 phép so ký tự và không có gì khác. Một phép nhân kèm lấy dư không cùng giá với một phép so hai ký tự, và trang này không đo giây, nên không cộng hai cột lại rồi so.
Cái so được là bảo đảm. KMP có một tính chất mà Rabin-Karp không có: chi phí của nó bị chặn tuyến tính theo O(n + m) bất kể dữ liệu là gì, vì con trỏ văn bản không bao giờ lùi. Rabin-Karp thì chỉ tuyến tính khi va chạm ít, và bảng ở mục trên cho thấy một modulo tồi đẩy nó về O(n·m) đúng bằng quét thẳng. Đó là cái Rabin-Karp đánh đổi để lấy khả năng gộp nhiều khuôn mẫu.
Và đây là chỗ tệ nhất của cái đánh đổi ấy: nếu cơ số và modulo là cố định và công khai, kẻ tấn công dựng được văn bản làm mọi cửa sổ va chạm, giống hệt cách bài trước dựng ca xấu nhất cho quét thẳng trong một dòng. Cách chống là chọn modulo ngẫu nhiên lúc chạy, để không ai dựng trước được ca xấu. Sim này không làm thế, vì engine.ts phải tiền định để mọi con số lặp lại được, nên phần chống đối kháng của Rabin-Karp không hề hiện ra trên trang. Nói ra thì tốt hơn để bạn tưởng thuật toán này an toàn theo mặc định.
Mốc biên, chỗ code thật hay chết
Bốn ca dưới đây cổng đều khoá bằng con số cụ thể, và khoá cả một bước bên cạnh mốc.
Khuôn mẫu rỗng. Theo quy ước của indexOf(""), nó khớp ở mọi vị trí, tức n + 1 = 15 vị trí, và tốn 0 phép so sánh cùng 0 bước băm. Đây là quy ước chứ không phải chân lý: có thư viện chọn báo lỗi.
Khuôn mẫu dài hơn văn bản. Rabin-Karp trả lời trước khi băm bất cứ thứ gì: không có cửa sổ nào, nên 0 bước băm và 0 phép so sánh. Đáng so với bài trước: KMP viết đúng như sách thì vẫn dựng bảng rồi vẫn quét hết văn bản trong đúng tình huống này. Một bước ngược lại, khuôn mẫu bằng đúng văn bản, thì có 1 cửa sổ và tốn đúng m = 5 phép.
Dấu trừ có thể làm hỏng mọi thứ. Trong bước cuộn, phép trừ đơn vị đi ra có thể xuống dưới 0, và phép % của JavaScript giữ dấu của toán hạng bên trái, nên mã băm sẽ thành số âm và không bao giờ khớp lại với mã băm khuôn mẫu nữa. Vì thế mã có cộng thêm modulo trước khi rút gọn. Cổng chạy 5.000 ca cố tình đẩy phép trừ xuống âm và đòi kết quả luôn nằm trong [0, modulo).
Đơn vị và điểm mã. Sim đếm theo điểm mã của dạng dựng sẵn NFC, và bài trước đã đo rằng lựa chọn đó đổi cả n lẫn m trên chữ tiếng Việt. Cổng còn kiểm một ca chữ ngoài mặt phẳng cơ bản: một chuỗi 7 đơn vị chiếm 10 đơn vị mã UTF-16, và chỉ số trả về được đếm theo đơn vị, không theo mã. Trộn hai cách đếm là lỗi rất hay gặp khi tô sáng kết quả tìm kiếm.
Sim này đếm gì và không đếm gì
Nó đếm phép so ký tự và phép nhân theo modulo, nó không đo giây. Đây không phải khiêm tốn khách sáo: một phép nhân kèm lấy dư đắt hơn một phép so ký tự, và tỉ số đó phụ thuộc máy. Muốn biết cái nào nhanh hơn trên máy bạn thì phải đo. Vì sao đếm phép tính vẫn đáng tin hơn bấm đồng hồ, và đáng tin tới đâu, đọc đếm phép tính.
Giá một bước cuộn là hai phép nhân, và đó là quy ước. Đổi quy ước thì mốc m = 3 dịch theo. Hình dạng hai đường thì không dịch.
Cổng kiểm số canh phép tính, không canh khẳng định về thế giới. Nó nói được "cấu hình này thì phải ra đúng con số này". Nó không nói được "Rabin-Karp là thuật toán tốt hơn".
Không có ngẫu nhiên ở đâu cả, nên phần quan trọng nhất của Rabin-Karp thật, tức chọn modulo ngẫu nhiên để chống ca xấu dựng cố ý, không xuất hiện trên trang này.
Trung bình O(n + m) là phát biểu xác suất mà sim không đo. Sim cho bạn hai đầu của dải: modulo 1 thì đúng bằng quét thẳng, modulo lớn thì đúng sàn số lần khớp × m.
Còn hai bài rất gần. Quét thẳng và KMP là cùng bài toán với hai thuật toán so ký tự, và có đúng cặp chuỗi của trang này để bạn đối chiếu. Hàm băm và va chạm là chỗ va chạm được giải quyết thay vì bị loại bỏ, và ở đó số nguyên tố cũng có vai trò, nhưng vì một lý do khác.
Băm cuộn tính mã băm cửa sổ kế tiếp trong thời gian hằng số, nên cả văn bản chỉ tốn đúng n bước băm thay vì (n - m + 1) × m bước. Nhưng cái phải nhớ hơn là hai chỗ dễ nói sai. Thứ nhất, băm khớp không phải chuỗi khớp: ở trạng thái mở bài, cửa sổ bcabd có cùng mã băm với abcab theo modulo 11, nên Rabin-Karp bắt buộc phải so ký tự, và bỏ phép xác nhận đó thì thuật toán báo sai chứ không phải chậm. Thứ hai, chi phí là tính chất của modulo, không phải của thuật toán: cùng 60 chữ a với khuôn mẫu 9 chữ a rồi b, modulo 1 cho 510 phép so ký tự, đúng 100% cận trên và đúng bằng quét thẳng, còn modulo 11 cho 0 phép. Đó là cái Rabin-Karp đánh đổi so với KMP, thứ vẫn O(n + m) bất kể dữ liệu. Bù lại nó gộp được nhiều khuôn mẫu vào một lượt: bốn khuôn mẫu tốn 23 phép nhân thay vì 92. Và ba chi tiết đo được, đừng đoán: cuộn chỉ có lãi từ m = 3, ở m = 2 hai cách bằng nhau đúng từng phép với mọi n; modulo lớn hơn không đương nhiên va chạm ít hơn (modulo 5 cho 0, modulo 11 cho 1); và modulo phải nằm dưới ngưỡng 2^53 của JavaScript, ngưỡng đó đo được ở 8.585.739.521, không phải suy ra.
- 1Văn bản `abcabdabcabcab`, khuôn mẫu `abcab`, cơ số 31, modulo 11. Cửa sổ ở vị trí 1 là `bcabd` và có mã băm bằng 1, đúng bằng mã băm khuôn mẫu. Rabin-Karp làm gì với cửa sổ đó, và nó tốn bao nhiêu?
- 2Văn bản là 60 chữ `a`, khuôn mẫu là 9 chữ `a` rồi một chữ `b`, và modulo đặt bằng 1. Rabin-Karp tốn bao nhiêu phép so ký tự, và vì sao con số đó đáng nhớ?
- 3Đặt cơ số 256 và modulo 256, khuôn mẫu dài 5 đơn vị. Bảng trọng số ra 0, 0, 0, 0, 1. Điều đó có nghĩa gì?