编程之法读书笔记第六章——算法心得

看了这章才知道真的应该从头看数据结构

事实上，针对时间问题，可以采用巧妙的算法搭配合适的数据结构（如布隆过滤器、哈希、位图、堆、数据库、倒排索引、Trie 树）来解决；而对于空间问题，可以采取分而治之（哈希映射）的方法，也就是说，把规模大的数据转化为规模小的，从而各个击破。

倒排索引

“反向索引”
常规的索引是文档到关键词的映射：
文档——> 关键词
但是这样检索关键词的时候很费力，要一个文档一个文档的遍历一遍。（这事不能忍）
于是人们发明了
倒排索引~倒排索引是关键词到文档的映射
关键词——> 文档
这样，只要有关键词，立马就能找到她在那个文档里出现过，剩下的事就是把她揪出来了

布隆过滤器

布隆过滤器是由巴顿. 布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, …,F8） 产生八个信息指纹（f1, f2, …, f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见原链接）

现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, …, F8）对这个地址产生八个信息指纹 s1,s2,…,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,…,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可 疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都 被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

字典树

字典树（Trie）可以保存一些字符串 -> 值的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。

Trie 的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。至于 Trie 树的实现，可以用数组，也可以用指针动态分配。

它有 3 个基本性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

实现

用 Python 的字典来实现

实现 add 函数，首先我们复制一个字典出来，然后是遍历 word 的所有字母，如果这个字母在字典中有，那么就继续下一个（通过移动字典），如果这个字母在字典中没有那么就加一个，同样继续下一个。注意最后还需要给叶子节点一些特殊的标记，例如多加一个 key value。

然后我们还要实现 search 函数，和前面 add 非常类似，这时只需要 for 循环找到那个标志即可。 

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
class TrieTree(object):
  def __init__(self):
    self.tree = {}  
  def add(self, word):
    tree = self.tree
    for char in word:
      if char in tree:
        tree = tree[char]
      else:
        tree[char] = {}
        tree = tree[char]
    # 标志位
    tree['exist'] = True
  def search(self, word):
    tree = self.tree
    for char in word:
      if char in tree:
        tree = tree[char]
      else:
        return False
    if "exist" in tree and tree["exist"] == True:
      return True
    else:
      return False
tree = TrieTree()
tree.add("abc")
tree.add("bcd")
print(tree.tree)
# Print {'a': {'b': {'c': {'exist': True}}}, 'b': {'c': {'d': {'exist': True}}}}
print(tree.search("ab"))
# Print False
print(tree.search("abc"))
# Print True
print(tree.search("abcd"))
# Print False
算法