Trong bài viết này, ta sẽ cùng tìm hiểu về thuật toán Knuth-Morris-Pratt được áp dụng trong tìm kiếm chuỗi con trong một chuỗi khác. Ta sẽ lấy ví dụ minh họa cho thuật toán này.

1. Tổng quan

Ý tưởng đằng sau cách tiếp cận đối sánh mẫu này có lẽ dễ nắm bắt nhất nếu chúng ta tưởng tượng việc đặt mẫu lên trên văn bản và trượt nó sang phải theo một cách nhất định.

Ta sẽ xem xét ví dụ tìm kiếm mẫu abcabcacab trong chuỗi ký tự babcbabcabcaabcabcabcacabc. ban đầu chúng ta sẽ đặt mẫu ở phần bên trái và chuẩn bị quét ký tự ngoài cùng bên trái của văn bản đầu vào.

thuat-toan-knuth-morris-pratt

Mũi tên ở đây cho biết ký tự văn bản hiện tại. Vì nó trỏ đến b, không khớp với a trong mẫu, do đó, chúng ta sẽ chuyển mẫu dịch sang phải một khoảng và chuyển sang vị trí tiếp theo.

thuat-toan-knuth-morris-pratt_1

Bây giờ chúng ta có thể thấy có một sự trùng khớp ở đây, vì vậy mẫu vẫn được giữ nguyên trong khi các ký tự tiếp theo sẽ được quét.

thuat-toan-knuth-morris-pratt_2

Và theo cách tiếp cân như vậy, ta sẽ cứ tiếp tục kiểm tra lần lượt từng ký tự trong mẫu so với chuỗi ký tự. Điều này sẽ gây tồn nhiếu thời gian nếu chuỗi dài hơn và lớn hơn. Do đó, thuật toán Knuth-Morris-Pratt sẽ được ứng dụng để giải quyết bài toán này.

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

Năm 1977, Donald Knuth, Vaughan Pratt và James H. Morris đã đưa ra một thuật toán tìm kiếm chuỗi được gọi là thuật toán KMP. Trong thuật toán KMP, ta sẽ cố gắng bỏ qua một số chữ cái.

Thuật toán hoạt động như sau:

Đầu tiên, chúng ta cần tạo một bảng đối sánh mẫu P.
Sau đó, chúng ta sẽ kiểm tra các mẫu bằng sự trợ giúp của bảng P.
Nếu bất kỳ ký tự nào không khớp, chúng ta có thể bỏ qua một số ký tự dựa trên bảng P này.

Bảng đối sánh từng phần

Ý tưởng chính của KMP chính là nằm ở bảng đối sánh một phần. Sau đây là bảng đối sánh từng phần cho mẫu cần tìm kiếm "abababca" như sau:

Ký tự	a	b	a	b	a	b	c	a
Chỉ số	0	1	2	3	4	5	6	7
Giá trị	0	0	1	2	3	4	0	1

Nếu ta có một mẫu tám ký tự (giả sử là “abababca”), bảng đối sánh từng phần của ta sẽ có tám ô. Nếu ta nhìn vào ô thứ tám và ô cuối cùng trong bảng, ta sẽ quan tâm đến toàn bộ mẫu (“abababca”). Nếu ta nhìn vào ô thứ bảy trong bảng, ta sẽ chỉ quan tâm đến bảy ký tự đầu tiên trong mẫu (“abababc”); chữ cái thứ tám (“a”) không liên quan. Nếu ta nhìn vào ô thứ sáu của bảng, thì ta sẽ chỉ quan tâm tới 6 chữ cái đầu tiên, và cứ như vậy.

[___WARNING_Lưu ý rằng ta chưa có nói về ý nghĩa của từng ô mà mới chỉ là lướt qua._WARNING___]

Bây giờ, để nói về ý nghĩa, chúng ta cần biết về tiền tố thích hợp (Proper Prefixes) và hậu tố thích hợp (Proper Suffixes).

Tiền tố thích hợp: Tất cả các ký tự trong một chuỗi, với một hoặc nhiều ký tự bị cắt ở cuối. “S”, “Sn”, “Sna” và “Snak” đều là tiền tố thích hợp của “Snake”.
Hậu tố thích hợp: Tất cả các ký tự trong một chuỗi, có một hoặc nhiều ký tự bị cắt bỏ phần đầu. “alo”, “uffalo”, “lo”, “o” đều là hậu tố thích hợp của “Buffalo”.

Tóm lại, ý tưởng chính là:

Độ dài của tiền tố thích hợp dài nhất trong mẫu (con) khớp với một hậu tố thích hợp trong cùng một mẫu (con).

Chúng ta sẽ xem xét về điều đó như sau. Giả sử chúng ta đang tìm kiếm trong ô thứ ba. Như đã đề cập ở trên, điều này có nghĩa là chúng ta chỉ quan tâm đến ba ký tự đầu tiên (“aba”). Trong “aba”, có hai tiền tố thích hợp là “a” và “ab” và hai hậu tố thích hợp (“a” và “ba”). Tiền tố thích hợp “ab” không khớp với một trong hai hậu tố thích hợp. Tuy nhiên, tiền tố thích hợp “a” khớp với hậu tố thích hợp “a”. Do đó, độ dài của tiền tố thích hợp dài nhất khớp với hậu tố thích hợp, trong trường hợp này, là 1.

Ta sẽ thử nó cho ô số bốn. Ở đây, chúng ta quan tâm đến bốn ký tự đầu tiên (“abab”). Chúng ta có ba tiền tố thích hợp là “a”, “ab” và “aba” và ba hậu tố thích hợp (“b”, “ab” và “bab”). Lần này, “ab” có trong cả hậu tố và tiền tố thích hợp và có độ dài là hai ký tự, vì vậy ô bốn nhận giá trị 2.

Chúng ta sẽ cũng thử nó cho ô số năm là “ababa”. Chúng ta có bốn tiền tố thích hợp (“a”, “ab”, “aba” và “abab”) và bốn hậu tố thích hợp (“a”, “ba”, “aba” và “baba”). Bây giờ, chúng ta có hai kết quả phù hợp là “a” và “aba” đều là tiền tố thích hợp và hậu tố thích hợp. Vì “aba” dài hơn “a” nên nó sẽ được chọn và ô năm nhận giá trị 3.

Giờ ta sẽ chuyển sang ô thứ bảy (ô thứ hai đến ô cuối cùng), có liên quan đến mẫu “abababc”. Ngay cả khi không liệt kê tất cả các tiền tố và hậu tố thích hợp, rõ ràng là sẽ không có bất kỳ kết quả phù hợp nào; tất cả các hậu tố sẽ kết thúc bằng chữ cái “c” và không có tiền tố nào khác. Vì không có kết quả phù hợp nào nên ô thứ bảy nhận giá trị là 0.

Cuối cùng, ta sẽ xem xét ô số tám, ô này liên quan đến toàn bộ mẫu (“abababca”). Vì cả hai đều bắt đầu và kết thúc bằng “a”, chúng ta biết rằng chắc chắn sẽ có giá trị ít nhất là 1. Từ độ dài từ hai trở lên, tất cả các hậu tố đều chứa c, trong khi chỉ có tiền tố cuối cùng (“abababc”). Tiền tố bảy ký tự này không khớp với hậu tố bảy ký tự (“bababca”), vì vậy ô tám nhận giá trị là 1.

Dưới đây là code mẫu tham khảo về cách thức để thiết lập bảng Đối sánh từng phần

RUN_CODE (*** phân biệt ***)

Python 3

p = "abcabcacab"
failureFunction(p)

def failureFunction(p):
    f = [0] * len(p)
    f[0] = 0
    for j in range(0, len(p)):
        f[j] = kiemTra(p, j)
    print(*f)

def kiemTra(p, j):
    i = j - 1
    print("\n Kiểm tra giá trị:")
    for k in range (0,j+1):
        print(p[k],end = " ")
    while i >= 1:
        if soSanhChuoi(p, j+1, i) == 1:
            print(" Ra kết quả i = ",i)
            return i
        i -= 1
    print("Không ra gì cả")
    return 0

def soSanhChuoi(p, j, i):
    check = 0
    # Bắt đầu kiểm tra chuỗi hậu tố với chuỗi tiền tố
    for k in range(i):
        # Kiểm tra từng ký tự của chuỗi hậu tố với chuỗi ký tự của chuỗi tiền tố
        # Tại đây chuỗi tiền tố độ dài là [0..n] thì chuỗi hậu tố chỉ kiểm tra tới [1..n]
        if p[k] == p[j - i + k]:
            check += 1
    if check == i:
        return 1
    return 0

Làm cách nào để sử dụng bảng đối sánh một phần?

Chúng ta có thể sử dụng các giá trị trong bảng đối sánh từng phần để bỏ qua (thay vì thực hiện lại các so sánh cũ không cần thiết) khi chúng ta tìm thấy đối sánh từng phần. Công thức hoạt động như sau:

Nếu tìm thấy kết quả trùng khớp một phần của độ dài part_match_length và table[part_match_length]> 1, chúng ta có thể bỏ qua part_match_length - table[part_match_length - 1] ký tự.

Giả sử chúng ta đang đối sánh mẫu “abababca” với một đoạn văn bản “bacbababaabcbab”. Sau đây là bảng đối sánh từng phần của chúng ta để dễ dàng tham chiếu:

Ký tự	a	b	a	b	a	b	c	a
Chỉ số	0	1	2	3	4	5	6	7
Giá trị	0	0	1	2	3	4	0	1

Đầu tiên chúng ta có được sự trùng khớp một phần nằm tại vị trí như trong hình dưới đây:

thuat-toan-knuth-morris-pratt_3

Độ dài của đối sánh một phần partial_match_length trong trường hợp này là 1. Giá trị tại table[part_match_length - 1] (hoặc table[0]) là 0, vì vậy chúng ta sẽ không thể bỏ qua bất kỳ ký tự nào. Đối sánh một phần tiếp theo mà chúng ta nhận được là:

thuat-toan-knuth-morris-pratt_4

Độ dài đối sánh một phần trong trường hợp này là 5. Giá trị tại table[part_match_length - 1] (hoặc table[4]) là 3. Điều này có nghĩa là ta sẽ bỏ qua partial_match_length - table[partial_match_length - 1] hay 5 - table[4] = 5 – 3 = 2 ký tự.

thuat-toan-knuth-morris-pratt_5

Trong đó x là ký tự bỏ qua.

Độ dài của đối sánh một phần trong trường hợp này là 3. Giá trị tại table[part_match_length - 1] (hoặc table[2]) là 1. Điều đó có nghĩa là chúng ta có thể bỏ qua partial_match_length - table[partial_match_length - 1] = 3 - table[2] = 3 - 1 = 2 ký tự.

thuat-toan-knuth-morris-pratt_6

Tại đây, mẫu của chúng ta dài hơn các ký tự còn lại trong văn bản, vì vậy chúng ta biết rằng sẽ không có sự trùng khớp nào.

Ta có thể tham khảo hàm xử lý thuật toán thông qua đoạn code dưới đây

Read_Code (*** phân biệt ***)

Python 3

def xuLy(t, p, table):
    i = 0
    j = 0
    check = 0
    sopheptinhlap = 0
    part_match_length = j
    k = i + j
    while part_match_length != len(p):
        if t[k] == p[j]:
            k += 1
            j += 1
            part_match_length += 1
            sopheptinhlap += 1
        elif table[part_match_length - 1]>0 and i >0 and part_match_length - 1 >= 0:
            i += part_match_length - table[part_match_length-1]
            j = 0 
            sopheptinhlap += 1
            break
        else:
            i +=1
            j=0
            sopheptinhlap += 1    
            break
        
    if part_match_length == len(p):
        print("\nKQ: Vi tri", i)
        check = 1

    if check == 0:
        print("\nKQ: Khong co chuoi can tim")
    return sopheptinhlap

Như vậy, ta đã hoàn thành xong thuật toán Knuth-Morris-Pratt.

3. Độ phức tạp của thuật toán Knuth-Morris-Pratt

Đối với tính toán bảng P, vòng lặp for được lặp lại $m - 1$ lần trong đó m là kích thước của chuỗi mẫu. Độ phức tạp của phần đó là $O(m)$. Và trong phần đối sánh KMP, vòng lặp chạy n lần trong đó n là kích thước của văn bản S. Vì vậy, độ phức tạp về thời gian cho phần đối sánh là $O(n)$. Và thuật toán KMP chạy ở độ phức tạp về thời gian là $O(m + n)$. Độ phức tạp về không gian của thuật toán này là $O(n)$.

4. Hiệu chỉnh thuật toán Knuth-Morris-Pratt

Ngoài ra, thay vì luôn phải tìm từ giá trị P[0] sẽ khiến gây mất nhiều thời gian, ta có thể tối ưu hóa thuật toán Knuth-Morrirs-Pratt bằng cách sau:

nếu không khớp tại vị trí P[j]
if (P[j] != T[i]){
   j = table[j-1]
}

Trên đây là khái niệm và ví dụ cơ bản về danh sách liên kết đôi. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

Thuật toán Knuth-Morris-Pratt trong tìm kiếm xâu con