티스토리 뷰
마르코프 체인은 이미 자연어 처리와 관련된 분야에서는 한물간(?) 취급을 받고 있는 알고리즘인 것 같습니다. 그러나 관련 분야 전문가가 아닌 저와 같은 사람이 코딩을 통해 문장을 생성하는 가장 직관적이고 쉬운 알고리즘이라는 생각이 듭니다.
위 그림은 마르코프 체인을 설명할 때 가장 많이 볼 수 있는 그림인데 알파벳은 상태를, 화살표는 상태의 시간적 흐름을 숫자는 상태 전이가 일어날 확률을 보여주고 있습니다. 쉽게 말해 A 에서 B 가 될 확률은 0.5, 그 반대는 0.8 이라는 것이죠.
이것을 통해서 무엇을 할 수 있을까요? 어떤 상태의 패턴을 추론할 수 있습니다. 가령 날씨를 예로 들자면 '흐림 > 비 > 맑음 > 흐림 > 비 > 맑음' 과 같은 패턴을 가지고 있다면 이 데이터를 통해 각각의 날씨에서 다른 날씨로 바뀔 확률을 계산할 수 있을 것이고 다음날의 날씨를 예측할 수 있을 것입니다. 물론 이는 완벽하게 다음 상태를 추론해 주지는 못합니다. 그저 지난 패턴을 바탕으로 확률적으로 높은 결과를 불완전하게 추론해 낼 수 있을 뿐이지요.
그러나 이 알고리즘을 통해 간단한 더미 문장을 만들어내는 것 정도는 충분히 할 수 있습니다.
문장생성기
입력받은 대량의 텍스트 데이터들을 특정 단위(형태소, 단어)로 잘라서 그 패턴을 통해 확률을 계산한다면 어떨까요? 위 그림에서 원 안에 표시된 알파벳이 형태소또는 단어가 되고 거기서 다른 형태소 혹은 단어로 이어질 확률이 자연스럽게 구해질 것입니다.
이렇게 구해진 확률을 바탕으로 다음에 올 단어 혹은 형태소를 쉽게 추론할 수 있고 이 과정을 자동화 시키면 쉽게 문장 생성기를 만들 수 있을 것입니다.
제대로 된 문장 생성기를 만들기 위해서는 형태소 분석에서부터 복잡한 과정을 제법 거쳐야 하겠지만 저는 상용화 목적의 프로그램을 만드는 것은 아니기 때문엑 간단하게 공백 단위로 단어를 분리해서 사용하도록 하겠습니다.
private Map<String, List<String>> createDictionary(String input) {
String[] words = input.split(BLANK);
Map<String, List<String>> dictionary = new HashMap<>();
for (int i = 0; i < words.length - KEY_SIZE; i++) {
String key = getKey(words, i);
String value = words[i + KEY_SIZE];
if (isEndOfSentence(key)) {
i += KEY_SIZE - 1;
continue;
}
if (dictionary.containsKey(key)) {
dictionary.get(key).add(value);
continue;
}
List<String> values = new ArrayList<>();
values.add(value);
dictionary.put(key, values);
}
return dictionary;
}
위 코드는 문장생성기의 핵심이 되는 dictionary 생성 메소드입니다. dictionary는 위에서 설명한 다음에 위치할 단어를 결정하는 확률을 나타낸다고 볼 수 있습니다.
코드에서 KEY_SIZE 는 확률을 검색할 단위를 나타내고 저는 공백에 의해 분리된 각 단어를 하나의 단위로 삼았기 때문에 KEY_SIZE가 다나태는 것은 단어의 개수가 될 것입니다.
이렇게 완성된 dictionary 를 이용해 문장을 생성하는 코드는 다음과 같습니다.
private String createRandomSentence(List<String> prefixes, Map<String, List<String>> dictionary) {
String prefix = prefixes.get(random.nextInt(prefixes.size()));
StringBuilder output = new StringBuilder(prefix);
for (int i = 0; i < OUTPUT_MAXIMUM_WORDS_SIZE; i++) {
List<String> nextList = dictionary.get(prefix);
if (isLastWord(nextList)) {
break;
}
output.append(BLANK);
int next = random.nextInt(nextList.size());
output.append(nextList.get(next));
prefix = getNextPrefix(prefix, nextList.get(next));
}
return output.toString();
}
문장의 처음에 쓸 단어를 골라주고 dictionary에 저장된 다음 단어들을 가져와서 문장을 이어 나갑니다. 이제 실제로 이 코드를 통해 문장을 생성해 보도록 하겠습니다.
결과
제가 좋아하는 작사가가 쓴 가사 몇 곡을 입력하고 문장을 생성해 본 결과입니다. 입력된 자료의 크기가 적다보니 키 사이즈를 늘리면 문장을 똑같이 베껴 쓰는 문제가 있어서 부득이 키 사이즈를 1로 두고 문장을 생성했습니다.
신발장에 제일 예쁜 걸
고르다가 오늘도 같은 걸
예쁠 이유가 모자라서
나의 사진 처량해
그 얼굴이 내게 다 주고 가요
날 보낸다고
말도 안 되는 그 흐르던 멜로디
여전히 듣고 있기를
이 빛 고마워 누구든
여보세요
딱 알맞게 사랑하지 않았었나봐
나는 좀 덜 사랑해서 널 못 보내 가슴이 너무 좁아
떠나간 너의 행복 빌어줄 그런 사랑
이제 알 것 같아
나만 무너진 건가
고작 사랑 메말라 갈라질 때까지 다 가져가 버리지 그랬어요
그 추억 돌아올지도 모를 그 까짓게 뭐라고
한 사람 솔직히 견디기 버거워
니가 조금 더 그리워진다
모두 내 눈을 잘 볼 거야
또렷하게 보겠어
나와의 거리를
나의 다음 사람은
훨씬 멋있다고 해
분위기 있다고 해
가끔 스친 내 하루와 닮았어
내 방안에는 깔끔히 정리된 외로움만이
무표정한 양치질 위에
입가에 하얀 거품이 예쁜데
닦아버리면 또다시 무표정한 사람아
내 모든 걸 아예 다 아니까
그 알량한 자존심 때문에
너무 잘 사는 줄 다 가져가 버리지 그랬어요
그 추억 돌아올지도 모를 그 흐르던 멜로디
여전히 듣고 있기를
이 빛 고마워 누구든
여보세요
입력한 데이터의 크기도 작은데다가 키 사이즈를 한 단어 단위로 하다보니 아무래도 어색한 문장이 많이 나옵니다. 또 전 문장과 다음문장이 자연스럽게
'algorithm' 카테고리의 다른 글
DP on Strings 문자열 문제에서의 동적계획법 (0) | 2020.01.25 |
---|---|
이분탐색(binary search) (4) | 2019.06.29 |
힙 정렬(Heapsort) (0) | 2019.06.20 |
서울에서 경산까지 (0) | 2019.05.22 |
카드게임 문제 (1) | 2019.05.15 |
- Total
- Today
- Yesterday
- 경고
- 로그
- 자바스크립트개론
- DP
- 디자인패턴
- 문장 생성기
- Markov
- 크롬
- 동적계획법
- 마르코프
- Spring in Action
- 유지보수
- was
- markov chain
- 코딩의 기술
- html
- REST API
- 클린코드
- Warning
- Count
- 몰라서망신
- 마르코프 연쇄
- CONVENTIONS
- GROUP BY
- restful api
- RESTful
- 야근
- 자바스크립트 개론
- java
- 전략패턴
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |