在线观看www成人影院-在线观看www日本免费网站-在线观看www视频-在线观看操-欧美18在线-欧美1级

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

用 Python 實現一個大數據搜索引擎

馬哥Linux運維 ? 來源:未知 ? 作者:鄧佳佳 ? 2018-03-06 17:26 ? 次閱讀

前言

搜索是大數據領域里常見的需求。Splunk和ELK分別是該領域在非開源和開源領域里的領導者。本文利用很少的Python代碼實現了一個基本的數據搜索功能,試圖讓大家理解大數據搜索的基本原理。

布隆過濾器 (Bloom Filter)

第一步我們先要實現一個布隆過濾器。

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

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

classBloomfilter(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"""

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

returnself.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

forterm 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: 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’是一樣的。

分詞

下面一步我們要實現分詞。 分詞的目的是要把我們的文本數據分割成可搜索的最小單元,也就是詞。這里我們主要針對英語,因為中文的分詞涉及到自然語言處理,比較復雜,而英文基本只要用標點符號就好了。

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

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]), ...

foridx,ch inenumerate(s):

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

returnresults

主要分割

主要分割使用空格來分詞,實際的分詞邏輯中,還會有其它的分隔符。例如Splunk的缺省分割符包括以下這些,用戶也可以定義自己的分割符。

] < >( ) { } | ! ; , ‘ ” * s & ? + %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()

foridx,ch inenumerate(s):

ifch inminor_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

def segments(event):

"""Simple wrapper around major_segments / minor_segments"""

results = set()

formajor inmajor_segments(event):

forminor inminor_segments(major):

results.add(minor)

returnresults

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

我們看看這段 code是如何運行的:

forterm insegments('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

搜索

好了,有個分詞和布隆過濾器這兩個利器的支撐后,我們就可以來實現搜索的功能了。

上代碼:

classSplunk(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

forterm insegments(event):

self.bf.add_value(term)

ifterm notinself.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)

ifnotself.bf.might_contain(term):

return

# In Splunk this probably runs in O(log N) where N is the number of terms in the tsidx

ifterm notinself.terms:

return

forevent_id insorted(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')

forevent ins.search('1.2.3.4'):

print event

print'-'

forevent ins.search('src_ip'):

print event

print'-'

forevent ins.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來實現更復雜的搜索邏輯。

上代碼:

classSplunkM(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

forterm insegments(event):

self.bf.add_value(term)

ifterm notinself.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)))

forterm interms:

# If a term isn't present at all then we can stop looking

ifnotself.bf.might_contain(term):

return

ifterm notinself.terms:

return

# Drop events that don't match from our results

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

forevent_id insorted(results):

yield self.events[event_id]

def search_any(self,terms):

"""Search for an OR of all terms"""

results = set()

forterm interms:

# If a term isn't present, we skip it, but don't stop

ifnotself.bf.might_contain(term):

continue

ifterm notinself.terms:

continue

# Add these events to our results

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

forevent_id insorted(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')

forevent ins.search_all(['src_ip','5.6']):

print event

print'-'

forevent ins.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。大家如果有興趣可以去看網上的視頻

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • python
    +關注

    關注

    56

    文章

    4810

    瀏覽量

    85074

原文標題:用 Python 實現一個大數據搜索引擎

文章出處:【微信號:magedu-Linux,微信公眾號:馬哥Linux運維】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    阿里國際推出全球首個B2B AI搜索引擎Accio

    近日,在歐洲科技峰會Web Summit上,阿里國際正式推出了全球首個B2B領域的AI搜索引擎——Accio。這創新產品面向全球商家開放,標志著阿里國際正式入局當前備受矚目的AI Search賽道。
    的頭像 發表于 11-15 16:53 ?767次閱讀

    阿里國際推出B2B領域AI搜索引擎Accio

    近日,阿里國際宣布正式進軍AI搜索領域,并面向全球商家推出了首個B2B領域的AI搜索引擎——Accio。這創新產品的推出,標志著阿里國際在電子商務和人工智能技術結合方面邁出了重要
    的頭像 發表于 11-14 11:47 ?500次閱讀

    Meta開發新搜索引擎,減少對谷歌和必應的依賴

    近日,Meta正在積極進軍人工智能領域,并試圖跟上OpenAI的發展步伐。為實現目標,Meta正在開發款全新的搜索引擎,該搜索引擎具備
    的頭像 發表于 10-29 11:49 ?458次閱讀

    月訪問量超2億,增速113%!360AI搜索成為全球增速最快的AI搜索引擎

    與傳統搜索引擎不同,作為AI原生搜索引擎的360AI搜索基于公開網絡、知識庫、大模型三大支柱。借助首創的 CoE 技術架構,360AI搜索整合了國內主流的16家廠商51款大模型,支持用
    的頭像 發表于 09-09 13:44 ?587次閱讀
    月訪問量超2億,增速113%!360AI<b class='flag-5'>搜索</b>成為全球增速最快的AI<b class='flag-5'>搜索引擎</b>

    OpenAI推出SearchGPT原型,正式向Google搜索引擎發起挑戰

    在人工智能領域的持續探索中,OpenAI 邁出了重大步,發布了其最新的 SearchGPT 原型,直接瞄準了 Google 的核心業務——搜索引擎。這舉動不僅標志著 OpenAI 在技術上的又
    的頭像 發表于 07-26 15:11 ?617次閱讀

    微軟計劃在搜索引擎Bing中引入AI摘要功能

    近期,科技界傳來新動向,微軟緊隨百度與谷歌的步伐,宣布計劃在其搜索引擎Bing中引入先進的AI摘要功能,旨在為用戶帶來更加智能、豐富的搜索體驗。
    的頭像 發表于 07-26 14:23 ?514次閱讀

    OpenAI否認將推出搜索產品或GPT-5

    此消息對致力于將ChatGPT嵌入必應搜索引擎的微軟或許有所積極影響。早期已有報導披露,該AI企業有意研發競品以抗衡谷歌搜索引擎
    的頭像 發表于 05-13 15:14 ?419次閱讀

    OpenAI注冊新域名,準備推出結合AI技術的搜索引擎挑戰谷歌

    OpenAI最近注冊了“search.chatgpt.com”域名,看起來是要推出款新的搜索引擎
    的頭像 發表于 05-08 10:41 ?524次閱讀

    OpenAI或將推出ChatGPT搜索引擎

    據可靠消息透露,OpenAI正秘密研發款以ChatGPT為基礎的大型產品,其核心功能將是款新型搜索引擎,旨在為用戶提供更便捷的上網體驗。
    的頭像 發表于 05-08 10:19 ?545次閱讀

    新火種AI|挑戰谷歌,OpenAI要推出搜索引擎

    新的搜索引擎,幫助用書輕松上網。 OpenAI的這動向引起了業界的廣泛關注。作為OpenAI開發的款強大的AI大語言模型,ChatGPT已經在自然語言處理的領域取得了顯著的成果,并給了人們全新的獲取信息的體驗。因此,自誕生以
    的頭像 發表于 05-07 22:06 ?399次閱讀
    新火種AI|挑戰谷歌,OpenAI要推出<b class='flag-5'>搜索引擎</b>?

    OpenAI或將在5月9日發布ChatGPT版搜索引擎

    OpenAI可能即將與谷歌展開正面競爭,推出基于ChatGPT的搜索引擎。根據Reddit網友的最新爆料,OpenAI有望在5月9日公布其全新的搜索產品。據悉,與這新產品相對應的搜索
    的頭像 發表于 05-07 09:28 ?671次閱讀

    潤和軟件與新財富聯合發布金融AI對話式搜索引擎“金融搜搜”產品

    3月29日,新財富投顧嘉年華活動中,江蘇潤和軟件股份有限公司(以下簡稱“潤和軟件”)與深圳市新財富數字科技有限責任公司(以下簡稱“新財富”)聯合發布了金融AI對話式搜索引擎——“金融搜搜”產品,助力金融投資場景智能化升級。
    的頭像 發表于 04-02 10:15 ?565次閱讀
    潤和軟件與新財富聯合發布金融AI對話式<b class='flag-5'>搜索引擎</b>“金融搜<b class='flag-5'>一</b>搜”產品

    微軟向Windows 10/11推送更新,建議將Bing設為Chrome默認搜索引擎

    微軟通過提示窗口表示,只要將Bing設為Chrome瀏覽器的默認搜索引擎,即可免費享用ChatGPT-4,且每天可與Bing人工智能進行數百次的對話交流。
    的頭像 發表于 03-15 14:32 ?1409次閱讀

    Redis官方搜索引擎來了,性能炸裂!

    RediSearch 是 Redis 模塊,為 Redis 提供查詢、二級索引和全文搜索功能。
    的頭像 發表于 02-21 10:01 ?2563次閱讀
    Redis官方<b class='flag-5'>搜索引擎</b>來了,性能炸裂!

    生成式AI恐使搜索引擎衰退,預計2026年搜索量將下滑25%

    據市場分析機構Gartner報道,生成式AI對傳統搜索引擎構成重大威脅,預計至2026年搜索量將降低25%。為此,企業需調整營銷策略。
    的頭像 發表于 02-20 10:04 ?781次閱讀
    主站蜘蛛池模板: 都市激情亚洲 | 国内精品久久久久影院免费 | 五月天婷婷社区 | 美女拍拍拍爽爽爽爽爽爽 | 欧美一级在线全免费 | 五月激情站 | 免费看欧美一级特黄a大片 免费看欧美一级特黄a大片一 | 四虎影院4hu | 久久99精品一级毛片 | 最新版天堂中文在线官网 | 亚洲一卡二卡在线 | 国产精品久线观看视频 | 国产香蕉视频在线 | 亚洲第一视频在线 | 人人做人人插 | 天天曰| 在线观看一级毛片 | 麻豆三级在线播放 | 欧美一级一一特黄 | 日日操夜夜操狠狠操 | 久久久伊香蕉网站 | 国产免费糟蹋美女视频 | 中文字幕一二三四区2021 | 天天射天天干天天 | 亚洲444kkk | 天天干夜夜笙歌 | 伊人网大 | 午夜69成人做爰视频网站 | 狠狠色综合久久久久尤物 | 日韩亚洲人成在线综合日本 | gav久久 | 亚洲激情网站 | 国产一级特黄一级毛片 | 美女18黄 | 在线观看网址你懂得 | 黄色理伦| 亚洲ay| 在线亚洲精品中文字幕美乳 | 婷婷丁香激情 | 91精品福利久久久 | 综合五月天婷婷丁香 |