단순 결합 질의(simple conjunctive query)

이번 포스팅에선 불린 검색 모델(Boolean Retrieval Model)의 기본인 단순 결합 질의(simple conjunctive query)를 파이썬으로 구현하는 걸 살펴보도록 하겠습니다. 이 글의 알고리즘은 Introduction to Information Retrieval(Manning, C. D. et al., 안동언 외 옮김)을 바탕으로 하되 코드는 제가 직접 작성했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

풀려는 문제

풀려는 문제는 다음과 같습니다. 예컨대 영화 리뷰 말뭉치에서 ‘영화’, ‘재미’, ‘깨알’ 세 단어가 동시에 사용된 문서를 찾고 싶은 겁니다. 이 때 세 단어들은 질의(query)가 됩니다. 우선 왓챠에서 72만2813건의 문서를 수집했고, 리뷰 하나가 하나의 행이 되도록 csv파일로 저장해뒀습니다. 이를 파이썬으로 읽어들이는 코드는 다음과 같습니다.

import pandas as pd
corpus = pd.read_table('review.csv', sep=',')

단어-문서 색인

영화 리뷰 말뭉치에 있는 단어와 문서를 다음과 같이 색인합니다. 우리가 필요한 정보는 특정 단어가 전체 문서집합 가운데 몇 건의 문서에 등장했는지(document frequency), 그리고 등장한 문서의 ID 집합(postings list)입니다.

위와 같이 색인하는 코드는 다음과 같습니다.

def make_index(corpus):
    # corpus 형태 : document로 이뤄진 list
    from collections import defaultdict

    # split docs and words
    docs = [doc.split() for doc in corpus 
            if isinstance(doc, str)]
    words = sorted(list(set(flatten(docs))))

    # indexing
    term_doc = defaultdict(list)
    for doc_idx, words in enumerate(docs):
        for word in words:
            term_doc[word].append(doc_idx)
    term_docfreq = {}
    term_post = {}
    for word, value in zip(term_doc.keys(),
                           term_doc.values()):
        term_docfreq[word] = len(value)
        term_post[word] = list(set(value))
    return term_docfreq, term_post

def flatten(x):
    result = []
    for el in x:
        if isinstance(el, list):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

포스팅 목록 비교 함수

‘영화’라는 단어가 등장한 문서의 ID는 다음과 같다고 칩시다. 이 아이디는 term_post로부터 구할 수 있습니다.

2, 4, 7, 8, 11

‘재미’는 다음과 같다고 합니다.

7, 368, 383, 434, 1049

우선 ‘영화’ 목록의 첫번째 포인터가 가리키는 2와 ‘재미’의 7을 비교합니다. 다르니까 패스합니다. 2는 7보다 작으므로 ‘영화’의 포인터를 하나 옮깁니다.

이번엔 4와 7을 비교합니다. 다르니까 또 패스합니다. 4는 7보다 작으므로 ‘영화’의 포인터를 하나 옮깁니다.

‘영화’의 7과 ‘재미’의 7이 이번엔 일치하네요. 이를 정답 리스트에 저장해놓습니다. 이런 식으로 검색해야 할 포스팅 목록이 사라질 때까지 같은 작업을 반복하는 겁니다.

코드는 다음과 같습니다.

def intersection(p1, p2):
    # 포스팅 목록 두개를 단순 비교
    # 계산복잡성은 p1 길이 + p2 길이
    p1 = sorted(p1)
    p2 = sorted(p2)
    answer = []
    while len(p1) > 0 and len(p2) > 0:
        if p1[0] is p2[0]:
            answer.append(p1[0])
            p1 = p1[1:]
            p2 = p2[1:]
        else:
            if p1[0] < p2[0]:
                p1 = p1[1:]
            else:
                p2 = p2[1:]
    return answer