Thuật toán McCreight xây dựng cây hậu tố -- McCreight Algorithm

Trong bài trước, chúng ta đã làm quen với cây hậu tố (suffix tree) và thuật toán đơn giản xây dựng cây hậu tố trong thời gian O(n^2). Mình khuyến khích bạn đọc xem lại các khái niệm của bài trước. Một số khái niệm mình sẽ không nhắc lại ở đây. Trong bài này chúng ta sẽ làm quen với thuật toán McCreight xây dựng cây hậu tố trong thời gian O(n) giả sử bảng chữ cái có kích thước |\Sigma| = O(1). Thuật toán McCreight được đề xuất vào năm 1976 bởi McCreight đơn giản hóa thuật toán O(n) trước đó đề xuất bởi Weiner. Ngoài thuật toán McCreight, thuật toán Ukkonen xây dựng cây hậu tố cũng có thời gian O(n) và có thể được áp dụng trong trường hợp online, có nghĩa là chúng ta có thể cập nhật lại cây hậu tố khi có thêm các kí tự mới. Tuy nhiên, so với thuật toán Ukkonen, thuật toán McCreight đơn giản hơn. Chúng ta sẽ làm quen với thuật toán Ukkonen trong bài sau.

Mình nhắc lại khái niệm cây hậu tố ở đây:

Definition (Suffix Tree): Cây hậu tố, kí hiệu là Ts, của một văn bản T[1,2,\ldots,n] là một cây biểu diễn T với các tính chất sau:

  1. Tsn nút lá được đánh số 1,2,\ldots,n, mỗi lá tương ứng với một hậu tố của T.
  2. Mỗi nút trong (internal node) có ít nhất 2 nút con.
  3. Mỗi cạnh của cây được gán cho một nhãn là một xâu con của T.
  4. Ghép (concatenation) nhãn của các cạnh trên đương đi từ gốc của Ts tới lá thứ i là hậu tố bắt đầu từ i (T[i,i+1,\ldots,n]) của T.
  5. Nhãn của các cạnh cùng một nút cha tới các nút con bắt đầu từ các kí tự khác nhau.

 

Ý tưởng của thuật toán McCreight có thể được coi là cải tiến của thuật toán đơn giản sử dụng liên kết hậu tố (suffix link). Mỗi nút trong của cây hậu tố xây dựng trong thuật toán MacCreight ngoài các trường cơ bản \mathrm{edgelabel}, \mathrm{nodelabel}, \mathrm{parent}, \mathrm{children} như đã mô tả ở bài trước còn có thêm một trường là liên kết hậu tố (định nghĩa dưới đây), kí hiệu là \mathrm{slink}.

Goi v là một nút trong với \mathrm{pathlabel}(v) = \mathrm{c\alpha} trong đó c là kí tự đầu tiên trong \mathrm{pathlabel}(v)\alpha là một xâu (\alpha có thể là một xâu rỗng).

  1. Nếu \alpha = \emptyset, liên kết hậu tố của v sẽ là liên kết trỏ vào nút gốc của cây hậu tố Ts, i.e, \mathrm{slink}(v) = \mathrm{root}(Ts).
  2. Nếu \alpha \not= \emptyset thì liên kết hậu tố của v sẽ trỏ vào một nút trong u của Ts thỏa mãn \mathrm{pathlabel}(u) = \alpha, i.e, \mathrm{slink}(v) = u.

Hai trường hợp ở trên được minh họa ở hình dưới đây. Đường màu đỏ có mũi tên biểu diễn liên kết hậu tố:
suffix-link-ill
Ví dụ xâu T = \mathrm{xabxacxabxxabx\$} có cây hậu tố và các liên kết hậu tố như hình sau:
suffix-link
Nếu coi nút gốc có liên kết hậu tố trỏ tới chính nó thì nhìn vào hình trên, ta sẽ thấy mọi nút trong đều có đúng 1 liên kết hậu tố. Tính chất này không dễ thấy nếu chúng ta chỉ nhìn vào định nghĩa của liên kết hậu tố.

Theorem 1: Với mỗi nút trong v của cây hậu tố Ts, luôn tồn tại duy nhât một nút trong u mà liên kết hậu tố của v trỏ tới.

 
Chứng minh: Dựa vào định nghĩa của cây hậu tố và liên kết hậu tố, nếu một nút trong v có liên kết hậu tố tới một nút u, nút u đó phải là duy nhất. Do đó, chúng ta chỉ cần chứng minh tồn tại nút u như vậy.

Nút trong v được tại thành là do khi chèn hậu tố S_i, với một số i nào đó thỏa mãn 1 \leq i \leq n, \mathrm{c\alpha} là tiền tố của S_i và là xâu con chung lớn nhất (gọi tắt là tiền tố con chung lớn nhất) của S_i với cây hậu tố Ts_{i-1}. Thêm nữa, c\alpha phải là tiền tố của một hậu tố S_j nào đó với j \leq i. Xét S_{i+1}, rõ ràng \alpha là một tiền tố con chung S_{i+1} với cây hậu tố sau khi đã chèn S_{i}. Giả sử nút u với \mathrm{pathlabel}(u) = \mathrm{\alpha} chưa tồn tại khi nút v được thêm vào cây hậu tố. Do c\alpha là tiền tố con chung lớn nhất của S_i với cây hậu tố hiện tại, \alpha sẽ là tiền tố con chung lớn nhất của S_{i+1} với cây hậu tố Ts_{i}. Do đó, nút u sẽ được tạo ra khi chièn S_{i+1}, từ đó suy ra dpcm.


Như vậy, Theorem 1 cho ta biết với mọi cây hậu tố, mỗi nút trong luôn có đúng một liên kết hậu tố tới một nút trong khác. Chứng minh trên cũng cho ta nhận xét sau:

Nhận xét: Nếu một nút trong v được tạo ra khi chèn hậu tố S_{i}, liên kết hậu tố của v có thể được cập nhật ngay tại bước sau đó.

Tại sao liên kết hậu tố lại hữu dụng? Về mặt trực quan, nếu ta chèn hậu tố S_i có tiền tố con chung lớn nhất với cây hiện tại là c\alpha thì tiền tố chung lớn nhất của S_{i+1}Ts_{i} ít nhất có chiều dài |\alpha|. Do đó, khi chèn S_{i+1}, ta chỉ cần đi theo liên kết hậu tố để tiết kiệm được |\alpha| phép so sánh kí tự so với thuật toán đơn giản.

Thuật toán O(n)

Thuật toán thực hiện trong n bước, bước thứ i+1 chèn hậu tố S_{i+1} vào cây hiện tại Ts_{i}. Việc chèn hậu tố S_{i+1} phụ thuộc vào bước trước. Khi chúng ta chèn S_{i}:

  1. Nếu cây Ts_{i-1} có một nút trong v sao cho \mathrm{pathlabel}(v) ( \mathrm{pathlabel}(v) = c\alpha) là tiền tố con chung lớn nhất của S_{i} với Ts_{i-1}, ta chỉ việc đi theo liên kết hậu tố của v để chèn S_{i+1} như đã chỉ ra ở trên.
  2. Nếu nút v như trên không tồn tại, tương tự như thuật toán đơn giản, ta sẽ tìm một nút v sao cho tiền tố con chung lớn nhấtcủa S_iTs_{i-1} là tiền tố của \mathrm{pathlabel}(v) và ta bẻ cạnh giữa v và cha của nó để chèn thêm nút x, tạo một nút lá là con của x và gán S_{i} là con của nút lá đó. Nút x lúc này chưa có liên kết hậu tố. Ta sẽ đi theo liên kết hậu tố của \mathrm{parent}(x) để chèn S_{i+1}. Ở đây, ta cũng biết trước độ dài đoạn khớp ít nhất là độ dài của nhãn của cạnh (x,\mathrm{parent}(x)), kí hiệu là L, do đó ta có thể "nhảy cóc" một số nút khi so sánh S_{i+1} với Ts_{i}.

Để minh họa cho hai trường hợp trên, ta sẽ xét hai ví dụ được minh họa bởi hình dưới đây. Ví dụ thứ nhất (hình (1) của hình dưới đây), ta xây dựng cây hậu tố cho xâu T =  \mathrm{xabxacxabxxabx\$}. Khi chèn hậu tố S_{11} vào cây hậu tố Ts_{10}, ta sẽ tìm thấy một nút v đã có liên kết hậu tố (như ở hình vẽ) và chèn nút lá tương ứng với hậu tố thứ 11 vào cây Ts_{10}. Khi chèn S_{12}, ta đi theo liên kết hậu tố của v đến nút uu, gọi là nút cuối của liên kết hậu tố, và bắt đầu tìm so sánh S_{12} với cây con gốc tại uu. Trong trường hợp của ví dụ trong hình, ta chỉ việc tạo thêm một nút lá là con của uu và gán hậu tố S_{12} là con của nút uu.

Ví dụ thứ hai, khi ta chèn hậu tố S_{i} = \mathrm{axbxacxf\$} vào cây hậu tố Ts_{i-1}, ta sẽ tìm được một nút v (như trong hình) và bẻ cạnh giữa v và nút cha pv của nó để thêm một nút x. Sau đó tạo một nút lá là con của x và gán S_{i} vào nút lá đó. Tiếp theo đó, ta chèn S_{i+1} = \mathrm{xbxacxf\$}. Lúc này nút x chưa có liên kết hậu tố, ta sẽ đi theo liên kết hậu tố của pv để đến một nút uu (như trong hình vẽ) và tìm kiếm S_{i+1} bắt đầu từ cây con gốc uu. Tuy nhiên, ta đã biết trước đoạn khớp sẽ ít nhấtL = 3 do nhãn của cạnh (x,pv) có chiều dài 3. Do đó, ta có thể nhảy cóc 2 nút như mũi tên trong hình vẽ để chèn S_{i+1}. Cuối cùng, ta sẽ cập nhật liên kết hậu tố của x.

insert-1

Trong giả mã dưới đây, vv lưu giữ nút cần cập nhật liên kết hậu tố. Biến uu lưu giữ nút cuối của liên kết hậu tố ở bước trước. Do đó, tại dòng (*) của giả mã dưới đây, ta luôn tìm kiếm bắt đầu từ nút uu thay vì từ gốc. Biến L lưu giữ độ dài ít nhất của đoạn khớp khi tìm kiếm S_{i+1}. Độ dài này ta tính được trong bước thứ i khi chèn S_i. Quy luật cập nhật L đã được chỉ ra ở trên.

Thủ tục FastFindPath(P[i,2,\ldots,m], L, \mathrm{root}) sẽ tìm kiếm đoạn khớp của P[i,2,\ldots,m] với cây con gốc tại \mathrm{root} của cây hậu tố hiện tại khi biết trước độ dài đoạn khớp ít nhất là L. Thủ tục này trả lại nút v sao cho tiền tố chung lớn nhất là xâu con của \mathrm{pathlabel}(v), độ dài vị trí khớp cuả P[i,2,\ldots,m] và vị trí khớp của văn bản. Xem thêm tại bài trước với hàm tương tự FindPath(P[1,2,\ldots,m], Ts). Điểm khác biệt chính với thủ tục FindPath(P[1,2,\ldots,m], Ts) ở bài trước là ta kết hợp cập nhật liên kết hậu tố trong quá trình tìm kiếm.

Giả mã của thuật toán như sau:

McCreightSuffixTree(T[1,2,\ldots, n]):
   Ts \leftarrow InitSuffixTree(T[1,2,\ldots,n])
    r \leftarrow \mathrm{root}(Ts)
    uu  \leftarrow r, vv \leftarrow Null
    L \leftarrow 0
    for i \leftarrow 2 to n
        dp \leftarrow \mathrm{strdepth}(uu)
        (v,\mathrm{mlp}, \mathrm{mlt}) \leftarrow FastFindPath(T[i+dp, \ldots,n], L, uu)         [[(*)]]
        if \mathrm{mlt} < \mathrm{rightEL}(v)
            x \leftarrow MakeNode(\mathrm{leftEL}(v), \mathrm{mlt})
            \mathrm{leftEL}(v) \leftarrow \mathrm{mlt} + 1
            \mathrm{strdepth}(x) \leftarrow \mathrm{strdepth}(v) + \mathrm{mlt}- \mathrm{leftEL}(v)+1
            x \leftarrow ReplaceParent(v, x)
            if vv \not= Null
                \mathrm{slink}(vv) \leftarrow x
            vv \leftarrow x
            \mathrm{elgx} \leftarrow \mathrm{rightEL}(x)-\mathrm{leftEL}(x)+1
            L \leftarrow \mathrm{elgx}  - [\mathrm{parent}(x) = root]
        else
            x \leftarrow v
            L \leftarrow 0
        u \leftarrow MakeLeaf(\mathrm{mlt}+1,n,i)
        \mathrm{parent}(u) \leftarrow x
        Cr[x][T[\mathrm{mlp}+1]] \leftarrow u

 

FastFindPath(P[k,2,\ldots,m], L, \mathrm{root}):
    u \leftarrow Cr[r][P[k]]
    if L = 0 and vv \not= Null
        \mathrm{slink}(vv) \leftarrow \mathrm{root}
        vv \leftarrow Null
    if u = Null
        uu \leftarrow \mathrm{slink}(\mathrm{root})
        return (\mathrm{root}, k-1,\mathrm{rightEL}(\mathrm{root}))
    else
        \mathrm{elg} \leftarrow \mathrm{rightEL}(\mathrm{root}) - \mathrm{leftEL}(\mathrm{root})+1         [[\mathrm{elg} is the edge length]]
        if L \geq \mathrm{elg}                      [[(**)]]
            return FastFindPath(P[k + \mathrm{elg},\ldots,m], L-\mathrm{elg}, u)
        else
            i \leftarrow L+1
            j \leftarrow \mathrm{leftEL}(u) + L
            while P[i] = T[j] and j \leq \mathrm{rightEL}(u)         [[(***)]]
                i \leftarrow i+1, j \leftarrow j+1
        if j  data-recalc-dims= \mathrm{rightEL}(u)" />
            return FastFindPath(P[k + \mathrm{elg},\ldots,m], 0, u)
        else
            \mathrm{uu} \leftarrow \mathrm{slink}(\mathrm{root})
            return (u,i-1,j-1)

 

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

char *T;
snode *uu,*vv;
int L = 0;

snode *mccreight_suffix_tree(char *Txt){
		T = Txt;
		int n = strlen(T)-1;
		snode *root = init_suffix_tree(n);
		uu = root; vv = NULL;
		int i = 0;
		int mlt = 0,mlp=0, mlgp = 0;
		snode *v = NULL;
		int dp;
		snode *x, *u;
		int L = 0;
		for (i = 2; i <= n; i++){
			dp = uu->strdepth;
			v = fast_find_path(T, i + dp, n, L, uu, &mlp, &mlt);
			if(mlt < v->rightEL){
				x = make_node(v->leftEL, mlt);
				snode *pv = v->parent;
				x->strdepth = pv->strdepth + mlt - v->leftEL + 1;
				v->leftEL = mlt + 1;
				replace_parent(x,v);
				if(vv != NULL)	vv->slink = x;
				vv = x;
                                L = (x->rightEL - x->leftEL+ 1)  - ((pv == root )?1:0); // the lenght of the matched of the next suffix
			
			} else {
				x = v;
				L = 0;
			}
			u = make_leaf(mlp + 1, n, i);
			u->parent = x;
			x->Cr[get_index(T[mlp+1])] = u;
		}
		return root;

}

snode *fast_find_path(char *P, int first, int last, int L, snode *root, int *mlp, int *mlt){
	snode *u = root->Cr[get_index(P[first])];
	if( L == 0 && vv != NULL){
		vv->slink = root;
		vv = NULL;
	}
	if( u == NULL){
		if( L == 0){
			uu = root->slink;
		} else {
			printf("invalid parameter setup! %d\n", L);
			exit(0);
		}
		*mlp = first-1;
		*mlt = root->rightEL;
		return root;
	}else {
		int elg = u->rightEL - u->leftEL + 1;
		if(L >=  elg){
			return fast_find_path(P, first + elg, last, L - elg, u, mlp, mlt);
		}else {
			int i = first + L;
			int j = u->leftEL + L;
			while(P[i] == T[j] && j <= u->rightEL){
				i++;j++;
			}
			if(j > u->rightEL){
				return fast_find_path(P, first + elg, last, 0, u, mlp, mlt);
			} else {
				uu = root->slink;
				*mlp = i-1;
				*mlt = j -1;
				return u;
			}
		}
	}
}

Hàm [\mathrm{parent}(x) = root] trả lại 1 nếu \mathrm{parent}(x) = root và 0 nếu ngược lại. Các thủ tục khác của giả mã không trình bày ở đây tương tự như trong bài trước.

Phân tích thuật toán: Việc phân tích thuật toán trên có thể được tách thành hai thành phần sau: tổng số phép so sánh kí tự (vòng while ở dòng (***)) và số lần "nhảy cóc" ( lệnh if ở dòng (**)). Do phép nhảy cóc, mỗi kí tự của văn bản được so sánh đúng 1 lần. Do đó tổng số phép so sánh kí tự là n. Phần khó nhất là phân tích số lần "nhảy cóc".

Với mỗi nút v của cây hậu tố, gọi \mathrm{treedepth}(v) là số nút trong đường đi từ gốc tới v của cây hậu tố trừ đi 1. Ta có nhận xét sau:

Nhận xét: Nếu nút v có một liên kết hậu tố tới nút u thì:

\mathrm{treedepth}(u) \geq \mathrm{treedepth}(v)-1

Do đó, nếu ta nhảy cóc k lần tại bước i+1, nút uu lại có \mathrm{treedepth}(uu) tăng lên k-1 so với tree depth của nó tại bước thứ i. Do \mathrm{treedepth}(v) \leq n với mọi v, tổng số lần nhảy cóc là không quá 3n. Do đó ta có:

Theorem 1: Thuật toán McCreight xây dựng cây hậu tố trong thời gian O(n), giả sử bảng chữ cái có kích thước O(1).

 

Code: Mcreight-Suffix-Tree

Tham khảo

[1] Weiner, Peter. Linear pattern matching algorithms. Switching and Automata Theory, 1973. SWAT'08. IEEE Conference Record of 14th Annual Symposium on. IEEE, 1973.
[2] McCreight, Edward M. A space-economical suffix tree construction algorithm. Journal of the ACM (JACM) 23.2 (1976): 262-272.
[3] Ukkonen, Esko. On-line construction of suffix trees.. Algorithmica 14.3 (1995): 249-260.
[4] Aluru, Srinivas. Suffix Trees and Suffix Arrays. Handbook of Data Structures and Applications (2004).

Tags: , , , ,

  1. Lê Văn Hạnh’s avatar

    Đã không viết thì thôi, viết thì viết cho đàng hoàng chứ.

    Reply

    1. Hung Le’s avatar

      Hi bạn,
      Xin lỗi vì bạn có những trải nghiệm không hay với blog. Nếu bạn có comment cụ thể phần nào bạn cảm thấy chưa hài lòng thì xin để lại. Mình sẽ sửa cho bài viết chuẩn hơn!

      Hùng

      Reply

Reply

Your email address will not be published. Required fields are marked *