用Python实现一个大数据搜索引擎

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

01

布隆过滤器 (Bloom Filter)

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

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

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

1class Bloomfilter(object):
2    """
3    A Bloom filter is a probabilistic data-structure that trades space for accuracy
4    when determining if a value is in a set.  It can tell you if a value was possibly
5    added, or if it was definitely not added, but it can't tell you for certain that
6    it was added.
7    """

8    def __init__(self, size):
9        """Setup the BF with the appropriate size"""
10        self.values = [False] * size
11        self.size = size
12
13    def hash_value(self, value):
14        """Hash the value provided and scale it to fit the BF size"""
15        return hash(value) % self.size
16
17    def add_value(self, value):
18        """Add a value to the BF"""
19        h = self.hash_value(value)
20        self.values[h] = True
21
22    def might_contain(self, value):
23        """Check if the value might be in the BF"""
24        h = self.hash_value(value)
25        return self.values[h]
26
27    def print_contents(self):
28        """Dump the contents of the BF for debugging purposes"""
29        print self.values

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

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

我们看看这段代码是如何运行的:

1bf = Bloomfilter(10)
2bf.add_value('dog')
3bf.add_value('fish')
4bf.add_value('cat')
5bf.print_contents()
6bf.add_value('bird')
7bf.print_contents()
8Note: contents are unchanged after adding bird - it collides
9for term in ['dog''fish''cat''bird''duck''emu']:
10    print '{}: {} {}'.format(term, bf.hash_value(term), bf.might_contain(term))

结果:

14[FalseFalseFalseFalseTrueTrueFalseFalseFalseTrue]
15[FalseFalseFalseFalseTrueTrueFalseFalseFalseTrue]
16dog: 5 True
17fish: 4 True
18cat: 9 True
19bird: 9 True
20duck: 5 True
21emu: 8 False

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

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

然后加入‘bird’对象,布隆过滤器的内容并没有改变,因为‘bird’和‘fish’恰好拥有相同的哈希。

最后我们检查一堆对象('dog', 'fish', 'cat', 'bird', 'duck', 'emu')是不是已经被索引了。结果发现‘duck’返回True,2而‘emu’返回False。因为‘duck’的哈希恰好和‘dog’是一样的。

02

分词

下面一步我们要实现分词。 分词的目的是要把我们的文本数据分割成可搜索的最小单元,也就是词。这里我们主要针对英语,因为中文的分词涉及到自然语言处理,比较复杂,而英文基本只要用标点符号就好了。

下面我们看看分词的代码:

1def major_segments(s):
2    """
3    Perform major segmenting on a string.  Split the string by all of the major
4    breaks, and return the set of everything found.  The breaks in this implementation
5    are single characters, but in Splunk proper they can be multiple characters.
6    A set is used because ordering doesn't matter, and duplicates are bad.
7    """

8    major_breaks = ' '
9    last = -1
10    results = set()
11
12    # enumerate() will give us (0, s[0]), (1, s[1]), ...
13    for idx, ch in enumerate(s):
14        if ch in major_breaks:
15            segment = s[last+1:idx]
16            results.add(segment)
17
18            last = idx
19
20    # The last character may not be a break so always capture
21    # the last segment (which may end up being "", but yolo)    
22    segment = s[last+1:]
23    results.add(segment)
24
25    return results

  • 主要分割

主要分割使用空格来分词,实际的分词逻辑中,还会有其它的分隔符。例如Splunk的缺省分割符包括以下这些,用户也可以定义自己的分割符。

1] < > ( ) { } | ! ; , ' " * \n \r \s \t & ? + %21 %26 %2526 %3B %7C %20 %2B %3D -- %2520 %5D %5B %3A %0A %2C %28 %29
2
3def minor_segments(s):
4    """
5    Perform minor segmenting on a string.  This is like major
6    segmenting, except it also captures from the start of the
7    input to each break.
8    """