一种基于科技查新的跨库检索去重算法
郝慧
北京工业大学图书馆 北京 100124
通讯作者:郝慧, ORCID: 0000-0002-1669-5340, E-mail:haohsm@163.com
摘要

【目的】通过对科技查新中的跨库检索结果进行去重, 提高查新检索效率。【方法】选取不同数据库检索记录中唯一性的特征四元组{论文名称, 期刊名, 发表时间, 第一作者}信息, 用改进的I-Match中的对比算法构建检索记录特征字串作为去重的计算依据。【结果】跨库检索去重算法对数据库检索结果进行初步分析和去重, 提高查新检索效率。通过测试, 算法去重准确率较高, 而召回率受数据库收录信息完善度的影响, 还有提高的空间。【局限】算法处理效果依赖于从数据库检索记录中提取特征四元组, 由于不同数据库的检索返回结果存在差异, 需要针对不同论文数据库定制检索记录特征抽取模板。【结论】通过实验测试, 算法具有较高的去重准确率和处理效率, 符合预定科技查新需求。

关键词: 跨库检索; 科技查新; 去重算法; I-Match
中图分类号:G250
A Duplicate Removal Algorithm of Cross-database Search Based on Sci-tech Novelty Retrieval
Hao Hui
Beijing University of Technology Library, Beijing 100124, China
Abstract

[Objective] Remove the data redundancy of cross-database searching in sci-tech novelty retrieval and improve the retrieval efficiency.[Methods] Choose thesis names, serial titles, publication dates and first authors of search records from different databases and build the character strings of search records by modifying comparison algorithm related to I-Match as the evidence of duplicate removal.[Results] The duplicate removal algorithm can improve retrieval effeciency by analyzing and duplicating the retrieval results from different databases. The experient suggests the precision of algorithm is superior, while the recall of the algorithm could be improved by modifying database records.[Limitations] The treatment effect depends on four characters extracted from database search records, different feature extraction model of search records needed to be customized according to different thesis databases due to the search result diffenrence.[Conclusions] The experiment test suggests the algorithm has a decent precision of duplicate removal and treatment efficency, which accords with the requirement of sci-tech retreival.

Keyword: Cross-database search; Sci-tech novelty retrieval; Duplicate removal algorithm; I-Match
1 科技查新跨库检索的文献去重问题

科技查新是查新机构根据查新委托人提供的需要查证其新颖性的科学技术内容, 按照《科技查新规范》进行操作, 并做出结论[1]。查新机构以查新委托人提供的待查内容, 制定合适的检索策略对数据库、网络及实体印刷资料进行查找, 并对所查到的相关文献、专利及科技成果等进行分析整理, 汇总为查新报告。查新人员根据用户所提供的关键词和查新点从多个数据库进行文献检索, 然而, 在不同的数据库中检索容易出现文献重复的情况[2], 因此, 考虑通过软件来代替人工完成跨库检索去重的工作, 以使资料查找更迅速和准确, 提高工作效率。

有数据表明, 维普数据库对万方期刊数据库的重复率为93.6%, 对中国知网的重复率为94.1%[3], 外文文献库也存在这样的问题。为了提高查新员的分析效率, 计算机需要对查新结果进行初步分析, 实现检索结果的去重。

目前, 对跨库检索去重所采用的计算机处理方法可总结为: 首先确定数据库查询所返回的信息中是否包含能确定该记录唯一性的信息, 再以这些信息作为关键特征构建记录对比特征, 最后对检索结果进行依次对比。由于需要对检索结果中的每条记录和检索结果中的所有记录作对比, 算法的效率较低, 且用户查询的数据库越多, 查询效率会呈指数下降。

鉴于网页去重和查新跨库检索去重在算法方面具有相似性, 本文充分利用已有的网页去重算法, 通过分析不同数据库检索返回的信息, 构建唯一性的特征, 对检索结果进行去重, 从而提高检索效率。

2 基于查新需求的去重算法
2.1 网页去重算法介绍

目前网页去重算法的基本思路是提取网页特征并对其进行处理, 去除重复的网页内容, 该算法可以达到节省存储空间、提高搜索引擎检索信息效率和网页收集速度的效果。不同算法对网页特征的定义可概括为:

(1) 网页特征提取: 用特征提取算法对网页文件进行处理, 提取特征是基于网页中的信息数据来确定的, 通常是对整个文章做分词处理, 过滤无关词, 并对剩余信息进行算法处理, 针对每个网页生成网页特征数据;

(2) 生成文档指纹: 文档指纹是对文档特征的概括化描述, 通过文档指纹处理, 可将文档特征转换为指纹信息, 减少了文档信息量, 有利于进行相似性比较;

(3) 相似性计算: 将提取的指纹特征与特征数据库中的数据进行对比, 特征对比一般采用向量空间模型或是编辑距离算法(Levenshtein Distance, LCS), 以提高对比效率。

目前针对网页去重处理的算法主要有:

(1) Shingling算法[4]

Broder[5]提出了子序列或数据块(Shingling)算法, 其核心思想是将文本内容进行文本分块处理, 得到一系列Shingling (即连续出现的单词序列整体)数据块。通过对每个Shingling数据块进行Hash运算, 抽取Shingling数据集合的数据文件特征。利用Cosine、Dice、Overlap、Jaccard或Hamming算法, 对比文件特征的相似性, 从而得到其对应的网页文本的相似性。该算法的缺点是对大文档的处理效率较低, 已有的改进算法是先将文档进行算法处理, 得到对应的特征内容, 然后再进行切分和对比。

(2) I-Match[6]

I-Match算法主要通过大规模的文本集合统计分析来实现, 该算法假设文档中高频词和低频词无法反映文档的真正内容, 通过去掉高频词来获得某一文章的特征, 对该特征字串计算Hash值(使用SHA1算法), 构建二元组(doc id, SHA1), 并将该二元组插入词典。如果数值存在冲突, 则表示词典中已有的文档和新插入文档相似。

该算法的缺陷主要是不能处理空文档, 且文档中某一词语变化, 其计算得出的Hash数值将出现显著变化, 从而影响最终的比较, 有学者提出使用随机化方法来解决这一问题。另外, I-Match算法对文档中词语的位置不敏感, 即使某一文章中两个词语出现顺序不同, 算法仍会判断该文档为相似文档。诸多学者对I-Match算法的不足之处进行了改进, 将其应用于网页去重及反垃圾邮件领域。

(3) SimHash[7]

Charikar于2002年提出SimHash算法, 并将其应用于Google搜索引擎的网页去重。不同于I-Match算法, SimHash是一种局部敏感算法, 即文章中某些词的不同不会造成Hash值的较大变化。算法首先对需要处理的文档进行分词处理, 分词处理算法可为特定算法或是简单采用N分法, 从而得到一组f维的特征向量, 对特征向量进行Hash处理, 将文档特征向量转换为f位二进制数据Q。初始化f维的向量V和f位最小哈希签名S, 并使用如下算法确定V和S的数值:

if Qi=1, V的第i个元素加上该特征权重;

else V的第i个元素减去该特征权重。

if Vi> 0, S的第 i 位为1;

else S的第 i 位为0。

对比两文档的SimHash签名值Si与Sj, 如果这两者的Hamming距离越小, 则 Jaccard 相似度越高, 文档也越相近。

SimHash算法在较高时间复杂度和空间复杂度的案例中应用良好, 适用于海量文本去重领域。

2.2 基于科技查新的检索结果去重算法

(1) 特征确定

由于查新结果的网页去重主要基于检索结果中的某些关键信息来实现结果的确认, 而网页去重往往需要对整篇文章进行处理, 因此对于查新结果的去重, 可以通过统计分析国内外主流论文数据库的数据检索结果, 确定检索结果中信息关键特征, 并以此作为检索结果去重的特征。

以同一关键词, 手工检索不同的论文数据库, 通过对比不同论文数据库的结果, 得到国内外主流论文数据库的检索返回格式情况, 仅列出论文基本信息, 如表1表3所示:

表1 国内主要论文数据库的检索部分返回格式
表2 国外主要全文数据库的检索部分返回格式
表3 国外主要文摘数据库的检索部分返回格式

与期刊论文相比, 学位论文存在特殊性, 本文将学位论文作为一种特殊形式的期刊论文, 在其检索返回格式中以“ 机构+学位论文” 代表“ 期刊刊名” , 如: 北京工业大学学位论文。从表1可以看出, 除万方外, 其他国内主要文献数据库并未使用DOI标识(数字对象唯一标识, 是识别数字资源的命名方法)。如果某一检索结果中论文的DOI标识与其他检索结果中的DOI数值一致, 表示该论文为同一论文。对于未使用DOI标识的论文, 需针对检索结果对其进一步分析, 确定检索结果的唯一性。

基于对国内外论文数据库的统计分析结果, 选用四元组{论文标题, 期刊名, 发表时间, 第一作者}作为关键要素, 并设定在数据库检索结果中, 满足某一论文的四元组特征的数据一致(即同时满足论文标题、期刊名、发表时间及第一作者数据均一致)即为同一论文。考虑到不同论文数据库对于期刊号的描述可能不一致(如某些数据库期刊号采用中文描述, 而有些采用英文Vol描述), 将四元组中的发表时间只限定到年。通过对各数据库检索结果的确认, 笔者认为设定符合实际检索情况。

为提高检索结果分析效率, 笔者引入相似性数据检测算法, 将跨库检索结果去重问题转化为可以使用基于数据相似性的算法来解决的问题。通过提取结果特征值, 以特征值集合来计算相似性, 通过降低空间和计算复杂性来提高性能。

(2) 算法选择和改进

基于查新检索结果四元组特征字段及对算法的要求:

①检索结果对比要求完全匹配, 无需近似性对比需求;

②四元组中内容变化时, 无Hash数值变化限制;

③对对比算法效率要求较高;

④对较短的文本内容处理结果良好。

本文通过定义四元组特征信息后, 借鉴I-Match算法, 去重流程如下:

①获取检索结果, 对检索记录结果进行编号, 记录为search_id, 依次提取每个检索记录的四元组信息;

②对四元组信息进行SHA1运算, 并以此作为该条检索记录的特征值;

③以检索记录编号search_id和该检索记录特征Hash值构成一个二维数组(search_id, SHA1值);

④将(search_id, SHA1值) 插入基于SHA1值的存储数据字典中;

⑤如果存在冲突, 表示字典中已经有该检索记录描述的论文文档。

在最坏情况下, 即检索记录中所有检索结果均重复, 时间复杂度为O(d), 正常情况下, 查询是否重复的复杂度为O(d logd)。

(3) 算法处理流程

由于国外普遍采用DOI对论文进行标引, 直接基于DOI信息的对比可加快检索结果处理速度, 避免由于提取四元组特征信息造成的处理延迟。整个检索结果去重处理流程如图1所示:

图1 基于科技查新的跨库检索结果去重算法流程

①基于跨库检索设定, 对设定中的数据库依次提交检索请求;

②解析不同数据库对检索请求的返回数据, 并进行格式化处理, 格式化处理包括将不同数据库中的检索格式进行一致性处理, 例如去除返回结果中的非关键信息, 如论文所属科研项目等;

③依次处理各条检索记录, 直到最后完全处理完成, 去重算法流程包括以下步骤④-步骤⑨;

④查询每条检索记录, 检查是否有DOI信息。如有, 则基于DOI信息计算Hash值, 并以此作为检索记录的特征值doi_sha1, 将此特征值插入特征字典中, 作为判重的依据(处理DOI信息的主要目的是加速对检索记录的处理, 当检索记录都带有DOI信息时, 程序可基于DOI信息进行去重, 而无需提取四元组特征);

⑥如插入成功, 表示检索结果中没有与DOI相同信息的索引记录, 如插入失败表示索引结果中存在重复, 丢弃该检索记录, 流程将跳转到步骤③, 继续处理获取的检索记录, 直到所有检索记录都被处理。如不存在重复, 表示该条检索记录是以DOI信息为特征的唯一结果。由于国内数据库并未完全采用DOI进行信息标注, 因此, 在处理DOI信息后, 依然需要计算四元组特征信息, 并以此作为该条记录的去重特征信息之一;

⑦如无DOI信息, 直接对检索记录提取四元组特征信息。四元组信息由{论文标题, 期刊名, 发表时间, 第一作者}构成。对四元组信息进行SHA1运算, 并以此作为该条检索记录的特征值, 以检索记录编号search_id和该检索记录特征Hash值构成二维数组(search_id, SHA1值);

⑧将 (search_id, SHA1值) 插入基于SHA1值的存储数据字典中;

⑨如果存在冲突, 表示字典中已经有该检索记录描述的论文文档; 如果没有冲突, 表示该检索记录所描述的论文目前还未重复。在完成此步骤后, 流程将跳转到步骤③, 继续处理获取的检索记录, 直到所有检索记录都被处理。

3 实验效果及分析

算法实现采用Python语言, 检索结果抓取采用urllib2库, 网页解析采用BeautifulSoup, 前台界面基于Django框架开发。计算机硬件配置为: Intel Quard Core Q9500, 4GB内存, 1TB硬盘。网络环境为100M校园网络环境, 测试系统部署于Windows XP Sp3系统。

系统提供用户管理、查新检索设置、查新检索及检索结果查阅等功能。用户登录系统后, 设置需要跨库检索的数据库, 检索系统提供普通检索和专业检索两种检索方式。测试选取科技查新检索中使用频次较高的中国知网(CNKI)和万方数据库中的检索结果进行去重处理来验证系统的去重效果。图2为去重系统选择界面, 设定跨库检索在CNKI和万方两个数据库中进行, 并采用科技查新常用检索策略, 以更符合实际应用环境。另外, 通过人工去重和程序自动去重的效果进行对比, 验证算法的有效性。

图2 科技查新跨库检索去重验证系统选择界面

3.1 效果评估方法

为评估去重处理效果, 采用信息检索系统性能评价方法对跨库检索的去重效果进行评估。准确率(Precision)和召回率(Recall)广泛用于信息检索和统计学分类领域的信息检索结果质量评价, 其中Precision用于衡量信息检索系统的查准率; Recall用来衡量信息检索系统的查全率。

令集合M为经由去重算法去重后检测出的重复检索记录数集合, 集合N为去重后实际重复检索记录数集合, 对于本文中提及的跨库检索去重的准确率和召回率用公式表示为:

3.2 去重效果及分析

跨库检索的去重结果展示界面如图3所示:

图3 科技查新跨库检索去重验证系统结果展示界面

多组实验数据所得的验证结果如表4所示:

表4 算法实验效果分析

其中, 准确率、召回率分别反映查准率及查全率。从表4可见, 系统反映出的查准率较高, 而查全率尚待提高, 这主要是部分数据库记录不规范, 算法所获得的输入与算法预设存在差异造成的。在序号1的测试中, 测试使用的检索式为: (沉水植物+贝类+鱼类)* 生态系统* 水质* (种类+密度), 在CNKI数据库与万方数据库中, 对同一论文名称, 出现了不同的描述, 比较典型的有: 陈开宁等于2006年发表在《湖泊科学》杂志上的论文, CNKI收录的名称为“ 太湖五里湖生态重建示范工程— — 大型围隔试验” , 而万方收录的名称为“ 太湖五里湖生态重建示范工程--大型围隔试验” , 由于论文名称存在符号差异, 造成了去重的失败。同样的情况出现在冯慧的硕士论文(2009)中, CNKI收录的名称为“ 黄河上游龙羊峡— 刘家峡河段水生生物多样性研究及生态系统健康评价” , 而万方收录的名称为“ 黄河上游龙羊峡-刘家峡河段水生生物多样性研究及生态系统健康评价” 。还有一种情况是同一论文名称是否添加小标题的情况, 如测试示例1中所出现的韩飞国的硕士论文(2012), CNKI收录名称为“ 水生植物群落构建对入湖河流污染物的净化效应” , 而万方收录名称为“ 水生植物群落构建对入湖河流污染物的净化效应— — 以巢湖小柘皋河为例” 。类似情况多次出现, 大大影响了算法的查全率。

数据库收录信息的完善度会造成四元组组成元素的信息缺失, 也会对准确率造成影响。例如, 万方数据库中收录了专利文档, 当检索到相关信息时, 专利文档并不提供时间字段, 而某些数据库中检索到的论文甚至未提供作者信息。从表4可见, 当数据库中文献相关信息存储规范时, 系统的去重效果较好。

3.3 误差处理及算法改进

通过实验验证, 笔者发现算法对于数据库收录文章上的标准不一致性, 影响了算法的处理效果, 降低了去重算法的准确率和召回率。大量测试数据表明, 对去重算法准确性影响较大的主要是不同论文数据库中对于同一论文使用不同的符号。例如, 同样的一篇论文, 在不同数据库中的论文名中使用中文括号和英文括号会造成去重算法判定是两篇完全不同的论文, 而多个论文作者使用不同的分隔符, 也会造成去重算法的处理错误。对于这种情况, 笔者认为可通过在构建四元组信息后, 对四元组信息进行格式化处理, 过滤四元组中的符号信息, 从而避免此类信息对去重算法造成的干扰。

4 结语

随着论文数据库资源数量的急剧增加, 查新人员在数据库检索过程中需要花费越来越多的时间。本文针对科技查新跨库检索系统中的检索记录去重问题, 通过借鉴针对网页去重的对比算法, 结合分析数据库返回结果, 提出了一种新的去重算法。该算法能有效地提高去重效率, 具有极大的发展潜力。

参考文献
[1] 谢新洲, 滕跃. 科技查新手册[M]. 北京: 科学技术文献出版社, 2004.
Xie Xinzhou, Teng Yue. Science and Technology Novelty Search Hand book [M]. Beijing: Scientific and Technical Documentation Press, 2004. [本文引用:1]
[2] 李雪婷, 李莘, 王晓丹. 基于JAVA 的图书馆中文查新智能去重系统的研究与实现[J]. 图书馆学研究, 2013(17): 56-58.
Li Xueting, Li Shen, Wang Xiaodan. Research and Implementation of Intelligent Duplicate Removal System about Chinese Novelty Search in Library Based on JAVA[J]. Researches on Library Science, 2013(17): 56-58. [本文引用:1]
[3] 洪道广. Google Scholar 的数据整合研究[J]. 现代情报, 2010, 30(7): 39-41, 45.
Hong Daoguang. Research on Data Integration of Google Scholar[J]. Journal of Modern Information, 2010, 30(7): 39-41, 45. [本文引用:1]
[4] Broder A Z, Glassman S C, Manasse S, et al. Syntactic Clustering of the Web [C]. In: Proceedings of the 6th International World Wide Web Conference. Essex, UK: Elsevier Science Publishers, 1997: 1157-1166. [本文引用:1]
[5] Broder A Z. Identifying and Filtering Near-duplicate Documents [C]. In: Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (COM’00). London, UK: Springer-Verlag, 2000: 1-10. [本文引用:1]
[6] Chowdhury A, Frieder O, Grossman D, et al. Collection Statistics for Fast Duplicate Document Detection[J]. ACM Transactions on Information Systems, 2002, 20(2): 171-191. [本文引用:1] [JCR: 1.07]
[7] Charikar M S. Similarity Estimation Techniques from Rounding Algorithms [C]. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC’02). New York, USA: ACM, 2002: 380-388. [本文引用:1]