Tìm một chuỗi trong chuỗi khác
Tìm một chuỗi trong chuỗi khác
Ctrl+F là thao tác bạn làm mỗi ngày. Bên dưới nó là hai thuật toán rất khác nhau, và cái nhanh hơn về lý thuyết không phải lúc nào cũng là cái rẻ hơn trên văn bản của bạn. Bài này đếm từng phép so sánh của cả hai, rồi tìm đúng chỗ chúng đổi ngôi.
Bài toán nghe đơn giản tới mức không đáng đặt tên: cho một văn bản dài n đơn vị và một mẫu dài m đơn vị, hãy tìm mọi chỗ mẫu xuất hiện. Cách nghĩ đầu tiên của ai cũng giống nhau: đặt mẫu vào đầu văn bản, so từng đơn vị, lệch thì dịch mẫu sang phải một bước rồi so lại từ đầu. Gọi là quét thẳng.
Chỗ tốn tiền của quét thẳng nằm ở hai chữ "từ đầu". Khi mẫu đã khớp được bốn đơn vị rồi mới lệch ở đơn vị thứ năm, quét thẳng ném đi cả bốn kết quả vừa biết, dịch một bước, và so lại từ đơn vị đầu tiên. Nhưng bốn đơn vị đã khớp kia là thông tin: chúng cho biết văn bản ở đoạn đó trông như thế nào, vì chúng bằng đúng bốn đơn vị đầu của mẫu. Knuth Morris Pratt chỉ làm một việc: tính trước, một lần duy nhất, xem từ thông tin đó thì được phép nhảy tới đâu, để con trỏ văn bản không bao giờ phải lùi.
Cái bảng tính trước đó gọi là bảng tiền tố. Hầu như mọi sách đều in ra bảng đã dựng xong rồi bảo bạn tin, và đó là chỗ người học rơi ra khỏi bài. Nên sim dưới đây cho bạn dựng nó từng bước, và đếm luôn cả số phép so sánh mà việc dựng bảng tốn, vì đó là khoản KMP phải trả trước.
Mọi tham số đều sửa được: gõ hai chuỗi khác là 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. Ba mục cuối chính là chỗ tôi làm việc đó với các kết luận của chính mình.
1 · Hai chuỗi, và hoá đơn của hai thuật toán ✎ sửa được
| n = 14, m = 5 | quét thẳng | Knuth Morris Pratt |
|---|---|---|
| phép so sánh dựng bảng tiền tố | 0 (không có bảng) | 4 |
| phép so sánh khi tìm | 24 | 15 |
| tổng phép so sánh | 24 | 19 |
| số vị trí căn mẫu | 10 | 6 |
| số lần dịch mẫu | 9 | 5 |
| số lần khớp tìm được | 3 | 3 |
(n - m + 1) × m = 502 · Quét thẳng, đi từng bước ▶ chạy được
3 · Bảng tiền tố của KMP, dựng từng bước ▶ chạy được
pi[q] là độ dài đoạn dài nhất vừa là tiền tố của mẫu vừa là hậu tố của đoạn mẫu tính tới vị trí q, và phải ngắn hơn chính đoạn đó. Con số ấy trả lời đúng một câu hỏi: khi khớp được q + 1 đơn vị rồi mới lệch, thì bao nhiêu đơn vị đầu mẫu đã khớp sẵn ở vị trí mới, để không phải so lại. Chỗ đẹp nhất là bảng tự dùng lại chính nó: khi ứng viên dài k không xài được, nó tụt về pi[k - 1], một ô đã điền xong từ trước.
2m - 3 = 7 phép, và cận đó chạm được: mẫu gồm một chữ lặp lại rồi đổi ở đơn vị cuối chạm đúng vào nó.4 · KMP tìm kiếm, đi từng bước ▶ chạy được
i phải tới được 14, nên KMP không thể tốn ít hơn n = 14 phép so sánh. Quét thẳng thì sàn chỉ là n - m + 1 = 10: mỗi cửa sổ ít nhất một phép. Chính cái sàn cao hơn này, cộng khoản trả trước cho bảng, là chỗ KMP có thể thua.5 · Ca xấu nhất dựng bằng tay, và mốc lật kèo ✎ sửa được
Văn bản tổng hợp gồm 1 chữ khác nhau, lặp vòng cho tới 60 đơn vị. Mẫu là 10 đơn vị đầu của đúng vòng lặp đó, nhưng đơn vị ở vị trí d bị thay bằng chữ z không hề có trong văn bản. Vậy d là độ sâu mà mọi cửa sổ hứa hẹn bị chết: càng sâu thì quét thẳng càng phải so nhiều trước khi biết là lệch. Mẫu không bao giờ xuất hiện, nên cả hai đều phải đi hết văn bản và số đo so được với nhau.
| độ sâu lệch d | quét thẳng | KMP (bảng + tìm) | quét thẳng so với (n-m+1)m | KMP so với n | ai ít phép hơn |
|---|---|---|---|---|---|
| 0 | 51 | 69 = 9 + 60 | 10,0% | 1,15 lần | ✓ quét thẳng |
| 1 | 102 | 135 = 16 + 119 | 20,0% | 2,25 lần | ✓ quét thẳng |
| 2 | 153 | 133 = 15 + 118 | 30,0% | 2,22 lần | ✓ KMP |
| 3 | 204 | 131 = 14 + 117 | 40,0% | 2,18 lần | ✓ KMP |
| 4 | 255 | 129 = 13 + 116 | 50,0% | 2,15 lần | ✓ KMP |
| 5 | 306 | 128 = 13 + 115 | 60,0% | 2,13 lần | ✓ KMP |
| 6 | 357 | 128 = 14 + 114 | 70,0% | 2,13 lần | ✓ KMP |
| 7 | 408 | 128 = 15 + 113 | 80,0% | 2,13 lần | ✓ KMP |
| 8 | 459 | 128 = 16 + 112 | 90,0% | 2,13 lần | ✓ KMP |
| 9 (sâu nhất) | 510 | 128 = 17 + 111 | 100,0% | 2,13 lần | ✓ KMP |
d = m - 1 = 9, quét thẳng chạm đúng 100% cận trên chặt của nó khi văn bản chỉ có một chữ.| số chữ khác nhau | mốc d để KMP có lãi | quét thẳng ở d = 9 | KMP ở cùng chỗ | hơn được mấy lần |
|---|---|---|---|---|
| 1 (một chữ lặp lại) | d ≥ 2 | 510 | 128 | 3,98 lần |
| 2 | d ≥ 2 | 285 | 99 | 2,88 lần |
| 3 | d ≥ 3 | 204 | 88 | 2,32 lần |
| 4 | d ≥ 3 | 168 | 84 | 2,00 lần |
| 5 | d ≥ 3 | 150 | 81 | 1,85 lần |
| 6 | d ≥ 4 | 132 | 79 | 1,67 lần |
| 8 | d ≥ 4 | 114 | 77 | 1,48 lần |
| 10 | d ≥ 5 | 105 | 75 | 1,40 lần |
| 13 | d ≥ 6 | 87 | 73 | 1,19 lần |
| 17 | d ≥ 8 | 78 | 72 | 1,08 lần |
| 21 | d ≥ 8 | 78 | 72 | 1,08 lần |
| 25 | d ≥ 8 | 78 | 72 | 1,08 lần |
6 · Mốc trên chính văn bản bạn đang gõ ✎ sửa được
Một cặp chuỗi không chứng minh được gì, nên mục này quét mọi mẫu: với từng độ dài m, nó cắt tất cả n - m + 1 cửa sổ của văn bản ra làm mẫu, chạy cả hai thuật toán trên từng mẫu, rồi cộng lại. Mẫu cắt từ văn bản thì luôn khớp ít nhất một lần, đúng như khi bạn gõ vào hộp tìm kiếm một từ có thật trong trang.
| độ dài mẫu m | số mẫu đã thử | tổng phép, quét thẳng | tổng phép, KMP | trong đó dựng bảng | ai ít phép hơn |
|---|---|---|---|---|---|
| 1 | 14 | 196 | 196 | 0 | = bằng nhau |
| 2 | 13 | 220 | 201 | 13 | ✓ KMP |
| 3 | 12 | 222 | 204 | 24 | ✓ KMP |
| 4 | 11 | 214 | 201 | 33 | ✓ KMP |
| 5 (mẫu đang gõ) | 10 | 194 | 195 | 42 | ✓ quét thẳng |
| 6 | 9 | 162 | 187 | 49 | ✓ quét thẳng |
| 7 | 8 | 142 | 175 | 52 | ✓ quét thẳng |
| 8 | 7 | 118 | 160 | 54 | ✓ quét thẳng |
| 9 | 6 | 90 | 143 | 54 | ✓ quét thẳng |
| 10 | 5 | 76 | 126 | 52 | ✓ quét thẳng |
m còn giá mỗi cửa sổ của quét thẳng thì gần như không đổi. Ở m = 1 hai bên bằng nhau đúng từng phép, vì mẫu một đơn vị thì KMP không có gì để tụt về.7 · Tiếng Việt: một ký tự là mấy đơn vị
| cách chia đơn vị | n | m | quét thẳng | KMP (bảng + tìm) | số lần khớp |
|---|---|---|---|---|---|
| điểm mã, chữ dựng sẵn (NFC) (đang dùng) | 14 | 5 | 24 | 19 = 4 + 15 | 3 |
| điểm mã, dấu tách rời (NFD) | 14 | 5 | 24 | 19 = 4 + 15 | 3 |
| cụm hiển thị (chữ và dấu gộp làm một) | 14 | 5 | 24 | 19 = 4 + 15 | 3 |
q cộng dấu sắc thì không có, và ở đó hai chế độ tách ra ngay.- Nó đếm phép so sánh, không đo giây. Đây không phải khiêm tốn: quét thẳng đọc bộ nhớ liền một mạch nên bộ đệm nạp sẵn cả dải, còn KMP nhảy con trỏ mẫu qua lại. Trên mảng nhỏ, thứ thua về số phép so sánh vẫn có thể nhanh hơn về thời gian. Muốn biết thì phải đo trên máy của bạn.
- Một phép so sánh là một lần đối chiếu hai đơn vị. Ở chế độ cụm hiển thị, một đơn vị có thể là mấy điểm mã mà vẫn tính là một phép. Cài đặt thật so từng byte thì đếm khác. Đây là quy ước, và mốc lật kèo dịch theo quy ước.
- Số lần dịch mẫu được định nghĩa là số lần vị trí căn mẫu đổi. Với cách đếm đó, ở ca xấu nhất KMP dịch nhiều hơn quét thẳng dù so ít hơn nhiều. Nên đừng dùng số lần dịch để kết luận ai nhanh hơn: phép so sánh mới là thứ tốn tiền.
- KMP ở đây viết đúng như sách, không có chốt
m > nở đầu hàm, nên ở mốc biên đó nó tốn công vô ích. Sim để nguyên và nói ra, thay vì lặng lẽ vá cho đẹp số. - Bộ gộp cụm ở đây phủ các dấu tiếng Việt (dải
U+0300tớiU+036Fvà bốn dải nữa). Nó không phải bộ tách cụm hiển thị đầy đủ của Unicode: emoji ghép, chữ Hàn tổ hợp, chữ Ấn Độ cần nhiều luật hơn.
Ở trạng thái mở bài, sim đang nói gì
Văn bản là abcabdabcabcab, dài 14 đơn vị. Mẫu là abcab, dài 5 đơn vị. Mẫu xuất hiện ba lần, ở vị trí 0, 6 và 9. Con số 9 đáng để ý: 9 = 14 - 5, tức lần khớp cuối cùng chạm đúng đơn vị cuối của văn bản. Hai mốc biên "khớp ở đầu" và "khớp ở cuối" nằm ngay trong trạng thái mở bài, không phải đi tìm.
Quét thẳng tốn 24 phép so sánh. Nó thử 10 vị trí căn mẫu, tức 14 - 5 + 1, và dịch mẫu 9 lần. Giá của từng vị trí không hề bằng nhau, đây là chỗ đáng nhìn kỹ nhất của quét thẳng:
| vị trí căn | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| phép so sánh | 5 | 1 | 1 | 3 | 1 | 1 | 5 | 1 | 1 | 5 |
Ba vị trí khớp trọn tốn đủ 5 phép. Vị trí 3 tốn 3 phép: ab khớp rồi d gặp c nên chết. Sáu vị trí còn lại chết ngay ở phép đầu, chỉ tốn 1. Cộng lại đúng 24. Cận trên chặt của quét thẳng ở đây là (n - m + 1) × m = 10 × 5 = 50, nên nó mới dùng 48,0% cận đó. So với con số n × m = 70 mà người ta hay trích thì chỉ 34,3%.
KMP tốn 19 phép so sánh, gồm 4 phép dựng bảng và 15 phép khi tìm. Nó chỉ đặt mẫu vào 6 vị trí thay vì 10, và các vị trí đó là 0, 3, 5, 6, 9, 12: nó nhảy, không dịch từng bước. Chênh lệch cuối cùng là 5 phép so sánh, tức KMP rẻ hơn 1,26 lần. Một cặp chuỗi cho ra 1,26 lần thì chưa nói được gì cả, và ba mục cuối của bài sẽ đo trên hàng nghìn cặp.
Bảng tiền tố: đọc cho hiểu, rồi dựng cho quen
pi[q] là độ dài đoạn dài nhất vừa là tiền tố của mẫu vừa là hậu tố của đoạn mẫu tính tới vị trí q, và phải ngắn hơn chính đoạn đó (nếu không thì đáp án luôn là cả đoạn, vô nghĩa). Với mẫu abcab:
| q | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| đơn vị | a | b | c | a | b |
| pi | 0 | 0 | 0 | 1 | 2 |
Đọc từng ô: tới q = 3 thì đoạn là abca, và a vừa là tiền tố vừa là hậu tố, nên pi[3] = 1. Tới q = 4 thì đoạn là abcab, và ab vừa là tiền tố vừa là hậu tố, nên pi[4] = 2.
Con số đó dùng để làm gì? Nó trả lời đúng một câu hỏi: khi đã khớp q + 1 đơn vị rồi mới lệch, thì bao nhiêu đơn vị đầu mẫu đã khớp sẵn ở vị trí mới? Trong sim, sau lần khớp ở vị trí 0, con trỏ mẫu tụt về pi[4] = 2 chứ không về 0, nên mẫu nhảy thẳng từ vị trí 0 sang vị trí 3, và KMP biết trước rằng hai đơn vị đầu mẫu đã khớp ở đó nên không so lại.
Chỗ đẹp nhất là bảng tự dùng lại chính nó khi đang dựng: nếu ứng viên dài k không xài được thì nó tụt về pi[k - 1], một ô đã điền xong từ trước. Bấm từng bước ở mục 3 với mẫu aaaab để thấy rõ nhất: ở vị trí cuối, ứng viên tụt ba lần liên tiếp 3 → 2 → 1 → 0 trước khi chịu ghi số 0.
Dựng bảng không miễn phí, và đây là con số mà sách hay bỏ qua. Với abcab nó tốn 4 phép so sánh. Cận trên đo được là 2m - 3, và cận đó chạm được: mẫu gồm một chữ lặp lại rồi đổi ở đơn vị cuối chạm đúng vào nó, chẳng hạn mẫu aaaaaaaaab tốn đúng 2 × 10 - 3 = 17 phép. Cổng kiểm số của bài đã quét toàn bộ 8.190 mẫu nhị phân dài tới 12 đơn vị: không mẫu nào vượt 2m - 3, và có mẫu chạm đúng.
Nói thẳng một chuyện về con số đó: khi tự tính tay số phép so sánh của mẫu ababaca, tôi ra 7. Hai đường tính độc lập trong cổng đều ra 8, và khi dò lại từng bước thì 8 mới đúng: ở vị trí 5, chữ c phải tụt hai lần rồi mới so với p[0], tức ba phép chứ không phải hai. Tôi giữ lại chuyện này trong bài vì nó đúng là lý do phải có hai đường tính.
Vì sao con trỏ văn bản không lùi lại là chuyện lớn
Bấm từng bước ở mục 4 và nhìn cột chỉ số văn bản: nó chỉ tăng, không bao giờ giảm. Hệ quả thì đơn giản mà ít ai nói ra: mỗi vòng lặp của KMP tốn đúng một phép so sánh, và i phải đi từ 0 tới n, nên KMP không thể tốn ít hơn n phép so sánh. Cổng đã kiểm mệnh đề này trên 126.945 cặp chuỗi nhị phân: không cặp nào cho KMP xuống dưới n, và cũng không cặp nào cho nó vượt 2n.
Còn sàn của quét thẳng là n - m + 1: mỗi cửa sổ ít nhất một phép so sánh. Sàn đó thấp hơn sàn của KMP, thấp hơn đúng m - 1.
Hai cái sàn khác nhau đó, cộng với khoản trả trước cho bảng, là toàn bộ nội dung của phần còn lại bài này. Ai bảo "KMP luôn nhanh hơn" là đã bỏ qua chúng.
Ca xấu nhất của quét thẳng, và nó dễ dựng tới mức nào
Bấm preset Ca xấu nhất của quét thẳng. Văn bản là 60 chữ a. Mẫu là 9 chữ a rồi một chữ b. Chỉ có thế.
Mọi cửa sổ đều khớp được 9 đơn vị rồi mới chết ở đơn vị thứ 10, nên không cửa sổ nào được thoát sớm:
- quét thẳng tốn 510 phép so sánh, đúng bằng
(60 - 10 + 1) × 10, tức 100,0% cận trên chặt của nó và 85,0% con sốn × m = 600; - KMP tốn 128 phép: 17 cho bảng cộng 111 cho việc tìm;
- KMP rẻ hơn 3,98 lần.
Đây là chỗ phải sửa lại một câu nói quen tai. Người ta hay bảo ca xấu nhất khiến quét thẳng leo lên gần n × m còn KMP thì "giữ ở gần n". Nửa đầu đúng: 510 trên 600. Nửa sau sai, và sai theo một chiều dễ kiểm: 128 phép trên văn bản 60 đơn vị là 2,13 lần n, không phải gần n. Lý do là chính ca xấu nhất của quét thẳng cũng đẩy KMP về gần cận trên của nó: phần tìm chạm 2n - m + 1 = 111, còn phần dựng bảng chạm 2m - 3 = 17. Nói cho đúng thì phải là: quét thẳng bay từ tuyến tính lên bậc hai, còn KMP đứng yên ở tuyến tính với hệ số 2. Ba con số 510, 128 và 2,13 đều bị cổng khoá.
Và một chi tiết nữa mà tôi đã định bỏ đi cho gọn, nhưng nó quá đáng nhớ: trên đúng ca này, KMP dịch mẫu nhiều hơn quét thẳng, 51 lần so với 50 lần. Nếu bạn chọn "số lần dịch mẫu" làm thước đo thì bạn sẽ chấm quét thẳng thắng, trong khi nó tốn gấp bốn lần số phép so sánh. Số lần dịch không phải thứ tốn tiền, phép so sánh mới là.
Mốc thứ nhất: mẫu phải lệch sâu bao nhiêu
Mục 5 của sim dựng một họ chuỗi có đúng ba núm và không có ngẫu nhiên ở đâu cả. Văn bản gồm σ chữ khác nhau lặp vòng cho tới n đơn vị. Mẫu là m đơn vị đầu của đúng vòng lặp đó, nhưng đơn vị ở vị trí d bị thay bằng một chữ không hề có trong văn bản. Vậy d là độ sâu mà mọi cửa sổ hứa hẹn bị chết, và mẫu thì không bao giờ xuất hiện, nên cả hai thuật toán đều phải đi hết văn bản.
Với n = 60, m = 10, σ = 1, tức đúng văn bản một chữ, số phép so sánh của quét thẳng là 51 × (d + 1), và cổng đã khoá công thức đó ở cả 10 dòng:
| độ sâu d | quét thẳng | KMP (bảng + tìm) | ai ít phép hơn |
|---|---|---|---|
| 0 | 51 | 69 = 9 + 60 | quét thẳng |
| 1 | 102 | 135 = 16 + 119 | quét thẳng |
| 2 | 153 | 133 = 15 + 118 | KMP |
| 9 | 510 | 128 = 17 + 111 | KMP |
Mốc là d = 2. Cổng khoá cả hai phía: đúng tại mốc thì KMP thắng, còn ở d = 1, đúng một bước dưới mốc, quét thẳng vẫn thắng. Điều đáng nhớ hơn cái mốc là hình dạng hai cột: cột quét thẳng đi từ 51 tới 510, gấp mười lần, còn cột KMP nhúc nhích trong khoảng 69 tới 135. Một bên phụ thuộc hoàn toàn vào dữ liệu, bên kia gần như không.
Mốc thứ hai: văn bản phải lặp lại bao nhiêu
Giữ n và m, kéo núm số chữ khác nhau rồi xem mốc d chạy đi đâu. Bảng thứ hai của mục 5 làm sẵn việc đó:
| số chữ khác nhau | 1 | 2 | 3 | 5 | 6 | 10 | 13 | 17 | 25 |
|---|---|---|---|---|---|---|---|---|---|
| mốc d để KMP có lãi | 2 | 2 | 3 | 3 | 4 | 5 | 6 | 8 | 8 |
| hơn được mấy lần ở d sâu nhất | 3,98 | 2,88 | 2,32 | 1,85 | 1,67 | 1,40 | 1,19 | 1,08 | 1,08 |
Đọc hàng trên: văn bản càng ít chữ khác nhau, tức càng lặp lại, thì mốc càng thấp, nghĩa là KMP có lãi sớm hơn. Trên dải 12 giá trị đã quét, mốc không hề giảm khi số chữ tăng, và đó là chuyện đo được trên đúng dải này, không phải một định lý tôi chứng minh được. Hàng dưới còn quan trọng hơn: phần lãi teo từ 3,98 lần xuống 1,08 lần. Với văn bản gần như không lặp, hai thuật toán gần bằng nhau, và lúc đó mọi thứ khác (bộ nhớ đệm, độ phức tạp của code, khả năng viết sai) mới là thứ quyết định.
Chiều ngược lại: trên tiếng Việt bình thường thì sao
Bấm preset Đoạn văn tiếng Việt. Đoạn văn dài 212 đơn vị, mẫu là từ thuật toán dài 10 đơn vị và xuất hiện hai lần, ở vị trí 98 và 157.
Kết quả trên đúng cặp chuỗi này: quét thẳng 242 phép, KMP 233 phép, tức 11 cho bảng cộng 222 cho việc tìm. KMP thắng, hơn 9 phép so sánh.
Tôi được giao bài này kèm một khẳng định: trên văn bản tiếng Việt bình thường thì quét thẳng thường thắng, vì ca xấu gần như không xảy ra. Con số 242 so với 233 nói ngược lại. Nhưng một cặp chuỗi không chứng minh được điều gì theo chiều nào cả, nên mục 6 của sim làm việc tử tế hơn: nó cắt mọi cửa sổ của văn bản ra làm mẫu, chạy cả hai thuật toán trên từng mẫu, rồi cộng lại.
| độ dài mẫu m | số mẫu đã thử | tổng phép, quét thẳng | tổng phép, KMP | ai ít phép hơn |
|---|---|---|---|---|
| 1 | 212 | 44.944 | 44.944 | bằng nhau |
| 3 | 210 | 48.104 | 48.026 | KMP |
| 4 | 209 | 47.988 | 48.058 | quét thẳng |
| 10 | 203 | 46.646 | 47.919 | quét thẳng |
Vậy khẳng định kia đúng về hướng nhưng sai về cách phát biểu, và cách sửa thì đo được:
- với mẫu từ 4 đơn vị trở lên, cộng trên toàn bộ mẫu cắt từ đoạn văn, quét thẳng ít phép hơn. Ở
m = 3, đúng một bước dưới mốc, KMP còn thắng. Cổng khoá cả hai phía; - ở
m = 10, trung bình mỗi mẫu quét thẳng tốn 229,78 phép còn KMP tốn 236,05. Cái mẫuthuật toántôi chọn ban đầu chỉ là một mẫu may cho KMP: 242 thì trên trung bình của quét thẳng, còn 233 thì dưới trung bình của KMP. Chọn một từ rồi kết luận là đúng kiểu sai mà bài này muốn chữa; - ở
m = 1hai bên bằng nhau đúng từng phép, cả hai tốn đúngn, vì mẫu một đơn vị thì KMP không có gì để tụt về.
Nguyên nhân thì không phải "ca xấu không xảy ra", mà cụ thể hơn thế. Ở m = 10, riêng phần tìm của KMP tốn 45.984 phép, vẫn ít hơn 46.646 phép của quét thẳng. Nó thua vì phần dựng bảng tốn 1.935 phép nữa, và khoản đó lớn lên theo m còn giá mỗi cửa sổ của quét thẳng thì gần như đứng yên (cộng trên cả 203 mẫu thì đo được 1,13 phép mỗi cửa sổ, so với 1,00 ở m = 1; riêng mẫu thuật toán thì tốn 1,19). Nói cách khác, chiều của mốc này ngược với trực giác: trên văn bản không lặp, mẫu càng dài thì quét thẳng càng lợi, chứ không phải càng dài thì KMP càng lợi.
Tiếng Việt: một ký tự là mấy đơn vị
Đây là chỗ tiếng Việt khác tiếng Anh, và nó đổi số phép so sánh chứ không chỉ là chuyện hiển thị. Chữ ế mà bạn nhìn thấy có thể được lưu bằng một điểm mã dựng sẵn, hoặc bằng ba điểm mã tách rời: chữ e, dấu mũ, dấu sắc. Cùng một đoạn văn, hai cách lưu, hai độ dài.
Đo trên đúng đoạn văn ở trên, với đúng mẫu thuật toán:
| cách chia đơn vị | n | m | quét thẳng | KMP | số lần khớp |
|---|---|---|---|---|---|
| dựng sẵn (NFC) | 212 | 10 | 242 | 233 = 11 + 222 | 2 |
| tách rời (NFD) | 275 | 13 | 310 | 299 = 14 + 285 | 2 |
| cụm hiển thị | 212 | 10 | 242 | 233 = 11 + 222 | 2 |
Ba chuyện đọc ra từ bảng này:
Tách dấu làm văn bản dài thêm 63 đơn vị, tức 29,7%, và số phép so sánh tăng 28,1%. Hai con số đó gần nhau không phải tình cờ: chi phí của cả hai thuật toán ở đây gần như tuyến tính theo độ dài, nên kéo dài văn bản 30% thì hoá đơn cũng đội lên chừng đó. Nếu bạn từng thắc mắc vì sao một hàm tìm kiếm chạy nhanh trên dữ liệu này mà chậm trên dữ liệu kia dù "nội dung giống nhau", đây là một trong các lý do rất thật.
Số lần khớp thì ba chế độ luôn bằng nhau, vì chuẩn hoá không làm mất chữ nào. Nhưng vị trí khớp thì khác: 98 và 157 ở dạng dựng sẵn, 130 và 205 ở dạng tách rời. Chỉ số trả về được đo bằng đơn vị, nên nó chỉ có nghĩa khi bạn nói rõ đơn vị là gì. Đây là lỗi rất hay gặp khi tô sáng kết quả tìm kiếm: tìm bằng một cách đếm, tô bằng một cách đếm khác, và dấu bị cắt làm đôi.
Cụm hiển thị cho ra đúng con số của dạng dựng sẵn trên chữ tiếng Việt. Đó là kết quả đo được, không phải trùng hợp: mọi chữ tiếng Việt đều có sẵn một điểm mã dựng sẵn. Nhưng hai chế độ đó không phải một: chuỗi q cộng dấu sắc thì không có dạng dựng sẵn, nên dạng dựng sẵn đếm 2 đơn vị còn cụm hiển thị đếm 1, và số phép so sánh tách ra ngay (6 so với 4 trên chuỗi thử của cổng).
Sim đếm theo đơn vị bạn chọn, và một phép so sánh là một lần đối chiếu hai đơn vị. Ở chế độ cụm hiển thị, một đơn vị có thể gồm mấy điểm mã mà vẫn tính là một phép. Đó là quy ước, không phải chân lý: cài đặt thật so từng byte thì đếm khác, và mốc lật kèo dịch theo quy ước. Muốn hiểu vì sao "một từ" tiếng Việt cũng không có định nghĩa hiển nhiên, đọc tiếng Việt, âm tiết và từ.
Mốc biên, chỗ code thật hay chết
Năm 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.
Mẫu rỗng. Theo quy ước của bài, cũng là quy ước của indexOf(""), mẫu rỗng khớp ở mọi vị trí, tức n + 1 vị trí, và tốn 0 phép so sánh cho cả hai thuật toán. Đây là quy ước chứ không phải chân lý: có thư viện chọn báo lỗi thay vì trả về 0.
Mẫu dài hơn văn bản. Quét thẳng thoát ngay, vì điều kiện s + m <= n không bao giờ đúng: 0 phép so sánh. 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: với văn bản abc và mẫu abcdefg, nó tốn 6 phép cho bảng cộng 3 phép quét, tức 9 phép cho một việc chắc chắn vô ích. Sim để nguyên và nói ra thay vì lặng lẽ vá, vì cái chốt m > n ở đầu hàm là thứ bạn nên tự thêm và nên hiểu tại sao.
Mẫu bằng đúng văn bản. Chỉ có một vị trí căn, nên quét thẳng tốn đúng m phép, còn KMP tốn thêm cả bảng: 5 so với 9 trên abcab. Quét thẳng thắng bằng cách không làm gì thêm.
Mẫu không xuất hiện. Với mẫu xyz trên văn bản mở bài: quét thẳng 12 phép (một phép mỗi cửa sổ, vì x không có trong văn bản), KMP 14 phép quét cộng 2 phép bảng. Đúng cái sàn n đã nói ở trên: KMP phải đọc hết văn bản, quét thẳng thì không cần đọc m - 1 đơn vị cuối.
Mẫu ở đầu và ở cuối. Trạng thái mở bài đã có cả hai: khớp ở vị trí 0, và khớp ở vị trí n - m = 9 nên cửa sổ cuối chạm đúng đơn vị cuối. Cổng còn kiểm rằng dịch mẫu đó thêm một đơn vị thì nó biến mất, để chắc chắn phép kiểm không phải luôn tìm thấy.
Sim này đếm gì và không đếm gì
Nó đếm phép so sánh, nó không đo giây. Đây không phải khiêm tốn khách sáo, nó là khác biệt có thể lật ngược kết luận. Quét thẳng đọc bộ nhớ liền một mạch nên bộ đệm nạp sẵn cả dải và bộ nạp trước đoán đúng bước kế tiếp. KMP thì nhảy con trỏ mẫu qua lại, và trên chuỗi ngắn thì cái bảng phụ còn chiếm chỗ trong bộ đệm. Muốn biết cái nào nhanh hơn trên máy bạn thì phải đo, và đừng suy ra từ trang này. Vì sao đếm phép tính lại đáng tin hơn bấm đồng hồ, và đáng tin tới đâu, đọc đếm phép tính.
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 "KMP là thuật toán tốt hơn".
Cách đếm số lần dịch mẫu là một định nghĩa tôi chọn: số lần vị trí căn mẫu đổi. Với cách đếm đó, ở ca xấu nhất KMP dịch nhiều hơn quét thẳng. Đổi định nghĩa thì con số đổi, nên đừng mang riêng nó đi so.
Bộ gộp cụm hiển thị ở đây chỉ phủ các dấu tiếng Việt và bốn dải dấu khác. Nó không phải bộ tách cụm đầy đủ của Unicode: emoji ghép, chữ Hàn tổ hợp, chữ Ấn Độ cần nhiều luật hơn hẳn.
Còn hai bài rất gần với bài này. Nếu bạn muốn thấy cùng một kiểu đánh đổi "trả trước rồi tiết kiệm sau" trên bài toán khác, đọc tìm tuyến tính so với tìm nhị phân: ở đó khoản trả trước là chi phí sắp xếp, và mốc hoà vốn tính được ra con số. Nếu bạn muốn hỏi "hai chuỗi này giống nhau bao nhiêu" thay vì "chuỗi này có nằm trong chuỗi kia không", đọc khoảng cách chỉnh sửa: cùng họ bài toán, nhưng lời đáp là một bảng động chứ không phải một vị trí.
Quét thẳng có ca xấu nhất O(n·m), và ca đó dựng được trong một dòng: văn bản một chữ lặp lại, mẫu lặp chính chữ đó rồi khác ở đơn vị cuối. Đo được 510 phép so sánh trên n = 60, m = 10, đúng 100% cận trên chặt (n - m + 1) × m. KMP giữ ở 128, tức tuyến tính, nhưng là 2,13 lần n chứ không phải "gần n": chính ca đó cũng đẩy KMP về cận trên của nó. Nhưng chiều ngược lại thật hơn nhiều với công việc hàng ngày: trên đoạn văn tiếng Việt bình thường, cộng trên mọi mẫu cắt từ văn bản, quét thẳng ít phép hơn từ m = 4 trở lên, vì sàn của nó là n - m + 1 còn sàn của KMP là n, cộng thêm khoản dựng bảng lớn lên theo m. Cái quyết định không phải độ dài mẫu mà là độ lặp của văn bản: mốc đo được chạy từ d = 2 khi văn bản chỉ có một chữ tới d = 8 khi có 25 chữ, và phần lãi teo từ 3,98 lần xuống 1,08 lần. Cuối cùng, "một ký tự" là một quy ước: tách dấu tiếng Việt làm văn bản dài thêm 29,7% và hoá đơn đội thêm 28,1%. Trước khi chọn thuật toán, hãy nhìn dữ liệu của bạn, và đếm.
- 1Văn bản là 60 chữ `a`, mẫu là 9 chữ `a` rồi một chữ `b`. Quét thẳng tốn bao nhiêu phép so sánh ký tự?
- 2Trên một đoạn văn tiếng Việt 212 đơn vị, cộng số phép so sánh trên MỌI mẫu dài 10 đơn vị cắt ra từ chính đoạn văn đó, ai ít phép hơn và vì sao?
- 3Mẫu `abcab` có bảng tiền tố pi bằng 0, 0, 0, 1, 2. Con số pi[4] bằng 2 nói lên điều gì khi thuật toán đang tìm?