hkbin的小博客~
0%

网络信息获取之主动获取

发表于 分类于
1.8k 7 分钟

网络信息获取之主动获取

Created: November 26, 2023 4:16 PM
Reviewed: No

网络信息搜索系统的一般结构

搜索器、索引器、检索器、用户接口

Untitled

搜索器(爬虫)

功能是在互联网中漫游，发现和收集信息。要尽可能多、尽可能快地搜集各种类型地新信息，还需要定期更新旧信息，避免死链接和无效链接。

爬虫的分类

  1. 批量型爬虫：批量型爬虫有明确的抓取范围和目标，当爬虫达到这个设定的目标后，即停止抓取过程。

  2. 增量型爬虫：增量型爬虫会持续不断地抓取，对于抓取的网页可以实现定期更新，通用的商业搜索引擎爬虫基本属于此类。

  3. 垂直型爬虫(聚焦爬虫)：垂直型爬虫关注特定主题或属于特定行业的网页，其他主题或其他行业的内容不在考虑范围之内。

主要技术

爬虫缓冲池：抓取种子url放入队列中，取出URL，抓取页面并将URL放入已抓取队列，分析已抓取URL队列中的URL得到新URL，进入下一个循环。

在爬虫角度上的互联网划分

  1. 已下载未过期页面

  2. 已下载已过期页面

  3. 待下载页面

  4. 可知页面

  5. 不可知网页

网络搜索策略

深度优先

深度优先遍历策略指网络爬虫会从起始页开始，一个链接一个链接地追踪下去，完整地处理完一条路之后再转入下一个起始页。多数情况下会导致爬虫的trapped问题。

广度优先

也就是通用爬虫的思路(

缺点是大量的无关页面将被下载并过滤，算法的效率会降低。

最佳优先

在抓取地过程中，按照一定的页面分析算法，预测候选的URL和目标网页地相似度，或者与主题地相关性，选取评价最好的一个或者几个URL进行抓取。

缺点是在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最有搜索算法。

这样的闭环调整可以将无关页面数量降低30%~90%

多机抓取算法和单机抓取算法

多级抓取算法可以理解为多了一个调度器，用来统一分配URL，下面的都是它的线程/肉鸡，思路都一样，分配的时候n = hash(url) mod N，分配给N节点。

Untitled

Untitled

索引器

索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。

评价网站好坏→PageRank算法

PageRank根据网站的外部链接和内部链接的数量和质量衡量网站的价值。

示例：

Untitled

中心思想

数量假设：

当在网页模型图中，一个网页接受到的其他网页指向的入链(in-links)越多，说明该网页越重要。

质量假设：

当一个质量高的网页指向(out-links)一个网页，说明这个被指的网页重要。

公式：

$$
PR(v_i) = \sum_{v_j\in M(v_i)}\frac {PR(j)}{L(v_j)}, i=1,2,…,n
$$

其中M(vi)表示指向节点vi的节点集合。

L(vj)表示节点vj连出的有向边个数。

例题：

Untitled

Untitled

上述只是迭代了第一次。需要一直迭代直到极限。

Untitled

Dead Ends问题

当一个节点没有任何出链，这就是Dead Links，它会导致网站权重变为0

一直迭代下去会导致所有节点的PR值为0

例如：

Untitled

这个时候需要一个修正：

Untitled

Untitled

Untitled

Spider Traps问题

这个问题出现在于有节点指向自己，PageRank算法迭代下去会发现，该节点的PR值为1，别的节点为0。

修正方式：

随机游走，也就是打开网页B的时候，有概率打开网页C/D。

Untitled

检索器

检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。

检索器常用的四种模型有集合理论模型，代数模型，概率模型和混合模型四种。

用户接口

用户接口的作用是输入用户查询，显示查询结果，提供用户相关性反馈机制，主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎得到有效、及时地信息。

主被动获取技术比较

Untitled

P2P网络

P2P系统的分类

基于目录服务器地P2P网络(集中式)

三张图理解

Untitled

Untitled

Untitled

不足：

Untitled

Untitled

(具有分布式雏形

完全分布式的P2P

Untitled

特点就是泛洪

但是全网泛红又有缺点

所以出现了层次P2P

层次P2P

Untitled

Untitled

分布式哈希表系统(结构化P2P)

这个系统可以提高文件搜索效率的同时，又不依赖中心节点或局部中心节点。使用结构化对等网，基于分布式哈希表(Distributed Hash Table，简称DHT)而建。

结构化P2P：直接根据查询内的关键字定位其索引的存放节点，索引为<key, value>对。

Untitled

需要尽可能地保证表小一点，而且能够查询所有节点。需要在O(n)复杂度找到目标。

参考二分查找，路由表应该这样建

节点n的路由表：

1 n+1
2 n+2
3 n+4
4 n+8
5 n+16

另外一种操作 Chord-Hash表分布

Untitled

简单来说就是对两个值进行hash

N = hash(IP)，这个用来弄出你是第几个节点

K = hash(X)，这个表示你要上传/下载的东西应该放在哪

例如上传K = 54，则应该放在N51~N56之间，而且存放在N56，

查询的时候同理搜索至N56

优化：

Untitled

将每个节点的表变为二分的表，增大了一点，但是查询/上传效率高了不少

Kademlia(Kad)也是一种经典的结构化P2P

Kad网络中每一个节点都有一个160bits的ID值作为标志符，Key也是一个160bits的标志符，每加入一个Kad，网络都会被分配一个Kad(可以认为ID是随机产生的)，<key, value>对的数据就存放在ID值最接近key值得节点上

Untitled

Untitled

如何查询：

Untitled

K桶

Untitled

Untitled

总的来说就是每个节点都会有个K桶，这个K桶通过计算距离，可以来搜索目标节点。

当新节点加入得时候需要泛红来传播新Kad节点信息。

当然K桶不需要这么大，我觉得二分大小也可以。

总结

P2P结构分类

非结构化的→完全分布式的P2P网络

基于目录服务器的P2P网络

层次P2P网络

结构化P2P

P2P技术的特点

非中心化

扩展性

健壮性

高性价比