如何在龐大的數(shù)據(jù)中高效的檢索自己需要的東西？本篇內(nèi)容介紹了Python做出一個大數(shù)據(jù)搜索引擎的原理和方法，以及中間進行數(shù)據(jù)分析的原理也給大家做了詳細介紹。

布隆過濾器 （Bloom Filter）
第一步我們先要實現(xiàn)一個布隆過濾器。

布隆過濾器是大數(shù)據(jù)領(lǐng)域的一個常見算法，它的目的是過濾掉那些不是目標的元素。也就是說如果一個要搜索的詞并不存在與我的數(shù)據(jù)中，那么它可以以很快的速度返回目標不存在。

讓我們看看以下布隆過濾器的代碼：

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

基本的數(shù)據(jù)結(jié)構(gòu)是個數(shù)組（實際上是個位圖，用1/0來記錄數(shù)據(jù)是否存在），初始化是沒有任何內(nèi)容，所以全部置False。實際的使用當中，該數(shù)組的長度是非常大的，以保證效率。

利用哈希算法來決定數(shù)據(jù)應(yīng)該存在哪一位，也就是數(shù)組的索引

當一個數(shù)據(jù)被加入到布隆過濾器的時候，計算它的哈希值然后把相應(yīng)的位置為True

當檢查一個數(shù)據(jù)是否已經(jīng)存在或者說被索引過的時候，只要檢查對應(yīng)的哈希值所在的位的True／Fasle

看到這里，大家應(yīng)該可以看出，如果布隆過濾器返回False，那么數(shù)據(jù)一定是沒有索引過的，然而如果返回True，那也不能說數(shù)據(jù)一定就已經(jīng)被索引過。在搜索過程中使用布隆過濾器可以使得很多沒有命中的搜索提前返回來提高效率。

我們看看這段 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 collidesfor term in ['dog', 'fish', 'cat', 'bird', 'duck', 'emu']:print '{}: {} {}'.format(term, bf.hash_value(term), bf.might_contain(term))

結(jié)果：

[False, False, False, False, True, True, False, False, False, True][False, False, False, False, True, True, False, False, False, True]dog: 5 Truefish: 4 Truecat: 9 Truebird: 9 Trueduck: 5 Trueemu: 8 False