网络爬虫的设计与实现(16)

过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。

广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。

结点的扩展规则也就是如何从现有的结点生成新结点。对不同的问题，结点的扩展规则也不相同，需要按照问题的要求确定。

3）搜索策略

为了便于进行搜索，要设置一个表存储所有的结点。因为在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般设计成队列的数据结构。

搜索的步骤一般是：

（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。

（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。

（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展......。

最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。

3.3 网络爬虫的主题相关度判断

主题爬虫的系统组成最初考虑是对页面的过滤，不像普通爬虫对所有页面的链接进行处理，先对页面与受限领域的主题相关度进行分析，只有当其主题相关度符合要求时才处理该页面中的链接，因为如果该页面和本领域比较相关，它所包含的链接和领域相关的几率也较大，这样提高了爬行精度，虽然会遗漏少数页面，但综合效果是令人满意的。因此，主题相关度的分析是主题爬虫设计的关键。