字符串匹配
字符串匹配是最简单、直观的方法,直接在文本中查找是否存在敏感词列表中的词汇。如在Java中使用contains方法或者正则表达式都可以判断。
但是他只适合小规模文本或敏感词较少的场合下使用,比如我们在避免SQL注入的时候,需要对用户输入的内容进行一些特殊字符的过滤,就可以用这种方式,又或者是我们在做数据脱敏的时候,也可以用这种方式实现。
他的优点就是,实现简单,易于理解。但是缺点也很明显,就是效率比较低,特别是在处理大量文本或敏感词库较大时。还有就是无法处理变体词汇,如错别字、同音字等。
前缀树
前缀树,也被称为Trie树,是一种用于快速检索字符串数据集中的键的树形数据结构。
这种数据结构特别适合解决与一组字符串有关的问题,如自动补全、拼写检查、词频统计、敏感词过滤等。前缀树的核心优势在于,它能够通过共享前缀来最大化地减少查询和存储空间,特别是当处理大量具有共同前缀的字符串时。 前缀树比较适合敏感词有共同前缀的场景,如具有相同根词的不同变形。并且他比字符串更加适合大量敏感词和长文本的处理。
当需要检测一段文本是否包含敏感词时,可以将文本的每个字符作为起点,尝试在前缀树中进行匹配。
前缀树的优点是,插入和查询效率高,特别是在敏感词有共同前缀的情况下(如ab、abc、abcd)。而且他的空间效率较高,因为是共享公共前缀的。
但是他也有缺点,一方面是构建树的初期成本较高。另外对于没有共同前缀的敏感词,效率提升不明显。
所以,前缀树适合做高效的字典查找、根据前缀自动补全、利用前缀匹配进行快速路由等场景。
DFA算法
DFA是Deterministic Finite Automaton的缩写,翻译过来叫确定有限自动机,DFA算法是一种高效的文本匹配算法,特别适合于敏感词过滤。
DFA由一组状态组成,以及在这些状态之间的转换,这些转换由输入字符串驱动。每个状态都知道下一个字符的到来应该转移到哪个状态。如果输入字符串结束时,DFA处于接受状态,则输入字符串被认为是匹配的。
首先,为每个敏感词构建DFA。这个过程从一个初始状态开始,对于敏感词中的每个字符,如果当前状态下没有对应该字符的转换,则创建一个新的状态,并添加一条从当前状态到新状态的转换,这条转换由该字符触发。如果已经有了对应该字符的转换,则沿着这条转换到达下一个状态。重复这个过程直到敏感词的每个字符都被处理。最后一个字符对应的状态被标记为接受状态,意味着到达这个状态表示找到了一个敏感词。
当需要检测一段文本时,从DFA的初始状态和文本的第一个字符开始。对于文本中的每个字符,根据当前状态和字符确定下一个状态。如果存在对应字符的转换,则跟随这条转换到达下一个状态;如果不存在,则返回到初始状态。如果在某个点达到了接受状态,意味着匹配到了一个敏感词。然后可以选择标记或替换该敏感词,并继续处理文本的剩余部分。
DFA适合复杂模式匹配,如正则表达式匹配。以及网络内容过滤和安全审计,用于检测和过滤特定模式的文本。