PageRank 와 구글 검색엔진

v1.0 2007/11/02 Copyleft by 전경헌@사이냅소프트

페이지랭크(PageRank)

비싼거라는데… 구구절절한 음식 설명보다는 먼저 먹어보는게 좋지 않겠나?
구글창업자중 한명인 래리페이지가 만든 페이지랭크의 정의는 아래와 같다.

그림1) 노드 A와 T1 … Tn 사이의 관계

페이지랭크는 모든 노드에 대한 확률분포를 나타낸다.
따라서 모든 노드의 페이지랭크의 합은 1이다.

예제1) 링크가 하나뿐인 구조에서의 페이지랭크

그림2) 두개의 노드 하나의 링크

계산을 위한 초기값으로 d=0.85, PR0(A)=1, PR0(B)=1를 주고 계산한다.
(왜? d값은 구글이 쓰는 값을 사용하였고, PR(A), PR(B)의 초기값은 어떤 값이어도
 같은 값으로 수렴한다. 의심나면 직접 바꿔서 해보길 바란다.)

 PR1(A) = 0.15 + 0.85 * 0 = 0.15
 PR1(B) = 0.15 + 0.85 * 1 = 1.00

 PR2(A) = 0.15 + 0.85 * 0 = 0.15
 PR2(B) = 0.15 + 0.85 * 0.15 = 0.28

 PR3(A) = 0.15 + 0.85 * 0 = 0.15
 PR3(B) = 0.15 + 0.85 * 0.15 = 0.28

더이상 값의 변화가 없이 수렴하므로,

PR(A) = 0.15 / 0.43 = 0.35
PR(B) = 0.28 / 0.43 = 0.65

예제2) 링크가 두개이며 서로 링크하는 구조에서의 페이지랭크

그림3) 두개의 노드, 두개의 링크

앞서와 같이 초기값으로 d=0.85, PR0(A)=1, PR0(B)=1를 주고 계산한다.

 PR1(A) = 0.15 + 0.85 * 1 = 1.00
 PR1(B) = 0.15 + 0.85 * 1 = 1.00

계산값이 수렴하므로,

PR(A) = 1.00/2.00 = 0.5
PR(A) = 1.00/2.00 = 0.5

검색엔진 개요

PageRank는 검색과 관련이 없는 개념이라 볼 수 있지만,
관련 될 수 도 있다. 그래서 검색부터 설명하도록 한다.

(별로 중요한 것은 아니지만…)
많은 사람들이 네이버나 다음, 엠파스를 검색엔진이라 부른다.
이를 조금 덜 모호하게 말하자면 검색엔진을 장착한 포탈이다.
이 문서에서는 좁은 의미의 검색엔진에 대해서만 설명한다.

그림4) 일반적인 검색엔진의 구조

검색엔진은 크게 수집, 색인과 검색의 세부분으로 나뉜다.

• 수집(Crawl) – 에이전트나 게이트웨이를 통하여 검색대상이 되는 문서를 모으는 작업
  (중복제거, 링크추출, 병렬처리, 암호화, 압축, DB연계 등이 문제가 됨)
• 색인(Index) – 수집된 문서를 분석하여, 검색하기 좋은 형태로 저장하는 작업
  (하부저장구조, 형태소분석, 사전관리, 색인 속도, 색인 용량, 온라인색인 등)
• 검색(Search) – 질의어에 부합하는 문서를 색인에서 찾아 유저에게 보여주는 작업
  (질의어분석/확장, 속도, 병렬처리, 재현률과 정확률, 랭킹, 소팅, 머징, 그룹핑 등)

각각에 대해서는 수도없이 많은 논문들이 있으므로, 깊이 알고자하면 쉽게 배울 수 있음.
특히, 요즘엔 검색엔진과 관련된 다양한 오픈소스가 존재하므로
좋은 오픈소스를 참조하여 공부하는 것을 권장함.

DBMS와 비교하여 검색엔진의 가장 큰 차이점을 말한다면,
정확히 일치하는 것이 아니라 유사한 정도를 가지고 문서를 찾아야 한다는 것과
DBMS가 백업/복구 등 다양한 관리기능을 중시하는 것과는 달리
검색엔진은 검색결과의 만족도와 검색속도를 중요시 한다.

3노드 페이지랭크

이제 노드가 3개있는 구조의 페이지랭크를 구해보자.

그림5) 3노드 직렬 링크 구조

먼저, PageRank 공식에 대입하여 써보자.

PRi(A) = 0.15
PRi(B) = 0.15 + 0.85(PRi-1(A)/1)
PRi(C) = 0.15 + 0.85(PRi-1(B)/1)

연습장에 손으로 풀어도 되겠고, 간단한 프로그램을 짜도 되겠으나,
엑셀이 가장 좋다.(초기값을 바꿔서 실행하기 최고 아닌가?)

따라서,
PR(A) = 0.18, PR(B) = 0.34, PR(C) = 0.47

그림6) 3노드, 3링크 구조

PRi(A) = 0.15
PRi(B) = 0.15 + 0.85(PRi-1(A)/2)
PRi(C) = 0.15 + 0.85(PRi-1(A)/2 + PRi-1(B)/1)

따라서,
PR(A) = 0.20, PR(B) = 0.28, PR(C) = 0.52

페이지랭크는 다른 노드가 얼마나 괜찮은 지에 대한 투표를 하는 것이다.
참고로 이 투표는 누구나 여러표를 행사할 수 있고, 투표하지 않아도 된다.
예를 들어 A가 두표를 행사해서 B와 C에 표를 주었다면,
A의 지지도는 분산되며 B와 C는 A로부터 동일한 정도의 지지를 받은 것으로 판단한다.

그림에서 어느 노드가 가장 많은 지지를 받고 있는 지 생각해보고,
이를 수치화한 PageRank값과 비교해 보기 바란다.

구글 검색엔진의 구조

상대적으로 자료규모가 작은 기업용 검색엔진을 만들고자 하는 경우에는 DBMS와 유사한 정도의 많은 기능이 필요하다. 그러나 인터넷상의 많은, 정말로 많은 자료를 검색하고자 하는 대용량 검색엔진을 만들고자 하는 경우는 다양한 기능보다 검색이라는 하나의 기능이 할 수 있는한 최대한 빠르게, 정확하게 되는 것이 필요하다.

그림7) 구글 검색엔진의 구조

검색엔진은 일종의 유틸리티 집합처럼 작동한다. 사실 검색엔진 뿐만 아니라 대부분의 서비스들이 이처럼 작은 프로그램들로 구분되서 개발되어진다.

그림8) 1998년 당시의 구글 통계

페이지랭크의 왜곡

구글이 제공하는 구글툴바를 사용하면 웹브라우저에서 현재 보고있는 페이지의 페이지랭크를 알 수 있다. 아래 그림에서 사이냅소프트 홈페이지의 PageRank는 5이다.

그림9) 구글툴바를 설치하면 페이지랭크를 볼 수 있다.

툴바가 제시하는 페이지랭크는 실제적인 값이 아니라, 실제값을 10개의 범위로 나뉘어 보여준 것이라서 정확한 값을 알기는 어렵다. 능력되시는 분은 구글 툴바를 해킹해서 실제 페이지랭크값을 볼 수도 있겠다.(구글툴바 라이센스 위반이라고 하네요, 설치시에 누가 라이센스 읽어보나…ㅡㅡ;)

그림10) 구글 툴바가 제시하는 값과 실제 페이지랭크 값(추정치, 구글이 발표한 자료가 아님)

툴바는 그다지 정확하지 않다고한다.
툴바는 종종 페이지랭크를 추정한 값을 보여준다 또한 정확한 값을 알 수는 없다.

페이지랭크는 웹페이지의 중요도 또는 괜찮은 정도를 나타낸다고 보면 되나,
아래와 같은 몇가지 경우에 왜곡 된다.

1) Reciprocal links – “내꺼 링크해줘, 나도 링크해줄께”
2) Link Requirements – “우리 스크립트를 사용하시려면 우리 홈페이지를 링크해주세요”
3) Friends and Family – “내 친구 성연이의 사이트입니다”, “우리 개 사이트가 여기 있어요”
4) Free Page Add-ons – “이 카운터는 www.linktocounter.com 에서 제공된 것입니다”

검색엔진최적화 또는 마케팅 업체

페이지랭크 등 검색엔진에서 사용되는 랭킹알고리즘을 연구하여 특정페이지가 Top 10 페이지 안에 들어올 수 있도록 해주고 돈을 받는다.

대용량 검색결과

우리 모두가 정답을 알고 있다. 그렇다 잘 보여줘야 한다. 그러나 재현률과 정확률이 100%인 경우라도 “노무현”을 검색한 결과가 칠백삼십육만오천육백이십이개가 나왔다면 도대체 사용자에게 어떤 10개를 화면에 보여주는 게 좋을까? 여기에서 랭킹이 등장한다. 사용자가 더 원할 만한 것의 랭킹을 높여서 가장 랭킹이 높은 10개를 보여줄 방법이 필요하다.

구글이 검색결과에 사용하는 기본적인 랭킹은 다음과 같다.
1) 검색에 사용된 키워드와 매치되는 모든 페이지를 찾는다
2) 각 페이지에 있는 키워드와 같은 요소를 중심으로 랭킹을 한다.
3) 인바운드(페이지로 들어오는) 앵커텍스트를 계산한다.
4) 페이지랭크 점수를 랭킹점수에 곱해서 높은 순서대로 10개를 보여준다.

Final Rank Score = (score for all Non-PageRank factors) * (actual PageRank score)

보다시피 페이지랭크는 랭킹에 반영되는 하나의 요소일 뿐이지 절대적인 것은 아니다.
또한, 예전에 비해서 페이지랭크가 반영되는 정도가 계속 감소하고 있는 추세이다.

PageRank는 구글이 검색결과의 정렬에 사용하는 100여개의 알고리즘 중의 하나이다.

우리가 만든 페이지가 특정키워드의 검색결과페이지(SERPs)에 나타나기를 바란다면,

먼저 해당 키워드가 우리 페이지에 있어야 한다. 이 키워드가 Title Tag에 등장하거나
Body Text에 강조된 형태로 나오면 더 좋다.

그리고 우리 페이지를 링크하는 외부 페이지들에서 해당 키워드가 앵커텍스트로 등장해주면
더 좋다.(앵커텍스트의 가중치가 더 높다)

끝으로 페이지 랭크가 높아야 한다.

4노드 페이지랭크

그림11) 4노드 구조

PRi(A) = 0.15 + 0.85(PRi-1(C)/1)
PRi(B) = 0.15 + 0.85(PRi-1(A)/3)
PRi(C) = 0.15 + 0.85(PRi-1(A)/3 + PRi-1(B)/1 + PRi-1(D)/1)
PRi(D) = 0.15 + 0.85(PRi-1(A)/3)

따라서,
PR(A) = 0.35, PR(B) = 0.14, PR(C) = 0.37, PR(4) = 0.14

초기값이 얼마여도 최종 결과에는 관계가 없다.
노드 수가 많아질수록 반복계산량이 많아진다.

2600만개 노드에 대한 PR계산에 워크스테이션 한대에서 몇시간정도 소요(1998, 구글)

반복횟수를 줄이기 위하여 수렴오차범위를 넓게 잡거나,
매번 새로운 PageRank를 계산하는 게 아니라 이전에 계산했던 값을 유지할 수도 있고,
여러개의 컴퓨터를 이용하여 병렬로 계산할 수도 있다(컴퓨터간에 서로 Sync를 맞춰야 한다)

비 PageRank Factor Threshold

검색결과의 랭크에 있어서 페이지랭크를 제외한 다른 요소들은 특정한 기준 점수(Non-PageRank Factor Threshold) 이상만 되면 크게 차이가 나지 않는다. 다시말하면 앵커텍스트가 두배가 된다고 해도 그다지 점수가 높아지지 않는다. 마치 로그함수의 그래프를 생각하면 되겠다.

아래 수식의 Non-PageRank는 로그적으로 증가한다고 보면 맞다.
Final Rank Score = (score for all Non-PageRank factors) * (actual PageRank score)

그래서 이때부터는 PageRank가 매우 중요해진다. PageRank를 모아서 값이 높아져야만 SERPs에 등장할 수 있다.

정말로 중요할 것 같지 않은가? 어느정도 수준이 되는 페이지들이라면 이때부터는 페이지랭크 값이 결정적이다.

SERPs에서 그릇된 페이지를 발견했을 경우

검색결과페이지내에 각 항목별로 버튼을 두어서
버튼이 눌리면…

해당페이지의 PageRank를 0으로 하여 검색결과의 제일 뒤로 보낸다.
해당페이지와 관계된 링크들을 Links에서 제거해버린다.

참고문헌

1) Sergey Brin and Lawrence Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine”
2) Chris Ridings and Mike Shishigin, “PageRank Uncovered”

부록. 직접 검색엔진을 만들고자 하는 분들에게…

아주 간단한 검색엔진을 직접 만들어 보고 싶다면, 수집 프로그램은 직접 만들기보다는(검색엔진에서 수집기가 가장 어려운 부분일지 모른다, 잘하려면 거의 인터넷 익스플로러를 다 만들어야 할 수도 있다) 인터넷 검색에서 “open source crawler“를 검색해서 나오는 것 중에 오래되고 자주 업데이트되는 것을 하나 골라서 쓰도록 하고, 특별히 나는 남의 코드 보는 능력이 뛰어나다고 자신한다면, Mozilla 소스를 커스터마이징해서 쓰기를 권장한다. 남의 것은 죽어도 싫다면… 구글처럼 파이썬으로 만들어라.

색인 프로그램을 만들기 위해서는 어떤 검색기능이 필요한 지를 알아야 한다. 단순 키워드 검색이면 되는 것인지, 멀티 키워드 검색이 가능해야 하는지, 키워드간의 근접성(proximity)이 필요한 것인지 등 색인과 검색은 사실 하나의 틀에서 개발이 이루어져야 한다. 가장 단순한 검색을 한다고 하고, 하부저장구조로는 버클리DB나(포탈에서 좋아한다) 위스콘신대학의 Shore를(연구소에서 좋아한다) 사용하도록 하고, 국문법에 대한 상당한 이해가 필요한 형태소분석보다는 N-Gram방식을 이용하라. 인터넷을 찾아보면 N-Gram 소스코드도 찾을 수 있다.

대용량 처리가 필요하다면, 모든 자료구조를 숫자화하도록하고, 다양한 저장구조가 있겠지만 그 중에서도 해쉬를 사용하기 바란다. 음… 좀 더 직접적으로 설명하자면, 키워드를 모두 숫자형태의 id로 맵핑해서 사용하고, 문서도 마찬가지로 모두 숫자형태의 id로 맵핑해서 사용한다, 그리고 미리 소팅해놓을 필요가 있는 것들은 b-tree같은 구조를 사용하는 것도 좋고, 할 수만 있다면 hash를 쓰도록한다. 어떠한 자료구조라도 이론적으로는 hash보다 빠를 수는 없다.

수집할 데이타가 얼마 안된다면(일반적으로 기업체 내부에서 쓰이는 자료) DBMS와 유사한 아주 다양한 검색기능을 만들어야 유저가 행복해 할 것이다. 그러나 수집할 데이타가 아주 방대하다면(대형 포탈에서 대상으로 하는 자료) 유저는 단순한 검색기능이라도 결과가 잘 나오면 기뻐할 것이다.

어떤 경우에도 검색 결과의 만족도와 검색 속도는 절대로 훼손하면 안되는 것이다. 검색결과의 만족도가 낮으면 누구도 쓰려고 하지 않을 것이고, 검색 속도가 느리면 많은 사용자들이 동시에 검색할 경우 거의 사용불가능 상태가 될 수가 있다.

검색결과의 만족도라는 것은 사람마다 다르고 정성적인 것이라 일종의 인공지능에 관련된 문제다. 처음 검색엔진을 만들 때는 인공지능성격의 문제는 아예 접근하지 않는 게 좋다. 상업용이 아니라 연습용이라면 처음에는 검색결과의 만족도를 무시하라.

검색 프로그램은 사용자의 질의를 색인시에 사용했던 N-Gram을 써서 분리하고, 해당 키워드의 id로 맵핑해서 질의어의 키워드 id 목록을 만든다. 이제 이 키워드 id목록을 가지고 각각의 키워드 id에 해당하는 문서 id들을 모아와서 하나로 결과를 하나로 합쳐서 사용자의 화면에 보여준다.

검색/색인 개발과정은 클라이언트/서버 개발과정과 비슷하다. 검색이 좀 편하려면, 색인을 잘해줘야 하고, 색인을 부실하게 하면 검색이 힘들다. 색인과 검색을 나눠서 개발하고 서로 일을 미루면 잘 개발 안된다.

-끝-