




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
牛耳薮肓件■国互联网前沿技术人才摇篮用Python实现一个大数据搜素引擎搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的Python代码实现了一个基本的数据搜索功能,试图让大家理解大数据搜索的基本原理。布隆过滤器(BloomFilter)第一步我们先要实现一个布隆过滤器。布隆过滤器是大数据领域的一个常见算法,它的目的是过滤掉那些不是目标的元素。也就是说如果一个要搜索的词并不存在与我的数据中,那么它可以以很快的速度返回目标不存在。让我们看看以下布隆过滤器的代码:classBloomfilter(object):件■国互联网前沿技术人才摇篮ABloomfilterisaprobabilisticdata-structurethattradesspaceforaccuracywhendeterminingifavalueisinaset.Itcantellyouifavaluewaspossiblyadded,orifitwasdefinitelynotadded,butitcan'ttellyouforcertainthatitwasadded.def__init__(self,size):"SetuptheBFwiththeappropriatesize""”self.values=[False]*sizeself.size=sizedefhash_value(self,value):"""HashthevalueprovidedandscaleittofittheBFsize"""returnhash(value)%self.size件■国互联网前沿技术人才摇篮defadd_value(self,value):AddavaluetotheBF"h=self.hash_value(value)self.values[h]=Truedefmight_contain(self,value):"""CheckifthevaluemightbeintheBF""”h=self.hash_value(value)returnself.values[h]defprint_contents(self):"""DumpthecontentsoftheBFfordebuggingpurposes""”printself.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:contentsareunchangedafteraddingbird-itcollidesfortermin['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:5Truefish:4Truecat:9Truebird:9Trueduck:5Trueemu:8False首先创建了一个容量为10的的布隆过滤器用国互联网前沿技术人才摧篮牛耳我盲然后分别加入‘dog’,‘fish’,‘cat’三个对象,这时的布隆过滤器的内容如下:用国互联网前沿技术人才摧篮牛耳我盲然后加入‘bird’对象,布隆过滤器的内容并没有改变,因为‘bird’和‘fish’恰好拥有相同的哈希。
件■国互联网前沿技术人才摇篮最后我们检查一堆对象(’dog’,‘fish’,‘cat’,‘bird’,‘duck’,’emu’)是不是已经被索引了。结果发现’duck’返回True,2而’emu’返回False。因为’duck’的哈希恰好和‘dog’是一样的。用国互联网前沿技术人才摇篮分词下面一步我们要实现分词。分词的目的是要把我们的文本数据分割成可搜索的最小单元,也就是词。这里我们主要针对英语,因为中文的分词涉及到自然语言处理,比较复杂,而英文基本只要用标点符号就好了。下面我们看看分词的代码:defmajor_segments(s):件■国互联网前沿技术人才摇篮Performmajorsegmentingonastring.Splitthestringbyallofthemajorbreaks,andreturnthesetofeverythingfound.Thebreaksinthisimplementationaresinglecharacters,butinSplunkpropertheycanbemultiplecharacters.Asetisusedbecauseorderingdoesn'tmatter,andduplicatesarebad.major_breaks=''last=-1results=set()#enumerate()willgiveus(0,s[0]),(1,s[1]),...foridx,chinenumerate(s):ifchinmajor_breaks:件■国互联网前沿技术人才摇篮segment=s[last+1:idx]results.add(segment)last=idx#Thelastcharactermaynotbeabreaksoalwayscapture#thelastsegment(whichmayendupbeing"",butyolo)segment=s[last+1:]results.add(segment)returnresults主要分割主要分割使用空格来分词,实际的分词逻辑中,还会有其它的分隔符。例如Splunk的缺省分割符包括以下这些,用户也可以定义自己的分割符。件■国互联网前沿技术人才摇篮]<>(){}|!;,‘"*s&?+%21%26%2526%3B%7C%20%2B%3D—%2520%5D%5B%3A%0A%2C%28%29defminor_segments(s):"""Performminorsegmentingonastring.Thisislikemajorsegmenting,exceptitalsocapturesfromthestartoftheinputtoeachbreak."""minor_breaks='_.'last=-1results=set()foridx,chinenumerate(s):ifchinminorbreaks:件■国互联网前沿技术人才摇篮segment=s[last+1:idx]results.add(segment)segment=s[:idx]results.add(segment)last=idxsegment=s[last+1:]results.add(segment)results.add(s)returnresults次要分割件■国互联网前沿技术人才摇篮次要分割和主要分割的逻辑类似,只是还会把从开始部分到当前分割的结果加入。例如""的次要分割会有1,2,3,4,1.2,1.2.3defsegments(event):Simplewrapperaroundmajor_segments/minor_segmentsresults=set()formajorinmajor_segments(event):forminorinminor_segments(major):results.add(minor)returnresults分词的逻辑就是对文本先进行主要分割,对每一个主要分割在进行次要分割。然后把所有分出来的词返回。我们看看这段code是如何运行的:件■国互联网前沿技术人才摇篮forterminsegments('src_ip='):printtermsrc.4src_ip1.2.3ip件■国互联网前沿技术人才摇篮搜索好了,有个分词和布隆过滤器这两个利器的支撑后,我们就可以来实现搜索的功能了。上代码:classSplunk(object):def__init__(self):self.bf=Bloomfilter(64)self.terms=(}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):Addsaneventtothisobject件■国互联网前沿技术人才摇篮#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch(self,term):件■国互联网前沿技术人才摇篮Searchforasingleterm,andyieldalltheeventsthatcontainit"""InSplunkthisrunsinO(1),andislikelytobeinfilesystemcache(memory)ifnotself.bf.might_contain(term):returnInSplunkthisprobablyrunsinO(logN)whereNisthenumberoftermsinthetsidxiftermnotinself.terms:returnforevent_idinsorted(self.terms[term]):yieldself.events[event_id]用国互联网前沿技术人才摇篮Splunk代表一个拥有搜索功能的索引集合每一个集合中包含一个布隆过滤器,一个倒排词表(字典),和一个存储所有事件的数组当一个事件被加入到索引的时候,会做以下的逻辑为每一个事件生成一个unqieid,这里就是序号对事件进行分词,把每一个词加入到倒排词表,也就是每一个词对应的事件的id的映射结构,注意,一个词可能对应多个事件,所以倒排表的的值是一个Set。倒排表是绝大部分搜索引擎的核心功能。当一个词被搜索的时候,会做以下的逻辑用国互联网前沿技术人才摇篮检查布隆过滤器,如果为假,直接返回检查词表,如果被搜索单词不在词表中,直接返回在倒排表中找到所有对应的事件id,然后返回事件的内容我们运行下看看把:s=Splunk()s.add_event('src_ip=')s.add_event('src_ip=')s.add_event('dst_ip=')foreventins.search(''):件■国互联网前沿技术人才摇篮printeventprint'-foreventins.search('src_ip'):printeventprint'-foreventins.search('ip'):printeventsrc_ip=dst_ip=-src_ip=src_ip=src_ip=用国互联网前沿技术人才摇篮src_ip=dst_ip=是不是很赞!更复杂的搜索更进一步,在搜索过程中,我们想用And和Or来实现更复杂的搜索逻辑。上代码:classSplunkM(object):def__init__(self):self.bf=Bloomfilter(64)self.terms=(}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):件■国互联网前沿技术人才摇篮"""Addsaneventtothisobject""”#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch_all(self,terms):件■国互联网前沿技术人才摇篮"""SearchforanANDofallterms"""#Startwiththeuniverseofallevents...results=set(range(len(self.events)))forterminterms:#Ifatermisn'tpresentatallthenwecanstoplookingifnotself.bf.might_contain(term):returniftermnotinself.terms:return#Dropeventsthatdon'tmatchfromourresultsresults=ersection(self.terms[term])件■国互联网前沿技术人才摇篮forevent_idinsorted(results):yieldself.events[event_id]defsearch_any(s
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年金融科技在财富管理领域的创新应用研究
- 2025年在线教育平台课程进度跟踪与用户满意度评价报告
- 工业互联网平台入侵检测系统2025年可视化安全监控优化报告001
- 深度解读2025年不良资产处置市场格局与创新模式发展报告
- 2025年医院电子病历系统优化与医疗信息化人才培养策略报告
- 2025届广东省广州市南沙区八年级英语第二学期期中达标测试试题含答案
- 咨询工程师2017课件
- 2025年医药企业研发外包(CRO)模式下的临床试验监测与数据收集报告
- 周长课件介绍
- 麻醉护理制度培训课件
- 电力市场交易体系规则培训PPT
- 内河船员(一类)轮机实操考试资料二三管轮
- 抽样检验知识培训
- 急性肺栓塞抢救流程
- 零件清理、精整作业指导书
- 2023年广东省广州市南沙区万顷沙镇社区工作人员考试模拟题含答案
- GB/T 9634.8-2018铁氧体磁心表面缺陷极限导则第8部分:PQ型磁心
- GB/T 1094.16-2013电力变压器第16部分:风力发电用变压器
- GA 1016-2012枪支(弹药)库室风险等级划分与安全防范要求
- 从亮剑看销售精神-王朝之道
- word版DL/T5210.1-2012电力建设施工质量验收及评定规程第1部分:土建工程
评论
0/150
提交评论