Thuật toán Wu-Manber trong đối sánh đa mẫu

Trong bài viết này, ta sẽ cùng tìm hiểu về thuật toán Wu-Manber trong đối sánh đa mẫu. Ta sẽ cùng tìm hiểu về khái niệm và các kiến thức liên quan cho thuật toán này.

Thuật toán Wu-Manber

Giả sử sử là tập hợp các mẫu, là các chuỗi ký tự từ tập hợp ký tự alphabet cố định . Cho là một đoạn văn bản lớn, bao gồm các ký tự từ tập . Bài toán đặt ra là tìm ra tất cả sự xuất hiện của các mẫu trong P nằm ở trong T.

Bài toán đối sánh đa mẫu đã có được nhiều ứng dụng. Nó được sử dụng trong việc lọc dữ liệu (còn gọi là khai thác dữ liệu) để tìm các mẫu đã chọn, ví dụ, từ một luồng nguồn cấp tin tức, nó được sử dụng trong các ứng dụng bảo mật để phát hiện một số từ khóa đáng ngờ. Nó được sử dụng để tìm kiếm các mẫu có thể có một số dạng chẳng hạn như ngày tháng.

Cách tiếp cận đối sánh đa mẫu của Wu-manber dựa trên ý tưởng của Boyer và Moore.

Khái quát về thuật toán Wu-Manber

Ý tưởng của thuật toán Boyer-Moore như sau. Giả sử mẫu cần tìm có độ dài là . Ta sẽ thực hiện so sánh ký tự cuối cùng của mẫu với , ký tự thứ của văn bản. Nếu không có sự trùng khớp, ta sẽ xác định sự xuất hiện ở bên phải của trong mẫu và dịch chuyển tương ứng. Ý tưởng này cũng được vận dụng vào trong thuật toán của Wu-manber.

1. Bước tiền xử lý

Có 3 bảng được xây dựng trong bước này bao gồm SHIFT, HASH và PREFIX. Bảng SHIFT được sử dụng để xác định số ký tự trong đoạn văn bản sẽ được dịch chuyển hay là bỏ qua khi đoạn văn bản được quét. Bảng Hash và PREFIX được sử dụng khi giá trị dịch chuyển là 0. Chúng được sử dụng để xác định mẫu nào là ứng viên cho việc đối sánh và xác minh kết quả trùng khớp.

Điều đầu tiên chúng ta tính độ dài tối thiểu của một mẫu, là m và chỉ xem xét m ký tự đầu tiên của mỗi mẫu. Nói cách khác, chúng ta sẽ áp đặt một yêu cầu rằng tất cả các mẫu phải có cùng độ dài. Và điều này là rất quan trọng đối với tính hiệu quả của thuật toán. Lưu ý rằng nếu một trong các mẫu rất ngắn, chẳng hạn như độ dài là 2, thì chúng ta không bao giờ có thể dịch chuyển nhiều hơn 2, vì vậy việc có các mẫu ngắn sẽ làm cho cách tiếp cận này trở nên kém hiệu quả hơn

Thay vì xem xét các ký tự trong từng đoạn văn bản, chúng ta xem xét chúng trong các khối có kích thước là B. Gọi M là tổng kích thước của tất cả các mẫu, , và gọi là kích thước của bảng chữ cái. Giá trị tốt của B theo thứ tự là . Trong thực tế, chúng ta sẽ sử dụng hoặc . Bảng SHIFT đóng vai trò giống như trong thuật toán Boyer-Moore, ngoại trừ việc nó xác định sự thay đổi dựa trên B ký tự cuối cùng thay vì chỉ một ký tự.

Ví dụ, nếu chuỗi có B ký tự trong đoạn văn bản không xuất hiện trong bất kỳ mẫu nào, thì chúng ta có thể dịch chuyển theo . Bây giờ, giả sử rằng bảng SHIFT chứa một mục đầu vào cho mỗi chuỗi có thể có kích thước là B, vì vậy kích thước của nó là . Mỗi chuỗi có kích thước là B được ánh xạ với một số nguyên được sử dụng làm chỉ số cho bảng SHIFT bằng cách sử dụng hàm băm. Các giá trị trong bảng SHIFT sẽ xác định khoảng cách mà ta có thể bỏ qua khi ta quét (duyệt) qua đoạn văn bản. Giả sử là B ký tự trong đoạn văn bản mà ta đang quét, và giả sử X được ánh xạ tới đầu vào thứ i của bảng SHIFT. Sẽ có hai trường hợp như sau:

1. X không xuất hiện trong bất kỳ mẫu nào của P.
   • Trong trường hợp này, chúng ta có thể dịch chuyển hay bỏ qua ký tự trong văn bản. Bất kỳ sự dịch chuyển nào nhỏ hơn sẽ đặt B các ký tự cuối cùng của văn bản gần hơn so với chuỗi con của một trong các mẫu mà không khớp. Chúng ta sẽ lưu trữ trong SHIFT[i] là .

2. X xuất hiện trong một vài mẫu.
   • Trong trường hợp này, chúng ta sẽ tìm thấy sự xuất hiện ngoài cùng bên phải của X trong bất kỳ mẫu nào; giả sử rằng X kết thúc ở vị trí q của Pj và X không kết thúc ở bất kỳ vị trí nào lớn hơn q trong bất kỳ mẫu nào khác. Chúng ta sẽ lưu trữ trong SHIFT[i].

Để tính các giá trị của bảng SHIFT, ta sẽ xem xét từng mẫu . Ta sẽ ánh xạ từng chuỗi của con của có kích thước là vào trong bảng SHIFT và đặt giá trị tương ứng với giá trị nhỏ nhất của giá trị hiện tại (giá trị ban đầu cho tất cả là ) và (số lượng lần dịch chuyển cần thiết để lấy được chuỗi con).

Các giá trị trong bảng SHIFT là các giá trị an toàn lớn nhất có thể cho các lần dịch chuyển. Thay thế bất kỳ mục nào trong bảng SHIFT bằng một giá trị nhỏ hơn sẽ làm bớt đi sự dịch chuyển và sẽ mất nhiều thời gian hơn, nhưng vẫn đảm bảo an toàn, không có kết quả trùng khớp nào bị bỏ qua. Vì vậy, chúng ta có thể sử dụng một bảng nén cho SHIFT, ánh xạ một số chuỗi khác nhau vào cùng một mục, miễn là chúng ta đặt số lần dịch chuyển tối thiểu của tất cả làm giá trị. Khi số lượng mẫu ít, chúng ta chọn B = 2 và sử dụng bảng chính xác cho SHIFT, nếu không, chúng ta chọn B = 3 và sử dụng bảng nén cho SHIFT. Trong cả hai trường hợp, thuật toán không biết liệu bảng SHIFT có chính xác hay không.

Miễn là giá trị dịch chuyển lớn hơn 0, chúng ta có thể dịch chuyển một cách an toàn và tiếp tục quét. Mặt khác, một chuỗi con hiện tại trong đoạn văn bản có thể trùng khớp một vài mẫu trong danh sách mẫu.

Để tránh so sánh chuỗi con với mọi mẫu trong danh sách mẫu, chúng ta sử dụng kỹ thuật băm để giảm thiểu số lượng mẫu được so sánh. Chúng ta đã tính toán một ánh xạ của các ký tự B thành một số nguyên được sử dụng làm chỉ số cho bảng SHIFT. Chúng ta sử dụng cùng một số nguyên để lập chỉ số vào một bảng khác, được gọi là HASH. Mục đầu vào thứ i của bảng Hash, Hash[i], chứa một con trỏ tới danh scahs các mẫu mà có B các ký tự cuối cùng băm thành i. Bảng Hash sẽ khá thưa, bởi nó chỉ giữ các mẫu, trong khi đó bảng SHIFT giữ tất cả các chuỗi có thể có với kích thước B. Điều này gây ra tốn kém cho bộ nhớ, nhưng nó cho phép ta sử dụng lại hàm băm, tiết kiệm được nhiều thời gian. Gọi h là giá trị băm của hậu tố hiện tại trong đoạn văn bản và giả sử SHIFT[h]=0. Giá trị của Hash[h] là một con trỏ p trỏ vào trong hai bảng khác nhau tại cùng một thời điểm. Ta giữ một danh sách các con trỏ tới các mẫu này, PAT_POINT, được sắp xếp bởi các giá trị băm của B các ký tự cuối cùng của mỗi mẫu. Con trỏ p trỏ tới đầu danh sách các mẫu mà giá trị băm là h. Để tìm phần cuối của danh sách, ta sẽ tăng con trỏ này cho tới khi nó bằng giá trị trong Hash[h+1]. Ví dụ, nếu SHIFT[h] khác 0, thì Hash[h] = Hash[h+1]. Ngoài ra, ta sẽ giữ một bảng gọi là PREFIX.

Các đoạn văn bản ngôn ngữ tự nhiên không phải là ngẫu nhiên. Ví dụ, các hậu tố như ion hay ing là rất thông dụng trong các đoạn văn bản tiếng anh. Các hậu tố này sẽ không chỉ xuất hiện trong các đoạn văn bản mà còn trong một vài các mẫu. Chúng sẽ gây ra xung đột trong bảng Hash. Tất cả các mẫu có cùng hậu tố sẽ được ánh xạ tới cùng một mục đầu vào trong bảng HASH. Khi chúng ta gặp một hậu tố như vậy trong văn bản, chúng ta sẽ thấy rằng giá trị SHIFT của nó là 0. Chúng ta sẽ phải kiểm tra riêng tất cả các mẫu có hậu tố này để xem chúng có khớp với văn bản hay không. Để tăng tốc quá trình này, chúng ta sẽ đưa ra một bảng khác, được gọi là PREFIX.

Ngoài việc ánh xạ các ký tự B cuối cùng của tất cả các mẫu, chúng ta cũng ánh xạ các ký tự B đầu tiên của tất cả các mẫu vào bảng PREFIX. Khi chúng ta tìm thấy giá trị SHIFT bằng 0 và chúng ta chuyển đến bảng HASH để xác định xem có khớp hay không, chúng ta kiểm tra các giá trị trong bảng PREFIX.

Bảng HASH không chỉ chứa, đối với mỗi hậu tố, danh sách tất cả các mẫu có hậu tố này, mà còn chứa (giá trị băm của) tiền tố của chúng. Chúng ta sẽ tính toán tiền tố tương ứng trong văn bản (bằng cách dịch chuyển m – B′ ký tự sang trái) và sử dụng nó để lọc các mẫu có hậu tố giống nhau nhưng tiền tố khác nhau. Đây là một phương pháp lọc hiệu quả vì rất ít khi có các mẫu khác nhau mà có cùng một tiền tố và cùng một hậu tố.

2. Bước quét

Vòng lặp chính của thuật toán Wu-Manber bao gồm các bước sau:

1. Tính giá trị băm h dựa trên B ký tự hiện tại từ đoạn văn bản (bắt đầu bằng )
2. Kiểm tra giá trị của SHIFT[h]: Nếu nó lớn hơn 0, bỏ qua đoạn văn bản và quay trở về 1, nếu không thì đi tới bước 3.
3. Tính toán giá trị băm của tiền tố của đoạn văn bản (bắt đầu từ m ký tự bên trái của vị trí hiện tại), gọi nó là text_prefix
4. Kiểm tra cho từng p, nếu . Khi chúng bằng nhau, kiểm tra mẫu thực (được cho bởi PAT_POINT[p]) với đoạn văn bản một cách trực tiếp.

Trên đây là khái niệm và ví dụ cơ bản về thuật toán Wu-Manber. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người!