Ứ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<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 80(04): 109 - 113<br /> <br /> ỨNG DỤNG THUẬT TOÁN XÂU CON CHUNG DÀI NHẤT<br /> TRONG SO SÁNH MÃ NGUỒN CHƯƠNG TRÌNH<br /> Trần Ngọc Hà1*, Triệu Hải Long1, Nguyễn Ngọc Tuấn2<br /> 1<br /> <br /> 2<br /> <br /> Trường Đại học Sư phạm, Đại học Thái Nguyên,<br /> K17 Khoa học máy tính, Đại học Công Nghệ, Đại học Quốc gia Hà Nội<br /> <br /> TÓM TẮT<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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.<br /> 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<br /> <br /> MỞ ĐẦU*<br /> Mã nguồn là một dãy các câu lệnh được viết<br /> bằng một ngôn ngữ lập trình. Tìm phần chung<br /> giữa các code được hiểu là tìm các đoạn code<br /> có sự trùng lặp hoàn toàn hoặc một phần, có<br /> thể về nội dung hoặc cấu trúc đoạn code. Khi<br /> làm việc với code, nhất là code do người khác<br /> viết ra (cùng nhóm, học sinh...), việc tìm ra<br /> những phần giống nhau giúp giảm bớt thời<br /> gian, chi phí thực hiện, phát hiện sự sao<br /> chép... Tuy nhiên việc này gặp nhiều khó<br /> khăn như sự phức tạp của các ngôn ngữ lập<br /> trình, về mặt cú pháp, cách sử dụng câu<br /> lệnh... ví dụ ngôn ngữ lập trình Pascal không<br /> phân biệt kí tự thường và hoa, cản trở việc<br /> nhận dạng từ. Ở mức cao hơn, việc so sánh<br /> đoạn code gần giống nhau, như về câu lệnh,<br /> cấu trúc (ví dụ đoạn code chỉ khác nhau ở tên<br /> biến) hay có sự thêm bớt đoạn code khác thì<br /> chỉ cần đưa ra đoạn giống nhau. Hiện nay đã<br /> có nhiều nghiên cứu về so sánh văn<br /> bản[2][3][6][7] nhưng các phương pháp đề<br /> xuất chưa xử lí được với code. Để giải quyết<br /> các vấn đề trên chúng tôi đề xuất thuật toán<br /> xử lý được mô tả qua các bước như sau: Ta<br /> tạm coi code là chuỗi kí tự đã loại bỏ kí tự<br /> điều khiển, chú thích… chỉ bao gồm các từ<br /> khóa (ví dụ var, if, for), câu lệnh (=, >, A[j] then<br /> Begin<br /> tg:=A[j-1];<br /> A[j-1]:=A[j];<br /> A[j]:=tg;<br /> End;<br /> a. Code1<br /> For x:=2 to n do<br /> For y:=n downto x1 do<br /> If A[y-1]>A[y] then<br /> Begin<br /> tg:=A[y-1];<br /> A[y-1]:=A[y];<br /> A[y]:=tg;<br /> End;<br /> b. Code2<br /> For i:=2 to n do<br /> For j:=n downto i do<br /> If A[j-1]>A[j] then<br /> Begin<br /> tg:=A[j-1];<br /> A[j-]:=A[j];<br /> A[j]:=tg;<br /> End;<br /> c. Dãy từ chung code1 và code2 (phần chung<br /> được đánh dấu bằng phần gạch chân).<br /> 110<br /> <br /> 80(04): 109 - 113<br /> <br /> Trong ví dụ trên cả hai đoạn mã nguồn trên<br /> chỉ khác nhau ở tên biến nhưng cấu trúc câu<br /> lệnh giống nhau, code1 sử dụng “i” và “j” còn<br /> code2 dùng “x” và “y”, tuy nhiên cùng mô tả<br /> thuật toán sắp xếp nổi bọt, ta cần nhận dạng,<br /> đánh dấu cho bước xử lý sau đó.<br /> Xử lý biến: Quá trình này tìm ra mối liên<br /> quan giữa các biến trong code1 và code2,<br /> Trong so sánh code nếu code2 sử dụng 1 phần<br /> mã code1 thì các biến trong phần code đó<br /> giống hệt nhau, ta chỉ việc đánh dấu các biến<br /> đó trong code1 và code2. Tuy nhiên nếu<br /> code2 chỉ sử dụng một phần, hay thay chỉ<br /> thay đổi tên biến khác đi so với code1, thì cần<br /> nhận dạng sự tương ứng giữa các biến dựa<br /> trên dãy từ chung tìm được trước đó. Nếu vai<br /> trò 2 biến như nhau ta coi 2 biến đó là tương<br /> đương. Trong ví dụ 1 thì “i” và “x” là tương<br /> đương, và chúng ta có thể nhận biết điều này<br /> vì liền kề với “i” trong code1 và “x” trong<br /> code2 là dãy từ chung của 2 code và từ chung<br /> này giống nhau, ngoài ra vị trí, số lượng xuất<br /> hiện cũng trùng lặp, những cơ sở đó giúp ta<br /> đưa ra kết luận tương đương các biến , còn<br /> biến “i” và “y” không tương đương vì số<br /> lượng, vị trí xuất hiện không giống nhau.<br /> Truy vết & output: các dãy từ dài nhất<br /> không lưu trực tiếp trong bộ nhớ mà lưu<br /> dưới dạng dãy chỉ số từ trong code2, từ dãy<br /> chỉ số này ta khôi phục dãy từ chung và đưa<br /> ra output.<br /> CẢI TIẾN THUẬT TOÁN TÌM DÃY<br /> CHUNG DÀI NHẤT<br /> Sau khi tách được các từ trong code1 và<br /> code2, từ 2 dãy từ (input) nhiệm vụ của chúng<br /> ta là tìm dãy chung dài nhất giữa 2 dãy, sau<br /> đó đánh dấu và đưa ra output của bài toán. Để<br /> tiện theo dõi ta coi code1 là một dãy các từ<br /> đặt trong mảng A[n] (n là số từ code1),tương<br /> tự code2 là B[m] với m là số từ trong code2.<br /> Thuật toán tìm dãy từ trên thuật toán Hunt [5]<br /> có nhiệm vụ tìm ra dãy từ chung dài nhất từ<br /> A[n] và B[m] sao cho dãy chung có các từ<br /> xuất hiện trong code1 và code2 là gần nhất.<br /> Tư tưởng chung của thuật toán như sau:<br /> A[i]=B[j]với mỗi A[i] ta định vị một từ B[j]<br /> tương ứng sao cho:<br /> <br /> Trần Ngọc Hà và đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br />  A[i ] = B[j ]<br /> <br />  j min<br /> Để làm việc này ta sử dụng một mảng<br /> THRESH[O:n] để lưu vị trí j min trong B sao<br /> cho A[i]=B[j] và có thể chèn vào dãy từ<br /> chung. Với mỗi A[i] nếu được định vị trong B<br /> làm tăng kích thước THRESH lên 1 đơn vị,<br /> cuối cùng kích thước THRESH chính là độ<br /> dài dãy từ lớn nhất. Tuy nhiên dãy THRESH<br /> chứa vị trí các từ trong B chưa chắc đã là vị<br /> trí các từ thuộc dãy chung lớn nhất, mà chúng<br /> được lưu lại trong danh sách LINK, gồm<br /> thông tin nối từ i sang j và từ chung trước đó<br /> LINK[k-1]. Cuối cùng sử dụng danh sách<br /> LINK để khôi phục dãy chung dài nhất.<br /> Để tăng tốc thuật toán và giảm bớt bộ nhớ,<br /> với mỗi A[i] thay vì lần lượt tìm B[j] ta tìm<br /> B[j] qua mảng MATCHLIST chứa chỉ số các<br /> từ trùng lặp B[j] được xây dựng trước đó.<br /> Ví dụ A=”a b c b d d a”<br /> B=”b a d b a b d”<br /> MATCHLIST[1] = (5, 2)<br /> MATCHLIST[2] = (6, 4, 1)<br /> MATCHLIST[3] = ( )<br /> MATCHLIST[4] = MATCHLIST[2]<br /> MATCHLIST[5] = (7, 3)<br /> MATCHLIST[6] = MATCHLIST[5]<br /> MATCHLIST[7] = MATCHLIST[I]<br /> Hay để giảm chi phí tìm kiếm và bộ nhớ hơn<br /> nữa có thể tổ chức MATCHLIST dưới dạng<br /> danh sách kề (adjacency list)[1]. Chi tiết thuật<br /> toán như sau:<br /> integer array THRESH[O:n];<br /> list array MATCHLIST[1 :n];<br /> pointer array LINK[1 :n];<br /> pointer PTR;<br /> Step 1: Xây dựng MATCHLIST;<br /> for i := 1 step 1 until n do<br /> set MATCHLIST[i] : (j1 ,j2, ... ,jp)<br /> such that<br /> j1 >j2 > ... >jp and code1[i] =<br /> code2[jq] for i