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. | 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 .
