Document distance metric used in plagiarism detection
Mingxiao Hu, Ibm Toronto · 2010
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.Finally,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(n2) 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.