Trong lập trình, thuật toán Suffix Array Construction là một kỹ thuật quan trọng được sử dụng để tìm kiếm mẫu và phân tích chuỗi nhanh chóng. Cấu trúc dữ liệu này sắp xếp tất cả các hậu tố của một chuỗi theo thứ tự từ điển. Điều này góp phần vào việc tối ưu hóa các thuật toán tìm kiếm mẫu bằng cách giảm thiểu thời gian cần thiết để khớp các chuỗi con trong một chuỗi dài. Bài viết này sẽ hướng dẫn bạn cách cài đặt thuật toán xây dựng mảng hậu tố một cách chi tiết.
Giới Thiệu về Mảng Hậu Tố
Mảng hậu tố của một chuỗi là một mảng chứa các chỉ số bắt đầu của mọi hậu tố trong chuỗi đó, được sắp xếp theo thứ tự từ điển. Ví dụ, đối với chuỗi "banana", các hậu tố sẽ gồm "banana", "anana", "nana", "ana", "na", và "a".
Các Bước Cài Đặt
1. Tạo Các Hậu Tố
Mỗi hậu tố có thể được đại diện bởi chỉ số bắt đầu của nó trong chuỗi gốc. Do đó, bước đầu tiên chính là việc lặp qua chuỗi và tạo ra danh sách các hậu tố với chỉ số tương ứng.
def suffixes(s):
return [s[i:] for i in range(len(s))]
2. Sắp Xếp Các Hậu Tố
Tiếp theo, chúng ta cần sắp xếp các hậu tố theo thứ tự từ điển. Trong Python, việc này có thể thực hiện dễ dàng bằng cách sử dụng hàm sorted().
def sorted_suffixes(s):
suffixes_list = suffixes(s)
return sorted(suffixes_list)
3. Xây Dựng Mảng Hậu Tố
Mảng hậu tố chỉ chứa các chỉ số bắt đầu của các hậu tố. Sau khi sắp xếp xong các hậu tố, chúng ta cần chuyển đổi danh sách này thành một mảng chứa chỉ số.
def suffix_array(s):
suffixes_list = suffixes(s)
sorted_suffixes_list = sorted([(suffix, i) for i, suffix in enumerate(suffixes_list)])
suffix_array_result = [index for suffix, index in sorted_suffixes_list]
return suffix_array_result
Cài Đặt Hoàn Chỉnh
Dưới đây là cài đặt hoàn chỉnh của thuật toán xây dựng mảng hậu tố bằng Python:
def build_suffix_array(s):
n = len(s)
suffixes = [(s[i:], i) for i in range(n)]
suffixes.sort()
suffix_array = [suffix[1] for suffix in suffixes]
return suffix_array
# Ví dụ sử dụng
s = "banana"
suffix_array = build_suffix_array(s)
print("Mảng hậu tố:", suffix_array)
Tối Ưu Hóa
Thuật toán trên có độ phức tạp thời gian là O(n log n), phù hợp cho nhiều ứng dụng đơn giản. Tuy nhiên, đối với các chuỗi dài hơn hoặc trong các ứng dụng đòi hỏi hiệu suất cao, bạn có thể áp dụng các thuật toán nâng cao như thuật toán SA-IS (Suffix Array Induced Sorting) với độ phức tạp thời gian là O(n).
Dưới đây là cách triển khai cài đặt nâng cao này:
def build_suffix_array_optimized(s):
import numpy as np
def sort_cyclic_shifts(s):
n = len(s)
alphabet = sorted(set(s))
p = [0] * n
c = [0] * n
cnt = [0] * (len(alphabet))
for i in range(n):
cnt[alphabet.index(s[i])] += 1
for i in range(1, len(alphabet)):
cnt[i] += cnt[i - 1]
for i in range(n - 1, -1, -1):
c[i] = alphabet.index(s[i])
cnt[c[i]] -= 1
p[cnt[c[i]]] = i
c[p[0]] = 0
classes = 1
for i in range(1, n):
if s[p[i]] != s[p[i - 1]]:
classes += 1
c[p[i]] = classes - 1
pn = [0] * n
cn = [0] * n
h = 0
while (1 << h) < n:
for i in range(n):
pn[i] = p[i] - (1 << h)
if pn[i] < 0:
pn[i] += n
cnt = [0] * classes
for i in range(n):
cnt[c[pn[i]]] += 1
for i in range(1, classes):
cnt[i] += cnt[i - 1]
for i in range(n - 1, -1, -1):
p[cnt[c[pn[i]]] - 1] = pn[i]
cnt[c[pn[i]]] -= 1
cn[p[0]] = 0
classes = 1
for i in range(1, n):
cur = (c[p[i]], c[(p[i] + (1 << h)) % n])
prev = (c[p[i - 1]], c[(p[i - 1] + (1 << h)) % n])
if cur != prev:
classes += 1
cn[p[i]] = classes - 1
c = np.copy(cn)
h += 1
return p
s += '$'
suffix_array = sort_cyclic_shifts(s)
return suffix_array[1:]
# Ví dụ sử dụng
s = "banana"
optimized_suffix_array = build_suffix_array_optimized(s)
print("Mảng hậu tố tối ưu:", optimized_suffix_array)
Kết Luận
Việc xây dựng mảng hậu tố là một bài toán quan trọng trong lập trình, đặc biệt đối với các ứng dụng phân tích và tìm kiếm chuỗi. Bài viết đã giới thiệu cách cài đặt cơ bản của thuật toán cũng như một phương pháp tối ưu hơn để xử lý các chuỗi lớn. Hy vọng rằng thông qua các ví dụ và cài đặt chi tiết, bạn sẽ dễ dàng ứng dụng thuật toán này vào công việc của mình.
Comments