Bài tập lớn Thiết kế và Phân tích Thuật toán
Đề số 8: Bài toán tìm xâu con chung dài nhất
Sinh viên : Lê Ngọc Minh
Lớp : Khoa học máy tính
Khoá : 52
SHSV : 20071946
Hà Nội, tháng 11/2010
Mục lục
Chương 1. Giới thiệu 3
Chương 2. Cây hậu tố 4
2.1. Khái niệm 4
2.2. Biểu diễn cây hậu tố trong máy tính 5
2.3. Giải thuật dựng cây hậu tố Ukkonen 6
2.3.1. Cây hậu tố ngầm định (implicit suffix tree) 6
2.3.2. Dựng cây hậu tố ngầm định 7
2.3.3. Liên kết hậu tố (suffix link) 9
2.3.4. Tăng tốc thuật toán sử dụng liên kết hậu tố 9
2.3.5. Thuật toán dựng cây hậu tố ngầm định trong thời gian tuyến tính 12
2.3.6. Dựng cây hậu tố thực sự 13
Chương 3. Cây hậu tố tổng quát 14
3.1. Khái niệm 14
3.2. Biểu diễn cây hậu tố tổng quát trong máy tính 14
3.3. Dựng cây hậu tố tổng quát trong thời gian tuyến tính 15
Chương 4. Bài toán tìm xâu con chung dài nhất 16
4.1. Khái niệm 16
4.2. Tìm xâu con chung dài nhất của hai xâu 16
4.3. Tìm xâu con chung dài nhất của nhiều hơn hai xâu 16
4.3.1. Tính số C(v) 17
Chương 5. Chương trình thử nghiệm 18
5.1. Kết quả thử nghiệm 18
5.2. Hướng dẫn cài đặt chương trình 19

đường đi theo thứ tự.
• Nhãn đường đi của một nút là nhãn của đường đi bắt đầu từ gốc đến nút đó
• Độ sâu chuỗi của một nút là độ dài nhãn đường đi của nút đó
• Độ sâu nút (node-depth) của một nút là số nút trên đường đi từ gốc đến nút đó
• Nhãn của một đường đi kết thúc ở giữa cạnh (u, v) chia nhãn của (u, v) tại một điểm được định
nghĩa là nhãn của u ghép với các kí tự trong nhãn của (u, v) từ đầu đến điểm chia.
Hình 1: Cây hậu tố của chuỗi xabxac
Ví dụ trong Hình 1, nhãn của w là xa, nhãn của u là a và xâu xabx là nhãn của đường đi từ gốc đến
giữa cạnh (w, 1).
2.2. Biểu diễn cây hậu tố trong máy tính
Theo cách đơn giản nhất, mỗi cạnh của cây được gán nhãn đúng bằng một xâu con của S. Do tổng
chiều dài tất cả các xâu con vào cỡ O(m
2
) nên giới hạn dưới cho thời gian tính của thuật toán dựng cây
cũng là O(m
2
).
Để giảm kích thước bộ nhớ và đạt được thời gian tính nhỏ hơn, ta biểu diễn cạnh của cây bằng chỉ
số đầu và chỉ số cuối của nó trong xâu S. Như vậy mỗi cạnh chỉ cần hai số để gán nhãn và số cạnh tối
đa là 2m-1 nên bộ nhớ yêu cầu là O(m).
Hình 2: Cây bên trái là một phần của cây hậu tố cho chuỗi S=abcdefabcuvw với nhãn của cạnh được
viết tường minh. Cây bên phải biểu diễn nhãn sử dụng hai chỉ số. Lưu ý rằng cạnh có nhãn 2,3 cũng có
thể được gán nhãn 8,9
Để cho đơn giản, các hình vẽ và diễn giải sau đây vẫn coi như nhãn của cạnh là cả xâu con của
chuỗi.
2.3. Giải thuật dựng cây hậu tố Ukkonen
Báo cáo này sẽ tiếp cận giải thuật Ukkonen theo cách trước hết trình bày một giải thuật đơn giản,
dễ hiểu nhưng kém hiệu quả sau đó sẽ tăng tốc dần bằng các quan sát bổ sung và các mẹo cài đặt.
2.3.1. Cây hậu tố ngầm định (implicit suffix tree)
Định nghĩa: Cây hậu tố ngầm định của xâu S là cây nhận được từ cây hậu tố của S sau các bước

i+1
nh ng có ít nh t m t đ ng đi n i ti p ư ấ ộ ườ ố ế β:
tr ng h p này ta c n thêm m t c nh có nhãn là Sườ ợ ầ ộ ạ
i+1
, nếu β k t thúc gi a m t c nh thì m tế ở ữ ộ ạ ộ
nút m i cũng c n đ c t o.ớ ầ ượ ạ
3. N u ế có đ ng ườ đi n i ti pố ế β b t đ u b ng ắ ầ ằ S
i+1
: không làm gì và chuy n sang b c ti p theo.ế ướ ế
T i b c m r ng i+1 c a pha i+1, ạ ướ ở ộ ủ β là xâu r ng, thu t toán đ n gi n thêm kí t Sỗ ậ ơ ả ự
i+1
bên d i nútướ
g c (tr khi nó đã đó).ố ừ ở
Xét ví d trong ụ Hình 5 và Hình 6, b n h u t đ u tiên k t thúc nút lá nh ng h u t cu i cùng chố ậ ố ầ ế ở ư ậ ố ố ỉ
g m kí t x k t thúc bên trong m t c nh. Khi thêm kí t th sáu b, b n h u t đ u tiên đ c m r ngồ ự ế ộ ạ ự ứ ố ậ ố ầ ượ ở ộ
b ng lu t 1, h u t th năm s d ng lu t 2 và v i h u t th 6 là lu t 3.ằ ậ ậ ố ứ ử ụ ậ ớ ậ ố ứ ậ
Hình 5: Cây hậu tố ngầm định cho xâu axabx trước khi kí tự thứ 6, b, được thêm
Hình 6: Cây hậu tố ngầm định sau khi thêm kí tự b
D th y r ng ta có th tìm đi m k t thúc c a m i h u t trong i+1 h u t c a xâu S[1 i] b ng cáchễ ấ ằ ể ể ế ủ ỗ ậ ố ậ ố ủ ằ
duy t cây t g c v i chi phí th i gian là O(|ệ ừ ố ớ ờ β|). Sau khi đã tìm đ c đi m k t thúc c a h u t , thao tácượ ể ế ủ ậ ố
m r ng ch c n th i gian h ng s .ở ộ ỉ ầ ờ ằ ố
V i cách làm này, s phép toán c b n c n th c hi n là ớ ố ơ ả ầ ự ệ , do đó đ ph cộ ứ
t p tính toán vào kho ng O(nạ ả
3
). Rõ ràng thu t toán này không th c t vì có nh ng cách làm đ n gi nậ ự ế ữ ơ ả
h n đ tìm xâu con chung dài nh t trong th i gian O(nơ ể ấ ờ
2
) trong tr ng h p t i nh t. Chúng ta s xem xétườ ợ ồ ấ ẽ
cách c i ti n gi i thu t trong các ph n sau.ả ế ả ậ ầ
2.3.3. Liên k t h u t (suffix link)ế ậ ố

• Giả sử định lí đúng với cây I
i
, ta cần chứng minh nó vẫn đúng với cây I
i+1
.
• Theo bổ đề trên, nếu một nút trong v được tạo ra trong bước mở rộng j, nút s(v) của nó sẽ được
tạo ra hoặc tìm thấy trong bước mở rộng j+1. Bước mở rộng cuối cùng thêm xâu chỉ gồm kí tự
S
i+1
nên không tạo ra nút trong mới nào.
Vậy, hệ quả được chứng minh. Ta thấy khi xây dựng xong cây I
i+1
, mọi nút trong của nó đều có
liên kết hậu tố, ta có hệ quả tiếp theo.
Hệ quả: Với mọi cây hậu tố ngầm định I
i
, nếu một nút trong có nhãn xα thì có một nút khác của
cây I
i
có nhãn α.
Dựa vào liên kết hậu tố, ta có thể tăng tốc thuật toán để đạt được độ phức tạp tính toán thực tế hơn.
2.3.4. Tăng tốc thuật toán sử dụng liên kết hậu tố
Trong giải thuật đầu tiên, tại pha i+1, bước mở rộng j ta cần tìm đường đi β có nhãn S[j i] mất
thời gian O(|β|). Liên kết hậu tố có thể được sử dụng để giảm độ phức tạp của bước này xuống hằng số.
Đường đi có nhãn S[1 i] chắc chắn phải kết thúc ở lá vì nó là đường đi dài nhất trong cây I
i
. Khi
xây dựng cây I
i
ta lưu lại nút lá tương ứng với toàn bộ xâu đang xét S[1 i]. Bước bổ sung đầu tiên của

α
. Tuy nhiên, độ sâu nút của
v có thể lớn hơn, bằng hoặc nhỏ hơn độ sâu nút của s(v) một đơn vị. Ví dụ, nút có nhãn xab có độ
sâu hai, nút có nhãn ab có độ sâu một; nút có nhãn xabcdefg có độ sâu bốn, nút có nhãn abcdefg
có độ sâu năm.
Bổ đề: Mỗi pha của giải thuật Ukkonen có thể được thực hiện trong thời gian O(m).
CHỨNG MINH: Trừ bước mở rộng đầu tiên thực hiện được trong thời gian hằng số, các bước mở
rộng tiếp theo bao gồm việc đi ngược lên từ nút hiện tại không qua một nút, theo liên kết hậu tố đến nút
mới và đi xuống một số nút để tìm ra vị trí kết thúc của đường đi. Ta có thể tính được giới hạn trên của
tổng số thao tác đi xuống bằng nhận xét sau: độ sâu tối đa của cây hậu tố là m. Thật vậy, mỗi cạnh của
cây là một xâu con khác rỗng và đường đi từ gốc đến lá bất kì biểu diễn một hậu tố của cây nên tổng số
cạnh tối đa trên đường đi từ gốc đến một nút lá bất kì bằng m hay độ sâu tối đa của mọi nút là m. Mỗi
pha gồm có i+1 ≤ m b c m r ng, tr b c đ u tiên không c n di chuy n nên s b c đi lên t i đaướ ở ộ ừ ướ ầ ầ ể ố ướ ố
c a m t pha là m. C ng v i m i l n đi theo liên k t h u t đ sâu nút gi m t i đa là m t nên t ng s l nủ ộ ộ ớ ỗ ầ ế ậ ố ộ ả ố ộ ổ ố ầ
gi m đ sâu nút là 2m. Đ sâu c a nút hi n t i không th quá m nên t ng c ng s b c đi xu ng trongả ộ ộ ủ ệ ạ ể ổ ộ ố ướ ố
c pha không quá 3m. V y th i gian tính toán c a m i pha là O(m).ả ậ ờ ủ ỗ
T ng c ng có m pha nên ta có ngay b đ ti p theo:ổ ộ ổ ề ế
B đổ ề: Thu t toán Ukkonen có th đ c th c hi n trong th i gian O(mậ ể ượ ự ệ ờ
2
).
Đ n đây hi u qu c a thu t toán đã đ c c i thi n đáng k tuy nhiên ta v n có th gi m đ ph cế ệ ả ủ ậ ượ ả ệ ể ẫ ể ả ộ ứ
t p tính toán xu ng th i gian h ng s b ng m t vài nh n xét nh .ạ ố ờ ằ ố ằ ộ ậ ỏ
2.3.5. Thu t toán d ng cây h u t ng m đ nh trong th i gian tuy n tínhậ ự ậ ố ầ ị ờ ế
Nh n xét 1ậ : Lu t m r ng s 3 k t thúc m i pha.ậ ở ộ ố ế ỗ
CH NGỨ MINH: N u lu t s 3 đ c áp d ng nghĩa là đ ng đi có nhãn S[j i] ch c ch n đ c n i ti pế ậ ố ượ ụ ườ ắ ắ ượ ố ế
b ng kí t Sằ ự
i+1
nên t t c các đ ng đi có nhãn S[k i] v i k > j cũng v y và lu t th 3 ti p t c đ c ápấ ả ườ ớ ậ ậ ứ ế ụ ượ
d ng cho các b c m r ng còn l i c a pha.ụ ướ ở ộ ạ ủ
G i j* là ch s c a b c m r ng đ u tiên lu t s 3 đ c áp d ng. Theo nh n xét trên ta khôngọ ỉ ố ủ ướ ở ộ ầ ậ ố ượ ụ ậ

đến j
*
. Do bước mở rộng cuối cùng luật 1 hoặc 2 được áp dụng chính là một bước trước khi luật 3
lần đầu tiên được áp dụng nên ta có j
i
= j
*
-1. Như vậy số bước mở rộng được thực hiện có thể tính theo
công thức: . Vậy thời gian thực hiện của thuật toán là
O(m).
Hình 9: Hình ảnh quá trình thực hiện của thuật toán. Mỗi dòng là một giai đoạn trong thuật toán, mỗi
số là một bước mở rộng tường minh được thực hiện.
2.3.6. Dựng cây hậu tố thực sự
Cây hậu tố ngầm định cuối cùng I
m
có thể được chuyển thành cây hậu tố thực sự trong thời gian
O(m). Ta chỉ việc thêm kí tự $ vào cuối xâu S và thực hiện thuật toán, kết quả là một cây hậu tố ngầm
định của một chuỗi mà không có hậu tố nào là tiền tố của hậu tố khác, đồng thời cũng là cây hậu tố
thực sự của xâu.
Tóm lại ta có:
Định lí: Giải thuật Ukkonen dựng cây hậu tố của xâu m kí tự S trong thời gian O(m).
Chương 3. Cây hậu tố tổng quát
3.1. Khái niệm
Trong các phần trên ta đã từng bước xây dựng cây hậu tố cho một chuỗi. Để giải quyết bài toán
xâu con chung lớn nhất của hai hay nhiều chuỗi ta cần mở rộng khái niệm cây hậu tố để chứa nhiều
chuỗi hơn trong một cấu trúc dữ liệu chung.
Định nghĩa: Cho tập các chuỗi {S
1
, S
2

2
, S
3
, S
K
trước tiên ta tìm tiền
tố dài nhất S
k
[1 i] đã tồn tại trong cây. Ta thực hiện các giai đoạn i+1, i+2, m
k
của thuật toán
Ukkonen để mở rộng cây hậu tố tổng quát phủ toàn bộ xâu.
Đi sâu vào chi tiết, việc tìm tiền tố dài nhất đã có trong cây đồng nghĩa với việc tìm đường đi dài
nhất trong cây có nhãn S
k
[1 i] bằng cách quét từng kí tự trên đường đi từ gốc. Có hai trường hợp xảy
ra:
1. Đường đi kết thúc ở nút v (có thể là nút gốc): thêm nút con mới nối với v bằng cạnh có nhãn
là S
k
[i+1].
2. Đường đi kết thúc giữa một cạnh: chia đôi cạnh tại điểm đường đi kết thúc và tạo ra nút mới
v. Tạo nút con của v nối với nó bằng cạnh S
k
[i+1].
Sau khi thực hiện xong bước trên bước mở rộng đầu tiên của giai đoạn i+1 đã hoàn thành, ta có thể
đi theo nút cha của v, theo liên kết hậu tố v.v để thực hiện các bước mở rộng tiếp theo. Lưu ý rằng
trong trường hợp thứ 2 ta cũng cần đảm bảo liên kết hậu tố của v sẽ được thiết lập trong bước mở rộng
tiếp theo.
Chương 4. Bài toán tìm xâu con chung dài nhất

1
= abcdefg và S
2
= bccdegf ta có:
• Z = bc là xâu con chung.
• Xâu efg không phải xâu con chung.
• Z = bc có độ dài 2 không phải xâu con chung dài nhất vì có
• Xâu cde là xâu con chung có độ dài 3.
• Xâu cde là xâu con chung dài nhất vì không tìm được xâu con chung có độ dài 4.
4.2. Tìm xâu con chung dài nhất của hai xâu
Trong cây hậu tố tổng quát của xâu S
1
và S
2
, đánh dấu các nút trong bằng 1 (hoặc 2) nếu cây con
tại nút đó chứa nút lá có nhãn 1 (hoặc 2). Nhãn của đường đi từ gốc đến mỗi nút được đánh dấu cả hai
là một xâu con chung của hai xâu. Nút có nhãn dài nhất hay độ sâu đường đi lớn nhất cho ta lời giải của
bài toán.
Ví dụ trong Hình 10 (trang 14) các đỉnh u, v, w, t lần lượt tương ứng với các xâu con chung bx,
abx, a, x của hai xâu ban đầu. Xâu con chung dài nhất là abx tương ứng với đỉnh v. Qua hình vẽ ta cũng
nhận thấy rằng khi đã tìm được một đỉnh trong thoả mãn xâu con của nó chứa cả nút lá của S
1
và S
2
thì
không cần xét các đỉnh cha của nó nữa vì đường đi tương ứng với các đỉnh cha chắc chắn ngắn hơn
đường đi của đỉnh đó. Trong trường hợp này việc xét đỉnh w là không cần thiết.
Ta có thể duyệt đồng thời tính độ sâu đường đi cho tất cả các nút trong cây trong thời gian O(|V|+|
E|) bằng giải thuật tìm kiếm theo chiều sâu (DFS). Do số nút và số cạnh của cây đều là O(N) với N là
tổng độ dài hai xâu nên ta có giải thuật tìm xâu con chung dài nhất trong thời gian tuyến tính.

ch s xâu là k và tăng giá tr C(v) lên m t đ n v .ỉ ố ị ộ ơ ị
M i l n duy t c n th i gian O(N) do s nút c a cây tăng tuy n tính v i N nên t ng công K l nỗ ầ ệ ầ ờ ố ủ ế ớ ổ ầ
duy t ta m t kho ng th i gian O(KN), đây cũng là đ ph c t p th i gian c a toàn b thu t toán tìm cácệ ấ ả ờ ộ ứ ạ ờ ủ ộ ậ
xâu con chung dài nh t c a K xâu.ấ ủ
Chương 5. Chương trình thử nghiệm
5.1. Kết quả thử nghiệm
Hình 12 cho thấy thời gian dựng cây hậu tố phụ thuộc tuyến tính vào độ dài xâu.
Hình 13 cho thấy thời gian giải bài toán k-xâu con chung lần lượt với 2, 3, 4, 5 xâu có độ dài bằng
nhau. Đồ thị thể hiện rất rõ sự phụ thuộc tuyến tính của thuật toán vào tích của số xâu và độ dài xâu.
Chương trình thử nghiệm được cài đặt bằng ngôn ngữ C, chạy trên máy Intel Core Duo với 1Gb
bộ nhớ trong.
Hình 12: Đồ thị thời gian dựng cây hậu tố phụ thuộc vào kích thước xâu. Kích thước tính theo đơn vị
4Kb, thời gian tính theo giây.
5.2. Hướng dẫn cài đặt chương trình
Chương trình cs-suffix-tree sử dụng bộ giao diện đa nền GTK+ và phần mềm GraphViz để trực
quan hoá cây hậu tố. Chương trình có thể chạy trên hệ điều hành *nix và Windows.
Một bản GTK được phát hành kèm với chương trình, để chạy chương trình bằng bản này hãy dùng
tệp cs-suffix-tree.bat. Nếu đã cài GTK trong máy và thư mục bin có trong biến môi trường PATH của
Windows, người sử dụng có thể chạy trực tiếp tệp cs-suffix-tree.exe.
Bộ cài đặt GraphViz đi kèm với chương trình và cần được hoàn thành trước khi chạy chương
trình. Sau khi cài đặt xong GraphViz người dùng cũng nên thêm thư mục bin (chẳng hạn “C:\Program
Files\Graphviz2.26.3\bin”) vào biến môi trường PATH của Windows để tiện lợi khi sử dụng.
5.3. Hướng dẫn sử dụng chương trình
5.3.1. Trực quan hoá cây hậu tố
Kích hoạt chương trình bằng cách chạy tệp cs-suffix-tree.bat hoặc cs-suffix-tree.exe không có
tham số.
Màn hình chương trình gồm hai phần:
• Phần thông tin bên tay trái
• Phần hình ảnh bên tay phải
Người sử dụng nhập ít nhất là một xâu vào trong các text box có nhãn S1, S2, , S5 và nhấn nút

5.4. Hướng dẫn biên dịch mã nguồn
Để biên dịch mã nguồn trên Linux chỉ cần cài Eclipse với plugin CDT.
Để biên dịch mã nguồn trên Windows ngoài Eclipse + CDT còn cần thiết lập môi trường lập trình
gồm có (các tệp cài đặt được đặt trong thư mục dev của gói sản phẩm):
• MinGW ( hoặc mingw-get-inst-20101030.exe): tạo môi trường biên
dịch GNU C trên hệ điều hành Windows.
• MSYS ( đi kèm với bộ cài MinGW): một số công cụ cần
thiết để biên dịch chương trình GNU C.
• GTK ( hoặc gtk+-bundle_2.22.0-
20101016_win32.zip): thư viện giao diện, giải nén vào thư mục C:\GTK.
Giao diện chương trình được thiết kế bằng chương trình Glade và chứa trong tệp ui.glade. Để xem
tệp này cần cài đặt Glade 3 ( hoặc tệp
glade3-3.6.7-with-GTK+.exe trong thư mục dev).
Sau khi cài đặt các gói phần mềm trên, cần thiết lập môi trường để Eclipse có thể tìm được các tệp
thực thi cũng như các tệp header của thư viện. Tốt nhất là nên thêm đường dẫn đến thư mục bin của
MinGW, bin của MSYS (nằm trong MinGW), bin của GTK vào biến môi trường PATH của Windows.
Một số hình ảnh về cách cấu hình dự án trong Eclipse như sau (phải chuột vào tên dự án, chọn
Properties ):
class="bi x5 y160 w2 h1e"
Hình 14: Cấu hình Linker: thêm cờ mms-bitfields
Hình 15: Cấu hình assembler: thêm cờ mms-bitfields
Hình 16: Cấu hình compiler: thêm cờ mms-bitfields