用 Python 实现一个大数据搜索引擎Word格式.docx
《用 Python 实现一个大数据搜索引擎Word格式.docx》由会员分享，可在线阅读，更多相关《用 Python 实现一个大数据搜索引擎Word格式.docx（13页珍藏版）》请在冰点文库上搜索。
returnhash（value）%self.size
defadd_value（self,value）:
AddavaluetotheBF"
h=self.hash_value（value）
self.values[h]=True
defmight_contain（self,value）:
CheckifthevaluemightbeintheBF"
returnself.values[h]
defprint_contents（self）:
DumpthecontentsoftheBFfordebuggingpurposes"
printself.values
基本的数据结构是个数组（实际上是个位图，用1/0来记录数据是否存在），初始化是没有任何内容，所以全部置False。
实际的使用当中，该数组的长度是非常大的，以保证效率。
利用哈希算法来决定数据应该存在哪一位，也就是数组的索引
当一个数据被加入到布隆过滤器的时候，计算它的哈希值然后把相应的位置为True
当检查一个数据是否已经存在或者说被索引过的时候，只要检查对应的哈希值所在的位的T
看到这里，大家应该可以看出，如果布隆过滤器返回False，那么数据一定是没有索引过的，然而如果返回True，那也不能说数据一定就已经被索引过。
在搜索过程中使用布隆过滤器可以使得很多没有命中的搜索提前返回来提高效率。
我们看看这段code是如何运行的：
bf=Bloomfilter（10）
bf.add_value（'
dog'
）
fish'
cat'
bf.print_contents（）
bird'
#Note:
contentsareunchangedafteraddingbird-itcollides
fortermin['
'
duck'
emu'
]:
print'
{}:
{}{}'
.format（term,bf.hash_value（term）,bf.might_contain（term））
结果：
[False,False,False,False,True,True,False,False,False,True]
dog:
5True
fish:
4True
cat:
9True
bird:
duck:
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）
]
returnresults
主要分割
主要分割使用空格来分词，实际的分词逻辑中，还会有其它的分隔符。
例如Splunk的缺省分割符包括以下这些，用户也可以定义自己的分割符。
]<
>
（）{}|!
;
‘”*
s
&
?
+%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='
_.'
ifchinminor_breaks:
segment=s[:
results.add（s）
次要分割
次要分割和主要分割的逻辑类似，只是还会把从开始部分到当前分割的结果加入。
例如“1.2.3.4”的次要分割会有1，2，3，4，1.2，1.2.3
defsegments（event）:
Simplewrapperaroundmajor_segments/minor_segments"
formajorinmajor_segments（event）:
forminorinminor_segments（major）:
results.add（minor）
分词的逻辑就是对文本先进行主要分割，对每一个主要分割在进行次要分割。
然后把所有分出来的词返回。
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
forevent_idinsorted（self.terms[term]）:
yieldself.events[event_id]
Splunk代表一个拥有搜索功能的索引集合
每一个集合中包含一个布隆过滤器，一个倒排词表（字典），和一个存储所有事件的数组
当一个事件被加入到索引的时候，会做以下的逻辑
为每一个事件生成一个unqieid，这里就是序号
对事件进行分词，把每一个词加入到倒排词表，也就是每一个词对应的事件的id的映射结构，注意，一个词可能对应多个事件，所以倒排表的的值是一个Set。
倒排表是绝大部分搜索引擎的核心功能。
当一个词被搜索的时候，会做以下的逻辑
检查布隆过滤器，如果为假，直接返回
检查词表，如果被搜索单词不在词表中，直接返回
在倒排表中找到所有对应的事件id，然后返回事件的内容
我们运行下看看把：
s=Splunk（）
s.add_event（'
src_ip=5.6.7.8'
dst_ip=1.2.3.4'
foreventins.search（'
1.2.3.4'
printevent
-'
src_ip'
ip'
src_ip=1.2.3.4
dst_ip=1.2.3.4-
src_ip=5.6.7.8-
src_ip=5.6.7.8
dst_ip=1.2.3.4
是不是很赞！
更复杂的搜索
更进一步，在搜索过程中，我们想用And和Or来实现更复杂的搜索逻辑。
classSplunkM（object）:
defsearch_all（self,terms）:
SearchforanANDofallterms"
#Startwiththeuniverseofallevents...
results=set（range（len（self.events）））
forterminterms:
#Ifatermisn'
tpresentatallthenwecanstoplooking
#Dropeventsthatdon'
tmatchfromourresults
results=results.intersection（self.terms[term]）
forevent_idinsorted（results）:
defsearch_any（self,terms）:
SearchforanORofallterms"
tpresent,weskipit,butdon'
tstop
continue
#Addtheseeventstoourresults
results=results.union（self.terms[term]）
利用Python集合的intersection和union操作，可以很方便的支持And（求交集）和Or（求合集）的操作。
运行结果如下：
s=SplunkM（）
foreventins.search_all（['
5.6'
]）:
foreventins.search_any（['
dst_ip'
总结
以上的代码只是为了说明大数据搜索的基本原理，包括布隆过滤器，分词和倒排表。
如果大家真的想要利用这代码来实现真正的搜索功能，还差的太远。
升级会员 