Bloom Filter , 中文译作布隆过滤器。

从 filter 和过滤器可以看出它的用途，筛选东西，判断它是否满足要求。 它的优点是空间效率和时间效率，缺点是有一定的误判率和撤销困难。

1. bit 和 byte 的关系

1

1 byte = 8 bit

一个字节 (byte) 有八位 (bit)。

2. 优点

2.1 空间效率

1
2
3
4

s1 = 'http://www.dust8.com'
s2 = 'http://www.the5fire.com'
>>> len(s1), len(s2)
(20, 23)

字符串s1的长度为20，字符串s2的长度为23。也就是说s1占20个字节，s2占23个字节。

有人觉得它们太占地方了，想了个办法减少它们占的空间。 用它们的长度来代替它们，这样每个字符串都可以只用一个字节表示，大大减少空间。慢慢的字符串多了起来，有了

1
2
3
4

s3 = 'http://www.github.com'
s4 = 'http://www.google.com'    
>>> len(s3), len(s4)
(21, 21)

字符串s3和s4的长度都为21。要表示这4个字符串就要4个字节。有人又想了个办法，用一个bit来表示一个字符串。比如表示s1，就用第20个bit来表示，s2就用第23个bit来表示。怎么表示了，常见的就是把该bit设置为1，跟默认值不一样。这4个字符串长度最大的为23，所以用3个字节就可以表示它们了。

85个字节用3个字节就可以表示了，所以说它空间效率高。

2.2 时间效率

它在内存操作，所以速度快。

它只要一次查询就可以完成，所以速度快。比如要看是否有s1，只要看第20个bit是不是1，是1就有，如果是0则没有。

3.缺点

3.1 误判

s3和s4的长度都为21，都用第21个bit来表示，这就会产生误判。分不清表示的是s3，还是s4，或者2个都表示。

3.2 撤销困难

同样是s3和s4，如果表示了s3和s4，那么第21个bit就是1。现在不想表示s3了，却不能把第21个bit设置为0，设置为0就会影响s4的表示。

4. 设计Bloom Filter

如何降低误判率是关键，这需要

• 选取区分度高的哈希函数。比如上面的长度函数区分度就比较低，导致s3和s4分不清。
• 根据存储数组、哈希函数个数、误判率之间的关系，分配空间、个数

m是总共开辟的存储空间位数，n是待存储字符串的个数，k是哈希函数的个数，f是误判率。

大致可以认为误判率跟 m／n 和 k 成反比。当k为固定值时，m/n 越大，误判率越小。

5. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import math
import hashlib


class BloomFilter:
    hash_algorithms = [hashlib.md5, hashlib.sha1,
                       hashlib.sha224, hashlib.sha256]

    def __init__(self, m):
        self.m = m
        self.filter = bytearray(math.ceil(m / 8))

    def _hash(self, value):
        for hash_algorithm in self.hash_algorithms:
            digest = int(hash_algorithm(str(value).encode()).hexdigest(), 16)
            # 进行and运算来保证值在存储范围内
            yield digest & (self.m - 1)

    def add(self, value):
        for digest in self._hash(value):
            # 把对应的bit设置为1
            self.filter[int(digest / 8)] |= 2 ** (digest % 8)

    def __contains__(self, item):
        return all(self.filter[int(digest / 8)] & (2 ** (digest % 8))
                   for digest in self._hash(item))


if __name__ == '__main__':
    bf = BloomFilter(200)
    bf.add('1')
    bf.add(1)
    print(1 in bf, '20' in bf)  # True False

一个函数能调用自身就叫做递归。通常情况下，一个递归函数将具有一个终止条件和一个或多个递归调用其自身。

1.1 例子：计算指数

1
2
3
4
5
6
7
8
9
10
11

def exp(x, n):
    '''计算 x 的 n 次方
    >>> exp(2, 3)
    8
    >>> exp(3, 2)
    9
    '''
    if n == 0:
        return 1
    else:
        return x * exp(x, n-1)

还有斐波纳契也常做例子。

1.2 例子： 展开嵌套的序列

将一个多层嵌套的序列展开成一个单层序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def flatten_list(l, result=None):
    '''展开嵌套的序列
    >>> flatten_list([ [1, 2, [3, 4] ], [5, 6], 7])
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if result is None:
        result = []

    for x in l:
        if isinstance(x, list):
            flatten_list(x, result)
        else:
            result.append(x)

    return result

1.3 例子：JSON编码

把python对象编码成JSON字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def json_encode(data):
    '''JSON 编码
    >>> json_encode(['foo', {'bar': ('baz', None, 1.0, 2)}])
    '["foo", {"bar":["baz", null, 1.0, 2]}]'
    '''
    if isinstance(data, bool):
        return "false" if not data else "true"
    elif isinstance(data, type(None)):
        return "null"
    elif isinstance(data, (int, float)):
        return str(data)
    elif isinstance(data, str):
        return '"' + escape_string(data) + '"'
    elif isinstance(data, (list, tuple)):
        return "[" + ", ".join(json_encode(d) for d in data) + "]"
    elif isinstance(data, dict):
        return '{' + ', '.join(json_encode(k) + ':' + json_encode(v) for k, v in data.items()) + '}'
    else:
        raise TypeError('%s is not JSON serializable, is %s' %
                        (repr(data), type(data)))


def escape_string(s):
    """Escapes double-quote, tab and new line characters in a string."""
    s = s.replace('"', '\\"')
    s = s.replace("\t", "\\t")
    s = s.replace("\n", "\\n")
    return s

在这里给我的 bencoding 打个广告，

它是一个 B编码 的 python 库，也是基于递归写的。

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，

是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

有些正则引擎就是使用了它. 我们看个 python 里面的例子:

1
2
3
4

import re
re.findall(r'[0-9]+', '067p')
>>>
['067']

再来看张图片:

开始把当前状态设置为 1，如果满足转换条件（是 0 到 9 之间的数字),

就把当前状态设置为 2，如果满足转换条件（是 0 到 9 之间的数字),

还是把当前状态设置为 2，最后检查是否在接受状态(这里的接受状态是状态 2)。

用 python 来模拟下上图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#  (1, '0'):2中1是状态，‘0’是转换条件，2是满足转换条件后转到的状态
edges = {(1, '0'): 2,
         (1, '1'): 2,
         (1, '2'): 2,
         (1, '3'): 2,
         (1, '4'): 2,
         (1, '5'): 2,
         (1, '6'): 2,
         (1, '7'): 2,
         (1, '8'): 2,
         (1, '9'): 2,
         (2, '0'): 2,
         (2, '1'): 2,
         (2, '2'): 2,
         (2, '3'): 2,
         (2, '4'): 2,
         (2, '5'): 2,
         (2, '6'): 2,
         (2, '7'): 2,
         (2, '8'): 2,
         (2, '9'): 2}

# 接受的状态
acception = [2]

def fsmsim(string, current_state, edges, acception, pos=0):
    if pos >= len(string):
        return current_state in acception, string[:pos]
    else:
        letter = string[pos]
        if (current_state, letter) in edges:
            current_state = edges[(current_state, letter)]
            pos += 1
            return fsmsim(string, current_state, edges, acception, pos)
        else:
            return False, string[:pos]


fsmsim('0', 1, edges, acception)
>>>
(True, '0')

fsmsim('06', 1, edges, acception)
>>>
(True, '06')

fsmsim('067', 1, edges, acception)
>>>
(True, '067')

fsmsim('067p', 1, edges, acception)
>>>
(False, '067')

想搞个百度网盘搜索,今天抓了下百度网盘链接,记录下.

• http://pan.baidu.com/pcloud/feed/getsharelist?&auth_type=1&start=0&limit=60&query_uk=3154767138
• http://pan.baidu.com/pcloud/user/getinfo?query_uk=3154767138
• http://pan.baidu.com/pcloud/friend/getfanslist?query_uk=3154767138&limit=24&start=0
• http://pan.baidu.com/pcloud/friend/getfollowlist?query_uk=3154767138&limit=24&start=0

获取分享列表

getsharelist :获取分享列表

start :分享列表起始索引

limit :分享列表分页每页的数量

query_uk :查询uk

返回的 json 数据,用 json.loads() 处理成 dict.

feed_time 是 毫秒, 该用户分享该文件的时间.

path 是 文件路径, 被url转码过, 所以可以用 urllib.parse.unquote() 转回来.

获取用户的信息

getinfo :获取用户的信息

同上处理成 字典.

fans_count :粉丝数

follow_count : 订阅数

pubshare_count : 分享数

获取粉丝列表

getfanslist : 获取粉丝列表

获取订阅列表

getfollowlist : 获取订阅列表

通过上面4个 url, 就可以从一些初始的用户开始爬取他们的分享文件, 在根据他们的订阅和粉丝来获取下一步的爬取对象.

工具

• json格式化
• url转码

yield 表达式文档: Yield expressions

yield 表达式的作用有点像 return, 但是又有些不同.

相同的是执行到它就会返回, 不同的是 return 不会再回来; yield 还会回来. 举个栗子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def p():
    i = 0
    while True:
        print('start', i)
        yield i
        i += 1
        print('end', i)

p = p()

next(p)
print('-'*10)
next(p)
print('-'*10)
next(p)
print('-'*10)
next(p)

输出为:

1
2
3
4
5
6
7
8
9
10

start 0
----------
end 1
start 1
----------
end 2
start 2
----------
end 3
start 3

可以看到,第一次执行到 yield 就返回了; 第二次则是先执行 yield后面的,然后循环到 yield 再返回, 重要的是它还记得你上次返回时的状态(例如 i 的值), 而 return 就不会.

yield from 表达式文档: yield from

举个栗子:

1
2
3
4
5
6
7
8
9

def g(x):
    print('this first yield from')
    yield from range(x, 0, -1)
    print('this second yield from')
    yield from range(x)


for i in g(5):
    print(i)

输出为:

1
2
3
4
5
6
7
8
9
10
11
12

this first yield from
5
4
3
2
1
this second yield from
0
1
2
3
4

yield from 后面是迭代器, 并且 yield 完这个迭代器, 才会去执行第二个 yield from.