Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm trying to detect if an article or forum post is a duplicate entry within the database. I've given this some thought, coming to the conclusion that someone who duplicate content will do so using one of the three (in descending difficult to detect):

  1. simple copy paste the whole text
  2. copy and paste parts of text merging it with their own
  3. copy an article from an external site and masquerade as their own

Prepping Text For Analysis

Basically any anomalies; the goal is to make the text as "pure" as possible. For more accurate results, the text is "standardized" by:

  1. Stripping duplicate white spaces and trimming leading and trailing.
  2. Newlines are standardized to \n.
  3. HTML tags are removed.
  4. Using a RegEx called Daring Fireball URLs are stripped.
  5. I use BB code in my application so that goes to.
  6. (ä)ccented and foreign (besides Enlgish) are converted to their non foreign form.

I store information about each article in (1) statistics table and in (2) keywords table.

(1) Statistics Table The following statistics are stored about the textual content (much like this post)

  1. text length
  2. letter count
  3. word count
  4. sentence count
  5. average words per sentence
  6. automated readability index
  7. gunning fog score

For European languages Coleman-Liau and Automated Readability Index should be used as they do not use syllable counting, so should produce a reasonably accurate score.

(2) Keywords Table

The keywords are generated by excluding a huge list of stop words (common words), e.g., 'the', 'a', 'of', 'to', etc, etc.

Sample Data

  • text_length, 3963
  • letter_count, 3052
  • word_count, 684
  • sentence_count, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • keyword 1, killed
  • keyword 2, officers
  • keyword 3, police

It should be noted that once an article gets updated all of the above statistics are regenerated and could be completely different values.

How could I use the above information to detect if an article that's being published for the first time, is already existing within the database?


I'm aware anything I'll design will not be perfect, the biggest risk being (1) Content that is not a duplicate will be flagged as duplicate (2) The system allows the duplicate content through.

So the algorithm should generate a risk assessment number from 0 being no duplicate risk 5 being possible duplicate and 10 being duplicate. Anything above 5 then there's a good possibility that the content is duplicate. In this case the content could be flagged and linked to the article's that are possible duplicates and a human could decide whether to delete or allow.

As I said before I'm storing keywords for the whole article, however I wonder if I could do the same on paragraph basis; this would also mean further separating my data in the DB but it would also make it easier for detecting (2) in my initial post.

I'm thinking weighted average between the statistics, but in what order and what would be the consequences...

share|improve this question

migrated from stackoverflow.com Oct 8 '12 at 0:01

This question came from our site for professional and enthusiast programmers.

    
If it's an exact match you could simply set a field to unique. If not, you'd need to decide at what point a text can be considered a copy or a closely derived work. –  James Poulson Oct 8 '12 at 0:01
2  
There are many directions in which this kind of analysis can go. People write entire books on this sort of topic. If your goal is to determine "relative closeness" you really have little choice but to dig into what's called Natural Language Processing and Machine Learning. That's what computer scientists call it, but it's really just advanced statistical analysis. A good starting point might be looking at levenshtein distances, but "dumb" stats like word/sentence counts are likely going to do very little for you. –  rdlowrey Oct 8 '12 at 0:05
1  
Also, before it was migrated from SO this was tagged [php], so you might check out php's native levenshtein function –  rdlowrey Oct 8 '12 at 0:07
    
Great idea to have a human check likely duplicates! You may be able to automatically decide that > 7 is a duplicate and < 6 is different and only have humans check scores of 6 or 7. I know that with spam identification there is a machine-doesn't-know-AND-human-doesn't-know-either category; a gray area between a near duplicate and an original work where the best you can do is make a somewhat arbitrary judgement call. –  GlenPeterson Oct 8 '12 at 1:14
    
@rdlowrey - Levenshtein algorithms are what I used in a similar project I did in C#. I agree, it's a good place to start and may be enough. –  jfrankcarr Oct 8 '12 at 2:47
add comment

4 Answers

up vote 3 down vote accepted

There are many algorithms that deal with document similarity in NLP. Here's a seminal paper describing various algorithms. Also wikipedia has a larger collection. I favor the Jaro Winkler measure and have used it for grad school projects in aglomerative clustering methods.

share|improve this answer
add comment

For an exact mathematical math I'd store a hash and then compare that.

I think the systems which are used for exams measure groups of words and then the frequency of groups of each size. For example a chain of 30 words which are copied would score 5 risk points and 5 occurrences of 10 word chains wold score 5 points. Then you'd have a thresh hold of 30 points per 500 words.

Really you need a semantic algorithm so that words like 'also' and 'and' are parsed as the same.

share|improve this answer
add comment

Take a look at the Rabin-Karp algborithm. It uses a rolling hash somewhat like rsync uses to minimize bytes transmitted during a sync. By adjusting the size of the window you use for the hash you can make it more or less sensitive. R-K is used for, amongst other things, plagiarism detection, which is basically looking for sort-of dupes.

share|improve this answer
4  
The problem the OP describes seems exactly like plagiarism detection, and I'd suggest that as the first place to look for help. (Just be sure to identify your sources!) –  Caleb Oct 8 '12 at 6:01
add comment

A first go at this might be to detect sentences (or some other reasonable block of data. Take those blocks and strip any mete data, html random white space, returns etc. Take an MD5 of result and store it in a table. You could then match against these blocks to try to find matches.

If this does not work you might try n-grams. Here you need one entry of each word on the page, but it should be able to give you pretty good matches.

http://en.wikipedia.org/wiki/N-gram

share|improve this answer
    
n-grams based measures are much better than md5 hashes especially for semi-structured data such as html. –  Candide Oct 8 '12 at 0:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.