Spam

Time limit1sMemory limit128 MB

Summary

Count trigram frequencies in sample spam and non-spam messages, then classify each test message by which sample it matches more closely under the cosine similarity measure.

Level: Medium5 of 10
Topics: String, Hash map, Math, Implementation
Solved: No attempts yet

Problem

Unsolicited email (spam) is annoying and clutters your mailbox. Write a spam filter: a program that reads email messages made of ordinary ASCII characters and decides whether or not each message is spam.

How can we tell whether a message is spam? Spam tends to contain words and phrases that are uncommon in genuine email. For example, the phrase

MAKE MONEY FAST, HONEY!!

is all uppercase, contains the word money, and ends with a double exclamation mark.

One way to build a spam filter is to read many spam and non-spam messages and come up with a set of rules that classify any particular message. Doing this by hand is tedious and error prone, so instead we write a program to automate it.

A useful step is to split the text into a set of trigrams. A trigram is a sequence of three adjacent characters that appear in the message, and it is case sensitive. The phrase above is composed of the trigrams:

MAK
AKE
KE 
E M
 MO
MON
ONE
NEY
EY 
Y F
 FA
FAS
AST
ST,
T, 
, H
 HO
HON
ONE
NEY
EY!
Y!!

If we examine a sample of spam and non-spam messages, some trigrams turn out to be more common in spam and others more common in non-spam. This leads to a classification method:

Take a large sample of spam messages and count how many times each trigram occurs. In the phrase above there are $20$ distinct trigrams: ONE and NEY occur twice each and the remaining $18$ occur once each. (A trigram that never appears occurs $0$ times.) Formally, for each trigram $t$ we compute the frequency $f_{\text{spam}}(t)$ with which it occurs in the spam sample.
Take a large sample of non-spam messages and compute $f_{\text{non-spam}}(t)$ , the frequency with which each trigram $t$ appears in that sample.
For each message to be filtered, compute $f_{\text{message}}(t)$ for every trigram $t$ .
If $f_{\text{message}}$ resembles $f_{\text{spam}}$ more closely than it resembles $f_{\text{non-spam}}$ , the message is spam; otherwise it is non-spam.
A similarity measure tells how closely $f_1$ and $f_2$ resemble one another. One of the simplest is the cosine measure:

$\text{similarity}(f_1, f_2) = \frac{\sum_t f_1(t) \times f_2(t)}{\sqrt{\sum_t [f_1(t)]^2} \times \sqrt{\sum_t [f_2(t)]^2}}$

A message is classified as spam if

$\text{similarity}(f_{\text{message}}, f_{\text{spam}}) > \text{similarity}(f_{\text{message}}, f_{\text{non-spam}})$

Input

The first line contains three integers: $s$ , the number of sample spam messages that follow; $n$ , the number of sample non-spam messages that follow; and $c$ , the number of messages to be classified as spam or non-spam using the trigram frequencies of the sample messages. Each message consists of several lines of text and is terminated by a line containing exactly ENDMESSAGE. This terminator line never appears anywhere else in the input and is not considered part of the message.

Output

For each of the $c$ messages, print two lines. On the first line print $\text{similarity}(f_{\text{message}}, f_{\text{spam}})$ and $\text{similarity}(f_{\text{message}}, f_{\text{non-spam}})$ , each rounded to five decimal places. On the second line print the classification of the message (spam or non-spam).

When forming trigrams we never include a newline character, and we never form a trigram that spans two lines. For example, in the first spam message of the first sample the only trigrams are:

AAA
BBB
BB 
B  
  C
 CC
CCC

Examples2

Example 1

Input

2 1 1
AAAA
BBBB  CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE

Expected output

0.21822 0.73030
non-spam

Example 2

Input

1 1 2

 DOES THIS SOUND LIKE YOU?



 * Tired of Mounting Credit Card Debt?

 * Frustrated by Creditor Harrassment?

 * Bogged down by Medical Expenses?

 * Just Plain Tired of the Financial Insanity?



 HERES WHAT WE CAN DO...



 * Reduce your debts by up to 60%!

 * Reduce or Eliminate Interest!

 * Preserve or Rebuild your Credit

 * Stop the Harrassing Phone Calls!



 CLICK HERE TO GET OUT OF DEBT 



 Did you know that you could reduce all of your unsecured debt by up to

 60% and consolidate it into ONE monthly payment WITHOUT taking out

 another loan?!



 Let US deal with your creditors, we'll negotiate a reduced payback and

 combine all of your debt into one simple payment saving you thousands

 of dollars! Take 90 seconds to fill out the simple quote form to see

 how much less you could be paying. It's fast, free and there is no

 obligation to apply!



 CLICK HERE FOR A FREE QUOTE 

 Please know that we do not want to send you information regarding our

 special offers if you do not wish to receive it. If you would no

 longer like us to contact you or feel that you have received this

 email in error, please click here to unsubscribe.

ENDMESSAGE

If any of them do Java stuff, they might be interested in Soot, our

research compiler. A new release is due out any day now.

http://www.sable.mcgill.ca/soot/



Of course, there are other similar things out there. The Flex compiler

at MIT is quite nice. It's a native code compiler, whereas Soot outputs

bytecode.



I guess Chambers has some stuff too, but I haven't played with it. He

apparently uses Soot for his courses.



Other stuff we have (www.sable.mcgill.ca):

SableCC, a better yacc in Java

Ashes, a bunch of Java benchmarks

SableVM, would have been a nice VM, but no really usable versions exist yet

an mostly up-in-the-air profiling and visualization thingie



We don't have any non-Java stuff. Laurie has some old C stuff, but I

don't know that it's very general-purpose.



Ondrej

ENDMESSAGE

We collect Child Support AND OUR SERVICES COST YOU NOTHING!!!



Do you or someone you know need help collecting your child support payments?



We have strong interest in uncollected Child Support in your

City and Area.



We are the largest firm in the world specializing in the

Collection of Child Support.



Currently we are processing millions of dollars worth of Child Support in

the United States alone. We have associate offices in virtually every city

in the US and in most foreign countries.



Let us help you collect what your children are due!



Contact us now for more information.

You have absolutely nothing to lose!!!





Please call 1 877 306 6599 8am to 5pm CST Mon-Sat.

Consultants are waiting for your call...

















++++++++++++++++++++++++++++++++++++++++++++++++++++++++

This ad is pro duced and sent out by:

Unive rsal Adve rtising Syste ms

ENDMESSAGE

Thanks for giving GB the good word on Web traps and treatment thereof.



However, I am puzzled (as usual). I have occasionally encountered similar

garbage which is difficult to dump but I almost never approach the Web via

IE

but use Netscape Communicator to get to Google and so on. GB declares that

she, also, uses Netscape. Do IE and Net ever talk to each other?



We seem to have developed the old problem of the task bar (?) being vertical

rather than horizontal. I looked up you past advice, e.g about the RH mouse

button, but haven't had success in getting the bar back down to the bottom.

It's certainly not a serious problem but sometimes I have to do a a lot of

fiddling to get at the close button and scroll control.



I have finally got around to burning some pictures onto CD's. I had a lot

of trouble matching up what it said in the "manual" with what it said on the

screen but now I ignore the manual and things work fine. I have had

absolutely no Adobe seizures in the course of these burns. What Adobe

doesn't seem to like is combined operations involving the printer. There it

often quite cold at various stages in the procedure.



Has Judy moved from the active to the nail-biting phase of the comp exam?

Pass on our regards.



ENDMESSAGE

Expected output

0.28761 0.20595
spam
0.44314 0.49243
non-spam