1. Phép xây dựng DFA cơ bắp
Chúng ta đang xét bài toán tìm tất cả các xuất hiện của chuỗi p[0..m-1] trong chuỗi s[0..n-1], với bộ ký tự là Σ. Thuật toán KMP thật ra cũng chỉ là mô phỏng một automaton đơn định (DFA). Lần này ta xây dựng hẳn một DFA để giải quyết bài toán này. Ta thiết kế DFA có ít trạng thái nhất để nhận dạng ngôn ngữ Σ*p.
Ví dụ, nếu p = "abaa" thì DFA là
Kiểm tra bằng … mắt, dễ thấy rằng DFA này nhận dạng pattern p = "abaa". Thế làm thể nào để xây dựng DFA trong trường hợp pattern bất kỳ? Ta có thể xây dựng DFA một cách đệ quy. Để đơn giản, giả sử pattern của ta là abaab, và ta đã xây dựng được DFA cho tiền tố abaa rồi (chính là DFA ở trên). Khi có thêm ký tự b, ta “bẻ” mũi tên nhãn b từ trạng thái số 4 trỏ ngang qua trạng thái mới, số 5. Thế các mũi tên từ trạng thái số 5 thì trỏ đi đâu? Nhớ rằng nếu không có trạng thái 5 thì khi gặp ký tự b ta từ trạng thái 4 chuyển sang trạng thái 2. Như vậy, trạng thái số 5 — với ý nghĩa là đã gặp ký tự b từ trạng thái 4 — sẽ phải di chuyển y như trạng thái 2. Vì thế, các mũi tên từ trạng thái 5 sẽ trỏ đi y như các mũi tên từ trạng thái 2. Kết quả là
Sau khi đã xây dựng được DFA thì phần còn lại của chương trình là rất đơn giản. Ta viết nó bằng Python:
def dfa_pm(s, p): # print all occurrences of pattern p in string s
n = len(s); m = len(p)
atoz = map(chr, range(97, 123)) # list from 'a' to 'z'
dfa = [dict.fromkeys(atoz, 0)] # the string matching automaton
# build the automaton
for i in range(m):
q = dfa[i][p[i]]
dfa[i][p[i]] = i+1
dfa.append({})
dfa[i+1].update(dfa[q])
# scan the text string
q = 0
for j in range(n):
q = dfa[q][s[j]]
if (q == m): print "Match at position ", j-m+1
>>> dfa_pm("abacabcabcabbc", "cabc")
Match at position 3
Match at position 6
Với cách viết như trên thì thuật toán này cần thời gian O(m|Σ|) để xây dựng DFA, không gian O(m|Σ|) để chứa DFA, và thời gian O(n) để quét chuỗi nhập. Với Σ nhỏ thì không có vấn đề gì, nhưng với Σ lớn thì cả thời gian tiền xử lý và không gian cần cho DFA hơi bị phí. Nhớ rằng, trong thuật toán Knuth-Morris-Pratt thì thời gian và không gian tiền xử lý chỉ có O(m) thôi.
2. Xây dựng DFA “nén”
Để giảm thời gian và không gian tiền xử lý, ta phân tích kỹ hơn cấu trúc của cái DFA nọ. Trạng thái số 0 có ý nghĩa là ta chưa gặp ký tự nào trong pattern. Nếu ta đang ở trạng thái thứ i, 1 ≤ i ≤ m thì có nghĩa là ta đã “match” được i ký tự của p. Cụ thể hơn, giả sử ta đã quét chuỗi nhập s đến vị trí s[j], cái hậu tố w dài nhất của s[0..j] mà cũng đồng thời là tiền tố của p có chiều dài đúng bằng |w| = i. Bạn đọc nên đối chiếu lại với thuật toán Morris-Pratt để thấy rằng Morris-Pratt (và KMP) thật sự là mô phỏng một DFA.
Cái DFA có hai loại cạnh, cạnh tiến là các cạnh loại (i, i+1), và cạnh lùi là các cạnh loại (k, i) với i ≤ k. Chức năng của cạnh tiến thì đã rõ. Xét một cạnh lùi (k, i, a), nghĩa là cạnh lùi (k, i) với nhãn là ký tự a. Ta gọi đại lượng k-i là chiều dài của cạnh lùi này. Lý do ta phải đi lùi là vì p[k] != a, không tiến được nữa. Nếu i == 0 thì có nghĩa là không có tiền tố nào của p[0..k-1] mà cũng đồng thời là hậu tố của p[0..k-1]a. Khi i > 0 thì p[0..i-1] là hậu tố của p[0..k-1]a. Đặc biệt ta suy ra rằng p[i-1] == a != p[k].
Gọi các cạnh lùi (k, i) với i > 0 là các cạnh lùi dương. Xét hai cạnh lùi dương (k, i, a) và (k', i', a') có chiều dài bằng nhau. Ta sẽ chứng minh rằng i == i', từ đó dễ thấy rằng k == k' và a == a'. Không mất tính tổng quát, giả sử i < i'. Như trên đã phân tích, ta có p[0..i'-1] là một hậu tố của p[0..k'-1]a'. Do đó, p[i-1..i'-1] là một hậu tố của p[0..k'-1]a'. Từng ký tự một thì ta phải có p[i'-1] == a', p[i'-2] == p[k'-1], vân vân, đến p[i-1] == p[(i-1)+(k'-i'+1)] Nhưng mà k'-i' == k-i. Do đó, p[i] == p[k], vô lý.
Do có tối đa m chiều dài khác nhau cho các cạnh lùi dương, mà mỗi chiều dài chỉ có một cạnh lùi dương (bất kể bộ ký tự lớn nhỏ!), tổng số cạnh lùi dương tối đa là m. Như vậy, thay vì dùng một bảng kích thước m|Σ| để lưu trữ cái DFA, ta chỉ cần lưu trữ m cạnh lùi dương. Tất cả các cạnh lùi khác là lùi về 0 và không cần phải lưu trữ chúng. Với mỗi một trạng thái i, ta lưu trữ một danh sách các cạnh lùi dương từ nó. Cấu trúc dữ liệu thích hợp là một associative array (trong Python gọi là dictionary), tại vì ta cần chứa và tìm kiếm các cặp (key, value) với key là một ký tự và value là một trạng thái dương. Các associative arrays thường được hiện thực bằng một dạng cây cân bằng (như cây đỏ đen), hoặc bảng băm. Cây đỏ đen với m đỉnh chẳng hạn, thì các phép tìm kiếm và insert mất O(log m) thời gian. Với bảng băm thì tìm kiếm chỉ mất O(1) thời gian, và mất khoảng O(m)-space để xây dựng. Nhìn chung, bằng cách “nén” các cạnh về trạng thái 0, xây dựng DFA chỉ còn mất O(m) không/thời gian.
Mã Python dùng dictionary có thể viết như sau:
def compact_dfa(s, p): # print all occurrences of pattern p in string s
n = len(s); m = len(p); dfa = [{}]
# build the automaton
for i in range(m):
if (dfa[i].has_key(p[i])): q = dfa[i][p[i]]
else: q = 0
dfa[i][p[i]] = i+1
dfa.append({})
for key in dfa[q].keys(): dfa[i+1][key] = dfa[q][key]
# scan the text string
q = 0
for j in range(n):
if (dfa[q].has_key(s[j])): q = dfa[q][s[j]]
else: q = 0
if (q == m): print "Match at position ", j-m+1