R로 만들어본 자동 띄어쓰기 알고리즘

작성일자 글쓴이

최근 포스트들을 보자면 R 응용 책 하나에 한 챕터로 들어갈 만한 것들이 많았던거 같다.

역시 오늘 포스팅도 마찬가지 코드이다.

사실 개인적으로 띄어쓰기를 잘 못한다. 그냥 워드프로세서에 하자는 대로 그대로 따르는 편이다. 게다가 블로그도 Live Writer를 사용해서 역시 띄어쓰기 검증을 받아왔다.

오늘 만들어본 코드 조각은 최인훈의 광장과 회색인 소설을 코퍼스로 활용 띄어쓰기 알고리즘을 학습해봤다.

자동 띄어쓰기 방법은 HMM 모델을 사용했고, 아주 직관적인 인터페이스를 자랑하는 HMM 패키지를 사용했다.

일단 학습된 띄어쓰기 모델 결과는 아래와 같다.

1
2
3
4
5
6
7
8
9
10

> spacing(hmm, str)
[1] "네애비가 그렇게 열렬한 빨갱이 니깐 어렸을 때부터공산주의 의 영향을 받았을 게아냐?"
> spacing(hmm, "아이들은화롯대에장작을피우고,고구마를구워먹는다.")
[1] "아이 들은 화롯대에 장작을 피우고, 고구마를 구워먹는 다. "
> spacing(hmm, "아버지가방에들어가신다.")
[1] "아버지가 방에 들어가 신다. "
> spacing(hmm, "국회의원직을사퇴한뒤그는미국에서체류하다가대한민국에서금융사업을시작하였다.")
[1] "국회의 원직을 사퇴한 뒤그는 미국에서 체류하다가 대한 민국에서 금융사업을 시작하였다. "
> spacing(hmm, "일정한조건에따르면,자유롭게이것을재배포할수가있습니다.")
[1] "일정한 조건에 따르면, 자유롭게 이것을 재배포할 수가 있습니다. "

부분적으로 띄어쓰기가 잘 되는 것들이 있는 반면에 이상하게 판단하는 부분도 있는걸 알 수 있으나 첫 시도 치고는 기대 이상의 결과라 할 수 있다.

이 부분은 좀더 양질의 코퍼스를 넣어서 학습시키면 좋아지지 않을까 한다.

코드에 대한 개략적인 설명은 넣어 두었고 HMM 알고리즘의 경우 인터넷에 자료가 많으니 참고하면 쉽게 이해할 수 있을 거라 생각한다.

책을 쓴다면 자세한 설명이 필요하겠지만 일단 코드만 공유한다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#sentence spacing algorithm with HMM  
#setwd("C:/work/RWork/spacing")
library(HMM)
 
#문자열 코딩, 00101 
makeCorpus <- function(str){
  strv <- strsplit(str,split="")[[1]]
  lenstrv <- length(strv)
  spacev <- vector(mode="character",length=lenstrv)
  charv  <- vector(mode="character",length=lenstrv)
  vidx <- 1
  for(i in 1:lenstrv){
    if(strv[i] == " ") {
      next
    }
    if(i + 1 <= lenstrv && strv[i + 1] == " "){
      #spacev <- append(spacev, "1")
      spacev[vidx] <- "1"
    }else{
      if(i == lenstrv){
        spacev[vidx] <- "1"
      }else{
        spacev[vidx] <- "0"
      }
    }
    charv[vidx] <- strv[i]
    vidx <- vidx + 1
  }
  return(data.frame(status=spacev,char=charv))
}
 
 
#전이확률 계산 
getTransprob <- function(str){
  charv <- strsplit(str,split="")[[1]]
  status <- unique(charv)
  transMat <- matrix(0,nrow=length(status),ncol=length(status), 
                     dimnames=list(status, status))
  for(i in 1:(length(charv) -1)){
    rowidx <- which(rownames(transMat) == charv[i])
    colidx <- which(colnames(transMat) == charv[i + 1])
    transMat[rowidx, colidx] <- transMat[rowidx, colidx] + 1
  }
  prop.table(transMat,margin=1)
}
 
#관측확률 계산
observProb <- function(rawcorpus){
  statecntdf <- aggregate(rawcorpus[[1]], by=list(rawcorpus[[2]]), table)  
  statecnts <- as.data.frame(statecntdf$x)
  prob0 <- statecnts$`0`/rowSums(statecnts)
  prob1 <- statecnts$`1`/rowSums(statecnts)
  cbind(char=statecntdf[,1], statecnts, prob0, prob1)
}
 
 
# 모델을 가지고 하는 띄어쓰기
spacing <- function(hmm, str){
  strsp <- strsplit(str, split="")[[1]]
  emissions <- viterbi(hmm, strsp)
  if(length(strsp) != length(emissions)){
    stop("lengths are not match!")
  }
  strspacing <- vector(mode="character",length=length(strsp) * 2)
  spacingidx <- 1
  for(i in 1:length(emissions)){
    strspacing[spacingidx] <- strsp[i]
    if(emissions[i] == "1"){
      spacingidx <- spacingidx + 1
      strspacing[spacingidx] <- " "
    }
    spacingidx <- spacingidx + 1
  }
  return(paste(strspacing[1:spacingidx-1], collapse=""))
}
 
 
 
################ 실행 ########################################################
 
 
#코퍼스 파일 읽음 
fp <- file("choi.txt", encoding="UTF-8")
lines <- readLines(fp)
close(fp)
fullstr <- paste(lines, collapse="")
#띄어쓰기 코딩 
fullrawcorpus <- makeCorpus(fullstr)
#관측확률 계산 
oprob <- observProb(fullrawcorpus)
#전이확률 계산 
trprob <- getTransprob(paste(fullrawcorpus$status,collapse=""))
 
#HMM 모델 빌드
hmm <- initHMM(c("0", "1"), oprob$char, 
        startProbs=c(.9,.1), transProbs=trprob, emissionProbs=t(as.matrix(oprob[,c(5,6)])))
 
# 비터비 알고리즘으로 띄어 쓰기  
spacing(hmm, "일정한조건에따르면,자유롭게이것을재배포할수가있습니다.")

전이 확률은 0,1(붙여쓰기, 띄어쓰기) 기호간의 확률값을 의미하며, 관측확률은 특정 상태에서 특정 문자가 나올 확률값을 가지게 된다. 이 정도로 정리가 되었으면 모델 빌드는 다된 것이다.

이 후 HMM 모델을 이용해서 띄어쓰기 확률이 최대가 되는 최적 상태(띄어쓰기)를 찾게 된다. 잘 아시다시피 비터비 알고리즘의 경우 Dynamic Programming방식으로 빠르게 최적 패스를 찾게 된다(비터비 알고리즘의 경우 학교 다닐 때 시험문제나 알고리즘 코딩 문제로 많이 풀어본바 R의 장점인 패키지 시스템에서 찾아 썼다).

 

역시나 이런 학습 모델의 경우 코퍼스가 중요한데, 여기서 사용된 코퍼스는 저작권 문제로 공유하기는 힘드니, 테스트시 개개인이 가지고 있는 소설 파일이나 신문기사들을 사용할 수 있을 것이다.

그리고 어떤걸 사용하느냐에 따라서 퍼포먼스는 달라질 것이다.  데이터에 따라서 결과가 달라지는 것을 경험해 보길 바란다.

CC BY-NC 4.0 R로 만들어본 자동 띄어쓰기 알고리즘 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.