스팸

시간 제한1초메모리 제한128 MB

요약

스팸과 비스팸 표본에서 트라이그램 빈도를 세고, 각 시험 메시지를 코사인 유사도로 어느 표본에 더 가까운지 판정한다.

난이도: 보통10점 중 5점
유형: 문자열, 해시맵, 수학, 구현
정답자: 아직 제출이 없습니다

문제

원치 않는 이메일(스팸)은 성가시고 메일함을 어지럽힙니다. 스팸 필터, 즉 일반 ASCII 문자로 이루어진 이메일 메시지를 읽어 각 메시지가 스팸인지 아닌지를 판별하는 프로그램을 작성하세요.

메시지가 스팸인지 어떻게 판별할 수 있을까요? 스팸에는 정상적인 이메일에서는 흔치 않은 단어와 문구가 자주 등장합니다. 예를 들어 다음 문구

MAKE MONEY FAST, HONEY!!

는 전부 대문자이고, money라는 단어를 포함하며, 느낌표 두 개로 끝납니다.

스팸 필터를 만드는 한 가지 방법은 많은 스팸 메시지와 정상 메시지를 읽고, 임의의 메시지를 분류하는 규칙 집합을 만드는 것입니다. 이 과정을 사람이 직접 하면 지루하고 실수하기 쉬우므로, 대신 이를 자동화하는 프로그램을 작성합니다.

자동 분류에 유용한 한 단계는 텍스트를 트라이그램(trigram) 집합으로 나누는 것입니다. 트라이그램은 메시지에 등장하는 서로 인접한 세 문자의 나열이며, 대소문자를 구분합니다. 위 문구는 다음 트라이그램들로 이루어집니다:

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

스팸과 정상 메시지의 표본을 살펴보면, 어떤 트라이그램은 스팸에서 더 자주 나타나고 어떤 것은 정상 메시지에서 더 자주 나타납니다. 이로부터 다음 분류 방법을 얻습니다:

많은 수의 스팸 메시지로 이루어진 표본을 살펴보고, 각 트라이그램이 나타나는 횟수를 셉니다. 위 문구에는 서로 다른 트라이그램이 $20$ 개 있으며, ONE과 NEY는 각각 두 번, 나머지 $18$ 개는 각각 한 번 나타납니다. (한 번도 나타나지 않는 트라이그램의 빈도는 $0$ 으로 봅니다.) 좀 더 형식적으로, 각 트라이그램 $t$ 에 대해 스팸 표본에서 나타나는 빈도 $f_{\text{spam}}(t)$ 를 계산합니다.
많은 수의 정상 메시지로 이루어진 표본을 살펴보고, 각 트라이그램 $t$ 가 그 표본에서 나타나는 빈도 $f_{\text{non-spam}}(t)$ 를 계산합니다.
분류할 각 메시지에 대해 모든 트라이그램 $t$ 의 빈도 $f_{\text{message}}(t)$ 를 계산합니다.
$f_{\text{message}}$ 가 $f_{\text{non-spam}}$ 보다 $f_{\text{spam}}$ 에 더 가까우면 그 메시지는 스팸으로, 그렇지 않으면 정상으로 판별합니다.
유사도(similarity)는 $f_1$ 과 $f_2$ 가 서로 얼마나 닮았는지를 나타냅니다. 가장 간단한 척도 중 하나는 코사인 유사도입니다:

$\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}}$

따라서 다음이 성립하면 메시지를 스팸으로 판별합니다:

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

입력

첫째 줄에는 세 정수가 주어집니다: 이어서 주어지는 표본 스팸 메시지의 개수 $s$ , 이어서 주어지는 표본 정상 메시지의 개수 $n$ , 그리고 표본 메시지들의 트라이그램 빈도를 바탕으로 스팸 또는 정상으로 분류할 메시지의 개수 $c$ 입니다. 각 메시지는 여러 줄의 텍스트로 이루어지며, 정확히 ENDMESSAGE만 적힌 줄로 끝납니다. 이 줄은 입력의 다른 어디에도 나타나지 않으며, 메시지의 일부로 간주되지 않습니다.

출력

$c$ 개의 각 메시지에 대해 두 줄을 출력합니다. 첫째 줄에는 $\text{similarity}(f_{\text{message}}, f_{\text{spam}})$ 과 $\text{similarity}(f_{\text{message}}, f_{\text{non-spam}})$ 를 각각 소수점 아래 다섯째 자리까지 반올림하여 출력합니다. 둘째 줄에는 그 메시지의 분류 결과(spam 또는 non-spam)를 출력합니다.

트라이그램을 만들 때 줄바꿈 문자는 절대 포함하지 않으며, 두 줄에 걸치는 트라이그램도 만들지 않습니다. 예를 들어 첫 번째 예제의 첫 번째 스팸 메시지에서 만들어지는 트라이그램은 다음이 전부입니다:

AAA
BBB
BB 
B  
  C
 CC
CCC

예제2

예제 1

입력

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

예상 출력

0.21822 0.73030
non-spam

예제 2

입력

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

예상 출력

0.28761 0.20595
spam
0.44314 0.49243
non-spam