用Python实现一个大数据搜索引擎
搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的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 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
首先创建了一个容量为10的的布隆过滤器
然后分别加入 ‘dog’，‘fish’，‘cat’三个对象，这时的布隆过滤器的内容如下：
然后加入‘bird’对象，布隆过滤器的内容并没有改变，因为‘bird’和‘fish’恰好拥有相同的哈希。
最后我们检查一堆对象（’dog’, ‘fish’, ‘cat’, ‘bird’, ‘duck’, ’emu’）是不是已经被索引了。结果发现‘duck’返回True，2而‘emu’返回False。因为‘duck’的哈希恰好和‘dog’是一样的。
分词
下面一步我们要实现分词。 分词的目的是要把我们的文本数据分割成可搜索的最小单元，也就是词。这里我们主要针对英语，因为中文的分词涉及到自然语言处理，比较复杂，而英文基本只要用标点符号就好了。
下面我们看看分词的代码：
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]
results.add(segment)
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:]
results.add(segment)
return results
主要分割
主要分割使用空格来分词，实际的分词逻辑中，还会有其它的分隔符。例如Splunk的缺省分割符包括以下这些，用户也可以定义自己的分割符。
] < >( ) { } | ! ; , ‘ ” * \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]
results.add(segment)
segment = s[:idx]
results.add(segment)
last = idx
segment = s[last+1:]
results.add(segment)
results.add(s)
return results
次要分割
次要分割和主要分割的逻辑类似，只是还会把从开始部分到当前分割的结果加入。例如“1.2.3.4”的次要分割会有1，2，3，4，1.2，1.2.3
def segments(event):
"""Simple wrapper around major_segments / minor_segments"""
results = set()
for major in major_segments(event):
for minor in minor_segments(major):
results.add(minor)
return results
分词的逻辑就是对文本先进行主要分割，对每一个主要分割在进行次要分割。然后把所有分出来的词返回。
我们看看这段 code是如何运行的：
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 = []
def add_event(self, event):
"""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):
self.bf.add_value(term)
if term not in self.terms:
self.terms[term] = set()
self.terms[term].add(event_id)
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()
s.add_event('src_ip = 1.2.3.4')
s.add_event('src_ip = 5.6.7.8')
s.add_event('dst_ip = 1.2.3.4')
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
是不是很赞！
更复杂的搜索
更进一步，在搜索过程中，我们想用And和Or来实现更复杂的搜索逻辑。
上代码：
class SplunkM(object):
def __init__(self):
self.bf = Bloomfilter(64)
self.terms = {} # Dictionary of term to set of events
self.events = []
def add_event(self, event):
"""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):
self.bf.add_value(term)
if term not in self.terms:
self.terms[term] = set()
self.terms[term].add(event_id)
def search_all(self, terms):
"""Search for an AND of all terms"""
# Start with the universe of all events...
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]
利用Python集合的intersection和union操作，可以很方便的支持And（求交集）和Or（求合集）的操作。
运行结果如下：
s = SplunkM()
s.add_event('src_ip = 1.2.3.4')
s.add_event('src_ip = 5.6.7.8')
s.add_event('dst_ip = 1.2.3.4')
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
数据分析咨询请扫描二维码
若不方便扫码，搜微信号：CDAshujufenxi
数据分析在当今信息时代发挥着重要作用。单因素方差分析（One-Way ANOVA）是一种关键的统计方法，用于比较三个或更多独立样本组 ...
2025-04-25CDA持证人简介： 居瑜 ，CDA一级持证人国企财务经理，13年财务管理运营经验，在数据分析就业和实践经验方面有着丰富的积累和经 ...
2025-04-25在当今数字化时代，数据分析师的重要性与日俱增。但许多人在踏上这条职业道路时，往往充满疑惑： 如何成为一名数据分析师？成为 ...
2025-04-24以下的文章内容来源于刘静老师的专栏，如果您想阅读专栏《刘静：10大业务分析模型突破业务瓶颈》，点击下方链接 https://edu.cda ...
2025-04-23大咖简介： 刘凯，CDA大咖汇特邀讲师，DAMA中国分会理事，香港金管局特聘数据管理专家，拥有丰富的行业经验。本文将从数据要素 ...
2025-04-22CDA持证人简介 刘伟，美国 NAU 大学计算机信息技术硕士， CDA数据分析师三级持证人，现任职于江苏宝应农商银行数据治理岗。 学 ...
2025-04-21持证人简介：贺渲雯 ，CDA 数据分析师一级持证人，互联网行业数据分析师 今天我将为大家带来一个关于用户私域用户质量数据分析 ...
2025-04-18一、CDA持证人介绍 在数字化浪潮席卷商业领域的当下，数据分析已成为企业发展的关键驱动力。为助力大家深入了解数据分析在电商行 ...
2025-04-17CDA持证人简介：居瑜 ，CDA一级持证人，国企财务经理，13年财务管理运营经验，在数据分析实践方面积累了丰富的行业经验。 一、 ...
2025-04-16持证人简介： CDA持证人刘凌峰，CDA L1持证人，微软认证讲师（MCT）金山办公最有价值专家（KVP），工信部高级项目管理师，拥有 ...
2025-04-15持证人简介：CDA持证人黄葛英，ICF国际教练联盟认证教练，前字节跳动销售主管，拥有丰富的行业经验。在实际生活中，我们可能会 ...
2025-04-14在 Python 编程学习与实践中，Anaconda 是一款极为重要的工具。它作为一个开源的 Python 发行版本，集成了众多常用的科学计算库 ...
2025-04-14随着大数据时代的深入发展，数据运营成为企业不可或缺的岗位之一。这个职位的核心是通过收集、整理和分析数据，帮助企业做出科 ...
2025-04-11持证人简介：CDA持证人黄葛英，ICF国际教练联盟认证教练，前字节跳动销售主管，拥有丰富的行业经验。 本次分享我将以教培行业为 ...
2025-04-11近日《2025中国城市长租市场发展蓝皮书》（下称《蓝皮书》）正式发布。《蓝皮书》指出，当前我国城市住房正经历从“增量扩张”向 ...
2025-04-10在数字化时代的浪潮中，数据已经成为企业决策和运营的核心。每一位客户，每一次交易，都承载着丰富的信息和价值。 如何在海量客 ...
2025-04-09数据是数字化的基础。随着工业4.0的推进，企业生产运作过程中的在线数据变得更加丰富；而互联网、新零售等C端应用的丰富多彩，产 ...
2025-04-094月7日，美国关税政策对全球金融市场的冲击仍在肆虐，周一亚市早盘，美股股指、原油期货、加密货币、贵金属等资产齐齐重挫，市场 ...
2025-04-08背景 3月26日，科技圈迎来一则重磅消息，苹果公司宣布向浙江大学捐赠 3000 万元人民币，用于支持编程教育。 这一举措并非偶然， ...
2025-04-07在当今数据驱动的时代，数据分析能力备受青睐，数据分析能力频繁出现在岗位需求的描述中，不分岗位的任职要求中，会特意标出“熟 ...
2025-04-03
