搜索引擎原理实现

绪论

1. 基本要求：
   在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表，这个列表的每一条目至少包含三个元素(标题,网址链接,摘要)。其中的关键字：
   1. “可以接受的时间”：指响应时间，通常也就在“秒”这个量级。更进一步的,这样的响应时间要求不仅要能满足单个用户查询,而且要能在系统设计负载的情况下满足所有的用户。也就是说,系统应该在额定吞吐率的情况下保证秒级响应时间。
   2. ”匹配“：搜索结果应以某种形式包含搜索词
   3. ”列表“：“ 列表”这蕴含着一种“序”(rank)。在绝大多数情况下,L 是相当长的,例如超过1万个条目，而对于一个长长的列表,很少有用户有耐心都审视一遍
2. 网页搜集
   • 这个软件系统操作的数据不仅包括内容不可预测的用户查询,还要包括在数量上动态变化的海量网页,并且这些网页不会主动送到系统来,而是需要由系统去抓取。
   • 搜集方法：
     1.定期搜集（批量搜集）：每次搜集替换上一次的内容。对于大规模搜索引擎来说,每次搜集的时间通常会花几周。而由于这样做开销较大,通常两次搜集的间隔时间也不会很短。这样做的好处是系统实现比较简单,主要缺点是“时新性”(freshness)不高,还有重复搜集所带来的额外带宽的消耗。
     2.增量搜集：开始时搜集一批,往后只是(1)搜集新出现的网页,(2)搜集那些在上次搜集后有过改变的网页,(3)发现自从上次搜集后已经不再存在了的网页,并从库中删除。这样的系统表现出来的信息时新性就会比较高,主要缺点是系统实现比较复杂
   • 扒取实现方案：将 Web 上的网页集合看成是一个有向图,搜集过程从给定起始 URL 集合 S(或者说“种子”)开始,沿着网页中的链接,按照先深、先宽、或者某种别的策略遍历,不停的从 S 中移除 URL,下载相应的网页,解析出网页中的超链接 URL,看是否已经被访问过,将未访问过的那些 URL 加入集合S。外一种可能的方式是在第一次全面网页搜集后,系统维护相应的 URL 集合 S,往后的搜集直接基于这个集合。每搜到一个网页,如果它发生变化并含有新的 URL,则将它们对应的网页也抓回来,并将这些新 URL 也放到集合 S 中;如果 S 中某个 url 对应的网页不存在了,则将它从 S 中删除。
3. 预处理
   主要包括四个方面：
   1. 关键词的提取：主要获取出现频率高的关键字，但应注意去掉要去掉诸如“的”,”在”等没有内容指示意义的词
   2. “镜像网页” (网页的内容完全相同,未加任何修改)或“转载网页”(near-replicas,主题内容基本相同但可能有一些额外的编辑信息等,转载网页也称为“近似镜像网页”)的消除。据统计，当你通过一个 URL在网上看到一篇网页的时候,平均还有另外 3 个不同的 URL 也给出相同或者基本相似的内容。重复的搜集会消耗机器时间和网络带宽资源。而且如果在查询结果中出现,无意义地消耗了计算机显示屏资源,也会引来用户的抱怨。
   3. 链接分析：大量的 HTML 标记既给网页的预处理造成了一些麻烦,也带来了一些新的机遇。例如在同一篇文档中, < H1>和< /H1>之间的信息很可能就比在< H4>和< /H4>之间的信息更重要。再如对“北大学报”这几个字在北京大学学报社会科学版的主页上是没有的,，因此一个仅靠内容文字分析的搜索引擎就不可能返回该主页作为结果。但是北京大学主页上是用“北大学报(社)”作为链接信息指向了北京大学学报社会科学版的主页。因此在很好利用链接信息的搜索引擎中应该能返回北京大学学报社会科学版的主页。
   4. 网页重要程度的计算。根据人们参照科技文献重要性的评估方式,核心想法就是“被引用多的就是重要的”。
4. 查询服务
   • 在预处理后的网页元素，至少包含如下几个方面：
     1. 原始网页文档
     2. URL 和标题
     3. 编号
     4. 所含的重要关键词的集合(以及它们在文档中出现的位置信息)
     5. 其他一些指标(例如重要程度,分类代码等)
   • 而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构,使得一旦得到一个关键词输入,系统能迅速给出相关文档编号的集合输出。而用户搜索看到的是一个列表，因此我们需要完成集合->列表的转化
     1. 根据用户查询内容切词，如用户查询“网络与分布式系统实验室”，忽略一些几乎没有意义的字词（如“的”，“与”等）将搜索内容分成一个词列q = {t 1, t 2 , …, t m },在本例中就是q = {网络,分布式,系统,实验室}。而倒排文件就是用词来作为索引的一个数据结构,显然, q中的词必须是包含在倒排文件词表中才有意义。有了这样的q,它的每一个元素都对应倒排文件中的一个倒排表(文档编号的集合),记作L(t i ),它们的交集即为对应查询的结果文档集合,从而实现了查询和文档的匹配。
     2. 结果排序。我们通过前述关键词的提取过程,形成一篇文档的关键词集合,p = {t 1 , t 2 , …, t n }的时候,很容易同时得到每一个t i 在该文档中出现的次数,即词频,而倒排文件中每个倒排表的长度则对应着一个词所涉及的文档的篇数,即文档频率。但由于网页编写的自发性、随意性较强,仅仅针对词的出现来决定文档的顺序,在Web上做信息检索表现出明显的缺点,于是我们可以通过结合在预处理阶段形成的独立于查询次的重要性指标形成一个更可靠的排序序列
     3. 文档摘要。摘要也是搜索结果的重要组成部分，摘要的生成基本可以归纳成如下两种方式
        1. 静态方式,即独立于查询,按照某种规则,事先在预处理阶段从网页内容提取出一些文字,例如截取网页正文的开头 512个字节(对应 256 个汉字),或者将每一个段落的第一个句子拼起来等。虽然方便简单，但它最大的缺点是摘要和查询无关
        2. 动态方式。即在响应查询的时候,根据查询词在文档中的位置,提取出周围的文字来,在显示时将查询词标亮。为了保证查询的效率,需要在预处理阶段分词的时候记住每个关键词在文档中出现的位置。

Web信息搜集

1. 网页搜集：网页搜集的过程是从 URL 库(初始时包含用户指定的起始种子 URL 集合,可以是1 个或多个)获得输入,解析 URL 中标明的 Web 服务器地址、建立连接、发送请求和接收数据,将获得的网页数据存储在原始网页库,并从其中提取出链接信息放入网页结构库,同时将待抓取的 URL 放入 URL 库,保证整个过程的递归进行,直到 URL 库为空。
   定义 URL 类和 Page 类
   
enum url_scheme{
SCHEME_HTTP,
SCHEME_FTP,
SCHEME_INVALID
};


class CUrl
{
public:
string m_sUrl;// URL 字串
enum url_scheme m_eScheme; // 协议名
string m_sHost; // 主机名
int m_nPort;// 端口号
string m_sPath;// 请求资源
CUrl();
~CUrl();
bool ParseUrl( string strUrl );
private:
void ParseScheme ( const char *url );
};

   有了 URL,搜集系统就可以按照 URL 标识抓取其所对应的网页,网页信息
   保存在 Page 类中。
   
class CPage
{
public:
string m_sUrl;
// 网页头信息
string m_sHeader;
int m_nLenHeader;
int m_nStatusCode;
int m_nContentLength;
string m_sLocation;
bool m_bConnectionState;
// 如果连接关闭,是 false,否则为 true
string m_sContentEncoding;
string m_sContentType;
string m_sCharset;
string m_sTransferEncoding;
// 网页体信息
string m_sContent;
int m_nLenContent;
string m_sContentNoTags;
// link, in a lash-up state
string m_sContentLinkInfo;
// 为搜索引擎准备的链接,in a lash-up state
string m_sLinkInfo4SE;
int m_nLenLinkInfo4SE;
// 为历史存档准备的链接, in a lash-up state
string m_sLinkInfo4History;
int m_nLenLinkInfo4History;
//为搜索准备的链接,in a good state
RefLink4SE m_RefLink4SE[MAX_URL_REFERENCES];
int m_nRefLink4SENum;
//为历史存档准备的链接, in a good state
RefLink4History m_RefLink4History[MAX_URL_REFERENCES/2];
int m_nRefLink4HistoryNum;
map<string,string> m_mapLink4SE;
vector<string > m_vecLink4History;
enum page_type m_eType;
// 网页类型
public:
CPage();
CPage::CPage(string strUrl, string strLocation, char* header, char* body,
int nLenBody);
~CPage();
void ParseHeaderInfo(string header); // 解析网页头信息
bool ParseHyperLinks(); // 从网页体中解析链接信息
bool NormalizeUrl(string& strUrl);
bool IsFilterLink(string plink);
private:
// 解析网页头信息
void GetStatusCode(string header);
void GetContentLength(string header);
void GetConnectionState(string header);
void GetLocation(string header);
void GetCharset(string header);
void GetContentEncoding(string header);
void GetContentType(string header);
void GetTransferEncoding(string header);
// 从网页体中解析链接信息
bool GetContentLinkInfo();
bool GetLinkInfo4SE();
bool GetLinkInfo4History();
bool FindRefLink4SE();
bool FindRefLink4History();
};

2. 避免对网站的重复收集
   造成重复搜集的原因,一方面是搜集程序没有清楚记录已经访问过的URL,另一方面是由于域名与 IP 多重对应关系造成的。解决方法如下
   1. 记录未访问、已访问 URL 和网页内容摘要信息，通过对比未访问、已访问URL去重。除了存储上述“已访问表”和“未访问表”的摘要信息,还存储了已经获取网页内容的摘要信息。存储网页内容的摘要信息的原因是 Web 上存在大量的复制网页,它们是 url 不同,内容完全一样。
   2. 记录未访问和已访问 URL 信息,可以保证搜集的网页中所有的 URL 都不同。但是域名与 IP 的对应存在复杂的关系,导致即使 URL 不同,也可能指向的物理网页是相同的。而可能导致重复的ip与域名的对应方式有：
      1. 多个域名对应一个 IP（如使用虚拟主机）
      2. 一个域名对应多个ip（分布式系统可能用到）
      3. 多个域名对应多个ip

   要解决重复收集网页,就要找出那些指向同一物理位置 URL 的多个域名和IP。这是一个逐渐累积的过程。首先要累积到一定数量的域名和 IP,比如 100 万个,然后把这些域名和 IP 对应的首页和首页链接出的最开始的几个页面抓取回来。如果比较结果一样,则应该归为一组。以后搜集的时候可以只选择其中的一个进行搜集。选择的时候应该优先选择有域名的,有的网站对于直接用 IP 访问是被禁止的。

对搜集信息的预处理

网页预处理的第一步就是为原始网页建立索引,实现索引网页库,有了索引就可以为搜索引擎提供网页快照功能；接下来针对索引网页库进行网页切分,将每一篇网页转化为一组词的集合;最后将网页到索引词的映射转化为索引词到网页的映射,形成倒排文件(包括倒排表和索引词表),同时将网页中包含的不重复的索引词汇聚成索引词表
1. 切词算法
2. 建立倒排文件

信息查询服务

1. 检索算法
2. 动态摘要算法1