임의의 character vector에 대해 가장 긴 common string을 구해주는 함수를 만들어 보고자 한다. 다음과 같은 방법으로 풀어보았다.
allsubstr=function(x){
res=c()
for(i in 1:nchar(x)) res=c(res,unique(substring(x, i, i:nchar(x))))
res
}
allsubstr("나는 행복합니다.") [1] "나" "나는" "나는 "
[4] "나는 행" "나는 행복" "나는 행복합"
[7] "나는 행복합니" "나는 행복합니다" "나는 행복합니다."
[10] "는" "는 " "는 행"
[13] "는 행복" "는 행복합" "는 행복합니"
[16] "는 행복합니다" "는 행복합니다." " "
[19] " 행" " 행복" " 행복합"
[22] " 행복합니" " 행복합니다" " 행복합니다."
[25] "행" "행복" "행복합"
[28] "행복합니" "행복합니다" "행복합니다."
[31] "복" "복합" "복합니"
[34] "복합니다" "복합니다." "합"
[37] "합니" "합니다" "합니다."
[40] "니" "니다" "니다."
[43] "다" "다." "." myLCS_sub=function(a,b){
result=intersect(allsubstr(a),allsubstr(b))
if(length(result)==0) return(NULL)
result[which.max(nchar(result))]
}
myLCS_sub("나는 행복합니다.","너도 행복하니?")[1] " 행복"myLCS=function(x){
Reduce(myLCS_sub,x)
}
x=c("나는 행복합니다.","너도 행복하니?","행복한 세상")
myLCS(x)[1] "행복"allsubstr() 함수의 for loop를 없애기위해 다음과 같이 sapply함수를 써서 만들어 보았다.
allsubstr1=function(x){
unlist(sapply(seq_len(nchar(x)), function(i) unique(substring(x, i, i:nchar(x)))))
}
myLCS_sub1=function(a,b){
result=intersect(allsubstr1(a),allsubstr1(b))
if(length(result)==0) return(NULL)
result[which.max(nchar(result))]
}
myLCS1=function(x){
Reduce(myLCS_sub1,x)
}
myLCS1(x)[1] "행복"두 개의 함수의 성능을 비교하기 위해 다음과 같이 10000개의 원소를 갖는 character vector를 만들고 성능을 비교해 보았다.
x=paste0(1:10000,"행복",10000:1)
length(x)[1] 10000system.time(myLCS(x)) user system elapsed
2.197 0.018 2.219 system.time(myLCS1(x)) user system elapsed
2.432 0.009 2.442 10000개의 원소를 갖는 string vector를 가지고 성능을 비교해본 결과 for loop를 사용한 myLCS()함수의 성능이 더 좋았다.
하지만 이 함수는 개선할 점이 있다. 두개의 string의 모든 가능한 substring을 다 만들어 비교할 것이 아니고 두 개의 string 중 짧은 길이의 string의 길이를 알아내 그 길이 이하의 길이를 갖는 substring만 비교하면 될 것이다. 예를 들어 “행복”과 “나는 행복합니다.”를 비교할 때 “나는 행복합니다.”의 모든 substring을 만들어 비교하는 것이 아니라 “행복”의 문자길이(nchar)가 2이므로 2이상의 길이를 갖는 substring은 비교할 필요가 없다. 따라서 최대 길이 max이하의 substring만을 만들어 주는 함수를 만드는데 max를 입력하지 않으면 string의 길이를 사용하게 만든다.
allsubstr2=function(x,max=NULL){
res=c()
if(is.null(max)) max=nchar(x)
for(i in 1:max) res=c(res,unique(substring(x, 1:(nchar(x)-i+1),i:nchar(x))))
res
}
allsubstr2("행복한 세상") [1] "행" "복" "한" " " "세"
[6] "상" "행복" "복한" "한 " " 세"
[11] "세상" "행복한" "복한 " "한 세" " 세상"
[16] "행복한 " "복한 세" "한 세상" "행복한 세" "복한 세상"
[21] "행복한 세상"allsubstr2("행복한 세상",2) [1] "행" "복" "한" " " "세" "상" "행복" "복한" "한 " " 세"
[11] "세상"이 함수를 이용한 LCS함수를 만들면 다음과 같다.
myLCS_sub2=function(a,b){
n=min(nchar(a),nchar(b))
result=intersect(allsubstr2(a,n),allsubstr2(b,n))
if(length(result)==0) return(NULL)
result[which.max(nchar(result))]
}
myLCS2=function(x){
Reduce(myLCS_sub2,x)
}이 함수를 이용하여 성능을 비교해보면 다음과 같다.
system.time(myLCS(x)) user system elapsed
2.172 0.008 2.182 system.time(myLCS2(x)) user system elapsed
0.930 0.004 0.934 새로 만든 함수가 첫번째 함수에 비해 수행속도가 절반이하로 줄어든 것을 알 수 있다.
함수의 소스를 공개하는 이유는 내가 사용한 방법이 최선의 방법이 아닐수 있다고 생각하기 때문이다. 누구든지 이 함수를 개선하여 myLCS2()함수보다 빠른 속도를 보인다면 감사의 뜻으로 내가 쓴 책을 한권을 보내드릴테니 여러 가지 방법으로 시도해보시기 바란다.