Ứng dụng thuật toán xâu con chung dài nhất trong so sánh mã nguồn chương trình

Trần Ngọc Hà và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 109 - 113 
109 
ỨNG DỤNG THUẬT TOÁN XÂU CON CHUNG DÀI NHẤT 
TRONG SO SÁNH MÃ NGUỒN CHƯƠNG TRÌNH 
 Trần Ngọc Hà1*, Triệu Hải Long1, Nguyễn Ngọc Tuấn2 
1Trường Đại học Sư phạm, Đại học Thái Nguyên, 
2 K17 Khoa học máy tính, Đại học Công Nghệ, Đại học Quốc gia Hà Nội 
TÓM TẮT 
Trong xử lý văn bản nói chung và mã nguồn chương trình nói riêng, việc tìm ra những phần giống 
nhau trong các văn bản hay mã nguồn chương trình có vai trò khá quan trọng, nhất là khi cần phát 
hiện sự sao chép code. Trong bài viết này, chúng tôi muốn giới thiệu thuật toán và các phương 
pháp xử lí liên quan nhằm tìm ra những phần giống nhau trong các code với độ phức tạp về mặt 
thời gian và chi phí bộ nhớ là tuyến tính, độ chính xác cao kể cả trong một số trường hợp đặc biệt. 
Từ khóa: So sánh văn bản, xâu con chung dài nhất, mã nguồn, danh sách kề, sắp xếp đếm phân phối 
MỞ ĐẦU* 
Mã nguồn là một dãy các câu lệnh được viết 
bằng một ngôn ngữ lập trình. Tìm phần chung 
giữa các code được hiểu là tìm các đoạn code 
có sự trùng lặp hoàn toàn hoặc một phần, có 
thể về nội dung hoặc cấu trúc đoạn code. Khi 
làm việc với code, nhất là code do người khác 
viết ra (cùng nhóm, học sinh...), việc tìm ra 
những phần giống nhau giúp giảm bớt thời 
gian, chi phí thực hiện, phát hiện sự sao 
chép... Tuy nhiên việc này gặp nhiều khó 
khăn như sự phức tạp của các ngôn ngữ lập 
trình, về mặt cú pháp, cách sử dụng câu 
lệnh... ví dụ ngôn ngữ lập trình Pascal không 
phân biệt kí tự thường và hoa, cản trở việc 
nhận dạng từ. Ở mức cao hơn, việc so sánh 
đoạn code gần giống nhau, như về câu lệnh, 
cấu trúc (ví dụ đoạn code chỉ khác nhau ở tên 
biến) hay có sự thêm bớt đoạn code khác thì 
chỉ cần đưa ra đoạn giống nhau. Hiện nay đã 
có nhiều nghiên cứu về so sánh văn 
bản[2][3][6][7] nhưng các phương pháp đề 
xuất chưa xử lí được với code. Để giải quyết 
các vấn đề trên chúng tôi đề xuất thuật toán 
xử lý được mô tả qua các bước như sau: Ta 
tạm coi code là chuỗi kí tự đã loại bỏ kí tự 
điều khiển, chú thích chỉ bao gồm các từ 
khóa (ví dụ var, if, for), câu lệnh (=, >, <), giá 
trị số coi là “từ”, và các “biến”. Giả sử code 
mẫu là code1, code đem so sánh là code2. 
*Tel: 0983.168.400; Email: hatn84@gmail.com 
Bước 1: Loại bỏ phần không liên quan, sau 
đó tách riêng các từ khóa, câu lệnh và biến 
trong code. 
Bước 2: Áp dụng thuật toán tìm dãy các từ 
khóa, câu lệnh dài nhất xuất hiện ở cả 2 code 
giữ thứ tự trước sau. Nếu có nhiều dãy như vậy 
ưu tiên các dãy có từ xuất hiện gần nhau nhất. 
Bước 3: Dựa vào dãy các từ chung nhau tìm 
mối liên quan giữa các biến của code1 và 
code2, từ đó đưa ra kết luận biến code1 tương 
ứng biến code2 hay không. 
Bước 4: Truy vết đánh dấu dãy từ chung rồi 
đưa ra output. 
Hình 1: Sơ đồ minh họa thuật toán 
Tách từ: Phân lớp các từ trong code thành 2 
lớp riêng biệt dựa vào từ điển từ khóa và đặc 
trưng câu lệnh của ngôn ngữ lập trình. 
Tách từ 
code 
Biến Từ 
Code1 & 
Code2 
Tìm dãy từ 
chung 
Xử lý biến 
Truy vết 
Dãy con 
chung dài 
nhất 
Trần Ngọc Hà và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 109 - 113 
110 
Các biến có thể nhận biết dựa trên từ khóa 
khai báo, tùy vào ngôn ngữ lập trình và công 
cụ lập trình (IDE), có thể đi trước (C++)[4] 
hoặc đi sau (Pascal)... Các phần không liên 
quan cần loại bỏ để không đưa vào xử lí, ví 
dụ như phần chú thích, kí tự điều khiển, dẫn 
biên dịch, tiền xử lý... 
Tìm dãy chung: Việc sử dụng liên tiếp các 
câu lệnh giống nhau cho thấy có sự trùng lặp 
trong code, ta cần tìm ra các đoạn này với độ 
dài lớn nhất. Thuật toán trong mục II sẽ giúp 
tìm ra dãy từ chung dài nhất, và các từ này ưu 
tiên xuất hiện liền kề hoặc khoảng cách xuất 
hiện gần nhau nhất trong code. Trong ví dụ 
dưới đây với code1 và code2 cụ thể sẽ cho kết 
quả như sau: 
For i:=2 to n do 
For j:=n downto i do 
If A[j-1]>A[j] then 
 Begin 
 tg:=A[j-1]; 
 A[j-1]:=A[j]; 
 A[j]:=tg; 
 End; 
a. Code1 
For x:=2 to n do 
For y:=n downto x1 do 
If A[y-1]>A[y] then 
 Begin 
 tg:=A[y-1]; 
 A[y-1]:=A[y]; 
 A[y]:=tg; 
 End; 
b. Code2 
For i:=2 to n do 
For j:=n downto i do 
If A[j-1]>A[j] then Begin 
 tg:=A[j-1]; 
 A[j-]:=A[j]; 
 A[j]:=tg; 
 End; 
c. Dãy từ chung code1 và code2 (phần chung 
được đánh dấu bằng phần gạch chân). 
Trong ví dụ trên cả hai đoạn mã nguồn trên 
chỉ khác nhau ở tên biến nhưng cấu trúc câu 
lệnh giống nhau, code1 sử dụng “i” và “j” còn 
code2 dùng “x” và “y”, tuy nhiên cùng mô tả 
thuật toán sắp xếp nổi bọt, ta cần nhận dạng, 
đánh dấu cho bước xử lý sau đó. 
Xử lý biến: Quá trình này tìm ra mối liên 
quan giữa các biến trong code1 và code2, 
Trong so sánh code nếu code2 sử dụng 1 phần 
mã code1 thì các biến trong phần code đó 
giống hệt nhau, ta chỉ việc đánh dấu các biến 
đó trong code1 và code2. Tuy nhiên nếu 
code2 chỉ sử dụng một phần, hay thay chỉ 
thay đổi tên biến khác đi so với code1, thì cần 
nhận dạng sự tương ứng giữa các biến dựa 
trên dãy từ chung tìm được trước đó. Nếu vai 
trò 2 biến như nhau ta coi 2 biến đó là tương 
đương. Trong ví dụ 1 thì “i” và “x” là tương 
đương, và chúng ta có thể nhận biết điều này 
vì liền kề với “i” trong code1 và “x” trong 
code2 là dãy từ chung của 2 code và từ chung 
này giống nhau, ngoài ra vị trí, số lượng xuất 
hiện cũng trùng lặp, những cơ sở đó giúp ta 
đưa ra kết luận tương đương các biến , còn 
biến “i” và “y” không tương đương vì số 
lượng, vị trí xuất hiện không giống nhau. 
Truy vết & output: các dãy từ dài nhất 
không lưu trực tiếp trong bộ nhớ mà lưu 
dưới dạng dãy chỉ số từ trong code2, từ dãy 
chỉ số này ta khôi phục dãy từ chung và đưa 
ra output. 
CẢI TIẾN THUẬT TOÁN TÌM DÃY 
CHUNG DÀI NHẤT 
Sau khi tách được các từ trong code1 và 
code2, từ 2 dãy từ (input) nhiệm vụ của chúng 
ta là tìm dãy chung dài nhất giữa 2 dãy, sau 
đó đánh dấu và đưa ra output của bài toán. Để 
tiện theo dõi ta coi code1 là một dãy các từ 
đặt trong mảng A[n] (n là số từ code1),tương 
tự code2 là B[m] với m là số từ trong code2. 
Thuật toán tìm dãy từ trên thuật toán Hunt [5] 
có nhiệm vụ tìm ra dãy từ chung dài nhất từ 
A[n] và B[m] sao cho dãy chung có các từ 
xuất hiện trong code1 và code2 là gần nhất. 
Tư tưởng chung của thuật toán như sau: 
A[i]=B[j]với mỗi A[i] ta định vị một từ B[j] 
tương ứng sao cho: 
Trần Ngọc Hà và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 109 - 113 
111 
[ ] [ ]
min
A i B j
j
=


Để làm việc này ta sử dụng một mảng 
THRESH[O:n] để lưu vị trí j min trong B sao 
cho A[i]=B[j] và có thể chèn vào dãy từ 
chung. Với mỗi A[i] nếu được định vị trong B 
làm tăng kích thước THRESH lên 1 đơn vị, 
cuối cùng kích thước THRESH chính là độ 
dài dãy từ lớn nhất. Tuy nhiên dãy THRESH 
chứa vị trí các từ trong B chưa chắc đã là vị 
trí các từ thuộc dãy chung lớn nhất, mà chúng 
được lưu lại trong danh sách LINK, gồm 
thông tin nối từ i sang j và từ chung trước đó 
LINK[k-1]. Cuối cùng sử dụng danh sách 
LINK để khôi phục dãy chung dài nhất. 
Để tăng tốc thuật toán và giảm bớt bộ nhớ, 
với mỗi A[i] thay vì lần lượt tìm B[j] ta tìm 
B[j] qua mảng MATCHLIST chứa chỉ số các 
từ trùng lặp B[j] được xây dựng trước đó. 
Ví dụ A=”a b c b d d a” 
 B=”b a d b a b d” 
MATCHLIST[1] = (5, 2) 
MATCHLIST[2] = (6, 4, 1) 
MATCHLIST[3] = ( ) 
MATCHLIST[4] = MATCHLIST[2] 
MATCHLIST[5] = (7, 3) 
MATCHLIST[6] = MATCHLIST[5] 
MATCHLIST[7] = MATCHLIST[I] 
Hay để giảm chi phí tìm kiếm và bộ nhớ hơn 
nữa có thể tổ chức MATCHLIST dưới dạng 
danh sách kề (adjacency list)[1]. Chi tiết thuật 
toán như sau: 
integer array THRESH[O:n]; 
list array MATCHLIST[1 :n]; 
pointer array LINK[1 :n]; 
pointer PTR; 
Step 1: Xây dựng MATCHLIST; 
for i := 1 step 1 until n do 
set MATCHLIST[i] : (j1 ,j2, ... ,jp) 
such that 
j1 >j2 > ... >jp and code1[i] = 
code2[jq] for i <= q < =p; 
Step 2: Khởi tạo THRESH; 
THRESH[O] := 0; 
for i := 1 step 1 until n do THRESH[i] := n 
+ 1; 
LINK[O] := null; 
Step 3: Tìm dãy chung lớn nhất; 
for i := 1 step 1 until n do 
for j on MATCHLIST[i] do 
begin 
find k such that THRESH[k-1] < j < 
THRESH[k]; 
if j < THRESH[k] then 
begin 
THRESH[k] := j; 
LINK[k] := newnode ( i, j, 
LINK[k-l]); 
end; 
end; 
Step 4: Khôi phục dãy chung; 
k := largest k such that THRESH[k] ≠ n + 1; 
PTR := LINK[k]; 
while PTR ≠ null do 
begin 
print (i,j) pair pointed to by PTR; 
advance PT 
end. 
PHÂN TÍCH VÀ ĐÁNH GIÁ 
Do làm việc với A[n] lần lượt từ đầu tới cuối 
đúng 1 lần nên không cần lưu trữ code1 mà 
có thể làm việc trực tiếp từ file lưu trữ code1. 
Các mảng sử dụng trong thuật toán đều 1 
chiều và độ lớn nhỏ hơn max(n, m), do vậy 
chi phí bộ nhớ là tuyến tính. Chi phí thời gian 
của thuật toán chủ yếu cho Step 3, tuy nhiên 
việc tìm vị trí k trong THRESH có thể sử 
dụng phương pháp tìm kiếm nhị phân, do dễ 
dàng nhận thấy các giá trị trong THRESH 
luôn tăng. Trong Step 1, để xây dựng 
MATCHLIST, có thể đưa về sắp xếp B[m] 
kèm lưu chỉ số, tuy nhiên vì số lượng các từ 
trong ngôn ngữ lập trình không nhiều, ta có 
thể dùng phương pháp sắp xếp đếm phân phối 
(distribution sort)[1] để giảm chi phí thời gian 
xuống O(m). Dễ thấy độ phức tạp thời gian 
Trần Ngọc Hà và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 109 - 113 
112 
của thuật toán là O((r + n) log n) với 
r<max(n, m); còn chi phí về mặt bộ nhớ 
làO(max(n,m). Đây là những chi phí chấp 
nhận được và có thể áp dụng với code rất dài. 
THỰC NGHIỆM 
Với những cơ sở lý thuyết nêu trên chúng tôi 
xây dựng một chương trình minh họa xử lý 
văn bản, và so sánh với một số chương trình 
sẵn có, tuy nhiên do hạn chế thời gian nên 
chương trình minh họa chưa trang bị đầy đủ 
chức năng trong bài viết mà tập trung tìm 
dãy từ chung dài nhất giữa hai code. Hình 2 
minh họa giao diện chương trình, sau khi xử 
lý các code1 và code2, chương trình sẽ đưa 
ra phần code chung bằng cách đánh dấu và 
tỉ lệ khớp (match). 
Cũng với đoạn code1 và code2 như trên, thì 
phần mềm của nhóm tác giả Đại học Bách khoa 
Hà Nội chưa nhận biết những đoạn code trùng 
nhau. Kết quả minh họa như trong hình 3. 
Hình 2: Chương trình minh họa 
Hình 3. Phần mềm so sánh văn bản của ĐHBK Hà Nội 
Trần Ngọc Hà và đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 80(04): 109 - 113 
113 
 Hình 4. So sánh code với CodeCompare 
Với phần mềm CodeCompare, một sản phẩm 
thương mại của công ty phát triển phần mềm 
Devart (đối tác cung cấp phần mềm của các 
tập đoàn lớn trên thế giới như Hitachi, 
Siemens, Intel...), hầu hết các đoạn code 
giống nhau được phát hiện, tuy nhiên chưa 
chỉ ra được các biến có vai trò tương tự nhau. 
Các phần khác nhau được đánh dấu đậm 
hơn, các phần giống nhau hoàn toàn được 
giữ nguyên. 
TỔNG KẾT 
Trên đây chúng tôi đã giới thiệu phương pháp 
tìm phần chung của code, thuật toán tìm dãy 
từ chung dài nhất và xây dựng chương trình 
minh họa tính năng so sánh mã nguồn, đây là 
những ứng dụng thực tế giúp ích cho người 
lập trình hoặc giáo viên... những người làm 
việc với code. Trong tương lai có thể áp dụng 
cơ sở lý thuyết để phát triển ứng dụng thông 
minh và tự động hơn, như tự động so sánh 
code với các cơ sở dữ liệu sẵn có như Internet, 
cơ sở dữ liệu bài thi có sẵn... Cuối cùng chúng 
tôi xin gửi lời cảm ơn thạc sỹ Nguyễn Văn 
Trường, khoa Toán, Đại học Sư phạm - Đại 
học Thái Nguyên, đã có nhiều đóng góp giúp 
chúng tôi thực hiện bài báo này. 
TÀI LIỆU THAM KHẢO 
[1]. Alfred V.Aho, Jeffrey D.Ullman, John 
E.Hopcroft, (January 11, 1983), Data Structures 
and Algorithms, Addison Wesley. 
[2]. Beate Commentz-Walter, 1979, A string 
matching algorithm fast on the average Extended 
abstract, Springerlink: Volume 71/1979, 118-132, 
DOI: 10.1007/3-540-09510-1_10. 
[3]. Bilenko; Mooney; Cohen; Ravikumar, 
P.Fienberg, Sep/Oct 2003, Adaptive name 
matching in information integration, IEEE. 
[4]. Herbert Schildt (1998-08-01). C++ The 
Complete Reference Third Edition. Osborne 
McGraw-Hill. ISBN 978-0078824760. 
[5]. James W.Hunt, Thomas G.Szymanski, May 
1977, A fast algorithm for computing longest 
common subsequences, Association for 
Computing Machinery: Volume 20 Issue 5. 
[6]. Michael Steinbach George Karypis Vipin 
Kumar, 2000, A Comparison of Document 
Clustering Techniques, Citeseerx. 
[7]. William W. Cohen, Pradeep Ravikumar 
Stephen, E. Fienberg, 2003, A Comparison of 
String Metrics for Matching Names and Records, 
the Proceedings of the IJCAI. 
SUMMARY 
COMPARE SOURCE CODE OF PROGRAMS USING FAST LONGEST 
COMMON SUBSEQUENCES ALGORITHM 
Tran Ngoc Ha1*, Trieu Hai Long1, Nguyen Ngoc Tuan2 
1
 College of Education – Thai Nguyen University, 
2
 K17 Computer Science – College of Technology-Vietnam National University, Hanoi 
Finding the similar part of text of source code plays an important role in detecting forged code. In 
this paper, we present our algorithm and involved methods to find out similar codes. That can 
reduce time and space complexities to linear ones, increase the rate of accuracy. 
Keywords: Compare documents, Longest Common Subsequences, Source code, adjacency list, 
distribution sort.
*
 Tel: 0983.168.400; Email: hatn84@gmail.com