14 ms·

You can use a two-step hashing approach: for the source file, 1. use Rolling Hash [1] to find the boundaries of the variable-sized blocks of the file, 2. comput

by ww520 12y ago

You can use a two-step hashing approach: for the source file, 1. use Rolling Hash [1] to find the boundaries of the variable-sized blocks of the file, 2. compute a strong hash (sha1) of each block. Repeat the same steps for the target file. Sort the two lists of sha1 block hashes. Then do a merge-compare of the two lists of hash. Blocks of same content have the same hash. See how many blocks are the same out of the two lists. Compute a percentage of similarity. Have some threshold to declare the two files are similar or not. Rolling Hash is good in finding dynamic boundaries of similar blocks, gracefully handling addition, deletion, and movement of content. Once the block boundaries are known, use sha1 to strongly find equivalence. Sorting the two lists allows comparing out-of-order blocks. [1] Content based slicing using rolling hash. http://en.wikipedia.org/wiki/Rolling_hash#Content_based_slicing_using_Rabin-Karp_hash http://en.wikipedia.org/wiki/Rolling_hash#Content_based_slic...

bunderbunder 12y ago
This approach can be very good for finding things like duplicate articles. It might not perform as well with blogspam, though. Rolling hash approaches can be very sensitive to "high-frequency" variation, so all a spammer would need to do to evade it is insert a reasonably high rate of spelling errors or word substitutions. That would have the effect of keeping the segment hashes themselves well-randomized (since even a single character difference should result in a completely different cryptographic hash), or prevent the rolling hash from selecting segment boundaries in a consistent manner. One of the nice things about locality-sensitive hashing algorithms for less-than-pristine data is that you can instead tune it to construct the fingerprint from a larger number of smaller samples, which makes it more likely that you'll get at least some samples which represent all signal and no noise.
- 2510c39011c5 12y ago
  well, how do you define a spam? Is it any document that has been constructed around some key phrases or some urls that are in the spam database? If that's the case, why not just do a similar document evaluation see if the similarity of the document and some sample in the DB reaches certain threshold?
- ww520 12y ago
  Good point about introducing different spelling and word substitution. The original approach is for general data processing. If text document is the only kind of data, then add a pre-processing step to normalize the text. Remove all the stop words. Normalize words to their root to smooth out the different spellings and substitution. Even the Different word normalizations can be tried, Soundex, NYSIIS, or Metaphone.

by ww520 12y ago

bunderbunder 12y ago

This approach can be very good for finding things like duplicate articles. It might not perform as well with blogspam, though. Rolling hash approaches can be very sensitive to "high-frequency" variation, so all a spammer would need to do to evade it is insert a reasonably high rate of spelling errors or word substitutions. That would have the effect of keeping the segment hashes themselves well-randomized (since even a single character difference should result in a completely different cryptographic hash), or prevent the rolling hash from selecting segment boundaries in a consistent manner. One of the nice things about locality-sensitive hashing algorithms for less-than-pristine data is that you can instead tune it to construct the fingerprint from a larger number of smaller samples, which makes it more likely that you'll get at least some samples which represent all signal and no noise.

2510c39011c5 12y ago
well, how do you define a spam? Is it any document that has been constructed around some key phrases or some urls that are in the spam database? If that's the case, why not just do a similar document evaluation see if the similarity of the document and some sample in the DB reaches certain threshold?
ww520 12y ago
Good point about introducing different spelling and word substitution. The original approach is for general data processing. If text document is the only kind of data, then add a pre-processing step to normalize the text. Remove all the stop words. Normalize words to their root to smooth out the different spellings and substitution. Even the Different word normalizations can be tried, Soundex, NYSIIS, or Metaphone.