I'd like to be able to identify duplicate jokes posted on a website. I can build up a reasonably large database of previously-posted jokes, and then I'd like to look at each new joke as it comes in and pick out the most "similar" jokes from the database and spit them out, in order, if my confidence that the new joke is a duplicate is above some threshold.
I could look for exact character-by-character matches but that's not very interesting, and it would fail to catch "near duplicates." For example, I'd like the following two jokes to be considered the same:
Three men walk into a bar. The first one says "ouch!", the second one says "ouch!" The third one ducks.
Three men go to the bar. The first one says "ow!!!!", the second one says "OWW!!!!!", the third one ducks.
I imagine that many duplicate jokes involve names of characters being swapped out (i.e. a story about "Little Suzy" rather than "Little Johnny", or a joke about the president with "Barack Obama" swapped for "George Bush"), and I'd like those to be counted as the same joke, too.
I've been reading about plagiarism detection algorithms and none of them seem to quite fit, since they're geared towards much larger texts (the average joke is probably only a few dozen words), or they rely on some special property of academic work (i.e. citation analysis).
I found a paper at one point that I haven't been able to find again that I thought was an interesting that went something like this: collapse each text into a vector
v such that if the
ith word of your vocabulary appears
n times, then the value of
n. Then when you get a new joke, compute the distance between it and all of the other vectors you've built; the closest vector is the most likely source text. It explored a few different variations on the idea and compared their effectiveness.
This seems like a sensible idea to me, but I wonder if it won't be too sensitive to things like swapping out names, and I can't find the paper again to check the exact details of how they handled it.
I'm not sure how I could apply other machine learning techniques to this, like an SVM or neural net, since it's basically a classification problem over a few thousand different classes with no more than a handful of examples for each class. And there's no nicely-labeled dataset out there of duplicate jokes, as far as I know.
What's a reasonable strategy for this? Can anyone point me in the direction of useful literature?
(This project is purely for fun, and I'm just looking for some semi-reasonable approximation. I know that NLP in general is very hard to do and that a real, accurate answer to this would be virtually impossible.)
EDIT (in response to the dupe flag): as I've sketched out in some comments, I don't think that string edit distance is a great approach to this because:
- it places inappropriate weight on swapping out things consisting of multiple characters that shouldn't change the meaning (names, for example)
- it requires me manually figuring out a good threshold for a positive match; there's no dataset for me to test it on
- it cares about order: I'd rather have something like a bag-of-word approach because a joke can be substantively the same while flipping around sentences
- it's potentially expensive: whenever I see a new entry, I need to recompute its string edit distance against every single joke I've seen
- it's not very interesting (I'm doing this for fun, after all) and I'm not convinced that there isn't an algorithm that better captures the notion of "joke similarity" than straight character-by-character comparison; if someone has evidence that string edit distance is the best tool for this job, I'm open to hearing that --- but that's not an argument provided by the answer linked in the dupe flag