搜索技术总结整理

sowang

原贴：http://hunteagle.javaeye.com/blog/118548

搜索技术总结整理 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的感觉是，它很经典，它的索引文件有 点烦琐，它的检索方式很值得学习。




Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1824784