Bài toán tìm một mẫu chuỗi trong một văn bản lớn — Ctrl+F, grep, tìm gen trong ADN — có một cách làm "ngây thơ" (naive) mà ai cũng nghĩ ra ngay, và một thuật toán "thông minh" tên KMP mà sách giáo khoa dạy để thay thế. Câu chuyện quen thuộc: naive là O(n·m) nên chậm, KMP là O(n+m) nên nhanh, hãy dùng KMP. Bài này đo, và phát hiện câu chuyện đó đúng một nửa — cái nửa còn lại là một trong những minh họa rõ nhất cả sê-ri về khoảng cách giữa trường hợp xấu nhất và điều thực sự xảy ra.
Naive và KMP: khác nhau ở chỗ "so lại"
Cách naive rất trực tiếp: đặt mẫu P (dài m) tại từng vị trí của văn bản T (dài n), so từng ký tự; nếu lệch ở đâu, trượt mẫu sang phải một bước và so lại từ đầu. Cái "so lại từ đầu" là chỗ tốn: nếu mẫu khớp được nhiều ký tự rồi mới lệch, tất cả những so sánh đó bị vứt đi và làm lại ở vị trí kế. Trong trường hợp xấu nhất, mỗi vị trí so gần hết m ký tự, cho O(n·m).
KMP (Knuth-Morris-Pratt) xóa bỏ sự lãng phí đó. Nó tiền xử lý mẫu P thành một bảng gọi là hàm tiền tố: với mỗi vị trí trong mẫu, bảng cho biết đoạn đầu (tiền tố) dài nhất của mẫu cũng chính là đoạn vừa khớp (hậu tố). Khi lệch, KMP dùng bảng này để trượt mẫu đi xa mà không cần so lại phần đã khớp — vì nó đã biết phần đó trông thế nào. Kết quả là mỗi ký tự của văn bản được xét một số lần hằng định, cho O(n+m) bảo đảm, kể cả trường hợp xấu nhất. Nghe như KMP luôn thắng. Nhưng "trường hợp xấu nhất" là cụm từ đáng đo, nên tôi đo.
Đo: trên văn bản thường, naive gần O(n)
Tôi cài cả hai, đếm số phép so sánh ký tự và bấm giờ, trên hai loại văn bản. Trước hết là văn bản ngẫu nhiên — bảng chữ 26 ký tự, n = 5 triệu, mẫu m = 50:
so sánh / ký tự thời gian
naive 1,04 3,4 ms
KMP 1,04 4,3 ms
Hai thuật toán ngang nhau, và naive thậm chí nhanh hơn một chút (3,4 so với 4,3 mili giây). Lý do: trên văn bản ngẫu nhiên, khi naive đặt mẫu ở một vị trí, gần như chắc chắn ký tự đầu tiên đã lệch (xác suất khớp chỉ 1/26), nên nó trượt ngay mà không so thêm. Trung bình chỉ 1,04 so sánh mỗi ký tự — thực chất là O(n), không có bóng dáng nào của O(n·m). KMP làm cùng số so sánh nhưng phải trả thêm phí xây bảng tiền tố và một vòng lặp phức tạp hơn, nên nhỉnh chậm hơn. Đây là chỗ tôi đã hớ.
Một lần tôi đo hớ: O(n·m) là trường hợp xấu, không phải ca thường
Tôi vào bài với niềm tin sách vở gọn gàng: "naive là O(n·m), tức là chậm về bản chất, luôn phải thay bằng KMP." Đo ra naive ngang KMP trên văn bản thường, thậm chí nhanh hơn. Nhãn "O(n·m)" mô tả trường hợp xấu nhất — một tình huống cụ thể mà văn bản ngẫu nhiên gần như không bao giờ rơi vào. Để thấy cái O(n·m) đó thật sự bật ra, tôi phải cố tình dựng ca xấu: văn bản toàn ký tự giống nhau T = "aaaa...a", và mẫu P = "aaaa...ab" (toàn a rồi một b ở cuối). n = 1 triệu, m = 1000:
so sánh / ký tự thời gian
naive 999 240,4 ms -> O(n*m)
KMP 2,0 1,2 ms -> O(n+m)
Ở đây câu chuyện lật hẳn. Naive làm 999 so sánh mỗi ký tự — vì tại mỗi vị trí, nó khớp được 999 ký tự a rồi mới lệch ở ký tự b cuối cùng, rồi trượt một bước và lặp lại toàn bộ. Đó chính là O(n·m) hiện hình: 240 mili giây, gần một tỉ so sánh. KMP thì thản nhiên 2,0 so sánh mỗi ký tự, 1,2 mili giây — nhanh hơn 194 lần. Bài học đo lường: cái nhãn O(n·m) không nói dối, nó chỉ mô tả một góc đầu vào mà bạn có thể không bao giờ chạm tới; và giá trị của KMP không phải "luôn nhanh hơn" mà là "không bao giờ chậm thảm hại" — một bảo hiểm cho đúng góc đó. Trên văn bản thường, khoản bảo hiểm ấy không trả gì (thậm chí tốn nhẹ vì phí tiền xử lý); trên văn bản lặp lại, nó trả gấp 194 lần.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, thực dụng: với tìm kiếm chuỗi thông thường trên văn bản tự nhiên, cách naive hoàn toàn ổn — thậm chí là lựa chọn tốt vì đơn giản và không có phí tiền xử lý. Bạn không cần cài KMP để tìm một từ trong một tài liệu; vòng so sánh ngây thơ (hay hàm strstr/indexOf của thư viện, vốn thường là một biến thể naive tối ưu) chạy gần O(n). Đừng "tối ưu" bằng KMP khi dữ liệu của bạn không có cấu trúc lặp — bạn chỉ thêm phức tạp mà không nhanh hơn.
Hệ quả thứ hai: KMP (và họ hàng) đáng giá đúng khi dữ liệu có tính lặp lại cao — nơi trường hợp xấu O(n·m) thực sự sống. Đó là ADN và protein (bảng chữ nhỏ, nhiều đoạn lặp), dữ liệu nhị phân, tín hiệu tuần hoàn, hay bất kỳ đầu vào nào đối thủ có thể cố tình chế để làm naive quỳ gối (một dạng tấn công từ chối dịch vụ). Ở những chỗ đó, sự bảo đảm O(n+m) của KMP không phải xa xỉ mà là cần thiết. Câu hỏi để chọn: văn bản của tôi có lặp lại nhiều không, và đầu vào có thể do kẻ xấu tạo không?
Hệ quả thứ ba là con số mang theo: naive O(n·m) chỉ là trường hợp xấu nhất — trên văn bản ngẫu nhiên nó làm ~1 so sánh mỗi ký tự (gần O(n)) và ngang KMP, thậm chí nhanh hơn nhờ khỏi tiền xử lý; O(n·m) chỉ bật ra trên văn bản lặp lại (T toàn 'a', P là 'aa...b'), nơi naive làm ~m so sánh mỗi vị trí (999/ký tự, 240ms) còn KMP giữ O(n+m) (1,2ms, nhanh 194 lần). Một nhãn độ phức tạp xấu nhất không phải bản án cho mọi đầu vào; nó là cảnh báo về một góc — và biết góc đó nằm ở đâu (văn bản lặp) là biết khi nào cần đến thuật toán thông minh.
Thử ba mươi giây
Hỏi về dữ liệu bạn sẽ tìm kiếm: nó là văn bản tự nhiên (bảng chữ lớn, ít lặp) hay là chuỗi bảng chữ nhỏ lặp nhiều (ADN, chuỗi bit, log tuần hoàn)? Nếu là loại đầu, một vòng so sánh naive — hay hàm tìm chuỗi có sẵn của ngôn ngữ — gần như chắc chắn chạy gần O(n), và bạn không cần gì phức tạp hơn. Cách thử nhanh nếu bạn nghi ngờ: lấy đúng loại dữ liệu của bạn, chạy tìm kiếm naive và đếm trung bình bao nhiêu ký tự được so mỗi bước — nếu con số gần 1, bạn đang ở vùng O(n) an toàn; nếu nó lớn (gần bằng độ dài mẫu), dữ liệu của bạn có tính lặp và đã đến lúc KMP. Đừng chọn thuật toán theo nhãn xấu nhất trên giấy; chọn theo con số so sánh mỗi ký tự mà chính dữ liệu của bạn tạo ra.
