Markov chain(마르코프 체인)을 이용한 JAVA 문장 생성기

 

마르코프 체인은 이미 자연어 처리와 관련된 분야에서는 한물간(?) 취급을 받고 있는 알고리즘인 것 같습니다. 그러나 관련 분야 전문가가 아닌 저와 같은 사람이 코딩을 통해 문장을 생성하는 가장 직관적이고 쉬운 알고리즘이라는 생각이 듭니다. 

 

위 그림은 마르코프 체인을 설명할 때 가장 많이 볼 수 있는 그림인데 알파벳은 상태를, 화살표는 상태의 시간적 흐름을 숫자는 상태 전이가 일어날 확률을 보여주고 있습니다. 쉽게 말해 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로 두고 문장을 생성했습니다.

 

신발장에 제일 예쁜 걸
고르다가 오늘도 같은 걸
예쁠 이유가 모자라서

나의 사진 처량해
그 얼굴이 내게 다 주고 가요

날 보낸다고
말도 안 되는 그 흐르던 멜로디
여전히 듣고 있기를
이 빛 고마워 누구든
여보세요

딱 알맞게 사랑하지 않았었나봐
나는 좀 덜 사랑해서 널 못 보내 가슴이 너무 좁아
떠나간 너의 행복 빌어줄 그런 사랑
이제 알 것 같아
나만 무너진 건가

고작 사랑 메말라 갈라질 때까지 다 가져가 버리지 그랬어요
그 추억 돌아올지도 모를 그 까짓게 뭐라고
한 사람 솔직히 견디기 버거워
니가 조금 더 그리워진다

모두 내 눈을 잘 볼 거야
또렷하게 보겠어
나와의 거리를
나의 다음 사람은

훨씬 멋있다고 해
분위기 있다고 해
가끔 스친 내 하루와 닮았어
내 방안에는 깔끔히 정리된 외로움만이
무표정한 양치질 위에

입가에 하얀 거품이 예쁜데
닦아버리면 또다시 무표정한 사람아

내 모든 걸 아예 다 아니까
그 알량한 자존심 때문에
너무 잘 사는 줄 다 가져가 버리지 그랬어요
그 추억 돌아올지도 모를 그 흐르던 멜로디
여전히 듣고 있기를
이 빛 고마워 누구든
여보세요

 

입력한 데이터의 크기도 작은데다가 키 사이즈를 한 단어 단위로 하다보니 아무래도 어색한 문장이 많이 나옵니다. 또 전 문장과 다음문장이 자연스럽게