[C++] 광학 문자 인식 OCR

https://algospot.com/judge/problem/read/OCR

소요 시간: 2시간 + α

해결: X

---

인식한 문자열 R과 원문 Q가 있을 때, T[i][j](단어 i 다음에 단어 j가 올 확률)와 M[i][j](문자 i를 j로 잘못 인식할 확률)로 R에서 Q를 구해내는 문제입니다.

 

현재 위치에 어떤 단어가 올지 모르니 모든 단어에 대한 확률을 계산해야 합니다.

이전에 선택한 단어의 인덱스가 prev일 때 이번 선택한 단어의 인덱스가 curr일 확률은 T[prev][curr]

문장의 첫 단어는 T 대신 B[curr]을 사용하면 됩니다.

 

현재 단어를 인식한 문장의 pos번째 단어 R[pos]로 잘못 인식할 확률은 M[curr][R[pos]]

 

이 식을 교재에서는 아래처럼 표현했습니다.

 

저는 아래처럼 재귀적인 구조를 떠올렸습니다.

---

어찌저찌 원문을 만드는 확률을 구하는 것까지는 좋았는데 두 가지 문제가 남아있었습니다.

문제1. 확률이 지나치게 작아서 0이 되어버리는 현상

인식한 문자의 길이는 100개, 단어 풀은 500개, 입력이 커지게 되면 확률이 0에 근사해지면서 컴퓨터에서는 0으로 표현되어버립니다.

사실 확률 문제 자체도 익숙지 않은 상태라서, 교재를 보기 전까지는 이런 현상이 있는 줄도 몰랐네요.

(stl에 log 변환 함수가 있는지도 처음 알았...)

 

이런 현상은 로그 확률로 해결할 수 있습니다.

확률에 로그를 취하면 로그 확률을 구할 수 있습니다.

 

로그 확률은 음수 형태로 나타나며, 독립 사건의 로그 확률은 더해집니다.

https://en.wikipedia.org/wiki/Log_probability

Log probability - Wikipedia

 

 

문제2. 구한 확률로부터 원문을 복원하기

부분 문제를 풀며 어떤 선택을 했는지 저장 해놓은 다음 따라가면서 복원하면 됩니다.

저장은 이전에 prev번 단어를 선택했을 때 pos번째에 어떤 단어를 선택할지 저장하면 되겠네요.

 

저는 prev을 무시하고 pos만 고려하는 1차원 배열로 생각을 해서 한참 헤맸습니다...

 

choice의 (0, 0)에 저장되어 있는 첫 번째 단어부터 따라 올라가면서 출력하면 됩니다.

---

int m,q;
double B[SZ], T[SZ][SZ], M[SZ][SZ];
string dict[SZ];
vector<int> R;
double cache[101][SZ];
int choice[101][SZ];

int get_idx(string word){
    for(int i=0;i<m;i++)
        if(dict[i]==word)
            return i;
    return -1;
}

double select(int pos, int prev){
    if(pos==input.size())return 0.0;
    
    double& ret = cache[pos][prev];
    if(ret!=1.0)return ret;
    ret = -1e200;
    
    int& cho = choice[pos][prev];
    
    for(int curr=0; curr<m; curr++){
        double prob = (pos==0?B[curr]:T[prev][curr]);
        prob +=  M[curr][R[pos]] + select(pos+1, curr);
        if(ret<prob){
            ret = prob;
            cho = curr;
        }
    }
    return ret;
}

void print_output(int len){
    int prev = 0;
    for(int pos=0; pos<len; pos++){
        int curr = choice[pos][prev];
        cout<<dict[curr]<<' ';
        prev = curr;
    }
    cout<<'\n';
}