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

2017/11/24 10:49

布隆过滤器 （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
"""
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

"""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

bf = Bloomfilter(10)
bf.print_contents()
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

分词

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

# enumerate() will give us (0, s[0]), (1, s[1]), ...
for idx, ch in enumerate(s):
if ch in major_breaks:
segment = s[last+1:idx]

last = idx

# The last character may not be a break so always capture
# the last segment (which may end up being "", but yolo)
segment = s[last+1:]

return results

] < > ( ) { } | ! ; , ' " * \n \r \s \t & ? + %21 %26 %2526 %3B %7C %20 %2B %3D -- %2520 %5D %5B %3A %0A %2C %28 %29

def minor_segments(s):
"""
Perform minor segmenting on a string.  This is like major
segmenting, except it also captures from the start of the
input to each break.
"""
minor_breaks = '_.'
last = -1
results = set()

for idx, ch in enumerate(s):
if ch in minor_breaks:
segment = s[last+1:idx]

segment = s[:idx]

last = idx

segment = s[last+1:]

return results

def segments(event):
"""Simple wrapper around major_segments / minor_segments"""
results = set()
for major in major_segments(event):
for minor in minor_segments(major):
return results

for term in segments('src_ip = 1.2.3.4'):
print term
src
1.2
1.2.3.4
src_ip
3
1
1.2.3
ip
2
=
4

搜索

class Splunk(object):
def __init__(self):
self.bf = Bloomfilter(64)
self.terms = {}  # Dictionary of term to set of events
self.events = []

"""Adds an event to this object"""

# Generate a unique ID for the event, and save it
event_id = len(self.events)
self.events.append(event)

# Add each term to the bloomfilter, and track the event by each term
for term in segments(event):

if term not in self.terms:
self.terms[term] = set()

def search(self, term):
"""Search for a single term, and yield all the events that contain it"""

# In Splunk this runs in O(1), and is likely to be in filesystem cache (memory)
if not self.bf.might_contain(term):
return

# In Splunk this probably runs in O(log N) where N is the number of terms in the tsidx
if term not in self.terms:
return

for event_id in sorted(self.terms[term]):
yield self.events[event_id]
• Splunk代表一个拥有搜索功能的索引集合
• 每一个集合中包含一个布隆过滤器，一个倒排词表（字典），和一个存储所有事件的数组
• 当一个事件被加入到索引的时候，会做以下的逻辑
• 为每一个事件生成一个unqie id，这里就是序号
• 对事件进行分词，把每一个词加入到倒排词表，也就是每一个词对应的事件的id的映射结构，注意，一个词可能对应多个事件，所以倒排表的的值是一个Set。倒排表是绝大部分搜索引擎的核心功能。
• 当一个词被搜索的时候，会做以下的逻辑
• 检查布隆过滤器，如果为假，直接返回
• 检查词表，如果被搜索单词不在词表中，直接返回
• 在倒排表中找到所有对应的事件id，然后返回事件的内容

s = Splunk()

for event in s.search('1.2.3.4'):
print event
print '-'
for event in s.search('src_ip'):
print event
print '-'
for event in s.search('ip'):
print event
src_ip = 1.2.3.4
dst_ip = 1.2.3.4
-
src_ip = 1.2.3.4
src_ip = 5.6.7.8
-
src_ip = 1.2.3.4
src_ip = 5.6.7.8
dst_ip = 1.2.3.4

更复杂的搜索

class SplunkM(object):
def __init__(self):
self.bf = Bloomfilter(64)
self.terms = {}  # Dictionary of term to set of events
self.events = []

"""Adds an event to this object"""

# Generate a unique ID for the event, and save it
event_id = len(self.events)
self.events.append(event)

# Add each term to the bloomfilter, and track the event by each term
for term in segments(event):
if term not in self.terms:
self.terms[term] = set()

def search_all(self, terms):
"""Search for an AND of all terms"""

results = set(range(len(self.events)))

for term in terms:
# If a term isn't present at all then we can stop looking
if not self.bf.might_contain(term):
return
if term not in self.terms:
return

# Drop events that don't match from our results
results = results.intersection(self.terms[term])

for event_id in sorted(results):
yield self.events[event_id]

def search_any(self, terms):
"""Search for an OR of all terms"""
results = set()

for term in terms:
# If a term isn't present, we skip it, but don't stop
if not self.bf.might_contain(term):
continue
if term not in self.terms:
continue

# Add these events to our results
results = results.union(self.terms[term])

for event_id in sorted(results):
yield self.events[event_id]

s = SplunkM()

for event in s.search_all(['src_ip', '5.6']):
print event
print '-'
for event in s.search_any(['src_ip', 'dst_ip']):
print event
src_ip = 5.6.7.8
-
src_ip = 1.2.3.4
src_ip = 5.6.7.8
dst_ip = 1.2.3.4

6
143 收藏

5 评论
143 收藏
6