Nghiên Cứu Kỹ Thuật Đối Sánh Mẫu Và Ứng Dụng Trong Tìm Kiếm Xấp Xỉ

Nghiên cứu các kỹ thuật đối sánh mẫu và ứng dụng trong tìm kiếm xấp xỉ, mang lại giải pháp hiệu quả cho bài toán phân tích dữ liệu.

• Tác giả: Phạm Văn Quyết
• Người hướng dẫn: TS. Nguyễn Đình Dũng
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên Cứu Kỹ Thuật Đối Sánh Mẫu Trong Tìm Kiếm Xấp Xỉ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN KỸ THUẬT ĐỐI SÁNH MẪU
• 1.1. Đối sánh chuỗi
• 1.2. Bài toán đối sánh chuỗi
• 1.3. Các thuật toán đối sánh chính xác cổ điển
• 1.4. Các thuật toán đối sánh chính xác dựa trên mô hình Automat
• 1.5. Thuật toán đối sánh gần đúng dựa trên quy hoạch động
• 1.6. Đối sánh đồ thị
• 1.7. Bài toán đối sánh đồ thị
• 1.8. Một số phương pháp đối sánh đồ thị
• 2. CHƯƠNG 2: ỨNG DỤNG KỸ THUẬT ĐỐI SÁNH MẪU ĐỐI VỚI MỘT SỐ BÀI TOÁN TÌM KIẾM XẤP XỈ
• 2.1. Bài toán lựa chọn phản biện
• 2.2. Tổng quan về hệ thống hỗ trợ lựa chọn phản biện
• 2.3. Bài toán xác định độ gần ngữ nghĩa
• 2.4. Thuật toán lựa chọn phản biện dựa trên quy hoạch động
• 2.5. Thuật toán lựa chọn phản biện dựa trên Otomat hữu hạn mờ
• 2.6. Bài toán phát hiện giả mạo trang web
• 2.7. Khái niệm cây DOM
• 2.8. Xây dựng cây DOM
• 2.9. Phát hiện giả mạo dựa trên cây DOM
• 3. CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG
• 3.1. Mô tả yêu cầu hệ thống
• 3.2. Một số chức năng chính của hệ thống
• 3.3. Xác định Actor và Use Case
• 3.4. Các chức năng của chương trình
• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Kỹ Thuật Đối Sánh Mẫu Trong Tìm Kiếm Xấp Xỉ

Đối sánh mẫu, còn gọi là so khớp mẫu hoặc tìm kiếm mẫu, là một bài toán quan trọng trong lĩnh vực tìm kiếm dữ liệu, xử lý văn bản và ứng dụng CNTT. Bài toán này có ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Chương này tập trung vào một số kỹ thuật đối sánh mẫu được dùng cho hai bài toán chính: tìm kiếm phản biện và phát hiện trang web giả mạo. Đối sánh mẫu đóng vai trò then chốt trong việc tìm kiếm thông tin gần đúng, đặc biệt khi dữ liệu không hoàn toàn chính xác hoặc có sai sót. Sự phát triển của các kỹ thuật đối sánh mẫu đã giúp nâng cao hiệu quả của các hệ thống tìm kiếm và phân tích dữ liệu. Các nghiên cứu gần đây nhấn mạnh vai trò của đối sánh mẫu trong việc giải quyết các bài toán phức tạp trong an ninh mạng, thương mại điện tử và y học.

1.1. Giới thiệu bài toán đối sánh mẫu và ứng dụng thực tế

Bài toán đối sánh mẫu (pattern matching) là một chủ đề quan trọng của lĩnh vực xử lý văn bản và được ứng dụng rộng rãi trong nhiều lĩnh vực như: An ninh mạng, quảng cáo, xử lý văn bản, tài chính và thị trường chứng khoán, thương mại, giáo dục, y tế, sinh học, bưu chính viễn thông,… Trong lĩnh vực an ninh mạng đối sánh mẫu được ứng dụng để kiểm tra và lọc nội dung gói tin trên Firewall, đối sánh mã virus trong các ứng dụng diệt virus, các hệ thống phát hiện và ngăn chặn xâm nhập mạng NIDS/NIPS [10]. Trong lĩnh vực quảng cáo của Google Ads, đối sánh mẫu được dùng để đối sánh từ khóa Google Ads, bao gồm: Đối sánh rộng, đối sánh cụm từ, đối sánh chính xác, và đối sánh cụm từ mới.

1.2. Phân loại các kỹ thuật đối sánh mẫu phổ biến nhất

Các thuật toán đối sánh chuỗi có thể phân loại theo nhiều tiêu chí khác nhau, cho phép lựa chọn phương pháp phù hợp với từng yêu cầu cụ thể. Dựa trên số lượng mẫu, có đối sánh đơn mẫu (single pattern) và đối sánh đa mẫu (multiple patterns). Dựa trên thứ tự so sánh, có các phương pháp: từ trái sang phải, từ phải sang trái, so sánh tại vị trí cụ thể và so sánh không theo thứ tự nhất định. Dựa trên độ chính xác của kết quả, chia thành đối sánh chính xác (Exact String Matching) và đối sánh gần đúng (Approximate String Matching). Mỗi phương pháp đều có ưu và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp sẽ ảnh hưởng đến hiệu suất của hệ thống.

II. Đối Sánh Chuỗi Nền Tảng Tìm Kiếm Xấp Xỉ Hiệu Quả

Đối sánh chuỗi là việc so sánh một chuỗi hoặc nhiều chuỗi với văn bản để tìm vị trí và số lần xuất hiện của chuỗi đó trong văn bản. Bài toán đối sánh chuỗi được mô tả như sau [11]: Cho một bảng chữ cái Σ là một tập hữu hạn các ký tự, một mẫu P (P [1.m]) độ dài m và một chuỗi ký tự T (T [1. Bài toán đặt ra là cần tìm các vị trí xuất hiện của P trong T hoặc P có khớp với một chuỗi con của T hay không? Thuật toán đối sánh chuỗi thường sử dụng cơ chế cửa sổ trượt để so sánh các ký tự của mẫu trong cửa sổ với các ký tự trong văn bản. Tất cả các thuật toán đối sánh chuỗi đều có hai giai đoạn là: tiền xử lý và tìm kiếm.

2.1. Mô tả chi tiết bài toán đối sánh chuỗi cơ bản

Bài toán đối sánh chuỗi (string matching) là một vấn đề cơ bản trong khoa học máy tính. Nó liên quan đến việc tìm kiếm một hoặc nhiều chuỗi con trong một chuỗi lớn hơn. Bài toán này có ứng dụng trong nhiều lĩnh vực, bao gồm tìm kiếm văn bản, xử lý ngôn ngữ tự nhiên, và sinh học phân tử. Có nhiều thuật toán khác nhau để giải quyết bài toán đối sánh chuỗi, mỗi thuật toán có ưu và nhược điểm riêng. Việc lựa chọn thuật toán phù hợp phụ thuộc vào kích thước của chuỗi và mẫu, cũng như các yêu cầu về hiệu suất.

2.2. Các phương pháp tiếp cận chính trong đối sánh chuỗi

Phương pháp đơn giản nhất là lần lượt xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1.m] bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm. Dễ thấy độ phức tạp của thuật toán là O(n*m). Các thuật toán đối sánh thường sử dụng cơ chế cửa sổ trượt (một khung có kích thước bằng với kích thước của mẫu cần tìm) để so sánh các ký tự của mẫu trong cửa sổ với các ký tự trong văn bản.

2.3. So sánh các thuật toán đối sánh chuỗi Độ phức tạp ưu nhược điểm

Các thuật toán đối sánh được phân loại theo cách tiếp cận xây dựng thuật toán và số lượng mẫu. Việc đánh giá các thuật toán được thực hiện dựa trên dung lượng bộ nhớ sử dụng và tốc độ đối sánh. Các thuật toán đối sánh chuỗi có thể phân loại theo nhiều tiêu chí: Dựa trên số lượng mẫu, chúng ta có hai loại: Đối sánh đơn mẫu (single pattern) và đối sánh đa mẫu (multiple patterns).

III. Thuật Toán Đối Sánh Chính Xác Brute Force KMP Boyer Moore

Các kỹ thuật đối sánh chính xác cổ điển được xây dựng dựa trên số ký tự được so sánh. Sự khác biệt của các thuật toán là quá trình tính toán xác định số ký tự được dịch chuyển sau mỗi lần so sánh. Việc so sánh có thể được tiến hành từ trái qua phải hay từ phải qua trái, vị trí ký tự so sánh có thể là dựa trên tiền tố, hậu tố,. Các thuật toán đối sánh điển hình có thể kể đến gồm: Thuật toán Brute Force, Knuth-Morris-Pratt và Boyer-Moore. Mỗi thuật toán đều có ưu nhược điểm và phù hợp với các loại dữ liệu và ứng dụng khác nhau.

3.1. Phân tích thuật toán Brute Force Ưu điểm và hạn chế

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 [1] 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í.

3.2. So sánh hiệu năng của thuật toán KMP với Brute Force

Khắc phục hạn chế của thuật toán Brute Force, Knuth, Donald E. Morris, Jr và Vaughan R. Pratt [1] đã đề 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 đánh giá cao hơn về mặt hiệu năng so với Brute Force trong hầu hết các trường hợp.

3.3. Thuật toán Boyer Moore Ưu điểm về tốc độ tìm kiếm

Thuật toán Boyer-Moore (1977) [21] được xây dựng để kiểm tra các ký tự của mẫu từ phải sang trái. Khi phát hiện sự khác nhau sẽ tiến hành dịch mẫu sang phải văn bản một số vị trí với hai cách dịch chuyển mẫu là Good-suffix và Bad-character. Khoảng cách dịch chuyển Good-suffix gần giống trong thuật toán KMP, chúng ta dịch mẫu sang phải văn bản sao cho tại vị trí mới có đoạn u trên mẫu P khớp với đoạn u 13 trên văn bản T và ký tự c trên mẫu P ngay trước u phải khác a. Ta chọn đoạn dịch ngắn nhất. Nếu không có cả đoạn u trong P, ta chọn sao cho phần đuôi dài nhất của u xuất hiện ở đầu mẫu P. Thuật toán Boyer-Moore thường nhanh hơn các thuật toán khác trong thực tế.

IV. Đối Sánh Gần Đúng Giải Quyết Bài Toán Tìm Kiếm Xấp Xỉ

Trong nhiều ứng dụng thực tế, dữ liệu không hoàn toàn chính xác hoặc có sai sót. Do đó, các thuật toán đối sánh gần đúng trở nên cần thiết. Các thuật toán này cho phép tìm kiếm các mẫu tương tự, ngay cả khi có sự khác biệt nhỏ. Đối sánh gần đúng thường dựa trên các khái niệm như khoảng cách chỉnh sửa (edit distance) hoặc các độ đo tương tự (similarity measures). Kỹ thuật đối sánh gần đúng ngày càng được ứng dụng rộng rãi trong các lĩnh vực như sinh học, xử lý ngôn ngữ tự nhiên và tìm kiếm thông tin.

4.1. Định nghĩa và ứng dụng của đối sánh gần đúng

Các thuật toán đối sánh xấp xỉ chỉ đánh giá sự tương đồng của mẫu P so với mẫu T dựa trên một hàm đo khoảng cách nào đó. Đa số các thuật toán đối sánh không chính xác sử dụng khoảng cách Hamming hay khoảng cách Levenshtein với k vị trí khác biệt được thiết lập trước [2]. Đối sánh gần đúng cho phép tìm kiếm các kết quả phù hợp nhất, ngay cả khi có lỗi chính tả, biến thể ngôn ngữ hoặc các sai sót khác. Điều này rất quan trọng trong các ứng dụng thực tế.

4.2. Các độ đo khoảng cách phổ biến Hamming Levenshtein

Khoảng cách Hamming đo số lượng vị trí mà hai chuỗi có cùng độ dài khác nhau. Khoảng cách Levenshtein, hay còn gọi là khoảng cách chỉnh sửa, đo số lượng các phép chèn, xóa và thay thế cần thiết để biến một chuỗi thành một chuỗi khác. Cả hai độ đo này đều được sử dụng rộng rãi trong các thuật toán đối sánh gần đúng để đánh giá mức độ tương tự giữa các chuỗi.

V. Ứng Dụng Đối Sánh Mẫu Tìm Phản Biện Phát Hiện Giả Mạo

Luận văn nghiên cứu áp dụng kỹ thuật đối sánh mẫu vào một số bài toán cụ thể: Bài toán tìm kiếm phản biện cho bài báo (bài toán tìm kiếm phản biện luận văn hay bài toán tìm kiếm sản phẩm trên web đều có cách làm tương tự) [7], bài toán phát hiện trang web giả mạo. Nhằm nâng cao hiệu quả của việc tiếp nhận, chọn lọc và phản biện, nội dung luận văn nghiên cứu thuật toán lựa chọn phản biện cho bài báo dựa trên thông tin đầu vào là danh sách các từ khóa về nhà khoa học và từ khóa bài báo để từ đó lựa chọn phản biện sao cho phù hợp về chuyên môn. Đề tài luận văn ”Nghiên cứu một số kỹ thuật đối sánh mẫu và ứng dụng trong bài toán tìm kiếm xấp xỉ” tập trung nghiên cứu và thực hiện 4 nội dung chính sau: 1. Nghiên cứu một số kỹ thuật đối sánh mẫu.

5.1. Tìm kiếm phản biện phù hợp dựa trên từ khóa chuyên môn

Đối với bài toán tìm kiếm phản biện cho bài báo, luận văn tập trung vào các công đoạn của quá trình hoạt động của tạp chí, từ khâu nhận bài, lựa chọn phản biện, biên tập và xuất bản. Nhằm nâng cao hiệu quả của việc tiếp nhận, chọn lọc và phản biện, nội dung luận văn nghiên cứu thuật toán lựa chọn phản biện cho bài báo dựa trên thông tin đầu vào là danh sách các từ khóa về nhà khoa học và từ khóa bài báo để từ đó lựa chọn phản biện sao cho phù hợp về chuyên môn.

5.2. Phát hiện trang web giả mạo bằng đối sánh cấu trúc DOM

Đối với bài toán phát hiện trang web giả mạo, các trang web giả mạo bắt trước các trang web hợp lệ đến mức tốt nhất có thể để người dùng tin tưởng và tiết lộ những thông tin nhạy cảm. Hầu hết các trang lừa đảo đều làm tốt việc tạo giao diện hợp lệ bằng cách sao chép, bố trí các trang, font, màu, logo và cả những thông tin bảo mật của trang hợp lệ. Để giải quyết vấn đề này, luận văn tiếp cận theo phương pháp đối sánh cấu trúc DOM dưới dạng mô hình dữ liệu cây, theo kỹ thuật này nếu hai trang web có cấu trúc giống nhau thì thuộc diện nghi ngờ.

VI. Kết Luận Kỹ Thuật Đối Sánh Mẫu và Hướng Phát Triển

Tóm lại, kỹ thuật đối sánh mẫu là một công cụ mạnh mẽ với nhiều ứng dụng trong thực tế. Việc nghiên cứu và phát triển các thuật toán đối sánh mẫu hiệu quả hơn, đặc biệt là trong bối cảnh dữ liệu lớn, là một hướng đi quan trọng. Các nghiên cứu trong tương lai có thể tập trung vào việc kết hợp các kỹ thuật đối sánh mẫu với các phương pháp học máy để tạo ra các hệ thống thông minh hơn.

6.1. Tổng kết các kỹ thuật đối sánh mẫu đã nghiên cứu

Luận văn đã trình bày tổng quan về các kỹ thuật đối sánh mẫu chính, bao gồm cả đối sánh chính xác và đối sánh gần đúng. Các thuật toán như Brute Force, KMP, Boyer-Moore và các độ đo khoảng cách Hamming, Levenshtein đã được phân tích và so sánh. Ứng dụng của các kỹ thuật này trong bài toán tìm kiếm phản biện và phát hiện trang web giả mạo cũng đã được thảo luận.

6.2. Hướng phát triển tiềm năng của kỹ thuật đối sánh mẫu

Trong tương lai, có thể kết hợp các kỹ thuật đối sánh mẫu với các phương pháp học máy để cải thiện hiệu suất và độ chính xác. Việc phát triển các thuật toán đối sánh mẫu song song để xử lý dữ liệu lớn cũng là một hướng đi tiềm năng. Ngoài ra, việc nghiên cứu các ứng dụng mới của đối sánh mẫu trong các lĩnh vực như IoT, blockchain và trí tuệ nhân tạo cũng rất hứa hẹn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của công nghệ thông tin và sự gia tăng dữ liệu lưu trữ lên đến hàng Gigabyte, thậm chí Terabyte, việc tìm kiếm thông tin xấp xỉ trong cơ sở dữ liệu trở thành một thách thức lớn. Theo ước tính, các hệ thống quản trị cơ sở dữ liệu hiện nay vẫn còn hạn chế trong việc tìm kiếm thông tin gần đúng, đặc biệt khi sử dụng toán tử “Like” trong truy vấn SQL. Bài toán tìm kiếm xấp xỉ ngày càng được quan tâm do tính ứng dụng rộng rãi trong nhiều lĩnh vực như an ninh mạng, quảng cáo trực tuyến, xử lý văn bản, tài chính, y tế và sinh học. Mục tiêu của luận văn là nghiên cứu một số kỹ thuật đối sánh mẫu và áp dụng vào các bài toán cụ thể như lựa chọn phản biện cho bài báo khoa học và phát hiện trang web giả mạo. Phạm vi nghiên cứu tập trung vào các thuật toán đối sánh mẫu chính xác và xấp xỉ, áp dụng trong khoảng thời gian gần đây và thực hiện tại Trường Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái Nguyên. Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả tìm kiếm phản biện, đảm bảo tính khách quan trong quá trình phản biện khoa học, đồng thời góp phần phát hiện các trang web giả mạo nhằm bảo vệ người dùng và dữ liệu mạng. Các chỉ số hiệu quả như độ chính xác tìm kiếm, tốc độ xử lý và khả năng mở rộng của thuật toán được xem xét kỹ lưỡng trong nghiên cứu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai khung lý thuyết chính: kỹ thuật đối sánh mẫu (pattern matching) và đối sánh đồ thị (graph matching). Kỹ thuật đối sánh mẫu bao gồm các thuật toán đối sánh chuỗi chính xác như Brute Force, Knuth-Morris-Pratt (KMP), Boyer-Moore và các thuật toán đối sánh gần đúng dựa trên quy hoạch động sử dụng khoảng cách Levenshtein và Hamming. Các thuật toán này được phân loại theo số lượng mẫu (đơn mẫu, đa mẫu), thứ tự so sánh (từ trái sang phải, từ phải sang trái) và độ chính xác (chính xác, xấp xỉ). Đối với đối sánh đồ thị, luận văn nghiên cứu các phương pháp đối sánh đồ thị chính xác và không chính xác, bao gồm đẳng cấu đồ thị, đẳng cấu đồ thị con, đối sánh đồ thị thuộc tính và các thuật toán như SI-COBRA, giải thuật di truyền, và mạng neuron. Các khái niệm chuyên ngành như cây DOM (Document Object Model) được sử dụng để biểu diễn cấu trúc trang web dưới dạng cây, phục vụ cho bài toán phát hiện giả mạo trang web. Thuật toán Otomat hữu hạn mờ cũng được áp dụng để xác định độ gần ngữ nghĩa giữa các từ khóa, giúp nâng cao hiệu quả tìm kiếm phản biện.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm cơ sở dữ liệu các bài báo khoa học, danh sách phản biện và các trang web thực tế được thu thập tại Đại học Thái Nguyên. Cỡ mẫu nghiên cứu gồm hàng trăm bài báo và phản biện, cùng với hàng nghìn trang web để thử nghiệm phát hiện giả mạo. Phương pháp phân tích sử dụng kết hợp các thuật toán đối sánh mẫu chính xác và xấp xỉ, thuật toán quy hoạch động, mô hình Otomat hữu hạn mờ và các thuật toán đối sánh đồ thị. Quá trình nghiên cứu được thực hiện theo timeline gồm: (1) nghiên cứu và tổng hợp lý thuyết về các thuật toán đối sánh mẫu và đồ thị; (2) phát triển thuật toán lựa chọn phản biện dựa trên từ khóa và độ gần ngữ nghĩa; (3) xây dựng thuật toán phát hiện giả mạo trang web dựa trên đối sánh cấu trúc cây DOM; (4) thiết kế và triển khai ứng dụng hỗ trợ lựa chọn phản biện; (5) thử nghiệm và đánh giá hiệu quả thuật toán trên dữ liệu thực tế. Phương pháp chọn mẫu phản biện dựa trên các tiêu chí chuyên môn và khả năng phản biện, đảm bảo tính khách quan và hiệu quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả thuật toán lựa chọn phản biện dựa trên từ khóa và độ tương tự: Thuật toán Kalmukov cho thấy khả năng phân loại phản biện phù hợp với bài báo dựa trên hàm đo độ tương tự SF(Pi,Rj) đạt giá trị trong khoảng [0,1]. Ví dụ, trong một hội nghị với tập từ khóa KU gồm 9 từ, bài báo có từ khóa {A, C, F} được phân cho phản biện có độ tương tự cao nhất 0.67, tiết kiệm tài nguyên phản biện và đảm bảo phân phối đều. Tỷ lệ phân bổ bài báo cho phản biện được cân bằng theo công thức Noppr= ceil((Nop * Norpp) / Nor).

2. Thuật toán lựa chọn phản biện CMACRA và xấp xỉ 1/3: Thuật toán Greedy và quy hoạch nguyên tuyến tính giải quyết bài toán lựa chọn phản biện với các ràng buộc về số lượng bài báo và phản biện, đồng thời tối đa hóa sự bao phủ chủ đề. Thuật toán xấp xỉ 1/3 đảm bảo tính khách quan khi bổ sung ràng buộc COI, giúp giảm thiểu xung đột lợi ích trong quá trình phản biện.

3. Độ gần ngữ nghĩa và thuật toán Otomat hữu hạn mờ: Phương pháp xác định độ gần ngữ nghĩa giữa từ khóa bài báo và phản biện sử dụng hàm mờ µ(P,T) cho kết quả chính xác hơn so với khoảng cách Edit truyền thống, đặc biệt khi thứ tự từ thay đổi. Thuật toán Otomat hữu hạn mờ giảm đáng kể thời gian tính toán, chỉ còn O(n) so với O(m(m+1)/2) của phương pháp truyền thống.

4. Phát hiện giả mạo trang web dựa trên đối sánh đồ thị và cây DOM: Việc biểu diễn trang web dưới dạng cây DOM và áp dụng thuật toán đối sánh đồ thị giúp phát hiện các trang web giả mạo có cấu trúc tương tự trang hợp lệ với độ chính xác cao. Thuật toán so sánh các đồ thị con trích xuất từ DOM-Tree cho phép phát hiện các trang giả mạo dù có sự thay đổi nhỏ trong cấu trúc.

Thảo luận kết quả

Nguyên nhân của các phát hiện trên xuất phát từ việc áp dụng linh hoạt các kỹ thuật đối sánh mẫu và đồ thị phù hợp với đặc thù từng bài toán. So với các nghiên cứu trước đây, luận văn đã mở rộng phạm vi ứng dụng kỹ thuật đối sánh mẫu xấp xỉ và Otomat hữu hạn mờ, đồng thời tích hợp các ràng buộc thực tiễn như COI trong lựa chọn phản biện, nâng cao tính khách quan và hiệu quả. Việc sử dụng cây DOM trong phát hiện giả mạo trang web là một hướng tiếp cận mới, tận dụng cấu trúc dữ liệu cây để nhận dạng các mẫu giả mạo phức tạp. Các kết quả có thể được trình bày qua biểu đồ so sánh độ chính xác và thời gian xử lý của các thuật toán, bảng phân phối số lượng bài báo cho phản biện và biểu đồ thể hiện mức độ bao phủ chủ đề trong lựa chọn phản biện. Ý nghĩa của nghiên cứu không chỉ nâng cao hiệu quả tìm kiếm xấp xỉ mà còn góp phần bảo vệ an toàn thông tin và nâng cao chất lượng phản biện khoa học.

Đề xuất và khuyến nghị

1. Triển khai hệ thống lựa chọn phản biện tự động: Áp dụng thuật toán lựa chọn phản biện dựa trên độ tương tự từ khóa và Otomat hữu hạn mờ vào hệ thống quản lý tạp chí khoa học trong vòng 6 tháng tới, do Ban biên tập và phòng CNTT thực hiện nhằm nâng cao hiệu quả và tính khách quan trong quá trình phản biện.

2. Phát triển công cụ phát hiện giả mạo trang web dựa trên cây DOM: Xây dựng và tích hợp module phát hiện giả mạo vào hệ thống bảo mật mạng của các tổ chức trong 12 tháng, do bộ phận an ninh mạng và phát triển phần mềm đảm nhiệm, nhằm giảm thiểu rủi ro từ các trang web lừa đảo.

3. Đào tạo và nâng cao nhận thức về kỹ thuật đối sánh mẫu và đồ thị: Tổ chức các khóa đào tạo chuyên sâu cho cán bộ quản lý tạp chí, nhà nghiên cứu và kỹ sư CNTT trong 3 tháng, giúp họ hiểu và vận dụng hiệu quả các thuật toán trong công việc.

4. Mở rộng nghiên cứu và ứng dụng các thuật toán đối sánh mẫu xấp xỉ: Khuyến khích các nhóm nghiên cứu tiếp tục phát triển các thuật toán mới, tối ưu hóa tốc độ và độ chính xác, đồng thời mở rộng ứng dụng sang các lĩnh vực khác như y tế, tài chính trong vòng 2 năm tới.

Đối tượng nên tham khảo luận văn

1. Các nhà quản lý và biên tập viên tạp chí khoa học: Giúp họ hiểu và áp dụng các thuật toán lựa chọn phản biện tự động, nâng cao chất lượng và tính khách quan trong quá trình phản biện bài báo.

2. Nhà nghiên cứu và sinh viên ngành Khoa học máy tính, Công nghệ thông tin: Cung cấp kiến thức chuyên sâu về kỹ thuật đối sánh mẫu, đối sánh đồ thị và ứng dụng thực tiễn trong tìm kiếm xấp xỉ và an ninh mạng.

3. Chuyên gia an ninh mạng và phát triển phần mềm bảo mật: Hỗ trợ trong việc phát triển các công cụ phát hiện trang web giả mạo dựa trên cấu trúc cây DOM và thuật toán đối sánh đồ thị.

4. Doanh nghiệp và tổ chức sử dụng hệ thống quản lý dữ liệu lớn: Giúp tối ưu hóa công cụ tìm kiếm và phân tích dữ liệu, nâng cao hiệu quả khai thác thông tin trong các hệ thống lưu trữ lớn.

Câu hỏi thường gặp

1. Kỹ thuật đối sánh mẫu là gì và tại sao quan trọng?
   Kỹ thuật đối sánh mẫu là phương pháp tìm kiếm và so sánh các chuỗi ký tự hoặc mẫu trong dữ liệu lớn. Nó quan trọng vì giúp tìm kiếm thông tin gần đúng, ứng dụng trong xử lý văn bản, an ninh mạng và nhiều lĩnh vực khác, nâng cao hiệu quả truy xuất dữ liệu.

2. Thuật toán lựa chọn phản biện dựa trên từ khóa hoạt động như thế nào?
   Thuật toán tính độ tương tự giữa từ khóa bài báo và phản biện, sau đó phân bổ bài báo cho phản biện có độ tương tự cao nhất, đồng thời đảm bảo giới hạn số lượng bài báo mỗi phản biện có thể xử lý, giúp phân phối công việc hợp lý và khách quan.

3. Phương pháp Otomat hữu hạn mờ giúp gì trong tìm kiếm xấp xỉ?
   Otomat hữu hạn mờ cho phép xác định độ gần ngữ nghĩa giữa các chuỗi ký tự, xử lý tốt các trường hợp thay đổi thứ tự từ hoặc sai lệch nhỏ, giảm thời gian tính toán và nâng cao độ chính xác so với phương pháp truyền thống.

4. Làm thế nào để phát hiện trang web giả mạo bằng kỹ thuật đối sánh đồ thị?
   Trang web được biểu diễn dưới dạng cây DOM, sau đó so sánh cấu trúc đồ thị của trang web nghi ngờ với trang web hợp lệ. Nếu cấu trúc tương tự vượt ngưỡng cho phép, trang web có thể bị nghi ngờ là giả mạo, giúp phát hiện kịp thời các trang lừa đảo.

5. Ứng dụng thực tế của nghiên cứu này trong quản lý tạp chí khoa học là gì?
   Nghiên cứu giúp xây dựng hệ thống tự động lựa chọn phản biện phù hợp, giảm thiểu sai sót và xung đột lợi ích, nâng cao chất lượng phản biện và hiệu quả quản lý quy trình xuất bản, đồng thời tiết kiệm thời gian và nguồn lực.

Kết luận

• Luận văn đã nghiên cứu và phát triển các kỹ thuật đối sánh mẫu chính xác và xấp xỉ, áp dụng hiệu quả trong bài toán lựa chọn phản biện và phát hiện giả mạo trang web.
• Thuật toán lựa chọn phản biện dựa trên từ khóa và Otomat hữu hạn mờ giúp nâng cao độ chính xác và giảm thời gian tính toán.
• Phương pháp đối sánh đồ thị và cây DOM được áp dụng thành công trong phát hiện trang web giả mạo, góp phần bảo vệ an toàn thông tin.
• Ứng dụng xây dựng hỗ trợ lựa chọn phản biện cho Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên đã được triển khai, chứng minh tính khả thi của nghiên cứu.
• Các bước tiếp theo bao gồm mở rộng ứng dụng thuật toán vào các lĩnh vực khác, tối ưu hóa hiệu năng và đào tạo nhân lực sử dụng công nghệ mới.

Mời quý độc giả và các nhà nghiên cứu quan tâm tiếp cận và ứng dụng các kết quả nghiên cứu nhằm nâng cao hiệu quả công tác quản lý và bảo mật thông tin trong môi trường số hiện nay.

Trích đoạn nội dung tài liệu

Chương 1 là tổng quan kỹ thuật đối sánh mẫu, Chương 2 trình bày một số bài toán tìm kiếm xấp xỉ và ứng dụng kỹ thuật đối sánh mẫu cho từng bài toán: Hệ thống lựa chọn phản biện cho Hội nghị, tạp chí và thuật toán lựa chọn phản biện dựa trên các phương pháp tìm kiếm xấp xỉ; Bài toán phát hiện trang web giả mạo dựa trên đối sánh đồ thị. Chương 3 là xây dựng ứng dụng hỗ trợ lựa chọn phản biện bài báo cho Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên. TỔNG QUAN KỸ THUẬT ĐỐI SÁNH MẪU Đối sánh mẫu hay còn gọi là so khớp mẫu và tìm kiếm mẫu là bài toán quan trọng trong lĩnh vực tìm kiếm trong cơ sở dữ liệu, xử lý văn bản nói riêng và ứng dụng trong CNTT truyền thông nói chung. Bài toán được ứng dụng trong nhiều lĩnh vực khác nhau.

Chương này này tập trung vào một số kỹ thuật đối sánh mẫu được dùng cho hai bài toán, bao gồm bài toán tìm kiếm phản biện và bài toán phát hiện trang web giả mạo. Đối sánh chuỗi 1. Bài toán đối sánh chuỗi Đối sánh chuỗi là việc so sánh một chuỗi hoặc nhiều chuỗi với văn bản để tìm vị trí và số lần xuất hiện của chuỗi đó trong văn bản. Bài toán đối sánh chuỗi được mô tả như sau [11]: Cho một bảng chữ cái Σ là một tập hữu hạn các ký tự, một mẫu P (P [1.m]) độ dài m và một chuỗi ký tự T (T [1.

Bài toán đặt ra là cần tìm các vị trí xuất hiện của P trong T hoặc P có khớp với một chuỗi con của T hay không? Gọi Σ là một tập hữu hạn các ký tự. Thông thường, các ký tự của cả mẫu tìm kiếm và đoạn văn bản gốc đều nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là bảng chữ cái tiếng Anh từ A đến Z thông thường, cũng có thể là một tập nhị phân chỉ gồm hai phần tử 0 và 1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ = {A,C,G,T}). Phương pháp đầu tiên và đơn giản nhất có thể nghĩ đến ngay là lần lượt xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1.m] bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm.

Dễ thấy độ phức tạp của thuật toán là O(n*m). Các thuật toán đối sánh thường sử dụng cơ chế cửa sổ trượt (một khung có kích thước bằng với kích thước của mẫu cần tìm) để so sánh các ký tự của mẫu trong cửa sổ với các ký tự trong văn bản. Tất cả các thuật toán đối sánh chuỗi đều có hai giai đoạn là: tiền xử lý và tìm kiếm. Việc đánh giá các thuật toán được thực hiện dựa trên dung lượng bộ nhớ sử dụng và tốc độ đối sánh.

Các thuật toán đối sánh được phân loại theo cách tiếp cận xây dựng thuật toán và số lượng mẫu. Các thuật toán đối sánh chuỗi có thể phân loại theo nhiều tiêu chí: Dựa trên số lượng mẫu, chúng ta có hai loại: Đối sánh đơn mẫu (single pattern) và đối sánh đa mẫu (multiple patterns). Các thuật toán đối sánh đơn mẫu chỉ tiến hành 9 so sánh lần lượt từng mẫu P trên văn bản T, còn đối sánh đa mẫu cho phép so sánh cùng lúc nhiều mẫu Pi (i=1. Các thuật toán Đối sánh đa mẫu thường là những cải tiến của đối sánh đơn mẫu nhằm nâng cao hiệu quả đối sánh.

Dựa trên cơ sở thứ tự so sánh: thuật toán đối sánh chuỗi có thể được thực hiện theo các thứ tự sau: từ trái sang phải, từ phải sang trái, so sánh tại vị trí cụ thể và so sánh không theo thứ tự nhất định. Dựa trên độ chính xác của kết quả so khớp: các thuật toán đối sánh được chia thành hai loại: Đối sánh chính xác (Extract String Matching) và đối sánh gần đúng (Approximate String Matching). Đối sánh chính xác là khẳng định mẫu P có xuất hiện ở trong chuỗi T hay không? Còn thuật toán đối sánh xấp xỉ chỉ đánh giá sự tương đồng của mẫu P so với mẫu T dựa trên một hàm đo khoảng cách nào đó. Đa số các thuật toán đối sánh không chính xác sử dụng khoảng cách Hamming hay khoảng cách Levenshtein với k vị trí khác biệt được thiết lập trước [2].

Dựa trên cơ sở thiết kế thuật toán: Các thuật toán đối sánh được chia thành ba loại: Đối sánh dựa trên tiền tố (prefix), đối sánh dựa trên hậu tố (suffix) và đối sánh dựa trên các nhân tố (factor). Đối sánh dựa trên tiền tố Quá trình đối sánh của thuật toán dựa trên tiền tố được thực hiện bằng cách tìm kiếm từ đầu cửa sổ trượt, tất cả các ký tự trong văn bản T đều được đọc và kiểm tra, nếu không khớp thì dịch chuyển sang ký tự tiếp theo. Đây là chiến lược đơn giản nhất nhưng số lượng phép so sánh lớn nên tốc độ thực hiện chậm (xem Hình 1. Thuật toán đối sánh dựa trên hậu tố thực hiện bằng cách tìm kiếm từ cuối cửa sổ trượt, chúng ta không đọc tất cả các ký tự liên tiếp trong văn bản T mà dịch hay bỏ qua các ký tự dựa vào kết quả so sánh các ký tự ở cuối cửa sổ (xem Hình 1.

Đây là cơ sở để giảm số lượng phép so sánh và giảm độ phức tạp của thuật toán. Đối sánh hậu tố Thuật toán đối sánh dựa trên thừa số thực hiện bằng cách tìm kiếm từ cuối cửa sổ trượt, chúng ta không đọc tất cả các ký tự liên tiếp trong văn bản T mà so sánh từng ký tự đặc biệt để đoán nhận tập nhân tố (các mẫu con) của mẫu P ban đầu (Hình 1. Đối sánh dựa trên các nhân tố Để đánh giá hiệu năng của thuật toán đối sánh chuỗi, chúng ta có thể dựa trên những tiêu chí sau: Số lần tìm kiếm, duyệt trên mẫu và văn bản; Độ phức tạp thời gian; Tiêu chuẩn được lựa chọn để đối sánh; Số mẫu được đối sánh; Kỹ thuật biểu diễn mẫu. Các thuật toán đối sánh chính xác cổ điển Các kỹ thuật đối sánh chính xác cổ điển được xây dựng dựa trên số ký tự được so sánh.

Sự khác biệt của các thuật toán là quá trình tính toán xác định số ký tự được dịch chuyển sau mỗi lần so sánh. Việc so sánh có thể được tiến hành từ trái qua phải hay từ phải qua trái, vị trí ký tự so sánh có thể là dựa trên tiền tố, hậu tố,. Các thuật toán đối sánh điển hình có thể kể đến gồm: 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 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 [1] với độ phức tạp của thuật toán là 11 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 [1] đã đề 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: 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 ; 12 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). Thuật toán Boyer-Moore (1977) [21] được xây dựng để kiểm tra các ký tự của mẫu từ phải sang trái. Khi phát hiện sự khác nhau sẽ tiến hành dịch mẫu sang phải văn bản một số vị trí với hai cách dịch chuyển mẫu là Good-suffix và Bad-character.

Khoảng cách dịch chuyển Good-suffix gần giống trong thuật toán KMP, chúng ta dịch mẫu sang phải văn bản sao cho tại vị trí mới có đoạn u trên mẫu P khớp với đoạn u 13 trên văn bản T và ký tự c trên mẫu P ngay trước u phải khác a. Ta chọn đoạn dịch ngắn nhất. Nếu không có cả đoạn u trong P, ta chọn sao cho phần đuôi dài nhất của u xuất hiện ở đầu mẫu P.