In the paper, considered the problem of fuzzy duplicate detection. There are given the basic approaches to detection of text duplicates-distance between strings, fuzzy search algorithms without indexing data, fuzzy search algorithms with indexing data. Thereview of existing methods for the fuzzy duplicate detection is given. The algorithm of fuzzy duplicate detection is present. The algorithm of fuzzy duplicate texts detection was implemented in the system AVTOR.NET. The paper presents the results of testing of the system.The use of filtering text, stemming and character replacement, allow the algorithm to found duplicates even in minor modified texts.
Today computer technology and the World Wide Web have become part of our lives. Billions of users use the Internet every day. The Internet contains a huge number of documents. Many books are transformed in a digital form. Users can read books, articles, newspapers directly from computers and electronic gadgets. Today, in the Internet there are many studying materials: lectures, textbooks, methodical literature, etc. There are big collections of essays, course and diploma projects and scientific dissertations. It leads to problem un-controlling coping of information.
The text of document may be a part of another document, formed from several documents, may be modified part of another document (with a change of words to synonyms, endings, times, etc.). In this way, the document is fuzzy duplicate of other documents.
There is the problem of text checking to presence of fussy duplicates. The purpose of work is the algorithm creation of fuzzy duplicate detection.
The task of comparing texts reduced to comparing their strings. For this reason, assume that the text document is aone string of a large length. There is a requirement to determine the measure of the string similarity. This measure is called the distance between strings.
The distance is the minimum number of string characters changes, which is necessary for the
transformation of one string within another. The Hamming and Levenshtein algorithms used to
determine the distance [
(a) The algorithm of Hamming [
The algorithm of Hamming is used to search the distance between strings of equal length, by using
the operation "replacement". This algorithm is not suitable to search the distance between the strings,
various by length.
(b) The algorithm of Levenshtein [
The algorithm of Levenshtein uses operations "replacement", "insert", "delete". They allow to search the distance between strings, different by length. But time of calculation of distance between strings is disproportionately increases with increases of strings size. Therefore, the use of this algorithm is only suitable for comparing multiple pages of documents.
(c) The algorithm of Damerau-Levenshtein [
This is modification of the Levenshtein distance. It is also consider the operation of "transposition" the next two letters.The method of calculation of Levenshtein distance was the basis for several algorithms of search for common subsequences.
(d) The algorithm of Wagner and Fisher [
This method is based on calculating the Levenshtein distance between the strings prefixes (substrings). The matrix of editorial prescription is made. It contains a summary value of Levenshtein distance (minimum weight operations to change characters). The size of editorial prescription matrix is (p+1)∙(b+1), where p and b – compared strings prefixes.
The number of string comparisons is k∙p∙b, where k – coefficient (for natural language k=0,2). The
complexity of algorithm is O(p∙b) [
The algorithm is modification of Wagner and Fisher algorithm with applying the approach Arlazorov, Diniz, Kronrod and Faradjev. The distance matrix in it is separated into submatrixes with edges computed in accordance with contiguous to their submatrixes.
The complexity of algorithm is О(k∙(p∙b/log(p))).
This algorithm faster than the algorithm of Wagner and Fischer, but, at the direction of the authors
themselves [
(f) The algorithm of Ukkonen [
For this algorithm it is required the construction of suffix tree of strings set to minimize search time in substring.
Complexity of algorithm is O(k∙m), where m – maximum vertex depth of suffix tree.
Algorithm of Ukkonen is more applicable for search of exact matches strings. If searching for very different texts, then working time is greatly increased.
(g) The algorithm of Hirschberg [
The algorithm is modification of Wagner and Fisher algorithm. It is not calculated the distance between the strings but the distance between the longest common subsequence.
The complexity of algorithm is O(k∙(p+b)).
(h) The algorithm of Hunt and Szymanski [
It is based on searching of maximum increasing path on a matching elements graph of compared strings.
The complexity of algorithm isO(k∙(g+b)∙log(b)), where g – the number of positions in which the string symbols are the equal.
Under certain circumstances, this algorithm shows good results, but in other cases, the comparison time is quadratic.
(i) The suffix tree [
This method is proposed of McCreight in 1976. It is similar to the Ukkonen algorithm, but the suffixes are added in reverse order.
The complexity of algorithm is O(k∙m).
Disadvantage of algorithms working with suffix trees is use a fixed alphabet. It is suitable only for search of exact match strings.
Let’s consider fuzzy search algorithms without data indexing [
(a) Linear search algorithm [
The algorithm uses the distance metric and applies it to the text words. Efficiency of the method depends on the number of errors and mismatches of texts. More numerous they are the more increases the comparison.
The algorithm complexity is O(s∙p), where s – the number of errors made when checking, p – the text length.
(b) The Bitap algorithm [
This algorithm is applied more than the linear search. In view modifications it calculates the Levenshtein distance between words. At normal conditions, speeds of these two algorithms are the same. The algorithm complexity is O(s∙p), but the speed of this algorithm significantly higher on long words than a linear method.
It is necessary to index the text for the application of this group of algorithms. The dictionary is constructed by thetext. It contain words and their position in the text. On base of dictionary creates the index required for further search.
(a) The algorithm of sample expansion.
This algorithm is composedfor the search of many erroneous words and then look for them in the dictionary.
Complexity of the algorithm is O((b A )s b log p) , where A – the dictionary size, b and p – compared words, s – the number of errors in a word.
Disadvantage of the algorithm is that with increasing number of errors, the time of its operation also increase.
(b) The N-gram algorithm [
This algorithm is based on words separation to parts (substrings) with the length N (N-grams). It is compiled N-gram list, contain all the words of this text with occurrences of the substring. Next separated similarly inquiry is searched by this list.Most often used division into trigrams. Complexity of algorithm isO(w∙H), where w – the probability of occurrence of N-grams in the word, H – the number of words in the N-gram list.
(c) Hashing by signature [
This algorithm represents a word of the text in a code ("hash"), consisting of digits. Indexed words recorded in the table. Query also indexed is make the search in the table.
Complexity of algorithm is O( E s p ) , where E – the hash function, representing the word as a 2 E code, p – the text length, s – the number of errors.
(d) The shingles algorithm [
The source text is separated into a set of sequences of a defined length (shingles). Documents are similar if the equal some amount of their shingles. Number of shingles is sufficiently large. Therefor are used methods reduce of shingles set.
For example, can be considered only those shingles, whose fingerprint is divided into a defined number n. Other way are selected shingles with the minimal fingerprint, or simply taken a defined amount of shingles.
(e) The algorithm of D. Fetterly [
For each document are computed 84 fingerprint by algorithm of Karp-Rabin using a random sample of shingles. These shingles are separated into 6 groups, which are called "super shingle". The combination of 2 super shingle is "mega shingle". 15 mega shingle are computed for the each document. Two documents are similar if they have the same at least one mega shingle.
Algorithm complexity is O(S1∙S2), where S1 – number of shingles from document 1, S2 – number of shingles from document 2.
(f) The I-Match algorithm [
Dictionary A is built for a group of documents. Dictionary consist of words with the average values of a code IDF. For each document is created dictionary B and determine the intersection of A and B. Words of document, included in the intersection, are used to build I-Match signature of the document. If I-Match signatures are equals, then texts are similar.
(g) The algorithm of key words [
From the index are selected "key" words with threshold frequency. For a document constructed binary vector (signature). Value of i-th coordinate of the vector is equal to 1 if the frequency of i-th "key" word in the text is more than the threshold value, or 0 if its frequency in the text is less than the threshold. Texts are similar if they have the same signature.
(h) The TF*IDF algorithm [
It is a calculated inverse frequency of word in the collection of documents, called as Inverse Document Frequency (IDF). It is a calculated frequency of the word in the documents called as a Term Frequency (TF). A Values TF*IDF helps measure similarity documents to query. This is a very popular method. The disadvantage of this method is that it ignores a relative arrangement of the words in the documents.
At present, there are a large number of approaches for finding similar strings and small texts [
Let’s consider our algorithm of fuzzy duplicate detection.
A checked text document can have different encodings. For a Russian language it is win1251, KOI8R, UTF-8, ASCII. Therefore, the checked text document is converted to the uniform character set UTF-8.
A text document is a set of strings. Formatting of the same documents may be very different. Therefore, it is necessary to simplify the presentation of the text. For this purpose, we used a linear representation of the text as a sequence of characters. In other words, the text appears as a single long length string (an wide string). 3.3. Pre-processing of a text.
It is perform pre-processing of a text: the text of a document is replaced by a filtered copy. For this purpose the following steps are performed: Removal of HTML tags.
A text document can to contain HTML tags. Because HTML tags are used for a document formatting, they do not affect to its contents. Therefore presence of HTML tags will just interfere to checking and must be removed from a document.
Removal of punctuation marks and special characters.
In the text there are punctuation marks and special characters, including tabs, new line, etc. All this characters are removal from the document.
Case conversion.
In the text of documents many words can be written with a lowercase or uppercase letters, consist entirely of uppercase letters or contain mixed uppercase and lowercase letters in words. Therefore, all characters are converted to lowercase.
Processing of replacement characters.
Sometimes, in text documents there are replacement characters. For example, in Russian words several letters of the Russian alphabet replaced the similar Latin letters (such as “o”, “a”, “e”, “y”, “x”, “c”, “p”, etc.). In this case, it is processed the replacement characters and they transform to an original form.
Removal of stop words.
Stop words are common words occurring in an almost every document, such as "the", "of", "on", "a", "at", "by" etc. Therefore, these words do not help in the search of text duplicates, but increase the processing time. They must be removed from the document.
Filtration of the text (not informative words removal).
A filtering of a text is a removal the most frequent words, not informative words etc. Also, filtering words that contain special characters, digits, words of great length, etc. This procedure allows to asignificantly reducing the amount of a computation (the length of the checked text). Stemming (processing of word endings).
A stemming is processed closure words. In this case, they are simply deleted. This avoids the effect of such modifications of the text, as a change in the singular and plural forms, masculine and feminine, a present and a past tense etc.
Our algorithm is based on a method of shingles. The text is divided into a sequence of words. A length of the sequence is fixed (5 words). For the each sequence of words is computed a MD5 code (shingles). The algorithm works with that code (figure 1).
A classical method of shingles used all words to create a sequence of words. We propose to consider not all the text of document but its a processed and filtered copy.
Tobe, or not tobe: thatisthequestion. 0baf14642840e122b781165e0a570ace eba8ebc8628706f53d89f2de5475f87d
e2e2085e08a720f59b4bc7aed2680a46
The number of matching MD5 codes shows the measure of matching documents. If all codes in two documents are match, then documents are full duplicates. If there aren’t match codes, then documents are different. If only a part of MD5 codes is match, documents are fuzzy duplicates.
On the basis of the Vladimir State University, the authors developed the system of fuzzy duplicates
detection. The system checks both the sources available on the Internet and on an internal database
(databases of articles, course works and examinations etc.). The system generates a report with
colouring duplicate parts of texts and viewing found duplicate sources. Let’s consider the system
structure [
A text preparation includes removal of HTML tags, removal of punctuation marks and special characters, case conversion, processing of replacement characters, removal of stop words, filtration of the text, a stemming.
The system of fuzzy duplicates detection includes two modules. An each module operates independently of each other.
The first module checks the internal database sources. Base sources include a database of articles, course works and examinations, diploma projects, textbooks, lecture courses. Sources are stored in the form of a full-text and in the form of specially organized search index. A search index is needed for quick checking duplicates of a text in a database sources. There is no need for each check to a view all the available texts and make them fairly laborious process. All the necessary information for search is already included in a structured search index. A search index generated from the pre-processing text.
The second module checks the documents from the Internet. Text of the document is divided into informative parts. The number of parts depends on the size of the document. Next, using a search engine is searched for a sources containing these informative pieces. A search module use Yandex.XML, Yandex.com, Google.ru, Rambler.ru, Yahoo.com, Poisk.Mail.ru, Nigma.ru etc. Received documents are compared with the original document. To do this, the document format is determined (html-document, txt-file, doc-or rtf-document, pdf-file). From a html-document all markup tags are removed. The files *.doc, *.docx, *.rtf and *.pdf converted in a plain text format with no markup. In a next step documents are pre-processed and computed the similarity with the original document.
The main requirements for the system are the completeness and accuracy of duplicates detection. We did not set thetask of reducing a check time.
The algorithm of fuzzy duplicate texts detection was implemented in a system AVTOR.NET [
In 2016 the system Avtor.NET was used to check for a plagiarism of diploma projects full texts in department of technospheric safety of Vladimir State University. During the 10 days was checked more than 70 diploma projects. An each work has been from 60 to 120 pages. For this purpose, it was necessary to get up a new module to reduce the load on the search engines. A system Avtor.NET coped with the task. All diploma projects have been checked and we have received detailed reports on the presence of a plagiarism.
To test the efficiency of the algorithm we were compiled of three group of tests: Fussy duplicates of one document with a reordering of the sentence (T1); Fussy duplicates with a change in the text of the times and kinds of words (Т2); Fussy duplicates of one document with a reordering of the sentence and the addition of the original text between sentences (Т3); Fussy duplicates of some documents with a reordering of the sentence (Т4).
All the tests had a size about 4000 characters and contained an average of 400 words. We used collection of essays, available on the Internet, to creating of tests. 10 tests of each groups was composed.
We compared the results of systems Antiplagiat, AdvegoPlagiatus, AntiPlagiarism.NET, Etxt.ru,Content-watch.ru, Text.Rucont.ru, Unicheck.comwith our algorithm (system Avtor.NET). To assess the quality of detection was used Recall, showing what percentage of duplicate text was really detected. Precision of all the systems was high and trends to 1.
All systems correctly handle test T1. Slightly worse result of Etxt.ru (Recall = 0.75) is due of features comparison algorithm implementation. With the test T2, the systems AdvegoPlagiatus, Text.Rucont.ru and Avtor.NET coped well. Worst results showed systems Unicheck.com (Recall = 0.32), AntiPlagiarism.NET (Recall = 0.58) and Antiplagiat (Recall = 0.63). System Antiplagiat AdvegoPlagiatus AntiPlagiarism.NET Etxt.ru Content-watch.ru Text.Rucont.ru Unicheck.com Avtor.NET
T1 0.98 0.99 0.83 0.75 0.90 0.94 0.95 0.99
Test T3 was well overcome by Text.Rucont.ru, Avtor.NET (Recall = 0.94), Antiplagiat (Recall = 0.89) and Content-watch.ru (0.87).
Test T4 badly passed only Etxt.ru (Recall = 0.49). All other systems showed very good results.
How can we see the system Avtor.NET coped well with all four tests. The algorithm copes well with the replacement of endings, permutations of pieces of text, compilation from several sources and the alteration of texts with the insertion of new words.
The system Avtor.NET correctly handle all texts and show results that are not inferior and sometimes exceed the results of existing systems.Thus, it was created the algorithm of fuzzy duplicates detection. The use of filtering text, stemming and character replacement, allow the algorithm to found duplicates even in minor modified texts.