[종만북]9.동적 계획법 테크닉-광학 문자 인식

문제

출처 : https://www.algospot.com/judge/problem/read/OCR

광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정을 말합니다. OCR 알고리즘들은 대개 수많은 필기 샘플을 통계적으로 분석하고 패턴을 찾아내어 각 단어들을 인식하곤 합니다. 하지만 단순히 각 단어들을 개별적으로 인식하기보다, 단어의 분포나 문법 등을 고려하면 더 나은 결과를 얻을 수 있는 경우가 많습니다. 이 문제에서는 과거 자료로부터 추출한 정보를 이용해 문자 인식의 정확도를 높여 봅시다.

과거에 인식했던 수많은 문장들을 분석해 원본 문장의 형태를 파악하려고 합니다. 이 작업을 위해 우선 과거 자료에 출현하는 모든 단어의 목록을 만든 뒤, 각 단어가 문장의 첫 단어로 사용된 비율을 계산했습니다. 그리고 각 단어 쌍에 대해, 한 단어가 다른 단어 다음에 출현할 확률을 계산했습니다. 이때 우리가 인식해야 할 원본 문장은 과거 자료와 똑같은 분포를 가진다고 가정합시다. 달리 말해 이 확률 테이블만 있으면 어떤 원본 문장이 출현할 확률을 정확히 계산할 수 있다고 가정한다는 얘깁니다.

우리의 문자 인식 알고리즘은 원문 그림을 여러 조각으로 쪼갠 후 각 조각을 비슷해 보이는 단어로 분류합니다. 이 분류하는 알고리즘을 분류기(classifier)라고 부릅니다. 이 분류기는 완벽하지 않기 때문에 특정 단어를 다른 단어로 잘 인식할 수도 있습니다. 예를 들어 boy라는 단어를 buy나 bay로 인식할 수 있다는 이야기입니다. 수많은 예제 입력에 대해 분류기를 시험하여, 각 단어가 적힌 조각을 분류기에 입력했을 때 어떤 출력을 얻을 수 있는지, 그리고 각각의 확률은 얼마였는지를 계산했습니다. 예를 들어 분류기에 실제 boy라고 씌어 있는 조각을 입력했을 때, 정확하게 boy로 인식할 확률은 0.7, bay일 확률은 0.25, buy일 확률은 0.04, bye일 확률은 0.01이었다는 식입니다.

이와 같은 정보들을 이용하면 좀더 나은 문자 인식을 할 수 있습니다. 각 조각을 앞에서 예로 든 분류기를 이용해 인식한 결과 “I am a bay.”라는 문장을 결과로 얻었다고 합시다. 그런데 자료를 살펴보니 a 후에 bay가 올 확률은 얼마 없는 반면, a 후에 boy가 올 확률은 매우 컸다고 합시다. 우리의 분류기가 bay라고 인식한 조각이 사실은 boy일 확률이 0.25나 되기 때문에, 이 문장의 인식 결과를 “I am a boy.”로 고치는 편이 더 올바른 분류일 것입니다.

어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부 확률이 가장 높은 문장을 찾아내는 프로그램을 작성하세요.

입력

입력은 분석이 끝난 과거 자료의 통계치와, 분류기가 인식한 문장으로 구성됩니다.

입력의 첫 줄에는 원문에 출현할 수 있는 단어의 수 m (1≤m≤500)과 처리해야 할 문장의 수 q (1≤q≤20)가 주어집니다.
두 번째 줄에는 원문에 출현할 수 있는 m개의 단어가 공백으로 구분되어 주어집니다. 각 단어는 알파벳 대소문자로만 구성되어 있습니다. 모든 단어의 길이는 10 이하입니다.
세 번째 줄에는 각 단어가 문장의 처음에 출현할 확률 B[i]가 m개의 실수로 주어집니다. B[i]는 i번 단어가 첫 단어로 출현할 확률입니다. 모든 B[i]의 합은 1입니다.
그 후 m줄에 m×m 크기의 실수 행렬 T가 주어집니다. 이 행렬에서 i행 j열의 숫자 T[i, j]는 i번 단어의 다음 단어가 j번 단어일 확률을 나타냅니다. 각 행에 있는 확률의 합은 항상 1입니다.
그 후 m줄에 m×m 크기의 실수 행렬 M이 주어집니다. 이 행렬에서 i행 j열의 숫자 M[i, j]는 i번 단어가 적힌 조각을 j번 단어로 분류할 확률을 나타냅니다. 각 행에 있는 확률의 합은 항상 1입니다.
그 후 q줄에 한 줄에 하나씩 분류기로 인식한 문장이 주어집니다. 각 줄의 처음에 단어의 수 n (1≤n≤100)이 주어지고, 그 후 n개의 단어로 분류기의 인식 결과가 주어집니다. 모든 단어는 처음에 주어진 m개의 단어 중 하나입니다.

입력의 크기가 크므로 빠른 입력 방식을 사용하기를 권장합니다.

출력

한 문장마다 한 줄에 주어진 인식 결과에 대해 조건부 출현 확률이 가장 높은 문장을 출력합니다. 주어지는 입력에서 가장 확률이 높은 문장이 여러 개인 경우 어느 것을 출력해도 좋습니다.

풀이

문제의 조건이 매우 복잡하여 풀기 어려워 보이나 실제로는 간단한 확률 문제임을 알 수 있다. 분류기로 입력받은 문장에서 각각의 단어에서 확률을 계산하는데, 이 때의 확률이 최대가 되는 값을 찾아 저장한다. 핵심은 T와 M으로 입력받은 확률값이다. T는 현재단어의 다음 단어 확률을 나타내는 값으로 현재 단어가 무엇이냐에 따라 다음 단어의 확률이 결정된다. 따라서, 현재 단어의 확률은 결정된 이전 단어에 따라 영향을 받는다고 볼 수 있다. 그러므로 함수를 구현할 때 매개변수로 현재 단어와 이전 단어에 대한 값을 설정하여야 한다. 또한 현재 위치에 올 단어가 그 단어일 확률을 T를 통해 계산하여 이를 곱하여야 한다.

이를 통해 계산하고자 하는 단어의 위치에 모든 단어를 비교하면서 각각 해당 위치에 올 수 있는 확률을 계산하여 확률이 최대가 되는 단어를 찾아야 한다. 즉, T와 M을 곱하여 확률을 해당 위치에 올 단어의 확률을 계산하여야 한다. 이 때 중요한 것은 단순 해당 위치에 올수 있는 확률이 최대인 단어가 온다고 해서 문장 전체가 옳은 문장인 것은 아니라는 것이다. 즉, 해당 위치의 다음 단어들로부터 계산된 확률 또한 같이 생각하여 문장 전체의 확률을 계산해 전체 확률을 비교하여야 한다. 따라서 이러한 개념에 재귀호출을 적용하여 다음 단어들로부터 계산된 확률을 곱하여 해당 위치로부터 나머지 단어들까지의 확률을 계산하는 함수를 구현하여야 한다.

// 입력받은 문자열의 idx~ 위치값의 최대 확률값 계산(prev = 앞 단어의 기준 단어에서 위치)
static double OCR(int idx, int prev) {
		// 기저 사례 : 문장 끝에 도달한 경우
		if (idx == n)
			return 0;
		double ret = -Double.MAX_VALUE;
		int wid = S[idx];
		if (cache[idx][prev] != 1.0) {
			return cache[idx][prev];
		}
		for (int i = 1; i <= m; i++) {
			double temp = T[prev][i] + M[i][wid] + OCR(idx + 1, i);
			if (temp > ret) {
				ret = temp;
				cache[idx][prev] = ret;
				choice[idx][prev] = i;
			}
		}
		return ret;

	}

함수는 입력받은 문자열의 현재 위치 idx와 앞 단어의 위치(기준 단어에서 인덱스값) prev를 매개변수로 하여, 이전 단어가 prev로 분류되고 idx부터 계산된 확률을 리턴하는 함수이다. idx는 분류할 문장에서의 단어 위치로 확률값에서 나타내는 인덱스 값이 아니기 때문에 주어진 단어가 기준 단어들 중 몇번째 인덱스인지 찾아 대입하여야 한다. 이를 위해 분류기에서 단어를 입력받는 과정에 입력받은 단어가 기준 단어의 몇번째 인덱스인지 저장하도록 배열 S에 저장하여 S[idx]로 그 값을 찾도록 구현하였다.

나의 풀이는 책의 풀이와 개념과 구조는 동일하나 세부적인 방식에서 차이가 나타났는데, 확률값이 동시에 일어날 확률은 곱연산이나 매우 작은 값으로 입력되어 프로그램상에서 오차가 발생할 가능성을 고려하여 로그연산으로 변환하였다는 것이다. 즉, 확률값 T와 M을 입력할 때 로그값으로 변환하여 저장하고, 이후 확률을 계산하는데 있어서 로그값으로 생각하여 곱연산이 아닌 덧셈연산(log ab = log a + log b)을 통해 계산하여 오차를 최소화하도록 구현하였다. 또한, 분류기에 들어온 문장 중 첫번째 단어는 앞 단어가 없으므로 T가 아닌 B(첫 단어일 확률)을 통해 계산하는데, 이렇게 되면 첫단어를 따로 검사하여 B를 사용해 계산하여야 하므로 보다 효율적인 연산을 위해 T에서 맨 앞 인덱스(0)를 B의 확률값으로 넣고, 1부터 원래 확률값으로 생각하여 한번에 계산하도록 구현하였다. 즉, -1위치에서 가상의 단어값이 있다고 생각하고, 각 인덱스에 1씩 더하여 이를 구현한 것이다.

위 함수를 통해 최대 확률값이 계산되었을 때 해당 단어의 인덱스를 따로 choice 배열에 저장하고, 이를 아래와 같은 별도 함수를 통해 재분류된 문장을 구성하도록 하였다.

static String reconstruct(int idx, int prev) {
		int ch = choice[idx][prev];
		String ret = words[ch];
		if (idx < n - 1)
			ret = ret + " " + reconstruct(idx + 1, ch);
		return ret;
	}

choice배열은 앞서 구현하였던 함수에서 idx와 prev값에 따라 최대 확률값을 나타내는 인덱스를 저장하였기 때문에, 초기 위치에서 시작하여 재귀적으로 호출해 각 위치에 오는 분류된 단어들을 불러오도록 하였다. 이를 통해 확률이 가장 높은 문장의 각 단어들을 출력할 수 있다.

Menu

문제

입력

출력

풀이