4 ms·

You both might be interested in this little Nim program "framed" to frame & digest text for near-duplicate detection: https://github.com/c-blake/ndup/blob/

by cb321 4y ago

You both might be interested in this little Nim program "framed" to frame & digest text for near-duplicate detection: https://github.com/c-blake/ndup/blob/main/framed.nim which does a rolling hash with the late Bog Uzgalis' Buz Hash which is (IMO) about 10x simpler than Rabin fingerprinting. It's really just xor out old, xor in new. In my context of near duplicate detection I worry about false negatives as well as false positives and displaying near-bys to the user & such. So, things are set up for random seeds for very independent framings & digests (to avoid unlucky ones). { This is very different from the more common "backup/rsync/transfer" context of "content-based slicing" aka "content-defined chunking". }

__MatrixMan__ 4y ago
Oh wow, this is great. We're up against similar problems here, but what I've got as unnamed musings you've got as links to relevant Wikipedia articles. I've got some reading and thinking to do. I'll probably just include both algorithms, make it a parameter, and do a bunch of testing (which I'll be sure to publish). I can't put my finger exactly on why I feel better about Rabin fingerprints, maybe buzhash just needs time to sink in. It's only recently that I've been thinking of this as a framing problem. The right words eluded me because I only care about the frames near the annotation. So instead of "multiple statistically independent framings" I've been thinking of separate "feature channels" (one for each prime polynomial in GF2) which cause different substrings to be identified as features, but I think it's more or less the same thought deep down. I want a more or less uniform distribution of features so that wherever a user wants to put an annotation, there's always something nearby to anchor it to. In the event of a large gap I've imagined schemes to switch to different framings until its filled . Or maybe I show the features to the user and let them click something to "change the channel" until they get a set of features that works for their particular annotation. Putting this as a nearly-duplicate-files problem makes me wonder if it could be used to arrange files into a graph based on how they differ. Like when browsers unhelpfully just increment a counter and redownloads the the file every time you click a link to it. It's hard to keep track of the fact that copy 6 is the one I want, but if they were rendered as a sort of constellation of files, where the edges are longer for more dissimilarity... That would be fun to play with. Anyway, I'll be looking through this more in the future. Thanks for sharing it.
- cb321 4y ago
  You are welcome. Thanks are too rarely offered. :-) You may also be interested in word stemming ( such as used by snowball stemmer in https://github.com/c-blake/nimsearch https://github.com/c-blake/nimsearch ) or other NLP techniques, but I don't know how internationalized/multi-lingual that stuff is, but conceptually you might want "series of stemmed words" to be the content fragments of interest. Similarity scores have many applications. Weights on graph of cancelled downloads ranked by size might be one. :) Of course, for your specific "truncation" problem, you might also be able to just do an edit distance against the much smaller filenames and compare data prefixes in files or use a SHA256 of a content-based first slice. ( There are edit distance algos in Nim in https://github.com/c-blake/cligen/blob/master/cligen/textUt.nim https://github.com/c-blake/cligen/blob/master/cligen/textUt.... as well as in https://github.com/c-blake/suggest https://github.com/c-blake/suggest ). Or, you could do a little program like ndup/sh/ndup to create a "mirrored file tree" of such content-based slices then you could use any true duplicate-file finder (like https://github.com/c-blake/bu/blob/main/dups.nim https://github.com/c-blake/bu/blob/main/dups.nim) on the little signature system to identify duplicates and go from path suffixes in those clusters back to the main filesystem. Of course, a single KV store within one or two files would be more efficient than thousands of tiny files. There are many possibilities.

by cb321 4y ago

__MatrixMan__ 4y ago

Oh wow, this is great. We're up against similar problems here, but what I've got as unnamed musings you've got as links to relevant Wikipedia articles. I've got some reading and thinking to do. I'll probably just include both algorithms, make it a parameter, and do a bunch of testing (which I'll be sure to publish). I can't put my finger exactly on why I feel better about Rabin fingerprints, maybe buzhash just needs time to sink in. It's only recently that I've been thinking of this as a framing problem. The right words eluded me because I only care about the frames near the annotation. So instead of "multiple statistically independent framings" I've been thinking of separate "feature channels" (one for each prime polynomial in GF2) which cause different substrings to be identified as features, but I think it's more or less the same thought deep down. I want a more or less uniform distribution of features so that wherever a user wants to put an annotation, there's always something nearby to anchor it to. In the event of a large gap I've imagined schemes to switch to different framings until its filled . Or maybe I show the features to the user and let them click something to "change the channel" until they get a set of features that works for their particular annotation. Putting this as a nearly-duplicate-files problem makes me wonder if it could be used to arrange files into a graph based on how they differ. Like when browsers unhelpfully just increment a counter and redownloads the the file every time you click a link to it. It's hard to keep track of the fact that copy 6 is the one I want, but if they were rendered as a sort of constellation of files, where the edges are longer for more dissimilarity... That would be fun to play with. Anyway, I'll be looking through this more in the future. Thanks for sharing it.

cb321 4y ago
You are welcome. Thanks are too rarely offered. :-) You may also be interested in word stemming ( such as used by snowball stemmer in https://github.com/c-blake/nimsearch https://github.com/c-blake/nimsearch ) or other NLP techniques, but I don't know how internationalized/multi-lingual that stuff is, but conceptually you might want "series of stemmed words" to be the content fragments of interest. Similarity scores have many applications. Weights on graph of cancelled downloads ranked by size might be one. :) Of course, for your specific "truncation" problem, you might also be able to just do an edit distance against the much smaller filenames and compare data prefixes in files or use a SHA256 of a content-based first slice. ( There are edit distance algos in Nim in https://github.com/c-blake/cligen/blob/master/cligen/textUt.nim https://github.com/c-blake/cligen/blob/master/cligen/textUt.... as well as in https://github.com/c-blake/suggest https://github.com/c-blake/suggest ). Or, you could do a little program like ndup/sh/ndup to create a "mirrored file tree" of such content-based slices then you could use any true duplicate-file finder (like https://github.com/c-blake/bu/blob/main/dups.nim https://github.com/c-blake/bu/blob/main/dups.nim) on the little signature system to identify duplicates and go from path suffixes in those clusters back to the main filesystem. Of course, a single KV store within one or two files would be more efficient than thousands of tiny files. There are many possibilities.