欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎

 更新時(shí)間:2017年11月28日 10:41:01   作者:naughty  
這篇文章主要介紹了淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧

搜索是大數(shù)據(jù)領(lǐng)域里常見的需求。Splunk和ELK分別是該領(lǐng)域在非開源和開源領(lǐng)域里的領(lǐng)導(dǎo)者。本文利用很少的Python代碼實(shí)現(xiàn)了一個(gè)基本的數(shù)據(jù)搜索功能,試圖讓大家理解大數(shù)據(jù)搜索的基本原理。

布隆過濾器 (Bloom Filter)

第一步我們先要實(shí)現(xiàn)一個(gè)布隆過濾器。

布隆過濾器是大數(shù)據(jù)領(lǐng)域的一個(gè)常見算法,它的目的是過濾掉那些不是目標(biāo)的元素。也就是說如果一個(gè)要搜索的詞并不存在與我的數(shù)據(jù)中,那么它可以以很快的速度返回目標(biāo)不存在。

讓我們看看以下布隆過濾器的代碼:

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. 基本的數(shù)據(jù)結(jié)構(gòu)是個(gè)數(shù)組(實(shí)際上是個(gè)位圖,用1/0來記錄數(shù)據(jù)是否存在),初始化是沒有任何內(nèi)容,所以全部置False。實(shí)際的使用當(dāng)中,該數(shù)組的長度是非常大的,以保證效率。
  2. 利用哈希算法來決定數(shù)據(jù)應(yīng)該存在哪一位,也就是數(shù)組的索引
  3. 當(dāng)一個(gè)數(shù)據(jù)被加入到布隆過濾器的時(shí)候,計(jì)算它的哈希值然后把相應(yīng)的位置為True
  4. 當(dāng)檢查一個(gè)數(shù)據(jù)是否已經(jīng)存在或者說被索引過的時(shí)候,只要檢查對(duì)應(yīng)的哈希值所在的位的True/Fasle

看到這里,大家應(yīng)該可以看出,如果布隆過濾器返回False,那么數(shù)據(jù)一定是沒有索引過的,然而如果返回True,那也不能說數(shù)據(jù)一定就已經(jīng)被索引過。在搜索過程中使用布隆過濾器可以使得很多沒有命中的搜索提前返回來提高效率。

我們看看這段 code是如何運(yùn)行的:

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

結(jié)果:

[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

首先創(chuàng)建了一個(gè)容量為10的的布隆過濾器

然后分別加入 ‘dog',‘fish',‘cat'三個(gè)對(duì)象,這時(shí)的布隆過濾器的內(nèi)容如下:

然后加入‘bird'對(duì)象,布隆過濾器的內(nèi)容并沒有改變,因?yàn)椤産ird'和‘fish'恰好擁有相同的哈希。

最后我們檢查一堆對(duì)象('dog', 'fish', 'cat', 'bird', 'duck', 'emu')是不是已經(jīng)被索引了。結(jié)果發(fā)現(xiàn)‘duck'返回True,2而‘emu'返回False。因?yàn)椤甦uck'的哈希恰好和‘dog'是一樣的。

分詞

下面一步我們要實(shí)現(xiàn)分詞。 分詞的目的是要把我們的文本數(shù)據(jù)分割成可搜索的最小單元,也就是詞。這里我們主要針對(duì)英語,因?yàn)橹形牡姆衷~涉及到自然語言處理,比較復(fù)雜,而英文基本只要用標(biāo)點(diǎn)符號(hào)就好了。

下面我們看看分詞的代碼:

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

主要分割

主要分割使用空格來分詞,實(shí)際的分詞邏輯中,還會(huì)有其它的分隔符。例如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

次要分割

次要分割和主要分割的邏輯類似,只是還會(huì)把從開始部分到當(dāng)前分割的結(jié)果加入。例如“1.2.3.4”的次要分割會(huì)有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

分詞的邏輯就是對(duì)文本先進(jìn)行主要分割,對(duì)每一個(gè)主要分割在進(jìn)行次要分割。然后把所有分出來的詞返回。

我們看看這段 code是如何運(yùn)行的:

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

搜索

好了,有個(gè)分詞和布隆過濾器這兩個(gè)利器的支撐后,我們就可以來實(shí)現(xiàn)搜索的功能了。

上代碼:

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代表一個(gè)擁有搜索功能的索引集合

每一個(gè)集合中包含一個(gè)布隆過濾器,一個(gè)倒排詞表(字典),和一個(gè)存儲(chǔ)所有事件的數(shù)組

當(dāng)一個(gè)事件被加入到索引的時(shí)候,會(huì)做以下的邏輯

  1. 為每一個(gè)事件生成一個(gè)unqie id,這里就是序號(hào)
  2. 對(duì)事件進(jìn)行分詞,把每一個(gè)詞加入到倒排詞表,也就是每一個(gè)詞對(duì)應(yīng)的事件的id的映射結(jié)構(gòu),注意,一個(gè)詞可能對(duì)應(yīng)多個(gè)事件,所以倒排表的的值是一個(gè)Set。倒排表是絕大部分搜索引擎的核心功能。

當(dāng)一個(gè)詞被搜索的時(shí)候,會(huì)做以下的邏輯

  1. 檢查布隆過濾器,如果為假,直接返回
  2. 檢查詞表,如果被搜索單詞不在詞表中,直接返回
  3. 在倒排表中找到所有對(duì)應(yīng)的事件id,然后返回事件的內(nèi)容

我們運(yùn)行下看看把:

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

是不是很贊!

更復(fù)雜的搜索

更進(jìn)一步,在搜索過程中,我們想用And和Or來實(shí)現(xiàn)更復(fù)雜的搜索邏輯。

上代碼:

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(求合集)的操作。

運(yùn)行結(jié)果如下:

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

總結(jié)

以上的代碼只是為了說明大數(shù)據(jù)搜索的基本原理,包括布隆過濾器,分詞和倒排表。如果大家真的想要利用這代碼來實(shí)現(xiàn)真正的搜索功能,還差的太遠(yuǎn)。所有的內(nèi)容來自于Splunk Conf2017。希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • python 通過視頻url獲取視頻的寬高方式

    python 通過視頻url獲取視頻的寬高方式

    今天小編就為大家分享一篇python 通過視頻url獲取視頻的寬高方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • python?包實(shí)現(xiàn)?time?時(shí)間管理操作

    python?包實(shí)現(xiàn)?time?時(shí)間管理操作

    這篇文章主要介紹了python包實(shí)現(xiàn)time時(shí)間管理操作,文章通過獲取當(dāng)前時(shí)間戳,即當(dāng)前系統(tǒng)內(nèi)表示時(shí)間的一個(gè)浮點(diǎn)數(shù),下文更多相關(guān)內(nèi)容需要的小伙伴可以參考一下
    2022-04-04
  • python使用seaborn繪圖直方圖displot,密度圖,散點(diǎn)圖

    python使用seaborn繪圖直方圖displot,密度圖,散點(diǎn)圖

    這篇文章主要介紹了python使用seaborn繪圖直方圖displot,密度圖,散點(diǎn)圖,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下
    2022-07-07
  • python使用pymysql操作MySQL錯(cuò)誤代碼1054和1064處理方式

    python使用pymysql操作MySQL錯(cuò)誤代碼1054和1064處理方式

    這篇文章主要介紹了python使用pymysql操作MySQL錯(cuò)誤代碼1054和1064處理方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-06-06
  • Python大批量搜索引擎圖像爬蟲工具詳解

    Python大批量搜索引擎圖像爬蟲工具詳解

    這篇文章主要介紹了Python大批量搜索引擎圖像爬蟲工具,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-11-11
  • 運(yùn)行django項(xiàng)目指定IP和端口的方法

    運(yùn)行django項(xiàng)目指定IP和端口的方法

    今天小編就為大家分享一篇運(yùn)行django項(xiàng)目指定IP和端口的方法。具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2018-05-05
  • 教你用Python實(shí)現(xiàn)Excel表格處理

    教你用Python實(shí)現(xiàn)Excel表格處理

    今天教各位小伙伴怎么用Python處理excel,文中有非常詳細(xì)的代碼示例及相關(guān)知識(shí)總結(jié),對(duì)正在學(xué)習(xí)python的小伙伴們很有幫助,需要的朋友可以參考下
    2021-05-05
  • Python使用Webargs實(shí)現(xiàn)簡化Web應(yīng)用程序的參數(shù)處理

    Python使用Webargs實(shí)現(xiàn)簡化Web應(yīng)用程序的參數(shù)處理

    在開發(fā)Web應(yīng)用程序時(shí),參數(shù)處理是一個(gè)常見的任務(wù),Python的Webargs模塊為我們提供了一種簡單而強(qiáng)大的方式來處理這些參數(shù),下面我們就來學(xué)習(xí)一下具體操作吧
    2024-02-02
  • matplotlib圖形整合之多個(gè)子圖繪制的實(shí)例代碼

    matplotlib圖形整合之多個(gè)子圖繪制的實(shí)例代碼

    matplotlib繪制多個(gè)子圖的時(shí)候,我們可以根據(jù)自己的想法去排列子圖的順序,也可以生成不同的子圖數(shù)量,本文就詳細(xì)的介紹了matplotlib 多子圖繪制,具有一定的參考價(jià)值,感興趣的可以了解一下
    2022-04-04
  • Python實(shí)現(xiàn)Youku視頻批量下載功能

    Python實(shí)現(xiàn)Youku視頻批量下載功能

    前段時(shí)間由于收集視頻數(shù)據(jù)的需要,自己搗鼓了一個(gè)YouKu視頻批量下載的程序。下面小編把實(shí)現(xiàn)過程分享到腳本之家平臺(tái),供大家參考
    2017-03-03

最新評(píng)論