Ứ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

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.
Nội dung trích xuất từ tài liệu:
Ứ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 Ứ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 1 2 Trường Đại học Sư phạm, Đại học Thái Nguyên, 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 (=, >, 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). 110 80(04): 109 - 113 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Ệ  A[i ] = B[j ]   j min Để 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 ...