Thuật toán Boyer-Moore trong tìm kiếm xâu con

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ch&uacute;ng ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n Boyer-Moore được ứng dụng trong việc t&igrave;m kiếm chuỗi x&acirc;u con trong một chuỗi kh&aacute;c.</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;">Thuật to&aacute;n Boyer-Moore, giống như thuật to&aacute;n Knuth-Morris-Pratt hoặc Rabin-Karp, l&agrave; một thuật to&aacute;n t&igrave;m kiếm chuỗi hiệu quả. N&oacute; được ph&aacute;t triển bởi Robert Boyer v&agrave; J Strother Moore v&agrave;o năm 1977. Thuật to&aacute;n n&agrave;y xử l&yacute; trước cho mẫu cần t&igrave;m kiếm.</p> <p style="text-align: justify;">Thuật to&aacute;n t&igrave;m kiếm chuỗi n&agrave;y hiệu quả v&igrave; n&oacute; kh&ocirc;ng đi qua to&agrave;n bộ kh&ocirc;ng gian t&igrave;m kiếm khi n&oacute; đang thực hiện t&igrave;m kiếm một mẫu ph&ugrave; hợp. N&oacute; sẽ bỏ qua một c&aacute;ch th&ocirc;ng minh để giảm số lượng k&yacute; tự so s&aacute;nh m&agrave; mỗi lần t&igrave;m kiếm được thực hiện.</p> <p style="text-align: justify;">C&oacute; hai giai đoạn cho qu&aacute; tr&igrave;nh t&igrave;m kiếm chuỗi n&agrave;y. Giai đoạn đầu ti&ecirc;n l&agrave; tạo một bảng chỉ số cho mẫu t&igrave;m kiếm. Bảng t&igrave;m kiếm n&agrave;y được sử dụng để bỏ qua chuỗi t&igrave;m kiếm nhằm giảm số lượng c&aacute;c thao t&aacute;c đối s&aacute;nh.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;"><strong>2. &Yacute; tưởng của thuật to&aacute;n</strong></h2> <p style="text-align: justify;">Thuật to&aacute;n t&igrave;m kiếm chuỗi Boyer-Moore được dựa tr&ecirc;n 2 c&aacute;ch tiếp cận heuristics:</p> <ol style="text-align: justify;"> <li>C&aacute;ch 1: Thực hiện so s&aacute;nh mẫu t&igrave;m kiếm P với chuỗi k&yacute; tự con của T.</li> <li>C&aacute;ch 2: Nếu một sự sai lệch kh&ocirc;ng tr&ugrave;ng khớp xảy ra tại T[i] = c: <ol> <li>Nếu mẫu t&igrave;m kiếm P c&oacute; chứa k&yacute; tự c, thực hiện dịch chuyển mẫu P sang phải sao cho k&yacute; tự c cuối c&ugrave;ng trong P nằm thẳng h&agrave;ng với T[i]</li> <li>Mặt kh&aacute;c, thực hiện dịch chuyển P sao cho P[0] thẳng h&agrave;ng với T[i+1]</li> </ol> </li> </ol> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. H&agrave;m t&igrave;m kiếm lần xuất hiện cuối c&ugrave;ng của k&yacute; tự</h2> <p style="text-align: justify;">Thuật to&aacute;n Boyer-Moore sẽ thực hiện xử l&yacute; mẫu t&igrave;m kiếm P v&agrave; một bảng chữ c&aacute;i $\sum$ để x&acirc;y dựng h&agrave;m t&igrave;m kiếm lần xuất hiện cuối c&ugrave;ng của k&yacute; tự v&agrave; thực hiện &aacute;nh xạ bảng $\sum$ tới c&aacute;c số nguy&ecirc;n, trong đ&oacute;, $L(c)$&nbsp;được định nghĩa như sau:</p> <ul style="text-align: justify;"> <li>Chỉ số lớn nhất i sao cho $P[i] = c$&nbsp;hoặc</li> <li>Bằng -1 nếu chỉ số kh&ocirc;ng tồn tại.</li> </ul> <p style="text-align: justify;">V&iacute; dụ:</p> <ul> <li style="text-align: justify;">$\sum = a, b, c, d$</li> <li style="text-align: justify;">$P = abacab$</li> </ul> <table style="border-collapse: collapse; width: 56.7692%; height: 60px; margin-left: auto; margin-right: auto;" border="1"> <tbody> <tr> <td style="width: 18.9168%; text-align: center;" width="125">c</td> <td style="width: 18.9168%; text-align: center;" width="125">a</td> <td style="width: 18.9168%; text-align: center;" width="125">b</td> <td style="width: 18.9168%; text-align: center;" width="125">c</td> <td style="width: 18.9195%; text-align: center;" width="125">d</td> </tr> <tr> <td style="width: 18.9168%; text-align: center;" width="125">L(c)</td> <td style="width: 18.9168%; text-align: center;" width="125">4</td> <td style="width: 18.9168%; text-align: center;" width="125">5</td> <td style="width: 18.9168%; text-align: center;" width="125">3</td> <td style="width: 18.9195%; text-align: center;" width="125">-1</td> </tr> </tbody> </table> <p>H&agrave;m t&igrave;m kiếm lần xuất hiện cuối c&ugrave;ng của chữ c&aacute;i được t&iacute;nh trong thời gian $O(m + s)$, trong đ&oacute; m l&agrave; k&iacute;ch thước của $P$ v&agrave; $s$ l&agrave; k&iacute;ch thước của bảng $\sum$.</p> <h2 id="ftoc-heading-4" class="ftwp-heading">4. Giải thuật Boyer-Moore</h2> <p>$\text{BoyerMooreMatch}$ $(T, P, \sum)$</p> <ul> <li>$L \leftarrow \text{lastOccurenceFunc}$$(P, \sum)$</li> <li>$i \leftarrow m - 1$</li> <li>$j \leftarrow m - 1$</li> <li>Thực hiện v&ograve;ng lặp <ul> <li>Nếu $T[i] = P[j]$ <ul> <li>Nếu $j = 0$ <ul> <li>Trả về $i$&nbsp;(kết quả tr&ugrave;ng khớp xảy ra tại i)</li> </ul> </li> <li>Mặc kh&aacute;c <ul> <li>$i \leftarrow i - 1$</li> <li>$j \leftarrow j - 1$</li> </ul> </li> </ul> </li> <li>Mặc kh&aacute;c <ul> <li>(Thực hiện nhảy c&aacute;ch k&yacute; tự)</li> <li>$l \leftarrow&nbsp; L[T[i]]$</li> <li>$i \leftarrow i + m - \text{min}(j, 1+ l)$</li> <li>$j \leftarrow m - 1$</li> </ul> </li> </ul> </li> <li>Cho tới khi $i &gt; n - 1$</li> <li>Trả về&nbsp; $-1$ (Kh&ocirc;ng c&oacute; trường hợp tr&ugrave;ng khớp)</li> </ul> <p>V&iacute; dụ: Ch&uacute;ng ta sẽ thực hiện t&igrave;m kiếm mẫu APPLE từ chuỗi k&yacute; tự APPSTOREAPPLE.</p> <p><img style="width: 100%;" src="../../../public_files/b0079f0a-9aa6-4485-8c7b-b2eb77de87da" alt="thuat-toan-boyer-moore" /></p> <p style="text-align: justify;">Trong lần so s&aacute;nh đầu ti&ecirc;n, v&igrave; k&yacute; tự T kh&ocirc;ng hề c&oacute; xuất hiện trong mẫu t&igrave;m kiếm P = &ldquo;APPLE&rdquo;, do đ&oacute;, số k&yacute; tự ta cần dịch chuyển l&agrave; 5 k&yacute; tự. Hay n&oacute;i c&aacute;ch kh&aacute;c với c&aacute;ch tiếp cận của giải thuật Boyer-Moore, m&igrave;nh sẽ thực hiện dịch chuyển mẫu t&igrave;m kiếm P sang phải sao cho k&yacute; tự A (Phần tử đầu ti&ecirc;n của mẫu P[0]) của mẫu t&igrave;m kiếm nằm thẳng h&agrave;ng với k&yacute; tự O (Phần tử T[i+1] của chuỗi k&yacute; tự).</p> <p><img style="width: 100%;" src="../../../public_files/8608dc2c-09d5-48df-accd-9f633eee4c50" alt="thuat-toan-boyer-moore-2" /></p> <p style="text-align: justify;">Tiếp theo, trong lần so s&aacute;nh thứ 2, v&igrave; k&yacute; tự P của chuỗi k&yacute; tự c&oacute; xuất hiện trong mẫu t&igrave;m kiếm P, v&agrave; vị tr&iacute; l&agrave; 2. Do đ&oacute;, m&igrave;nh sẽ thực hiện dịch chuyển mẫu cần t&igrave;m kiếm sang phải 2 k&yacute; tự để sao cho k&yacute; tự P của chuỗi k&yacute; tự thẳng h&agrave;ng với k&yacute; tự P (xuất hiện lần cuối c&ugrave;ng) của mẫu t&igrave;m kiếm.</p> <p><img style="width: 100%;" src="../../../public_files/5b9135d1-b61a-4269-b9a9-53b5a4b3a602" alt="thuat-toan-boyer-moore-3" /></p> <p style="text-align: justify;">Tiếp theo, trong lần so s&aacute;nh thứ 3, k&yacute; tự L c&oacute; xuất hiện trong mẫu t&igrave;m kiếm, do đ&oacute;, giống như c&aacute;ch l&agrave;m b&ecirc;n tr&ecirc;n, m&igrave;nh sẽ thực hiện dịch chuyển mẫu t&igrave;m kiếm sang b&ecirc;n phải 1 vị tr&iacute;. V&agrave; tiếp theo, m&igrave;nh sẽ thực hiện so s&aacute;nh từng k&yacute; tự trong mẫu t&igrave;m kiếm P với chuỗi k&yacute; tự T.</p> <p><img style="width: 100%;" src="../../../public_files/2e7faee4-64e0-4f19-8c19-337880accd83" alt="thuat-toan-boyer-moore-4" /></p> <p><img style="width: 100%;" src="../../../public_files/3174ad63-d572-4b1a-bac6-f0a98f386d2b" alt="thuat-toan-boyer-moore-5" /></p> <p><img style="width: 100%;" src="../../../public_files/4a356311-0d23-4fe0-a280-15562c3288e3" alt="thuat-toan-boyer-moore-6" /></p> <p><img style="width: 100%;" src="../../../public_files/627898a8-1763-44ab-bc23-c2826600fe14" alt="thuat-toan-boyer-moore-7" /></p> <p><img style="width: 100%;" src="../../../public_files/03d4c7fc-5aec-4c4e-8701-58c20280be2a" alt="thuat-toan-boyer-moore-8" /></p> <p><img style="width: 100%;" src="../../../public_files/0be294ff-23dd-49ec-9465-4118aca4c566" alt="thuat-toan-boyer-moore-9" /></p> <p style="text-align: justify;">Như vậy, việc so s&aacute;nh đ&atilde; thực hiện tr&ecirc;n to&agrave;n bộ mẫu t&igrave;m kiếm P v&agrave; kết quả trả về l&agrave; n&oacute; tr&ugrave;ng khớp với chuỗi k&yacute; tự con trong T. Như vậy, m&igrave;nh đ&atilde; ho&agrave;n th&agrave;nh xong việc t&igrave;m kiếm chuỗi k&yacute; tự bằng giải thuật Boyer-Moore.</p> <p style="text-align: justify;">Ch&uacute;ng ta c&ugrave;ng thực hiện th&ecirc;m một v&iacute; dụ nữa nh&eacute;!</p> <p style="text-align: justify;">V&iacute; dụ 2: M&igrave;nh sẽ thực hiện t&igrave;m kiếm mẫu APPLE từ chuỗi k&yacute; tự RIPPLEAPPLE.</p> <p><img style="width: 100%;" src="../../../public_files/e03754a6-6118-4d56-956c-2785fea130bd" alt="thuat-toan-boyer-moore-10" /></p> <p style="text-align: justify;">Trong lần so s&aacute;nh đầu ti&ecirc;n, v&igrave; k&yacute; tự L c&oacute; xuất hiện trong mẫu t&igrave;m kiếm P, do đ&oacute;, m&igrave;nh sẽ dịch chuyển mẫu t&igrave;m kiếm sang phải sao cho k&yacute; tự L trong mẫu nằm thẳng h&agrave;ng với k&yacute; tự L trong chuỗi k&yacute; tự (dịch sang phải 1 k&yacute; tự).</p> <p><img style="width: 100%;" src="../../../public_files/b960ed99-b240-4343-aece-bf9d55869a6f" alt="thuat-toan-boyer-moore-11" /></p> <p><img style="width: 100%;" src="../../../public_files/31b7277d-7d98-4bd4-9038-cf07bda2dab4" alt="thuat-toan-boyer-moore-12" /></p> <p><img style="width: 100%;" src="../../../public_files/c602c20d-41e7-4503-80e8-ec005ce3db5d" alt="thuat-toan-boyer-moore-13" /></p> <p><img style="width: 100%;" src="../../../public_files/a6954b55-9e8d-4e31-b34b-92330950a4bd" alt="thuat-toan-boyer-moore-14" /></p> <p><img style="width: 100%;" src="../../../public_files/91000155-88a3-4fe4-931c-93d28901eeec" alt="thuat-toan-boyer-moore-15" /></p> <p style="text-align: justify;">V&agrave; m&igrave;nh sẽ thực hiện so s&aacute;nh từng k&yacute; tự trong mẫu t&igrave;m kiếm P cho đến khi gặp k&yacute; tự A trong mẫu, kết quả l&agrave; một sự kh&ocirc;ng tr&ugrave;ng khớp đ&atilde; xảy ra, do đ&oacute;, m&igrave;nh sẽ dịch chuyển mẫu t&igrave;m kiếm P sang b&ecirc;n phải 1 vị tr&iacute;, hay n&oacute;i c&aacute;ch kh&aacute;c, dịch chuyển sao cho P[0] thẳng h&agrave;ng với k&yacute; tự T[i+1].</p> <p><img style="width: 100%;" src="../../../public_files/1264365a-71e3-42a4-a682-a87a6181f05d" alt="thuat-toan-boyer-moore-16" /></p> <p style="text-align: justify;">Tiếp theo, m&igrave;nh lại thực hiện so s&aacute;nh như c&aacute;ch l&agrave;m b&ecirc;n tr&ecirc;n, dịch chuyển mẫu t&igrave;m kiếm P sang 4 vị tr&iacute; để A trong chuỗi k&yacute; tự thẳng h&agrave;ng với k&yacute; tự A trong mẫu t&igrave;m kiếm P.</p> <p><img style="width: 100%;" src="../../../public_files/8fe6f45f-0dc0-43b7-aad3-c8d75f7971f2" alt="thuat-toan-boyer-moore-17" /></p> <p><img style="width: 100%;" src="../../../public_files/b0c23c91-4430-4c08-b466-c2517b2c32a5" alt="thuat-toan-boyer-moore-18" /></p> <p><img style="width: 100%;" src="../../../public_files/c0d956de-2d9a-4321-8135-c4941be91ff5" alt="thuat-toan-boyer-moore-19" /></p> <p style="text-align: justify;">Cuối c&ugrave;ng, m&igrave;nh thực hiện so s&aacute;nh từng k&yacute; tự trong mẫu t&igrave;m kiếm với chuỗi k&yacute; tự con của T v&agrave; kết quả trả về l&agrave; sự tr&ugrave;ng khớp. Do đ&oacute;, m&igrave;nh đưa ra th&ocirc;ng b&aacute;o l&agrave; đ&atilde; t&igrave;m thấy mẫu t&igrave;m kiếm P trong chuỗi k&yacute; tự T.</p> <p style="text-align: justify;">Như vậy, ch&uacute;ng ta đ&atilde; t&igrave;m hiểu về thuật to&aacute;n Boyer-Moore, v&agrave; c&aacute;ch hoạt động của n&oacute; c&ugrave;ng với v&iacute; dụ. Hy vọng rằng c&aacute;c bạn đ&atilde; hiểu được thuật to&aacute;n v&agrave; c&aacute;ch hoạt động. Nếu c&aacute;c bạn c&oacute; thắc mắc hoặc đ&oacute;ng g&oacute;p &yacute; kiến, c&aacute;c bạn h&atilde;y để lại b&igrave;nh luận b&ecirc;n dưới cho m&igrave;nh nh&eacute;, rất vui v&igrave; được chia sẻ những b&agrave;i học hay cho c&aacute;c bạn.</p> <p style="text-align: justify;">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="../../../">tek4</a>&nbsp;nh&eacute;!</p>