Ứ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