이번에 살펴볼 예제는, Markov process의 원리를 이용하여 N-grams random writing을 해 보려고 합니다. 앞서 했던 word count 예제를 참고하시면 조금 더 익숙하게 작업하실 수 있을 것 같네요 :)

이번에 할 작업의 원리는 아래와 같습니다. 만약 이런 글이 있다고 가정하면,

나는 사람입니다. 나는 학생입니다. 나는 졸업합니다.

‘나는’ 이라는 단어 다음에는 세가지 말이 나올 확률이 존재하게 됩니다. 그러면 ‘나는’ 이라는 단어 다음에 우리는 ‘사람입니다.’, ‘학생입니다.’, ‘졸업합니다.’ 중의 하나를 랜덤하게 택해서 글을 쓸 수 있겠죠? 굉장히 쉬운 원리 같지만, 되게 있어보이게 들리는 Markov process라고 표현합니다. 또한 N-grams라고도 불리는데, N의 값에 따라서 seed word의 길이가 달라지게 되는 것이죠.

우리가 위에서 예를 든 것은 1-gram입니다. 3-grams이라고 하면,

우리 나라 좋은 나라. 우리 나라 좋은 경치. 우리 나라 좋은 사람.

이 경우에 3-grams는 세 개의 단어가 seed word가 되어, ‘우리 나라 좋은’이라는 말 다음에 올 가능성은 ‘나라’, ‘경치’, ‘사람’ 이렇게 세 가지 중의 하나라는 것을 이용하여 랜덤 글쓰기를 하게 됩니다.

자 이제 이것을 실제로 코드로 구현해 봅시다. 예제로 사용될 constitution.txt파일입니다.

import re
import random

f = open('constitution.txt', 'r')
wordDict = {} # 비어있는 dictionary를 만듭니다.
wordList = re.split(' +', f.read()) # 중복된 공백을 포함하여 공백들만 다 제거한 체 리스트로 받아옵니다. 결국 단어(.이나 줄바꿈 포함)들의 리스트가 되겠죠.
N = 3 # N-grams에서 N입니다.

### seed word에 따른 다음 단어들을 리스트의 형태로 추가해 줍니다.
wordList = wordList + wordList[:N]
for i in range(len(wordList)-N):
    curr_word = tuple(wordList[i:i+N])
    next_word = wordList[i+N]
    if curr_word in wordDict:
        wordDict[curr_word].append(next_word)
    else: #만약 처음 등장하는 seed word이면 새로 list를 만들어서 다음 단어 저장
        wordDict[curr_word] = [next_word]

이렇게 하면 wordDict라는 dictionary에 각 seed word에 따른 가능한 다음 단어들이 저장되어 있게 됩니다. 이제 실제로 random writing을 시작해 볼까요? 알고리즘은 간단합니다. 처음에 올 seed word를 랜덤으로 택한 후, 우리가 원하는 길이까지 계속해서 랜덤하게 출력해 나갑니다.

numWords = 200 #출력할 단어의 수
seed = random.choice(wordDict.keys()) #첫 단어는 seed words 중 랜덤하게 선택
random_writing = ' '.join(seed) #seed가 tuple 식으로 되어있기 때문에 string형태로 고쳐서 대입합니다.

### 원하는 단어 수만큼 랜덤하게 출력합니다.
for _ in range(numWords):
    random_next_word = random.choice(wordDict[seed]) #다음 단어를 랜덤하게 선택
    random_writing += " " + random_next_word #결과 string에 붙여주고,
    seed = seed[1:]+(random_next_word,) #seed word를 하나씩 밀어서 만들어준다.

>>> print random_writing
the
Day on which they shall give their Votes; which Day shall be the President, if such Number be a Majority of each shall
constitute a Quorum to do Business; but a smaller Number may adjourn
from day to day, and may be authorized to compel the Attendance of
absent Members, in such Manner, and under such Penalties as each House
may provide.

Each House may determine the Rules of its Proceedings, and from time to
time ordain and establish. The Judges, both of the United States nor any State be formed by the Junction of two or more who have equal
Votes, the Senate shall choose the
Vice-President; a quorum for this purpose shall consist of a member or members
from two-thirds of the states, and a majority of either the principal
officers of the executive Authority of the United States for delivery or use therein of
intoxicating liquors, in violation of the laws thereof, is hereby
prohibited.

Section 3.
This article shall be inoperative unless it shall have been committed, which district
shall have been previously ascertained by law, and to be informed of
the nature and cause of the accusation; to be confronted with the
witnesses against him; to have compulsory process for obtaining
witnesses in his favor, and to have the Assistance of Counsel for his
defence.

Amendment VII

In Suits

제법 그럴싸한 글이 완성되지 않았나요?? 실제로 이를 바탕으로 거짓 논문을 작성해서 journal에 accept된 사례가 있어서 N-grams의 우수성(?)을 논문으로 발표했다고 하네요 ㅋㅋ