Cây hậu tố -- Suffix Tree

Trong bài trước ta đã tìm hiểu các thuật toán tìm kiếm xâu với thời gian $O(n+m)$ trong đó $n$ là độ dài của văn bản và $m$ là độ dài của xâu tìm kiếm. Mỗi thuật toán có đặc tính và ứng dụng riêng [2]: thuật toán Z là thuật toán tìm kiếm tuyến tính đơn giản nhất, thuật toán Boyer-Moore là thuật toán có thời gian sublinear trong thực tế, thuật toán Knuth-Morris-Pratt có ý nghĩa về mặt lịch sử cũng như ý tưởng của thuật toán và thuật toán này còn có thể được mở rộng ra trong trường hợp thời gian thực và tìm kiếm một tập nhiều mẫu, thuật toán Rabin-Karp được mở rộng và áp dụng trong phát hiện đạo văn.

Tuy nhiên, tất cả các thuật toán này đều rất khó mở rộng khi chúng ta muốn thực hiện các truy vấn (query) văn bản. Một số truy vấn thường gặp như:

Problem 1: Cho một văn bản $T[1,2,\ldots,n]$ và một xâu mẫu $P[1,2,\ldots,m]$ với các kí tự trong bảng chữ cái $\Sigma$, thực hiện các truy vấn sau:

  1. Xác định xem $P$ có phải là một xâu con của $T$ hay không?
  2. Xác định xem $P$ có phải là một hậu tố[1] (suffix) của $T$ hay không?
  3. Đếm sự xuất hiện của $P$ trong $T$?
  4. Tìm xâu con chung dài nhất của $T$ và $P$?
  5. Tìm xâu con dài nhất xuất hiện ít nhất 2 lần trong $T$?
  6. Tìm hậu tố xuất hiện đầu tiên theo thứ tự từ điển của $T$?

 
Ngoài hai truy vấn cuối cùng, các truy vấn còn lại có thể được thực hiện lặp đi lặp lại với các xâu mẫu $P$ khác nhau. Ta có thể tưởng tượng trong thực tế văn bản $T$ có kích thước lớn còn xâu mẫu $P$ có kích thước nhỏ. Do đó, một truy vấn có thể coi là hiệu quả nếu thời gian thực hiện truy vấn chỉ phụ thuộc vào độ dài của $P$, không phụ thuộc vào độ dài của $T$. Phương pháp đầu tiên chúng ta có thể nghĩ tới đó là tìm một cách biểu diễn $T$ sao cho việc thực hiện các truy vấn được thực hiện hiệu quả. Thời gian để biểu diễn $T$ sẽ được tính vào thời gian tiền xử lí. Thông thường, thời gian tiền xử lí là khá lớn.

Cây hậu tố (suffix tree), được đề xuất bởi Weiner [1] vào năm 1973, là một trong những cách biểu diễn có thể trả lời tất cả các truy vấn trên một cách hiệu quả. Điều đặc biệt là cây hậu tố có thể được xây dựng trong thời gian $O(n)$. Knuth, theo Wikipedia, đã gọi thuật toán xây dựng cây hậu tố của Winer là "giải thuật của năm 1973".

Cây hậu tố là gì?

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.

 
Ví dụ: $T[1,2,\ldots,6] = \mathrm{xabxac}$, hình dưới đây biểu diễn cây hậu tố $Ts$ với 6 nút lá.
suffix-ex
Một điều đặc biệt chú ý là không phải mọi xâu đều có cây hậu tố biểu diễn tương ứng. Ví dụ $T[1,2,3] = \mathrm{xcx}$ không có cây hậu tố biểu diễn nào thỏa mãn 5 tính chất ở trên (mình khuyến khích bạn đọc nên thử xây dựng). Lí do (sau khi bạn thử xây dựng bạn sẽ thấy) $T[1,2,3] = \mathrm{xcx}$ không có cây hậu tố tương ứng là vì hậu tố $x$ là tiền tố của hậu tố $\mathrm{xcx}$. Tổng quát hóa ta sẽ thấy:

Nhận xét: $T$ không có cây hậu tố biểu diễn nó khi và chỉ khi $T$ có một hậu tố là tiền tố của một hậu tố khác.

Do đó, để đảm bảo ta luôn có thể xây dựng được cây hậu tố cho mọi văn bản đầu vào, ta sẽ thêm kí tự $\, trường hợp của nhận xét trên không bao giờ xảy ra. Từ đoạn này trở đi của bài viết, ta luôn giả sử $T[n] = \ thì $\mathrm{pathlabel}(v)$ chính là hậu tố cần tìm.

Giả mã của các truy vấn này được cho ở phần phụ lục ở cuối bài. Dưới đây, chúng ta giới thiệu thuật toán đơn giản với thời gian $O(n^2)$ xây dựng cây hậu tố. Bài tiếp theo chúng ta sẽ làm quen với thuật toán $O(n)$.

Thuật toán $O(n^2)$

Ta lần lượt xây dựng cây hậu tố bằng cách chèn lần lượt các hậu tố $S_1,S_2,\ldots, S_n$, trong đó $S_i$ là hậu tố thứ $i$ của $T$, vào cây hậu tố hiện tại. Cây hậu tố $Ts_{1}$ chỉ có 1 nút lá (và một nút gốc) biểu diễn hậu tố $S_1$. Tại bước thứ $i$, thuật toán chèn hậu tố $S_i$ vào cây hậu tố hiện tại $Ts_{i-1}$. Để chèn hậu tố $S_i$ vào cây hậu tố hiện tại $Ts_{i-1}$, ta sẽ:

  1. Tìm một nút $v$ sao cho: (a) độ dài của tiền tố chung của $\mathrm{pathlabel}(v)$ và $S_i$ là lớn nhất và (b) $v$ gần gốc nhất . Thủ tục FindPath($T[1,2,\ldots,i],Ts$) dưới đây sẽ thực hiện thao tác này, trả lại 3 thông tin:
    1. Nút $v$.
    2. Vị trí cuối cùng của đoạn khớp của $P$, kí hiệu là $\mathrm{mlp}$ (là viết tắt của matched location of the pattern )
    3. Vị trí cuối cùng của đoạn khớp của $T$, kí hiệu là $\mathrm{mlt}$ (là viết tắt của matched location of the text)
  2. Có hai trường hợp: (I) Nếu $s < \mathrm{right}(\mathrm{edgelabel}(v))$ thì ta sẽ thêm vào một nút $x$ vào giữa cạnh nối $v$ và cha của nó tại vị trí kí tự ứng với $s$, thêm một nút lá $u$, gán $u$ là con của $x$ và gắn hậu tố $S_i$ với $u$. (II) Nếu $s = \mathrm{right}(\mathrm{edgelabel}(v))$ thì ta sẽ thêm một nút lá $u$ là con của $v$ và gắn hậu tố $S_i$ với $u$.

Ví dụ $T[1,2,\ldots,10] = \mathrm{xabxacxad\$}$ Cây hậu tối khi chèn $S_4$ và $S_7$ lần lượt tương ứng với trường hợp (I) và (II) sẽ như ở hình vẽ sau:
insert-suffix

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

NativeSuffixTree($T[1,2,\ldots, n]$):
   $Ts \leftarrow $ InitSuffixTree($T[1,2,\ldots,n]$)
    $r \leftarrow \mathrm{root}(Ts)$
    for $i \leftarrow 2$ to $n$
        $(v,\mathrm{mlp}, \mathrm{mlt})\leftarrow$ FindPath($T[i,i+1,\ldots,n],r$)
        $\ell v \leftarrow \mathrm{leftEL}(v)$
        $rv \leftarrow \mathrm{rightEL}(v)$
        if $\mathrm{mlt}$ < $rv$
            $\mathrm{leftEL}(v) \leftarrow \mathrm{mlt}+1$
            $x \leftarrow$ MakeNode($\ell v,\mathrm{mlt}$)
            ReplaceParent($v,x$)
        else
            $x \leftarrow v$
        $u \leftarrow$ MakeLeaf($\mathrm{mlt}+1,n,i$)
        $\mathrm{parent}(u) \leftarrow x$
        $Cr[x][T[\mathrm{mlp}+1]] \leftarrow u$

 

FindPath($P[1,2,\ldots,m], r$):
    $i \leftarrow 1$
    $c \leftarrow Cr[r][P[i]]$
    $j \leftarrow \mathrm{leftEL}(c)$
    $rc \leftarrow \mathrm{rightEL}(c)$
    if $c = $ Null or $ m = 0$
        return $(v,i-1,\mathrm{rightEL}(v))$
    while $T[i] = T[j]$
            $i \leftarrow i+1, j \leftarrow j+1$
    if $j > rc$
        return FindPath($P[i,i+1,\ldots,m], c$)
    else
        return $(c,i-1,j-1)$

 

ReplaceParent($v, x$):
    $pv \leftarrow \mathrm{parent}(v)$
    $\ell x \leftarrow \mathrm{leftEL}(x)$
    $\ell v \leftarrow \mathrm{leftEL}(v)$
    $Cr[pv][T[\ell x]] \leftarrow x$         [[set $x$ to be a child of $pv$]]
    $Cr[x][T[\ell v]] \leftarrow v$        [[set $v$ to be a child of $x$]]
    $\mathrm{parent}(v) \leftarrow x$
    $\mathrm{parent}(x) \leftarrow pv$

 

InitSuffixTree($T[1,2,\ldots,n]$):
    $u \leftarrow $ MakeLeaf($1,n,1$)
    $r \leftarrow $ MakeNode($0,0$)
    $Cr[r][T[1]] \leftarrow u$
    $\mathrm{parent}(u) \leftarrow r$
    return $r$

 

MakeNode($i, j$):
    $\mathrm{parent}(u) \leftarrow$ Null
    $Cr[u] \leftarrow $ Null
    $\mathrm{leftEL}(u) \leftarrow i$
    $\mathrm{rightEL}(u) \leftarrow j$
    return $u$

 

MakeLeaf($i,n, k$):
    $u \leftarrow$ MakeNode($i,n$)
    $\mathrm{nodelabel}(u) \leftarrow k$
    return $u$

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


#define ALPHABET_SIZE 27 // the size of the alphabet
char *T;
char Alphabet[ALPHABET_SIZE]= "abcdefghijklmnopqrstuvwxyz{";

typedef struct snode {
int leftEL;
int rightEL;
int node_label;
struct snode** Cr; // children pointers
struct snode *parent;
int leafcnt;  // the number of leaves of the subtree rooted at this node
int strdepth; // the string depth
} snode;

snode *native_suffix_tree(char *Txt){
T = Txt;
int n = strlen(T)-1;
snode *root = init_suffix_tree(n);
int i = 0;
int mlt = 0,mlp=0;
snode *v = NULL;
int rv,lv;
snode *x;
for(i = 2; i &lt;= n ;i++){
v = find_path(T,i,n,root, &amp;mlp, &amp;mlt);
lv = v-&gt;leftEL;
rv = v-&gt;rightEL;
if(mlt &lt; rv){
v-&gt;leftEL = mlt+1;
x = make_node(lv,mlt);
replace_parent(x,v);
} else {
x = v;
}
snode *u = make_leaf(mlp+1,n,i);
u-&gt;parent = x;
x-&gt;Cr[get_index(T[mlp+1])]  = u; // T[mlp+1] is the first character of the edge xu
}
return root;
}

snode *find_path(char *P, int first, int last, snode *r, int *mlp, int *mlt){
snode *c = r-&gt;Cr[get_index(P[first])];
if(c == NULL || first &gt; last){
*mlt = r-&gt;rightEL;
*mlp = first-1;
return r;
}
int i = first;
int j = c-&gt;leftEL;
int rc = c-&gt;rightEL;
while(P[i] == T[j] &amp;&amp; j &lt;= rc){
i++; j++;
}
if( j &gt; rc){
return find_path(P,i, last,c,mlp,mlt);
}
else {
*mlt = j-1;
*mlp = i-1;
return c;
}
}

void replace_parent(snode *x, snode *v){
snode *pv = v-&gt;parent;
int lx = x-&gt;leftEL;
int lv = v-&gt;leftEL;
pv-&gt;Cr[get_index(T[lx])] = x;
x-&gt;Cr[get_index(T[lv])] = v;
v-&gt;parent = x;
x-&gt;parent = pv;
}

snode *init_suffix_tree(int n){
snode *r = make_node(0,0);
snode *u = make_leaf(1,n,1);
r-&gt;Cr[get_index(T[1])] = u;
u-&gt;parent = r;
return r;
}

snode *make_node(int i, int j){
snode *u  = malloc(sizeof(snode));
u-&gt;leftEL = i;
u-&gt;rightEL = j;
u-&gt;node_label = 0;
u-&gt;Cr = malloc(ALPHABET_SIZE*sizeof(snode));
u-&gt;parent = NULL;
u-&gt;leafcnt = 0;
u-&gt;strdepth = 0;
memset(u-&gt;Cr, 0, sizeof(*u-&gt;Cr));
return u;
}

snode *make_leaf(int i,int n, int k){
snode *u = make_node(i,n);
u-&gt;node_label = k;
return u;
}

// Get the index of a character in the alphabet
int get_index(char c){
return c - 'a';
}

Phân tích thuật toán: Trước hết ta phân tích xem cây hậu tố ở trên có tối đa bao nhiêu nút. Dễ dàng thấy số nút lá của cây hậu tố là $n$, bằng kích thước của văn bản đầu vào, vì mỗi nút lá ứng với một hậu tố. Trong quá trình xây dựng cây hậu tố, một nút trong chỉ xuất hiện khi chèn thêm một hậu tố mới. Do đó, số nút trong của cây không thể vượt quá $n$ là số nút lá. Do đó, cây hậu tố có tối đa $2n$ nút.

Nếu biểu diễn con trỏ tới các nút con bằng mảng như thực hiện ở trên, thì cần $|\Sigma|$ con trỏ cho mỗi nút trong của cây. Do đó, mỗi nút chiếm bộ nhớ là $O(\Sigma)$ để biểu diễn và tổng bộ nhớ cần để biểu diễn cây là $O(n|\Sigma|)$. Tuy nhiên, nếu ta biểu diễn con trỏ tới các nút con là một danh sách, thì số lượng con trỏ của tất cả các nút trong không lớn hơn số cạnh của cây hậu tố. Vì cây hậu tố có tối đa $2n$ nút, nó sẽ có tối đa $2n-1$ cạnh và do đó số con trỏ đó không quá $2n-1$. Như vậy, bộ nhớ để biểu diễn cây trong trường hợp này là $O(n)$.

Về mặt thời gian, có thể thấy rằng thuật toán xây dựng cây hậu tố trong $n$ bước. Bước thứ $i$ tìm kiếm hậu tố $T[i,i+1,\ldots,n]$ trong cây hậu tố đang xây dựng hiện tại. Bước này sử dụng $n-i+1$ (là chiều dài của hậu tố $S_i$) phép so sánh để tìm kiếm. Do đó, tổng thời gian của thuật toán là $O(n+ n-1+\ldots + 1) = O(n^2)$.

Phụ lục các truy vấn

Truy vấn 1

IsSubstring($P[1,2,\ldots,m], Ts$):
    $r \leftarrow \mathrm{root}(Ts)$
    $(v,\mathrm{mlp},\mathrm{mlt}) \leftarrow$ FindPath($P[1,2,\ldots,m], r$)
    if $\mathrm{mlp} = m$
        return True
    else
        return False

 

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

int is_substring(char *P, snode *r){
int mlp = 0;
int mlt = 0;
int m = strlen(P)-1;
find_path(P, 1, m, r, &amp;mlp, &amp;mlt);
if( m == mlp){
return TRUE;
} else {
return FALSE;
}
}

Truy vấn 2

IsSuffix($P[1,2,\ldots,m], Ts$):
    $r \leftarrow \mathrm{root}(Ts)$
    $(v,\mathrm{mlp},\mathrm{mlt}) \leftarrow$ FindPath($P[1,2,\ldots,m], r$)
    if $\mathrm{nodelabel}(v) \not= $ Null and $\mathrm{mlt} = \mathrm{rightEL}(v)$
        return True
    else
        return False

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

int is_suffix(char *P, char *T){
snode *root = native_suffix_tree(T);
int mlp = 0;
int mlt = 0;
int m = strlen(P)-1;
snode *v = find_path(P, 1, m, root, &amp;mlp, &amp;mlt);
if( v-&gt;node_label != 0 &amp;&amp; v-&gt;rightEL == mlt){
return TRUE;
} else {
return FALSE;
}
}

Truy vấn 3

Như đã nhắc đến ở trên, để thực hiện truy vấn này, với mỗi nút $v$, chúng ta lưu thêm một trường $\mathrm{leafcnt}(v)$ lưu số lượng nút lá của cây con gốc $v$. Thông tin này có thể được cập nhật trong quá trình xây dựng cây mà không làm giảm thời gian tiệm cận xây dựng cây.

CountOccurence($P[1,2,\ldots,m],Ts$):
    $r \leftarrow\mathrm{root}(Ts)$
    $(v,\mathrm{mlp},\mathrm{mlt}) \leftarrow$ FindPath($P[1,2,\ldots,m], r$)
    if $\mathrm{mlp} \not= m$        [[$P$ is not a substring of $T$]]
        return 0
    else
        return $\mathrm{leafcnt}(v)$

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

int count_occurence(char *P, snode *r){
int mlp = 0;
int mlt = 0;
int m = strlen(P)-1;
snode *v = find_path(P, 1, m, r, &amp;mlp, &amp;mlt);
if(mlp &lt; m) return 0;
else return v-&gt;leafcnt;
}

Truy vấn 4

Để thực hiện truy vấn này, với mỗi nút $v$, chúng ta lưu thêm một trường $\mathrm{strdepth}(v)$ lưu string depth của nút $v$. Thông tin này có thể được cập nhật trong quá trình xây dựng cây mà không làm giảm thời gian tiệm cận xây dựng cây.

LongestRepeatedSubstring($Ts$):
    $r \leftarrow \mathrm{root}(Ts)$
    $\mathrm{dpn} \leftarrow $ FindNonleafDeepestNode($Ts$)
    $\mathrm{it} \leftarrow \mathrm{dpn}$
    $i \leftarrow 0$
    while $\mathrm{it} \not= r$
        $j \leftarrow \mathrm{leftEL}(\mathrm{it})$
        while $j \leq \mathrm{rightEL}(\mathrm{it})$
            $S[i] \leftarrow T[j]$
            $i \leftarrow i+1, j \leftarrow j+1$
        $\mathrm{it} \leftarrow \mathrm{parent}(\mathrm{it})$
    return Reverse($S$)

 

FindNonleafDeepestNode($Ts$):
    $r \leftarrow \mathrm{root}(Ts)$
    $j \leftarrow 0$
    $\mathrm{tmp} \leftarrow $ Null
    $\mathrm{dpn} \leftarrow r$
        for $i \leftarrow 1$ to AlphabetSize
            if $Cr[r][i] \not= $ Null and $\mathrm{nodelabel}(Cr[r][i]) \not= 0$
                $\mathrm{tmp} \leftarrow $ FindNonleafDeepestNode($Cr[r][i]$)
                if $\mathrm{strdepth}(\mathrm{tmp}) > \mathrm{strdepth}(\mathrm{dpn})$
                    $\mathrm{dpn} \leftarrow \mathrm{tmp}$
    return $\mathrm{dpn}$

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

char *longest_repeated_substr(snode *r){
snode * dpn = find_nonleaf_deepest_node(r);
char *S;
S = (char *)malloc(dpn-&gt;strdepth*sizeof(char));
int i = -1, j = 0;
snode *it = dpn;
while(it != r){
for(j = it-&gt;rightEL; j &gt;= it-&gt;leftEL; j--){
S[++i] = T[j];
}
it = it-&gt;parent;
}
return strrev(S);
}

snode *find_nonleaf_deepest_node(snode *r){
int i = 0;
snode *dpn, *tmp;
int j = 0;
dpn = r;
for(i = 0; i &lt; ALPHABET_SIZE; i++){
if(r-&gt;Cr[i] != NULL &amp;&amp; r-&gt;Cr[i]-&gt;node_label == 0){
tmp = find_nonleaf_deepest_node(r-&gt;Cr[i]);
if(tmp-&gt;strdepth &gt; j){
j = tmp-&gt;strdepth;
dpn = tmp;
}
}
}
return dpn;
}

Truy vấn 5

PrintSmallestLexSuffix($Ts$):
    $r \leftarrow \mathrm{root}(Ts)$
    if $\mathrm{leftEL}(r) = 0$ or $Cr[r][\$] \not=$ Null
        $i \leftarrow 0$
        while $i$ < AlphabetSize and $Cr[r][i] = $ Null
            $i \leftarrow i+1$
        if $i \not= $ AlphabetSize
            print $T[\mathrm{leftEL}(Cr[r][i]), \ldots, \mathrm{rightEL}(Cr[r][i])]$
            PrintSmallestLexSuffix($Cr[r][i]$):

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

void print_smallest_lex_suffix(snode *r){
int i = 0, j, jj = 0;
if(r-&gt;leftEL == 0 || r-&gt;Cr[get_index('{')] == NULL){
while(i &lt; ALPHABET_SIZE &amp;&amp; r-&gt;Cr[i] == NULL)i++;
if(i != ALPHABET_SIZE){
j = r-&gt;Cr[i]-&gt;leftEL;
jj = r-&gt;Cr[i]-&gt;rightEL;
for(; j &lt;= jj; j++){
printf("%c", T[j]);
}
print_smallest_lex_suffix(r-&gt;Cr[i]);
}
}
}

Code: suffixtree-and-queries.

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] Gusfield, Dan. Algorithms on strings, trees and sequences: computer science and computational biology, Chapter 5,6. Cambridge university press, 1997.
[3] Carl Kingsford. Suffix Tree Lecture Note. CMSC 423, CMU.

Footnotes

[1] Hậu tố của một xâu $T[1,2,\ldots,n]$ là một xâu con của $T$ có dạng $T[i,i+1,\ldots,n]$ với $i$ là một số nào đó thỏa mãn $1 \leq i \leq n$. Ví dụ $T = \mathrm{ABCDAB}$ thì $\mathrm{DAB}$ là một hậu tố của $T$. Chú ý $T$ là hậu tố của chính nó.

[2] Một hậu tố của $T$ được gọi là một hậu tố riêng (proper suffix) nếu hậu tố đó khác $T$.

Facebook Comments

Tags: , ,

Reply

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