CHƯƠNG 1 Trong chương này, chúng tôi trình bày tổng quan về bài toán hỗ trợ lựa chọn phản biện và các phương pháp giải quyết bài toán đã được công bố như Thuật toán Kalmukov, Bài toán lựa chọn phản biện CMACRA, Thuật toán Greedy xấp xỉ 1/3. 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 2. Một số phương pháp so khớp mẫu trong tính toán độ gần tựa ngữ nghĩa Bài toán xác định độ gần ngữ nghĩa ngày càng được nhiều tác giả quan tâm và có nhiều ứng dụng trong thực tế do sự tăng trưởng nhanh chóng của các hệ thống tìm kiếm thông tin [20, 24, 25]. Các kết quả nghiên cứu thường tập trung vào các phương pháp thống kê sử dụng độ đo dựa vào sự xuất hiện của từ, tần suất xuất hiện của từ [2, 21], độ đo Levenshtein tìm khoảng cách giữa hai từ [24]… hoặc các phương pháp dựa trên quan hệ ngữ nghĩa giữa các từ.
Phương pháp thống kê có ưu điểm tốc độ xử lý nhanh đối với hệ thống dữ liệu lớn.Vì vậy, trong nội dung luận văn này chúng tôi tập trung nghiên cứu phương pháp thống kê làm cơ sở lý thuyết cho việc xây dựng thuật toán lựa chọn phản biện bài báo cho tạp chí. Các nhà khoa học tham gia phản biện và các từ khóa chuyên môn được cập nhật thường xuyên làm cho cơ sở dữ liệu ngày càng lớn.Vì vậy, nếu sử dụng nội dung bài báo hay tóm tắt bài báo để làm dữ liệu tìm kiếm trong cơ sở dữ liệu phản biện sẽ phải chấp nhận chi phí khá lớn về thời gian tính toán.Điều này hoàn toàn không khả thi mà thay vào đó mỗi bài báo sẽ được đặc trưng bởi một số từ khóa, các từ khóa này sẽ đóng vai trò là dữ liệu đầu vào cho thuật toán. Kết quả của thuật toán là danh sách các phản biện được sắp xếp theo thứ tự ưu tiên về chuyên môn gần nhất với bài báo. Độ ưu tiên gần nhất về chuyên môn với bài báo được hiểu là độ gần ngữ nghĩa giữa từ khóa chuyên môn phản biện và từ khóa bài báo.Trong đó, độ gần ngữ nghĩa là đại lượng dùng để phản ánh sự giống nhau về nội dung, ý nghĩa giữa hai hay nhiều đối tượng.
Từ khóa là tập hợp các từ đơn được sắp xếp như một từ ghép nhằm chỉ sự đặc trưng của một đối tượng. Như vậy, bài toán tìm phản biện được quy về bài toán tính độ gần nghữ nghĩa giữa các xâu ký tự. Bài toán xác định độ gần ngữ nghĩa được phát biểu như sau: Cho xâu mẫu P=P0P1…Pm và xâu đích T=T0T1…Tn (m ≤ n) trên cùng một bảng chữ cái A. Cần tìm độ gần ngữ nghĩa giữa xâu mẫu P và xâu đích T.
Lời giải cho bài toán này đã được nhiều tác giả nghiên cứu. Để rõ hơn, sau đây chúng tôi trình bày một số thuật toán làm cơ sở lý thuyết cho ứng dụng, trong đó bao gồm các thuật toán đối sánh mẫu. Thuật toán Brute Force Đối sánh mẫu là một chủ đề quan trọng của lĩnh vực xử lý văn bản. Bài toán so mẫu chính xác tổng quát được phát biểu là: Cho xâu mẫu P và xâu đích (văn bản) T 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trên cùng bảng chữ cái A.
Tìm một sự xuất hiện của P trong T. Thuật toán cơ bản nhất tìm lời giải cho bài toán là thuật toán Brute Force [24] với độ phức tạp của thuật toán là O(mn), tư tưởng của thuật toán là kiểm tra tất cả các vị trí trong T từ vị trí đầu tiên đến vị trí thứ n-m, mỗi vị trí thứ i thuật toán thực hiện so sánh T[i,i+1,…,i+m-1] với xâu mẫu P, nếu thấy thì trả về vị trí i, nếu không thấy thì tiếp tục dịch sang vị trí thứ i+1. Nhược điểm của thuật toán này là kiểm tra tất cả các vị trí i (i=0,1,…,n-m) mà không quan tâm tới khả năng xuất hiện xâu mẫu hay không ở mỗi vị trí. Giả mã của thuật toán như sau: int BFmatcher(int n, int m){ int i = 0, s = 0; int matched = 1; for(i = 0; i <= n-m+1; i++){ s = 0; matched = 1; while((matched) && (s <= m-1)){ if (T[i+s] != P[s+1]){ matched = 0; }else { s++; } } if(matched){ return i; } } return -1; // -1 is NONE } Có thể thấy với mỗi vòng lặp, chúng ta mất tối đa mm phép so sánh để kiểm tra xâu P có xuất hiện trong văn bản hay không.
Do đó: Thời gian tìm xâu mẫu P trong văn bản T của giải thuật là O(mn). Thuật toán Knuth-Morris-Pratt Khắc phục hạn chế của thuật toán Brute Force, Knuth, Donald E. Morris, Jr và Vaughan R. Pratt [22] đã đề xuất thuật toán tìm kiếm KMP có độ phức tạp tuyến tính O(n+m), ý tưởng chính của thuật toán là tìm kiếm vị trí của xâu mẫu P trong T, nếu tìm thấy vị trí sai thì chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ được tận dụng thông tin từ quá trình tìm kiếm trước để không phải kiểm tra những vị trí mà chắc chắn là vị trí không xuất hiện xâu mẫu P.
Thuật toán KMP được mô tả như sau: 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Input: P, T Output: Vị trí của mẫu P xuất hiện trong T Thuật toán 1 i=0; l=0; pos=l; matched=0 ; while(l + i<= n){ if(P[i] ==T[l + i]){ i:= i + 1; if(i==m){ matched=1;returnpos; } } else if(KMP[i] > -1){ i=KMP[i];l=l + i - KMP[i];pos=l; } else{ i= 0;l=l + 1;pos=l; } } Return {pos, matched} Trong đó, matched là biến cho giá trị là 0 nếu không tìm thấy và giá trị là 1 nếu tìm thấy P xuất hiện trong T; pos là vị trí xuất hiện của P trong T;KMPlà bảng đối sánh một phần, với sự xuất hiện của KMP cho thấy thuật toán thực hiện với độ phức tạp là O(n), mục đích của bảng là cho phép thuật toán so sánh mỗi ký tự của T không quá một lần. Thuật toán xác định bảng KMP được mô tả như sau: Input:P Output: Bảng KMP Thuật toán tạo bảng KMP KMP[0]=-1; KMP[3]= 0; i=2; j=0; while(i<m){ if(P[i-1]==P[j]){ KMP[i]=j + 1; i=i + 1; j=j + 1; } else if (j> 0) j=KMP[j]; else{ KMP[i]= 0; i=i + 1; } } Độ phức tạp của thuật toán xây dựng bảng KMP là O(m). Phương pháp quy hoạch động và ứng dụng trong lựa chọn phản biện Trong nhiều ứng dụng tìm kiếm thực tế, mẫu P hoặc chuỗi văn bản T xảy ra các “lỗi” do các nguyên nhân khác nhau như sự thay đổi hình thái từ hay các lỗi chính tả 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com như thêm, bớt hay thay đổi ký tự trong từ thì đòi hỏi hệ thống tìm kiếm cần phải linh hoạt và mềm dẻo hơn mà vẫn cho kết quả như mong muốn, và cụ thể là trong ứng dụng tìm độ gần ngữ nghĩa giữa từ khóa bài báo và từ khóa người phản biện. Ví dụ: nếu cho xâu mẫu P=”approximate searching” và văn bản T=”approximated searching”, nếu sử dụng các thuật toán đối sánh chính xác thì dễ thấy P không xuất hiện trong T.
Nhưng thực tế có thể thấy giữa P và T có nội dung gần giống nhau do có sai khác ký tự “d”. Chính vì vậy, lý thuyết so mẫu xấp xỉ ra đời cho phép tìm kiếm những thông tin gần giống và mang lại kết quả mềm dẻo hơn. Bài toán so mẫu xấp xỉ là sự mở rộng của bài toán so mẫu chính xác và đặt ra yêu cầu là tìm vị trí xuất hiện của P trong T với số “lỗi” tối đa là e “lỗi”. Như vậy bài toán so mẫu xấp xỉ có thể được quy về bài toán tìm khúc con chung dài nhất giữa hai xâu ký tự và lời giải được chấp nhận nếu như độ dài của khúc con chung có độ lệch không quá e ký tự so với mẫu P.
Đã có nhiều phương pháp tìm xâu con chung dài nhất như phương pháp quy hoạch động tìm khoảng cách Edit (hay còn goi là khoảng cách Levenshtein) [23] hoặc các phương pháp đối sánh mẫu theo cách tiếp cận otomat hữu hạn mờ [1],. Các phương pháp này còn được sử dụng khi xét sự tương đồng về mặt ngữ nghĩa khi thứ tự các từ trong xâu được bảo toàn. Phương pháp quy hoạch động Khái niệm Khoảng cách Levenshtein (hay còn gọi là khoảng cách Edit) thể hiện khoảng cách khác biệt giữa 2 chuỗi ký tự. Khoảng cách Levenshtein giữa chuỗi S và chuỗi T là số bước ít nhất biến chuỗi S thành chuỗi T thông qua 3 phép biến đổi là: Xoá 1 ký tự; thêm 1 ký tự; thay ký tự này bằng ký tự khác.
Khoảng cách này được đặt theo tên Vladimir Levenshtein, người đã đề ra khái niệm này vào năm 1965. Nó được sử dụng trong việc tính toán sự giống và khác nhau giữa 2 chuỗi, như chương trình kiểm tra lỗi chính tả của winword spellchecker. Ví dụ: Khoảng cách Levenshtein giữa 2 chuỗi "kitten" và "sitting" là 3, vì phải dùng ít nhất 3 lần biến đổi. kitten -> sitten (thay "k" bằng "s") sitten -> sittin (thay "e" bằng "i") sittin -> sitting (thêm ký tự "g") 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Để tính toán Khoảng cách Edit, ta sử dụng thuật toán quy hoạch động, tính toán trên mảng 2 chiều (n+1)*(m+1), với n, m là độ dài của chuỗi cần tính.
Sau đây là thuật toán quy hoạch động (S, T là chuỗi cần tính khoảng cách, n, m là độ dài của chuỗi S, T): Thuật toán quy hoạch động tìm khoảng cách Edit giữa hai xâu ký tự Input: S, T Output: Edit distance int Edit_distance(S, T){ for (int i = 0; i <= m; i++) d[i, 0] = i; for (int j = 0; j <= n; j++) d[0, j] = j; for (int i = 0; i <= m; i++) for (int j = 0; j <= n; j++) { if (S[i] == T[j]) cost = 0; Else cost = 1; d[i + 1, j + 1] = Min(d[i, j + 1] + 1, d[i + 1, j] + 1, d[i, j] + cost); } return d[i,j]; } Trong mục này, chúng tôi xây dựng thuật toán lựa chọn phản biện dựa trên phương pháp quy hoạch động. Việc chọn ra người phản biện có cùng hướng nghiên cứu với nội dung bài báo từ cơ sở dữ liệu các nhà khoa học đảm bảo tính chất khách quan, đúng vấn đề cần phản biện là điều hết sức cần thiết đối với một tạp chí khoa học. Muốn vậy, việc phân loại và chọn phản biện cần phải dựa vào nội dung bài báo, hay phần tóm tắt bài báo hoặc các từ khóa cho mỗi bài báo.