Re^3: numeric representation of string

Rolling checksums are great for detecting subsections that may be similar, but you then need a full 128-bit or better digest to check they actually are. And even that is not a 100% guarantee.

Your first decision will be how big to make your rolling block size? Bigger saves more space, but very quickly reduces the odds of your finding common sections. Smaller increases you odds of hits; but also increases your odds of false positives and increases the number of full digests you need to calculate in order to deal with those false positives.

And then you have the problem of how you store: 'a-bit-that-is-different' 'a-bit-that-is-the-same-as-some-chunk-of-some-other-email' 'a-bit-that-is-different' a-bit-that-is-the-same-...

Where do you store bits that are common to 2 or more emails? And how do you reference it from the places you removed it?

If your reference mechanism is (say) the 128-bit digest of the common section, that means the size of your rolling checksum block will need to be at least twice that for you to achieve any space saving at all; and probably 4 times to be of merit.

And remember, although the Rsync algorithm is designated as O(N); that is for comparing one pair of files or documents. If you are to do a full cross-compare of all your emails one against the other, you are looking at an O(N²) (or O((N-1)*(N/2)) if you're smart about it) process.

In the end; you'd almost certainly get better compression and save gobs of time and cpu by using gzip or similar.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^3: numeric representation of string

Replies are listed 'Best First'.
Re^4: numeric representation of string by Lawliet (Curate) on Aug 16, 2013 at 11:41 UTC
If you are to do a full cross-compare of all your emails one against the other, you are looking at an O(N²) (or O(N!) if you're smart about it)* process.* Did you forget a word? I'd be interested to see the case where the smart algorithm is O(N!), and the naive one is O(N²).	[reply]
Re^5: numeric representation of string by BrowserUk (Patriarch) on Aug 16, 2013 at 12:07 UTC
You're right of course. Too early in the morning and mixing up n + n-1 + n-2 ... with n * n-1 * n-2 .... It should be O((N-1)*N/2). Corrected. Thanks. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^4: numeric representation of string by mhearse (Chaplain) on Aug 16, 2013 at 17:47 UTC
I agree. My current code inserts email bodies to a compressed table. And that's it. Another simple idea I had was to break up the body by word boundary. Storing it in an array, then doing a bulk insert ignore into a unique column. Might look something like this.... although this a probably a pipe dream. But seems logical... at least based on my stunted repetitive vocabulary. Would have the benefit of being fast due to the lack of compression. `CREATE TABLE words ( rowid INT UNSIGNED NOT NULL AUTO_INCREMENT, word VARCHAR(255) NOT NULL UNIQUE ) ENGINE=InnoDB CHARACTER SET=utf8;` [download] `CREATE TABLE body ( rowid INT UNSIGNED NOT NULL AUTO_INCREMENT, word_order_num INT UNSIGNED NOT NULL, word_rowid FOREIGN KEY REFERENCES words(rowid) NOT NULL ) ENGINE=InnoDB CHARACTER SET=utf8;` [download]	[reply] [d/l] [select]