百度搜索引擎优化指南20 下载(Python代码实现了一个基本的数据搜索的基本原理基本功能)

　　百度搜索引擎优化指南20 下载(Python代码实现了一个基本的数据搜索的基本原理基本功能)

　　搜索是大数据领域的常见需求。Splunk 和 ELK 分别是非开源和开源领域的领导者。本文用很少的Python代码实现了一个基本的数据搜索功能，力图让大家了解大数据搜索的基本原理。

　　布隆过滤器

　　第一步是实现布隆过滤器。

　　布隆过滤器是大数据领域的常用算法，其目的是过滤掉那些不是目标的元素。换句话说，如果我的数据中不存在要搜索的词，那么它可以快速返回目标不存在。

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

　　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

　　看到这里，大家应该可以看出，如果布隆过滤器返回False，那么数据肯定没有被索引，但是如果返回True，就不能说数据一定被索引了。在搜索过程中使用布隆过滤器可以让很多错过的搜索提前返回，提高效率。

　　让我们看看这段代码是如何工作的：

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

　　结果：

　　[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

　　首先，创建一个容量为 10 的布隆过滤器

　　

　　然后分别添加“狗”、“鱼”和“猫”三个对象。这时候布隆过滤器的内容如下：

　　

　　然后添加'bird'对象，Bloom过滤器的内容没有改变，因为'bird'和'fish'恰好有相同的hash。

　　

　　最后，我们检查一堆对象（'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]), ...

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

　　主要细分

　　主切分使用空格来切词。在实际的切分逻辑中，还会有其他的分隔符。例如，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

　　中学部

　　小分割的逻辑与大分割的逻辑类似，只是将开始部分到当前分割的结果相加。比如“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()

for major in major_segments(event):

for minor in minor_segments(major):

results.add(minor)

return results

　　分词的逻辑是先对文本进行一次大分词，然后对每个大分词进行二次分词。然后返回所有分隔的单词。

　　让我们看看这段代码是如何工作的：

　　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

　　搜索

　　好了，有了分词和布隆过滤器这两个强大的工具的支持，我们就可以实现搜索功能了。

　　在代码上：

　　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]

　　当一个词被搜索到时，它会做以下逻辑

　　让我们运行它看看：

　　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

　　是不是很赞！

　　更复杂的搜索

　　此外，在搜索过程中，我们希望使用 And 和 Or 来实现更复杂的搜索逻辑。

　　在代码上：

　　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集合的交集和并集操作，可以轻松支持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')

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

　　总结

　　上面的代码只是为了说明大数据搜索的基本原理，包括布隆过滤器、分词和倒排表。如果真想用这段代码实现真正的搜索功能，还差得很远。所有内容均来自 Splunk Conf2017。有兴趣的可以去看网上的视频。