布隆过滤器
布隆过滤器用来判断一个集合中的是否包含某一个元素，由于采用hash运算，有hash碰撞的原因，所以会存在误判。布隆过滤器判定一个元素存在的情况，这个元素可能不存在，但是判定一个元素不存在的时候，是一定不存在的。
利用redisson的布隆过滤器实现敏感词过滤
public static void main(String[] args) { Config config = new Config(); config.useSingleServer().setAddress("redis://192.168.56.102:6379"); // config.useSingleServer().setPassword(""); // 构造Redisson RedissonClient redissonClient = Redisson.create(config); // 初始化布隆过滤器：预计元素为100000000L个，误差率为3% RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("phoneList"); bloomFilter.tryInit(100000000L, 0.03); // 将号码插入到布隆过滤器中 bloomFilter.add("张雪"); bloomFilter.add("张学友"); bloomFilter.add("张雪1"); bloomFilter.add("张三"); // 判断下面的号码是否在布隆过滤器中 System.out.println(bloomFilter.contains("张雪1")); System.out.println(bloomFilter.contains("李四")); System.out.println(bloomFilter.contains("张学友")); }
布隆过滤器特性，
- 无法返回具体的敏感词是什么
- 会存在敏感词的误判
DFA
- 将敏感词拆分储存
- 设置标记位标记是否结束
如敏感词有张学友，张学良，叶良，叶良辰，如图示:
java实现
public class SensitiveWordUtil { public static Map<String, Object> dictionaryMap = new HashMap<>(); /** * 生成关键词字典库 * @param words * @return */ public static void initMap(Collection<String> words) { if (words == null) { System.out.println("敏感词列表不能为空"); return ; } // map初始长度words.size()，整个字典库的入口字数(小于words.size()，因为不同的词可能会有相同的首字) Map<String, Object> map = new HashMap<>(words.size()); // 遍历过程中当前层次的数据 Map<String, Object> curMap; Iterator<String> iterator = words.iterator(); while (iterator.hasNext()) { String word = iterator.next(); curMap = map; int len = word.length(); //DFA算法,Deterministic Finite Automaton,即确定有穷自动机。 for (int i =0; i < len; i++) { // 遍历每个词的字 String key = String.valueOf(word.charAt(i)); // 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据 Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key); if (wordMap == null) { // 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志) wordMap = new HashMap<>(2); wordMap.put("isEnd", "0"); curMap.put(key, wordMap); } curMap = wordMap; // 如果当前字是词的最后一个字，则将isEnd标志置1 if (i == len -1) { curMap.put("isEnd", "1"); } } } dictionaryMap = map; } /** * 搜索文本中某个文字是否匹配关键词 * @param text * @param beginIndex * @return */ private static int checkWord(String text, int beginIndex) { if (dictionaryMap == null) { throw new RuntimeException("字典不能为空"); } boolean isEnd = false; int wordLength = 0; Map<String, Object> curMap = dictionaryMap; int len = text.length(); // 从文本的第beginIndex开始匹配 for (int i = beginIndex; i < len; i++) { String key = String.valueOf(text.charAt(i)); // 获取当前key的下一个节点 curMap = (Map<String, Object>) curMap.get(key); if (curMap == null) { break; } else { wordLength ++; if ("1".equals(curMap.get("isEnd"))) { isEnd = true; } } } if (!isEnd) { wordLength = 0; } return wordLength; } /** * 获取匹配的关键词和命中次数 * @param text * @return */ public static Map<String, Integer> matchWords(String text) { Map<String, Integer> wordMap = new HashMap<>(); int len = text.length(); for (int i = 0; i < len; i++) { int wordLength = checkWord(text, i); if (wordLength > 0) { String word = text.substring(i, i + wordLength); // 添加关键词匹配次数 if (wordMap.containsKey(word)) { wordMap.put(word, wordMap.get(word) + 1); } else { wordMap.put(word, 1); } i += wordLength - 1; } } return wordMap; } public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("张学友"); list.add("张学良"); list.add("叶良"); list.add("叶良辰"); initMap(list); String content="我是张学友，不是叶良， 更不是叶良辰"; Map<String, Integer> map = matchWords(content); System.out.println(map); //{叶良=1, 张学友=1, 叶良辰=1} } }
