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();
}
}
}

Read More...

Một số thuật toán cơ bản

 

Kiểm tra 1 số nguyên tố

 + Định nghĩa: Là số nguyên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Các số nguyên tố từ 1-100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

+ Thuật toán: Để kiểm tra 1 số nguyên n có phải số nguyên tố hay không, ta làm theo các bước.
- Nếu n<2 thì không phải số nguyên tố.
- Kiểm tra trong đoạn từ 2..sqrt(n) xem có ước của n không, nếu có tồn tại thì n không phải số nguyên tố
- Ngược lại, n là số nguyên tố.

 

 
Phương pháp sàng Eratosthene

 + Mục đích: Để lập bảng các số nguyên tố nhỏ hơn hoặc bằng 1 số n cho trước.

+ Thuật toán: Sử dụng 1 bảng bool isPrimeNumber[0..n+1] để lưu kết quả
- Khởi tạo: tất cả các số từ 1->n là nguyên tố.
- Xóa số 1 ra khỏi bảng.
- Lặp: Tìm 1 số nguyên tố đầu tiên trong bảng sau đó xóa tất cả các bội của nó trong bảng.
- Quá trình lặp kết thúc khi gặp số nguyên tố >= sqrt(n).
- Tất cả các số chưa bị xóa trong bảng là số nguyên tố.

 

Tìm ước số chung lớn nhất (GCD)

+ Định nghĩa: Ước số chung lớn nhất (Greatest Common Divisor) của 2 số a và b, được định nghĩa như sau: gcd(a,b)=d <=> d là số lớn nhất trong tất cả các ước chung của a và b.

+ Thuật toán: Giải thuật Euclid, định nghĩa đệ qui như sau:
- gcd(a,0)=a
- gcd(a,b)=gcd(b,a mod b)

 

 

Tìm bội số chung nhỏ nhất (lcm)

 + Định nghĩa: Bội số chung nhỏ nhất (Least Common Multiple) của 2 số a và b được định nghĩa LCM(a,b)=m <=> m là số nhỏ nhất trong tất cả các bội chung của a và b.

+ Thuật toán: Ta có công thức:

 

 

Tính n giai thừa (Factorial)

 + Công thức:

 

 Phát biểu bằng lời: Giai thừa của 1 số nguyên dương n là tích tất cả các số nguyên dương nhỏ hơn hoặc bằng n.

 + Thuật toán: Ta có thuật toán đệ qui như sau:

 

 
Tính tổ hợp chập k của n

 + Công thức:

  

 + Thuật toán:
- Trâu bò (Brute Force): sử dụng hàm tính giai thừa.

- Sử dụng vòng lặp:

 

Kiểm tra số chính phương

 + Định nghĩa: Số chính phương (SquareNumber) là số có căn bậc 2 là 1 số nguyên. Ví dụ: 4,9,100...

+ Thuật toán: Để kiểm tra n có phải số chính phương hay không ta lấy phần nguyên của căn bậc 2 của n rồi bình phương, sau đó so sánh với n.
Ví dụ: sqrt(4)=2.0 Ta thấy 2^2=4 => 4 là số chính phương
sqrt(7)=2.4657 , phần nguyên là 2. Ta thấy 2^2 <> 7 => 7 không phải số chính phương.

Tìm kiếm nhị phân (Binary Search)

 + Sơ lược: Tìm kiếm nhị phân là thuật toán nhằm xác định vị trí của 1 phần tử trong 1 mảng đã được sắp xếp. Thuật toán hoạt động dựa trên việc so sánh giá trị phần tử đầu vào với phần tử ở giữa (middle) của dãy. Việc so sánh sẽ cho biết phần tử ở giữa này bằng, nhỏ hơn hay lớn hơn giá trị đầu vào. Khi phần tử được đem so sánh mà bằng input thì việc tìm kiếm sẽ kết thúc và trả về vị trí của phần tử đó. Nếu phần tử này nhỏ hơn input thì đồng nghĩa với việc ta cần tìm input trong đoạn từ middle+1..top, ngược lại nếu lớn hơn input thì ta cần tìm input trong đoạn bottom..middle-1. Khi dãy tại bước hiện tại không có phần tử nào (bottom>top) thì không cần tìm kiếm. Kết thúc quá trình tìm kiếm nếu không thấy input xuất hiện trong dãy thì kết quả trả về -1.

+ Code:Visual C# Code:

public int BinarySearch(int[] a, int value, int bottom, int top)
{
while (bottom <= top) // trong khi dãy đang xét còn phần tử
{
int middle = (bottom + top) / 2;
if (a[middle] == value) return middle; // đã tìm thấy tại vị trí middle, quá trình tìm kiếm dừng.
else if (a[middle] > value) top = middle - 1; // cần tìm value trong đoạn bottom..middle-1
else bottom = middle + 1; // cần tìm value trong đoạn middle+1..top
}
return -1; //Không tìm thấy
}

Chú ý: 
+ Độ phức tạp của thuật toán là O(log(n))
+ Thông thường giá trị bottom và top ban đầu tương ứng với 0 và N-1.

Số hoàn hảo (Perfect Number)

 + Định nghĩa: Số hoàn hảo là số có tổng các ước nhỏ hơn nó bằng chính nó. Ví dụ: 6 = 1+2+3. 28 = 1+2+4+7+14.

+ Thuật toán: Để kiểm tra n có phải Perfect Number hay không, đi tìm tổng tất cả các ước nhỏ hơn n rồi so sánh.

 

 

Kiểm tra số nguyên tố cùng nhau

 + Đặt vấn đề: Trong khi thao tác với các con số nhiều lúc các bạn gặp phải cụm từ hai số nguyên tố cùng nhau!; lúc đó có bạn nghĩ rằng đó phải là 2 số nguyên tố gần nhau. Hì, sai mất rồi đó; vậy nên trong Vấn đề 5 Peter đã khái quát qua (dẫn các bạn trước khi vào vấn đề này) là: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau khi và chỉ khi Ước chung lớn nhất của chúng là 1; tức là (a,b)=1; chứ không hẳn a và b phải là 2 số nguyên tố đứng gần nhau (hoặc có một cái hiểu tương tự), dĩ nhiên nếu a và b là hai số nguyên tố khác nhau thì chúng cũng thoả mãn tính chất là hai số "nguyên tố cùng nhau" (Lẫn lộn quá, nhưng các bạn chú ý cho điều này).

+ Phương pháp: Vậy làm sao để kiểm tra chúng nguyên tố cùng nhau hay không? Rất đơn giản là (ký hiệu hàm là CoPrime()):
- Nếu ước chung lớn nhất của chúng khác 1 thì trị trả về cho hàm kiểm tra là 0, báo hiệu hai số không nguyên tố cùng nhau.
- Ngược lại, thì trị trả về cho hàm kiểm tra là 1, báo hiệu hai số nguyên tố cùng nhau.

 

 

Số các ước số nguyên dương của một số nguyên dương

 + Đặt vấn đề: Trong toán lý thuyết số thì vấn đề về liệt kê các ước nguyên dương của một số nguyên dương chiếm một vị trí cũng khá quan trọng, số các ước số nguyên dương của một số nguyên dương n được cho bởi công thức sau:
Các bạn thường gặp một bài toán phổ biến là Phân tích một số ra tích các thừa số nguyên tố (mà ngày xưa học lớp 6 Peter mới được tiếp cận); nhìn thấy các bạn giải quyết chúng khá đơn giản bằng các vòng lặp for. Đó là:

+ Code:C++ Code:
int NoOfDivisor(int n)
{
int dem=0;
for (int i=1;i<=(int)sqrt(n);i++)
if (n%i==0)
dem++;
return dem;
}

 

 

 

Read More...