Ứ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ấn

2

1

Trườ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: [email protected]

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