[동적 계획법] OCR 광학 문자 인식

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
 
string words[500];
int classifiedIndex[101];
int wordN = 0, stringN = 0, classifiedN = 0;
double T[501][500];  // i -> j next sum = 1 T[before][start] 
double M[500][500];  // i -> j p  sum = 1
 
double cache[501][100];
int cacheI[501][100];
 
int findIndex(string str)
{
    for(int i = 0; i < wordN; i++)
        if( words[i].compare(str) == 0)
            return i;
    return -1;
}
 
double decode(int before, int len);
 
void show(int before , int len)
{
    if(cacheI[before + 1][len] != -1)
    {
        cout<<words[cacheI[before + 1][len]];
        if(len + 1 == classifiedN)
        {
            cout<<"\n";
            return;
        }
        else
            cout<<" ";
        
        return show(cacheI[before + 1][len] , len + 1);
    }
    else 
        return;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    double tmpp;
    cin>>wordN>>stringN;
    for(int i = 0; i < wordN; i++)
        cin>>words[i];    
    for(int i = 0; i < wordN; i++)
    {    cin>>tmpp; T[0][i]=log(tmpp);}
    for(int i = 1; i <= wordN; i++)
        for(int j = 0; j < wordN; j++)
        {   cin>>tmpp; T[i][j] = log(tmpp);}
    for(int i = 0; i < wordN; i++)
        for(int j = 0; j < wordN; j++)
       {   cin>>tmpp; M[i][j] = log(tmpp);}
    for(int i = 0; i < stringN; i++)
    {
        fill_n(&cache[0][0],501*100, 1.0 );
        memset(cacheI, -1, sizeof cacheI);
        
        cin>>classifiedN;
 
        string tmp;
        for(int j = 0; j < classifiedN; j++)
        {
            cin>>tmp;
            classifiedIndex[j] = findIndex(tmp);
        }
        decode(-1, 0);
        show(-1, 0);
    }
}
 
double decode(int before, int len)
{
    if(len == classifiedN) return 0;
 
    double &ret = cache[before + 1][len]; 
 
    if(ret != 1.0) return ret;
 
    
    ret = -1e200;
    
    for(int i = 0; i < wordN; i++)
    {
        double p_q = T[before + 1][i]; 
        double p_rq = M[i][classifiedIndex[len]];
        double cand = decode(i, len + 1) +  p_q + p_rq;
        if(cand > ret)
        {
            ret = cand;
            cacheI[before + 1][len] = i;
        }
    }
 
    return ret;
}

1. 문제의 핵심

이 문제의 핵심은 "확률" 과 "언더플로" 이다.

 

2. 조건부 확률과 베이즈 정리

이 문제에서 구하는 조건부 확률은

분류된 문장이 A 일때 원래 문장이 B일 확률이다.

 

베이즈 정리로 표현해보자면

P(B|A) = P(A|B)*P(B) / P(A)

 

여기서 P(A)는 문제에 정해준 문장이 나오는 확률이다.

주어진 단어로 만든 임의의 B 문장과 다르게

P(A)는 문제에서 주어졌으며 항상 같다.

 

따라서

P(A|B) * P(B) 의 최대값만 구하면 답을 구할 수 있다.

 

P(A|B)

    = bi라는 단어를 ai로 해석할 확률  = Π M[b, a]

P(B)

    = 원문이 출현할 확률 = 마르코프 연쇄에 의해 생성된다고 가정

    = bi다음에 bi+1이 올 확률

    = Π T[bi-1 ,bi]

 

(문제에서 주어진 B[i] 배열은 T[0][i]에 해당한다)

 

3. 동적계획법

decode(-1, 0)

                                                   n

decode(before, len) = MAX( Π (decode(i, len+1)*T(before + 1, i) * M(i, A(i).index))) 

                                                 i = 0

 

다음 단어가 출현할 확률은 이전 단어에 의해 결정되기 때문에

재귀 호출함수에는 이전 단어를 전달해야하고 어느 위치에서 최대가 되는지 알아야하므로

포함된 단어의 개수 또한 전달해야한다.

 

 

4. 언더 플로

 

실제 확률의 곱대신 확률의 로그 값의 합을 쓴다     

 

입력에 주어지는 확률 값들은 매우 작기 때문에

언더 플로가 일어나기 쉽기 때문이다.

 

 

5. 은닉 마르코프 모델

마르코프 연쇄를 통해 생성된 데이터들을 우리가 직접 볼 수 없고,

오류가 있는 별도의 관찰자(분류기)를 통해 관찰해야 하는 모델

 

HMM의 관측결과가 주어질 때 가장 가능성 높은 실제 상태를 계산하는 것으로

이 방식은 비터비 알고리즘이라고 부르는 유명한 얼고리즘이다.

문자인식, 무선송신데이터, 음성인식결과 정정, DNA정보 분석 등등에 쓰인다

 

 

OCR