Nhưng đã giới thiệu ở bài trước, cây hậu tố là một cấu trúc dữ liệu rất mạnh để thực hiện nhiều truy vấn văn bản với thời gian . Tuy nhiên, điểm yếu chính của cây hậu tố là bộ nhớ lớn do mỗi nút của cây phải lưu nhiều thông tin, mặc dù về mặt lý thuyết là . Nếu thực thi cây hậu tố tốt thì mỗi kí tự cũng phải mất trung bình bộ nhớ 20 bytes. Như vậy nếu ta có 1GB text thì cần 20GB bộ nhớ cho cây hậu tố.

Mảng hậu tố (suffix array) được giới thiệu bởi Manber và Mayer [1] năm 1993 như là một thay thế cho cây hậu tố. Điểm mạnh của mảng hậu tố là tiết kiệm được nhiều bộ nhớ. Ngoài ra, nếu kết hợp mảng hậu tố với một vài mảng thông tin khác như mảng tiền tố chung lớn nhất (mảng LCP - Longest Common Prefix) thì có thể thực hiện hậu hết các truy vấn như cây hậu tố với cùng thời gian [5]. Do những lợi ích đó mà mảng hậu tố được rất nhiều nhà nghiên cứu quan tâm và rất nhiều giải thuật được phát triển để xây dựng cây hậu tố. Trong [4], các tác giả phân loại hàng chục thuật toán cũng như các phân tích thời gian và bộ nhớ. Mình đính kèm phân loại đó ở phần phụ lục.

Mảng hậu tố là gì?

Cho văn bản với các kí tự trong bảng chữ cái . Ta quy ước $ là kí tự nhỏ nhất thuộc bảng chữ cái và chỉ xuất hiện duy nhất một lần trong . Văn bản có hậu tố trong đó hậu tố thứ là . Ta tập hợp các hậu tố thành một mảng . Để sử dụng mảng này thực hiện các truy vấn, thông thường ta muốn mảng này được sắp xếp theo thứ tự từ điển . Do đó, ta sẽ gán nếu hậu tố (gọi là hậu tố thứ ) có vị trí thứ trong mảng hậu tố đã sắp xếp. Mảng gọi là mảng hậu tố.

Ví dụ: , mảng hậu tố của như sau:

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	15	12	2	8	5	13	3	9	6	14	11	1	7	4	10

 
Theo bảng trên, có nghĩa là hậu tố thứ (là ) đứng thứ 2 trong mảng các hậu tố đã sắp xếp theo thứ tự từ điển. Do $ là kí tự nhỏ nhất trong theo thứ tự từ điển, ta luôn có .

Đi kèm với mảng hậu tố là mảng tiền tố chung dài nhất, gọi tắt là mảng LCP. Mảng LCP, kí hiệu là , là mảng trong đó là chiều dài của tiền tố chung dài nhất của hai hậu tố và . Giá trị không xác định và quy ước là . Với ví dụ trên vì chiều dài tiền tố chung dài nhất của hậu tố (là ) và (là ) là .

Xây dựng mảng hậu tố

Thuật toán đơn giản nhất ta có thể nghĩ tới để xây dựng mảng hậu tố là liệt kê tất cả các hậu tố và sau đó sắp xếp các hậu tố theo thứ tự từ điển. Có tất cả hậu tố của xâu , do đó, sắp xếp các hậu tố có thể thực hiện trong phép so sánh (ví dụ QuickSort). Do so sánh hai hậu tố có thể thực hiện trong thời gian , ta có thể xây dựng mảng hậu tố trong thời gian .

Nếu bằng cách nào đó, chúng ta chỉ mất thời gian cho mỗi phép so sánh hai hậu tố, chúng ta sẽ thu được thuật toán . Phần này mình giới thiệu hai thuật toán khác nhau thực hiện ý tưởng so sánh đó.

Giải thuật dựa trên Rabin-Karp Fingerprint

Phương pháp này được trình bày trong lecture note [2]. Trước khi đọc tiếp, mình khuyến khích bạn đọc xem lại bài tìm kiếm xâu với thuật toán Rabin-Karp. Ý tưởng chính của thuật toán Rabin-Karp là biến mỗi xâu con thành một số nguyên không quá lớn (ví dụ 64 bit) sử dụng phép băm và việc so sánh hai xâu con được quy về so sánh hai số nguyên với thời gian .

Giả sử (bằng cách nào đó mà ta sẽ mô tả sau) chúng ta có thể kiểm tra xem hai xâu con của văn bản có bằng nhau hay không trong thời gian . Để so sánh hai hậu tố và của , ta sẽ sử dụng tìm kiếm nhị phân trong thời gian để tìm số sao cho:

và

Khi đã tìm được , ta chỉ cần so sánh và . Do đó, phép so sánh hai hậu tố được thực hiện trong .

Để phép kiểm tra hai xâu con có bằng nhau hay không trong thời gian , ta sẽ thực hiện tiền xử lí. Ta sẽ sử dụng hàm băm trong đó là một số nguyên tố được chọn ngẫu nhiên trong khoảng . Ta chọn ngẫu nhiên để đảm bảo, về mặt lý thuyết, xác suất đụng độ nhỏ (xem lại phân tích trong bài thuật toán Rabin-Karp). Trong thực tế ta chỉ cần chọn một số nguyên tố lớn. Ví dụ trong [2], tác giả chọn . Gọi là cơ số, thường chọn là số kí tự trong bảng chữ cái. Gọi là mảng trong đó . Định nghĩa mảng như sau (quy ước ):

Mảng và có thể tính được trong thời gian sử dụng phương pháp Horner.

Ta chuyển mỗi xâu con của thành một số nguyên (giá trị hash) có dạng:

Dễ thấy:

Do đó, giá trị với bất kì có thể tính được trong thời gian nếu biết và . Từ đó suy ra ta có thể kiểm tra xem hai xâu con có bằng nhau hay không trong thời gian bằng cách so sánh hai giá trị hash. Giả mã như sau:

 

 

 
Code của giả mã bằng C. Code đầy đủ được đính ở cuối bài.

#define min(x, y) (((x) < (y)) ? (x) : (y))
typedef unsigned long long int LLU;

char *T;   // the text
int n = 0; // the length of the text

int *A;  // the suffix array 
LLU *B, *PP; 
LLU b = (LLU)100; // the base assuming English text only
LLU p = (LLU) 1000000007;

int * rk_suffix_array(char *Txt){
	T = Txt;
	n = strlen(T)-1;// assuming the character array is indexed from 1 
	B = (LLU *)malloc((n+1)*sizeof(LLU));
	PP = (LLU *)malloc((n+1)*sizeof(LLU));
	A = (int *)malloc((n+1)*sizeof(int));
	memset(A, 0, (n+1)*sizeof(int));
	B[0] = 0;B[1] = (LLU)get_index(T[1]);
	PP[0] = 1; PP[1] = b; A[1] = 1;
	int i = 0;
	for(i = 2; i <= n; i++){
		B[i] = (B[i-1]*b+ (LLU)get_index(T[i])) %p;
		PP[i] = (PP[i-1]*b)%p;
		A[i] = i;
	}
	qsort(A, n+1, sizeof(int), rk_compare);
	return A;
}

int rk_compare(const void *a, const void *b){
	int *i = (int *)a;
	int *j = (int *)b;
	int h = min(n - *i + 1, n - *j+1);
	int l = 0, m = 0;
	while(l <= h){
		m = (l+h)/2;
		if(hashcode(*i,*i+m) == hashcode(*j,*j+m)){
			l = m+1;
		}else {
			h = m -1;
		}
	}
	return get_index(T[*i+l]) - get_index(T[*j+l]);
}
LLU hashcode(int i, int j){
	return (B[j] + p - (B[i-1]*PP[j-i+1])%p)%p;
}
// Get the index of a character in the alphabet
int get_index(char c){
	return c - '/';
}

Với hai hậu tố cho trước, sửa đổi thủ tục RKCompare một chút, ta có thể tính được chiều dài tiền tố chung lớn nhất trong thời gian . Do đó, ta có thể xây dựng mảng LCP trong thời gian . Chi tiết coi như bài tập cho bạn đọc. Tổng kết lại ta có:

 

Thuật toán nhân đôi tiền tố

Thuật toán nhân đôi tiền tố (prefix doubling) được đề xuất bởi Uber và Mayer [1] có thời gian sử dụng thuật toán đếm phân phối. Trong phần này mình trình bày một biến thể [2] sử dụng Quick Sort.

Trước hết coi văn bản đầu vào có chiều dài vô hạn bằng cách thêm vào cuối văn bản vô hạn kí tự $. Gọi văn bản vô hạn là . Chú ý là $ là kí tự nhỏ hơn ( theo thứ tự từ điển) tất cả các kí tự khác trong bảng chữ cái và chỉ xuất hiện trong văn bản đúng một lần tại vị trí cuối cùng. Do vô hạn, với mỗi số ta có đúng xâu con của chiều dài , mỗi xâu bắt đầu bằng một kí tự của . Thuật toán thực hiện theo bước như sau:

1. Sắp xếp xâu con của độ dài theo thứ tự từ điển.
2. Sắp xếp xâu con của độ dài theo thứ tự từ điển.
3. Sắp xếp xâu con của độ dài theo thứ tự từ điển.
5. Sắp xếp xâu con của độ dài theo thứ tự từ điển.
7. Sắp xếp xâu con của độ dài theo thứ tự từ điển.

Ta có nhận xét sau:

Nhận xét: Thứ tự của các xâu con thu được sau bước cuối cùng chính là thứ tự đã sắp xếp của các hậu tố bắt đầu bằng kí tự đầu tiên của các xâu con đó.

Nhận xét đó là do các kí tự $ là kí tự nhỏ nhất theo thứ tự từ điển. Chi tiết chứng minh của nhận xét đó coi như bài tập cho bạn đọc. Ta sẽ chứng minh rằng nếu sử dụng Quick Sort để sắp xếp thì mỗi bước của thuật toán có thể được thực thi trong thời gian .

 
Chứng minh: Bước đầu tiên ta có thể thực hiện trong thời gian sử dụng Quick Sort. Tại bước thứ , ta sẽ sắp xếp các xâu con có độ dài sử dụng Quick Sort. Để ý rằng tại bước , ta đã có thứ tự tương đối giữa các xâu con độ dài . Nếu coi xâu con độ dài là ghép của hai xâu con độ dài , xâu con độ dài thứ nhất gọi là khóa trái và xâu con độ dài thứ hai gọi là khóa phải, thì ta chỉ việc so sánh hai khóa cua hai xâu độ dài thay vì so sánh trực tiếp. Do đó, việc so sánh có thể thực hiện trong thời gian thay vì . Như vậy ta sẽ có thuật toán .

Tuy nhiên, đó vẫn chưa phải là tất cả chúng ta cần. Ta cần thêm một cách mã hóa để mã hóa vị trí tương đối giữa các xâu con. Do mỗi bước ta có đúng xâu con, ta gán cho mỗi xâu con một số trong tập để khi so sánh hai xâu, ta chỉ cần so sánh hai số tương ứng. Chú ý là hai xâu giống nhau ta phải gán cho hai số giống nhau. Ta có thể làm như sau:

Tại bước , sau khi sắp xếp, mỗi xâu độ dài sẽ được gán cho một số là vị trí của nó trong mảng đã sắp xếp. Ta sẽ thực hiện duyệt qua mảng để một lần để gán lại, đảm bảo hai xâu con giống nhau được gán cho cùng một số. Bước duyệt này chỉ mất .

Như vậy, ta có thể thực hiện mỗi bước trong thời gian

---

Trước khi trình bày giả mã của thuật toán, mình sẽ nói qua đôi chút về tổ chức dữ liệu (theo [2]). Với mỗi xâu con độ dài , ta sẽ lưu 3 giá trị:

1. Vị trí của kí tự đầu tiên của xâu con. Giá trị này sẽ được biểu diễn bởi .
2. Mã của khóa trái của xâu con. Giá trị này sẽ được biểu diễn bởi .
3. Mã của khóa phải của xâu con. Giá trị này sẽ được biểu diễn bởi .

Ta cũng sử dụng mảng hai chiều trong đó hàng lưu mã của xâu con bắt đầu từ độ dài như mô tả trong chứng minh của Lemma 1.

Giả mã như sau:

 
Code của giả mã bằng C. Code đầy đủ được đính kèm ở cuối bài:

typedef unsigned long long int LLU;
char *T; // the text

int n = 0; // the length of the tex

typedef struct data{
	int lkey, rkey;
	int index;
}data;

data *S; // each data element for a substring of T
int **M;
int *A; // the suffix array

int *pd_suffix_array(char *Txt){
	T = Txt;
	n = strlen(T)-1; // assuming the first character is empty
	S = (data *)malloc((n+1)*sizeof(data));
	M = (int **)malloc(32*sizeof(int *)); // 2^31-1 is the maximum length of the text
	A = (int *)malloc((n+1)*sizeof(int));
	memset(A, 0, (n+1)*sizeof(int)); // set everything to 0
	int k = 0, i = 0;
	for(k = 0; k < 32; k++){
		M[k] = (int *)malloc((n+1)*sizeof(int));
	}
	S[0].lkey = 0; S[0].rkey = 0; S[0].index = 0;

	for(i = 1; i <= n; i++) {
		S[i].index = i;
		S[i].lkey = T[i] - '`'; // the index of T[i] in the alphabet
		S[i].rkey = S[i].lkey;
	}

	int ell = 1;
	k = -1;
	while(ell < n){
		k++;
		ell = 1 << k; // ell = 2^k
		qsort(S, n+1, sizeof(data), lex_compare);
		for(i = 1; i <=n; i++){ // assigning code for each substring
			M[k][S[i].index] = lex_compare(&S[i], &S[i-1]) == 0? M[k][S[i-1].index] : i;
		}
		for(i = 1; i <=n; i++){
			S[i].lkey = M[k][S[i].index];  // update the left key for the next iteration
			S[i].rkey = (S[i].index + ell) <= n ? M[k][S[i].index + ell] : 0; // update the right key for the next iteration
		}
	}
	for(i = 1; i <= n ;i++){
		A[i] = S[i].index; // the suffix array
	}
	return A;
}

/* Compare two suffixes based on the lexical order of 2-tuple (lkey, rkey) where
 * lkey is the left key and rkey is the right key
 * return 1 if u > v, 0 if u = v and -1 if u < v
 */
int lex_compare(const void *u, const void *v){
	data *a = (data *)u;
	data *b = (data *)v;
	return (a->lkey == b->lkey) ? (a->rkey == b->rkey ? 0 : (a->rkey > b->rkey ? 1 : -1)) : ((a->lkey > b->lkey) ? 1: -1);
}

Dựa vào mảng , ta có thể tính được chiều dài cuả tiền tố chung dài nhất của hai hậu tố trong thời gian bằng cách chia nhị phân. Do đó, mảng LCP có thể tính được trong thời gian . Giả mã như sau:

 
Code của giả mã bằng C:

/* Compute the length of the longest common prefix of two suffixes starting from x and y, respectively. */
int pd_lcp(int x, int y) {
	if( x == y){
		return n-x+1;
	}
	int k = 1;
	for(k =1; (1<<k) < n; k++){} // k = [log_2 n]
	int s = 0;
	while(k >= 0){
		if(M[k][x] == M[k][y]){
			x += (1 << k);
			y+= (1 << k);
			s+= (1 << k);
		}
		k--;
	}
	return s;
}

 

Remarks:

1. Nếu để ý kĩ ta sẽ thấy và là các số trong tập . Do đó, ta có thể thay Quick Sort bằng Bucket Sort trong thủ tục PDSuffixArray. Do Bucket Sort có thời gian , ta sẽ thu được thuật toán . Đây chính là thuật toán gốc của Menber và Myers.
2. Trong thuật toán xây dựng mảng hậu tố PDSuffixArray, giá trị của hàng thứ của mảng không phụ thuộc vào các hàng trước đó. Do đó, ta có chỉ sử dụng mảng 1 chiều thay vì 2 chiều. Tuy nhiên lúc đó ta sẽ không thể tính mảng LCP như ở trên được. Thay vào đó, ta có thể sử dụng thuật toán của Kasai, Lee, Arimura, Arikawa và Park [6] tính mảng LCP trong thời gian .

Mình khuyến khích bạn đọc code và submit bài tại SPOJ. Cả hai thuật toán trên sẽ được khoảng 60 điểm. Code submit mình đính kèm dưới đây.

Code đầy đủ của giả mã: rk_suffix, pd_suffix, rk_submitted, pd_submit.

Tham khảo
[1] Manber, Udi, and Myers, Gene. Suffix arrays: a new method for on-line string searches. Siam Journal on Computing 22.5 (1993): 935-948.
[2] Daniel Sleator. Suffix Array and Suffix Tree Lecture Note. CMU, Fall 2012.
[3] Vladu, Adrian, and Cosmin Negruşeri. Suffix arrays–a programming contest approach. (2005).
[4] Puglisi, Simon J., William F. Smyth, and Andrew H. Turpin. A taxonomy of suffix array construction algorithms. ACM Computing Surveys (CSUR) 39.2 (2007): 4.
[5] Abouelhoda, Mohamed Ibrahim, Stefan Kurtz, and Enno Ohlebusch. Replacing suffix trees with enhanced suffix arrays. Journal of Discrete Algorithms 2.1 (2004): 53-86.
[6] Kasai, Toru, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Combinatorial pattern matching, pp. 181-192. Springer Berlin Heidelberg, 2001.

Phụ lục

Phân loại các thuật toán xây dựng mảng hậu tố [4]: