Package Exports

js-aho-corasick-matcher
js-aho-corasick-matcher/index.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (js-aho-corasick-matcher) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

JS Aho-Corasick Matcher

AC 自动机（Aho-Corasick ）多关键字字符串搜索算法的简单实现，用于学习之目的，代码当中有每一部分的详细说明。

算法简介

AC 自动机是一种多关键字字符串搜索算法。多关键字字符串搜索是指在 目标字符串 里同时搜索多个指定的 关键字 所出现的位置。

简单思想

AC 自动机一次同时搜索多个关键字；
AC 自动机假定多个关键字之间存在相同的部分，比如 "abcd", "bcw" 这两个关键字的 "bc" 是相同的；
在搜索过程中，如果匹配中某个关键字的部分字符，然后接下来的字符不匹配，搜索会寻找跟当前 部分匹配字符 有 相同前缀 的其他关键字，如果存在则跳到其他关键字继续进行搜索。AC 自动机正是利用这种跳转来避免每次从头开始匹配每个关键字，以达到加速之目的；
如果多个关键字之间没有相同的部分，则 AC 自动机复杂度跟暴力搜索一样。

实现方法

用关键字构建一个前缀树，树的节点是关键字的字符，树的每条分支就是关键字，因为关键字之间有相同的部分，所以分支之间有可能有共用的地方；

比如关键字 "abcd", "bcw" 和 "aby" 的前缀树：

ROOT
   |--a
   |  |--b
   |  |  |--c
   |  |  |  |--d
   |  |  |
   |  |  |--y
   |
   |--b
   |  |--c
   |  |  |--w

为每个节点设置一个 匹配失败 的指针，用于当搜索某个关键字进行到一半而失败时，应该跳转到的节点。比如 "abcd" 的 "c" 的失败指针应该指向 "bcw" 的 "c"，因为它们有相同的前缀；
假设当前的被搜索的字符串是 "abcw"，一开始会沿着 "abcd" 分支的节点前进，当搜索到 "w" 时，当前节点是关键字 "abcd" 的 "c"，但它的子节点只有 "d" 而没有 "w"，所以这时会改道到 匹配失败 指针指向的 "bcw" 分支的 "c"，然后再查看其子节点是否存在 "w"；
因为失败指针指向的节点（注意它已经是另外一个关键字的分支上的节点）跟之前的节点有相同的前缀，所以被搜索字符串不需要回退，而搜索指针也不需要从根节点开始。

单元测试

执行命令：

$ npm test

应该能看到 testAhoCorasick() passed. 字样。

单步调试/跟踪

有时跟踪程序的运行过程，能帮助对程序的理解，启动单步调试的方法是：

在 vscode 里打开该项目，然后在单元测试文件里设置断点，再执行 Run and Debug 即可。

字符串搜索算法系列项目

JS Rabin-Karp Matcher https://github.com/hemashushu/js-rabin-karp-matcher
JS Boyer-Moore-Horspool Matcher https://github.com/hemashushu/js-boyer-moore-horspool-matcher
JS KMP Matcher https://github.com/hemashushu/js-kmp-matcher
JS Aho-Corasick Matcher https://github.com/hemashushu/js-aho-corasick-matcher
JS Regexp Interpreter https://github.com/hemashushu/js-regexp-interpreter