Using gzip As A Spam Filter 268
captainclever writes "Kuro5hin have an interesting article on detecting spam using gzip." Here's a sample: "Loosely speaking, the LZ (Zip) and the related gzip compression algorithms look for repeated strings within a text, and replace each repeat with a reference to the first occurrence. The compression ratio achieved therefore measures how many repeated fragments, words or phrases occur in the text."
Grep it instead! (Score:2, Funny)
Re:Grep it instead! (Score:2)
Re:Grep it instead! (Score:5, Funny)
Raw data (Score:5, Informative)
Not that different (Score:5, Interesting)
A Bayesian filter uses words as "symbols." gzip uses bytes as symbols.
The right thing to do would be to combine them.Ttake a gzip-style Markov model, using bytes as symbols and conditional probabilities, and plug it into a Bayesian filter. That would (1) make the filter more powerful and (2) make the filter applicable to any sort of data, arbitrary binary or readable text. Negligible computational overhead, sharper discrimination.
Sorry, that's not right (Score:5, Interesting)
Bayesian only refers to how you use the probabilities.
Now gzip implements similar ideas to LZW compression, which uses variable sized prefixes, which is quite different from an 1-order Markov model. For example, and order 1 Markov model is not allowed to depend on more than the current and immediately preceding symbol.
bzip2 results (Score:5, Informative)
And, of course, do try this at home.
It's all spam (Score:4, Funny)
Re:It's all spam (Score:5, Interesting)
You know, I noticed something peculiar. If you're from a non-English speaking country, like I am, you can filter the spam by looking at the language of the subject. In my case, if it is English it is almost certainly spam.
Do English-speaking people receive spam in foreign languages?
I receive a lot of Russian spam (Score:2)
In Soviet Russia...
Korean (Score:2)
Foreign Language Spam (Score:2)
Since a large portion of popular sites onlines are in english, it stands to reason that when you sign in your email address on an english site, it gets added to an english spamlist. Since I don't sign up on any Korean/Swiss/etc sites, they haven't yet gotten my email address yet (or don't care about it).
That being said, people in N. America and english speaking countries do get a lot of spam in english from foreign servers - which is where IP range blocklists and spamassassin come in handy.
Re:It's all spam (Score:2)
Of course, an insane number of those spam messages seem to be duplicates of themselves sent day after day, but still. Everything's in English in my account.
Slashdot filter (Score:5, Interesting)
Re:Slashdot filter (Score:4, Informative)
What is different, as has been pointed out, is that Slash compresses a particular post and looks at how well it compresses, but does not compress/compare with other posts.
Re:Slashdot filter (Score:3, Funny)
Err, ignore the troll account part, I never said that.
Re:Slashdot filter (Score:2)
Meet the Bayesian Filtering Algorythm (Score:5, Informative)
Re:Meet the Bayesian Filtering Algorythm (Score:3, Informative)
OTOH, it seems to me that some other model, such as a scheme that gives legitimate senders explicit advance AUTHORIZATION to send you email, might be what's needed. How to implement that is, well, left as "an exercise for the reader" -- actually, this has been discussed on
Re:Meet the Bayesian Filtering Algorythm (Score:5, Informative)
I understand what you're saying, but there are a couple of problems with this, depending on how you implement it. If you allow potential correspondents to request authorization by email, you'll still have to process at least one message per originating address. That obviously won't work to eliminate spam (or even cut it down to size...) The other option is to force potential correspondents to request authorization over another channel (phone, fax, whatever), but this neatly destroys a lot of the convenience of email. It also eliminates the impersonal nature of email (by forcing a personal contact) when it is partly this impersonality that distinguishes it in the first place (and encourages some first time correspondents to make contact at all...)
Actually, the Bayesian filter implemented by POPFile [sourceforge.net] is remarkably accurate. A friend of mine has been using it since it debuted on slashdot in November [slashdot.org] and it has correctly classified all of the spam he's received since (76% of his email in total, unfortunately...)
You can also set up POPFile to process the headers of your messages as well as the body, so it will effectively learn the email addresses of people you're willing to receive email from anyway. Depending on how you define words (what you use as token separators), you could attempt to make it generalize to domains as well.
Re:Meet the Bayesian Filtering Algorythm (Score:2)
I'm skeptical about heuristic filters, because of the possibility of the occasional false positive, which could be an embarrasment (or worse).
However, the filtering technology is very much of interest to me, for other reasons... I will take a look at POPFile for sure.
Right tool for right job (Score:2, Interesting)
HTML (Score:5, Interesting)
My friends do not use HTML in email. Ads for "Crimescene Cocksuckers" does.
Re:HTML (Score:2, Informative)
Re:HTML (Score:2)
Excellent (Score:5, Funny)
It won't work for businesses (Score:5, Funny)
Yes please! (Score:2)
Spam Conference talk (Score:5, Interesting)
Basically it's a way to discover features in emails using compression techniques, so rather than having us SpamAssassin developers have to carefully and manually examine emails to see what's new and interesting about them, MLD techniques can automatically detect these features.
Jason Rennie's web page (talk and paper available) about this is here [mit.edu]. Please do read it as it's extremely interesting.
The one downside of it is that Jason said at the end of his talk that it's extremely slow at doing the feature detection. When asked how slow he said that on a reasonably small corpus it took 4 months (although he said it was written in Perl, so a C port is probably a good plan).
In comparison to Bayesian techniques the MLD technique presents a great deal of interest - primarily because I work for a company doing spam filtering at the internet level [messagelabs.com], and so we can't feasibly do personal training which is what makes Bayesian techniques so great (see the talk I gave at the MIT spam conference). Without the personal training Bayes is only about 90-95% effective, so it should be interesting to see where these techniques lead us.
Re:Spam Conference talk (Score:3, Interesting)
At the personal level, each of these newly "discovered" techniques (I remember a
Re:Spam Conference talk (Score:3, Insightful)
No, for a large scale service you need much lower rates of false positives than any of the DNSBLs provide right now. They're fine as inputs into heuristic or statistical systems, but on their own they are just not accurate enough.
Re:Spam Conference talk (Score:3, Interesting)
In the case of open relays, yes a whole company can be hosed mail-wise when the get on a list, but if multiple BLs agree, then they've got a problem that needs to be fixed.
For the case of people who share a spammers address range, I feel for them, but... do I really want to take the pressure off of them in favor of flooding the world with spam? I'd personally be pissed at my ISP for allowing such spammers to screw over MY reputation among the BLs. ISPs should behave accordingly, but right now why would they? They get far more money from spammers than from people who will leave because a few folks listening to the BLs get mail from your customers.
Spam is an ugly thing, and combating it is hard. Casualties are going to arrise. The question is: how do you minimize that list of casualties and make sure that people know the safety dance ahead of time.
Re:Spam Conference talk (Score:2)
Frankly it's the spammers that should suffer, not the legitimate users. False positives in the fight against spam cause nothing but animosity. We've had DNSBLs for a long time now, and I see nothing but an increase in the level of spam. Are DNSBLs working for you? Maybe. Is the collateral damage model reducing the amount of spam the world sees? Nope. Not remotely.
Time to move on, try something else. Time to stop more spam and hit them in the pocket. We've no evidence that will work either, but at least we're trying something.
Re:Spam Conference talk (Score:5, Insightful)
What bothers me about this method is that you can never be 100% sure what the learning algorithm will actually learn. My friends seldom send me HTML mail. Most of my spam is HTML. A learning algorithm will probably learn that HTML mail is spam, especially if it never gets HTML "ham" during its training period. Then if one of my clueless friends sends me a HTML message, it will not go through and this is clearly bad.
I will never trust an automatic filter so as to delete a message marked as "spam" without reading, but I think it can still be useful for ranking messages, so that spam gets read less often and deleted faster.
Quantitive, not qualititive (Score:5, Interesting)
for example Two Emails:
1 (ham) "You have won a brand new Convertible, from the competition you entered."
and
2 (spam) "A brand new convertible to be won, have you entered?"
Ham would match about 80% with spam.
Word matching is a blunt instrument as mentioned. The English language is far too complex for simple calculations, this fact should be taken into consideration, when applying a 'Spam Likelihood' rating to Emails.
Re:Quantitive, not qualititive (Score:5, Interesting)
This happened to a friend of mine (Score:2)
The only slight problem was that he doesn't drive :-)
Don't compress (Score:3, Funny)
I delete it.
This will save me a lot more space
Same old problem... (Score:5, Insightful)
Given that, the alternative to having tagged emails automativally deleted is to collect them in a folder and scan the message senders and subject lines. If you're doing that, then the spammer is getting a pitch through to you in the subject line. This therefore does not lessen the incentive for the spammer, but simply causes him to change tactics and put his best pitch in his subject line.
Right now, I get 60-80 spams a day. What happens when I start getting 600-800 a day? Again, filtering starts to break down, because I have SO MANY messages to scan everyday that the possibility of me missing a legitimate one is very high.
Re:Same old problem... (Score:3, Informative)
BODY contains "The following message was sent to you as an opt-in subscriber to RB Express."
FROM contains Trivia
TO or CC contains "johnsmith@isorox.co.ku"
FROM contains theracingpost.com
TO or CC contains "spam" (I use sitespam@isorox to sign up to sites)
BODY contains "to receive" AND "more of these offers"
Move to a Spam folder
If TO or CC doesnt contain
isorox.co.ku
exeter.ac.ku
ex.ac.ku
Move to possible Spam
That gets about 80-90% of my spam.
I skim Possible Spam when I get time, usually once or twice a day. I skim Spam about once every 2 days. i've got a couple of rules that just delete the spam straight off (known junk addresses that I'll never need, certain subjects, etc). Keep all my spam too, and check it when I get time, just in case.
Re:Same old problem... (Score:5, Interesting)
One of the side effects of spam is that there are no "Really Important Emails" any more. Spam and spam filters have degraded the reliability of email to such an extent that you'd have to be crazy to send anything Really Important by email.
Right now, I get 60-80 spams a day. What happens when I start getting 600-800 a day?
That's a good point. The solution is to get less spam. You can do that by changing email addresses frequently (a really inconvenient solution that I don't recommend), or by getting spammers shut down (or yourself listwashed by the spammers).
Let the spammers know that if they send something to you, they'll lose money, and they won't send you so much spam. SpamCop [spamcop.net] reporting makes this easy. If you want to be listwashed, don't munge your address when you send reports. (This is an option with SpamCop.)
Some people claim that you'll get more spam or get listbombed or something if you send complaints without munging; that's not my experience. I get 20-30 spams per day, total, at all of my 4 publicly available email addresses. (Ninety to 95 percent of them get caught by the SpamCop filters, which have almost never caught valid email.)
Re:Same old problem... (Score:2)
Re:Same old problem... (Score:2)
And I don't miss the false positives because I scan my spam. But the key point is I don't interrupt what I'm doing in order to respond to spam anymore. Well, less often anyway.
Spam is bad, but spam is life. Filtering is not perfect, but it is helpful.
Re:Same old problem... (Score:2, Interesting)
What happens when I start getting 600-800 a day?
Start another account and don't give it to strangers who might sell it. Only give it to the person or persons who are going to send that really important email message. Throw in a few random numbers so if one gets leaked to spammers you can track the source (i.e., I gave my employment agency (obviously an important contact) chuck369, and nobody else. Now if chuck369 starts getting spam we know employment agency leaked it). Use 'throw away' accounts for untrusted contacts who might leak it to spammers.
Re: (Score:2)
Re:Same old problem... (Score:2)
Given that, the alternative to having tagged emails automativally deleted is to collect them in a folder and scan the message senders and subject lines. If you're doing that, then the spammer is getting a pitch through to you in the subject line. This therefore does not lessen the incentive for the spammer, but simply causes him to change tactics and put his best pitch in his subject line.
I guess that this is an interesting question. I keep hearing this argument that filtering is a bad thing because of the risk of false positives. But how is the risk of false positives reduced by removing the filter? Spam filtering for me is a valuable cognitive aid. (One modification to spam assassin would be to put the spam score on the subject line.) I can live with skimming subject lines because many spam models are based on the number of hits from users who buy or click on links in spam.
I also think that it argues a straw man. I don't read very many comments from people who believe that filtering is "the solution". However, content-based filtering is one valuable tool for sorting through large numbers of messages. By all means we should persue trasport-based and source-based strategies for fighting spam as well. But these have their own problems.
Finally, if someone wants to cold-call me out of the blue with a Really Important Message, don't they have a responsibility to compose their message without much of the hype, and html text that gets flagged as spam? It would seem that such a cold-call would have no problems getting through as long as they don't make excessive use of all caps, font tags, embedded images, base-64 encoded text, and references to my penis. If it was really important enough to be worth my time, then it probably is not going to have enough spam features to be flagged as spam.
Re:Same old problem... (Score:2)
That is why filtering fails as a solution.
You know that email from the headhunter that wanted to double your current pay rate and cut your hours by a third? No you don't, because it got flagged as spam and accidentally deleted.
Spammers will adjust their tactics (Score:5, Interesting)
Re:Moron (Score:5, Interesting)
I actually read the article.
The proposal is not to see how compressible is the message but to use a compression tool to see how lookalike the message is to a corpus of spam.
Yes, and compression ratio is used to determine this.
Alternative (Score:5, Interesting)
One problem with this is the right to open other people's mail. But you could use some basic scrambling (rot-13) to make sure that no one sees the inside. It wouldn't make difference to the comparing script.
Mailing lists might cause a problem too but wouldn't it be easier to allow the mailing lists you belong to than trying to block the ones you don't belong to?
Sequitur Most Likely Superior (Score:5, Interesting)
As an example of how Sequitur works, the string 'abcabdabcabd' produces the following grammar rules:
- 2 c 2 d
- a b
Representing the original string then is the sequence:1 1
The usage counts of the rules are available as output options.
Re:Sequitur Most Likely Superior (Score:2, Insightful)
Yay! (Score:5, Funny)
I could use this to avoid those people who keep saying the same thing all the time, over and over again...
Now, how can I convince my mother to use e-mail?
My spam compression approach (Score:2)
After at most 10 applications of said compression utility, all emails looks like this:
"1"
I never see any spam.
-josh
What is spam, though? (Score:5, Funny)
-Mark
How to stop spam.... (Score:4, Informative)
2: when registering use a unique address e.g. slashdot@mydomain.com
3: Make sure you check/uncheck the give my email address to mailing lists.
4: If ever you get spam to that account get litigious.
Use something like mailinglists@mydomain.com, and block anything that doesn't come from mailing lists you've subscribed to.
Re:How to stop spam.... (Score:3, Insightful)
Re:How to stop spam.... (Score:2)
I've got two hotmail accounts that have been relatively spam free for years.
I say relatively because you'll still receive spam if they guess [commonfirstname][commonMiddleName][CommonLastnam
Heck, one of 'em's the email I signed up on slashdot with!
Re:How to stop spam.... (Score:2, Informative)
I've been doing this for years, and in practice, it just means I get 12 copies of most spams, because they got my address from 12 different places, usually web archives of the mailing-lists.
You can't refuse mail from non-lists to mailinglists@your.domain, because then nobody can contact you saying "I saw your post on foo-list and was wondering if I could get a copy of foo-prog and if you could tell me how you made it foo bar baz".
filtering across multiple accounts (Score:2)
What about having a filter check all your accounts at once? If you're receiving the same email on more than one account, chances are it's spam.
Re:How to stop spam.... (Score:5, Interesting)
You need to expand on your step 4.
When I started getting spam, I wanted it to stop. I realized I couldn't just disable the email address because there might be somebody out there counting on it to contact me. I could disable it and send an autoreply with my current email address, but then spammers would just be able to look at the reply. I needed some solution where people could send me email even if the address they used had been disabled, but spammers wouldn't be able to get my current address. I decided to put a contact form on my website. Now I autorespond to a disabled email address with the contact form url. In addition, I was able to remove email addresses from my website which was a large source of spam.
Not being able to find a contact form that was secure, I ended up writing my own and releasing it under the GPL. You can get it at http://ostermiller.org/contactform/ [ostermiller.org].
I also realized that no matter how hard you try, your email address will leak to spammers. Ever giving an email address only to your closest friends and family will not prevent it from leaking out. Between the klez virus, gift certificates, invitation, greeting card, and crushlink websites, even my most personal email address leaked to spammers. You can't be afraid to disable an email address and send your friends the new one. Now even if I missed a friend, they can still get a message to me.
Just use a string entropy calculation algorithm... (Score:4, Interesting)
Besides, if I were a spammer, I could pad it with high entropy data at the end to make up for my warbling.
Re:Just use a string entropy calculation algorithm (Score:2)
If I were a spammer I'd concentrate more on trying to get average users to open my mail even though they've learned that Cindy's "Haven't seen you in ages, JOE23" Emails aren't real. And how to circumvent whatever anti-spam measures come installed in JOE23's AOL software.
Anyways, some geek in his dorm room is not likely to have enough money to buy penis prosthetics anyway and can also figure out how to jerk off to free thumbnail-pics.
If spammers started padding their mail with high entropy data I would set up a filter that filters out mails based on how close the character recognition is to standard English HTML-formatted mails, and discards random junk.
But then spammers would start not just using high entropy material from
Then the antispammer would have to use fuzzy-logic spell-checking and the spammer would have to start using random words out of the dictionary and finally spammers would be left with no other option than to send me really nice personalized eCards that say "Happy Birthday!" with a little singing chicken, because I haven't found a way to filter those yet. I can only filter spam with mammals
Re:Just use a string entropy calculation algorithm (Score:2)
What I was suggesting is that ISPs actually employ these methods... thus the average user will not even know they were spammed. (Most IPSs employ a troop of Geeks who know where to do:
"strings
Personally I prefer an active approach (such as ASK), and preferably the one with the features that has a minimal impact on legitemate users. I still receive about 30 spam mails a day, but with a combination between my IPSs anti-spam system, and my active spam protection, I see about 1 every month only.
Re:Just use a string entropy calculation algorithm (Score:2)
You're right on the money though what filtering at the ISP is concerned, that's where the most benefit would be for the end-user. I see two problems, though.
First, the ISP has to pay bandwidth for the incoming email, spend money on filtering but then isn't rewarded with more time/bandwidth consume by their clients.Secondly, I think they'd be deathly afraid of inadvertantly filtering out some false positives and being sued.
Think what would happen if some marketing department tries to send their customer the rough draft of a mailing and it keeps getting eaten by the ISP's spam filter.
Re:Just use a string entropy calculation algorithm (Score:3, Interesting)
While true that your measly Linux machine has no
But anyway, back to your question: if you're sad you don't have
ln -s
Compression algorithms as filters... (Score:5, Insightful)
a) Spammers might not always use messages redundant enough to be detectable from regular text.
b) If I happened to use some words a little too often, especially when writing mails discussing technical stuff or posting computer code fragments, would that be classified as spam?
I think this is a nice filter when sorting out more or less repetitive mails (spam or not) from novels, but a filter based on a spam database sounds better to me.
I can't figure this out... (Score:4, Interesting)
A couple of posts above state that spammers will "just adjust their tactics." Talk like this always puzzles me; on the spammer's side, does this not help him? If I'm selling a combination weight loss drug/mail order bride/penis enlarger/cable descrambler for only three payments of $49.99 in such a manner that every spam blocker in the world filters me, logically I'm only being filtered by people who know better than to buy my "product," thus not irritating them, in effect helping to slow regulation, and I don't loose touch with any significant chunk of my target demographic. Of course, this applies with the exception of corporate environments or similiar situations where Joe Insecure has someone else managing spam.
Can anyone share some +5 Insight on the matter?
Re:I can't figure this out... (Score:5, Insightful)
Take Yahoo, for example. They're a popular webmail service and they also do spam filtering to some extent on inbound email. I would say that, in general, people who use Yahoo mail are not necessarily the type of people who "know better" than to buy spamvertised products. That's not a slam on Yahoo, nor on the people who use Yahoo mail, it's just the way the demographics work out. The ratio of ripe targets to clued-in antispammers is simply better at Yahoo than it is on other domains.
To that end, Yahoo's spam filters aren't helping the spammers any. A spammer's goal is to get his ad in front of as many potential targets as possible, and Yahoo is full of potential targets. But if Yahoo's filters catch the spammer's message and route it straight to everyone's Bulk Mail folder, there's (thousands|millions) of "targets" who will never see the message.
So no, I can't agree that filtering helps the spammers any, at least not the big spammers who are after volume. There's probably a bit of "collateral assistance" in that people who would report the spam may never see it, but I'd say that benefit is cancelled out by the number of possible targets lost to filters.
Re:I can't figure this out... (Score:3, Insightful)
The numbers are part of their pissing contest, and the pool is your inbox. Spammers are not that bright, but their customers are much, much more stupid.
Re:I can't figure this out... (Score:2)
Rule 1: Spammers lie.
Rule 2: Spammers are stupid. Not to say they are not cunning, but stupid.
Rule 3: If you think a spammer is telling you the truth, see Rule 1.
Rule 4: Spammers will stop when they can't make money fast! spamming.
Stopping Spam (Score:5, Insightful)
Filters only work to a limited extend, and so might shutting down the spammers, if it were possible.
But neither is going to solve this problem.
The only solution I can think of is wide-spread adoption of PGP (or equivalent) aware mailers and certification of mail.
The problem with mail addresses is that you have no control over their spread. If I give one to a company it'll usually leak out in the end and it's open season on my inbox.
However if "genuine" mail is certified and mailers use certification validity as a filtering critera then it simplifies the game hugely.
Your mailer can spot the people you've genuinely given your address to, and naturally "distrust" uncertified (effectively anonymous) mail or mail whos certificate has been revoked or is unknown to you.
The "only" things standing in the way of this are:
1. Slow adoption of certification/encryption in mass market mailers. Usually poor or missing.
2. Cost/diffiulty of getting a valid certificate (e.g. with Verisign).
3. The pain of typing a password every time you send a mail.
4. It only works if everyone joins in.
But nothing's for free and this strikes at the heart of emails useability.
I'm continually suprised by the lack of certification use at least by large corporations and governments, but I suppose it removes plausible deniability
Re:Stopping Spam (Score:2, Insightful)
Think about this: Why do I get 1000's of spam emails per month and I get 10's of peices of junk snail mail/month? Simple: It costs nearly nothing to send millions of spam messages, while it costs a bundle to send junk snail mail.
A simple solution would be to find a way to charge per email...
Now, I certainly wouldn't pay per email. But, I shouldn't complain when someone abuses a messaging system that allows millions of messages to be sent out for nearly no cost. I use that system too, on a much smaller scale, for personal and legitimate business use.
All I can do is ignore as much of the mail as I can, and BOYCOTT anything that is sold via spam.
Ag.
Disposable Email addresses (Score:2)
I came to this realization driving home from work one night. My immediate follow-up thought was, why not make email addresses disposable, with a nice automated interface to control which ones will fwd to your "real" mailbox? I had worked out a rough framework for how I'd implement this at a site-wide level by the time I got home, only to discover that I wasn't the first one to come up with the idea. A quick google search on "disposable email address" found about half a dozen services that do (more or less) what I'd hashed out.
Doesn't solve everything, but it does give you a lot more control when choosing what to put in the "email" form when you buy something online
Re:Stopping Spam (Score:2, Interesting)
The only solution I can think of is wide-spread adoption of PGP (or equivalent) aware mailers and certification of mail.
I have to discourage your optimism a bit. IF the public-key encryption ever finds its way to the general public (I hope and think so), there are two possibilities:
a) Your public key will be available for the general public -- this is how it will probably work. If someone wants to send you an e-mail, he obtains your public key in a trusted way (e.g. from a trusted key server), encrypts the message and sends it. If the spammer wants to send you spam, once he gets your e-mail address, he does exactly the same. Obtains your public key, encrypts the spam and sends it. The only difference with today's situation: it will be impossible to filter spam on the server side (only to block some spamming IP addresses, no server-side spam filters).
b) You give your public key only to your friends you trust. This is exactly the approach "everything coming from an address, that's not in my address book, has to be spam." and even contradicts the basic idea: it's your public key...
Email to my girlfriend (Score:5, Funny)
"I'm sorry. Really, really, really, really sorry. I'm so very, very, very sorry. I'm sorry..."
Spammers just found another loophole.. (Score:5, Interesting)
To unsubscribe by postal mail, please send your request to:
P.O Box 272521
Boca Raton, FL 33427
Ref # XXXXXX -- scd
(XXXX.. replaced real reference number)
It seems that the unsubscription method doesn't have to be by email - just as long as it's by something and it's there. They musn't be specific in the law. Of course, no one is going to go write a letter by snail mail to unsubscribe to spam, although sending them some dog shit through the mail is tempting. I forgot the site that provides that service. Hrmm I should change my sig.
32k Window... (Score:4, Informative)
I'll be happy with spam assassin [spamassassin.org] until I get CRM114 [sourceforge.net] (and mailfilter) trained and working.
Similar article on heise was published a year ago (Score:2, Informative)
The article has a link to another article published in "Physical Review Letters" which deals with the topic of identifying content/author by applying compression algorithms.
The underlying idea is that LZ77 compressed data is near to the entropy of a message.
Even Better (Score:2, Informative)
Yawn -- read your papers (Score:4, Informative)
Correction (Score:2, Insightful)
The compression ratio achieved therefore measures how many repeated fragments, words or phrases occur in the text.
There is a minor problem with this sentence. And with this whole gzip business. It is misleading. Words, phrases? You cannot force gzip to match words, gzip tries to exploit every likeliness found, even at the character level. E.g., if your "spam dictionary" contains words sex and pants, mail about sextants will have a good compression ratio. And there is no way how to prevent this. That's why the Bayesian filters (operating on words) outperform gzip by a league. That's (one of more reasons) why I think this article belongs not to /. but to a wastebin instead. It simply presents a worse approach to do something. Interesting idea, yes, but that's all.
(Just FYI: it is proved, that the bzip2 algorithm due to Burrows and Wheeler exploits all such repeatings in the input file nearly optimally -- within some small ratio. Hence, it is even worse to use it as a spam filter :-)
Repost? (Score:4, Interesting)
Here is a code snippet from the comment:
How about.... (Score:3, Interesting)
A similar idea (no pun intended) (Score:2)
Bayesian Filters (Score:2)
Sorry, but I don't see how this is anything different from just another spin on Bayesian Statistical filtering of spam that everyone's been playing with.
It's hardly patentable. But it is interesting to see. But, once you look at it, not surprising.
Messages from teenagers would be spam (Score:5, Funny)
[E-mail from skittles9333@some.email marked as spam and deleted] So like, I was like sick, and like, I didn't go to school today. So like, I was told like, that Jim like said, that like you might like, have some homework due like tomorrow. Could you like, tell me what like that homework would like be?
Nope (Score:3, Insightful)
Zip on DNA & Different Languages. (Score:2, Interesting)
But from reading all these posts, perhaps a Bayesian method would work just as well. There seems to be no inherent advantage to using zip. One still needs a reference piece of work (non-spam email, or bacteria 1) for comparing entropies or probabilities. Of interest also is that the researchers applied their method to generating an accurate language tree of Indoeuropean languages (grouped by relatedness of course.)
The ref & abstract of above paper is here:
Phys. Rev. Lett. 88, 048702 (2002)
Dario Benedetto,1 Emanuele Caglioti,1 and Vittorio Loreto2,3
In this Letter we present a very general method for extracting information from a generic string of characters, e.g., a text, a DNA sequence, or a time series. Based on data-compression techniques, its key point is the computation of a suitable measure of the remoteness of two bodies of knowledge. We present the implementation of the method to linguistic motivated problems, featuring highly accurate results for language recognition, authorship attribution, and language classification. ©2002 The American Physical Society
Re:Text of the full article (Score:5, Insightful)
The current fad is in fact Bayesian filtering, sophisticated statistical analysis.
gzip used this way can be viewed as a very poor Bayesian analysis with substantially lower effectiveness. Lets just skip the half-assed attempt and go straight to the real thing.
Re:Text of the full article (Score:5, Informative)
An actual Bayesian filter would perform a statistical analysis of an existing body of spam and non-spam messages, identify key words or phrases that identify a message as spam or non-spam, and calculate the probability for every key word that a message containing that word is spam. Then every new message is classified as spam or non-spam by running a statistical analysis on its content, and the statistics of that message update and improve the probability model.
Re:Text of the full article (Score:2, Informative)
> The current fad is in fact Bayesian filtering, sophisticated statistical analysis.
Baysian filtering IS word-counting with (not very sophisticated) statistical heuristics applied to the results.
Re:Text of the full article (Score:3, Informative)
This may be the case, but most of the newer filters available now are not really Bayesian filtering by this definition. I use spambayes [sourceforge.net], and it has some very sophisticated algorithms to determine the statistical probability of the "spamminess" of a ham/spam.
Some of these fancier algorithms were developed by Gary Robinson and are discussed in some detail here [weblogs.com]. You can see the results of these different classification techniques (gary combining, chi-squared) in some nice graphs here [sourceforge.net].
On a related note, spambayes is VERY accurate in catching spam for me. Amazingly so in fact. It does a far better job than SpamAssassin or the Bayesian filter in Mail.app in my personal experience.
Re:Text of the full article (Score:2)
First you count the occurrances of each word in spam and nonspam. This gives you the probability that spam contains the word, and that nonspam contains the word. Then you use Bayes' theorem to compute the reverse - the probability that, given a message contains a word, it is spam or nonspam. You take the product of this value for all words in the message. Then you normalize so the sum of probability of spam and nonspam equals 1. (This is a so-called "naive bayesian classifier". Somebody might be using a bayesian network with a more complicated structure, but it would still be based on WORD COUNTING as the first step)
GZIP used this way ... (Score:3, Interesting)
As an aside, since it could be fully automated it would be interesting to run the such an algorithm with a graphical display, say a 2D plot of compression size vs time of day just to see what shakes out.
By the way, the problematic portion for bioinformatics apps is the compression. DNA sequences often exhibit _expansion_ when put through the common compression schemes. Li has come up with a compression scheme that is more optimal called GenCompress.
Kolmogorov Complexity - http://www.idsia.ch/~marcus/kolmo.htm
Minimum Description Length - http://www3.oup.co.uk/computer_journal/hdb/Volume
Bioinformatics app - http://www.cs.ucsb.edu/~mli/sam.ps
GeneCompressi
Re:Text of the full article (Score:2, Interesting)
I've often thought since that large mailhubs (yahoo, hotmail, etc) could automatically filter junk mail efficiently by a similar method, perhaps by limiting the delivery rate/fingerprint or just flagging high-occurence hashes as suspect (and then rating each mail by how many of its fingerprints are among this group, too many without an ADV: or bulk-mail tag would cause a mail to be marked as SPAM).
I wonder if it'd be possible to have a network of smaller hubs accomplish the same thing, perhaps even using an encrypting checksum instead of a simple hash so that individuals could contribute without anyone being able to recreate their original messages?
Re:this is nice (Score:3, Informative)
This, on the other hand, talks about gziping the mail in the context of corpora of known spam or known ham. Thus it serves as a classification of types of Englishg text, whereas the slashdot system only tries to classify whether or not it is actually English text at all.
Re:Maybe I am missing something here (Score:4, Funny)
the text in each is quite varied; e.g. longer xxx
The text in each of my spams seems to have more XXX...
Re:Legislation (Score:3, Funny)
RBL (Score:5, Interesting)