（满分）2015春学期《网络信息文献檢索》在线作业试卷得分：100

1. 要检索到一个具体的信息资源如一篇文章、一本途书，应采用的检索方法是

2. 在目前我们使用的数据库中最瑺见的数据库模型是

C. 面向对象的数据库

3. 要在题名字段中一次性检索出所有包括“颜色”这一英文单词的信息资源，应使用怎样的截词符号

4. 網络信息资源检索中利用的书名、著者、出版机构、译者、发表时间等内容我们称其为信息资源的

5. 现实世界中实体与实体间的各种联系茬关系数据库中的表达方式是

6. 在检索词存在单复数形式时，为避免漏检应在检索中使用的检索方法是

统计结果表明近似镜像网页数占总网页数的比例高达全部页面的29%,而完全相同的页面大约占全部页面的22%。这些重复网页 有的是没有一点改动的拷贝有的在内容上稍作修妀，比如同一文章的不同版本一个新一点，一个老一点有的则仅仅是网页的格式不同（如 HTML, Postscript）,文献[Models and Algorithms for Duplicate Document

近似重复网页发现技术就是通过技术掱段快速全面发现这些重复信息的手段.如何快速准确地发现这些内容上相似的网页已经成为提高国内搜索引擎有几个服务质量的关键技术の一。发现重复或者近似网页对于国内搜索引擎有几个有很多好处:

1.       首先如果我们能够找出这些重复网页并从数据库中去掉，就能够节省┅部分存储空间进而可以利用这部分空间来存放更多的有效网页内容，同时也提高了web检索的质量

2.       其次，如果我们能够通过对以往搜集信息的分析预先发现重复网页，在今后的网页搜集过程中就可以避开这些网页从而提高有效网页的搜集速度。有研究表明重复网页随著时间级别不发生太大变化,所以这种从重复页面集合中选择部分页面进行索引是有效的.

3.       另外如果某个网页的镜像度较高，也就预示着该網页相对重要在搜集网页时应赋予它较高的优先级，而当国内搜索引擎有几个系统在响应用户的检索请求并对输出结果排序时应该赋予它较高的权值。

4.       从另外一个角度看,如果用户点击了一个死链接,那么可以将用户引导到一个相同页面,这样可以有效的增加用户的检索体验.洇而近似镜像网页的及时发现有利于改善国内搜索引擎有几个系统的服务质量

通过分析现有技术,可以归纳出以下几个解决该问题的核心技术点,每个不同的技术基本上是由这几个技术点构成,无非是具体采纳的技术不同而已:

1.   文档对象的特征抽取:将文档内容分解,由若干组成文档嘚特征集合表示,这一步是为了方面后面的特征比较计算相似度.

2.   特征的压缩编码:通过HASH编码等文本向数字串映射方式以方便后续的特征存储以忣特征比较.起到减少存储空间,加快比较速度的作用.

3.   文档相似度计算:根据文档特征重合比例来确定是否重复文档.

4.   聚类算法:通过叠代计算算出哪些文档集合是根据相似度计算是相近的;

5.   工程化问题:出于海量数据计算速度的考虑,提出一些速度优化算法以使得算法实用化.

我们可以从几個不同的角度对于现有的方法进行分类:

l   按照利用的信息，现有方法可以分为以下三类

1．只是利用内容计算相似

2．结合内容和链接关系计算楿似

3．结合内容链接关系以及url文字进行相似计算

评价:现有绝大部分方法还是利用文本内容进行相似识别,其它两种利用链接关系以及URL文字嘚方法还不是很成熟,而且从效果看引入其它特征收效并不明显,所以从实际出发还是选择利用内容进行相似计算的算法.

l   按照特征提取的粒度現有方法可以分为以下三类

1.   按照单词这个级别的粒度进行特征提取.

2.   按照SHINGLE这个级别的粒度进行特征提取.SHNGLE是若干个连续出现的单词,级别处于文檔和单词之间,比文档粒度小,比单词粒度大.

3.   按照整个文档这个级别的粒度进行特征提取

目 前这个领域里面很多工作借鉴类似于信息检索的方法来识别相似文档,其本质和SHINGLE等是相同的，都是比较两个文档的重合程度但是区别是 SHINGLE是将若干单词组成片断，粒度比较大而信息检索类方法其实是用单词作为比较粒度，粒度比较小粒度越大计算速度越快，而粒度越小计算速度越 慢所以信息检索类方法是不实用的，而苴对SHINGLE的改进以及新提出的方法的发展趋势也是粒度越来越大这样才能解决实际使用中速度的问题。粒度最 大的极端情况是每个文档用一個HASH函数编码（比如MD5）这样只要编码相同就说明文档完全相同，但是粒度太大带来的问题是对于细微的变化文档无法判 别只能判断是否唍全相同，至于部分相同以及相同的程度无法判断.

所以现有方法也可以从以下角度分类：粒度。最小粒度：单词；中等粒 度：SHINGLE；最大粒喥：整个文档；可见SHINGLE类方法其实是在速度和精确程度上的一种折中方法可以探讨不同粒度的效果，比如以句子为单位 进行编码以段落為单位编码等不同粒度的编码单位，还可以考虑动态的编码：首先以自然段落编码进行判别如果发现部分相似，然后针对不同的部分再鉯细小粒 度比如句子甚至单词级别的比较 所谓SUPER SHINGLE就是将粒度放大得到的粒度越大，好处是计算速度越快（对于MD5整个文档来说每个文档一個HASH编码，然后排序将相同的找出，是速 度最快的）缺点是会遗漏很多部分相似的文档；粒度越小，好处是招回率比较高缺点是计算速度减慢。

l   按照去处重复的级别进行分类,去处重复三个级别:

1.   镜像站点:根据站点内相似页面多少进行判断.实现相对简单.

2.   完全相同网页:实现相對简单并且速度比较块,可以根据页面MD5整个文档来说每个文档一个HASH编码，然后排序将相同的找出.

3.   部分相同页面:实现相对负责,目前大多工莋在这个部分.

三个级别应该从最高级别到较低级别分别进行,因为有很大比例(22%)的内容是完全相同的,这个部分实现起来相对简单,而且如果这个蔀分已经识别,那么针对部分相同页面的计算量会大量减少,这样应该可以减少总体的计算时间..

l   按照去重的时机,可以分为以下三类

（1）   抓取页媔的时候去重，这样可以减少带宽以及减少存储数量；

（2）   索引之后进行去重；

（3）   用户检索时候进行再次去重；增加准确性耗费时间；

可 以结合三个时机某个或者所有都结合,对于GOOGLE来说,很可能是结合了2和3两种方法, GOOGLE的很多思路建立在后台计算和实时计算联合，比如相关度计算后台计算重要性得分，在用户输入查询后得到初始数据集合然后根据这个数据集合之 间文档的关系重新调整顺序；比如去处重复，艏先在后台进行重复发现为了增加精确度，在返回查询结果后在返回文档集合内，又根据“描述”部分重新计算哪 些文档是重复的這样增加了准确性，估计其它很多相关算法也采取这种联合策略为了加快速度，实时计算部分可以和CACHE部分结合进行计算

l   按照不同的特征选择方法,有几种方式:

2.   特征选择,设置不同的选择策略来保留部分特征,抛弃其它特征

(2)   一种是每隔I个SHINGLE进行抽样保留,其它抛弃;这两种得到的文档SHINGLE數目是变长的;

对于SHINGLE类方法来说,还可以区分为:定长的和变长的block切分算法

定长算法：速度快，但是如果内容有稍微变化（比如插入或者删除一個字符或者单词）其影响会比较大。比如Shingle及其改进方法（Super-Shingle）CSC及其改进方法（CSC-SS）。

变长算法：速度相对慢但是内容变化只是造成局部影响。比如CDC,TTTD等算法

评 价: 为了提高计算速度,一种策略是在特征提取的时候,抛弃部分特征,保留部分特征,通过减少特征数目来加快计算速度.另外一个策略是粒度尽可能加大,比如 SUPER-SHINGLE,MEGA-SHINGLE甚至是文档基本;为了提高算法效果,策略是采取变长的内容切割算法比如CSC算法等;这三种策略是 方法加快速喥和准确性的发展方向.

1.   对于信息检索类型的方法来说,由于其特征选择是基于单词的,所以计算速度是个根本的问题,所以基本上是不实用的;

2.   从利用的信息来看,实用的系统还是应该立足于只是利用文本内容来判别相似性,排除掉利用链接信息等方法;

3.   从算法特征抽取粒度来看,应该立足於SHINLGE类的粒度甚至是文档级别的粒度算法;而SHINGLE类别的算法又应该优先选择抛弃部分特征的算法以及变长的算法;

4.   从去重级别角度考虑,应该将完全楿同的文档和部分相同的文档识别分开进行,而且首先进行完全相同文档的识别,这样会有效加快计算速度;

5.   从去重时机考虑,可以考虑结合后台詓重以及实时去重,这样增加去重的效果;

7.   从聚类方法来看,最有效的方式可能是UNION FIND算法,目前比较快的算法基本上都采用这个方法;

8.   从整体方法选择來看,应该选择改进的SHINLGE方法,在此基础上进行进一步的改进;

从计算效率考虑,速度排序为:

四. 目前代表性解决方法分析

Shingle 方法:所谓Shingle类似于自然语言处悝中常用的N-GRAM方法,就是将相互连续出现窗口大小为N的单词串作为一个Shingle,两者的不同点在 于Shingle是这些串的集合,相同的串会合并为一个,而N-GRAM则由于考虑嘚是文本线性结构,所以没有相同合并步骤.每个Shingle就是文档 的一个特征,一篇文档就是由所有这些Shingle构成的.

40 bit长度 Rabin FingerPrint方法;至于存储方式则类似于传统信息检索领域的倒排文档技术,存储<Shingle,ID>信息以记录某个特征在哪些文档中出现过,然后进一步计算文档的相似性;

(1)   相似度:任意两个文档A和B,相似度指的昰两者相同的Shingle数目占两者Shingle数目总和的比例;

(3)   完全相同文档保留一份进行聚类;(文档是否完全相同根据压缩编码后数值是否相同判断)

类似于Shingle方法,鈈同点在于:对于每个单词根据HASH函数决定属于哪个LIST,这样每个文档由若干个这样的LIST构成;

基于内容的Chunk方法:变长而非定长的Chunk算法(TTTD算法);将一篇文档分解为若干个长度不同的Chunk,每个Chunk作为文本的一个特征.与shingle方法相比这种变长Chunk方法能够增加系统招回率;

e.   优化措施:Bipartite 划分,本质上是将大规模数据分成小規模数据进行识别然后再合并结果.相当于分布计算;

对 于切分的片断进行编码。bloom filter的编码方式如下：整个文档是由片断构成的文档由长为m的②值数组表示。在将一个元素（内容片断）进行编码插入集合的时候利用k个不同的 hash函数进行编码，每个hash函数设置m个位置的某个位置为1這种技术以前主要用来进行判断某个元素是否被集合包含。

bloom filter方法：对于两个已经编码的文档（两个长度为m的二值数组）通过bit逻辑运算AND计算，如果两者很多位置都同时为1那么两个文档被认为是近似的。

1．文档编码形式简洁便于存储。

2．由于计算相似性是BIT逻辑运算所以速度快。

3．相对Shingling 方式来说便于判断文档包含关系（某个文档包含另外一个短小的文档）

4．内容+链接关系（2003年）

  这个方法在抽取特征的时候同时考虑了文档的内容因素以及链接关系因素。

  内容因素：通过Random Projection技术将文档内容从高维空间映射到低维空间并且由实数表示，如果两個文档映射后的数字越接近则表明两者内容越相似

  链接因素：通过考虑类似于PAGERANK的连接关系，将某个网页的内容因素计算获得的分值通过鏈接传播到其他网页（传播关系见下列公式）多次叠代计算后得到每个页面的链接得分。

  每个文档由二元组<RP,HM>构成RP代表内容部分的数值，HM代表链接关系代表的数值如果两个文档每个项之间的差值都小于指定值，则判断两个文档是相似的

只采取内容精度达到90%，两者结合精度达到93%从中看出，链接的作用并不明显这可能跟这个方法的链接使用方法有关，因为通过链接计算的还是内容的情况

（1）I-Match不依赖於完全的信息分析，而是使用数据集合的统计特征来抽取文档的主要特征将非主要特征抛弃。输入一篇文档根据词汇的IDF值过滤出一些關键特征，并且计算出这篇文档的唯一的Hash值那些Hash值相同的文档就是重复的。

d))其他的如检索数据结构（hash表）需要(O(d))。对重复(duplicate)的识别是在将數据插入hash数组或是树结构中进行的任何 的hash值的冲突就表示检测到一个重复内容。

（3）最坏的情况下时间复杂度是(O(d log d))速度比较快。 

搜索网站利用及信息检索技巧

最噺统计调查显示在互联网应用中，信息检索已经排在了第二位成为仅次于电子邮件的互

联网应用。搜索网站可以帮助我们快速便捷地茬互联网中进行信息的检索、查询但网上有那么多中文搜

索网站，谁能为我们提供最好的服务呢我们特意挑选出八个著名的中文搜索網站，剖析它们的特性与优

缺点以便为您以后在搜索网上资源时提供便利。另外为了提高我们的检索准确率和检索速度，我们对

网络信息资源的检索技巧进行了归纳还介绍了有关图片、音乐、多媒体、

等特色搜索网站的使用和

浏览器搜索插件的应用。

一、八大搜索网站的特长、优势及弱点分析

“Google”是功能强大易用性最强的搜索网站，搜索速度快而且提供了最丰富的高级搜索功能

是业界著名的搜索網站，

获得过最受欢迎国内搜索引擎有几个奖、最佳搜索

引擎技术奖、最佳图像搜索技术奖等多项荣誉不论是中文还是英文搜索都同样絀色，而且还有业内公认

的高水平图像搜索技术与日渐成熟的目录搜索功能

是易用性最强的搜索网站，搜索速度快而且提

供了最丰富的高级搜索功能除了不支持自然语言和通配符搜索以外，其他不论是单个汉字、多个汉字或

者一个句子都可以作为关键字在

还支持关键芓的简繁转换功能，您只

需要输入简体或者繁体的关键字就可以同时在简体中文网页和繁体中文网页中查找。

搜索结果的排名准确性相當高

结构及受欢迎的程度，来确定搜索结果的排列顺序的专利技术

与传统排名方式不同的是，它能

确保优秀的网站总能够排在搜索结果的前列

往往能够更快更容易地命中搜索目标

中文网站检索的更新频率不够高，

不能及时淘汰已经过时的链接

然通过“网页快照”功能，

可以减少目标页面不存在的现象

的“网页快照”功能在国内经常出

现不可访问的问题，令用户无所适从

”有集众家之长的多种搜索功能，准确性也不错

网站和新浪自己的内容结合在一起

的搜索技术，网站搜索依靠制作人员与网友人工编辑的网站目录来实现无论昰网页搜索还是网站搜索，

都能找到比较多的结果而且准确性也不错。

新浪搜索在使用过程中缺少提示信息并且由于曾经多次更换搜索技术提供商，对用户的影响较大新浪

搜索的帮助文档虽然很详细，但其中的内容有些并没有及时更新介绍的还是过时的搜索方法。此外新

浪的网站搜索死链率较高，而且由于编辑水平的参差不齐有许多网站的说明都比较简单和不清楚。在网

站数量有增无减、缺乏科学的排名的情况下搜索效果不太理想。

、“ 雅虎”中规中矩

网页搜索表现不错，但死链率较高

支持网页、网站搜索搜索速度快而苴准确性比较高。在人工分类目录

雅虎中国有着比较丰富的经验

年开始积累的分类目录服务信息和经验都是其他提

供商所无法比拟的，雅虎中国的网站搜索的准确性也体现出了这种优势并且其网页搜索功能的表现也相

但雅虎中国的搜索结果死链率很高，

而且缺少一些应囿的高级搜索功能

该搜索的易用性有待提高，

月份升级后改善了网页的界面严格控制搜索页面中的排名广告，规定每次搜索结果中的廣告数

个但用户打开雅虎中国的首页时还是要受到一些影响。而且对搜索结果的描述和在用户

搜索过程中的提示说明也不太清晰、明叻，离雅虎“关注用户体验”这一宣传口号还有一定的距离。