BloomFilter和trie
记录下最近刚刚了解到了两种数据结构BloomFilter和trie
trie:
有一天,有个同学问了个问题,假设有个敏感词列表["敏感词1","敏感词2","敏感词3","敏感词4"],
如何快速判断一组字符串的每个字符串是否包含了所有的敏感词.
这要是用双重for循环,contains那套方法,估计都能跑死.所以我当时想到了把敏感词列表预先做成自动机.然后循环一遍
字符串数组.不过怎么构造那个自动机呢,后来那同学提到了trie的概念.trie可以用来实现高速的字符串匹配.这是典型的空间换时间
具体可以看http://en.wikipedia.org/wiki/Trie
BloomFilter:
BloomFilter是做hadoop semijoin时发现的,它的思路是用容错率来换空间.就像一个hashset,只是BloomFilter有一定的不准确性.
具体可以看http://en.wikipedia.org/wiki/Bloom_filter
