前缀树

前缀树的3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

前缀树实现敏感词过滤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
    "傻": {
        "逼": {
            "isEnd": "Y"
        },
        "子": {
            "isEnd": "Y"
        },
        "大": {
            "个": {
                "isEnd": "Y"
            }
        }
    }
}

树结构：

1
2
3
4
5
6
7
8
9
private static class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEnd;

        TrieNode() {
            children = new HashMap<>();
            isEnd = false;
        }
    }

前缀树的创建

好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建trie树就得到

img

1
2
3
4
5
6
7
8
private static void insertWord(String word) {
       TrieNode node = root;
       for (char c : word.toCharArray()) {
           node.children.computeIfAbsent(c, k -> new TrieNode());
           node = node.children.get(c);
       }
       node.isEnd = true;
   }

搜索文本中匹配的敏感词

1
2
3
4
5
6
7
8
9
10
11
12
13
public static List<String> matchWords(String text) {
        List<String> sensitiveWords = new ArrayList<>();
        int len = text.length();
        for (int i = 0; i < len; i++) {
            int wordLen = checkWord(text, i);
            if (wordLen > 0) {
                String word = text.substring(i, i + wordLen);
                sensitiveWords.add(word);
                i += wordLen - 1;
            }
        }
        return sensitiveWords;
    }

前缀树测试敏感词过滤

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
        insertWord("你是傻逼");
        insertWord("你是傻逼啊");
        insertWord("你是坏蛋");
        insertWord("你个大笨蛋");
        insertWord("我去年买了个表");
        insertWord("shit");,
        System.out.println(matchWords("你你你你是傻逼啊你，说你呢，你个大笨蛋。"));
    }

image-20231014231254498

虽然简单实现了但却很容易被破解，比如说，我在待检测文本中的敏感词中间加个空格，就可以成功绕过了。要解决这个问题也不难，有一个简单的方法是初始化一个无效字符库，比如：空格、*、#、@等字符，然后在检测文本前，先将待检测文本中的无效字符去除，这样的话被检测字符就不存在这些无效字符了，
如果敏感词是英文，则还要考虑大小写的问题。有一个比较简单的解决方案是在初始化敏感词时，将敏感词都以小写形式存储。同时，在检测文本时，也统一将待检测文本转化为小写，这样就能解决大小写的问题了。
比较棘手的是中文跟拼音混合的情况，比如“傻逼”这个敏感词，可以通过“sha逼”这种中文跟拼音混合的方式轻松绕过。

布隆过滤器

布隆过滤器的典型应用有：

  • 数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
  • 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
  • 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
  • WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务
  • Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
  • SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

原理

程序根据实际情况实现hash函数，将要添加的元素进行Hash计算得到的hash值金进行对应填充到bitmap中

不同的字符串可能哈希出来的位置相同，这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

综上，我们可以得出：布隆过滤器说某个元素存在，小概率会误判（也许不存在）。但是布隆过滤器说某个元素不在，那么这个元素一定不在。

Bloom Filter 的简单原理示意图

简单实现

看过HashSet源码的都知道，hashSet就是基于HashMap来实现的，我们可以仿照HashSet的实现来实现一个简单的布隆过滤器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Bloom{
        private  Object object = new Object();

        HashMap<String, Object> BloomMap = new HashMap<>();

        public void SetBloom(String[] keys) {
            for(String s : keys) BloomMap.put(s,object);
        }

    	public boolean contain(String key) {
        	return BloomMap.put(key,object) != null;
    	}

    }
1
2
3
4
5
6
public static void main(String[] args) {
        Bloom bloom =  new Bloom();
        bloom.SetBloom(new String[]{"123","abc","test"});
        System.out.println(bloom.contain("12345")); // false
        System.out.println(bloom.contain("test")); // true
    }