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.
