최근에 간단한 마르코프 체인을 이용해 텍스트를 생성하는 방법을 배웠다. 생성된 텍스트는 읽을 수는 있지만 완전한 헛소리다. 산문으로서의 가치는 별로 없지만, 휴대폰 키보드의 추천어처럼 다음 단어를 예측하는 용도로는 놀랍도록 유용하다.

이 알고리즘은 Kernighan과 Pike의 책 The Practice of Programming 3장에서 배웠다. 이 책에서는 프로그램 설계와 자료구조를 논하기 위해 여러 프로그래밍 언어로 이런 생성기를 구현한다.

참고로 이 알고리즘은 훨씬 더 일반적인 통계적 개념인 마르코프 체인의 수많은 활용 중 아주 작은 하나에 불과하다.

알고리즘

알고리즘은 설명하기 쉽다. 먼저 출력 생성에 사용할 구문이 담긴 입력 텍스트부터 시작한다. 입력에 등장하는 모든 단어 쌍에 대해, 그 쌍 뒤에 올 수 있는 단어들의 목록을 기록한다.

이 자료구조를 만들어 두면 원하는 만큼 길게 혹은 짧게 출력을 생성할 수 있다. 입력에 등장하는 임의의 단어 쌍으로 시작해, 가능한 세 번째 단어 중 하나를 무작위로 고른다. 그리고 한 칸 앞으로 이동해, 방금 생성한 단어가 쌍의 두 번째 단어가 되도록 한 뒤 다시 무작위로 다음 단어를 고르는 식으로 계속한다.

그게 전부다!

이 알고리즘은 바이그램이라고도 하는 단어 쌍을 사용한다. 단어 쌍 대신 단일 단어나 트라이그램을 사용하도록 일반화할 수도 있다. 하지만 The Practice of Programming에서 지적하듯:

접두사를 짧게 만들면 일관성 없는 산문이 생성되는 경향이 있고, 길게 만들면 입력 텍스트를 그대로 복제하는 경향이 있다. 영어 텍스트의 경우, 두 단어로 세 번째 단어를 선택하는 것이 좋은 절충안이다. 입력 텍스트의 느낌을 재현하면서도 나름의 기발한 변화를 더하는 것처럼 보이기 때문이다.

예제를 하나 살펴보자. 입력이 작을 때는 작동을 위해 어느 정도 반복이 필요하므로, 입력으로는 킹 제임스 성경에 나오는 십계명 중 마지막 다섯 개를 사용하겠다:

너는 살인하지 말라.

너는 간음하지 말라.

너는 도둑질하지 말라.

너는 네 이웃에 대하여 거짓 증거하지 말라.

너는 네 이웃의 집을 탐내지 말라, 너는 네 이웃의 아내를 탐내지 말며, 그의 남종이나 여종이나 소나 나귀나 네 이웃의 소유된 그 무엇도 탐내지 말라.

“가능한 세 번째 단어” 자료구조가 어떻게 생겼는지, 왼쪽에는 단어 쌍을, 오른쪽에는 |로 구분된 가능한 단어들을 표시해 처음 몇 개 항목을 보여주면 다음과 같다:

shalt not         kill. | commit | steal. | bear | covet | covet
Thou shalt        not | not | not | not | not
nor his           manservant, | maidservant, | ox, | ass,
not covet         thy | thy
covet thy         neighbours | neighbours
thy neighbours    house, | wife,
not kill.         Thou
kill. Thou        shalt
not commit        adultery.
...

따라서 “shalt not”으로 시작하면 다음 단어로 “kill.”, “commit”, “steal.”, “bear”, “covet” 중 하나를 무작위로 선택하게 된다. 가능성 목록에 “covet”이 두 번 등장하므로, 다른 단어들보다 선택될 확률이 두 배 높다.

단어에 대문자와 문장 부호를 그대로 포함시킨 것을 볼 수 있다. 이렇게 하면 단어를 나누는 작업이 더 간단해질 뿐만 아니라, 생성된 출력이 입력에 실제로 등장했던 대문자 표기와 문장 부호를 그대로 활용해 자동으로 “문장”을 생성하게 된다. 꽤나 영리한 방법이다!

생성된 출력은 어떻게 생겼을까? 위의 십계명 입력을 사용해 시도해 보자:

너는 네 이웃에 대하여 거짓 증거하지 말라. 너는 간음하지 말라. 너는 도둑질하지 말라. 너는 네 이웃의 집을 탐내지 말라, 너는 간음하지 말라. 너는 네 이웃의 집을 탐내지 말라, 너는 도둑질하지 말라. 너는 간음하지 말라. 너는 도둑질하지 말라. 너는 네 이웃의 것을 탐내지 말라…

보다시피 이렇게 작은 입력 텍스트를 사용하면 출력이 입력 텍스트를 그대로 복사한 것이 되거나 무작위로 거의 비슷한 것이 되는 경우가 많다는 문제가 있다.

더 큰 입력 텍스트를 사용하면 훨씬 더 흥미로운 출력을 얻을 수 있다.

좀 더 나은 예시들

아래는 더 큰 입력 텍스트를 사용해 만든 좀 더 재미있는 출력 예시들이다. 각 입력마다 100단어를 생성했다. 책들은 Project Gutenberg에서 가져왔다.

내 글들을 입력으로 사용한 경우

내가 쓴 글들을 입력으로 사용한 경우:

특히 값을 반환해야 하는 경우라면, 하지만 지금은 매우 평탄해졌다 — 거의 5배 빠르다. 그래도 커스텀 예외가 필요하다면 적절할 경우 내장 예외를 사용하라. 하위 호환성은 리눅스에서만 깨뜨려라, 이것은 x86의 SSE/SIMD 명령어를 사용해 AWK로 CSV를 처리하는데, 예를 들어 NF 같은 것은 AWKGo에서 읽기 전용이다. “Pythonic”이란 무슨 뜻일까? 정말 재미있다. 내 추천은 직접 타입 안전한 OrderedMap<int>을 만들어 쓰는 것이다. 하지만 Lox 문자열은 이스케이프 시퀀스를 지원하지 않으므로, null이나 undefined가 없고, 자, 완성이다! 그 수익 중 하나에서 나온 미니멀리스트 Make는…

내 기술적 관심사 대부분이 어떻게 담겼는지 보는 게 정말 마음에 든다. 성능, 관용적인 코드, 하위 호환성, AWK, CSV, 작은 언어 등등. ChatGPT 정도는 아니지만, 눈을 가늘게 뜨고 보면 꽤 그럴듯해 보인다!

출력에 입력에 있던 유효한 Markdown까지 포함되어 있다는 점도 주목할 만하다(링크 몇 개는 삭제했다).

이상한 나라의 앨리스를 입력으로 사용한 경우

루이스 캐럴의 이상한 나라의 앨리스를 입력으로 사용한 결과다. 이 책 자체가 원래부터 어느 정도 헛소리라서, 이건 거의 제대로 작동하는 것처럼 보인다:

케이크 입구 근처에 큰 장미나무가 서 있었고, 그녀의 홍학이 급히 사라진 것을 보고 기뻐했다. “그리고 그들의 이름은 Elsie, Lacie, 그리고 Tillie였어. 그리고 그들이 내가 했다는 걸 증명할 수 없어. 부정해 봤자 소용없어. Dinah가 다음엔 나에게 심부름을 시키겠지!” 그리고 그녀는 문을 열자마자 한꺼번에 재채기를 하기 시작했다. 겨울잠쥐는 다시 눈을 감고, 연못 속에서 큰 부채 속으로 무엇이 사라지는지 보려 했다. “그리고 그녀는 손 옆에서 너무 예쁘게 가르랑거리고 앉아 있네, 제한된 교체 권리를 기다리지도 않고 서둘러 사라졌다…”

구약성경(킹 제임스 성경)을 입력으로 사용한 경우

출력에 입력의 일부였던 (엉뚱한) 구절 번호가 포함된 것에 주목하라.

바빌론 왕이 어떻게 ‘구워지는지’ 찾아보라!

베냐민, 브라갸의 아들 야아시엘, 여호야김의 아들 고모라 왕과 거룩한 신들을 향하여 네 뜻대로 하라. 22:30 남쪽 바다 현관에, 산 맞은편에서 여호와께서 그 파도를 치시리라. 107:26 그들이 올라가 그들을 매장하려 올라가니, 그들과 그들의 자녀들이 제사장에게 보이니라. 13:17 그리고 바빌론 왕이 먼지의 이름으로 구워졌더라. 18:1 그 중 하나가 대답하되, 여호수아가 취하여 사울 내 아버지의 신하들과 내 생명을 멸망에서 건지려 그 손을 덮으니라…

신약성경(킹 제임스 성경)을 입력으로 사용한 경우

신약성경 출력이 구약의 핵심 인물인 “모세”로 시작한다는 점이 좀 웃기다(하지만 그 이름은 신약에도 80번 등장한다).

내 컴퓨터도 꽤 이단적인 말을 하는 것 같다. “우리는 몸의 말씀이 사람의 뜻이라고 전파해 왔다.”

그리고 참고로 “throughly”는 (고어지만) 엄연히 존재하는 단어다.

모세여, 너희는 우리가 그들 안에 거하기를 원하도다. 2:11 그러므로 기억하라, 내 목소리로 그들을 대적하였노라. 20:20 그들이 이르되, 스스로 낮추는 자는 주리라 하지 아니하였느냐, 그가 자기 타작마당을 철저히(throughly) 청소하고 밀을 바다로 모아 양식을 얻으리라. 우리가 몸의 말씀이 사람의 뜻이라고 전파하였거니와, 그대로 되리라. 그러나 우리가 나를 위해 보냈느냐? 10:30 그리고 예수께서 하나님의 나라에 들어가셨다. 5:6 아무도 말하지 못하리니, 어리석은 자여, 그가 욥바에 가까이 이르렀고 반대편에 있었노라. 10:33 그러나 누구든지…

우주 전쟁을 입력으로 사용한 경우

그리고 하나 더, 덤으로. H. G. 웰스의 우주 전쟁을 입력으로 사용한 결과다.

할리퍼드에서 나는 더비 데이에 보이는 그 검은 모습처럼 보였다. 내 형은 하이드파크의 철문 쪽으로 방향을 틀었다. 나는 두 구의 인간 해골을 본 적이 있다 — 시신이 아니라 해골, 깨끗이 발라진 — 그리고 구덩이 속에서 — 그 남자는 도망자들을 지나쳐 멈췄지만, 도울 생각은 하지 않았다. 여관은 마치 자전거를 탄 한 남자처럼 닫혀 있었고, 아이들은 먹을 것을 찾으러 가고 있었으며, 그에게 납 망토가 될 것이라고 말했다, 그러므로. 그것은 실로 셰퍼턴을 향해 강을 마주한 집들과 다른 집들의 새벽이었다. 미친 결의가 사로잡았다…

미친 결의를 안고, 이제 이걸 구현하는 데 사용한 파이썬 코드를 살펴보자.

파이썬 구현

먼저 전체 프로그램이다. 빈 줄과 주석 포함 24줄, 제외하면 16줄이다:

import collections, random, sys, textwrap

# Build possibles table indexed by pair of prefix words (w1, w2)
w1 = w2 = ''
possibles = collections.defaultdict(list)
for line in sys.stdin:
    for word in line.split():
        possibles[w1, w2].append(word)
        w1, w2 = w2, word

# Avoid empty possibles lists at end of input
possibles[w1, w2].append('')
possibles[w2, ''].append('')

# Generate randomized output (start with a random capitalized prefix)
w1, w2 = random.choice([k for k in possibles if k[0][:1].isupper()])
output = [w1, w2]
for _ in range(int(sys.argv[1])):
    word = random.choice(possibles[w1, w2])
    output.append(word)
    w1, w2 = w2, word

# Print output wrapped to 70 columns
print(textwrap.fill(' '.join(output)))

직접 판단해 보겠지만, 나는 꽤 읽기 쉽다고 생각한다.

이 프로그램은 단어 수를 명령줄 인수(sys.argv[1])로 받고, 입력 텍스트는 표준 입력으로 받는다. 실행하려면 다음과 같은 명령을 사용하면 된다:

$ python3 markov.py 100 <AliceInWonderland.txt 
A large rose-tree stood near the entrance of the cakes, and was
...

이 코드는 GitHub Gist로도 볼 수 있다: markov.py. 이 프로그램은 그리 독창적인 것도 아니니, 원하는 대로 사용해도 좋다고 허락한다.

결론

단순한 자료구조와 난수 생성기만으로 이렇게 흥미로운 출력이 나온다는 사실이 나는 참 매력적으로 느껴진다.

기록되는 “단어”에 대문자와 문장 부호를 포함시키는 아이디어도 꽤 영리하다고 생각한다. 사실 꼼수가 아니라 프로그램을 더 단순하게 만들면서 출력까지 더 좋게 만드는 우아한 설계 선택이다. 기존 프로그램들 속에 이렇게 단순화되기를 기다리는 비슷한 설계 선택이 또 얼마나 숨어 있을지 궁금하다.

여러분도 직접 입력으로 텍스트를 생성해 보며 즐겨 보길 바란다!