동시출현빈도 제대로 계산하기!

동시출현(Co-occurrence)은 두 단어(키워드)가 얼마나 같은 문헌에 자주 등장했는지에 대한 개념으로, 단어 간의 연관관계를 따지는데 가장 기초적이면서도 중추적인 역할을 수행합니다. 기초적이지만 중요한 개념이라고 할 수 있죠.

동시출현 빈도를 세는 작업은 의외로 간단합니다.

1. A, B, C

2. A, D, C

3. B, D, E

문헌 1, 2, 3에 단어 A, B, C, D, E가 다음과 같이 분포한다고 할때 단어 A, C는 문헌 1에도 함께 등장하고, 2에도 함께 등장하므로 동시출현 빈도는 2라고 간단하게 셀 수 있습니다. 따라서 이를 프로그래밍하는 것도 비교적 간단한 편이기에 코딩 연습 문제로 자주 나오는 편이기도 하죠. 어느 정도 코딩을 하신 분이라면 머리속에서 동시출현 빈도를 카운트하는 코드가 대략적으로 그려지실 수도 있습니다. 굉장히 간단해 보이는 코드지만, 이 코드가 수 백만건의 문헌들에 대해서 작동하도록 하는것은 의외로 간단하지 않습니다. 이번 포스팅에서는 동시출현 빈도를 잘! 계산하는 긴 여정에 대해 다뤄보도록 하겠습니다.

문제 정의

하나의 텍스트 파일이 있고, 한 줄에 한 문헌씩 데이터가 들어갑니다. 한 문헌 내의 단어들은 띄어쓰기로 구분되어 있습니다. 이 때 등장하는 단어들의 동시출현 빈도를 세는 것이 우리의 목표입니다. 쉽죠?

<데이터 예시>

link key figur internet busi news person manag inform order

evalu mine tool appli select scientif engin literatur paper address approach

7th intern confer extend databas technolog proceed contain paper special focu confer index

...

가장 간단한 풀이

Python으로 간단하게 다음과 같이 코드를 구현해볼 수 있습니다.

count = {} #동시출현 빈도가 저장될 dict for line in open('input.txt'): words = line.split() #한줄씩 읽어와서 단어별로 분리 for i, a in enumerate(words): for b in words[i+1:]: if a == b: continue #같은 단어의 경우는 세지 않음 if a > b: a, b = b, a #A, B와 B, A가 다르게 세어지는것을 막기 위해 항상 a < b로 순서 고정 count[a, b] = count.get((a, b), 0) + 1 #실제로 센다

설명할 것 없을 정도로 간단한 코드지요. 이 코드의 가장 큰 문제점은 뭘까요? 정답은 한 줄에 같은 단어가 여러개 등장할 경우 잘못되게 빈도를 계산한다는 것입니다. 예를 들어 한 문헌에 A, A, A, B, B 단어가 등장한다고 하면 총 (A, B) 쌍이 3*2번 등장하므로 이 코드는 (A, B)쌍의 동시출현 빈도를 6증가시킬것입니다. 실제로는 한 문헌에 같이 등장한 것이므로 1증가시키는게 맞겠죠.

따라서 이 문제를 해결하기 위해서는 먼저 한 문헌에 등장하는 단어들을 set에 넣어서 중복을 제거하고, 그 뒤 빈도 분석을 하는게 맞겠습니다.

count = {} #동시출현 빈도가 저장될 dict for line in open('input.txt'): words = list(set(line.split())) #단어별로 분리한 것을 set에 넣어 중복 제거하고, 다시 list로 변경 for i, a in enumerate(words): for b in words[i+1:]: if a == b: continue #같은 단어의 경우는 세지 않음 if a > b: a, b = b, a #A, B와 B, A가 다르게 세어지는것을 막기 위해 항상 a < b로 순서 고정 count[a, b] = count.get((a, b), 0) + 1 #실제로 센다

아주 잘 작동하는 좋은 코드입니다. 깔끔하기도 하구요. 학부생용 파이썬 과제였다면 여기서 끝나도 뭐 감점은 없을것 같습니다. 하지만 만약 파일이 백만 줄 짜리라면 이 프로그램이 결과를 낼때까지 얼마나 시간이 걸릴까요? 또 얼마나 많은 메모리가 필요할까요?

최적화1: 단어ID를 부여하자

파이썬의 dict와 같은 자료구조를 구현하는데에는 흔히 해시맵이나 그와 유사한 구조를 사용합니다. 문자열을 hash하여 일정한 정수로 바꾸고 이 값을 통해서 원하는 데이터에 O(1) 에 접근하도록 하기 위해서이죠. 문제는 문자열에 대한 해시 비용이 그렇게 싸지 않다는 것입니다. 즉 count.get((a, b))로 a, b 단어의 출현횟수를 찾기 위해 매번 해시를 계산하면서 꽤나 많은 시간을 소모하게 됩니다. 또한 각각의 엔트리가 문자열쌍을 key값으로 가지고 있어야 하므로, 메모리 소모도 엄청나죠. 서로 다른 단어가 10000개 있다고 하면, 조합 가능한 단어쌍은 최대 약 50000000개(5천만...)가 되고, 이게 메모리에 올라가려면...... 안되겠죠

좋은 방법은 각각의 단어에 고유 ID를 부여해주는 것입니다. 그리고 동시출현 빈도를 셀때도 단어쌍을 가지고 출현빈도를 세는게 아니라, 단어 ID들의 쌍을 가지고 빈도를 세는 겁니다. 마지막에 결과를 보여줄때는 단어ID에서 다시 이에 해당하는 단어를 되찾아서 보여주면 되는 것이구요. 이렇게 할 경우 1. 문자열 해시 비용을 절약할 수 있고, 2. count 변수에 key로 정수 쌍만 들어가므로 메모리 사용량도 훨씬 줄일 수 있습니다.

class VocabDict: # 단어에 고유 ID를 부여해주는 클래스 def __init__(self): self.d = {} # 단어->단어ID로 변환할때 사용 self.w = [] # 단어ID->단어로 변환할 때 사용 def getIdOrAdd(self, word): # 단어가 이미 사전에 등록된 것이면 해당하는 ID를 돌려주고 if word in self.d: return self.d[word] # 그렇지 않으면 새로 사전에 등록하고 ID를 부여함 self.d[word] = len(self.d) self.w.append(word) return len(self.d) - 1 def getWord(self, id): return self.w[id] vDict = VocabDict() count = {} #동시출현 빈도가 저장될 dict for line in open('input.txt'): words = list(set(line.split())) #단어별로 분리한 것을 set에 넣어 중복 제거하고, 다시 list로 변경 wids = [vDict.getIdOrAdd(w) for w in words] for i, a in enumerate(wids): for b in wids[i+1:]: if a == b: continue #같은 단어의 경우는 세지 않음 if a > b: a, b = b, a #A, B와 B, A가 다르게 세어지는것을 막기 위해 항상 a < b로 순서 고정 count[a, b] = count.get((a, b), 0) + 1 #실제로 센다

VocabDict 클래스를 만들어서 단어ID를 관리하도록 하였습니다. 훨씬 낫네요. 그렇지만 여전히 백만 개의 문헌에서 동시출현 빈도 분석을 하기에는 버겁습니다. 한 문헌에 N개의 단어가 있다고 하면, 조합 가능한 단어쌍을 모두 조사하는데 O(N²)의 시간이 걸릴테니깐요. N이 커지면 실행시간은 기하급수적으로 증가합니다.

최적화2: 모든 단어가 필요할까?

곰곰히 생각해보면 동시출현빈도를 보는데 모든 단어가 필요하지는 않습니다. 이 분석의 목표는 함께 자주 등장하는 단어 쌍을 찾는 것이지, 어쩌다 1, 2번 같이 등장한 단어쌍을 찾는게 아니거든요. 흔히 5나 10회 등 특정한 기준치를 잡아서 그 이상 함께 등장한 단어를 봅니다. 그러면 어차피 버려질 1~2번 같이 등장한 단어쌍은 애초에 무시하고 넘어가면 안될까요..? 하지만 그런 방법이 있을리가요

단어의 분포는 흔히 지프의 법칙(Zipf's Law)을 따른다고 알려져 있습니다. 이 법칙은 우리가 사용하는 텍스트의 대부분은 소수의 고빈도 어휘가 차지하고 있고, 나머지 어휘들은 매우 조금씩 사용된다고 주장합니다. NLP 세계의 80:20의 법칙 같은것이죠. 뜬금없이 이 얘기를 꺼낸것은 매우 조금씩 사용되는 어휘가 굉장히 많다는 것을 상기시키기 위해서입니다. 애초에 등장횟수가 10회가 안되는 소수 어휘들은 어차피 동시출현빈도가 10회가 넘을수가 없습니다. 그런데 지프의 법칙에 따르면 이렇게 조금씩 사용되는 어휘가 굉장히 많아요!!!

먼저 각 단어의 출현 빈도를 세어서 그 빈도가 T회 미만이 되는 단어들은 버립니다. 그리고 그 이상 등장하는 단어들에 대해서만 다시 동시출현 빈도를 계산하는 식으로 전략을 바꿀수 있겠습니다. (실제 사례로 약 1700개의 문헌에 서로 다른 단어가 24000여개가 있었는데, 이중 10회 이상 등장하는 단어는 2000여개였습니다.)

이렇게 어차피 버려질 단어를 사전에 버리면 N의 개수를 크게 줄일수 있으므로 조합가능한 단어쌍을 찾는데 필요한 시간인 O(N²)은 더 크게 줄어듭니다. 그 대신 번거로운 점이 하나 있다면, 전체 텍스트 파일을 2번 훑어야 한다는 것이죠.

class VocabDict: # 단어에 고유 ID를 부여해주는 클래스 def __init__(self): self.d = {} # 단어->단어ID로 변환할때 사용 self.w = [] # 단어ID->단어로 변환할 때 사용 def getIdOrAdd(self, word): # 단어가 이미 사전에 등록된 것이면 해당하는 ID를 돌려주고 if word in self.d: return self.d[word] # 그렇지 않으면 새로 사전에 등록하고 ID를 부여함 self.d[word] = len(self.d) self.w.append(word) return len(self.d) - 1 def getId(self, word): # 단어가 사전에 등록되어있는 경우 ID를 돌려주고 if word in self.d: return self.d[word] # 그렇지 않은 경우 -1을 돌려줌 return -1 def getWord(self, id): return self.w[id] vDict = VocabDict() vDictFiltered = VocabDict() wcount = {} # 단어별 빈도가 저장될 dict # 파일을 훑으며 단어별 빈도를 계산함 for line in open('input.txt'): words = list(set(line.split())) for w in words: wid = vDict.getIdOrAdd(w) wcount[wid] += wcount.get(wid, 0) + 1 for wid, num in wcount.items(): if num < 10: continue # 10회 이상 등장한 것들만 vDictFiltered에 저장함 vDictFiltered.getIdOrAdd(vDict.getWord(wid)) vDict = None # vDict에 할당된 메모리 반납 count = {} #동시출현 빈도가 저장될 dict # 파일을 다시 훑으며 동시출현빈도를 계산함 for line in open('input.txt'): words = list(set(line.split())) #단어별로 분리한 것을 set에 넣어 중복 제거하고, 다시 list로 변경 #vDictFiltered에 포함된 단어들에 대해서만 wid를 구함 wids = list(filter(lambda wid : wid>=0, [vDictFiltered.getId(w) for w in words])) for i, a in enumerate(wids): for b in wids[i+1:]: if a == b: continue #같은 단어의 경우는 세지 않음 if a > b: a, b = b, a #A, B와 B, A가 다르게 세어지는것을 막기 위해 항상 a < b로 순서 고정 count[a, b] = count.get((a, b), 0) + 1 #실제로 센다

짜잔! 조금 길어졌지만, 속도는 훨씬 빨라졌습니다. 조금 더 성능을 높일수 있는 방법은 count를 dict 자료구조 말고 2차원 배열로 바꾸는 것입니다. 필터링하여 필요없는 단어를 사전에 쳐냄으로써 전체 단어 개수가 눈에 띄게 줄었으므로, (단어개수 * 단어개수)의 행렬로 각 단어쌍의 동시출현 빈도를 저장할 수가 있습니다. 해시맵이 아무리 빨라도 배열보다 빠를순 없겠죠?

최적화3: 놀고 있는 코어를 활용하자!

마지막으로 좀더 성능을 끌어올릴수 있는 방법은 멀티 스레딩을 하는 것입니다. 특히 작업할 데이터를 파일로부터 읽어와야하기 때문에 단일 스레드 프로그램에서는 IO 지연을 숨길 방법이 없습니다. 멀티 스레딩을 통해 한쪽에서는 디스크로부터 파일을 읽어오고, 나머지 스레드들은 이를 동시다발적으로 분석하면 좀더 빠르게 처리가 가능하겠죠! 빈도 카운팅에서는 count 배열에 lock을 걸거나 atomic_add를 실행하는 것보다는 각자 스레드가 자신만의 count 배열을 가지게하고, 여기에 카운팅 결과를 보관한 다음 모든 처리가 끝나면 이를 합쳐서 전체 빈도를 구하는 것이 좋습니다.

사실 파이썬은 GIL 문제 때문에 멀티스레딩으로 얻을수 있는 성능이 적기 때문에 이 최적화 구현은 파이썬으로 하지 않았습니다. 그 대신 C++로 구현하여 바이너리로 만들었는데요, https://github.com/bab2min/CooccurrenceCounter/blob/master/CooccurrenceCounter.cpp 에서 코드 확인가능합니다. 실행 파일은 https://github.com/bab2min/CooccurrenceCounter/releases/tag/0.1 에서 다운 가능하구요.

사실 이 포스팅은 제가 동시출현 빈도 코드를 고치면서 거쳐온 과정을 나열한 것입니다... 처음 구현했을때는 제일 위에 제시한 코드와 비슷한 모양으로 Java로 구현했었는데, 1GB가 약간 안되는 텍스트 파일을 분석하는데 64GB RAM을 먹으면서 3일이나 걸렸지만 결국 결과를 내지 못하고 죽어버렸습니다. 화가 나서 최적화를 차례로 거친 뒤 최종적으로 c++로 구현하여 돌리니 10분도 안걸려서 결과가 나왔네요...! 진작 이렇게 할걸 그랬습니다.