Python搜索引擎实现原理和方法

如何在庞大的数据中高效的检索自己需要的东西？本篇内容介绍了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 collidesfor 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 Truefish: 4 Truecat: 9 Truebird: 9 Trueduck: 5 Trueemu: 8 False