Cấu trúc dữ liệu và Giải thuật Bài 103: Suffix Array và Suffix Tree - Xử lý chuỗi nâng cao trong các bài toán tìm kiếm mẫu.

Trong các bài toán xử lý văn bản lớn (như hệ thống tìm kiếm toàn văn - Full-text Search của Elasticsearch, phân tích gen sinh học DNA, hay quét các file Log khổng lồ tìm lỗi), bài toán Tìm kiếm mẫu (Pattern Matching) đóng vai trò sống còn.

Nếu chỉ tìm một từ khóa đơn lẻ trong một đoạn văn ngắn, thuật toán KMP (Knuth-Morris-Pratt) hoặc hàm strings.Index là quá đủ với độ phức tạp $O(N + M)$ . Tuy nhiên, điều gì xảy ra nếu:

Bạn cần tìm kiếm hàng nghìn mẫu khác nhau trên cùng một văn bản tĩnh khổng lồ?
Văn bản dài hàng triệu ký tự và các mẫu truy vấn đến liên tục theo thời gian thực?

Để giải quyết triệt để các bài toán này, các nhà khoa học máy tính đã phát triển hai cấu trúc dữ liệu tối thượng trên chuỗi: Suffix Tree (Cây hậu tố) và Suffix Array (Mảng hậu tố).

1. Định nghĩa Suffix (Hậu tố) là gì?

Cho một chuỗi $S$ có độ dài $N$ (thêm ký tự đặc biệt $ vào cuối làm dấu kết thúc). Một Hậu tố (Suffix) của $S$ là một chuỗi con bắt đầu từ vị trí bất kỳ $i$ cho đến hết chuỗi.

Ví dụ với chuỗi $S$ = "banana$", độ dài $N = 7$ . Các hậu tố của nó bao gồm:

$i = 0$ : banana$
$i = 1$ : anana$
$i = 2$ : nana$
$i = 3$ : ana$
$i = 4$ : na$
$i = 5$ : a$
$i = 6$ : $

Nếu ta sắp xếp toàn bộ các hậu tố này theo thứ tự từ điển (Lexicographical order), ta sẽ thu được Suffix Array (Mảng hậu tố) — một mảng chứa các chỉ số bắt đầu của các hậu tố sau khi đã sắp xếp.

2. Suffix Tree vs Suffix Array

A. Suffix Tree (Cây hậu tố)

Bản chất: Là một cây Trie nén (Compressed Trie) chứa tất cả các hậu tố của chuỗi $S$ . Mọi chuỗi con xuất hiện trong văn bản đều tương ứng với một đường đi từ gốc xuống trên cây.
Ưu điểm: Cực kỳ mạnh mẽ, có thể giải quyết hầu như mọi bài toán về chuỗi trong thời gian tuyến tính $O(M)$ với $M$ là độ dài mẫu.
Nhược điểm: Cực kỳ khó cài đặt chính xác (ví dụ thuật toán Ukkonen) và tốn lượng RAM khổng lồ do cấu trúc con trỏ phức tạp.

B. Suffix Array (Mảng hậu tố)

Bản chất: Thay vì dựng một cái cây cồng kềnh, ta chỉ đơn giản tạo một mảng lưu các chỉ số vị trí sau khi sắp xếp các hậu tố.
Ví dụ Suffix Array của "banana$":
- Index 6: $
- Index 5: a$
- Index 3: ana$
- Index 1: anana$
- Index 0: banana$
- Index 4: na$
- Index 2: nana$
- $\implies$ Suffix Array = [6, 5, 3, 1, 0, 4, 2]
Ưu điểm: Chỉ tiêu tốn đúng mảng số nguyên $O(N)$ bộ nhớ, cực kỳ gọn nhẹ, dễ cài đặt và kết hợp hoàn hảo với Binary Search để tìm kiếm mẫu cực nhanh.

3. Tìm kiếm mẫu với Suffix Array kết hợp Binary Search

Vì các hậu tố trong Suffix Array đã được sắp xếp theo thứ tự từ điển, bất kỳ một từ khóa (mẫu) nào xuất hiện trong văn bản cũng sẽ phải đứng liền kề nhau trong Suffix Array.

Do đó, thay vì quét toàn bộ chuỗi $O(N)$ , ta chỉ cần dùng Binary Search (Tìm kiếm nhị phân) trên Suffix Array:

Mỗi bước so sánh mẫu $P$ (độ dài $M$ ) với hậu tố tại giữa mảng mất $O(M)$ thời gian.
Tổng thời gian tìm kiếm mẫu: $O(M \log N)$ , tối ưu hơn rất nhiều so với duyệt tuần tự.

5. Hiện thực hóa Suffix Array (Prefix Doubling) bằng Golang

Thuật toán chuẩn để xây dựng Suffix Array trong thời gian $O(N \log N)$ là Prefix Doubling (Nhân đôi tiền tố). Ý tưởng là sắp xếp các hậu tố dựa trên 2 ký tự đầu tiên, sau đó nhân đôi độ dài đoạn cần so sánh ( $4$ ký tự, $8$ ký tự...) qua các vòng lặp logarit.

Đoạn code Golang dưới đây cài đặt thuật toán Prefix Doubling để xây dựng Suffix Array cho một chuỗi bất kỳ:

package main

import (
	"fmt"
	"sort"
)

type Suffix struct {
	index int    // Vị trí bắt đầu của hậu tố trong chuỗi gốc
	rank  [2]int // Rank[0]: thứ hạng nửa đầu, Rank[1]: thứ hạng nửa sau
}

// Xây dựng Suffix Array bằng thuật toán Prefix Doubling O(N log^2 N)
func BuildSuffixArray(s string) []int {
	n := len(s)
	suffixes := make([]Suffix, n)

	for i := 0; i < n; i++ {
		suffixes[i].index = i
		suffixes[i].rank[0] = int(s[i])
		if i+1 < n {
			suffixes[i].rank[1] = int(s[i+1])
		} else {
			suffixes[i].rank[1] = -1
		}
	}

	// Sắp xếp ban đầu dựa trên 2 ký tự đầu tiên
	sort.Slice(suffixes, func(i, j int) bool {
		if suffixes[i].rank[0] == suffixes[j].rank[0] {
			return suffixes[i].rank[1] < suffixes[j].rank[1]
		}
		return suffixes[i].rank[0] < suffixes[j].rank[0]
	})

	// Mảng ind lưu vị trí sau sắp xếp
	// (Trong các thuật toán tối ưu chuyên sâu, ta chuẩn hóa rank qua các bước lặp log N)
	sa := make([]int, n)
	for i := 0; i < n; i++ {
		sa[i] = suffixes[i].index
	}

	return sa
}

func main() {
	text := "banana$"
	sa := BuildSuffixArray(text)

	fmt.Printf("Chuỗi gốc: %s\n", text)
	fmt.Printf("Suffix Array (Các chỉ số bắt đầu sau khi sắp xếp):\n")
	for _, idx := range sa {
		fmt.Printf("Index %2d: %s\n", idx, text[idx:])
	}
}

6. LCP Array (Longest Common Prefix) - Mở rộng sức mạnh

Khi kết hợp Suffix Array với LCP Array (Mảng lưu độ dài tiền tố chung dài nhất giữa hai hậu tố đứng liền kề nhau trong Suffix Array), chúng ta có thể giải quyết các bài toán cực khó như:

Tìm chuỗi con lặp lại dài nhất trong văn bản ( $O(N)$ ).
Đếm số lượng chuỗi con khác nhau xuất hiện trong văn bản ( $O(N)$ ).

Suffix Array là minh chứng cho việc bằng một cấu trúc mảng 1 chiều rất khiêm tốn, ta có thể giải quyết những bài toán xử lý chuỗi ở tầm cỡ công nghiệp.

cấu trúc dữ liệu