搜索与排名思路整理

学习《集体智慧编程》第4章的思路整理：

本章的主要内容就是建立一个模拟的全文搜索引擎，主要的大步骤为：1.检索网页，2.建立索引，3.对网页进行搜索 4.多种方式对搜索结果进行排名

一、检索网页：主要利用python写了一个爬虫软件，通过爬取一个网站上链接来不断的扩充爬取的内容。主要利用了python的urllib库和BeautifulSoup库。这部分比较简单，核心代码如下：

这里采用了广度优先搜索方式

二、建立索引

1.sqlite数据库的使用：

在python2.x版本中需要自己下载安装这个数据库，但是在python3.x中我们只需要 import sqlite3即可。首先需要修改类的一些内建函数：

然后建立数据库，这里首先需要准备5张数据库表，分别为：urllist（保存的是已经过索引的url列表）、wordlist（保存的是单词列表）、wordlocation（保存的是单词在文档中的所处的位置列表）、link（保存两个Url ID 指明从一个表到另一张表的连接关系） linkwords（利用了字段wordid和linkid记录了哪些单词和链接实际相关），并且建立一些索引完整的数据库schema如下图：

具体代码如下：

2.在网页中查找单词，此处还是利用了BeautifulSoup的强大功能，将网页中的所有的文字信息提取出来，去掉一些标签，属性之类的。然后进行单词的分词。在这里的单词分词都是针对英文单词的，关于中文单词的分词，有个名为jieba的库可以实现。感兴趣的可以看一下：https://github.com/fxsjy/jieba/tree/jieba3k

3、加入索引，将网页以及所有的单词加入索引，在网页和单词之间建立关联，并且保存单词在文档中的位置。在本例中，文档的位置就是在列表中的索引号

三、查询

四、排名

1.基于内容的排名：评价度量包括以下三种：单词频度，文档位置，单词距离

首先我们要设定一个归一化函数，对结果进行归一化处理，使得他们具有相同的值域和变化方向。

 基于内容的排名的算法属于传统的早期搜索引擎使用的度量方式。其三种评价度量的代码分别如下：

2.著名的PageRank算法

Google使用的算法，为每一个网页都赋予了一个只是网页重要程度的评价值。网页的重要性是依指向该网页的所有的其他网页的重要性以及这些网页所包含的连接数求得的。

PageRank 使用一个阻尼因子：0.85

关于该算法的具体内容，可以自行百度。。。也可以查看http://www.cnblogs.com/FengYan/archive/2011/11/12/2246461.html的博文