Thuật toán Knuth-Morris-Pratt

+ Tác giả: Chuyên gia khoa học máy tính NQH

+ Đặt vấn đề: Pattern matching là một trong những bài toán cơ bản và quan trọng nhất của ngành máy tính.

Tìm patterns trong các chuỗi-DNA là bài toán cơ bản của sinh tin học. Các phần mềm quét virus hiện đại có mấy chục triệu “patterns” là các “chữ ký” (virus signature) của các con virus máy tính đã biết. Khi quét máy thì phần mềm phải tìm các patterns này trong các files hay bộ nhớ của máy. Mỗi pattern thường là một chuỗi bytes nhất định. Lệnh grep chúng ta thường dùng trong Unix cũng làm tác vụ tương tự, trong đó các patterns có thể được biểu diễn bằng các biểu thức chính quy (regular expressions).

Nếu chỉ tính các thuật toán tìm các xuất hiện của một chuỗi đơn (một chuỗi các ký tự cho sẵn) bên trong một chuỗi khác thôi thì ta đã có đến cả trăm thuật toán khác nhau. Knuth-Morris-Pratt (KMP) là một trong những thuật toán đó. KMP không phải là thuật toán nhanh nhất hay tốn ít bộ nhớ nhất trên thực tế. Trên thực tế các biến thể của thuật toán Boyer-Moore hay Rabin-Karp với hàm băm và bộ lọc Bloom thường được dùng. Ta sẽ nói về chúng sau. Nhưng KMP thật sự rất thanh lịch và nếu tác vụ tìm kiếm không ghê gớm quá thì KMP không kém Boyer-Moore là mấy.

Ý tưởng của KMP rất đơn giản. Nếu bạn đọc nó trong quyển CLRS (Introduction to Algorithms) thì bạn sẽ bị lạc trong sa mạc. Thật sự là CLRS làm cho mọi thứ phức tạp hơn cần thiết. Quá nhiều ký hiệu và quá ít trực quan. Ta sẽ thảo luận KMP dùng 2 bước. Bước 1 là thuật toán Morris-Pratt (1970, A linear pattern-matching algorithm, Technical Report 40, UC Berkeley). Bước 2 là một cải tiến của thuật toán MP, có thêm Knuth vào (1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350).

Mặc dù hai bài báo cách nhau 7 năm, thật ra là thuật toán này đã được khám phá từ khoảng 1969 với một lịch sử thú vị. Phần cuối bài báo của KMP mô tả chi tiết lịch sử này. Cả phần kỹ thuật lẫn lịch sử trong bài báo đều rất chi tiết, kiểu Knuth, đọc rất thích.

1. Thuật toán Morris-Pratt
MP là thuật toán thời gian O(n) đầu tiên cho bài này. Ý tưởng của thuật toán MP là như sau. Giả sử ta muốn tìm pattern p[0..m-1] trong chuỗi s[0..n-1]. Đến một lúc nào đó thì ta có mis-match: s[j] != p[i] như trong hình sau:



Nếu dùng thuật toán cơ bắp (điều mà bạn nên làm khi đi phỏng vấn người ta hỏi viết strstr() lên bảng) thì ta dịch p một vị trí và làm lại từ đầu. Thời gian chạy sẽ là O(mn). Tồi! Nhưng mà làm lại từ đầu thì rất phí công chúng ta đã so sánh đến s[j]. Ta tìm cách dịch p đi xa hơn. Càng xa càng tốt miễn là không bị lố qua một xuất hiện của pattern trong chuỗi s. Dễ thấy rằng, để giữ vị trí của j không đổi thì ta phải dịch p đi một đoạn sao cho một tiền tố (prefix) của p[0..i-1] được xếp trùng bằng một hậu tố (suffix) của p[0..i-1], tại vì đoạn hậu tố này đã được so trùng với đoạn hậu tố cùng chiều dài của s[0..j-1]. Khi đó, ta chỉ cần tiếp tục so sánh s[j] với p[map[i]] mà không cần làm lại từ đầu. Trong đó, map[i] < i chỉ chỗ cho ta biết xê dịch p như thế nào.

Chiều dài của sự xê dịch (bằng với đại lượng i - map[i]) được gọi là một chu kỳ (period) của chuỗi p[0..i-1]. Phần tiền tố và hậu tố trùng khớp với nhau được gọi là biên (border) của chuỗi p[0..i-1]. Chiều dài của biên bằng i trừ đi chu kỳ. Để cho sự xê dịch có nghĩa, chu kỳ phải lớn hơn 0 và vì thế biên của p[0..i-1] luôn có chiều dài nhỏ hơn i. Để tránh trường hợp bị bỏ sót một xuất hiện của p trong s thì ta phải chọn biên dài nhất của p[0..i-1], ký hiệu là border(p[0..i-1]).

Trong thuật toán MP ta tính trước dãy map. Sau đó dùng dãy map này để so sánh hai chuỗi. Chặt chẽ hơn, với một chuỗi x bất kỳ, định nghĩa w = border(x) là chuỗi w dài nhất thỏa mãn 0 ≤ |w| < |x| sao cho w vừa là tiền tố vừa là hậu tố của x, nghĩa là x = wy = zw, trong đó y, z là các chuỗi nào đó. Lưu ý rằng 0 < |y| = |z| = period(x).

Bây giờ giả sử ta đã có bảng map[0...m], trong đó map[0] = -1 và map[i] = |border(p[0..i-1])| với 1 ≤ i ≤ m. Thuật toán Morris-Pratt có thể được viết như sau:


Python Code:

def MP(s, p): # print all occurrences of pattern p in string s
map = compute_MP_map(p)
i = 0
n = len(s); m = len(p)
for j in range(n):
while ( (i >= 0) and (s[j] != p[i]) ):
i = map[i]
i = i+1
if (i == m):
print "Match at position ", j-m+1
i = map[i]

Ta phân tích thời gian chạy của MP dùng phương pháp phân tích khấu hao (Amortized Analysis). Ta cho mỗi chú s[j] 2 đồng xu để dùng. Và tưởng tượng bọn p[i] là m cái rọ. Lúc đầu bỏ vào rọ p[0] một đồng xu làm vốn. Mỗi lần phép so sánh ký tự ở dòng 6 được chạy thì ta dùng đồng xu có sẵn trong rọ p[i] để trả nợ cho phép so sánh này. (Lưu ý rằng ta giả sử nếu i=-1 thì không có phép so sánh. Nếu bạn cẩn thận bạn có thể bẻ đôi điều kiện của while ra để tránh truy cập p[-1]. Đoạn Python trên tôi đã chạy, không có vấn đề gì.) Xong rồi đến cuối, ngay trước khi thực hiện phép gán i = i+1 ở dòng 8 ta lấy 2 đồng xu của s[j] bỏ vào p[i] và p[i+1]. Như vậy thời gian chạy của MP là O(n), và nó chỉ dùng nhiều nhất 2n phép so sánh.

Vấn đề tiếp theo là làm sao tính map. Đây là một bài toán quy hoạch động hay. Lưu ý rằng biên của biên của một chuỗi x cũng là biên của x. Giả sử ta muốn tính map[i+1] = |border(p[0..i])|. Dễ thấy rằng, nếu p[i] = p[map[i]] thì map[i+1] = map[i] + 1. Nếu p[i] != p[map[i]] thì ta so p[i] với p[map[map[i]]], vân vân. Từ đó ta có đoạn mã sau:

Python Code:

def compute_MP_map(p):
m = len(p) # p is the input pattern
map = [-1]*(m+1) # map[0..m], the Morris-Pratt border map
i = 0; j = map[i]
while (i < m):
while ( (j >= 0) and (p[i] != p[j]) ):
j = map[j]
j = j+1; i = i+1
map[i] = j
return map

Bài tập: dùng phương pháp phân tích khấu hao tương tự như trên, chứng minh rằng thời gian chạy của compute_MP_map() là O(m).

Chạy thử:

C++ Code:

>>> MP("abcabcabcabc", "cabc")
Match at position 2
Match at position 5
Match at position 8

2. Thuật toán Knuth-Morris-Pratt

KMP cải tiến map một chút. Trong hình ở trên, nếu p[map[i]] = b thì ta lại có mis-match. Do đó, ta áp đặt một cú "dòm trước" (look ahead) khi tính map. Gọi MPmap là dãy map của thuật toán MP. Cái map cải tiến của thuật toán KMP được định nghĩa như sau. KMPmap[0] = -1. Với 1 ≤ i ≤ m-1 thì gọi j = MPmap[i]. Khi đó, nếu p[i] != p[j] thì KMPmap[i] = j. Nếu p[i] == p[j] thì KMPmap[i] = KMPmap[j]. Và cuối cùng, KMPmap[m] = MPmap[m]. Bạn nên nghĩ cẩn thận xem tại sao định nghĩa KMPmap như vậy là hữu lý.

Dĩ nhiên, nếu đã tính MPmap rồi thì tính KMPmap theo công thức trên dễ dàng thôi. Nhưng ta có thể viết hàm tính KMPmap trực tiếp. Đây là một bài tập lập trình rất hay! Trong Python có thể viết như sau:

Python Code:

def compute_KMP_map(p):
m = len(p) # p is the input pattern
map = [-1]*(m+1) # map[0..m], the Knuth-Morris-Pratt border map
i = 1; map[i] = 0; j = map[i]
while (i < m):
# at this point, j is MP_map[i], which is not necessarily KMP_map[i]
if (p[i] == p[j]):
map[i] = map[j]
else:
map[i] = j
while ( (j >= 0) and (p[i] != p[j]) ):
j = map[j]
j = j+1; i = i+1
map[m] = j
return map

def KMP(s, p): # print all occurrences of pattern p in string s
map = compute_KMP_map(p)
i = 0; j = 0
n = len(s); m = len(p)
for j in range(n):
while ( (i >= 0) and (s[j] != p[i]) ):
i = map[i]
i = i+1
if (i == m):
print "Match at position ", j-m+1
i = map[i]

>>> KMP("abcabcabcabc", "cabc")
Match at position 2
Match at position 5
Match at position 8

Điểm thú vị cuối cùng là, mỗi ký tự của chuỗi s được so sánh với nhiều nhất là (đại lượng này gọi là delay của thuật toán), trong đó là tỉ lệ vàng!

+ Code hoàn chỉnh:

Visual C# Code:

using System;

namespace Knuth_Morris_Pratt
{
class Test
{
private char[] s;
private char[] p;

public void Nhap()
{
Console.Write("Nhap xau S:");
string stdin1 = Console.ReadLine();
s = new char[stdin1.Length];
s = stdin1.ToCharArray();
Console.Write("Nhap xau P:");
string stdin2 = Console.ReadLine();
p = new char[stdin2.Length];
p = stdin2.ToCharArray();
}

private int[] compute_MP_map() // map[i]=| border(p[0..i-1]) |
{
int m = p.Length; // p is the input pattern
int[] MP_map = new int[m + 1]; // lưu ý rằng ta phải tính map[0..m]
// init
MP_map[0] = -1; // cái này chắc ai cũng hiểu
// bay gio di tinh map[1..m]
int i = 0; int j = MP_map[i];
while (i < m)
{
while (j >= 0 && (p[i] != p[j])) j = MP_map[j];
j++; i++;
MP_map[i] = j;
}
return MP_map;
}

private int[] compute_KMP_map() //thuật toán KMP cải tiến
{
int m = p.Length;
int[] KMP_map = new int[m + 1];
int[] MP_map = compute_MP_map();
KMP_map[0] = -1; KMP_map[m] = MP_map[m];
for (int i = 1; i < m; i++)
{
int j = MP_map[i];
if (p[i] != p[j]) KMP_map[i] = j;
else KMP_map[i] = MP_map[j];
}
return KMP_map;
}

public void Morris_Pratt()
{
int[] map = compute_KMP_map();
int n = s.Length;
int m = p.Length;
int i = 0;
string res = "";
for (int j = 0; j < n; j++)
{
while ((i >= 0) && (p[i] != s[j])) i = map[i];
i++; // Có 2 khả năng xảy ra: hoặc là đã đi hết chuỗi p (i=m-1) hoặc là i=-1 , lợi dụng cả 2 điều này
if (i == m)
{
res += (j - m + 1).ToString() + " ";
i = map[i];
}
}
Console.Write(res);
}


static void Main(string[] args)
{
Test object1 = new Test();
object1.Nhap();
object1.Morris_Pratt();

//Console.WriteLine("done");
Console.ReadLine();
}
}
}