Ở bài KMP ta tìm một mẫu trong văn bản bằng một lượt quét O(n+m) — rất tốt cho một lần tìm. Nhưng nếu bạn phải tìm hàng nghìn mẫu khác nhau trong cùng một văn bản cố định (một cuốn sách, một bộ gen, một tập log), mỗi lần lại quét toàn bộ văn bản thì lãng phí: văn bản có đổi đâu. Suffix array đảo ngược sự đánh đổi — bỏ công tiền xử lý văn bản một lần, để mỗi lần tìm sau đó gần như tức thì. Bài này đo cả hai vế, và tìm ra điểm mà sự đánh đổi ấy bắt đầu có lãi.
Suffix array: mọi hậu tố, sắp theo thứ tự từ điển
Một hậu tố (suffix) của văn bản là một đoạn kéo từ vị trí nào đó đến hết. Văn bản dài n có đúng n hậu tố. Suffix array là mảng chứa chỉ số bắt đầu của tất cả n hậu tố ấy, nhưng sắp xếp theo thứ tự từ điển của chính các hậu tố. Nó không sao chép hậu tố (thế thì tốn O(n²) bộ nhớ), chỉ giữ n con số — mỗi số trỏ về một vị trí trong văn bản.
Vì sao sắp xếp lại giúp tìm mẫu? Chìa khóa: mọi lần xuất hiện của một mẫu P trong văn bản đều là phần đầu (tiền tố) của một hậu tố nào đó. Ví dụ nếu "ana" xuất hiện ở vị trí 5, thì hậu tố bắt đầu tại 5 là "ana..." — có "ana" làm tiền tố. Khi mọi hậu tố đã được sắp theo thứ tự từ điển, tất cả hậu tố bắt đầu bằng "ana" nằm kề nhau thành một khối liên tục. Thế là tìm mẫu quy về tìm nhị phân khối đó: hai lần nhị phân tìm biên trái và biên phải, ra ngay khoảng chứa mọi lần xuất hiện. Mỗi truy vấn tốn O(m log n) — với m là độ dài mẫu.
Đo: mỗi truy vấn nhanh hơn KMP gần hai vạn lần
Tôi dựng suffix array cho một văn bản 2 triệu ký tự (bảng chữ cái nhỏ để có nhiều lần trùng), rồi đo thời gian mỗi truy vấn của ba cách tìm mẫu dài 8: nhị phân trên suffix array, KMP, và quét ngây thơ. (Kiểm đúng đắn trước: cả ba đếm ra cùng số lần xuất hiện — 31 — nên ta đang so cùng một việc.)
Tra một mẫu (dài 8) trong văn bản 2 triệu ký tự:
suffix array (nhị phân) : 0,21 µs/truy vấn
KMP : 3.869 µs/truy vấn (chậm hơn SA 18.554 lần)
quét ngây thơ O(n·m) : 3.674 µs/truy vấn (chậm hơn SA 17.616 lần)
Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần. Lý do rõ: KMP và quét ngây thơ đều phải đi qua cả 2 triệu ký tự văn bản cho mỗi lần tìm — công tỉ lệ với n. Suffix array chỉ làm vài chục bước nhị phân trên mảng đã sắp (m log n ≈ 8 × 21 ≈ 170 phép so), không đụng tới phần lớn văn bản. Nếu chỉ nhìn con số này, ta sẽ kết luận ngay: suffix array là cách nhanh nhất để tìm chuỗi con. Đó chính là chỗ tôi đo hớ.
Một lần tôi đo hớ: có một hóa đơn phải trả trước
Con số 0,21 µs kia bỏ qua một thứ: suffix array không tự có. Phải dựng nó — tức sắp xếp toàn bộ n hậu tố — trước khi tra được lần đầu tiên. Tôi đo riêng bước dựng:
Dựng suffix array (sắp 2 triệu hậu tố): 358 ms (một lần)
Bộ nhớ: 2 triệu số nguyên = 8 MB
358 mili giây — so với 3,9 mili giây mà KMP cần cho một lần tìm không cần dựng gì. Vậy nếu bạn chỉ tìm một mẫu trong văn bản này, dùng suffix array là một sai lầm: bạn trả 358 ms tiền dựng để tiết kiệm vài micro giây tra, trong khi KMP xong việc trong 3,9 ms. Chi phí dựng lấn át hoàn toàn. Câu "suffix array là cách nhanh nhất" chỉ đúng cho một truy vấn nếu ta lờ đi cái hóa đơn trả trước — mà cái hóa đơn đó lớn gấp gần trăm lần một truy vấn KMP.
Chỗ đo hớ của tôi là đã so tốc độ truy vấn mà quên chi phí tiền xử lý. So đúng phải là so tổng công cho cả bài toán, gồm cả dựng lẫn tra. Và khi viết ra tổng công, câu hỏi lộ ra ngay: bạn tra bao nhiêu lần trên cùng một văn bản?
Điểm hòa vốn: khấu hao chi phí dựng
Gọi Q là số truy vấn. Suffix array tốn dựng + Q × tra_SA; KMP tốn Q × tra_KMP (không dựng gì). Tôi tính tổng cho Q tăng dần:
Tổng thời gian theo số truy vấn Q:
Q= 1 : SA 357,7 ms | KMP 3,9 ms -> KMP thắng
Q= 10 : SA 357,7 ms | KMP 38,7 ms -> KMP thắng
Q= 100 : SA 357,7 ms | KMP 386,9 ms -> SA thắng
Q= 1.000 : SA 357,9 ms | KMP 3.869,3 ms -> SA thắng
Q= 10.000 : SA 359,8 ms | KMP 38.693 ms -> SA thắng (nhanh ~100 lần)
Điểm hòa vốn rơi vào khoảng 93 truy vấn. Dưới ngưỡng đó, KMP thắng vì suffix array còn chưa trả xong tiền dựng. Trên ngưỡng đó, suffix array thắng — và thắng ngày một đậm: ở 10.000 truy vấn, tổng công của nó gần như không đổi (vẫn ~360 ms, vì tra quá rẻ) trong khi KMP leo tới 38 giây, chậm gấp trăm lần. Đây chính xác là bài toán khấu hao của phần trước: một chi phí trả trước đắt đỏ chỉ đáng khi được chia đều (khấu hao) qua đủ nhiều lần dùng. Suffix array là "mua sỉ": lỗ nếu mua ít, lãi lớn nếu mua nhiều.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn công cụ tìm chuỗi theo số lần tìm, không theo tốc độ mỗi lần. Tìm một mẫu một lần trong dữ liệu dùng-xong-bỏ? Dùng KMP, hoặc thậm chí hàm strstr/grep có sẵn — khỏi dựng gì. Tìm vô số mẫu trong một văn bản cố định, tra đi tra lại (chỉ mục tìm kiếm toàn văn, tra cứu bộ gen, phân tích log lặp lại)? Bỏ công dựng suffix array (hay chỉ mục tương đương) một lần, rồi hưởng truy vấn gần như tức thì mãi về sau. Ranh giới là bài toán khấu hao, và ở đây nó nằm quanh ~90 truy vấn — một con số bạn nên ước lượng cho tình huống của mình.
Hệ quả thứ hai: "tiền xử lý" là một sự đánh đổi thời gian, phải tính vào tổng. Rất nhiều cấu trúc tăng tốc — chỉ mục cơ sở dữ liệu, suffix array, bảng băm dựng sẵn, sắp xếp trước để nhị phân — đều theo cùng khuôn: trả trước để rẻ sau. Khi so chúng với cách "quét thẳng", đừng chỉ so tốc độ truy vấn; cộng cả chi phí dựng, rồi chia cho số lần dùng thật sự. Một chỉ mục dựng mất một giờ mà bạn chỉ tra một lần thì là lỗ.
Hệ quả thứ ba là bài học đo lường bao trùm: "nhanh nhất" là một câu vô nghĩa nếu chưa hỏi "cho bao nhiêu lần dùng". Con số mang theo: mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs), nhưng phải dựng trước tốn 358 ms; nên cho một truy vấn KMP thắng đậm, và suffix array chỉ có lãi sau khoảng 93 truy vấn trên cùng văn bản — trên đó thì nó nhanh gấp trăm lần. Đo tốc độ một thao tác mà quên chi phí chuẩn bị là đo nửa bài toán; luôn hỏi tổng công trên toàn bộ khối lượng việc thật.
Thử ba mươi giây
Nghĩ về công cụ bạn dùng hằng ngày qua lăng kính này. Khi bạn grep "từ khóa" tệp.log một lần, grep quét cả tệp — đúng lựa chọn cho một lần tìm, không dựng chỉ mục. Nhưng khi bạn gõ vào ô tìm kiếm của một cơ sở dữ liệu và nó trả kết quả tức thì trên hàng triệu bản ghi, nó không quét — nó đã dựng một chỉ mục (thường có họ hàng với suffix array/cây hậu tố) từ trước, và bạn đang hưởng truy vấn đã-khấu-hao. Thử tự hỏi với một tác vụ tìm kiếm bất kỳ của bạn: dữ liệu này tôi tìm một lần hay nghìn lần? Câu trả lời quyết định nên grep thẳng hay nên bỏ công dựng chỉ mục — và giờ bạn biết điểm hòa vốn nằm ở cỡ vài chục lần tra, không phải một.
