Thuật toán KMP

Thuật toán KMP (Knuth-Morris-Pratt) là một thuật toán tìm kiếm chuỗi trong xâu với độ phức tạp thời gian O(n+m), trong đó n là độ dài của xâu và m là độ dài của chuỗi cần tìm. Thuật toán KMP sử dụng một bảng lớn để lưu trữ các thông tin về độ dài của các tiền tố và hậu tố của chuỗi cần tìm, từ đó giúp tối ưu hóa việc tìm kiếm.

Cách thực hiện thuật toán

Bước 1: Xây dựng bảng tiền tố và hậu tố

Trước khi thực hiện tìm kiếm chuỗi, ta cần xây dựng bảng tiền tố và hậu tố của chuỗi cần tìm. Bảng tiền tố (prefix table) là một mảng lưu trữ độ dài của các tiền tố của chuỗi tìm kiếm, trong khi bảng hậu tố (suffix table) là một mảng lưu trữ độ dài của các hậu tố của chuỗi tìm kiếm. Cả hai bảng này đều có độ dài bằng độ dài của chuỗi tìm kiếm.

Để xây dựng bảng tiền tố và hậu tố, ta có thể sử dụng một thuật toán đệ quy đơn giản như sau:

def prefix_suffix_table(pattern):
    n = len(pattern)
    table = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and pattern[j] != pattern[i]:
            j = table[j-1]
        if pattern[j] == pattern[i]:
            j += 1
        table[i] = j
    return table

Ví dụ, với chuỗi cần tìm kiếm là "ABABCABAA", bảng tiền tố và hậu tố tương ứng sẽ là:

prefix table: [0, 0, 1, 0, 1, 2, 3, 0, 1]
suffix table: [0, 1, 0, 0, 1, 2, 0, 1, 1]

Bước 2: Thực hiện tìm kiếm chuỗi

Sau khi xây dựng bảng tiền tố và hậu tố, ta có thể thực hiện tìm kiếm chuỗi bằng thuật toán KMP. Thuật toán KMP sử dụng hai biến i và j để theo dõi vị trí của xâu và chuỗi cần tìm trong quá trình tìm kiếm. Thuật toán sẽ di chuyển biến i qua từng ký tự của xâu, nếu ký tự hiện tại của xâu và ký tự hiện tại của chuỗi cần tìm giống nhau, thì biến j sẽ tăng lên một. Nếu ký tự hiện tại của xâu và ký tự hiện tại của chuỗi cần tìm không giống nhau, thì ta sẽ sử dụng bảng tiền tố và hậu tố để tìm vị trí mới của biến j.

Để thực hiện tìm kiếm chuỗi bằng thuật toán KMP, ta có thể sử dụng mã nguồn sau:

def kmp_search(text, pattern):
    m = len(pattern)
    n = len(text)
    table = prefix_suffix_table(pattern)
    i = 0
    j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            return i - j
        elifj > 0 and pattern[j] != text[i]:
            j = table[j-1]
        else:
            i += 1
    return -1

Ví dụ, nếu ta tìm kiếm chuỗi "ABABCABAA" trong xâu "ABABDABACDABABCABAA", ta sẽ có kết quả là vị trí đầu tiên của chuỗi cần tìm trong xâu là 14.

Giải thích thêm về bảng tiền tố

Bảng tiền tố là một mảng lưu độ dài của tiền tố dài nhất của mẫu, cũng là hậu tố của xâu con kết thúc tại vị trí hiện tại. Tiền tố là một xâu con bắt đầu của mẫu mà không phải là mẫu chính nó. Ví dụ, với mẫu "ABCD", bảng tiền tố sẽ là [0, 0, 0, 0], vì không có tiền tố nào dài hơn không mà cũng là hậu tố của xâu con kết thúc tại bất kỳ vị trí nào trong mẫu.

Bảng hậu tố là một mảng lưu độ dài của hậu tố dài nhất của mẫu, cũng là tiền tố của xâu con bắt đầu tại vị trí hiện tại. Hậu tố là một xâu con kết thúc của mẫu mà không phải là mẫu chính nó. Ví dụ, với mẫu "ABCD", bảng hậu tố cũng sẽ là [0, 0, 0, 0], vì không có hậu tố nào dài hơn không mà cũng là tiền tố của xâu con bắt đầu tại bất kỳ vị trí nào trong mẫu.

Trong quá trình tìm kiếm, bảng tiền tố và hậu tố được sử dụng để xác định vị trí bắt đầu của mẫu trong văn bản, mà không cần so sánh từng ký tự của mẫu với văn bản. Khi xảy ra một sự không phù hợp giữa văn bản và mẫu, thay vì bắt đầu so sánh từ đầu của mẫu, bảng tiền tố và hậu tố được sử dụng để xác định vị trí tiếp theo trong mẫu để tiếp tục so sánh. Điều này giúp giảm số lần so sánh giữa văn bản và mẫu, dẫn đến việc tìm kiếm nhanh hơn.

Dưới đây là ví dụ minh họa cho thuật toán KMP:

def kmp_search(text, pattern):
    prefix_table = [0] * len(pattern)
    suffix_table = [0] * len(pattern)
    # Tính toán bảng tiền tố và hậu tố
    for i in range(1, len(pattern)):
        j = prefix_table[i - 1]
        while j > 0 and pattern[i] != pattern[j]:
            j = prefix_table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        prefix_table[i] = j
    for i in range(len(pattern) - 2, -1, -1):
        j = suffix_table[i + 1]
        while j > 0 and pattern[i] != pattern[j]:
            j = prefix_table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        suffix_table[i] = j
    # Tìm kiếm mẫu trong văn bản
    i = 0
    j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                return i - j  # Tìm thấy mẫu tại vị trí i-j trong văn bản
        elif j > 0:
            j = prefix_table[j - 1]  # Sử dụng bảng tiền tố để xác định vị trí tiếp theo trong mẫu
        else:
            i += 1  # Tiếp tục tìm kiếm trong văn bản
    return -1  # Không tìm thấy mẫu trong văn bản

# Ví dụ
text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCD"
print(kmp_search(text, pattern))  # Kết quả: 15

Trong ví dụ này, mẫu "ABCD" được tìm kiếm trong văn bản "ABC ABCDAB ABCDABCDABDE". Khi xảy ra sự không phù hợp giữa văn bản và mẫu tại vị trí thứ tư của mẫu (tức là ký tự "D" trong mẫu không khớp với ký tự "A" trong văn bản), bảng tiền tố và hậu tố được sử dụng để xác định vị trí tiếp theo trong mẫu để tiếp tục so sánh, thay vì bắt đầu so sánh từ đầu của mẫu. Trong trường hợp này, bảng tiền tố cho biết tiền tố dài nhất của mẫu cũng là hậu tố của xâu con kết thúc tại vị trí 3 có độ dài bằng 0, và bảng hậu tố cho biết hậu tố dài nhất của mẫu cũng là tiền tố của xâu con bắt đầu tại vị trí 4 có độ dài bằng 0. Do đó, chúng ta có thể di chuyển mẫu sang phải một vị trí, tức là bắt đầu so sánh từ ký tự "B" thứ hai trong mẫu và ký tự "A" thứ năm trong văn bản.

Bằng cách sử dụng bảng tiền tố và hậu tố để xác định vị trí tiếp theo trong mẫu để tiếp tục so sánh, thuật toán KMP tránh được các so sánh không cần thiết giữa văn bản và mẫu, dẫn đến việc tìm kiếm nhanh hơn.

Ví dụ minh họa

Giả sử ta cần tìm chuỗi "ABCD" trong xâu "ABC ABCDAB ABCDABCDABDE". Ta sẽ thực hiện các bước như sau:

  1. Xây dựng bảng tiền tố và hậu tố của chuỗi cần tìm "ABCD":
prefix table: [0, 0, 0, 0]
suffix table: [0, 0, 0, 0]
  1. Thực hiện tìm kiếm chuỗi bằng thuật toán KMP. Ban đầu, i=0 và j=0.
  • So sánh ký tự đầu tiên của xâu và chuỗi cần tìm. Ký tự này là "A", giống với ký tự đầu tiên của chuỗi cần tìm. Ta tăng i và j lên một.

  • So sánh ký tự thứ hai của xâu và chuỗi cần tìm. Ký tự này là "B", giống với ký tự thứ hai của chuỗi cần tìm. Ta tăng i và j lên một.

  • So sánh ký tự thứ ba của xâu và chuỗi cần tìm. Ký tự này là "C", giống với ký tự thứ ba của chuỗi cần tìm. Ta tăng i và j lên một.

  • So sánh ký tự thứ tư của xâu và chuỗi cần tìm. Ký tự này là "D", giống với ký tự thứ tư của chuỗi cần tìm. Ta tăng i và j lên một.

  • Vì j bằng độ dài của chuỗi cần tìm, ta đã tìm thấy chuỗi cần tìm trong xâu. Kết quả là vị trí đầu tiên của chuỗi cần tìm trong xâu là 8.

Kết luận

Thuật toán KMP là một thuật toán tìm kiếm chuỗi hiệu quả trong xâu với độ phức tạp O(n+m). Việc sử dụng bảng tiền tố và hậu tố giúp tối ưu hóa việc tìm kiếm, giảm thiểu số lần so sánh cần thực hiện. Thuật toán này được sử dụng rộng rãi trong các ứng dụng tìm kiếm, xử lý ngôn ngữ tự nhiên, v.v.