文档章节

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

naughty
 naughty
发布于 2017/11/24 10:49
字数 2240
阅读 3174
收藏 143
点赞 5
评论 3

搜索是大数据领域里常见的需求。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

 

总结

以上的代码只是为了说明大数据搜索的基本原理,包括布隆过滤器,分词和倒排表。如果大家真的想要利用这代码来实现真正的搜索功能,还差的太远。所有的内容来自于Splunk Conf2017。大家如果有兴趣可以去看网上的视频。

© 著作权归作者所有

共有 人打赏支持
naughty
粉丝 232
博文 56
码字总数 94984
作品 0
其它
架构师
加载中

评论(3)

hlStack
hlStack
必须支持
singasong1995
singasong1995
支持一下��
电子工业出版社编辑
电子工业出版社编辑
赞!
Whoosh 原理与实战1--Python 搜索框架 Whoosh 简介

Whoosh 是一个纯 Python 编写的搜索框架,类似于Lucene。比较简单,可以快速构建站内搜索。也可以在此基础上构建搜索引擎,但需要自己扩展 爬虫Spider 和 中文分词组件。 Whoosh详细可以查看...

从前
2012/11/12
0
2
大数据分析挖掘学习方向?数据分析师的就业前景怎么样?

加米谷数据分析挖掘课程明细,从理论到云端实操环境到项目实战,手把手教您从0掌握数据分析与挖掘技术,带您走进数据时代。 第一阶段(python基础) python入门:1、Python版本特性介绍2、P...

加米谷大数据
04/17
0
0
6个最高效的语言处理Python库,你用过几个?

最近一段时间Python已经成为数据科学行业中大火的编程语言,今天技术学派收集了一些较为高效的语言处理Python库。下面分享给大家。 1.NLTK NLTK是构建Python程序以处理人类语言数据的领先平台...

Python燕大侠
06/05
0
0
聊聊python爬虫开发入门的必备技能

关于爬虫,相信有不少同学都接触过。譬如你通过百度搜索“慕课网”,然后跳转到慕课网的首页,这里你访问的百度首页就用到了爬虫技术,它把慕课网的首页源代码爬取到了搜索引擎服务器中,进行...

NavCat
07/02
0
0
详解Python开发的发展方向及其对应的薪资!

百度CEO曾表述:靠移动互联网的风口现已没有可能再出现独角兽了,由于市场现已进入了一个相对平稳的发展阶段,互联网人口渗透率现已超过了50%。而未来的机会在人工智能。确实互联网巨头公司在...

Python燕大侠
05/06
0
0
大数据开发学习的内容介绍,成都大数据培训机构哪里好?

大数据开发培训已经成为了越来越多人的选择,大数据开发工程师也是各公司争相争夺的金领人才之一了,在当今科技发展非常迅速的社会里,越来越多人把职业规划投向了大数据开发。这里为大家整理...

加米谷大数据
07/17
0
0
Python 2 和 Python 3 有哪些主要区别?

语法 print不再是语句,而是函数,比如原来是 print 'abc' 现在是 print('abc') 但是 python2.6+ 可以使用 from future import print_function 来实现相同功能 在Python 3中,没有旧式类,只...

cooffeelis
03/05
0
0
Python开发(基础):初识Python

Python可以应用于众多领域,如:数据分析、组件集成、网络服务、图像处理、数值计算和科学计算等众多领域。目前业内几乎所有大中型互联网企业都在使用Python,如:Youtube、Dropbox、BT、Quo...

wbb827
07/03
0
0
如何使用tensorflow做张量排序和字符串拼接?

欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定! 对商业智能BI、大数据分析挖掘、机器学习,python,R等数据领域感兴...

天善智能
07/17
0
0
大数据、java、Python、区块链、人工智能哪个发展前景刚好?

在这个信息时代高速发展的情况下,很多人会对自己该往哪个方向发展感到迷茫,下面我就浅显的给大家介绍一下五大流行区域的发展前景。 大数据的发展前景: 当前大数据行业真的是人才稀缺吗? 学...

琳达老师
06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
41分钟前
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
52分钟前
2
0
将博客搬至CSDN

AHUSKY
今天
1
0
Python web框架Django学习(1)

1.Django简介 (1)Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。Django是一个开放源代码的Web应用框架,由Python写成。 (2...

十年磨一剑3344
今天
0
0
Databook-数据之书

Databook-数据之书 用于数据分析的Jupyter Notebooks。 不需购买服务器,快速开始自己的数据分析过程。 源码:https://github.com/openthings/databook 作者:openthings,https://github.co...

openthings
今天
5
0
Python PIPEs

https://www.python-course.eu/pipes.php https://www.tutorialspoint.com/python/os_pipe.htm

zungyiu
今天
1
0
gRPC学习笔记

gRPC编程流程 1. proto文件定义 proto文件用于定义需要通过gRPC生成的接口,可以理解为接口定义文档 2. 通过构建工具生成服务基类代码-Maven或Gradle 3. 服务端开发 服务端实现类须实现通过构...

OSC_fly
今天
0
0
Docker Mac (三) Dockerfile 及命令

Dockerfile 最近学习docker的时候,遇到一件怪事,关于docker镜像可能会被破坏,还不知道它会有此措施 所以需要了解构建Dockerfile的正确方法 Dockerfile是由一系列命令和参数构成的脚本,这些命...

___大侠
今天
0
0
Android Studio+NDK+Cmake 移植FFmpeg-4.0.2命令行工具

一、编译 参考大神的帖子,亲测一次编译成功:https://blog.csdn.net/bobcat_kay/article/details/80889398 鉴于以前查文档的经验,这里附上编写例子的时间:2018年7月22日 我用的是ubantu,...

她叫我小渝
今天
0
0
mysql创建数据库

登录MYSQL mysql -u root -p 脚本创建数据库WeChat,并制定默认的字符集是utf8mb4。 CREATE DATABASE Wechat DEFAULT CHARSET utf8mb4 COLLATE utf8mb4_general_ci; 授权 grant all......

niithub
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部