자연어 처리하기: 너비우선탐색

어떤 페이지에서 시작해 목표 페이지에 도달하는 링크 체인을 찾는 문제는 첫 번째 단어와 마지막 단어가 정해진 상태에서 마르코프 체인을 찾는 것과 마찬가지입니다. 이런 종류의 문제를 방향성 그래프 문제라고 부릅니다. 방향성 그래프에서 가장 짧은 경로를 찾을 때 가장 좋고 가장 널리 쓰이는 방법은 너비 우선 탐색입니다.

너비 우선 탐색에서는 우선 시작 페이지에서 출발하는 링크를 모두 검색합니다. 검색한 링크에 목표 페이지가 들어 있지 않으면 2단계 링크, 즉 시작 페이지에서 링크된 페이지에서 다시 링크된 페이지를 찾습니다. 링크 단계 제한(여기서는 6)에 걸리거나, 목표 페이지를 찾을 때까지 이를 반복합니다.

import pymysql

conn = pymysql.connect(host = '127.0.0.1', user = 'root', passwd = '', db = 'mysql', charset = 'utf-8')
cur = conn.cursor()
cur.execute('USE wikipedia')

def getUrl(pageId):
    cur.execute('SELECT url FROM pages WHERE id = %s', (int(pageId)))
    return cur.fetchone()[0]

def getLinks(fromPageId):
    fromId = int(fromPageId)
    cur.execute('SELECT toPageId FROM links WHERE fromPageId = %s', (fromId))
    if cur.rowcount = 0:
        return []
    return [x[0] for x in cur.fetchall()]

def searchBreadth(targetPageId, path=[[1]]):
    newPaths = []
    for path in paths:
        links = getLinks(path[-1])
        for link in links:
            if link == targetPageId:
                return path + [link]
            else:
                newPaths.append(path+[link])
    return searchBreadth(targetPageId, newPaths)

nodes = getLinks(1)
targetPageId = 18088
pageIds = searchBreadth(targetPageId)
for pageId in pageIds:
    print(getUrl(pageId))