名称:Tire、字典树、查找树
特点:查找效率高,消耗内存大
应用:字符串检索、词频统计、字符串排序等
敏感词过滤器定义前缀树
package com.nowcoder.community.util; import org.springframework.stereotype.Component; import java.util.HashMap; import java.util.Map; @Component public class SensitiveFilter { //描述前缀树的每一个节点 private class TrieNode{ //关键词结束标识 private boolean isKeywordEnd=false; //当前节点的子节点(key是下级节点的字符,value是下级) · 999999 private MapsubModes=new HashMap<>(); public boolean isKeywordEnd() { return isKeywordEnd; } public void setKeywordEnd(boolean keywordEnd) { isKeywordEnd = keywordEnd; } //添加子节点的方法 public void addSubNode(Character c,TrieNode node){ subModes.put(c,node); } //获取子节点 public TrieNode getSubNode(Character c){ return subModes.get(c); } } }
根据敏感词,初始化前缀树
在sensitive.words.txt文件中一行定义一个敏感词
private static final Logger logger = LoggerFactory.getLogger(SensitiveFilter.class); //替换符 private static final String REPLACEMENT="***"; //初始化根节点 private TrieNode rootNode=new TrieNode(); @PostConstruct//在服务启动的时候会初始化这个方法,解决了只需要初始化一次的问题 public void init(){ try( InputStream is= this.getClass().getClassLoader().getResourceAsStream("sensitive-words.txt"); BufferedReader reader=new BufferedReader(new InputStreamReader(is)); ){ //读取每一个敏感词 String keyword; while ((keyword=reader.readLine())!=null){ //添加到前缀树 this.addKeyWord(keyword); } }catch (IOException e){ logger.error("加载敏感词文件失败"+e.getMessage()); } } //将一个敏感词添加到前缀树当中 private void addKeyWord(String keyword){ TrieNode tempNode=rootNode; for(int i=0;i编写过滤敏感词的方法
public String filter(String text){ if(StringUtils.isBlank(text)){ return null; } //指针1 TrieNode tempNode=rootNode; //指针2 int begin=0; //指针3 int position=0; //结果 StringBuilder sb=new StringBuilder(); while (position测试0x9FFF); } package com.nowcoder.community; import com.nowcoder.community.util.SensitiveFilter; import org.junit.Test; import org.junit.runner.RunWith; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import org.springframework.test.context.ContextConfiguration; import org.springframework.test.context.junit4.SpringRunner; @RunWith(SpringRunner.class) @SpringBootTest @ContextConfiguration(classes = CommunityApplication.class) public class SensitiveTest { @Autowired private SensitiveFilter sensitiveFilter; @Test public void testSensitiveFilter(){ String text="这里可以赌※博,可以嫖娼,哈哈哈"; System.out.println(sensitiveFilter.filter(text)); } }原理
检测目标以字符为单位
根据敏感词初始化前缀树,根节点为root,根据每个敏感词的字符来添加节点,将末节点进行标记。给定一个字符串“xwabfabcff”来过滤敏感词abc、bf、be,需要三个指针,指针1指向前缀树,指针2、指针3指向字符串,默认初始指针1指向root,指针2、3指向字符串的起始端。当过滤开始,指针2首先会停在x,然后指针1判断前缀树是否有x的起点,判断不是不需要过滤x,指针2会向后移动一位到w,随之指针3也会向后移动一位,类似判断没有w开始的敏感词不需要过滤w,指针2和3向后移动一位到a,指针1进行判断有a为起始端的树,然后指针2会停在a,指针3往后移动一位到b,指针1也会向下查看a下节点是否有b,判断有,但是没有到达末节点,指针3会继续向后移动,到f,指针1会在b在查看是否有f,判断没有不需要过滤a,指针2会移动到b,指针3也会回到指针2的位置,类似的判断bf是敏感词,会将其过滤为***代替,最终的字符串后过滤为"xwa*****ff"
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)