js-aho-corasick-matcher
v1.0.2
Published
AC 自动机 (Aho-Corasick ) 多关键字字符串搜索算法的简单实现,用于学习之目的,代码当中有每一部分的详细说明。
Downloads
3
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