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. $Ts$ có $n$ 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)$ 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}$ và $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_i$ và $Ts_{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ất là $L = 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 > \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 &lt;= n; i++){
dp = uu-&gt;strdepth;
v = fast_find_path(T, i + dp, n, L, uu, &amp;mlp, &amp;mlt);
if(mlt &lt; v-&gt;rightEL){
x = make_node(v-&gt;leftEL, mlt);
snode *pv = v-&gt;parent;
x-&gt;strdepth = pv-&gt;strdepth + mlt - v-&gt;leftEL + 1;
v-&gt;leftEL = mlt + 1;
replace_parent(x,v);
if(vv != NULL)	vv-&gt;slink = x;
vv = x;
L = (x-&gt;rightEL - x-&gt;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-&gt;parent = x;
x-&gt;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-&gt;Cr[get_index(P[first])];
if( L == 0 &amp;&amp; vv != NULL){
vv-&gt;slink = root;
vv = NULL;
}
if( u == NULL){
if( L == 0){
uu = root-&gt;slink;
} else {
printf("invalid parameter setup! %d\n", L);
exit(0);
}
*mlp = first-1;
*mlt = root-&gt;rightEL;
return root;
}else {
int elg = u-&gt;rightEL - u-&gt;leftEL + 1;
if(L &gt;=  elg){
return fast_find_path(P, first + elg, last, L - elg, u, mlp, mlt);
}else {
int i = first + L;
int j = u-&gt;leftEL + L;
while(P[i] == T[j] &amp;&amp; j &lt;= u-&gt;rightEL){
i++;j++;
}
if(j &gt; u-&gt;rightEL){
return fast_find_path(P, first + elg, last, 0, u, mlp, mlt);
} else {
uu = root-&gt;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).

Facebook Comments

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 *