本文首先会讨论搜索引擎的核心难题，同时讨论早期搜索引擎关于结果页面重要性评价算法的困境，借此引出PageRank产生的背景。第二部分会详细讨论PageRank的算法，以及处理Dead Ends的方法。

搜索引擎的难题

Google早已成为全球最成功的互联网搜索引擎，但这个当前的搜索引擎巨无霸却不是最早的互联网搜索引擎，在Google出现之前，曾出现过许多通用或专业领域搜索引擎。Google最终能击败所有竞争对手，很大程度上是因为它解决了困扰前辈们的最大难题：对搜索结果按重要性排序。而解决这个问题的算法就是PageRank。毫不夸张的说，是PageRank算法成就了Google今天的低位。要理解为什么解决这个难题如此重要，我们先来看一下搜索引擎的核心框架。

早期搜索引擎的做法

不评价

这个看起来可能有点搞笑，但实际上早期很多搜索引擎（甚至包括现在的很多专业领域搜索引擎）根本不评价结果重要性，而是直接按照某自然顺序（例如时间顺序或编号顺序）返回结果。这在结果集比较少的情况下还说得过去，但是一旦结果集变大，用户叫苦不迭，试想让你从几万条质量参差不齐的页面中寻找需要的内容，简直就是一场灾难，这也注定这种方法不可能用于现代的通用搜索引擎。

基于检索词的评价

基于检索词评价的思想非常朴素：和检索词匹配度越高的页面重要性越高。“匹配度”就是要定义的具体度量。一个最直接的想法是关键词出现次数越多的页面匹配度越高。比如搜索“719 博客”的例子：假设A页面出现“719”5次，“博客”10次；B页面出现“719”2次，“博客”8次。于是A页面的匹配度为5 + 10 = 15，B页面为2 + 8 = 10，于是认为A页面的重要性高于B页面。很多朋友可能意识到这里的不合理性：内容较长的网页往往更可能比内容较短的网页关键词出现的次数多。因此，我们可以修改一下算法，用关键词出现次数除以页面总词数，也就是通过关键词占比作为匹配度，这样可以克服上面提到的不合理。

早期一些搜索引擎确实是基于类似的算法评价网页重要性的。这种评价算法看似依据充分、实现直观简单，但却非常容易受到一种叫“Term Spam”的攻击。

Term Spam

现在假设Google单纯使用关键词占比评价页面重要性，而我想让我的博客在搜索结果中排名更靠前（最好排第一）。那么我可以这么做：在页面中加入一个隐藏的html元素（例如一个div），然后其内容是“719”重复一万次。这样，搜索引擎在计算“张洋 博客”的搜索结果时，我的博客关键词占比就会非常大，从而做到排名靠前的效果。更进一步，我甚至可以干扰别的关键词搜索结果，例如我知道现在欧洲杯很火热，我就在我博客的隐藏div里加一万个“欧洲杯”，当有用户搜索欧洲杯时，我的博客就能出现在搜索结果较靠前的位置。这种行为就叫做“Term Spam”。

早期搜索引擎深受这种作弊方法的困扰，加之基于关键词的评价算法本身也不甚合理，因此经常是搜出一堆质量低下的结果，用户体验大大打了折扣。而Google正是在这种背景下，提出了PageRank算法，并申请了专利保护。此举充分保护了当时相对弱小Google，也使得Google一举成为全球首屈一指的搜索引擎。

PageRank算法

PageRank算法的核心思想有2点：

1）一页面有越多的入链，那么这个页面就越重要。入链就是指别的网页中指向该页面的链接，比如A页面中，有一个链接指向B页面，那个A页面中的指向B页面的那个链接就是B页面的一个入链。这个思想背后的含义可以理解为，有很多页面引用我，说明我的质量好，大家都愿意从别的地方来我这。就好像有一个人写了一篇文章，然后别人觉得写得很好，就会在别的地方引用它，是一个道理。

2）指向一个页面的链接所在的页面质量越高，这个链接的权重就越大。举个例子，比如有一个页面www.xxx.com，这个页面在我的这篇博客网页中被引用，和在百度首页被引用，是有很大差别的，因为我这篇博客的页面，相对于百度首页的页面，质量都不在一个档次，因此要区别对待，给予不同的权重。

现在假设世界上只有四张网页：A、B、C、D，其抽象结构如下图：

显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。

然后需要用一种合适的数据结构表示页面间的连接关系。其实，PageRank算法是基于这样一种背景思想：被用户访问越多的网页更可能质量越高，而用户在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低。最简单的，我们可以假设当一个用户停留在某页面时，跳转到页面上每个被链页面的概率是相同的。例如，上图中A页面链向B、C、D，所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页，则可以组织这样一个N维矩阵：其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵（Transition Matrix）。下面的转移矩阵M对应上图：

然后，设初始时每个页面的rank值为1/N，这里就是1/4。按A-D顺序将页面rank为向量v：

注意，M第一行分别是A、B、C和D转移到页面A的概率，而v的第一列分别是A、B、C和D当前的rank，因此用M的第一行乘以v的第一列，所得结果就是页面A最新rank的合理估计，同理，Mv的结果就分别代表A、B、C、D新rank：

然后用M再乘以这个新的rank向量，又会产生一个更新的rank向量。迭代这个过程，可以证明v最终会收敛，即v约等于Mv，此时计算停止。最终的v就是各个页面的pagerank值。例如上面的向量经过几步迭代后，大约收敛在（1/4, 1/4, 1/5, 1/4），这就是A、B、C、D最后的pagerank。

处理Dead Ends

上面的PageRank计算方法假设Web是强连通的，但实际上，Web并不是强连通（甚至不是联通的）。下面看看PageRank算法如何处理一种叫做Dead Ends的情况。

所谓Dead Ends，就是这样一类节点：它们不存在外链。看下面的图：

注意这里D页面不存在外链，是一个Dead End。上面的算法之所以能成功收敛到非零值，很大程度依赖转移矩阵这样一个性质：每列的加和为1。而在这个图中，M第四列将全为0。在没有Dead Ends的情况下，每次迭代后向量v各项的和始终保持为1，而有了Dead Ends，迭代结果将最终归零（要解释为什么会这样，需要一些矩阵论的知识，比较枯燥，此处略）。

处理Dead Ends的方法如下：迭代拿掉图中的Dead Ends节点及Dead Ends节点相关的边（之所以迭代拿掉是因为当目前的Dead Ends被拿掉后，可能会出现一批新的Dead Ends），直到图中没有Dead Ends。对剩下部分计算rank，然后以拿掉Dead Ends逆向顺序反推Dead Ends的rank。

以上图为例，首先拿到D和D相关的边，D被拿到后，C就变成了一个新的Dead Ends，于是拿掉C，最终只剩A、B。此时可很容易算出A、B的PageRank均为1/2。然后我们需要反推Dead Ends的rank，最后被拿掉的是C，可以看到C前置节点有A和B，而A和B的出度分别为3和2，因此C的rank为：1/2 1/3 + 1/2 1/2 = 5/12；最后，D的rank为：1/2 1/3 + 5/12 1 = 7/12。所以最终的PageRank为（1/2, 1/2, 5/12, 7/12）。

引用http://blog.codinglabs.org/articles/intro-to-pagerank.html

RandNet的基本思想

RankNet是一种Pairwise的Learning to Rank算法。

RankNet方法就是使用交叉熵作为损失函数，学习出一些模型（例如神经网络、决策树等）来计算每个pair的排序得分，学习模型的过程可以使用梯度下降法。

方法流程

首先，我们要明确RankNet方法的目的就是要学习出一个模型，这个模型就是给文档算法的函数f(d)。其中d为文档特征。

哪一个网页与搜索更相关

网页u比第网页v与搜索更相关的的概率：

交叉熵作为损失函数。

我们知道，在机器学习中，一般来说，要训练，就要有个Loss Function，来衡量当前模型与Training Set的Loss，也就是差距，然后训练的过程就是把Loss不断减少的过程。

梯度下降法更新迭代求最优的网络模型

最后我们说一下RankNet算法的一大好处：使用的是交叉熵作为损失函数，它求导方便，适合梯度下降法的框架；而且，即使两个不相关的文档的得分相同时，C也不为零，还是会有惩罚项的。

引用http://blog.csdn.net/puqutogether/article/details/42124491
引用http://blog.csdn.net/orthocenterchocolate/article/details/43203891

vector是C++标准模板库中的部分内容，中文偶尔译作“容器”，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

1
2
3
4
5
6
7
8
9
10

//简单的使用方法
vector<int> test;//建立一个vector
test.pushback(1);//把1vector,这样test[0]就是1
vector<int>::iterator iter=test.begin();//定义一个可以迭代int型vector的迭代器iter，它指向test的首位
while(iter!=test.end()) {cout<<*iter;iter++}//iter++指的是向前迭代一位，直到iter到超出末端迭代器为止，输出迭代器指向的值
c.erase(pos)//删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end)//删除[beg,end)区间的数据，传回下一个数据的位置。
c.insert(pos,elem)//在pos位置插入一个elem拷贝
c.size()//返回容器中实际数据的个数。
c1.swap(c2);swap(c1,c2)//将c1和c2元素互换。同上操作。

内存机制

1
2
3
4
5
6
7
8

vector<int> arr;
ofstream wf("1.txt");
for(int i=0;i<100;++i)
{
	arr.push_back(i);
	wf<<"capacity="<<arr.capacity()<<",size="<<arr.size()<<end;
}
wf.close();

capacity()返回的是当前vector对象缓冲区（后面的对vector维护的内存空间皆称为缓冲区）实际申请的空间大小，而size()返回的是当前对象缓冲区中存储数据的个数，capacity永远是大于等于size的，当size和capacity相等时继续添加数据时vector会扩容。
基本上是扩容已有空间的50%。
从文件中可以观察capacity的变化，我们可以更直观的去扩容的源码。

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

if (max_size() - size() < _Count)_Xlen();	// result too long，抛出异常_THROW(length_error, "vector<T> too long");
else if (_Capacity < size() + _Count){	// not enough room, reallocate
	_Capacity = max_size() - _Capacity / 2 < _Capacity? 0 : _Capacity + _Capacity / 2;	// try to grow by 50%，扩容50%
	if (_Capacity < size() + _Count)//扩容50%后依然不够容下，则使容量等于当前数据个数加上新增数据个数
		_Capacity = size() + _Count;
	pointer _Newvec = this->_Alval.allocate(_Capacity);//申请新的空间
	pointer _Ptr = _Newvec;
	//拷贝原有数据到新的内存中
	...
	//拷贝新增数据到新的内存的后面
	...
	//释放原来申请的内存
	...
}

对的，就是每次扩容50%。至于删除容器中数据的时候，缓冲区大小并不会改变，仅仅只是清楚了其中的数据，只有在析构函数调用的时候vector才会自动释放缓冲区。

vector.resize() 与 vector.reserve()的区别

reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素时，需要用push_back()/insert()函数。
resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。

引用http://blog.csdn.net/mfcing/article/details/8746256

map是基于红黑树实现的，可以快速查找一个元素是否存在，是关系型容器，能够表达两个数据之间的映射关系。

unordered_map的插入、删除、查找 性能都优于 hash_map 优于 map，所以首选为 unordered_map.

它的缺陷是元素是无序的，当使用时候需要元素是有序的时候，不可以用它。

使用map/multimap之前要加入头文件#include

map和multimap内部的数据结构也是平衡二叉树。map 和 multimap 拥有 set 和 multiset 所有能为和所有操作函数。

map和multimap根据元素的key自动对元素进行排序，要修改元素的key必须先删除拥有该key的元素，然后插入拥有新的key/value的元素。

1.常用函数

注意：所有的搜索函数，参数是key，而不是value。这样你就不能以 find() 搜寻拥有某特定 value 的元素。

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

//返回键值等于 key 的元素个数
m.count(key)
//返回键值等于 key 的第一个元素，找不到就返回 end()
m.find(key)
//返回 键值 >= key 的第一个元素位置
m.lower_bound(key)
//返回 键值 >= key 的第一个元素位置
m.upper_bound(key)
//返回 键值 == key 的元素区间
m.equal_range(key)

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

//插入
c.insert(elem) 
c.insert(pos,elem)
c.insert(beg,end)
//删除
c.erase(elem)
c.erase(pos)
c.erase(beg,end)
//使迭代器失效，注意！！！！
typedef std::map<std::string,float> StringFloatMap;
StringFloatMap coll;
StringFloatMap::iterator pos;
for (pos = coll.begin(); pos != coll.end(); ++pos) 
{
   if (pos->second == value) {
            coll. erase (pos);    // 出错 !!!
   }
}
//正确处理迭代器所指元素的方法
typedef std::map<std::string,float> StringFloatMap;
StringFloatMap coll;
StringFloatMap::iterator pos;
//remove all elements having a certain value
for (pos = coll.begin(); pos != coll.end(); ) 
{
       if (pos->second == value) {
           c.erase(pos++);        // Make clear!!
       }
       else {
           ++pos;
       }
}

将value值传入map

1
2
3
4

//直接赋值
coll["otto"] = 7.7;
//用make_pair()
coll.insert(std::make_pair("otto",22.3));

引用http://blog.csdn.net/lwbeyond/article/details/7313204#