博客专栏

EEPW首页 > 博客 > 用Python实现一个大数据搜索引擎及源码分享

用Python实现一个大数据搜索引擎及源码分享

发布人:扣丁学习 时间:2020-10-28 来源:工程师 发布文章

  在日常生活中,大家了解搜索引擎如百度、360、搜狗、谷歌等,搜索是大数据领域里常见的需求。Splunk和ELK分别是该领域在非开源和开源领域里的领导者。本文利用很少的Python代码实现了一个基本的数据搜索功能,试图让大家理解大数据搜索的基本原理。

  布隆过滤器(BloomFilter)


  第一步我们先要实现一个布隆过滤器。


  布隆过滤器是大数据领域的一个常见算法,它的目的是过滤掉那些不是目标的元素。也就是说如果一个要搜索的词并不存在与我的数据中,那么它可以以很快的速度返回目标不存在。


  让我们看看以下布隆过滤器的代码:


  classBloomfilter(object):


  """


  ABloomfilterisaprobabilisticdata-structurethattradesspaceforaccuracy


  whendeterminingifavalueisinaset.Itcantellyouifavaluewaspossibly


  added,orifitwasdefinitelynotadded,butitcan'ttellyouforcertainthat


  itwasadded.


  """


  def__init__(self,size):


  """SetuptheBFwiththeappropriatesize"""


  self.values=[False]*size


  self.size=size


  defhash_value(self,value):


  """HashthevalueprovidedandscaleittofittheBFsize"""


  returnhash(value)%self.size


  defadd_value(self,value):


  """AddavaluetotheBF"""


  h=self.hash_value(value)


  self.values[h]=True


  defmight_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-itcollides


  fortermin['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:5True


  fish:4True


  cat:9True


  bird:9True


  duck:5True


  emu: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.Splitthestringbyallofthemajor


  breaks,andreturnthesetofeverythingfound.Thebreaksinthisimplementation


  aresinglecharacters,butinSplunkpropertheycanbemultiplecharacters.


  Asetisusedbecauseorderingdoesn'tmatter,andduplicatesarebad.


  """


  major_breaks=''


  last=-1


  results=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的缺省分割符包括以下这些,用户也可以定义自己的分割符。


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


  defminor_segments(s):


  """


  Performminorsegmentingonastring.Thisislikemajor


  segmenting,exceptitalsocapturesfromthestartofthe


  inputtoeachbreak.


  """


  minor_breaks='_.'


  last=-1


  results=set()


  foridx,chinenumerate(s):


  ifchinminor_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)


  returnresults


  次要分割


  次要分割和主要分割的逻辑类似,只是还会把从开始部分到当前分割的结果加入。例如“1.2.3.4”的次要分割会有1,2,3,4,1.2,1.2.3


  defsegments(event):


  """Simplewrapperaroundmajor_segments/minor_segments"""


  results=set()


  formajorinmajor_segments(event):


  forminorinminor_segments(major):


  results.add(minor)


  returnresults


  分词的逻辑就是对文本先进行主要分割,对每一个主要分割在进行次要分割。然后把所有分出来的词返回。


  我们看看这段code是如何运行的:


  forterminsegments('src_ip=1.2.3.4'):


  printterm


  src


  1.2


  1.2.3.4


  src_ip


  3


  1


  1.2.3


  ip


  2


  =


  4


  搜索


  好了,有个分词和布隆过滤器这两个利器的支撑后,我们就可以来实现搜索的功能了。上代码:


  classSplunk(object):


  def__init__(self):


  self.bf=Bloomfilter(64)


  self.terms={}#Dictionaryoftermtosetofevents


  self.events=[]


  defadd_event(self,event):


  """Addsaneventtothisobject"""


  #GenerateauniqueIDfortheevent,andsaveit


  event_id=len(self.events)


  self.events.append(event)


  #Addeachtermtothebloomfilter,andtracktheeventbyeachterm


  forterminsegments(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):


  return


  #InSplunkthisprobablyrunsinO(logN)whereNisthenumberoftermsinthetsidx


  iftermnotinself.terms:


  return


  forevent_idinsorted(self.terms[term]):


  yieldself.events[event_id]


  Splunk代表一个拥有搜索功能的索引集合


  每一个集合中包含一个布隆过滤器,一个倒排词表(字典),和一个存储所有事件的数组


  当一个事件被加入到索引的时候,会做以下的逻辑


  为每一个事件生成一个unqieid,这里就是序号


  对事件进行分词,把每一个词加入到倒排词表,也就是每一个词对应的事件的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')


  foreventins.search('1.2.3.4'):


  printevent


  print'-'


  foreventins.search('src_ip'):


  printevent


  print'-'


  foreventins.search('ip'):


  printevent


  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来实现更复杂的搜索逻辑。


  上代码:


  classSplunkM(object):


  def__init__(self):


  self.bf=Bloomfilter(64)


  self.terms={}#Dictionaryoftermtosetofevents


  self.events=[]


  defadd_event(self,event):


  """Addsaneventtothisobject"""


  #GenerateauniqueIDfortheevent,andsaveit


  event_id=len(self.events)


  self.events.append(event)


  #Addeachtermtothebloomfilter,andtracktheeventbyeachterm


  forterminsegments(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'tpresentatallthenwecanstoplooking


  ifnotself.bf.might_contain(term):


  return


  iftermnotinself.terms:


  return


  #Dropeventsthatdon'tmatchfromourresults


  results=results.intersection(self.terms[term])


  forevent_idinsorted(results):


  yieldself.events[event_id]


  defsearch_any(self,terms):


  """SearchforanORofallterms"""


  results=set()


  forterminterms:


  #Ifatermisn'tpresent,weskipit,butdon'tstop


  ifnotself.bf.might_contain(term):


  continue


  iftermnotinself.terms:


  continue


  #Addtheseeventstoourresults


  results=results.union(self.terms[term])


  forevent_idinsorted(results):


  yieldself.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')


  foreventins.search_all(['src_ip','5.6']):


  printevent


  print'-'


  foreventins.search_any(['src_ip','dst_ip']):


  printevent


  src_ip=5.6.7.8


  -


  src_ip=1.2.3.4


  src_ip=5.6.7.8


  dst_ip=1.2.3.4


  最后想要了解更多关于Python发展前景趋势,请关注扣丁学堂官网、微信等平台,扣丁学堂IT职业在线学习教育平台为您提供最新的Python培训视频教程系统,通过千锋扣丁学堂金牌讲师在线录制的Python视频教程课程,让你快速掌握Python从入门到精通开发实战技能。扣丁学堂Python技术交流群:816572891。

*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。



关键词:

相关推荐

技术专区

关闭