×

Cài đặt thuật toán Knuth-Morris-Pratt (KMP) trong lập trình

Avatar of admin
admin 5 Views

Trong các bài toán xử lý chuỗi, việc tìm kiếm một chuỗi con trong một chuỗi lớn hơn là một trong những vấn đề thường gặp. Thuật toán Knuth-Morris-Pratt (KMP) được phát triển để giải quyết bài toán này một cách hiệu quả hơn so với các phương pháp tiếp cận truyền thống. Bài viết này sẽ cung cấp một cái nhìn chi tiết về cách thức hoạt động và cách cài đặt thuật toán này trong lập trình.

Nguyên lý hoạt động của thuật toán KMP

Thuật toán KMP hoạt động dựa trên ý tưởng tiết kiệm vòng lặp bằng cách sử dụng thông tin thu thập được trong quá trình tìm kiếm trước đó. Cụ thể, KMP tận dụng một mảng phụ thêm, gọi là mảng LPS (Longest Prefix Suffix), để tránh việc phải quay lại so sánh từ đầu chuỗi mỗi khi phát hiện một ký tự không khớp.

Mảng LPS

Mảng LPS tại vị trí i lưu trữ độ dài lớn nhất của prefix (tiền tố) của mẫu (pattern) P[0..i] cũng đồng thời là suffix (hậu tố) của P[0..i]. Mục đích của việc này là để khi phát hiện một ký tự không khớp, thuật toán có thể bỏ qua một số lượng ký tự nhất định thay vì kiểm tra lại từ đầu.

Cài đặt thuật toán KMP

Dưới đây là các bước để cài đặt thuật toán này:

  1. Tạo mảng LPS:

    • Khởi tạo mảng LPS với độ dài bằng chiều dài của mẫu (pattern).
    • Sử dụng hai biến chỉ mục: một để duyệt mẫu và một để theo dõi độ dài của prefix.

  2. Sử dụng mảng LPS trong tìm kiếm:

    • Lặp qua từng ký tự trong văn bản (text).
    • Sử dụng thông tin trong mảng LPS để điều chỉnh vị trí so sánh trong mẫu khi phát hiện ký tự không khớp.

Dưới đây là mã Python để minh họa cách cài đặt thuật toán KMP:

def compute_lps(pattern):
    length = 0
    lps = [0] * len(pattern)
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = 0 # index for text
    j = 0 # index for pattern
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

# Sử dụng ví dụ
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)

Giải thích mã nguồn

  1. Tạo mảng LPS (hàm compute_lps): Hàm này duyệt qua mẫu và tính giá trị mảng LPS dựa trên sự khớp nối của các ký tự trong mẫu.

  2. Tìm kiếm bằng KMP (hàm kmp_search): Hàm này duyệt qua văn bản và mẫu, sử dụng mảng LPS để điều chỉnh vị trí bắt đầu so sánh khi phát hiện ký tự không khớp.

Ưu điểm của KMP

  • Hiệu quả hơn trong nhiều tình huống: Với độ phức tạp thời gian O(n), nơi n là độ dài của văn bản, KMP vượt trội hơn các phương pháp tìm kiếm chuỗi truyền thống khi xử lý các dữ liệu lớn.
  • Không cần quay lại: Nhờ việc sử dụng mảng LPS, KMP tránh được việc phải quay lại kiểm tra lại các ký tự trước đó.

Kết luận

Thuật toán này là một công cụ mạnh mẽ trong xử lý chuỗi, đặc biệt là trong các ứng dụng yêu cầu tìm kiếm nhanh như trình duyệt văn bản, xử lý ngôn ngữ tự nhiên và nhiều lĩnh vực khác. Hy vọng rằng bài viết này đã giúp bạn hiểu rõ hơn và có thể áp dụng thuật toán này trong các dự án của mình.

Comments

Bài viết liên quan