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

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n Wu-Manber trong đối s&aacute;nh đa mẫu. Ta sẽ c&ugrave;ng t&igrave;m hiểu về kh&aacute;i niệm v&agrave; c&aacute;c kiến thức li&ecirc;n quan cho thuật to&aacute;n n&agrave;y.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Giả sử sử $P = p_1, p_2, ... , p_k$ l&agrave; tập hợp c&aacute;c mẫu, l&agrave; c&aacute;c chuỗi k&yacute; tự từ tập hợp k&yacute; tự alphabet cố định $\sum$. Cho $T = t_1, t_2, ..., t_N$ l&agrave; một đoạn văn bản lớn, bao gồm c&aacute;c k&yacute; tự từ tập $\sum$. B&agrave;i to&aacute;n đặt ra l&agrave; t&igrave;m ra tất cả sự xuất hiện của c&aacute;c mẫu trong P nằm ở trong T.</p> <p style="text-align: justify;">B&agrave;i to&aacute;n đối s&aacute;nh đa mẫu đ&atilde; c&oacute; được nhiều ứng dụng. N&oacute; được sử dụng trong việc lọc dữ liệu (c&ograve;n gọi l&agrave; khai th&aacute;c dữ liệu) để t&igrave;m c&aacute;c mẫu đ&atilde; chọn, v&iacute; dụ, từ một luồng nguồn cấp tin tức, n&oacute; được sử dụng trong c&aacute;c ứng dụng bảo mật để ph&aacute;t hiện một số từ kh&oacute;a đ&aacute;ng ngờ. N&oacute; được sử dụng để t&igrave;m kiếm c&aacute;c mẫu c&oacute; thể c&oacute; một số dạng chẳng hạn như ng&agrave;y th&aacute;ng.</p> <p style="text-align: justify;">C&aacute;ch tiếp cận đối s&aacute;nh đa mẫu của Wu-manber dựa tr&ecirc;n &yacute; tưởng của Boyer v&agrave; Moore.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. Kh&aacute;i qu&aacute;t về thuật to&aacute;n Wu-Manber</h2> <p style="text-align: justify;">&Yacute; tưởng của thuật to&aacute;n Boyer-Moore như sau. Giả sử mẫu cần t&igrave;m c&oacute; độ d&agrave;i l&agrave; $m$. Ta sẽ thực hiện so s&aacute;nh k&yacute; tự cuối c&ugrave;ng của mẫu với $t_m$, k&yacute; tự thứ $m$ của văn bản. Nếu kh&ocirc;ng c&oacute; sự tr&ugrave;ng khớp, ta sẽ x&aacute;c định sự xuất hiện ở b&ecirc;n phải của $t_m$&nbsp;trong mẫu v&agrave; dịch chuyển tương ứng. &Yacute; tưởng n&agrave;y cũng được vận dụng v&agrave;o trong thuật to&aacute;n của Wu-manber.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">1. Bước tiền xử l&yacute;</h3> <p style="text-align: justify;">C&oacute; 3 bảng được x&acirc;y dựng trong bước n&agrave;y bao gồm&nbsp;<span id="urvanov-syntax-highlighter-6108c491c108f574256616" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">SHIFT</span></span></span>,&nbsp;<span id="urvanov-syntax-highlighter-6108c491c1097558749211" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">HASH</span></span></span>&nbsp;v&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6108c491c109a833763339" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">PREFIX</span></span></span>. Bảng&nbsp;<span id="urvanov-syntax-highlighter-6108c491c109b579772893" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">SHIFT</span></span></span>&nbsp;được sử dụng để x&aacute;c định số k&yacute; tự trong đoạn văn bản sẽ được dịch chuyển hay l&agrave; bỏ qua khi đoạn văn bản được qu&eacute;t. Bảng&nbsp;<span id="urvanov-syntax-highlighter-6108c491c109d901517701" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">Hash</span></span></span>&nbsp;v&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6108c491c109e001065664" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">PREFIX</span></span></span>&nbsp;được sử dụng khi gi&aacute; trị dịch chuyển l&agrave; 0. Ch&uacute;ng được sử dụng để x&aacute;c định mẫu n&agrave;o l&agrave; ứng vi&ecirc;n cho việc đối s&aacute;nh v&agrave; x&aacute;c minh kết quả tr&ugrave;ng khớp.</p> <p style="text-align: justify;">Điều đầu ti&ecirc;n ch&uacute;ng ta t&iacute;nh độ d&agrave;i tối thiểu của một mẫu, l&agrave; m v&agrave; chỉ xem x&eacute;t m k&yacute; tự đầu ti&ecirc;n của mỗi mẫu. N&oacute;i c&aacute;ch kh&aacute;c, ch&uacute;ng ta sẽ &aacute;p đặt một y&ecirc;u cầu rằng tất cả c&aacute;c mẫu phải c&oacute; c&ugrave;ng độ d&agrave;i. V&agrave; điều n&agrave;y l&agrave; rất quan trọng đối với t&iacute;nh hiệu quả của thuật to&aacute;n. Lưu &yacute; rằng nếu một trong c&aacute;c mẫu rất ngắn, chẳng hạn như độ d&agrave;i l&agrave; 2, th&igrave; ch&uacute;ng ta kh&ocirc;ng bao giờ c&oacute; thể dịch chuyển nhiều hơn 2, v&igrave; vậy việc c&oacute; c&aacute;c mẫu ngắn sẽ l&agrave;m cho c&aacute;ch tiếp cận n&agrave;y trở n&ecirc;n k&eacute;m hiệu quả hơn</p> <p style="text-align: justify;">Thay v&igrave; xem x&eacute;t c&aacute;c k&yacute; tự trong từng đoạn văn bản, ch&uacute;ng ta xem x&eacute;t ch&uacute;ng trong c&aacute;c khối c&oacute; k&iacute;ch thước l&agrave; B. Gọi M l&agrave; tổng k&iacute;ch thước của tất cả c&aacute;c mẫu, $M = k \times m$, v&agrave; gọi $c$ l&agrave; k&iacute;ch thước của bảng chữ c&aacute;i. Gi&aacute; trị tốt của B theo thứ tự l&agrave; $log_c(2) M$. Trong thực tế, ch&uacute;ng ta sẽ sử dụng $B = 2$ hoặc $B = 3$. Bảng SHIFT đ&oacute;ng vai tr&ograve; giống như trong thuật to&aacute;n Boyer-Moore, ngoại trừ việc n&oacute; x&aacute;c định sự thay đổi dựa tr&ecirc;n B k&yacute; tự cuối c&ugrave;ng thay v&igrave; chỉ một k&yacute; tự.</p> <p style="text-align: justify;">V&iacute; dụ, nếu chuỗi c&oacute; B k&yacute; tự trong đoạn văn bản kh&ocirc;ng xuất hiện trong bất kỳ mẫu n&agrave;o, th&igrave; ch&uacute;ng ta c&oacute; thể dịch chuyển theo $mB + 1$. B&acirc;y giờ, giả sử rằng bảng SHIFT chứa một mục đầu v&agrave;o cho mỗi chuỗi c&oacute; thể c&oacute; k&iacute;ch thước l&agrave; B, v&igrave; vậy k&iacute;ch thước của n&oacute; l&agrave; $|\sum|^B$. Mỗi chuỗi c&oacute; k&iacute;ch thước l&agrave; B được &aacute;nh xạ với một số nguy&ecirc;n được sử dụng l&agrave;m chỉ số cho bảng SHIFT bằng c&aacute;ch sử dụng h&agrave;m băm. C&aacute;c gi&aacute; trị trong bảng SHIFT sẽ x&aacute;c định khoảng c&aacute;ch m&agrave; ta c&oacute; thể bỏ qua khi ta qu&eacute;t (duyệt) qua đoạn văn bản. Giả sử $X = x_1, x_2, \cdots, x_B$&nbsp;l&agrave; B k&yacute; tự trong đoạn văn bản m&agrave; ta đang qu&eacute;t, v&agrave; giả sử X được &aacute;nh xạ tới đầu v&agrave;o thứ i của bảng SHIFT. Sẽ c&oacute; hai trường hợp như sau:</p> <ol style="text-align: justify;"> <li>X kh&ocirc;ng xuất hiện trong bất kỳ mẫu n&agrave;o của P. <ul> <li>Trong trường hợp n&agrave;y, ch&uacute;ng ta c&oacute; thể dịch chuyển hay bỏ qua $mB + 1$ k&yacute; tự trong văn bản. Bất kỳ sự dịch chuyển n&agrave;o nhỏ hơn sẽ đặt B c&aacute;c k&yacute; tự cuối c&ugrave;ng của văn bản gần hơn so với chuỗi con của một trong c&aacute;c mẫu m&agrave; kh&ocirc;ng khớp. Ch&uacute;ng ta sẽ lưu trữ trong SHIFT[i] l&agrave; $mB + 1$.</li> </ul> </li> </ol> <ol style="text-align: justify;" start="2"> <li>X xuất hiện trong một v&agrave;i mẫu. <ul> <li>Trong trường hợp n&agrave;y, ch&uacute;ng ta sẽ t&igrave;m thấy sự xuất hiện ngo&agrave;i c&ugrave;ng b&ecirc;n phải của X trong bất kỳ mẫu n&agrave;o; giả sử rằng X kết th&uacute;c ở vị tr&iacute; q của Pj v&agrave; X kh&ocirc;ng kết th&uacute;c ở bất kỳ vị tr&iacute; n&agrave;o lớn hơn q trong bất kỳ mẫu n&agrave;o kh&aacute;c. Ch&uacute;ng ta sẽ lưu trữ $m - q$&nbsp;trong SHIFT[i].</li> </ul> </li> </ol> <p style="text-align: justify;">Để t&iacute;nh c&aacute;c gi&aacute; trị của bảng SHIFT, ta sẽ xem x&eacute;t từng mẫu $p_i = a_1 a_2 ... a_m$. Ta sẽ &aacute;nh xạ từng chuỗi của con của $p_i$ c&oacute; k&iacute;ch thước l&agrave; $B a_{j - B + 1} ... a_j$ v&agrave;o trong bảng SHIFT v&agrave; đặt gi&aacute; trị tương ứng với gi&aacute; trị nhỏ nhất của gi&aacute; trị hiện tại (gi&aacute; trị ban đầu cho tất cả l&agrave; $m - B + 1$) v&agrave; $m - j$&nbsp;(số lượng lần dịch chuyển cần thiết để lấy được chuỗi con).</p> <p style="text-align: justify;">C&aacute;c gi&aacute; trị trong bảng SHIFT l&agrave; c&aacute;c gi&aacute; trị an to&agrave;n lớn nhất c&oacute; thể cho c&aacute;c lần dịch chuyển. Thay thế bất kỳ mục n&agrave;o trong bảng SHIFT bằng một gi&aacute; trị nhỏ hơn sẽ l&agrave;m bớt đi sự dịch chuyển v&agrave; sẽ mất nhiều thời gian hơn, nhưng vẫn đảm bảo an to&agrave;n, kh&ocirc;ng c&oacute; kết quả tr&ugrave;ng khớp n&agrave;o bị bỏ qua. V&igrave; vậy, ch&uacute;ng ta c&oacute; thể sử dụng một bảng n&eacute;n cho SHIFT, &aacute;nh xạ một số chuỗi kh&aacute;c nhau v&agrave;o c&ugrave;ng một mục, miễn l&agrave; ch&uacute;ng ta đặt số lần dịch chuyển tối thiểu của tất cả l&agrave;m gi&aacute; trị. Khi số lượng mẫu &iacute;t, ch&uacute;ng ta chọn B = 2 v&agrave; sử dụng bảng ch&iacute;nh x&aacute;c cho SHIFT, nếu kh&ocirc;ng, ch&uacute;ng ta chọn B = 3 v&agrave; sử dụng bảng n&eacute;n cho SHIFT. Trong cả hai trường hợp, thuật to&aacute;n kh&ocirc;ng biết liệu bảng SHIFT c&oacute; ch&iacute;nh x&aacute;c hay kh&ocirc;ng.</p> <p style="text-align: justify;">Miễn l&agrave; gi&aacute; trị dịch chuyển lớn hơn 0, ch&uacute;ng ta c&oacute; thể dịch chuyển một c&aacute;ch an to&agrave;n v&agrave; tiếp tục qu&eacute;t. Mặt kh&aacute;c, một chuỗi con hiện tại trong đoạn văn bản c&oacute; thể tr&ugrave;ng khớp một v&agrave;i mẫu trong danh s&aacute;ch mẫu.</p> <p style="text-align: justify;">Để tr&aacute;nh so s&aacute;nh chuỗi con với mọi mẫu trong danh s&aacute;ch mẫu, ch&uacute;ng ta sử dụng kỹ thuật băm để giảm thiểu số lượng mẫu được so s&aacute;nh. Ch&uacute;ng ta đ&atilde; t&iacute;nh to&aacute;n một &aacute;nh xạ của c&aacute;c k&yacute; tự B th&agrave;nh một số nguy&ecirc;n được sử dụng l&agrave;m chỉ số cho bảng SHIFT. Ch&uacute;ng ta sử dụng c&ugrave;ng một số nguy&ecirc;n để lập chỉ số v&agrave;o một bảng kh&aacute;c, được gọi l&agrave; HASH. Mục đầu v&agrave;o thứ i của bảng Hash, Hash[i], chứa một con trỏ tới danh scahs c&aacute;c mẫu m&agrave; c&oacute; B c&aacute;c k&yacute; tự cuối c&ugrave;ng băm th&agrave;nh i. Bảng Hash sẽ kh&aacute; thưa, bởi n&oacute; chỉ giữ c&aacute;c mẫu, trong khi đ&oacute; bảng SHIFT giữ tất cả c&aacute;c chuỗi c&oacute; thể c&oacute; với k&iacute;ch thước B. Điều n&agrave;y g&acirc;y ra tốn k&eacute;m cho bộ nhớ, nhưng n&oacute; cho ph&eacute;p ta sử dụng lại h&agrave;m băm, tiết kiệm được nhiều thời gian. Gọi h l&agrave; gi&aacute; trị băm của hậu tố hiện tại trong đoạn văn bản v&agrave; giả sử SHIFT[h]=0. Gi&aacute; trị của Hash[h] l&agrave; một con trỏ p trỏ v&agrave;o trong hai bảng kh&aacute;c nhau tại c&ugrave;ng một thời điểm. Ta giữ một danh s&aacute;ch c&aacute;c con trỏ tới c&aacute;c mẫu n&agrave;y, PAT_POINT, được sắp xếp bởi c&aacute;c gi&aacute; trị băm của B c&aacute;c k&yacute; tự cuối c&ugrave;ng của mỗi mẫu. Con trỏ p trỏ tới đầu danh s&aacute;ch c&aacute;c mẫu m&agrave; gi&aacute; trị băm l&agrave; h. Để t&igrave;m phần cuối của danh s&aacute;ch, ta sẽ tăng con trỏ n&agrave;y cho tới khi n&oacute; bằng gi&aacute; trị trong Hash[h+1]. V&iacute; dụ, nếu SHIFT[h] kh&aacute;c 0, th&igrave; Hash[h] = Hash[h+1]. Ngo&agrave;i ra, ta sẽ giữ một bảng gọi l&agrave; PREFIX.</p> <p style="text-align: justify;">C&aacute;c đoạn văn bản ng&ocirc;n ngữ tự nhi&ecirc;n kh&ocirc;ng phải l&agrave; ngẫu nhi&ecirc;n. V&iacute; dụ, c&aacute;c hậu tố như ion hay ing l&agrave; rất th&ocirc;ng dụng trong c&aacute;c đoạn văn bản tiếng anh. C&aacute;c hậu tố n&agrave;y sẽ kh&ocirc;ng chỉ xuất hiện trong c&aacute;c đoạn văn bản m&agrave; c&ograve;n trong một v&agrave;i c&aacute;c mẫu. Ch&uacute;ng sẽ g&acirc;y ra xung đột trong bảng Hash. Tất cả c&aacute;c mẫu c&oacute; c&ugrave;ng hậu tố sẽ được &aacute;nh xạ tới c&ugrave;ng một mục đầu v&agrave;o trong bảng HASH. Khi ch&uacute;ng ta gặp một hậu tố như vậy trong văn bản, ch&uacute;ng ta sẽ thấy rằng gi&aacute; trị SHIFT của n&oacute; l&agrave; 0. Ch&uacute;ng ta sẽ phải kiểm tra ri&ecirc;ng tất cả c&aacute;c mẫu c&oacute; hậu tố n&agrave;y để xem ch&uacute;ng c&oacute; khớp với văn bản hay kh&ocirc;ng. Để tăng tốc qu&aacute; tr&igrave;nh n&agrave;y, ch&uacute;ng ta sẽ đưa ra một bảng kh&aacute;c, được gọi l&agrave; PREFIX.</p> <p style="text-align: justify;">Ngo&agrave;i việc &aacute;nh xạ c&aacute;c k&yacute; tự B cuối c&ugrave;ng của tất cả c&aacute;c mẫu, ch&uacute;ng ta cũng &aacute;nh xạ c&aacute;c k&yacute; tự B đầu ti&ecirc;n của tất cả c&aacute;c mẫu v&agrave;o bảng PREFIX. Khi ch&uacute;ng ta t&igrave;m thấy gi&aacute; trị SHIFT bằng 0 v&agrave; ch&uacute;ng ta chuyển đến bảng HASH để x&aacute;c định xem c&oacute; khớp hay kh&ocirc;ng, ch&uacute;ng ta kiểm tra c&aacute;c gi&aacute; trị trong bảng PREFIX.</p> <p style="text-align: justify;">Bảng HASH kh&ocirc;ng chỉ chứa, đối với mỗi hậu tố, danh s&aacute;ch tất cả c&aacute;c mẫu c&oacute; hậu tố n&agrave;y, m&agrave; c&ograve;n chứa (gi&aacute; trị băm của) tiền tố của ch&uacute;ng. Ch&uacute;ng ta sẽ t&iacute;nh to&aacute;n tiền tố tương ứng trong văn bản (bằng c&aacute;ch dịch chuyển m &ndash; B&prime; k&yacute; tự sang tr&aacute;i) v&agrave; sử dụng n&oacute; để lọc c&aacute;c mẫu c&oacute; hậu tố giống nhau nhưng tiền tố kh&aacute;c nhau. Đ&acirc;y l&agrave; một phương ph&aacute;p lọc hiệu quả v&igrave; rất &iacute;t khi c&oacute; c&aacute;c mẫu kh&aacute;c nhau m&agrave; c&oacute; c&ugrave;ng một tiền tố v&agrave; c&ugrave;ng một hậu tố.</p> <h3 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">2. Bước qu&eacute;t</h3> <p style="text-align: justify;">V&ograve;ng lặp ch&iacute;nh của thuật to&aacute;n Wu-Manber bao gồm c&aacute;c bước sau:</p> <ol style="text-align: justify;"> <li>T&iacute;nh gi&aacute; trị băm h dựa tr&ecirc;n B k&yacute; tự hiện tại từ đoạn văn bản (bắt đầu bằng $t_{m - B + 1} ... t_m$)</li> <li>Kiểm tra gi&aacute; trị của SHIFT[h]: Nếu n&oacute; lớn hơn 0, bỏ qua đoạn văn bản v&agrave; quay trở về 1, nếu kh&ocirc;ng th&igrave; đi tới bước 3.</li> <li>T&iacute;nh to&aacute;n gi&aacute; trị băm của tiền tố của đoạn văn bản (bắt đầu từ m k&yacute; tự b&ecirc;n tr&aacute;i của vị tr&iacute; hiện tại), gọi n&oacute; l&agrave; text_prefix</li> <li>Kiểm tra cho từng p, $\text{Hash}[h]&nbsp; \leq p &lt; \text{Hash}[h + 1]$ nếu $\text{PREFIX}[p] = \text{text}_p\text{refix}$. Khi ch&uacute;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&aacute;ch trực tiếp.</li> </ol> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n Wu-Manber. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="https://tek4.vn/">tek4</a>&nbsp;nh&eacute;!</p>