Boolean Model 소개

+세상 +가장 +좋은 +검색엔진시스템

(정보검색엔진(정보검색(정보)(검색))(검색엔진(검색)(엔진)))

          정보검색엔진               Level 1
               |
        +------+-------+   
        |              |
    정보검색       검색엔진          Level 2 
        |              |
    +---+---+      +---+---+
    |       |      |       |
  정보     검색   검색    엔진       Level 3

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>

using namespace std;

struct Term
{
    string Term;
    int depth;
};

int main(int argc, char **argv)
{
    char *msg;
    int depth = 0;
    int i = 0, idx=0;
    char buf[80] = {0x00,};
    vector<Term> TermInfo; 
    Term lTerm;

    if (argc != 2)
    {
        printf("Usage : %s [query]\n", argv[0]);
        return 0;
    }
    msg = argv[1];

    for (i = 0; i < strlen(msg); i++)
    {
        if (msg[i] == '(')
        {
            if (idx > 0)
            {
                lTerm.Term = buf;
                lTerm.depth = depth;
                TermInfo.push_back(lTerm);
                memset(buf, 0x00, sizeof(buf));
                idx = 0;
            }
            depth++;
        }
        else if (msg[i] == ')')
        {
            if (idx > 0)
            {
                lTerm.Term = buf;
                lTerm.depth = depth;
                TermInfo.push_back(lTerm);
                memset(buf, 0x00, sizeof(buf));
                idx = 0;
            }
            depth--;
        }
        else
        {
            buf[idx] = msg[i]; 
            idx++;
        }
    } 
    for (i = 0; i < TermInfo.size(); i++)
    {
        printf("%s : %d\n", TermInfo[i].Term.c_str(), TermInfo[i].depth);
    }
}

# ./stack "(정보검색(정보)(검색))"
정보검색 : 1
정보 : 2
검색 : 2

# ./stack "(정보검색(정보)(검색))(시스템)"
정보검색 : 1
정보 : 2
검색 : 2
시스템 : 1

• A : 구글 검색엔진 ... 그래서 ... 이러한 특징을 ... ... ... ... .. 이다.
  
• B : 구글은 최근 ... ... 하는 과정에서 ... 검색엔진을 ... .. ... 했다.
  
• C : 오늘 ... 검색을 해봤더니 ... ... 구글에서 ... ... 엔진은 역시 벤츠.
  
  

1 MapReduce 소개

1. 병렬처리 : 하나의 거대한 데이터는 여러개의 분산된 시스템으로 보내어져서 병렬적으로 처리될 수 있어야 한다.
   
2. fault-tolerance : 병렬시스템중 몇개에 문제가 생기더라도 전체 시스템에 영향을 주면 안된다. 자동으로 관리할 수 있어야 한다.
   
3. 데이터분산 및 로드밸런싱
   
   

2 프로그래밍 모델

3 MapReduce 테스트

3.1 응용

3.1.1 전체 흐름

1. User Program은 효율적인 병렬/분산처리가 가능하도록 파일을 일정한 크기를 가지는 M 개의 조각으로 쪼갠다.
   
2. User Program에는 Master이라는 특별한 프로세스가 존재한다. Master은 worker에게 M map과 R reduce를 할당하며, 각 worker의 상태를 관리한다.
   
3. worker은 할당된 문서를 읽어들인다음 유저정의 Map 함수를 이용해서 key/value 형태로 데이터를 읽어들인다. Map함수는 만들어진 key/value를 buffer 메모리에 저장한다. 이 경우 key는 파일명이 될 것이고, value는 {단어,count}가 될 것이다.
   
4. buffer 메모리(혹은 파일)에 있는 key/value는 주기적으로 지역파일에 쓴다. 이 파일은 master에 의해서 관리되며, reduce worker에 할당이 된다.
   
5. reduce worker이 master로 부터 신호를받았다면, map worker에 의해서 지역파일에 씌여진 buffer 데이터를 가져온다. master와 reduce worker와의 통신은 remote procedure call등을 이용할 수 있을 것이다. 중간파일을 전부 읽어들였다면, 동일 key값을 이용해서, value와 관련된 필요한 계산을 하면 된다. 하나의 reduce작업에 다양한 종류의 key들이 존재하기 때문에, sort가 된후 작업이 되어질 필요가 있다. 이러한 작업은 상당히 많은 메모리를 차지하게 되는데, 이럴경우 다른 프로그램에 소트를 맡기도록 한다.
   
6. reduce worker에서 소트를 해서 유일한 key를 만들어 낼 수 있게 되는데, 이때 사용자 정의된 Reduce 함수를 이용해서, value에 대한 연산을 하면 된다. 연산후 결과는 output 파일로 씌여지게 된다 output 파일로 씌여지게 된다.
   
7. 모든 작업이 완료되었다면, reduce worker은 프로그램 리턴값을 User Program에게 넘겨준다.
   
   

3.2 Master 데이터 구조체

3.3 Fault Tolerance

3.3.1 Worker Failure

3.3.2 Master Failure

3.3.3 Semantics in ther Presence of Failures

3.3.4 Locality

4 샘플 프로그램

1. 4개의 RFC문서가 주어진다.
   
2. map worker에 분배하기 위해서 4개의 문서를 3개의 조각으로 바꾼다.
   
3. 3개의 map worker을 실행시키고, 각각의 조각을 읽어와서 <DID, Term> 형식의 데이터를 생성한다.
   
   이 작업은 병렬적으로 수행된다.
   
4. reduce worker에서 <DID, Term> 데이터를 읽어와서 <Term, DID>로 Term Invert한다.
   
5. Term Invert된 데이터를 Term.idx 파일에 저장한다.
   
   

struct LastIndexResult
{
    string Term;
    vector<string> DID;
}
set<LastIndexResult> IndexSet;

         .idx
   +--------------------+
   | A D I O Q R V X Z  | ---+
   +--------------------+    |
   +--------------------+    |-----+
   | A B J K L V Z      | ---+     |
   +--------------------+          |-----> OUTPUT set<LastIndexResult>
   +--------------------+          |
   | A B K L O P X Z    | ---+     |
   +--------------------+    |-----+
   +--------------------+    |
   | C I J Q R W Z      | ---+ 
   +--------------------+

5 Nutch의 MapReduce 엔진

• Mapper
  Map Task를 실행하기 위한 프로세스로, 파일을 Split 하고, Split된 각 부분을 읽어서 <Key, Value>로 만들기 위한 function을 가진다. <Key, Value>의 목록은 중간파일 형태로 저장이 될 것이다.
  
• Reducer
  Reduce Task를 실행하기 위한 프로세스로, Mapper에 의해서 중간파일 형태로 저장된 <Key, Value>파일을 읽어들여서, 결과파일로 만들어 낸다.
  
• Job Tracker
  각 Task를 실행하는 Job을 제어하기 위한 프로세스. Mapper과 Reduce를 실행시키고 Job을 할당한다.
  
  

6 참고문헌

1. mapreduce-osdi04.pdf
   
2. http://jaso.co.kr/tatter/index.php?pl=133 C언어를 이용한 hadoop 파일 시스템 처리
   
3. http://www.jaso.co.kr/tatter/index.php?page=8&setdate=200609 hadoop 살펴보기
   
4. http://wiki.apache.org/lucene-hadoop/HadoopMapReduce Hadoop MapReduce
   
5. 다카하시의 radium software 내의 MapReduce 번역 : 한글문서
   
6. 쓰레드 베이스의 MapReduce : 한글문서
   
7. MapReduce 소개글 : 한글문서

• Blog를 통한 배포.
  
  배포경로가 두개가 된다는 점외에도 커뮤니티 형성이 가능하다는 장점이 있다. 우리나라에서 wiki는 커뮤니티 형성이 거의 제로다. 위키에서의 커뮤니티라면 문서의 작성과 수정을 통해서 이루어지게 될건데, 실제 내 사이트에서 관리되는 문서의 95%이상은 내가 작성한 문서이며, 10페이지 이상 문서를 작성한 저자는 단 2명이다. 블로그는 이런점에서 훌륭한 커뮤니티 시스템이다. 커뮤니티로써의 블로그의 특징은 블로그 검색엔진의 미래 에 나름 생각을 정리해 둔게 있다.
  
• 문서 타이틀의 재작성
  
  이와 관련된 얘기는 검색엔진 최적화에 정리해둔걸 읽어 보기 바란다. 주로 문서의 특성이 최대한 잘 들어나게끔 제목을 재작성하는데, 많은 노력을 들였다. 예를 들어 문서의 제목이 malloc 이였다면, linux man page : malloc - 커널에 메모리 할당을 요청 이런 식으로 변경했다. 문서의 양이 많아서 모두다 하지는 못하고, 중요도가 높다고 생각되는 문서의 제목을 우선 최적화 시켰다.
  
• 링크의 사용
  
  포스트를 작성하고나면, 관련된 다른 블로거의 포스트를 찾아서 적극적으로 트랙백을 걸었다. 포스트와 관련된 다른 정보들을 얻을 수 있고, 커뮤니티를 형성할 수 있으며, 장기적으로 PageRank를 높이는 효과를 얻을 수 있다. 또한 블로그 포스트의 경우, 링크가 wiki의 원문으로 연결된 경우가 많은데, 역시 링크에 의한 페이지 중요도를 높일 수 있을 거라 생각했다.
  
  

Analytics.pdf

링크의 활용

1. 관련된 링크페이지를 찾는 것은 매우 번거로운 작업이다.
   
2. 일반적으로 하나의 링크는 하나의 페이지에 대응한다. 여러개의 페이지를 링크하는건 힘들거나 귀찮다.
   
   

  if (ereg("\([:][0-9]+[,]", $line))
  {
    $line2 = ereg_replace("([ \t\n]+)([^ <>=\.\(\)]+)\(([:][0-9]*),([^,]*)\)",
            "\\1<a href=\"$url_prefix/wiki.php/manSearch?google=none&name=\\2\">\\4</a>", $line);
  }

검색엔진의 활용

precision

Recall

예

상위 10개에서의 precision = 8/10 = 0.8
recall = 15/30 = 0.5 

precision 과 Recall 의 관계

1. Recall을 높일 경우 : Recall을 높이면 많은 문서를 가져오게 된다. 여기에는 관련있는 문서도 포함되겠지만 그렇지 않은 문서도 포함이 된다. 결국 precision이 낮아지게 될 것이다.
   
2. Recall이 낮을 경우 : 문서의 범위를 한정할 수 있으므로, precision이 높아지게 될 것이다. 그러나 범위가 한정되는 만큼, 많은 관련있는 문서를 놓치게 될 것이다.
   
   

웹문서

논문

참고문헌

• http://www.emh.co.kr/xhtml/google_search_engine.html
  
• http://en.wikipedia.org/wiki/Information_retrieval

TF - IDF 모델

• TF : 문서 Vector에 존재하는 Term의 갯수
  
• IDF : Term을 Vector에 포함하고 있는 모든 문서들
  
• Weight = TF * IDF
  
  

예제 : 문서의 유사도

1. 번째 원소는 "상상플러스"라는 단어의 빈도수
   
2. 번째 원소는 "김제동"
   
3. 번째 원소는 "무한도전" 이다.
   
   

1. d(A,B) = 2^2 + 4^2 = 20
   
2. d(A,C) = 10^2 + 5^2 = 125
   
3. d(B,C) = 8^2 + 9^2 = 145
   

예제 : Query 에 대한 문서의 유사도

1. 리눅스는 매우 좋은 운영체제이다. 어쩌고 저쩌고.. 한참후에 개발자입장에서 한번 써볼한 하다.
   
2. 리눅스는 개발자에게 매우 좋은 운영체제이다. 왜냐하면 어쩌고 저쩌고
   

장점

1. 동음이의어와 다의어 처리가 가능하다.
   
2. 결과의 정확도 - relevance scoring - 를 구할 수 있다.
   
3. 결과 피드백이 용이하다.
   
   

단점

1. Term의 갯수가 많아질수록 해당 문서는 더 낮은 similarity 값을 가지게 된다. 이는 큰 문서일 저 평가될 수 있음을 의미한다.
   
2. 찾고자 하는 키워드가 정확히 매치되어야 한다. - 이 문제는 좋은 형태소 분석기를 가짐으로써 어느정도 해결할 수 있다. -
   
3. 워낙에 광범위한 주제를 다루는 문서가 많고 문서에 포함된 Term의 양도 많기 때문에, 비슷한 주제를 다루는 문서라고 하더라도 전혀다른 Term으로 구성되는 경우가 발생한다.
   
4. 느리다.
   
   

o = 연예계 문서 (k-1에 대한 단어가 전혀 나타나지 않음)
x = k-1 관련 문서들 
최홍만
|o       x
|o      x
|o       x
|o      x
|o       x
|o      x
+-------------->  (K-1)

1. 같은 주제라고 하더라도 y축의 이쪽끝과 저쪽끝의 문서는 거리가 멀어진다.
   
2. 다른 주제라고 하더라도 y축상에 있는 문서끼리는 거리가 가깝다.
   
3. 결론 : 검색이 제대로 안된다 주제간의 차이를 반영하지 못하기 때문이다.
   
   

Markov random walk

(단어 2)
^
|             o o o
|          o          o o
|       o *     x          o       x
|      o           x x            x 
|                        x   x  x 
|                           
|
-------------------------------------> (단어 1)

o = 주제 1에 속하는 문서들
x = 주제 2에 속하는 문서들
* = 쿼리

|                o <-A
|       D->  o
|     C-> o  *   x <-B  
|          o 
|                          

• 쿼리 -> C -> D -> A : 확률값은 P(쿼리->C) * P(C->D) * P(D->A)
  
• 쿼리 -> D -> A : 확률값은 P(쿼리->D) * P(D->A)
  
• 기타 : 쿼리 -> C -> 쿼리 -> D -> A 등등등
  

Markov Random walk 와 PageRank

Q(A) = Q(B)/N(B) + Q(D)/N(D)

Q(A) = Q(B)*(1/N(B)) + Q(C)*0 + Q(D)*(1/N(D) 

Markov chain

lect_4.pdf

참고문헌

• wikipedia - Vector space model
  
• dc inside

컨텐츠의 영향력 확대

중심에 서기

첫째도 둘째도 셋째도 컨텐츠

위키와 블로그를 활용하라

검색엔진 최적화

문서의 점수 = tf * idf

• 키워드가 자주 발생하게 한다. tf를 높이겠다는 얘기가 되겠다.
  
  리눅스와 윈도우의 차이점에 대해서 얘기를 하겠다. 전자는 후자에 비해서 이런이런 장점을 가지고 있다이런식으로 작성하는 것보다는
  리눅스와 윈도우의 차이점에 대해서 얘기를 하겠다. 리눅스는 윈도우에 비해서 이런이런 ...식으로 키워드를 자주 노출시키도록 한다.
  
• 전문분야에 대한 컨텐츠를 많이 작성한다. idf를 높일 수 있다.
  
• 문서의 제목과 URL은 신중하게 결정한다.
  
  웹문서는 제목, 본문, URL의 3가지 요소로 구성된다. 똑같은 단어라도 어떤 요소에서 발생했는가에 따라서 부여하는 점수가 틀리다. URL > 제목 > 본문 순이다. 그러므로 URL과 제목은 그 문서를 특징할 수 있는 단어를 포함하게 해야 한다. 그것도 가능하면 2번이상 포함하게 한다.
  리눅스를 사용하자 라는 제목보다는 리눅스? 리눅스의 활용처가 궁금하다라는 식으로 제목을 작성하는게 좋다.
  
• URL과 제목은 간략하게
  
  단어의 갯수가 많아질수록 점수가 떨어진다. 여러분 리눅스를 사용하면 어떤 점이 좋을지 궁금하지 않으세요?" 보다 리눅스를 사용하자'''가 더 좋은 제목이다. 메타블로그에도 노출시킬 거라면, 후자가 반드시 좋은방법이라고 보기는 힘들것이다. 적절한 제목을 부여하도록 하자.
  
  

링크를 이길 수는 없다

애플 아이폰, 애플 아이폰, 애플 아이폰, 애플 아이폰 .... 한 100번쯤 반복

문서 중요도 = (tf * idf) * pagerank

자주 꾸준히 포스팅 하라