基于Python语言的大数据搜索引擎

搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的Python代码实现了一个基本的数据搜索功能，试图让大家理解大数据搜索的基本原理。

布隆过滤器 (Bloom Filter)

第一步我们先要实现一个布隆过滤器。

布隆过滤器是大数据领域的一个常见算法，它的目的是过滤掉那些不是目标的元素。也就是说如果一个要搜索的词并不存在与我的数据中，那么它可以以很快的速度返回目标不存在。

让我们看看以下布隆过滤器的代码：

class Bloomfilter(object): 
 """ 
 A Bloom filter is a probabilistic data-structure that trades space for accuracy 
 when determining if a value is in a set. It can tell you if a value was possibly 
 added, or if it was definitely not added, but it can't tell you for certain that 
 it was added. 
 """ 
 def __init__(self, size): 
 """Setup the BF with the appropriate size""" 
 self.values = [False] * size 
 self.size = size 
 def hash_value(self, value): 
 """Hash the value provided and scale it to fit the BF size""" 
 return hash(value) % self.size 
 def add_value(self, value): 
 """Add a value to the BF""" 
 h = self.hash_value(value) 
 self.values[h] = True 
 def might_contain(self, value): 
 """Check if the value might be in the BF""" 
 h = self.hash_value(value) 
 return self.values[h] 
 def print_contents(self): 
 """Dump the contents of the BF for debugging purposes""" 
 print self.values 

• 基本的数据结构是个数组(实际上是个位图，用1/0来记录数据是否存在)，初始化是没有任何内容，所以全部置False。实际的使用当中，该数组的长度是非常大的，以保证效率。
• 利用哈希算法来决定数据应该存在哪一位，也就是数组的索引
• 当一个数据被加入到布隆过滤器的时候，计算它的哈希值然后把相应的位置为True
• 当检查一个数据是否已经存在或者说被索引过的时候，只要检查对应的哈希值所在的位的True/Fasle

看到这里，大家应该可以看出，如果布隆过滤器返回False，那么数据一定是没有索引过的，然而如果返回True，那也不能说数据一定就已经被索引过。在搜索过程中使用布隆过滤器可以使得很多没有命中的搜索提前返回来提高效率。

我们看看这段 code是如何运行的：

bf = Bloomfilter(10) 
bf.add_value('dog') 
bf.add_value('fish') 
bf.add_value('cat') 
bf.print_contents() 
bf.add_value('bird') 
bf.print_contents() 
# Note: contents are unchanged after adding bird - it collides 
for term in ['dog', 'fish', 'cat', 'bird', 'duck', 'emu']: 
 print '{}: {} {}'.format(term, bf.hash_value(term), bf.might_contain(term)) 

结果：

[False, False, False, False, True, True, False, False, False, True] 
[False, False, False, False, True, True, False, False, False, True] 
dog: 5 True 
fish: 4 True 
cat: 9 True 
bird: 9 True 
duck: 5 True 
emu: 8 False 

首先创建了一个容量为10的的布隆过滤器

然后分别加入 ‘dog’，‘fish’，‘cat’三个对象，这时的布隆过滤器的内容如下：

（编辑：ASP站长网）