[C++] 영어에서 인접한 두 글자의 빈도수 구하기

단일 치환 암호를 풀 때 빈도수를 이용하면 효과적으로 해독할 수 있다. 그런데 한 글자의 빈도수를 세는 것만으로는 부족할 때가 많다.

code.org에서는 단일 치환 암호를 알파벳 치환을 실시간으로 바꾸며 해독해볼 수 있다. 위의 사진은 원본 암호이고, 글자들을 빈도순으로 나열하고 나서 영어의 알파벳 빈도 순서와 1:1로 치환하면 다음과 같이 된다.

Yah ogt ni tse giwsahtel bawkcatehr oy tse giyarsnoiabde eil oy tse certehi rmnhad ahu oy tse Padajf dner a ruadd gihepahlel feddoc rgi.

전혀 이해할 수가 없다.

이때 우리는 많이 쓰이는 특정 단어들의 패턴을 유추해서 그에 맞게 해독할 수가 있다.

예를 들어 unrehabde이나 giyarsnoiabde와 같은 단어가 있을 때, 영어에서 ~able로 끝나는 단어의 패턴이 많다는 사실을 이용해 d와 l의 위치를 바꿔보는 것을 고려해볼 수 있다.

그다음 lnttle은 little로, tse를 the, bgt를 but이라고 생각하면 n과 i를 바꾸고, s와 h를, u와 g를 바꿔볼 수 있다.

이렇게 한 글자의 빈도수만으로는 해독이 불가능할 때 문맥을 적절히 이용해야 하는데, 이 개념을 단순화한 것이 인접한 두 글자의 빈도수를 구하는 것이다.

예를 들어 'elephant'라는 단어의 '인접 글자'는 다음과 같다.

el / le / ep / ph / ha / an / nt

이렇게 만든 '인접 글자'들의 빈도를 저장한다.

a~z까지의 알파벳을 0~25의 숫자로 대응해서 26x26 이차원배열에 빈도를 저장한다.

예를 들어 'el'은 freq[4][11]에 저장한다.

    int freq[26][26] = { 0 }; // 인접 글자 빈도를 담는 2차원 배열
    int all = 0; // 총 인접 글자의 개수

    ifstream input;
    input.open("input.txt");

    string word;
    while (!input.eof()) {
        input >> word;

        for (int i = 0; i < word.length(); i++) {
            // 대문자는 소문자로 변환
            if (word[i] >= 'A' && word[i] <= 'Z') {
                word[i] += (-'A' + 'a');
            }
        }

        for (int i = 0; i < word.length() - 1; i++) {
            // 양쪽 글자 모두 알파벳인 경우
            if (word[i] >= 'a' && word[i] <= 'z'
                && word[i + 1] >= 'a' && word[i + 1] <= 'z')
            {
                freq[word[i] - 'a'][word[i + 1] - 'a']++;
                all++;
            }
        }
    }

 

그 다음 std::set를 이용해 인접 글자 빈도 순으로 인접 글자들을 정렬 후 출력한다. (내림차순 정렬은 하기 귀찮아서 그냥 빈도를 음수로 뒤집어 저장했다.)

	set<pair<int, string>> freqSet; // 인접 글자 빈도 순으로 인접 글자들을 정렬

	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < 26; j++) {
			freqSet.insert(pair<int, string>(-freq[i][j], makeSeq(i + 'a', j + 'a')));
		}
	}

	for (auto f : freqSet) {
		// 빈도가 0이면 출력x
        if (f.first == 0) break;
		cout << f.second << '\t' // 인접글자
			<< -f.first << '\t' // 인접글자 등장 횟수
			<< (double)-f.first / all * 100 << "%" << endl; // 빈도
	}

makeSeq은 그냥 두 char를 이어서 string으로 만들어주는 함수다.

string makeSeq(char c1, char c2) {
	return string(1, c1) + string(1, c2);
}

 

전체 코드는 맨 밑에 적겠다.

 

자료는 영어 위키백과에서 랜덤 글을 1000줄 정도 모았다. 실행 결과를 조금만 소개하면 다음과 같다.

in, on, the, at 등의 단어들이 많이 쓰였기 때문이라고 추론해볼 수 있다.

그림에는 없지만 is의 비율이 약 0.7%밖에 안 되는데, 생각보다 적다. 찾기 도구로 검색해봐도 총 483개밖에 없었다.

 

실제로 해보진 않았지만, 한 글자가 아닌 인접한 두 글자의 빈도를 같이 비교한다면, 더욱 효과적으로 단일 치환 암호를 해독할 수 있지 않을까 생각해본다.

 

<전체 코드>

#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

string makeSeq(char c1, char c2) {
	return string(1, c1) + string(1, c2);
}

int main() {
	int freq[26][26] = { 0 }; // 인접 글자 빈도를 담는 2차원 배열
	int all = 0; // 총 인접 글자의 개수
	set<pair<int, string>> freqSet; // 인접 글자 빈도 순으로 인접 글자들을 정렬

	ifstream input;
	input.open("input.txt");

	string word;
	while (!input.eof()) {
		input >> word;

		for (int i = 0; i < word.length(); i++) {
			if (word[i] >= 'A' && word[i] <= 'Z') {
				word[i] += (-'A' + 'a');
			}
		}
	
		for (int i = 0; i < word.length() - 1; i++) {
			if (word[i] >= 'a' && word[i] <= 'z'
				&& word[i + 1] >= 'a' && word[i + 1] <= 'z')
			{
				freq[word[i] - 'a'][word[i + 1] - 'a']++;
				all++;
			}
		}
	}

	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < 26; j++) {
			freqSet.insert(pair<int, string>(-freq[i][j], makeSeq(i + 'a', j + 'a')));
		}
	}

	for (auto f : freqSet) {
		if (f.first == 0) break;
		cout << f.second << '\t'
			<< -f.first << '\t'
			<< (double)-f.first / all * 100 << "%" << endl;
	}
}