스팸

원치 않는 이메일(스팸)은 성가시고 메일함을 어지럽힙니다. 스팸 필터, 즉 일반 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