Open ZhelinCheng opened 1 year ago
https://zhelin.me/83e19b1a7821ce77/?
敏感词过滤应该是许多后端同事经常会遇到的需求，无论是评论、弹幕、文章，都需要做敏感词过滤处理来规避风险。在前端开发中，使用replace函数来替换字符串是我们的常规操作，在这之前我思考过如果用JavaScript来实现敏感词过滤该怎么做。在学习过程中，接触到了Trie树，瞬间有一种拨开云雾见青天的感觉。
所以，我这里算法使用的是AC（Aho–Corasick）自动机算法。会简单的对方案进行阐述，主要是代码实现，需要注意的是，在这里将采用TypeScript编写。同时代码也上传至GitHub，点击此处查看本文完整代码
Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。
在正式进入到AC自动机算法之前，我们需要先了解Trie树。
Trie树（字典树）
在维基百科中，Trie 树的解释是这样的：
在计
https://zhelin.me/83e19b1a7821ce77/?
敏感词过滤应该是许多后端同事经常会遇到的需求，无论是评论、弹幕、文章，都需要做敏感词过滤处理来规避风险。在前端开发中，使用replace函数来替换字符串是我们的常规操作，在这之前我思考过如果用JavaScript来实现敏感词过滤该怎么做。在学习过程中，接触到了Trie树，瞬间有一种拨开云雾见青天的感觉。
所以，我这里算法使用的是AC（Aho–Corasick）自动机算法。会简单的对方案进行阐述，主要是代码实现，需要注意的是，在这里将采用TypeScript编写。同时代码也上传至GitHub，点击此处查看本文完整代码
Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。
在正式进入到AC自动机算法之前，我们需要先了解Trie树。
Trie树（字典树）
在维基百科中，Trie 树的解释是这样的：
在计