作　　者： ;

机构地区： 温州大学计算机科学与工程学院

出　　处： 《计算机工程与应用》 2010年第7期148-152,177,共6页

摘　　要： 广义编辑距离的计算是一个NP-完全问题,在充分考虑了文档抄袭行为的特点之后提出一种基于广义编辑距离的单向的低计算复杂性的文档距离度量方法。首先,计算第一文档的各段落在第二文档全文中的近似串匹配距离之和,同时确定各段落在第二文档中的近似匹配子串(即原象串),然后根据这些原象串得到回退数和前跳数,最后将三者求和作为文档距离。该文档距离是一种广义编辑距离的近似值,能够在O(n2)时间内计算,并能充分反映抄袭方向。针对人工文档和实际文档的两组实验表明该距离具有较低的漏检率、误检率。 The algorithm for generlized edit distance is NP-complete.A one-direction,low complexity document distance metric based on generalized edit distance is proposed after probing special patterns of document plagiarism.Firstly,compute the sum of approximate string matching distances of each paragraph of the first document to the full text of the second document,and determine the best matching substrings in the second document,which is called original map substring,for each paragraph.Then collect returning number and skipping number according to these original map substrings.Fiually,sum up the total approximate matching distances,returning number and skipping number to arrive document distance.This document distance metric is an approximation of generalized edit distance,and it can be calculated in O（n^2） time and can detect plagiarizing direction.Applications of this new metric on manually created and real-life documents indicate that it has low missing rate and false-alarm rate.

关 键 词： 文档距离 广义编辑距离 近似串匹配 抄袭识别 电子文档管理

领　　域： [自动化与计算机技术] [自动化与计算机技术]