搜索技术总结整理

搜索技术总结整理 2006/12/05 

作者：Hontlong from Hour41 (www.hour41.com)

学习搜索有一段时间了，为了复习巩固和提高，特把学习的结果总结一下。本文章搜索只特指小型搜索系统。之所以特指是小型系统，是因为大型小型搜索系统虽然整体处理过程大体相似，但整体架构和要处理的数据量和响应速度是密切相关的，百万量级的和十亿量级的搜索系统是不可同日而语的。

搜索系统处理大体分为：蜘蛛、切词、索引、检索，下面逐个的描述。

1. 蜘蛛

蜘蛛是用来抓取网页的。所谓的抓，其实也就是通过socket向http服务器发送post或者get请求，服务器根据你的请求把页面送给你的过程。大家通常用的IE浏览器就是要先做这个工作，然后在根据返回的Html源码生成你看到的网页。蜘蛛当然不需要去生成网页给人看了，它只是把html存储起来给其它程序用。我看到有人问如何写一个下载动态网页的蜘蛛，其实动态页面和静态页面对于蜘蛛是一样的，都是发送请求和接受，没有实质区别。

搜索技术中，蜘蛛看起来是最容易的。大家学习了一个语言和熟悉TCP/IP后都可以编写一个下载网页的程序了。但是，要写一个适应性强的蜘蛛却是相当难的，因为网络环境太过于复杂，你总是很难想象到别人会发什么给你，也就是蜘蛛要有很强的例外处理能力。最常见的问题是：

网路故障 造成蜘蛛抓取超时，没有抓取到网页或者抓取不全。

网站链接 有些网站对错误的链接或者蜘蛛使用的ip，返回一个很怪的页面，例如它的内部错误信息。

页面问题 页面问题中网页编码是首要问题，各个网站用的编码五花八门，需要你判断和处理合理的编码。有朋友会问，http协议头信息中有charset，html中也有charset，可以方便的判断编码，没错，这是主要的判断方式，但是，如果这两个地方都得不到charset信息呢？

其次，要提高蜘蛛的效率和速度，这就要涉及到待抓取url的权值值计算，因为并不是每个网页对我们来说都是同等重要的。由于网络的无边无际，所以采用广度搜索和深度搜索都不可取，只有采用种权值计算公式采用减枝方法做有效遍历。也有只依赖权值来决定搜索目标的。

最后是蜘蛛的性能。也就是并行处理方式。单个蜘蛛处理能力有限制，因此多采用多线程和多进程的方法，多个蜘蛛同时运行。另外，采用此方法的另一个重要原因是，网络速度是蜘蛛程序的瓶颈。

2.切词

切词仿佛是最简单的。采用最流行的倒序最大前序最大切词方法基本上就够用的了。但是切词也是让我最迷惑的东西，什么是切词？采用上述方法切出来的并不是标准的词语，更像是字符和分割组合，你查一下百度或者googel就可以看到它们的切词实现效果。切词程序真的不是在切词啊。

切词是深入处理中文信息的基本模块。在自然语言分析中也有切词，切词的基本方法和过程也基本相同，但我觉得在两者的是指导思想有些不一样。自然语言的分析很在意切词的准确性，而索引切词确更注重切词结果的覆盖情况。自然语言处理在切词后，需要词性标注和词法语法分析，因此必须切词准确，对新词、命名实体等的处理相对要求要高，而索引切词后就是做倒排索引了，只要能保证索引时切词和查询时的切词是同样的，基本上就可以正确使用索引，只是为了索引效果，需要尽可能的在符合词语的自然分段的基础上，把词的切割粒度定位在在效率和灵活性的一个调和位置，对新词和命名实体的识别就不那么看重。例如：北京大学，在第一中切词中会切割成一个词语，而在后一种切词中，为了保证能使用北京也可以搜索到，会被切割成北京和大学两个词。也有为了效率而做复合索引的，例如把北京大学切割为 北京大学、北京和大学这3个词，方便用户使用任何一个熟悉的词都能搜索到。

通过上面的讨论，分析到切词系统实际上是根据实际应用而不同的。就索引切词来说，切词的准确性并不重要，切词后的词能够快速准确找到索引，才重要。那么怎么切才能让后面的索引做的快速而且准确呢？想一想，我们为什么要切词呢，即便不切词，我们也可以在字上做索引，也可以在字节上做索引，开源搜索醒目lucence默认处理中国语言的方式就是双字切词，两个字两个字的切，例如：北京大学，切割后为，北京 京大 大学。但要讲到效率，根据搜索到的资料数据比较，还是基于词库的自然词切割是效果较好的。我想原因是：1，切割的完整性，不会遗漏词语，也不会有太多废词，例如 京大。因为使用索引查询的人的查询输入，也基本符合中文语法，基本不会出现 京大这样的词，相对的2字切词的处理方式就会产生废词，就要多做和维护一个基本用不到的索引。2，切割的后的词检索的效率，如果基于字或者字节做索引，虽然中国总数有2万多，但是常用的只有4~6千，要在这个范围内映射千万量级以上的文档，索引就比较大，每个字要对应万量级的文档，同时后期的归并和条件过滤处理工作量也比较大，而对应的词是中文语法结构的基本单位，常用词有5~10万，足以承担亿量级的文档索引分担。做了一段时间的索引程序后，我的感觉是词长在2~4之间比较好。

这里讨论的罗嗦的原因是为了比较说明索引切词并不是严格意义上的切词，只是融合了切词逻辑的字符切割。这种切割字符基本符合词语单位，我想是有必然的潜在的语言规则。我在学习切词时有走过弯路，总想把词切割的准确些，再准确些，结果程序效率下降，准确性也不能有明显提高，现在觉得，如果不涉及更深层次额语义处理，并不必要。

3.索引

对于学习过数据库，熟悉数据库基本原理的朋友们来说，做索引并不是很困难的事。现有的索引系统基本是采用倒排索引。基本含义就是在一个文件中记录下一个词在哪篇文章哪个位置出现，以便解析用户输入后可以直接读取对应的文章id，把对应的文章择要提取出来显示给用户。

我认为索引难做的一点是索引的维护，包括插入和删除。而索引的更新(update)，通常索引系统把它转化为删除(delete)和插入(insert)。信息的变更要尽可能快的反映到索引中，这个对索引系统的压力还是比较大的。想一下数据的删除过程，删除一片文章，要知道这篇文章都在哪些词的索引中，要逐个的清理数据，而这个数据清理，通常为了性能，又不是真实的清理，只是把文章对应的数据抹去（清零或做特定标记），这样索引中就像是留下了一个洞，时间一场，索引也就千疮百孔了，所以索引系统需要根据一定的算法计算索引中的空洞比率，在适合的条件下，整理索引，剔除空洞。

另外，插入索引也需要特别注意，简单的索引插入当然没有问题，因为文档id在索引中一般是排序的（整体排序或者分段排序），这样方便检索时快速处理。因此大批量或者频繁的插入时，就会有性能问题。通常的解决方案是采用大小索引的办法，新插入的索引并不直接插入到大索引中（数据处理量相对大），而是临时写入小索引文件，而检索时，从这两个索引中取值，然后归并就可以了。

另外，索引数据，为了提高读写速度，一般是经过简单压缩的，这时也就涉及到数据安全问题，为了避免万一问题，也可在代码中增加校验功能，保证数据完整，即便某个地方因计算错误而有问题，也要把他限定在最小范围内。

4.检索

我很怀疑google的pagerank计算公式，据说有超过一千的影响因素，这在我简单的脑袋里是不可想象的。我看google黑板报（google的中文官方blog）里曾经说到，简单就是最美的，公式的思想好像与这个相违背。总之pagerank的思想就是：我重要，你和我有友好关系，那么可以简单的推到出，你也重要。根据这样的思想，我们可以创建自己的计算公式。

我比较关心检索的组合，例如检索：测试 软件 程序员 -网站  。这个在检索时会处理成一个逻辑结果，好像，(a and b and c ) - d 。大家都知道这就是集合操作，熟悉数据库的朋友可以想到，这个很像数据查询语句的条件，没错，为了减少数据库和索引操作，分析和优化查询是很有必要的，处理过程完全可以借鉴数据库检索语句分析和优化过程。

总结一下，我写的这些是索引的入门。我对索引的理解是。根据处理的数据类型和数据量，索引系统有很大的不同。我记得百度掌门人说过，搜索人人可作，但要做大做好，就很困难了。具体索引的实现方式，要比描述的复杂写，有兴趣的朋友可以现学习lucence，非常棒的开源java程序，也有.net版本的开源。我对lucence的感觉是，它很经典，它的索引文件有点烦琐，它的检索方式很值得学习。