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