1-2. 한국어 띄어쓰기 구현 - N-Gram

2-1. N-Gram(Bi-Gram)

N-Gram : 카운트에 기반한 통계적 모델, 영어는 보통 단어 단위로 자르고 한국어는 음절 단위로 자른다.

N은 자르는 개수인데, N = 1이면 UniGram 2이면 BiGram 3이면 TriGram이라고 부른다. 여기서는 BiGram으로 구현하였다. 확장된 음절 bigram을 이용한 자동 띄어쓰기시스템(강승식) 논문을 참고하여 아래처럼 8가지 상태를 측정하였다.

"가나"	"가나 "	"가 나"	"가 나 "	" 가나"	" 가나 "	" 가 나"	" 가 나 "
0	1	2	3	4	5	6	7

def save_bigram(first, second, value):
    if bigram_dict.get(first + second) is None:
        list = np.zeros(8)
    else:
        list = bigram_dict[first + second]
    list[value] = list[value] + 1
    bigram_dict[first + second] = list


def bigram(line):
    i = 0
    while i < len(line) - 2:
        j = i
        left, middle, right = False, False, False

        if line[j] == " ":
            j += 1
            left = True
        first = line[j]

        if j + 1 < len(line) - 1:
            if line[j + 1] == " ":
                j += 1
                middle = True
        else:
            break
        j += 1
        second = line[j]

        if j + 1 < len(line):
            if line[j + 1] == " " or line[j + 1] == "\n" or line[j + 1] == "\r":
                right = True
        else:
            break

        save_bigram(first, second, count_dict_value(left, middle, right))
        i += 1

이렇게 입력받은 모든 line에 대해 각 상태를 카운트해 Dictionary로 저장해둔다.
Key = 두 음절(가나) value는 위의 측정한 list(각 상태별 count)
이후 띄어쓰기를 확인할 때(Test)에는 좌측, 중앙, 우측에 공백이 있을 확률을 각각 계산해 더해준 값이 Threshold를 넘으면 띄어쓰기를 해준다. Threshold는 0.4 ~ 0.6 사이가 적당해 보이나 직접 해보고 정해야 한다.
예를 들어 "가나다라"에서 "나다" 사이에 띄어쓰기가 있을 확률("나 다"일 확률)은
우측 공백 : ("가나 " + "가 나 " + " 가나 " + " 가 나 ") * 0.25
중앙 공백 : ("나 다" + "나 다 " + " 나 다" + " 나 다 ") * 0.5
좌측 공백 : (" 다라" + " 다 라" + " 다라 " + " 다 라 ") * 0.25
곱하는 값이 다른 이유는 보통 중앙에 띄어쓰기가 있는 경우가 큰 영향을 미치기 때문이다.(논문 참고)

def freq(key, location):
    list = bigram_dict.get(key)

    if list is not None:
        total = 0
        for i in range(len(list)):
            total += list[i]
        if location == 0:
            value = get_left_freq(list)
        elif location == 1:
            value = get_middle_freq(list)
        else:
            value = get_right_freq(list)
        return value / total
    else:
        return 0

if 우측 공백 + 중앙 공백 + 좌측 공백 > Threshold
띄어쓰기하기
로 볼 수 있다.