[Swift]Random Surfer Trick 구현

구글의 검색엔진이 어떻게 세계 최강의 자리에 단시간에 오를 수 있었을까?? 존 매코믹은 "미래를 바꾼 아홉 가지 알고리즘"에서 그 이유 중 하나로 "Page Rank" 알고리즘을 꼽는다. 

 

초창기 구글은 검색엔진을 사용하는 사용자에게 유용한 정보를 제공하기 위해, 두 가지 큰 절차를 따랐다. 첫 번째로 인덱싱이고 두 번째가 페이지 랭크이다.

인덱싱은 페이지에 포함되어 있는 단어들(HTML을 구성하는 텍스트들)의 페이지별 위치를 구성하는 기술이고, 페이지 랭크는 사용자가 입력한 내용이 포함된 페이지들 중에 어떤 페이지를 우선적으로 보여줄 것인지(높은 순위로 매길지)에 대한 기술이다. 

 

이번 포스팅에서는 Page Rank의 다양한 알고리즘 중에서 Random Surfer Trick을 구현해 보려고 한다. Random Surfer Trick은 단순히 참조되는 페이지의 수(Hyperlink Trick)는 물론이고, 참조하는 페이지의 영향력(Authority Trick)까지 고려한 알고리즘이다. 

Random Surfer Trick은 연결된 페이지를 순회하며 각 페이지에 참조되는 횟수를 저장하는 것은 Hyperlink Trick과 동일하지만 핵심은 일정 확률에 따라 무작위로 다른 페이지를 참조할 수 있다는 것이 핵심이다. 

 

책에서 소개한 예제를 인용하자면, 16개의 페이지가 아래와 같이 다른 페이지를 참조할 때(아래 그림의 화살표로 표현), Random Surfer Trick을 이용하여 페이지별 참조 횟수를 구할 수 있다(각 회색 사각형의 숫자). 그리고 이 횟수의 내림차순이 각 페이지의 순위가 된다. 

이 번 포스팅을 통해 책에서 말한 대로 알고리즘을 구현하면, 실제로 페이지 별로 순위가 잘 매겨지는지 확인해 보고자 한다. 

먼저 클래스 다이어그램을 살펴보자. 

프로퍼티는 총 세 개로 구성된다. WWW 상의 페이지들은 각각 고유의 URL이 있으므로 해당 값에 대응되는 urlString을 이용하여 페이지들을 구분할 것이고, 해당 페이지가 참조하는 페이지의 목록을 outComingPages를 통해 정의하였다. 마지막으로 각 페이지들의 순위를 나타내는 referedCount값을 정의하였다. 

 

메서드는 인스턴스를 생성하는 init을 포함하여 해당 페이지가 참조하는 페이지를 설정할 수 있는 setOutcomingPages와 실제로 randomSurferTrick 구현하는 randomSurferTrickSimulator, 그리고 randomSurferTrick의 무작위 참조 확률을 정할 isPossible로 구성되어 있다. 

 

Swift를 이용해 이를 실제로 구현해 보자. 먼저 프로젝트를 생성하고, 가장 먼저 Queue를 이용하기 위해, 지난 포스팅(https://taeminator1.tistory.com/38)에서 해본 것처럼 DataStrucutre.framework를 import 해주었다. 그리고 다음과 같이 import문을 이용해 해당 프레임워크를 사용하였다. 

import Foundation
import DataStructure

class Page
{
    var urlString: String
    var outcomingPages: [Page] = []
    var referedCount: Int = 0                   // for Random Surfer Trick
    
    init(_ urlString: String) {
        self.urlString = urlString
    }
}

 

Page 인스턴스를 생성할 때, 참조하는 페이지를 빈 배열로 초기화해주었다. 이는 실행 전에 아래와 같이 setOutcomingpages 메서드를 통해 참조하는 페이지를 설정해 줄 것이다. 

extension Page
{
    func setOutcomingPages(_ pages: Page...) {
        for page in pages {
            outcomingPages.append(page)
            page.authority += self.authority
            page.incomingPagesCount += 1
        }
    }
}

 

다음은 isPossible 함수를 구현할 텐데, 인스턴스와 관련 없는 함수이므로 static으로 선언하여 클래스를 통해 접근하도록 설정해 주었다. 

extension Page {
    static func isPossible(_ possiblity: Int) -> Bool? {
        if possiblity < 0 || possiblity > 100 {
            print("possiblity is out of range")
            return nil
        }
        return Int.random(in: 1 ... 100) <= possiblity
    }
}

매개변수 possiblity로 0부터 100까지의 정수를 입력하면 각각 0% ~ 100%의 확률로 true를 반환하도록 하였다. 

 

마지막으로 가장 중요한 randomSurferTrickSimulator 메서드를 살펴보자. 시뮬레이터를 돌리기 전에 시작 페이지를 설정해야 하는데, 해당 페이지는 함수를 호출하는 인스턴스로 해주면 되므로 생략하였다. 그리고 현재 페이지 위치에서 참조하는 페이지를 Queue에 넣어 너비 우선 방식으로 순회하였다. 

실제로 무작위 이동하는 부분과 참조하는 페이지로 이동하는 부분은 while문에서 이루어진다. 매개변수로 입력받은 surfPossiblity를 통해 무작위로 이동할지 참조하는 페이지로 이동할지가 결정된다. 해당 반복문은 Queue에 원소가 없거나, 특정 횟수만큼 반복된다. 

extension Page
{
    func randomSurferTrickSimulator(_ pages: [Page], surfPossiblity: Int = 100, repeatNumber: Int) {
        let pagesCount: Int = pages.count
        let pageQueue: Queue = Queue<Page>(Node(self))
        self.referedCount += 1
        var repeatCount: Int = 1
        
        loop: while repeatCount < repeatNumber && !pageQueue.isEmpty() {
            let popedPage: Page = pageQueue.pop()!.getData()
            
            if Page.isPossible(surfPossiblity)! {                   // Random Surfer
                var tmpPage: Page = pages[Int.random(in: 0 ..< pagesCount)]
                var isLinked: Bool = true
                while isLinked {
                    isLinked = false
                    if popedPage.urlString == tmpPage.urlString {   // 현재 페이지를 다시 선택하지 않도록
                        isLinked = true
                        tmpPage = pages[Int.random(in: 0 ..< pagesCount)]
                        continue
                    }

                    for p in popedPage.outcomingPages {             // 현재 페이지가 참조하는 페이지를 선택하지 않도록
                        if p.urlString == tmpPage.urlString {
                            isLinked = true
                            tmpPage = pages[Int.random(in: 0 ..< pagesCount)]
                            break
                        }
                    }
                }
                pageQueue.append(Node(tmpPage))
                tmpPage.referedCount += 1
                repeatCount += 1
                if repeatCount == repeatNumber { break loop }
                continue
            }
            else {
                for page in popedPage.outcomingPages {
                    pageQueue.append(Node(page))
                    page.referedCount += 1
                    repeatCount += 1
                    if repeatCount == repeatNumber { break loop }
                }
            }
        }
    }
}

 

이제 실제로 잘 동작하는지 확인해 볼 차례다. 앞서 설명한 예제대로 구현하기 위해, p0~p15의 16개 페이지를 선언하였고, setOutcomingpages를 통해 참조하는 페이지를 설정해 주었다. 

그리고 아래와 같이 나서 함수를 실행할 인스턴스와, surfPossiblity, repeatNumber를 결정하여 실행해주면 된다. 

실행 결과는 다음 포스팅에서 살펴보겠다.