`
kabike
  • 浏览: 599373 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics