师兄给了一个虚网映射的仿真（cpp），和之前的embed-detail的C语言仿真工具很像，经过一周左右的学习，挖掘出了其中虚网映射部分的内容，在此整理，以作日后学习。鉴于之前embed-detail的学习总结很繁琐，这里的总结只做精要的介绍。

数据结构

这一部分在Utility.h中完成，是对映射种种数据容器的整理。

节点：

编号，CPU，带宽和，优先度

最短路：

跳数，带宽，路径列表，下一跳

映射结果（单节点）：

物理节点对象，虚拟节点编号，所属根节点，到根节点跳数，Node_list中序号，Node_list总数

（类）物理拓扑：

节点总数，边总数，资源，节点资源，边资源；

节点群（一维向量），边群（二维向量），最短路群（二维结构向量）；

方法：

• 初始化，
• 节点排序算法，
• Floyd算法,
• 找到节点序号对应的下标，
• 计算网络资源

（类）虚拟拓扑（继承物理拓扑）：

//同物理拓扑

允许最大跳数，分割率，拓扑类型，起始时间，映射时间，存活时间，消耗，节点消耗，链路消耗，收入，收入支出比，是否匹配成功，是否起请求截止，是否delay过，是否失败

满足约束条件的节点群（二维向量），结果群（结果向量），最短路群（二维链表向量）

方法：

• 读入拓扑，
• 初始化，
• 计算最短路径和，
• 查找结点是否已经映射，
• 匹配节点（包含匹配边），
• 匹配边，
• 匹配过程（包含匹配节点），
• 分配或释放资源（匹配过程中完成），
• 打印结果，
• 计算收入支出，
• 计算收入，
• 释放虚网的所有资源

核心方法分析

这一部分在Utility.cpp中完成，是对映射种种方法的实现。

（物理网络）

1. 初始化：开辟最短路群空间，计算链路CPU/带宽和/PR值

2. 计算资源：节点，链路资源相加。

（虚拟网络）

1. 读入文件：读入节点数，链路数，开始时间，存活时间等。

2. 初始化：填充Node_list

3. 查找结点是否已被映射：for 循环遍历暴力查找

4. 匹配节点：读入物理网络和参照物理网络，当前结点所属根节点，已映射节点数。

（1）打印

（2）从可行最短跳（虚拟网络中的跳数）到最大允许跳开始循环

（2.1）从可行节点（Node_list）中查找满足CPU要求的节点

（2.2）查找匹配边（Match_Edge），若有打印信息并返回

（3）打印失败信息返回

5. 匹配链路：读入物理网络预期参照，当前结点编号和下标，已映射节点数。

（1）循环寻找所有与该节点关联的节点

（1.1）若有关联，清空并循环更新最短路向量

（1.2）循环检测带宽是否满足要求

（2）循环还原减少的带宽资源

（3）返回成功标记

6. 匹配：读入物理拓扑，完成一个虚网的匹配

（1）建立物理拓扑最短路矩阵

（2）初始化最短路群，root, chosen_num（已选中节点数）

（3）初始化根节点result类实例，若无备选节点，返回 0

（4）循环寻找可行的根节点直到遍历完成

（4.1）以当前父节点为基础开始匹配子节点，循环

（4.1.1）循环寻找父节点的关联的子节点

（4.1.1.1）若某节点无匹配物理节点，循环释放资源，返回 0

（4.1.1.2）若找到，更新result群向量，调用匹配节点，找到对应物理节点序号

（4.1.1.2.1）若成功返回，继续更新result，最短路矩阵，更新底层资源

（4.1.1.2.2）若不成功，回退chosen_num，释放资源，更新root，最短路

（4.1.2）若未回退到根节点，不用调整根节点，继续从下个父节点开始匹配，直到匹配完成

（4.2）若匹配未完成，释放根节点和其余资源

（5）若匹配成功计算收入支出返回回退次数，否则释放资源，返回 0；

7. 资源管理：通过标记值区分占用或是释放，循环更新节点和链路资源

8. 打印，计算收入支出

9. 释放虚网资源：循环释放，返回释放资源值

主程序

这一部分在VNM.cpp中完成，是时间窗模型下虚网映射的实现。步骤如下：

1. 初始化临时变量，

2. 从文件中读入底层物理网络，虚网请求

3.  打印初始信息，计算物理资源

4. 循环到所有请求都被处理完成或是有finish标记

4.1 循环计算该窗口内待映射请求数

4.2 循环这些请求

4.2.1 挑出未延迟且未成功的

4.2.1.1 初始化虚网，打印信息

4.2.1.2 开始匹配，计算时间

4.2.1.3 计算收入，更改标记为映射完成或延迟

4.2.1.4 计算当前物理资源，写入到文件

4.2.2 挑出匹配成功且到期的请求

4.2.2.1 更新它们的R/S和完成数目

4.2.2.2 释放它们的资源

4.2.3 挑出delay过久的请求，置为失败，更新资源和计数器

4.3 计算该时间窗内的支出，收入等数据，更新finish和计数器

4.4 打印该时间窗测试数据到文件

4.5 更新时间窗时间

5. 关闭文件，打印当前时间

前言：在北邮人论坛里看到了对多态，继承，多重继承等的讨论，遂对比较陌生的鸭子类型和反射做了些学习。实际上这两个概念属于编程范式的范畴，在语法层面之上。对之的了解，相信对于以后语言的学习，多少也有些触类旁通的帮助。

鸭子类型

静态语言和动态语言

编程语言按照数据类型大体可以分为两类，一类是静态类型语言，另一类是动态类型语言。

静态类型语言在编译时便已确定变量的类型，而动态类型语言的变量类型要到程序运行的时候，待变量被赋予某个值之后，才会具有某种类型。

静态类型语言的优点首先是在编译时就能发现类型不匹配的错误，编辑器可以帮助我们提前避免程序在运行期间有可能发生的一些错误。其次，如果在程序中明确地规定了数据类型，编译器还可以针对这些信息对程序进行一些优化工作，提高程序执行速度。

静态类型语言的缺点首先是迫使程序员依照强契约来编写程序，为每个变量规定数据类型，归根结底只是辅助我们编写可靠性高程序的一种手段，而不是编写程序的目的，毕竟大部分人编写程序的目的是为了完成需求交付生产。其次，类型的声明也会增加更多的代码，在程序编写过程中，这些细节会让程序员的精力从思考业务逻辑上分散开来。

动态类型语言的优点是编写的代码数量更少，看起来也更加简洁，程序员可以把精力更多地放在业务逻辑上面。虽然不区分类型在某些情况下会让程序变得难以理解，但整体而言，代码量越少，越专注于逻辑表达，对阅读程序是越有帮助的。

动态类型语言的缺点是无法保证变量的类型，从而在程序的运行期有可能发生跟类型相关的错误。这好像在商店买了一包牛肉辣条，但是要真正吃到嘴里才知道是不是牛肉味。

如在Ruby，Python，JavaScript等语言中，当我们对一个变量赋值时，显然不需要考虑它的类型，因此，JavaScript是一门典型的动态类型语言。

是什么

动态类型语言对变量类型的宽容给实际编码带来了很大的灵活性。由于无需进行类型检测，我们可以尝试调用任何对象的任意方法，而无需去考虑它原本是否被设计为拥有该方法。

这一切都建立在鸭子类型（duck typing）的概念上，鸭子类型的通俗说法是：“如果它走起路来像鸭子，叫起来也是鸭子，那么它就是鸭子。”

我们可以通过一个小故事来更深刻地了解鸭子类型。

从前有一个国王，他觉得世界上最美妙的声音就是鸭子的叫声，于是国王召集大臣，要组建一个1000只鸭子组成的合唱团。大臣们找遍了全国，终于找到999只鸭子，但是始终还差一只，最后大臣发现有一只非常特别的鸡，它的叫声跟鸭子一模一样，于是这只鸡就成为了合唱团的最后一员。

这个故事告诉我们，国王要听的只是鸭子的叫声，这个声音的主人到底是鸡还是鸭并不重要。鸭子类型指导我们只关注对象的行为，而不关注对象本身。

下面用代码来模拟。

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

var duck = {
    duckSinging: function(){
    console.log( '嘎嘎嘎' );
    }
};

var chicken = {
    duckSinging: function(){
    console.log( '嘎嘎嘎' );
    }
};

var choir = [];    // 合唱团

var joinChoir = function( animal ){
    if ( animal && typeof animal.duckSinging === 'function' ){
    choir.push( animal );
    console.log( '恭喜加入合唱团' )
    console.log( '合唱团已有成员数量:' + choir.length );
    }
};

joinChoir( duck );       // 恭喜加入合唱团
joinChoir( chicken );    // 恭喜加入合唱团

我们看到，对于加入合唱团的动物，大臣们根本无需检查它们的类型，而是只需要保证它们拥有duckSinging方法。

在动态类型语言的面向对象设计中，鸭子类型的概念至关重要。利用鸭子类型的思想，我们不必借助超类型的帮助，就能轻松地在动态类型语言中实现一个原则：“面向接口编程，而不是面向实现编程”。

为什么

那么，为什么要有鸭子出现？

一、组合

C++等语言实现面向对象的主要方法是继承，而鸭子类型实现面向对象的方式是组合。而我们所熟知的，甚至被奉为面向对象编程原则的”多组合，少继承“的思想也说明了组合要比继承更加灵活方便。

C++中的多继承特性从一定层面反映了开发这想通过更多的父类获得特性；优先组合的思想也反应出我们希望能够使用更多对象的特性并隐藏细节；接口的出现反映出我们不希望通过多继承这样庞大的机制就能够实现更为复杂的对象关系；这些原本都是继承机制的面向对象思想或原则。

在日常的面向对象编程过程中，通常会为了做一个相对完美的抽象，关注了更多的类之间的关系，而不能把主要精力集中在业务逻辑代码中。

鸭子类型提供了大道至简的编程思想和模式

二、复用

静态类型中最关键的一点是面向契约编程，即双方定下调用契约，然后你实现，我调用。这避免了许多运行中问题。可是，正因为此，复用被弱化很多。

这里再次提到C++，多重继承的提出也有复用的目的。因为，人们不满足于只能仅仅复用简单的个体，很希望能够吸取多种对象的功能。这和现实是很相近的。一个业务实体往往能够兼备多种实体的功能。

尽管后来其他语言都是采用接口的机制取代多重继承，来实现业务实体的多个功能面的契约定义。可是，接口只是解决的契约的定义。另外，对于契约，其实有时候是很不公平的事。微软的认证是一个例子：

微软的认证是有阶梯约束的。过了初级才能考中级，而不管你是否已经拥有了初级的能力。对于没有参与考试的人，这是件不公平的事。如果有一项任务，必须拥有某种资格认证的人才能做，你是看资质证书呢？还是看能力表现？

这是个非常有意思的问题。如果是你，你会选择哪个呢？静态语言选择了前者，动态语言选择了后者。鸭子类型就是充分想利用这些没有获得契约的资源。在不改变这些对象的前提下，对之复用。

总结

鸭子类型是一种多态的表现形式，是一些动态语言具有的特征。它能够避免一些类的重写，无需大量复制相同的代码，但是也需要良好的文档支持，和严谨的代码，否则代码调试起来会多处许多麻烦，谁知道你的鸭子是不是我的鹅呢？

反射

反射同样是个抽象的、在语法之上的概念，是一些语言具有的特征，它牺牲了语言的封装性来实现代码的重用和灵活性，有利有弊。在Java，Ruby，C++，C#，Scheme诸多语言，甚至C中都有体现。

是什么

从**元编程（Metaprogramming）的角度来看，一门语言同时也是自身的元语言的能力称之为反射（Reflection）。按照 Toby Davies 论文 Homoiconicity, Lazyness and First-Class Macros 的说法，反射（Reflection）其实是通过允许在运行时存取程序数据，以改变程序行为的程序设计技术。他认为，反射其实是一种“语义同像（Semantic Homoiconicity）”。具有语义同像性的语言必须把程序中的一些内部状态，比如符号表、指令指针，暴露**给程序员。这样，程序员就可以把这些东西当作 First-Class-Value 而很容易地操作它们。

提供反射这种特性，无外乎是出于为了提高生产力、提高编程时的灵活性等考量。

下面以Ruby为例。

1
2
3
4
5
6
7
8

irb> require 'what_methods'
=> true irb>[1, 2, 3, 4].what? 4 
[1, 2, 3, 4].last == 4  
[1, 2, 3, 4].pop == 4 
[1, 2, 3, 4].lenght == 4
[1, 2, 3, 4].size == 4
[1, 2, 3, 4].count == 4
=>[:last, :pop, :length, :size, :count, :max]

又是一个例子

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

module M; end
class A; include M; end
class B < A; end
class C < B; end

b = B.new
b.instance_of? A  #=> false
b.instance_of? B  #=> true
b.instance_of? C  #=> false
b.instance_of? M  #=> false

b.kind_of? A      #=> true
b.kind_of? B      #=> true
b.kind_of? C      #=> false
b.kind_of? M      #=> true

Scheme中甚至有指令指针级别的反射。例子略。

作用

解释究竟反射机制能够带来什么好处之前，先来看看具体的Reflection机制，以明白透过常见的Reflection支持，在程序中究竟能做到那些事情。这里以Java为例介绍，目的不在介绍Java完整的Reflection API，而是透过Java，帮助大家了解Reflection的一般性概念。

在Java中反射机制的源头，就是一个叫“Class”的class(在C#中有一个相似的类别，则叫做Type)。这个类别有点特殊，原因在于此类别的每一个对象都用来表示系统中的每一个类别。

具体来说，每个Class对象都描述了每个类别的相关信息，也提供你透过它可以进行的一些操作。想要开始Reflection的动作，就必须先取得Class类别的对象。最常被运用到的两个途径，一个便是Object(所有对象皆继承的类别)所提供的getClass()函数，另一个则是Class类别所提供的forName()静态函数。

前者让你得以取得一个对象(尤其是类型未知的对象)所属的类别，而后者则让你得以指定一个类别的名称后，直接得到该类别对应的Class对象。

有了Class对象之后，便能“审视”自身的特性，这些特性包括了它隶属于那个Package、类别本身究竟是Public还是Private、继承自那一类别、实作了那些接口等。更重要的是，你可以得知它究竟有那些成员变量以及成员函数(包括建构式)

透过这个自我审视的过程，程序便能够了解它所要处理的对象(尤其是类型未知的对象)，究竟具备了什么特质。对运用反射机制的程序而言，所了解到的这些特质，便会影响到该程序的运作行为。

取得了某类别的成员变量后(在Java中是以Field类别的对象表示)，便可以取得该类别对象的成员变量值，也可以设定其值。同样的，取得了某类别的成员函数后(在Java中是以Method类别的对象表示)，便可取得该成员函数的回传类型、传入的自变量列表类型，当然更重要的是，Method类别的对象，可被用以呼叫类别对象的相对应成员函数。

有了反射，程序代码在撰写及编译的时间点，毋需明白实际在运行时，究竟会涉及那些类别以及它们各自的行为。你所写下的程序代码，可以完全是对要处理的类别一无所知，也可以是对他们有一点基本的假设(例如要处理的类别都具有相同名称的函数，却没有实作相同的接口，或是继承同样的类别)，一切都可以等到执行时期，透过自我审视的能力，了解要面对的对象究竟具备什么特性，再依据相对应的逻辑，动态利用程序代码控制。 当程序毋需将行为写死，便消除了相依性

有了如此动态的能力，程序代码在撰写时毋需将行为写死，包括要处理的类别、要存取的成员变量、要呼叫的函数等。这大大增加了程序弹性，同时也增加了程序的扩充性。

举例来说，一个连接数据库的Java系统而言，在编译时期是不需要知道究竟运作时会使用那一个JDBC驱动程序，系统只需要透过某种方式，例如在设定档中指定类别名称，那么程序便可以依据这类别名称，加载相对应的JDBC驱动程序，程序代码中完全可以不涉及具体的JDBC驱动程序究竟为何。

总结

本来应该对程序员透明的机制，现在却暴露给了程序员，使得我们有能力去操纵它，让它能够更灵活地完成我们的工作。

所以说，反射这种东西，确实破坏了封装的初衷，但他们两者之间并不是绝对的对立。想一想，我们封装、隐藏细节、建立抽象屏障，无外乎都是为了降低程序的复杂度——这是工程上的折衷。但是在大量的实践中我们发现，我们抽象出来的通用模式并不是银弹，很多问题在它构建的框架之下解决起来就非常麻烦。

所以有了反射这么一手，把很多难以预测的问题留到运行时，动态地去考虑去解决。这也就使得我们在走投无路时，还可以有一道后门开着让我们大摇大摆地进入。

同时。

计算机程序在执行完一系列语句指令后，它知道自己执行的是啥么？它知道它自己是在干什么么？反射，就是试图在语言层面提供一种这样的能力：让代码有自省能力，让代码知道自己在干什么，尽管目前的实现还很初级、很浅薄。

结语

对于编程模式的研究，在我看来有点类似一把砍柴刀，磨刀不误砍柴工，这方面的研究学习在不同的语言和语法实现上，会有着催化剂般的作用。就像数学基础之于计算机算法。

参考资料

1. 动态类型语言和鸭子类型
2. 鸭子类型:一切都是为了复用
3. 初识go语言以及鸭子类型
4. 编程语言中的 鸭子模型(duck typing)
5. 动态与弹性 细看编程语言的反射机制
6. 为什么语言里要提供“反射”功能？
7. 语言的反射为什么比较慢，反射存在的意义是什么？为什么C++没有反射？
8. 元编程的魅力——反射机制

海量字符串检索是很考验算法效率的工作。Trie树和PAT树常用，但是内存占用严重。在垃圾邮件过滤或网络爬虫这种不要求检索结果完全正确的场景下，布隆过滤器是个很好的选择。

Hash函数

Hash（中译为哈希，或者散列）函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面（这些小的数据集叫做哈希值，或者散列值）。Hash table（散列表，也叫哈希表），是根据哈希值(Key value)而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。时间复杂度只有O(1).

哈希函数有以下两个特点：

• 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。但也可能不同，这种情况称为“散列碰撞”（或者“散列冲突”）。
  解决冲突的方法有许多，如向左或向右移位，拉链法等等。在数据量不大的情况下，Hash函数作为查找的解决方法看上去是很美好的。然而，数据量大了之后呢。不妨设想下面的应用场景。

假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL，怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：

1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
4. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。

以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。

方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？

方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。

方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。

方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍

实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

上面所举的爬虫只是一个例子，在允许少量错误的情况下，布隆过滤器将是最好的选择。

布隆过滤器（Bloom Filter）

布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。

基本思想

如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

优缺点

• 优点——相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
• 缺点——误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。

误算率（False Positive）分析

一个Bloom Filter有以下参数：

m | bit数组的宽度（bit数）
n | 加入其中的key的数量
k | 使用的hash函数的个数
f | False Positive的比率

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：1 - 1/m

那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是：(1 - 1 / m)^k

如果我们插入了 n 个元素，那么某一位仍然为 “0” 的概率是：(1 - 1 / m) ^ k*n

因而该位为 “1”的概率是：1 - (1 - 1 / m) ^ k*n

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：

1 - (1 - 1 / m) ^ k*n ≈ (1 - e ^ (-k * n / m)) ^ k

其实上述结果是在假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立为前提计算出来的，不难看出，随着 m （位数组大小）的增加，假正例（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升，对于给定的m，n，如何选择Hash函数个数 k 由以下公式确定：

m / n * ln2 ≈ 0.7 * m / n

此时False Positives的概率为：2 ^ -k ≈ 0.6185 ^ (m / n)

而对于给定的False Positives概率 p，如何选择最优的位数组大小 m 呢，

m = -n * lnp / (ln2) ^ 2

上式表明，位数组的大小最好与插入元素的个数成线性关系，对于给定的 m，n，k，假正例概率最大为：(1 - e ^ (-k * (n + 0.5)/(m - 1))) ^ k

值得注意的是，k值并非越大越好。可以证明，当 k = ln(2) * m/n 时出错的概率是最小的。

操作

1.加入字符串

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。

当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i个哈希函数映射的位置hash_i(x)就会被置为1（1≤i≤k）。

注意：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个”1”处）。

2. 检查字符串是否在集合中

在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hash_i(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y₁就不是集合中的元素（因为y1有一处指向了“0”位）。y₂或者属于这个集合，或者刚好是一个false positive。

3. 删除字符串

通常，字符串加入了就被不能删除了，因为删除会影响到其他字符串，且无法判断删除字符串是否真在集合内。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。

实现

C语言内，并没有定义Bitmap这个容器，所以需要自己实现。

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 268435456

/*init bitmap*/
unsigned char * bitmap_init(int size){
	int bytes;
	unsigned char * p = NULL;
	if(size % 8 == 0) 
		bytes = size / 8;
	else 
		bytes = size / 8 + 1;
	p = (unsigned char *)malloc(bytes);
	if(NULL == p)
		return NULL;
	memset(p, 0, bytes);
	return p;
}

/*set flag on a certain index bit*/
int bitmap_set(unsigned char * bitmap, int index, int flag){
//index range should have been checked outside!
	int seg = index / 8;
	int off = index % 8;
	unsigned char p =  0x1<< off;
	if(flag == 1)
		bitmap[seg] |= p;
	else if(flag == 0)
		bitmap[seg] &= ~p;
	else
		return 0;
	return 1;
}

/*get flag on a certain index bit*/
int bitmap_get(unsigned char * bitmap, int index){
///check index range outside first!
	int seg = index / 8;
	int off = index % 8;
	unsigned char p = 0x1 << off; 	int tmp = bitmap[seg] & p; 	return tmp > 0 ? 1 :0;
}
/*free bitmap*/
void bitmap_free(unsigned char * bitmap){
	free(bitmap);
	*bitmap = NULL;
}

之后，通过位图的置位和取位即可完成Bloom Filter的插入和检测操作。Hash函数选取如下（实际上，可以通过一个函数生成k个独立的哈希函数，存在优化空间）

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

unsigned int RSHash(char* str, unsigned int len)
{
   unsigned int b    = 378551;
   unsigned int a    = 63689;
   unsigned int hash = 0;
   unsigned int i    = 0;

   for (i = 0; i < len; str++, i++)
   {
      hash = hash * a + (*str);
      a = a * b;
   }

   return hash;
}
/* End Of RS Hash Function */

unsigned int JSHash(char* str, unsigned int len)
{
   unsigned int hash = 1315423911;
   unsigned int i    = 0;

   fo r(i = 0; i < len; str++, i++)
   {
      hash ^= ((hash << 5) + (*str) + (hash >> 2));
   }

   return hash;
}
/* End Of JS Hash Function */

unsigned int PJWHash(char* str, unsigned int len)
{
   const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
   const unsigned int ThreeQuarters     = (unsigned int)((BitsInUnsignedInt  * 3) / 4);
   const unsigned int OneEighth         = (unsigned int)(BitsInUnsignedInt / 8);
   const unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
   unsigned int hash = 0;
   unsigned int test = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (hash << OneEighth) + (*str);
      if((test = hash & HighBits) != 0) {
         hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
      }
   }

   return hash;
}
/* End Of  P. J. Weinberger Hash Function */

unsigned int ELFHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int x    = 0;
   unsigned int i    = 0;

   for (i = 0; i < len; str++, i++) {
      hash = (hash << 4) + (*str);
      if ((x = hash & 0xF0000000L) != 0) {
         hash ^= (x >> 24);
      }
      hash &= ~x;
   }

   return hash;
}
/* End Of ELF Hash Function */

unsigned int BKDRHash(char* str, unsigned int len)
{
   unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (hash * seed) + (*str);
   }

   return hash;
}
/* End Of BKDR Hash Function */

unsigned int SDBMHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (*str) + (hash << 6) + (hash << 16) - hash;
   }

   return hash;
}
/* End Of SDBM Hash Function */

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash;
}
/* End Of DJB Hash Function */

unsigned int DEKHash(char* str, unsigned int len)
{
   unsigned int hash = len;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
   }
   return hash;
}
/* End Of DEK Hash Function */

unsigned int BPHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int i    = 0;
   for(i = 0; i < len; str++, i++)
   {
      hash = hash << 7 ^ (*str);
   }

   return hash;
}
/* End Of BP Hash Function */

unsigned int FNVHash(char* str, unsigned int len)
{
   const unsigned int fnv_prime = 0x811C9DC5;
   unsigned int hash      = 0;
   unsigned int i         = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash *= fnv_prime;
      hash ^= (*str);
   }

   return hash;
}
/* End Of FNV Hash Function */

unsigned int APHash(char* str, unsigned int len)
{
   unsigned int hash = 0xAAAAAAAA;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash ^= ((i & 1) == 0)
         ? (  (hash <<  7) ^ (*str) * (hash >> 3))
         : (~((hash << 11) + ((*str) ^ (hash >> 5))));
   }

   return hash;
}
/* End Of AP Hash Function */

/*Hash string with 11 different hash function(flag = 0)
Or Search string in a maked bloom filter(flag = 1)
*/
int bloomfilter_insert(unsigned char * bitmap, char* emailstring, int flag){
	unsigned int index;

	index = RSHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = JSHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = PJWHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = ELFHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = BKDRHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = SDBMHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = DJBHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = DEKHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = BPHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = FNVHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = APHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	return 1;
}

测试部分略。

结语

实际操作中，Bloom Filter达到了和Trie一样的效果，且时间短，占用内存少。可见其效率。实际上，Bloom Filter已有诸多应用：

• Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
• Squid 网页代理缓存服务器在 cache digests中使用了也布隆过滤器。
• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
• Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

参考资料

1. 维基百科：布隆过滤器
2. 数学之美二十一：布隆过滤器（Bloom Filter）
3. 布隆过滤器(Bloom Filter)详解 - Haippy - 博客园
4. 海量数据处理算法—Bloom Filter
5. 那些优雅的数据结构(1) : BloomFilter——大规模数据处理利器
6. Bloom Filter算法详解及实例
7. bitmap应用及C语言实现
8. bitmap C语言实现
9. General Purpose Hash Function Algorithms

前言：编程第一次大作业，海量字符串检索。C语言，并要求使用trie树结构以及bloomfilter两种技术实现，体会它们的特点。这里对Trie做些学习笔记。

Trie树

Trie树，又称单词查找树、字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的，例如邮箱的公共后缀。

Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

特点

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同
   例如，给出一组单词：inn, int, at, age, adv, ant, 我们可以得到下面的Trie树

可以看出：

• 每条边对应一个字母。
• 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
• 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀”a”，所以他们共享从根节点到节点”a”的边。

实现

1. 插入过程

对于新的单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点做标记，表示该单词已插入trie树。

2. 检索过程

从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点没有标记，则表示该单词不存在，若最后的节点有标记，表示该单词存在。

3. 删除节点

很少使用，从该节点开始，释放它和所有子节点占用的空间。

4. 代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct TrieNode {
	int count; //statistics
	struct TrieNode* next[MAX];
}TrieNode;

TrieNode* CreateNode(){
	TrieNode* p = (TrieNode*)malloc(sizeof(TrieNode));
	p->count=0;
	memset(p->next, 0, sizeof(p->next));
	return p;
}

/*Insert new entry*/
void InsertTrieNode(TrieNode* pRoot, char *s, int flag){
	TrieNode *p = pRoot;
	int i,k;
	i = 0;
	while(s[i]){
		//confirm branch
		if(s[i] >= '0' && s[i] <= '9')
 			k = s[i++] - '0' + 2;
 		else if(s[i] >= '@' && s[i] <='Z')
 			k = s[i++] - '@' + 12;
 		else if(s[i] >= 'a' && s[i] <= 'z')
 			k = s[i++] - 'a' + 13;
 		else if(s[i] == '.' || s[i] == '-')
 			k = s[i++] - '-';
 		else if(s[i] == '_'){
 			k = 39;i++;
 		}
 		else
 			return;
 		if(NULL == p->next[k]) 
			p->next[k] = CreateNode();		
		p = p->next[k];
	}
	//mark the trie string
	p->count = flag;
}

/*Match certain string*/
int SearchTrie(TrieNode* pRoot, char *s){
	TrieNode *p = pRoot;
	int i,k;
	i = 0;
	while(s[i]){
		if(s[i] >= '0' && s[i] <= '9')
 			k = s[i++] - '0' + 2;
 		else if(s[i] >= '@' && s[i] <='Z')
 			k = s[i++] - '@' + 12;
 		else if(s[i] >= 'a' && s[i] <= 'z') 
			k = s[i++] - 'a' + 13;
 		else if(s[i] == '.' || s[i] == '-')
 			k = s[i++] - '-';
 		else if(s[i] == '_'){
 			k = 39;i++;
 		}
 		else
 			return 0;
 		if(p->next[k] == NULL)
			return 0;
		p = p->next[k];
	}
	if(p->count > 0){
		return p->count;
	}
	else
		return 0;
}

}

运行结果略。

查找性能分析

在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。

如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。如：若关键字长度最大是5，则利用trie树，利用5次比较可以从26^5＝11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行约23.5次比较。

Trie树的应用

• 串的快速检索：
  给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
  在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
• 串排序：
  给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。
  用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
• 最长公共前缀
  对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题（以后补上）。

Patricia Trie

针对，Trie树占用空间较多的缺点。可以对每个trie树节点做压缩工作，从而节省程序占用的内存空间。如果一颗Trie中有很多单词只有一个儿子结点，可以用Patricia Trie（Linux内核中叫做Radix Tree）压缩存储。由于#结束符标记被看作是一个叶子结点，那么一颗Patricia Trie的任何内部结点有2个或以上的孩子结点。

Linux radix树最广泛的用途是用于内存管理，结构address_space通过radix树跟踪绑定到地址映射上的核心页，该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。

作为Trie树的优化变异，Patricia树也可进行Trie树的操作。实现略。

Trie树之外

除了Trie树，最常用的字符串检索有Knuth-Morris-Pratt算法（最长前缀匹配），以及Boyer-Moore算法（最长后缀匹配）。关于这两个算法，参考资料的6和7的链接是我见过介绍的最好的，深入浅出易于理解。这里就不再废话了。

参考资料

1. http://blog.csdn.net/hguisu/article/details/8131559
2. http://blog.csdn.net/sjjbupt/article/details/6758309
3. http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=28977986&id=3807947
4. http://www.cnblogs.com/ljsspace/archive/2011/06/27/2091771.html
5. http://blog.chinaunix.net/uid-13245160-id-84371.html
6. http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
7. http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

许久未写过日志，实在是苦于终日碌碌无为的状态。更可悲的是，这种状态已经维持了近5个月了。我向来以做成事作为追求的目标。真正进入实验室后，却发现许多事还未做完，就被中途砍断。以至于重复做着机械式的工作，没有理由和时间踏实学习和做成一件事。自10号开学以来，情况并未见好转。趁着假期偷个闲，也寄希望于逃离琐事能把这些都看明白吧。

关于如何前进

回顾过去，初三、高三、大四的状态是我最满意的。那时，每天为做成一件事而努力着。最后也都能得偿所愿。大四上，我完成了两篇论文，远游两次颇有收获，岁末实习经验money双收。高三、初三的学习如鱼得水。略回想一下，那时努力时并不特别在意结果如何，只是专心做着该做的事。反倒之前不顺的几年，频繁的自我反省，最后收效甚微。也许，专注做事是目前最为迫切的了。该做的体育委员就真认真写策划，该负责的ONOS项目就认真看文档，做开发；看不到希望和前景的就果断放弃，不去希冀未来。简言之，该专注的就埋头去做，其余的就不去期待反馈。

我相信，以我的能力，埋头做的事即使不是设计的预期，也会有个妥当的结果。

有时候，解药并不一定长篇累牍，只是想太多。

关于择偶观等

晚饭后，与嫂子闲聊。从和表哥的认识到之后关心的处理，还是略有启发。这里先摆上结论：较为强势，有生活能力的女性对日后的家庭生活更有帮助。

诚如我们的共识，男人最后毕竟是要撑起整个家庭，在外挣钱养家的，不大可能操心家庭里太多。包括衣装，家务，做饭等等。这里并不是说不负责，只是主要精力不在这里。事业、家庭、社交几个方面，男人不可能全面涉及。从常规角度思考，重事业的男人会更有利于家庭的维系和发展。那么，一个精于或者说至少积极于家庭、社交的妻子就会更好的弥补这个角色缺陷。让男主人在下班回家后少操很多心。小鸟依人型的伴侣诚然在交往时，可以充分满足男人的大男子主义虚荣感，但在真实的生活面前就显得有些不够省心。

实际上，我的身边并不是没有这样的例子。嫂子就是一个，母亲又是一个。一个听在眼里，一个看在眼里。表哥醉心科研，短于社交，嫂子帮他完成家庭外的交往工作，察言，观色，为人，处世。在家庭生活里，也承担着几乎所有的家务，甚至包括维修家用电器等。无疑，表哥是幸福的。母亲从小就承担着我的教育责任和家庭的社交角色，并且精于此道。同时，在日常生活里，眼中有活，虽然由父亲承担了大部分，但是多半是母亲提醒的。设身处地地思考下，着实为表哥和父亲感到幸运。

一个眼里有活，精于察言观色的女性作为终身伴侣，从长远来看，会让家庭更稳定。而眼里有活，精于察言观色正是较为强势，会生活的外在表现。

的确，和这样的女性相处时，会出现矛盾。身边的无数实践已经提前证明了这点。不过多半的争吵是苦口良药，经过冷静的沟通后就会缓解。

说了这么多，纸上得来终觉浅。做了这么久的理论家，谁能来帮我圆一个实践家的梦呢？

关于其他

实际上，晚上的聊天内容还有很多。除了非普适内容和以上的核心论点外，就不剩多少了。谈到逆反心理这个话题时，有个点倒是异常有趣。表妹从小父母离异，由姑姑们培养长大。对姑姑们严格的管教多有怨言，而严厉的管教却还是依旧。逆反心理终会随年龄消退。但是嫂子提醒了一点：姑姑们虽然教育有方，不过孩子都是男孩。对男孩的教育方式真的同样适用于女孩吗？

虽说此话本身并没有什么可讨论的。不过阐发来看，平时许多我们习以为常的事，真的就是正确的看法吗？还是只是我们习惯了看问题的角度？这个我并没有找到实例，有待进一步讨论。