Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^2: numeric representation of string

by mhearse (Hermit)
on Aug 16, 2013 at 00:37 UTC ( #1049668=note: print w/ replies, xml ) Need Help??


in reply to Re: numeric representation of string
in thread numeric representation of string

Wow. Thanks for the excellent and thorough answer. I think for starters I'll use your suggestion of a running checksum. Thanks again!

Update: Just finished reading Re^3: Comparing sets of phrases stored in a database?. I'm going to do that as a project just for the fun of it. Great solution for determining similar phrases.


Comment on Re^2: numeric representation of string
Re^3: numeric representation of string
by BrowserUk (Pope) on Aug 16, 2013 at 10:12 UTC

    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(N2) (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.
      If you are to do a full cross-compare of all your emails one against the other, you are looking at an O(N2) (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(N2).

        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.
      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;
      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;

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1049668]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2014-10-21 03:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (95 votes), past polls