Naive string matching: vì sao O(n·m) chậm

TL;DR: Naive matching trượt pattern qua text từ trái sang phải, mỗi vị trí so từng ký tự. Worst-case O(n·m) xảy ra khi text lặp một ký tự (ví dụ "aaaa...a") và pattern gần như khớp hoàn toàn rồi lệch ở ký tự cuối, nên mỗi vị trí khởi đầu đều so gần hết pattern. Nhưng với văn bản tự nhiên và bảng chữ cái lớn, lệch xảy ra sớm nên thực nghiệm gần O(n). Hiểu rõ điểm lãng phí của naive (lùi con trỏ text và so lại đoạn đã biết) là chìa khoá để thấy tại sao KMP và Rabin-Karp ra đời.

Cứ hình dung bạn cần kiểm tra xem một đoạn DNA dài 10 triệu base pair có chứa chuỗi mồi (primer) dài 20 ký tự không. Cách đơn giản nhất: đặt chuỗi mồi vào vị trí 0, so từng ký tự, rồi trượt sang 1, so lại, tiếp tục cho đến cuối. Đó là naive matching: trực quan, dễ cài đặt, và trong trường hợp xấu nhất tốn tới 200 triệu phép so sánh. Bạn đã gặp nó mỗi khi gọi String.indexOf hay contains (xem bài String trong Java). Bài này phân tích cơ chế, worst-case, và điều kiện naive vẫn đủ dùng trước khi bạn đào sâu vào KMP ở bài sau.

1. Cơ chế trượt cửa sổ

Cách làm này giống việc dò một dòng trong trang sách bằng thước kẻ: đặt thước (pattern) dưới đoạn chữ, đối chiếu từng chữ; thấy lệch thì nhấc thước, dịch sang phải một chữ rồi đối chiếu lại từ chữ đầu thước.

Naive matching duy trì một cửa sổ (window) dài m (độ dài pattern) trượt qua text dài n. Với mỗi vị trí khởi đầu i từ 0 đến n - m, thuật toán so từng ký tự P[j] với T[i + j] cho j từ 0 đến m - 1. Nếu tất cả khớp → tìm thấy. Nếu có ký tự lệch → dịch cửa sổ sang phải 1 ô và bắt đầu lại từ j = 0. Đây là hai vòng lặp lồng nhau (vòng ngoài i, vòng trong j); nếu chưa quen đếm số lần lặp của vòng lồng, ôn lại Vòng lặp lồng nhau.

Điểm mấu chốt cần nhớ: khi lệch tại j = k, ta vứt bỏ mọi thông tin về k ký tự vừa khớp: con trỏ text lùi về i + 1 và so lại từ đầu. Đó là chỗ "lãng phí" mà KMP sẽ loại bỏ.

function naiveSearch(T, P):
    n <- T.length
    m <- P.length
    results <- rỗng
    for i from 0 to n - m:            -- dịch cửa sổ qua text
        j <- 0
        while j < m and T[i + j] = P[j]:   -- so từng ký tự
            j <- j + 1
        if j = m:                      -- khớp toàn bộ pattern
            thêm i vào results
    return results
// Time: O(n·m) worst-case  Space: O(1) ngoài kết quả

1.1 Trace nhỏ: T = "ABCABD", P = "ABD"

Nếu chưa quen đọc bảng trace, xem lại Bảng trace trước khi đọc bảng dưới.

Thứ bị vứt không trừu tượng chút nào: hai xác nhận vừa mua được, T[0] là A, T[1] là B, và một bước con trỏ. KMP ở bài sau giữ đúng hai xác nhận đó.