搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的Python代码实现了一个基本的数据搜索功能，试图让大家理解大数据搜索的基本原理。
学习Python中有不明白推荐加入交流群
号：960410445
群里有志同道合的小伙伴，互帮互助，
群里有不错的视频学习教程和PDF！
布隆过滤器 （Bloom Filter）
第一步我们先要实现一个布隆过滤器。
布隆过滤器是大数据领域的一个常见算法，它的目的是过滤掉那些不是目标的元素。也就是说如果一个要搜索的词并不存在与我的数据中，那么它可以以很快的速度返回目标不存在。
让我们看看以下布隆过滤器的代码：
classBloomfilter(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 """8def__init__(self, size):9"""Setup the BF with the appropriate size"""10self.values = [False] * size11self.size = size1213defhash_value(self, value):14"""Hash the value provided and scale it to fit the BF size"""15returnhash(value) % self.size1617defadd_value(self, value):18"""Add a value to the BF"""19h = self.hash_value(value)20self.values[h] =True2122defmight_contain(self, value):23"""Check if the value might be in the BF"""24h = self.hash_value(value)25returnself.values[h]2627defprint_contents(self):28"""Dump the contents of the BF for debugging purposes"""29printself.values
1基本的数据结构是个数组（实际上是个位图，用1/0来记录数据是否存在），初始化是没有任何内容，所以全部置False。实际的使用当中，该数组的长度是非常大的，以保证效率。
2利用哈希算法来决定数据应该存在哪一位，也就是数组的索引
3当一个数据被加入到布隆过滤器的时候，计算它的哈希值然后把相应的位置为True
4当检查一个数据是否已经存在或者说被索引过的时候，只要检查对应的哈希值所在的位的True／Fasle
看到这里，大家应该可以看出，如果布隆过滤器返回False，那么数据一定是没有索引过的，然而如果返回True，那也不能说数据一定就已经被索引过。在搜索过程中使用布隆过滤器可以使得很多没有命中的搜索提前返回来提高效率。
我们看看这段 code是如何运行的：
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()8#Note:contents are unchanged after adding bird - it collides9fortermin['dog','fish','cat','bird','duck','emu']:10print'{}: {} {}'.format(term,bf.hash_value(term),bf.might_contain(term))1112结果：1314[False,False,False,False,True,True,False,False,False,True]15[False,False,False,False,True,True,False,False,False,True]16dog:5True17fish:4True18cat:9True19bird:9True20duck:5True21emu:8False
首先创建了一个容量为10的的布隆过滤器
然后分别加入 ‘dog’，‘fish’，‘cat’三个对象，这时的布隆过滤器的内容如下：
然后加入‘bird’对象，布隆过滤器的内容并没有改变，因为‘bird’和‘fish’恰好拥有相同的哈希。
最后我们检查一堆对象（'dog', 'fish', 'cat', 'bird', 'duck', 'emu'）是不是已经被索引了。结果发现‘duck’返回True，2而‘emu’返回False。因为‘duck’的哈希恰好和‘dog’是一样的。
分词
下面一步我们要实现分词。 分词的目的是要把我们的文本数据分割成可搜索的最小单元，也就是词。这里我们主要针对英语，因为中文的分词涉及到自然语言处理，比较复杂，而英文基本只要用标点符号就好了。
下面我们看看分词的代码：
1defmajor_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 """8major_breaks =' '9last =-110results = set()1112# enumerate() will give us (0, s[0]), (1, s[1]), ...13foridx, chinenumerate(s):14ifchinmajor_breaks:15segment = s[last+1:idx]16results.add(segment)1718last = idx1920# The last character may not be a break so always capture21# the last segment (which may end up being "", but yolo) 22segment = s[last+1:]23results.add(segment)2425returnresults
主要分割
主要分割使用空格来分词，实际的分词逻辑中，还会有其它的分隔符。例如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 """ 9 minor_breaks = '_.'10 last = -111 results = set()1213 for idx, ch in enumerate(s):14 if ch in minor_breaks:15 segment = s[last+1:idx]16 results.add(segment)1718 segment = s[:idx]19 results.add(segment)2021 last = idx2223 segment = s[last+1:]24 results.add(segment)25 results.add(s)2627 return results28
次要分割
次要分割和主要分割的逻辑类似，只是还会把从开始部分到当前分割的结果加入。例如“1.2.3.4”的次要分割会有1，2，3，4，1.2，1.2.3
1def segments(event):2 """Simple wrapper around major_segments / minor_segments"""3 results = set()4 formajor in major_segments(event):5 forminor in minor_segments(major):6 results.add(minor)7 returnresults
分词的逻辑就是对文本先进行主要分割，对每一个主要分割在进行次要分割。然后把所有分出来的词返回。
我们看看这段 code是如何运行的：
1for term in segments('src_ip = 1.2.3.4'):2printterm34src51.261.2.3.47src_ip8391101.2.311ip12213=144
搜索
好了，有个分词和布隆过滤器这两个利器的支撑后，我们就可以来实现搜索的功能了。
上代码：
1classSplunk(object):2def__init__(self):3self.bf = Bloomfilter(64)4self.terms = {}# Dictionary of term to set of events5self.events = []67defadd_event(self, event):8"""Adds an event to this object"""910# Generate a unique ID for the event, and save it11event_id = len(self.events)12self.events.append(event)1314# Add each term to the bloomfilter, and track the event by each term15forterminsegments(event):16self.bf.add_value(term)1718iftermnotinself.terms:19self.terms[term] = set()20self.terms[term].add(event_id)2122defsearch(self, term):23"""Search for a single term, and yield all the events that contain it"""2425# In Splunk this runs in O(1), and is likely to be in filesystem cache (memory)26ifnotself.bf.might_contain(term):27return2829# In Splunk this probably runs in O(log N) where N is the number of terms in the tsidx30iftermnotinself.terms:31return3233forevent_idinsorted(self.terms[term]):34yieldself.events[event_id]1Splunk代表一个拥有搜索功能的索引集合2每一个集合中包含一个布隆过滤器，一个倒排词表（字典），和一个存储所有事件的数组3当一个事件被加入到索引的时候，会做以下的逻辑4为每一个事件生成一个unqie id，这里就是序号5对事件进行分词，把每一个词加入到倒排词表，也就是每一个词对应的事件的id的映射结构，注意，一个词可能对应多个事件，所以倒排表的的值是一个Set。倒排表是绝大部分搜索引擎的核心功能。6当一个词被搜索的时候，会做以下的逻辑7检查布隆过滤器，如果为假，直接返回8检查词表，如果被搜索单词不在词表中，直接返回9在倒排表中找到所有对应的事件id，然后返回事件的内容
我们运行下看看把：
1s = Splunk()2s.add_event('src_ip = 1.2.3.4')3s.add_event('src_ip = 5.6.7.8')4s.add_event('dst_ip = 1.2.3.4')56foreventins.search('1.2.3.4'):7printevent8print'-'9foreventins.search('src_ip'):10printevent11print'-'12foreventins.search('ip'):13printevent1415src_ip =1.2.3.416dst_ip =1.2.3.417-18src_ip =1.2.3.419src_ip =5.6.7.820-21src_ip =1.2.3.422src_ip =5.6.7.823dst_ip =1.2.3.42425是不是很赞！26更复杂的搜索2728更进一步，在搜索过程中，我们想用And和Or来实现更复杂的搜索逻辑。2930上代码：3132classSplunkM(object):33def__init__(self):34self.bf = Bloomfilter(64)35self.terms = {}# Dictionary of term to set of events36self.events = []3738defadd_event(self, event):39"""Adds an event to this object"""4041# Generate a unique ID for the event, and save it42event_id = len(self.events)43self.events.append(event)4445# Add each term to the bloomfilter, and track the event by each term46forterminsegments(event):47self.bf.add_value(term)48iftermnotinself.terms:49self.terms[term] = set()5051self.terms[term].add(event_id)5253defsearch_all(self, terms):54"""Search for an AND of all terms"""5556# Start with the universe of all events...57results = set(range(len(self.events)))5859forterminterms:60# If a term isn't present at all then we can stop looking61ifnotself.bf.might_contain(term):62return63iftermnotinself.terms:64return6566# Drop events that don't match from our results67results = results.intersection(self.terms[term])6869forevent_idinsorted(results):70yieldself.events[event_id]717273defsearch_any(self, terms):74"""Search for an OR of all terms"""75results = set()7677forterminterms:78# If a term isn't present, we skip it, but don't stop79ifnotself.bf.might_contain(term):80continue81iftermnotinself.terms:82continue8384# Add these events to our results85results = results.union(self.terms[term])8687forevent_idinsorted(results):88yieldself.events[event_id]
利用Python集合的intersection和union操作，可以很方便的支持And（求交集）和Or（求合集）的操作。
运行结果如下：
1s= SplunkM()2s.add_event('src_ip = 1.2.3.4')3s.add_event('src_ip = 5.6.7.8')4s.add_event('dst_ip = 1.2.3.4')56for event in s.search_all(['src_ip','5.6']):7printevent8print'-'9for event in s.search_any(['src_ip','dst_ip']):10printevent1112src_ip =5.6.7.813-14src_ip =1.2.3.415src_ip =5.6.7.816dst_ip =1.2.3.4
总结
以上的代码只是为了说明大数据搜索的基本原理，包括布隆过滤器，分词和倒排表。如果大家真的想要利用这代码来实现真正的搜索功能，还差的太远。
网友评论