《检测复制和近似复制的文件的制作方法》由会员分享，可在线阅读，更多相关《检测复制和近似复制的文件的制作方法（5页珍藏版）》请在金锄头文库上搜索。
1、检测复制和近似复制的文件的制作方法专利名称：检测复制和近似复制的文件的制作方法检测复制和近似复制的文件本申请是国际申请日为2007年8月3日、国际申请号为PCT/US2007/017487的 PCT国际申请的、进入中国国家阶段的国家申请号为200780036634. O、题为“检测复制和近似复制的文件”的专利申请的分案申请。1.发明背景1.1技术领域本发明一般涉及信息管理和检索。更具体地，本发明涉及诸如在要搜索的文档库中检测以及可选地移除复制和近似复制的信息或内容。1. 背景技术：在以下，术语“文档”应当被广义地解释并且可以包括诸如网页、文本文件、多媒体文件、对象特征、链接结构等内容。并且，应
2、当注意，当检测到近似复制的文档时，作为结果， 也将检测到准确复制的文档(虽然这样的准确复制件可能不一定与近似复制件相区分)。检测近似复制的文档具有许多潜在的应用。例如，复制或近似复制的文档可以指示剽窃或著作权侵权。近似复制的文档检测的一个重要应用在于信息存储和检索的环境中。存在检测是准确复制件的文档的高效技术。检测文档是否是近似复制件则更为困难，尤其是在文档的大型集合中。例如，因特网整体差不多包括几十亿的“网站”文档。在以下1. 2.1中，介绍了在因特网上的复制和近似复制的文档的源。然后，在以下 1.2.2中，介绍了由这些复制和近似复制的文档带来的对于终端用户和对于辅助终端用户的实体的问题。最
3、后，在以下1.2. 3中，介绍了用于在大型文档集合的环境中检测复制和近似复制的文档的在先技术，以及所发现的这些技术的缺点。 1.2.1在因特网上的复制和近似复制的文档的源在因特网上，万维网(被称为“环球网(the Web)”)可以包括以不同的形式或在不同的地方复制的相同的文档。(自然地，其它的网络或甚至独立的系统可以具有复制的文档)。此处介绍这样的复制的源。首先，一些文档在环球网的不同的站点处被“镜像”。这样的镜像被用来在许多用户试图在同一时间请求同一个文档时降低潜在的延迟，和/或将网络等待时间最小化(例如，通过将网页在本地缓存)。第二，一些文档将具有带不同格式的不同版本。例如，给定的文档可以
4、具有纯文本和HTML (超文本标记语言)版本使得用户能够以他们想要的形式呈现(render)或下载内容。随着越来越多的不同设备(例如，计算机、移动电话、个人数字助理等)被用来访问因特网，给定的文档可以具有越来越多的带不同格式的不同的版本(仅为文本、文本加其它媒体-rf* ) O第三，在文档的前面和后面经常附有与其在环球网上的位置有关的信息、日期、其最近被修改的日期、版本、标题、分层分类路径(可以将网页分类在网站分层中的一个以上的类别下)等。第四，在一些实例中，使用一致(consistent)的词语替换从现有的文档生成新的文档。例如，可以通过词语替换将网站“重新包装(re-brand)”用于不同
5、的受众。最后，一些网页将可从环球网上的另一个源获得的内容聚合或合并。1. 2. 2由复制和近似复制的文档带来的问题复制和近似复制的文档给访问(例如，来自环球网的)信息的人们和帮助人们访问期望的信息的实体(例如，搜索引擎公司)两者带来了潜在的问题。以下介绍了这些潜在的问题。虽然人们继续使用计算机来输入、操作和存储信息，考虑到数据存储、网间互联 (例如，因特网)、信息的互链接和交叉引用(例如，使用超文本链接冲的发展，人们正以不断扩展的范围使用计算机(或更一般地，信息访问机器)来访问信息。搜索引擎已被用来帮助用户发现期望的信息。搜索引擎通常根据用户查询搜索数据库化的内容或“网站”或“网页”。响应于用
6、户的查询，返回一个以排名排序的列表，该列表通常包括所发现的内容的简单描述以及指向所发现的内容的超文本链接(即具有相关联的URL的文本)。该列表的排名排序通常是基于出现在查询中的词语和出现 在内容中的词语的匹配。从用户的角度，复制和近似复制的文档带来问题。更具体地，当用户向搜索引擎提交查询时，绝大部分都不希望到具有大量冗余信息的网页的链接(以及其描述)。例如，搜索引擎通常通过提供以十条为一组的结果来对搜索查询作出响应。如果返回了具有复制内容的页面，在一个组中的许多结果可能包括相同的内容。这样，需要避免提供与具有复制内容的网页相关联(例如具有到具有复制内容的网页的链接)的搜索结果的技术。从托管搜索
7、引擎的实体的角度，复制和近似复制的文档也带来问题一给予终端用户他们所想要的，为其中一条。为了理解由复制和近似复制的文档带来的其它的一些潜在问题，首先介绍一些搜索引擎技术。大部分搜索引擎执行三个主要功能(I)爬行环球网；(2)索引环球网的内容；以及(3)使用所述索引生成搜索结果来对搜索查询作出响应。由于有大量的可用的信息，这三个主要功能在较大程度上被自动化。爬行操作将词语或短语与文档(例如网页)关联起来， 而索引操作将文档(例如网页)与词语或短语关联起来。搜索操作进而(I)使用该索引来找到包含搜索查询的各种词语的文档(例如，网页)，以及(2)对根据一些探试法找到的文档进行排名或排序。前面讲到，环
8、球网可以包括以不同的形式或在环球网上的不同地方复制的相同的文档。例如，如在以上 1.2.1所介绍的，可以在环球网的不同的站点处“镜像”文档，文档可以具有多个不同的格式，以使用户能够以他们喜好的形式呈现或下载内容，文档可以具有在其前或其后附有不同信息的不同版本，一些文档可以是使用一致的词语替换而从其它文档生成的，并且一些文档可以将可从环球网上的另一个源获得的文档聚合或合并。期望消除这样的复制件或近似复制件。除了消除复制或近似复制的文档以达到用户期望和愿望之外，对于搜索引擎托管实体而言消除复制或近似复制的文档也是所期望的，以(I)降低存储要求(例如，对于索引和从该索引导出的数据结构)，以及(2)降
9、低处理索引、查询等所需要的时间和/或计算资源。鉴于上述内容，需要检测(以及消除)近似复制的文档的技术。1.2.3用于检测复制和近似复制的文档的已知的技术以及其已知的局限性一种朴素的解决方案是将所有的对与文档相比较。由于这对于大型的数据集极其昂贵，曼巴(U. Manber, Finding similar files in a large file system, Proc. of the USENIX Winter 1994 Technical Conference (Tan. 1994)和亨策 (N. Heintze, Scalable Document Fingerprinting, Pr
10、oc. of the 2nd USENIX Workshop on Electronic Commerce (Nov 1996)提出了用于检测近似复制的文档的算法,这些算法减少了比较的数量。这两个算法在相邻字符的序列上运用。布灵等人(S. Brin, J. Davis, and H.Garcia-Molina, Copy Detection Mechanisms for Digital Documents, 1995 ACM SIGMOD International Conference on Management of Data, pp. 398-409(May 1995)开始使用词语序列来
11、检测著作权侵权。布劳德等人(A. Broder, S. Glassman, M. Manasse, and G.Zweig, Syntactic Clustering of the Web, 6th International World Wide ffeb Conference, pp. 93-404 (Apr. 1997)，此处以引用的方式并入)也使用了词语序列来有效地找出近似复制的网页。后来，查立卡(M. S. Charikar, Similarity Estimation Techniques from Rounding Algorithms, 34th Annual ACM Symp
12、osium on Theory of Computing(May 2002)，在此以引用的方式并入。也参见美国专利申请公开号2006/0101060，在此也以引用的方式并入)基于对文档中的词语的随机投射开发了一种方法。最近，侯德和枣贝尔(T. C. Hoad and J. Zobel, Methods for identifying versioned and plagiarised documents, Tournal of the American Society for Information Science and Technol ogi, 54 (3)，pp. 203-215(200
13、3)开发并比较了用于识别有版本的和剽窃的文档的方法。然而，不幸的是，侯德和枣贝尔推荐的技术效率较差，其具有O (N2)的计算复杂度，其中N是要与感兴趣的文档作比较的文档的数量。1. 2. 3.1对文档相似性的布劳德和查立卡算法的介绍在布劳德和查立卡算法两者中，每一个HTML页面被转换成标志(token)序列。这两个算法仅在它们如何将标 志序列转换成表示该页面的位串(bit string)上有所不同。为了将HTML页面转换成标志序列，页面中的所有的HTML标记被替代为空格，或在格式化指令的情况下被忽略。然后将每一个最大字母数字序列看作是词语并且使用拉宾的指纹方案(M. Rabin, Finger
14、printing by random polynomials, Report TR-15-81, Center for Research in Computing Technology, Harvard University (1981),此处以引用的方式并入)来将其散列以生成标志，但有两个例外。这两个算法从页面的标志序列生成位串并且使用该位串来确定该页面的近似复制件。设为页面的标志序列的长度。使用布劳德算法，用64位拉宾指纹对每一个有k 个标志的子序列(其中这些子序列重叠)采指纹(to fingerprint),这产生了(n_k+l)个被称为“shingle”的指纹的序列。设S (d)是页面
15、“d”的shingle的集合。布劳德算法假设两个页面d和d在独特(unique)的shingle的百分比上相合(agree)。S卩，布劳德算法假设是d和d，的相似性的良好测量。可以通过以m个不同的采指纹函数&对每一个shingle采指纹来模拟以上内容， 其中I彡i彡m。这导致对于每一个A有(11;+1)个值。对于每一个i，这些值的最小的一个被称为“第i个最小值(minvalue)”并被存储在页面中。作为结果，布劳德算法创建了最小值的m维向量。布劳德等人表明，两个页面d和d相合的在最小值向量中的条目的期望百分比与d和d在其上相合的独特的shingle的百分比相等。这样，为了估计两个页面的
16、相似性，确定最小值向量中的相合的条目的百分比就足够了。为了节省空间和加速相似性计算，可以通过对不重叠的最小值的序列采指纹来将最小值的m维向量简化为supershingle 的m维向量。设m可被m除尽并且设l=m/m。可以用另一个采指纹函数在O 具体实施方式本发明可以涉及用于确定文档是否相似的新的方法、装置、消息格式和/或数据结构。提供了以下的描述来使本领域的技术人员做出和使用本发明，并且是在特定应用和其需求的环境下提供了以下描述。因此，对符合本发明的实施例的以下描述提供了图示和描述，但是 并不意在穷举或将本发明限定在所公开的精确形式。对于本领域的技术人员对所公开的实施例的各种修改都是显而易见的，并且可以将以下披露的一般原理应用到其它实施例和应用中。例如，虽然可以参考流程图描述一系列动作，但是在其它实施方式中当一个动作的执行不依赖于另一个动作的完成时动作的次序可以不一样。并
