Thuật toán KMP

[shinichikudo0686]

Mình đang nghiên cứu thuật toán KMP. Mình đọc cái cách làm của thuật toán này trong mấy cuốn sách rồi mà không hiểu, ai biết thì vô đây chỉ giáo với.

[cn894677]

Bạn không hiểu ở chỗ nào vậy. có phải ở hàm FailureFuntion không ?

[shinichikudo0686]

Mình thấy không hiểu chỗ cái hàm để ghi lại cái mốc để quay trở về khi search không đúng

Thật ra cái hàm này thì theo sách mình cũng chỉ hiểu sơ sơ và tuy là viết chạy được nhưng vẫn muốn kiếm người cùng bàn bạc để làm sáng tỏ hơn về vấn đề mình còn mơ hồ.
Thuật toán KMP là do Knutt-Moris-Pratt cùng nghĩ ra.
Ví dụ ta có 2 chuỗi:
1 0 1 0 1 0 0 1 1 1 chuỗi 1
1 0 1 0 0 1 1 1 chuỗi 2
ta thấy khi so sánh 2 chuỗi thì đến kí tự thứ 5 thì 2 chuỗi khác nhau. Theo bình thường thì để tìm chuỗi bạn phải bắt đầu lại từ vị trí đầu tiên của chuỗi 2, nhưng thật chất bạn không cần phải bắt đầu lại từ đầu vì đã có 2 kí tự đầu của chuỗi 2 giống với kí tự thứ 3,4 của chuỗi 1 nên chuỗi 2 bạn chỉ phải bắt đầu so sánh từ kí tự thứ 3. Vấn đề là chúng ta phải xác định vị trí quay về cho chuỗi khi phát hiện sự khác nhau. Mình hiểu được tới đó còn mấy phần kia mình thấy mơ hồ quá. Bạn nào có hứng thú về vấn đề này thì vô đây cùng bình luận còn không thì mình sẽ không nói về vấn đề này nữa.

[cn894677]

Mình hiểu ý bạn nói gì.Ban hãy coi chuối 2 gồm những String sau đây
String 1 :1
String 2 :10
String 3 :101
.
.
va cứ thế đến String 10100111.Như vậy sẽ có tất cả 8 String
Mình đưa cho bạn một đoạn mã viết dưới dạng Java về cách tính hàm này, bạn hãy đọc qua để tìm hiểu, mình thấy cũng hay,viết không giống như trong các sách
private static int[] kmpFailureFunktion(String pattern) {

// Feld initialisieren
int[] arr = new int[pattern.length()];

// gesamtes Muster durchlaufen
for (int i = 1; i < pattern.length(); i++) {

// aktuelles Teilmuster ermitteln
String sub = pattern.substring(0, i + 1);

// aktuelles Teilmuster bis zur Hälfte (aufgerundet) durchlaufen
for (int j = 0; j < (sub.length() + 1) / 2; j++) {
// Teilstring (Anfang) vom Teilmuster
String s1 = sub.substring(0, j + 1);
// Teilstring (Ende) vom Teilmuster
String s2 = sub.substring(sub.length() - 1 - j, sub.length());
// bei Übereinstimmung => Größe speichern
if (s1.equals(s2)) arr[i] = j + 1;
}
}
// Feld zurückgeben
return arr;
// Beispiele:
// arr("ABACAB")=[0,0,1,0,1,2]
// arr("BABBA")=[0,0,1,1,2]
}

[shinichikudo0686]

Phải chia string ra làm nhiều phần à??

[cn894677]

Không phải chia mà ngầm hiểu la như vậy.Nếu tại một vị trí mà hai chuỗi không trùng nhau, thì tại chuỗi 2, những phần tử từ vị trí số 1 đến trước vị trí không trùng đó ta coi là một string, ta xet String này vì nó trùng với một đoạn trên của String 1.Tại String này bạn hãy xét tính lặp lại các phần tử của chuỗi, bạn hãy đọc kỹ đoạn code thì sẽ hiểu cách tính ra thôi.

[bete]

Tui nghĩ ý của cái hàm là như vầy:

Giả sử mình đang ướm chuỗi con pattern vô văn bản V
Giả sử thêm là đang khớp cho tới chỉ số i (chỉ số bắt đầu từ 0) và không khớp tại chỉ số (i+1):

V[k-i] khớp với pattern[0]
V[k-i+1] khớp với pattern[1]
.......................
V[k] khớp với pattern[i]
V[k+1] không khớp với pattern[i+1]

Mình muốn dịch chuỗi con pattern sang phải 1 bước m (1 <= m <= i) với điều kiện m là nhỏ nhứt thỏa:

pattern[0] khớp với pattern[m]
pattern[1] khớp với pattern[m+1]
................
pattern[i-m] khớp với pattern[i]
(tức là chuỗi pattern[0,i-m] khớp với chuỗi pattern[m,i])

Khi đó thì mình sẽ có:

V[k-i+m] khớp với pattern[0] (vì cùng khớp với pattern[m])
V[k-i+m+1] khớp với pattern[1] (vì cùng khớp với pattern[m+1])
.....................
V[k] khớp với pattern[i-m] (vì cùng khớp với pattern[i])

Nếu mình tìm được m cho chỉ số i này thì bước kế mình chỉ cần so sánh V[k+1] với pattern[i-m+1]. Còn nếu mình tìm không được m cho chỉ số i này thì bước kế mình sẽ so sánh V[k+1] với pattern[0]

Mình để ý kỹ hơn thì thấy chuỗi pattern[0,i-m] khớp với chuỗi pattern[m,i] cũng chính là: xét chuỗi s pattern[0,i] (độ dài là i+1), xét thêm 1 độ dài (j+1) (j+1==i-m+1; j+1 < i+1), gọi s1 là chuỗi con độ dài j tính từ đầu của s (chỉ số 0), gọi s2 là chuỗi con độ dài j tính từ cuối của s (chỉ số i-m) => s1 == s2

Để tìm m nhỏ nhứt thì mình có thể:
- bắt đầu từ m=1, tăng dần, khi nào s1==s2 thì ngưng ngay
- bắt đầu từ m=i, giảm dần, khi nào s1==s2 thì ghi nhớ nhưng không ngưng mà tiếp tục giảm m

Có vẻ như cái hàm java đưa ra làm theo hướng thứ 2 (giảm m, vì j==(i-m) nên giảm m có thể thay bằng tăng j).

Nhưng tui có 1 điều thắc mắc là tại sao họ lại chặn j < (sub.length()+1)/2 ? Như vậy là bắt buộc bước m phải lớn hơn (xấp xỉ) 1/2 của độ dài của chuỗi sub.
Mà nếu mình xét:
V=abababac..... và pattern=abababad (không khớp ở chỉ số là 7) thì khi đó: s="abababa" và "ababa" (chỉ số: 0->4) khớp với "abc" (chỉ số 2->6) => dịch 2 bước (m=2 < 4) !!!

Không biết tui có hiểu sai cái hàm java hay không ?

Nhận xét: cái hàm java viết đơn giản, dễ nhớ, nhưng hơi trâu bò 1 chút. Tui nghĩ cái hàm được trình bày bài bản trong sách vở sẽ nhanh hơn, nhưng khó hiểu và khó nhớ hơn. Thiệt sự thì cái hàm này chỉ cần chạy có 1 lần => có chậm thì cũng không có ảnh hưởng gì mấy; nhưng hàm bài bản cũng có góc độ rất hay về ý tưởng thuật toán

(có gì sai sót mong được góp ý, xin cám ơn)

-thân

[cn894677]

Tôi thấy bạn viết nhiều quá, không có thời gian đọc hết :-).Có lẽ bạn vẫn chưa hiểu đúng lắm về cách tính này.Khi ta xét chuỗi pattern này (co độ dài là pattern.lengt = m ).Bạn xét i (i=0;i<=m/2;i++)và một biến j=0:Nếu pattern(i)==pattern(m-1-i)(trong java Array bắt đầu từ 0) thì j+=1, tiếp tục tăng i lên 1 nếu trùng tiếp thì j=2, như vậy ta thấy tại điểm pattern(j)này sẽ là vị trí cần phải lùi về ,khi String pattern không trùng với String text.Bạn có thấy đúng như vậy không(chính là giá trị cần tính của hàm FailureFunction).Chuỗi String pattern mình vừa nói ở trên bạn hãy tách thành những String pattern nhỏ hơn (như bài đầu tôi nói cho bạn, co 8 String, riêng String 1 luôn nhận giá trị 0)và cũng xét tương tụ như vậy, và như vậy bạn sẽ tính ra được cài hàm KMP này
Bạn không có gí sai sót cả.Chúc vui vẻ