基于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’三个工具，这时的布隆过滤器的内容如下：

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!