Thuật toán Aho-Corasick 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 Aho-Corasick được ứng dụng trong đối s&aacute;nh đa mẫu. Ta sẽ t&igrave;m hiểu về kh&aacute;i niệm v&agrave; c&aacute;c kiến thức li&ecirc;n quan đến 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;">Thuật to&aacute;n Aho-Corasick bao gồm hai phần:</p> <ol style="text-align: justify;"> <li>Phần đầu ti&ecirc;n ta sẽ khởi tạo từ tập hợp c&aacute;c từ kh&oacute;a để tạo một m&ocirc; h&igrave;nh đối s&aacute;nh mẫu.</li> <li>Trong phần thứ hai, ta sẽ đưa c&aacute;c chuỗi k&yacute; tự đoạn văn bản l&agrave;m đầu v&agrave;o cho m&ocirc; h&igrave;nh n&agrave;y.</li> </ol> <h3 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">1. M&ocirc; h&igrave;nh đối s&aacute;nh mẫu trong thuật to&aacute;n Aho-Corasick</h3> <p style="text-align: justify;">M&ocirc; h&igrave;nh n&agrave;y sẽ x&aacute;c định vị tr&iacute; của c&aacute;c từ kh&oacute;a trong một đoạn văn bản. Trong b&agrave;i viết n&agrave;y, một chuỗi l&agrave; tập hợp hữu hạn chứa c&aacute;c k&yacute; hiệu. Cho $K = y_1, y_2, ..., y_k$&nbsp;l&agrave; một tập hợp hữu hạn c&aacute;c chuỗi m&agrave; ta sẽ gọi n&oacute; l&agrave; c&aacute;c từ kh&oacute;a v&agrave; x l&agrave; một chuỗi t&ugrave;y &yacute; v&agrave; ta gọi n&oacute; l&agrave; một chuỗi đoạn k&yacute; tự văn bản. B&agrave;i to&aacute;n đặt ra l&agrave; x&aacute;c định vị tr&iacute; v&agrave; x&aacute;c định c&aacute;c chuỗi con của x, l&agrave; c&aacute;c từ kh&oacute;a trong K. C&aacute;c chuỗi con n&agrave;y c&oacute; thể chồng ch&eacute;o lẫn nhau.</p> <p style="text-align: justify;">Một m&ocirc; h&igrave;nh đối s&aacute;nh mẫu cho K l&agrave; một chương tr&igrave;nh m&agrave; lấy đầu v&agrave;o l&agrave; một chuỗi k&yacute; tự văn bản x v&agrave; đưa ra cho đầu ra l&agrave; c&aacute;c vị tr&iacute; trong x m&agrave; tại đ&oacute; c&aacute;c từ kh&oacute;a của K xuất hiện (c&aacute;c chuỗi con). M&ocirc; h&igrave;nh đối s&aacute;nh mẫu bao gồm một tập hợp c&aacute;c trạng th&aacute;i. Mỗi trạng th&aacute;i được biểu diễn bởi một số. M&ocirc; h&igrave;nh sẽ xử l&yacute; chuỗi k&yacute; tự văn bản x bằng c&aacute;ch sẽ đọc lần lượt c&aacute;c k&yacute; tự trong x, đưa ra c&aacute;c chuyển đổi trạng th&aacute;i v&agrave; đưa ra kết quả đầu ra. C&aacute;c thao t&aacute;c của m&ocirc; h&igrave;nh đối s&aacute;nh mẫu được đưa ra bởi 3 h&agrave;m bao gồm: H&agrave;m goto, h&agrave;m failure, v&agrave; h&agrave;m output.</p> <p style="text-align: justify;">H&igrave;nh 1 b&ecirc;n dưới đ&acirc;y sẽ đưa ra c&aacute;c h&agrave;m được sử dụng bởi m&ocirc; h&igrave;nh cho tập hợp c&aacute;c từ kh&oacute;a&nbsp;<span id="urvanov-syntax-highlighter-6108c7dbb0398063671050" 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-sy">(</span><span class="crayon-v">he</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">she</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">his</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">hers</span><span class="crayon-sy">)</span></span></span>.</p> <p style="text-align: center;">H&igrave;nh 1</p> <p><img style="width: 100%;" src="../../../public_files/07872f51-5196-454d-b23a-dfcb059ebda4" alt="thuat-toan-aho-corasick" /></p> <p style="text-align: center;">H&igrave;nh a</p> <p style="text-align: center;"><img style="width: 100%;" src="../../../public_files/8e9ef0cc-8603-49c4-a379-45941df91ae5" alt="thuat-toan-aho-corasick-2" /></p> <p style="text-align: center;">H&igrave;nh b</p> <p style="text-align: center;"><img style="width: 100%;" src="../../../public_files/b07acd7f-4ca0-42fc-bd70-d37376b64864" alt="thuat-toan-aho-corasick-3" /></p> <p style="text-align: center;">H&igrave;nh c</p> <p style="text-align: justify;">Một trạng th&aacute;i bất kỳ sẽ được g&aacute;n l&agrave;m trạng th&aacute;i bắt đầu. Trong h&igrave;nh b&ecirc;n tr&ecirc;n, c&aacute;c trạng th&aacute;i l&agrave; $0, ..., 9$. H&agrave;m goto g sẽ &aacute;nh xạ một cặp bao gồm một trạng th&aacute;i v&agrave; một k&yacute; tự đầu v&agrave;o v&agrave;o trong một trạng th&aacute;i hoặc một th&ocirc;ng điệp l&agrave; fail. Biểu đồ c&oacute; hướng trong h&igrave;nh thứ nhất b&ecirc;n tr&ecirc;n l&agrave; h&agrave;m goto. V&iacute; dụ, cạnh được g&aacute;n nh&atilde;n h từ 0 tới 1 cho biết rằng $g(0, h) = 1$. Việc thiếu một mũi t&ecirc;n sẽ cho biết rằng l&agrave; fail. V&igrave; vậy, $g(1, \sigma)$ cho tất cả c&aacute;c k&yacute; tự đầu v&agrave;o $\sigma$ m&agrave; kh&ocirc;ng phải l&agrave; e hay i. Tất cả c&aacute;c m&ocirc; h&igrave;nh đối s&aacute;nh mẫu của ch&uacute;ng ta đều c&oacute; thuộc t&iacute;nh l&agrave; $g(0, \sigma)$ kh&aacute;c fail cho tất cả c&aacute;c k&yacute; hiệu đầu v&agrave;o $\sigma$. Ta sẽ thấy thuộc t&iacute;nh n&agrave;y của h&agrave;m goto trong trạng th&aacute;i 0 nhằm đảm bảo rằng một k&yacute; hiệu đầu v&agrave;o sẽ được xử l&yacute; bởi m&ocirc; h&igrave;nh trong mỗi v&ograve;ng lặp của m&ocirc; h&igrave;nh.</p> <p style="text-align: justify;">H&agrave;m failure f sẽ &aacute;nh xạ một trạng th&aacute;i v&agrave;o trong một trạng th&aacute;i kh&aacute;c. H&agrave;m failure được tham chiếu bất cứ khi n&agrave;o h&agrave;m goto th&ocirc;ng b&aacute;o l&agrave; fail. C&aacute;c trạng th&aacute;i nhất định được g&aacute;n l&agrave;m c&aacute;c trạng th&aacute;i đầu ra cho biết rằng tập hợp c&aacute;c từ kh&oacute;a đ&atilde; được t&igrave;m thấy. H&agrave;m output sẽ chuẩn h&oacute;a kh&aacute;i niệm n&agrave;y bằng c&aacute;ch li&ecirc;n kết tập hợp c&aacute;c từ kh&oacute;a với từng trạng th&aacute;i.</p> <p style="text-align: justify;">Một v&ograve;ng lặp thực thi của m&ocirc; h&igrave;nh đối s&aacute;nh mẫu được định nghĩa như sau. Cho s l&agrave; trạng th&aacute;i hiện tại của m&ocirc; h&igrave;nh v&agrave; a l&agrave; k&yacute; hiệu hiện tại của chuỗi đầu v&agrave;o x.</p> <ol style="text-align: justify;"> <li>Nếu $g(s, a) = s'$, m&ocirc; h&igrave;nh sẽ đưa ra dịch chuyển goto. Nếu n&oacute; v&agrave;o trạng th&aacute;i s&rsquo; v&agrave; k&yacute; hiệu tiếp theo của x trở th&agrave;nh k&yacute; hiệu đầu v&agrave;o hiện tại. Ngo&agrave;i ra, nếu output(s&rsquo;) kh&aacute;c rỗng, m&ocirc; h&igrave;nh sẽ đưa ra một tập hợp output(s&rsquo;) c&ugrave;ng với vị tr&iacute; của k&yacute; hiệu đầu v&agrave;o hiện tại. V&ograve;ng lặp được kết th&uacute;c.</li> <li>Nếu $g(s, a) = \text{fail}$, m&ocirc; h&igrave;nh sẽ tham khảo h&agrave;m failure f v&agrave; đưa ra một sự thay đổi failure. Nếu $f(s) = s'$, m&ocirc; h&igrave;nh sẽ lặp lại v&ograve;ng lặp với s&rsquo; l&agrave;m trạng th&aacute;i hiện tại v&agrave; a l&agrave; k&yacute; hiệu đầu v&agrave;o hiện tại.</li> </ol> <p style="text-align: justify;">Ban đầu, trạng th&aacute;i hiện tại của m&ocirc; h&igrave;nh l&agrave; trạng th&aacute;i bắt đầu v&agrave; k&yacute; hiệu đầu ti&ecirc;n của chuỗi k&yacute; tự văn bản l&agrave; k&yacute; hiệu đầu v&agrave;o. M&ocirc; h&igrave;nh sẽ xử l&yacute; chuỗi k&yacute; tự văn bản bằng c&aacute;ch thực hiện một v&ograve;ng lặp thực thi tr&ecirc;n mỗi k&yacute; hiệu của chuỗi văn bản.</p> <p style="text-align: justify;">V&iacute; dụ, xem x&eacute;t h&agrave;nh động của m&ocirc; h&igrave;nh M sử dụng c&aacute;c h&agrave;m trong h&igrave;nh b&ecirc;n tr&ecirc;n để xử l&yacute; chuỗi văn bản &ldquo;ushers&rdquo;. H&igrave;nh b&ecirc;n dưới đ&acirc;y sẽ chỉ ra c&aacute;c sự thay đổi trạng th&aacute;i được đưa ra bởi M trong việc xử l&yacute;.</p> <p><img style="width: 100%;" src="../../../public_files/0b3ddc10-51e6-491b-86d7-2e929c9caec8" alt="thuat-toan-aho-corasick-4" /></p> <p style="text-align: justify;">Xem x&eacute;t v&ograve;ng lặp thực thi khi M trong trạng th&aacute;i 4 v&agrave; k&yacute; hiệu đầu v&agrave;o hiện tại l&agrave; e. V&igrave; $g(4, e) = 5$, m&ocirc; h&igrave;nh sẽ th&ecirc;m trạng th&aacute;i 5, tiếp đến l&agrave; k&yacute; hiệu đầu v&agrave;o tiếp theo v&agrave; đưa ra output(5), chỉ ra rằng n&oacute; đ&atilde; t&igrave;m thấy c&aacute;c từ kh&oacute;a &ldquo;she&rdquo; v&agrave; &ldquo;he&rdquo; ở cuối vị tr&iacute; thứ 4 trong chuỗi k&yacute; tự văn bản.</p> <p style="text-align: justify;">Trong trạng th&aacute;i 5 tr&ecirc;n k&yacute; hiệu đầu v&agrave;o r, m&ocirc; h&igrave;nh tạo ra hai sự thay đổi trạng th&aacute;i trong v&ograve;ng lặp thực thi. V&igrave; $g(5, r) = \text{fail}$, M sẽ nhập trạng th&aacute;i $2 = f(5)$. V&igrave; $g(2, r)= 8$, M sẽ nhập trạng th&aacute;i 8 v&agrave; tiến đến c&aacute;c k&yacute; hiệu đầu v&agrave;o tiếp theo. V&agrave; kh&ocirc;ng c&oacute; kết quả đầu ra n&agrave;o được đưa ra trong v&ograve;ng lặp thực thi n&agrave;y.</p> <p style="text-align: justify;">Giải thuật sau đ&acirc;y sẽ t&oacute;m tắt h&agrave;nh động của m&ocirc; h&igrave;nh đối s&aacute;nh mẫu.</p> <p style="text-align: justify;">Giải thuật 1. M&ocirc; h&igrave;nh đối s&aacute;nh mẫu.</p> <pre class="language-cpp"><code>Đầu v&agrave;o, một chuỗi văn bản x = a1,a2,&hellip;,an, trong đ&oacute; mỗi ai l&agrave; một k&yacute; hiệu đầu v&agrave;o v&agrave; một m&ocirc; h&igrave;nh đối s&aacute;nh mẫu M với h&agrave;m goto g, h&agrave;m failure f, v&agrave; h&agrave;m output output. Đầu ra. C&aacute;c vị tr&iacute; m&agrave; c&aacute;c từ kh&oacute;a xuất hiện trong x. Phương thức Bắt đầu Trạng th&aacute;i &lt;- 0 Sử dụng v&ograve;ng lặp for với i từ 1 tới n, thực hiện Bắt đầu Trong khi g(trạng th&aacute;i state, ai) = fail, thực hiện g&aacute;n fail = f(trạng th&aacute;i state) Trạng th&aacute;i state &lt;- g(trạng th&aacute;i state, ai) Nếu output(trạng th&aacute;i state) kh&aacute;c rỗng, Bắt đầu In ra i In ra h&agrave;m output(trạng th&aacute;i state) Kết th&uacute;c Kết th&uacute;c Kết th&uacute;c</code></pre> <p style="text-align: justify;">Mỗi lần lặp qua v&ograve;ng lặp for sẽ biểu diễn cho một v&ograve;ng thực thi của m&ocirc; h&igrave;nh. Thuật to&aacute;n 1 được tạo giống với thuật to&aacute;n Knut-Morris-Pratt để t&igrave;m ra một từ kh&oacute;a trong một chuỗi văn bản.</p> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">2. X&acirc;y dựng h&agrave;m goto, failure v&agrave; output từ tập hợp c&aacute;c từ kh&oacute;a trong thuật to&aacute;n Aho-Corasick</h3> <p style="text-align: justify;">C&oacute; hai phần trong qu&aacute; tr&igrave;nh x&acirc;y dựng. Trong phần đầu ti&ecirc;n, ta sẽ định nghĩa c&aacute;c trạng th&aacute;i v&agrave; h&agrave;m goto. Trong phần hai ta sẽ t&iacute;nh to&aacute;n h&agrave;m failure.</p> <p style="text-align: justify;">Để x&acirc;y dựng h&agrave;m goto, ta sẽ tạo một biểu đồ goto. Biểu đồ bao gồm một đỉnh đại diện cho trạng th&aacute;i 0. Sau đ&oacute; ta sẽ nhập từng k&yacute; tự y v&agrave;o trong biểu đồ, th&ecirc;m một đường đi c&oacute; hướng tới biểu đồ m&agrave; bắt đầu ở trạng th&aacute;i bắt đầu. C&aacute;c đỉnh mới v&agrave; c&aacute;c cạnh được th&ecirc;m v&agrave;o trong biểu đồ để bắt đầu từ trạng th&aacute;i bắt đầu, một đường thẳng trong biểu đồ giải th&iacute;ch cho từ kh&oacute;a y. Từ kh&oacute;a y được th&ecirc;m v&agrave;o trong h&agrave;m output của trạng th&aacute;i m&agrave; ở đ&oacute; đường dẫn kết th&uacute;c. Ta th&ecirc;m c&aacute;c cạnh mới v&agrave;o trong biểu đồ chỉ khi cần thiết.</p> <ul> <li style="text-align: justify;">V&iacute; dụ, giả sử&nbsp;<span id="urvanov-syntax-highlighter-6108c7dbb03ab562150350" 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-sy">{</span><span class="crayon-v">he</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">she</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">his</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-v">hers</span><span class="crayon-sy">}</span></span></span>&nbsp;l&agrave; tập hợp c&aacute;c từ kh&oacute;a. Bằng c&aacute;ch th&ecirc;m từ kh&oacute;a đầu ti&ecirc;n v&agrave;o trong biểu đồ, ta c&oacute;:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/de69f47f-da72-4d94-ab0c-42848faa5e98" alt="thuat-toan-aho-corasick-5" /></p> <ul> <li style="text-align: justify;">Đường đi từ trạng th&aacute;i 0 tới trạng th&aacute;i 2 sẽ đại diện cho từ kh&oacute;a &ldquo;he&rdquo;, ta sẽ li&ecirc;n kết đầu ra &ldquo;he&rdquo; với trạng th&aacute;i 2. Bằng c&aacute;ch th&ecirc;m từ kh&oacute;a thứ 2 &ldquo;she&rdquo;, ta c&oacute; như sau:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/4dd82f83-f5b7-4363-b688-e7610463f9fe" alt="thuat-toan-aho-corasick-6" /></p> <ul> <li style="text-align: justify;">Đầu ra &ldquo;she&rdquo; được li&ecirc;n kết với trạng th&aacute;i 5. Bằng c&aacute;ch th&ecirc;m từ kh&oacute;a &ldquo;his&rdquo;, ta sẽ c&oacute; biểu đồ như sau. Ch&uacute; &yacute; rằng khi ta th&ecirc;m từ kh&oacute;a &ldquo;his&rdquo;, ta đ&atilde; c&oacute; một cạnh được g&aacute;n nh&atilde;n h từ trạng th&aacute;i 0 tới 1, v&igrave; vậy, ta sẽ kh&ocirc;ng cần th&ecirc;m cạnh g&aacute;n nh&atilde;n kh&aacute;c l&agrave; h từ trạng th&aacute;i 0 tới trạng th&aacute;i 1. Đầu ra &ldquo;his&rdquo; được li&ecirc;n kết với trạng th&aacute;i 7.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/3b7ad46b-ef92-4b61-9049-8ce6efc5b0c4" alt="thuat-toan-aho-corasick-7" /></p> <ul> <li>Sau khi th&ecirc;m từ kh&oacute;a cuối c&ugrave;ng l&agrave; &ldquo;hers&rdquo;, ta c&oacute;:</li> </ul> <p><img style="width: 100%;" src="../../../public_files/4a31a661-7bd1-4d7d-b43b-1919687b8250" alt="thuat-toan-aho-corasick-8" /></p> <ul> <li style="text-align: justify;">Từ kh&oacute;a &ldquo;hers&rdquo; được li&ecirc;n kết với trạng th&aacute;i 9. Ta c&oacute; thể sử dụng cạnh được g&aacute;n nh&atilde;n h từ trạng th&aacute;i 0 tới 1 v&agrave; cạnh e từ trạng th&aacute;i 1 tới 2.</li> <li style="text-align: justify;">Biểu đồ b&ecirc;n tr&ecirc;n l&agrave; một c&acirc;y c&oacute; hướng v&agrave; c&oacute; n&uacute;t gốc. Để x&acirc;y dựng h&agrave;m goto, ta sẽ th&ecirc;m một v&ograve;ng lặp từ trạng th&aacute;i 0 tr&ecirc;n tất cả c&aacute;c k&yacute; hiệu đầu v&agrave;o ngoại trừ h hoặc s. Ta sẽ c&oacute; một biểu đồ c&oacute; hướng trong h&igrave;nh 1 ban đầu.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/2cf32d08-3703-400c-9083-07763e7c4f76" alt="thuat-toan-aho-corasick-9" /></p> <p style="text-align: justify;">H&agrave;m failure được x&acirc;y dựng từ h&agrave;m goto. Ta sẽ định nghĩa độ s&acirc;u của một trạng th&aacute;i s trong biểu đồ goto l&agrave; độ d&agrave;i của đường đi ngắn nhất từ trạng th&aacute;i bắt đầu tới trạng th&aacute;i s. Trong h&igrave;nh a, trạng th&aacute;i bắt đầu sẽ c&oacute; độ s&acirc;u l&agrave; 0, trạng th&aacute;i 1 v&agrave; c&oacute; độ s&acirc;u l&agrave; 1, trạng th&aacute;i 2,4 v&agrave; 6 c&oacute; độ s&acirc;u l&agrave; 6 v&agrave; cứ tiếp tục như vậy.</p> <p style="text-align: justify;">Ta sẽ t&iacute;nh h&agrave;m failure cho tất cả c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u 1, sau đ&oacute; l&agrave; cho tất cả c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u 2, v&agrave; cứ như vậy cho tới khi h&agrave;m failure được x&acirc;y dựng cho tất cả c&aacute;c trạng th&aacute;i. Ta sẽ g&aacute;n $f(s) = 0$, cho tất cả c&aacute;c trạng th&aacute;i s c&oacute; độ s&acirc;u 1. Giả sử f được t&iacute;nh cho tất cả c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u nhỏ hơn d. H&agrave;m failure cho c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u d được t&iacute;nh to&aacute;n từ h&agrave;m failure cho c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u nhỏ hơn d. C&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u d c&oacute; thể được x&aacute;c định từ c&aacute;c gi&aacute; trị kh&ocirc;ng phải l&agrave; fail (nonfail) của h&agrave;m goto của c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u $d - 1$.</p> <p style="text-align: justify;">Để t&iacute;nh h&agrave;m failure cho c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u d, ta sẽ xem x&eacute;t từng trạng th&aacute;i r c&oacute; độ s&acirc;u d-1 v&agrave; thực hiện c&aacute;c thao t&aacute;c sau:</p> <ol style="text-align: justify;"> <li>Nếu $g(r, a) = \text{fail}$&nbsp;với tất cả a, kh&ocirc;ng l&agrave;m g&igrave; cả.</li> <li>Mặt kh&aacute;c, với mỗi k&yacute; hiệu a sao cho $g(r, a) = s$, thực hiện: <ul> <li>Đặt trạng th&aacute;i $\text{state} = f(r)$</li> <li>Thực hiện c&acirc;u lệnh g&aacute;n trạng th&aacute;i $\text{state} = f(\text{state})$&nbsp;với 0 hoặc nhiều lần, cho tới khi gi&aacute; trị cho trạng th&aacute;i c&oacute; thể lấy được sao cho g(trạng th&aacute;i, a) kh&aacute;c fail. (Lưu &yacute; rằng v&igrave; g(0, a) kh&aacute;c fail với mọi a, một trạng th&aacute;i sẽ lu&ocirc;n được t&igrave;m thấy)</li> <li>Đặt $f(s) = g(\text{state}, a)$</li> </ul> </li> </ol> <p style="text-align: justify;">V&iacute; dụ, để t&iacute;nh h&agrave;m failure từ h&igrave;nh a, ta sẽ đặt f(1) = f(3) = 0 v&igrave; 1 v&agrave; 3 l&agrave; c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u 1. Ta sẽ t&iacute;nh h&agrave;m failure cho 2, 6, v&agrave; 4, c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u 2. Để t&iacute;nh f(2), ta sẽ đặt trạng th&aacute;i = f(1) = 0, v&agrave; v&igrave; g(0,e) = 0, ta sẽ t&igrave;m được f(2) = 0. Để t&iacute;nh f(6), ta sẽ đặt trạng th&aacute;i = f(1) = 0, v&agrave; v&igrave; g(0,i) = 0, ta sẽ thấy rằng f(6) = 0. Để t&iacute;nh f(4), ta sẽ đặt trạng th&aacute;i = f(3) = 0 v&agrave; v&igrave; g(0,h) = 1, ta sẽ t&igrave;m ra f(4)&nbsp; = 1. V&agrave; cứ như vậy, ta c&oacute; được h&agrave;m failure trong h&igrave;nh 1b</p> <p style="text-align: justify;">Trong qu&aacute; tr&igrave;nh t&iacute;nh to&aacute;n h&agrave;m failure, ta sẽ cập nhật h&agrave;m output. Khi ta x&aacute;c định được f(s) = s&rsquo;, ta sẽ kết hợp c&aacute;c đầu ra của trạng th&aacute;i s với c&aacute;c đầu ra của trạng th&aacute;i s&rsquo;.</p> <p style="text-align: justify;">V&iacute; dụ, từ h&igrave;nh a, ta sẽ x&aacute;c định được f(5) = 2. Tại thời điểm n&agrave;y, ta sẽ gộp tập hợp đầu ra của trạng th&aacute;i 2, cụ thể l&agrave; {he}, với tập đầu ra của trạng th&aacute;i 5 để lấy được đầu ra mới l&agrave; tập hợp {he, she}. C&aacute;c tập hợp kết quả kh&ocirc;ng rỗng cuối c&ugrave;ng được chỉ ra trong h&igrave;nh c. C&aacute;c thuật to&aacute;n để t&iacute;nh to&aacute;n h&agrave;m goto, failure v&agrave; output từ K được t&oacute;m tắt như sau:</p> <p style="text-align: justify;">Thuật to&aacute;n 2. X&acirc;y dựng h&agrave;m goto</p> <pre class="language-cpp"><code>Đầu v&agrave;o. Tập hợp c&aacute;c từ kh&oacute;a K = {y1,y2,&hellip;,yk} Đầu ra. H&agrave;m goto g v&agrave; h&agrave;m output được t&iacute;nh to&aacute;n một phần. Phương thức. Giả sử output(s) l&agrave; rỗng khi trạng th&aacute;i s lần đầu ti&ecirc;n được tạo, v&agrave; g(s,a)=fail nếu a chưa được định nghĩa hoặc nếu g(s,a) chưa được định nghĩa. Phương thức enter(y) sẽ ch&egrave;n v&agrave;o trong biểu đồ goto một đường đi chỉ ra y. Bắt đầu Trạng th&aacute;i state mới &lt;- 0 Sử dụng v&ograve;ng lặp for với i = 1 cho tới k thực hiện enter(yi) Sử dụng v&ograve;ng lặp for tất cả a sao cho g(0,a) = fail, thực hiện g(0,a) &lt;-0 Kết th&uacute;c Phương thức enter(a1,a2,&hellip;,am) Bắt đầu Trạng th&aacute;i state &lt;-0, j&lt;-1 Trong khi g(trạng th&aacute;i state, aj) kh&aacute;c fail, thực hiện Bắt đầu Trạng th&aacute;i state &lt;- g(trạng th&aacute;i state, aj) j &lt;- j + 1 Kết th&uacute;c For p &lt;- j cho tới m, thực hiện Bắt đầu Trạng th&aacute;i state mới &lt;- trạng th&aacute;i state mới + 1 G(trạng th&aacute;i state, a_{p}) &lt;- trạng th&aacute;i state mới Trạng th&aacute;i state &lt;- trạng th&aacute;i state mới Kết th&uacute;c Output(trạng th&aacute;i state) &lt;- {a1,a2,&hellip;,am} Kết th&uacute;c</code></pre> <p>Thuật to&aacute;n 3. X&acirc;y dựng h&agrave;m failure</p> <pre class="language-cpp"><code>Đầu v&agrave;o. H&agrave;m goto g v&agrave; h&agrave;m output từ thuật to&aacute;n 2 Đầu ra. H&agrave;m failure f v&agrave; h&agrave;m output Phương thức Bắt đầu H&agrave;ng đợi queue &lt;- rỗng Sử dụng v&ograve;ng lặp For cho mỗi a sao cho g(0, a) = g kh&aacute;c 0, thực hiện Bắt đầu H&agrave;ng đợi queue &lt;- queue &cup; {s} f(s) &lt;- 0 Kết th&uacute;c Trong khi h&agrave;ng đợi queue kh&aacute;c rỗng, thực hiện Bắt đầu Cho r l&agrave; trạng th&aacute;i state tiếp theo trong h&agrave;ng đợi H&agrave;ng đợi queue &lt;- h&agrave;ng đợi queue &ndash; {r} For mỗi a sao cho g(r,a) = s kh&aacute;c fail, thực hiện Bắt đầu H&agrave;ng đợi queue &lt;- h&agrave;ng đợi queue &cup; {s} Trạng th&aacute;i state &lt;- f(r) While g(trạng th&aacute;i state, a) = fail thực hiện trạng th&aacute;i state &lt;- f(trạng th&aacute;i) f(s) &lt;- g(trạng th&aacute;i state, a) output(s) &lt;- output(s) &cup; output(f(s)) Kết th&uacute;c Kết th&uacute;c Kết th&uacute;c</code></pre> <p style="text-align: justify;">V&ograve;ng lặp đầu ti&ecirc;n t&iacute;nh to&aacute;n c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u 1 v&agrave; nhập v&agrave;o trong danh s&aacute;ch h&agrave;ng đợi v&agrave;o đầu ti&ecirc;n ra đầu ti&ecirc;n được chỉ định bởi biến queue (h&agrave;ng đợi). V&ograve;ng lặp ch&iacute;nh while t&iacute;nh to&aacute;n tập hợp c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u d từ tập hợp c&aacute;c trạng th&aacute;i c&oacute; độ s&acirc;u d-1.</p> <p style="text-align: justify;">H&agrave;m failure được tạo bởi thuật to&aacute;n 3 vẫn chưa tối ưu. Ta sẽ x&eacute;t m&ocirc; h&igrave;nh đối s&aacute;nh mẫu M trong h&igrave;nh 1. G(4,e) = 5. Nếu M ở trạng th&aacute;i 4 v&agrave; k&yacute; hiệu đầu v&agrave;o hiện tại $a_i$ kh&ocirc;ng phải l&agrave; e, th&igrave; M sẽ nhập trạng th&aacute;i $f(4) = 1$. V&igrave; M đ&atilde; x&aacute;c định $a_i$ kh&aacute;c $e$, M sẽ kh&ocirc;ng cần phải xem x&eacute;t gi&aacute; trị của h&agrave;m goto của trạng th&aacute;i 1 tr&ecirc;n e. Tr&ecirc;n thực tế, nếu từ kh&oacute;a &ldquo;his&rdquo; kh&ocirc;ng tồn tại, th&igrave; M c&oacute; thể đi trực tiếp từ trạng th&aacute;i 4 tới 0, bỏ quả c&aacute;c thay đổi trung gian cần thiết tới trạng th&aacute;i 1.</p> <p style="text-align: justify;">Để tr&aacute;nh tạo ra c&aacute;c sự thay đổi failure kh&ocirc;ng cần thiết, ta c&oacute; thể sử dụng f&rsquo;, tổng qu&aacute;t h&oacute;a h&agrave;m next, thay cho f trong thuật to&aacute;n 1. Định nghĩa $f'(1) = 0$. Sử dụng v&ograve;ng lặp For với $i &gt; 1$, $f'(i) = f'(f(i))$ nếu, với tất cả c&aacute;c k&yacute; hiệu đầu v&agrave;o $a, g(f(i), a)$ kh&aacute;c fail hay $g(i, a)$ kh&aacute;c fail, nếu kh&ocirc;ng $f'(i) = f(i)$. Tuy nhi&ecirc;n, để tr&aacute;nh tạo ra c&aacute;c sự thay đổi failure, ta c&oacute; thể sử dụng bản tự động giới hạn tất định của thuật to&aacute;n 1 được đưa ra trong phần 6.</p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">2. Loại bỏ c&aacute;c sự dịch chuyển sai lầm</h2> <p style="text-align: justify;">Ta sẽ loại bỏ c&aacute;c sự thay đổi failure trong giải thuật 1 bằng c&aacute;ch sử dụng h&agrave;m dịch chuyển tiếp theo của qu&aacute; tr&igrave;nh tự động h&oacute;a hữu hạn tất định thay cho h&agrave;m goto v&agrave; h&agrave;m failure.</p> <p style="text-align: justify;">Qu&aacute; tr&igrave;nh tự động h&oacute;a hữu hạn tất định bao gồm một tập hợp tất cả c&aacute;c trạng th&aacute;i S&nbsp; v&agrave; một h&agrave;m di chuyển tiếp theo $\gamma$ sao cho mỗi trạng th&aacute;i s v&agrave; k&yacute; hiệu đầu v&agrave;o a, $\gamma(s, a)$&nbsp;l&agrave; một trạng th&aacute;i trong S. Qu&aacute; tr&igrave;nh tự động h&oacute;a hữu hạn tất định sẽ đưa ra ch&iacute;nh x&aacute;c một lần thay đổi trạng th&aacute;i cho mỗi k&yacute; hiệu đầu v&agrave;o.</p> <p style="text-align: justify;">Bằng c&aacute;ch sử dụng h&agrave;m dịch chuyển tiếp theo $\gamma$ thay cho h&agrave;m goto, ta c&oacute; thể kh&ocirc;ng cần phải đưa ra c&aacute;c sự thay đổi failure bằng c&aacute;ch thay thế 2 trạng th&aacute;i đầu ti&ecirc;n trong v&ograve;ng lặp for của thuật to&aacute;n 1 với trạng th&aacute;i $\text{state} \leftarrow \gamma(\text{state}, a)$. Bằng c&aacute;ch sử dụng&nbsp;<img class="ql-img-inline-formula quicklatex-auto-format disappear appear" title="Rendered by QuickLaTeX.com" src="../../../wp-content/ql-cache/quicklatex.com-c4a67326bbefc853e0c5fd9a685a8c45_l3.svg" alt="\gamma" width="10" height="12" loading="lazy" />, thuật to&aacute;n 1 sẽ đưa ra ch&iacute;nh x&aacute;c một sự thay đổi trạng th&aacute;i cho mỗi k&yacute; tự đầu v&agrave;o.</p> <p style="text-align: justify;">Ta c&oacute; thể t&iacute;nh h&agrave;m di chuyển tiếp theo $\gamma$&nbsp;từ h&agrave;m goto v&agrave; failure bởi thuật to&aacute;n 4.</p> <p style="text-align: justify;">Trong trạng th&aacute;i 0, v&iacute; dụ, ta sẽ c&oacute; một sự thay đổi trạng th&aacute;i tr&ecirc;n h tới trạng th&aacute;i 1, một sự thay đổi tr&ecirc;n s sang trạng th&aacute;i 3, v&agrave; một sự thay đổi tr&ecirc;n bất kỳ k&yacute; hiệu n&agrave;o kh&aacute;c sang trạng th&aacute;i 0. Trong mỗi trạng th&aacute;i, dấu chấm đại diện cho bất kỳ k&yacute; tự n&agrave;o kh&aacute;c ngo&agrave;i c&aacute;c k&yacute; tự b&ecirc;n tr&ecirc;n.</p> <p style="text-align: justify;">Thuật to&aacute;n 4. X&acirc;y dựng qu&aacute; tr&igrave;nh tự động h&oacute;a hữu hạn tất định.</p> <pre class="language-cpp"><code>Đầu v&agrave;o. H&agrave;m goto g từ thuật to&aacute;n 2 v&agrave; h&agrave;m failure f từ thuật to&aacute;n 3. Đầu ra. H&agrave;m di chuyển tiếp theo (next move) gamma Phương thức. Bắt đầu H&agrave;ng đợi queue &lt;- rỗng Sử dụng v&ograve;ng lặp for mỗi k&yacute; hiệu a, thực hiện Bắt đầu gamma(0,a) &lt;- g(0,a) Nếu g(0,a) kh&aacute;c 0, th&igrave; queue &lt;- queue &cup; {g(0,a)} Kết th&uacute;c Trong khi h&agrave;ng đợi queue kh&aacute;c rỗng, thực hiện Bắt đầu Cho r l&agrave; trạng th&aacute;i state tiếp theo trong h&agrave;ng đợi queue H&agrave;ng đợi queue &lt;- queue &ndash; {r} Sử dụng v&ograve;ng lặp for cho mỗi k&yacute; hiệu a, thực hiện Nếu g(r,a) = s kh&aacute;c fail, thực hiện Bắt đầu H&agrave;ng đợi queue &lt;- queue &cup; {s} gamma(r, a) &lt;- s Kết th&uacute;c Nếu kh&ocirc;ng th&igrave; gamma(r,a) &lt;- gamma(f(r), a) Kết th&uacute;c Kết th&uacute;c</code></pre> <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 Aho-Corasick. 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="../../../">tek4</a>&nbsp;nh&eacute;!</p>