There's more than one way to do things PerlMonks

### numeric representation of string

by mhearse (Chaplain)
 on Aug 15, 2013 at 21:53 UTC Need Help??
mhearse has asked for the wisdom of the Perl Monks concerning the following question:

I'm storing email bodies to database. Because I'm a big fan of deduplication... I ask the following. How can I get a numeric representation of a utf8 encoded string (email body)? The goal being to search for a similar body and do a diff instead of re-storing the entire email body. Which seems wasteful. Thanks in advance. Update: I know I can manually do a Levenshtein algorithm against all previously stored bodies. But that seems to defeat the purpose... as it would be very wasteful. Hmmm... maybe convert to hex and then to decimal? I don't know.

Replies are listed 'Best First'.
Re: numeric representation of string
by BrowserUk (Pope) on Aug 15, 2013 at 23:39 UTC
How can I get a numeric representation of a utf8 encoded string?

Essentially, you cannot for strings of any usable length.

Unicode strings stored in computers are essentially very big numbers stored base-131072 (if you stick to just the very basic multi-lingual subset).

With decimal numbers encoded as a string (eg. '12345'), each digit can be 0-9, so the size of the number grows by a factor of 10 for each extra digit. So by the time you've got 20 digits, you've exhausted the capacity of 64-bit integers. And if you move to floating point, you start loosing accuracy after just 15 digits.

For hex numbers encoded as a string, each extra digit adds a factor of 16, so you exhaust 64-bits ints with only 16 digits.

With Unicode you have 128k for each digit, so by the time you've got a 4 character string you've exceeded the capacity of a 64-int by a factor of 10.

So basically, you can give up on the idea of an accurate representation of a string by a number.

Then you move into the realm of 'lossy' representations. And there is a whole science (and a lot of bunkum) that attempts to produce 'comparative' numerical values from documents -- numbers derived from text that will when sorted numerically tend to group the documents by similarity. These are used for applications such as plagiarism detection. A simple starting point which may lead you in many directions.

Another approach might be to use a 'running checksum' to detect sections of similarity. For that approach the Rsynch algorithm is a useful starting point.

For the most part, if your goal is simply to save space in your db, you'd probably be better off using a simple compression algorithm.

Update: for completeness, you might find Re^3: Comparing sets of phrases stored in a database? enlightening.

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

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.
Re: numeric representation of string
by tobyink (Abbot) on Aug 15, 2013 at 23:21 UTC

Similar; or same?

If you're matching bodies which are exactly identical, then use a digest algorithm like MD5 or SHA1/SHA256.

If there are some variations allowed (e.g. variations in whitespace) then it might still be possible to use a digest, provided you canonicalize the message body first (e.g. by stripping all whitespace).

package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
Re: numeric representation of string
by Corion (Pope) on Aug 16, 2013 at 08:08 UTC

In addition to BrowserUks comments, if you are dealing with mail and deduplication, you may want to look at what mailinator does. They discard lots of mail obviously, but their results may be interesting.

Thanks. I'll check that out.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1049658]
Approved by ww
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (9)
As of 2018-05-28 10:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (199 votes). Check out past polls.

Notices?