Cấu trúc dữ liệu và Giải thuật Bài 73: Mảng hậu tố (Suffix Array) và Mảng LCP - Tối ưu hóa bộ nhớ cho tìm kiếm chuỗi con.

Ở Bài 72, Cây Hậu Tố (Suffix Tree) đã chứng minh sức mạnh tuyệt đối khi tìm kiếm chuỗi con trong thời gian $O(M)$. Tuy nhiên, trong thực tế vận hành các hệ thống cơ sở dữ liệu hoặc máy chủ tìm kiếm, Suffix Tree hiếm khi được triển khai trực tiếp.

Nguyên nhân đến từ bộ nhớ (RAM). Một Suffix Tree cần tạo ra hàng triệu đối tượng Node, kèm theo vô số con trỏ (pointers) trỏ chéo nhau. Sự phân mảnh bộ nhớ này không chỉ ngốn RAM gấp 10-20 lần dung lượng văn bản gốc, mà còn gây ra hiện tượng Cache Miss liên tục trên CPU.

Để giữ lại tốc độ tìm kiếm thần tốc nhưng dọn dẹp hoàn toàn mớ bòng bong con trỏ, ngành Khoa học máy tính đã "phẳng hóa" Suffix Tree thành hai mảng số nguyên đơn giản, xếp liền kề nhau trên RAM: Mảng Hậu Tố (Suffix Array - SA) và Mảng Tiền Tố Chung Dài Nhất (LCP Array).

1. Mảng Hậu Tố (Suffix Array) là gì?

Thay vì vẽ ra một cái cây, Suffix Array đơn giản là một mảng lưu trữ chỉ số (index) bắt đầu của tất cả các hậu tố trong văn bản, sau khi chúng đã được sắp xếp theo thứ tự từ điển (Lexicographical order).

Xét văn bản $T = \text{"banana\$"}$:

1. Trích xuất tất cả hậu tố:

   • 0: banana$

   • 1: anana$

   • 2: nana$

   • 3: ana$

   • 4: na$

   • 5: a$

   • 6: $

2. Sắp xếp chúng theo thứ tự từ điển (A-Z):

   • 6: $

   • 5: a$

   • 3: ana$

   • 1: anana$

   • 0: banana$

   • 4: na$

   • 2: nana$

3. Trích xuất các chỉ số gốc để tạo thành Suffix Array:

   SA = [6, 5, 3, 1, 0, 4, 2]

Sức mạnh của Suffix Array: Tìm kiếm nhị phân

Vì các hậu tố đã được sắp xếp theo thứ tự từ điển, nếu bạn muốn tìm chuỗi con "ana", bạn chỉ cần thực hiện Tìm kiếm nhị phân (Binary Search) trực tiếp trên Suffix Array. Thời gian tìm kiếm là $O(M \log N)$ (với $M$ là độ dài chuỗi cần tìm, $N$ là độ dài văn bản gốc). Mặc dù chậm hơn một chút xíu so với $O(M)$ của Suffix Tree, nhưng nó tiết kiệm được một lượng RAM khổng lồ và chạy cực kỳ mượt mà trên L1/L2 Cache của CPU.

2. Mảng LCP (Longest Common Prefix): Linh hồn thứ hai

Suffix Array giải quyết xuất sắc bài toán "Tìm chuỗi con". Tuy nhiên, nếu đề bài yêu cầu: "Hãy tìm chuỗi con lặp lại dài nhất trong văn bản" (Longest Repeated Substring), chỉ dùng Suffix Array là không đủ. Chúng ta cần biết các hậu tố lân cận giống nhau đến mức nào.

Đó là lúc Mảng LCP xuất hiện.

LCP Array là một mảng số nguyên có cùng kích thước với SA, trong đó LCP[i] lưu trữ độ dài tiền tố chung dài nhất giữa hậu tố thứ $i$ và hậu tố ngay trước nó (thứ $i-1$) trong danh sách đã sắp xếp.

Tiếp tục với ví dụ "banana$":

• SA[1] = a$ và SA[2] = ana$ $\rightarrow$ Chung "a" (độ dài 1) $\rightarrow$ LCP[2] = 1

• SA[2] = ana$ và SA[3] = anana$ $\rightarrow$ Chung "ana" (độ dài 3) $\rightarrow$ LCP[3] = 3

Nhờ mảng LCP, bài toán "Chuỗi con lặp lại dài nhất" trở nên cực kỳ đơn giản: Bạn chỉ cần duyệt qua mảng LCP một vòng, tìm giá trị lớn nhất. Ở ví dụ trên, giá trị lớn nhất là $3$ (chuỗi "ana").

3. Triển khai Suffix Array và Thuật toán Kasai (LCP) bằng Golang

Thuật toán ngây thơ để xây dựng SA tốn $O(N^2 \log N)$. Trong thực tế production, ta dùng thuật toán Prefix Doubling ($O(N \log^2 N)$) hoặc DC3 ($O(N)$). Với LCP, ta dùng thuật toán Kasai đạt tốc độ $O(N)$.

Dưới đây là mã nguồn Golang cốt lõi, sử dụng hàm sort có sẵn (để mã nguồn trong sáng) kết hợp thuật toán Kasai sinh mảng LCP chuẩn mực:

Go

package main

import (
	"fmt"
	"sort"
	"strings"
)

// Xây dựng Suffix Array (Sử dụng sort.Slice cho mục đích giáo dục)
func buildSuffixArray(text string) []int {
	n := len(text)
	sa := make([]int, n)
	for i := 0; i < n; i++ {
		sa[i] = i
	}

	// Sắp xếp các chỉ số hậu tố dựa trên so sánh chuỗi
	sort.Slice(sa, func(i, j int) bool {
		return text[sa[i]:] < text[sa[j]:]
	})
	return sa
}

// Thuật toán Kasai: Xây dựng mảng LCP trong O(N)
func buildLCPArray(text string, sa []int) []int {
	n := len(sa)
	lcp := make([]int, n)
	
	// rank[i] lưu vị trí của hậu tố bắt đầu tại i trong Suffix Array
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		rank[sa[i]] = i
	}

	h := 0 // h là độ dài tiền tố chung
	for i := 0; i < n; i++ {
		if rank[i] > 0 {
			// Lấy chỉ số của hậu tố đứng ngay trước hậu tố i trong Suffix Array
			j := sa[rank[i]-1]

			// Mở rộng độ dài tiền tố chung (h)
			for i+h < n && j+h < n && text[i+h] == text[j+h] {
				h++
			}
			
			lcp[rank[i]] = h
			if h > 0 {
				h-- // Bước nhảy tối ưu của Kasai: Hậu tố tiếp theo sẽ có tiền tố chung ít nhất là h-1
			}
		}
	}
	return lcp
}

// Tìm kiếm nhị phân chuỗi pattern trên Suffix Array O(M log N)
func searchSubString(text, pattern string, sa []int) []int {
	n := len(text)
	m := len(pattern)
	
	// Tìm cận dưới
	left := sort.Search(len(sa), func(i int) bool {
		suffix := text[sa[i]:]
		if len(suffix) > m {
			suffix = suffix[:m]
		}
		return suffix >= pattern
	})

	// Tìm cận trên
	right := sort.Search(len(sa), func(i int) bool {
		suffix := text[sa[i]:]
		if len(suffix) > m {
			suffix = suffix[:m]
		}
		return suffix > pattern
	})

	// Trả về danh sách các chỉ mục xuất hiện pattern
	return sa[left:right]
}

func main() {
	text := "banana$"
	sa := buildSuffixArray(text)
	lcp := buildLCPArray(text, sa)

	fmt.Printf("Suffix Array: %v\n", sa)
	fmt.Printf("LCP Array: %v\n", lcp)

	pattern := "ana"
	matches := searchSubString(text, pattern, sa)
	fmt.Printf("Chuỗi '%s' xuất hiện tại các vị trí: %v\n", pattern, matches)
}

4. Phân tích Hiệu năng (Big-O)

• Thời gian Xây dựng (Build Time): $O(N \log N)$ cho việc sinh Suffix Array (nếu dùng các thuật toán chuyên sâu như Manber-Myers) và $O(N)$ tuyệt đối cho LCP Array nhờ thuật toán Kasai.

• Thời gian Truy vấn (Query Time): $O(M \log N)$ để tìm một chuỗi có độ dài $M$.

• Không gian (Space Complexity): $O(N)$ cho hai mảng số nguyên phẳng. Với văn bản 1GB, Suffix Tree sẽ ngốn khoảng 15GB RAM, trong khi Suffix Array và LCP kết hợp lại chỉ tốn khoảng 8GB (và thậm chí có thể nén thấp hơn nữa), dễ dàng tải toàn bộ vào RAM server hiện hành.

5. Ứng dụng Thực tế trong Hệ thống Enterprise

Việc "phẳng hóa" cấu trúc cây thành mảng tuyến tính giúp Suffix Array trở thành nền tảng cho hàng loạt hệ thống truy xuất siêu lớn:

• Bộ máy Tìm kiếm (Search Engines - Elasticsearch / Lucene): Lập chỉ mục các chuỗi văn bản không theo từ (như tiếng Nhật, tiếng Trung không có dấu cách) để tìm kiếm các cụm ký tự chéo siêu tốc mà không cần phân rã từ vựng (Tokenization).

• Thuật toán Nén Dữ Liệu (BWT - Burrows-Wheeler Transform): Suffix Array là cốt lõi để thực hiện phép biến đổi BWT — công nghệ nén thần thánh đứng sau các định dạng nén như .bz2 và các công cụ nén mã gen.

• Tin sinh học: Alignment (gióng) chuỗi gen cực lớn. Thay vì tốn RAM để dựng Suffix Tree cho bộ gen người (3.2 tỷ ký tự), Suffix Array với kỹ thuật nén cho phép phân tích gen mượt mà trên các máy trạm bình thường.

Chuỗi thuật toán xử lý văn bản đã khép lại với những cơ chế lưu trữ tối ưu nhất. Khi các bài toán không chỉ dừng ở việc tìm kiếm chuỗi, mà yêu cầu xử lý các truy vấn động phức tạp trên cây (như tìm kiếm khoảng cấu trúc cây đồ thị), chúng ta sẽ bước sang một kỹ thuật bẻ gãy không gian cây: Heavy-Light Decomposition.