메뉴

Related Link Project

2016-01-16 15:44:51

목차

Related Link 프로젝트의 필요성

현재- 2006/02/28 - Joinc에 포함된 wiki(:12)문서의 갯수는 2000개를 넘기고 있다. 많다면 많은 정보일 수 있는데, 이들 정보가 지식으로써의 위상을 가지기 위해서는 관련있는 문서끼리 연결되어서 네트워크(:12)를 구성할 수 있어야 한다.

위키의 단점 중 하나는 관리를 제대로 해주지 않을 경우, 각개의 정보들이 독립적으로 존재하고 되어서 유용한 정보를 가진 페이지들이 바다에 떠있는 섬처럼 될 수 있다는 점이다. 이를테면 고급정보를 포함한 낙서장이 될 수 있다라는 얘기다.

개인적으로 이러한 문제를 해결하기 위해서 다음과 같은 장치를 마련했다.

Directory 구조

유사한 성격의 데이터를 분류하기 위한 가장 일반적인 방법은 다중의 카테고리를 이용하는 것이다. 이 방법은 고대에서 부터 지금까지도 널리 사용되는 방식이다. Joinc의 wiki도 이러한 방식을 도입해서 페이지를 관리하고 있으며, 이를 위해서 subindex와 같은 디렉토리 관리 메크로도 사용하고 있다.

즉 아래와 같은 구조를 가지게 된다. 
Site ---+-- C --+-- Documents ----+---- HowTo
        |       |                 |
        |       |                 +---- Debug
        |       |
        |       +-- Sample -------+---- Hello.C
        |
        +-- Mysql
방문자는 해당 카테고리내에서 비슷한 주제를 가지는 문서를 쉽게 탐색할 수 있게 된다. Site 위키페이지를 방문해보면 어떻게 관리되는지 확인할 수 있을 것이다.

Meta Page

디렉토리 구조는 좋은 방식이긴 하지만, 문서단위로 관리가 되어지기 때문에 문서에 포함된 정보를 가진 단어 수준에서의 탐색을 지원하지는 못한다. 다행히도 우리는 HyperLink 라는 매우 훌륭한 도구를 이용해서 단어 단위에서의 탐색을 할 수 있음을 알고 있다.

HyperLink는 대체로 사용하기 쉽지만 효과적으로 단어와 문서를 연결시켜주는 도구는 아니다. 게다가 한번에 하나의 페이지만 링크시킬 수 있다. 예를 들어 socket(:12) 이라는 단어가 있다면, 이 단어에 대한 정보를 제공하는 여러개의 문서가 있을 수 있다. 소켓함수를 설명하는 문서, 네트워크 프로그래밍 관련된가 이에 해당될 것이다. 이 경우 HyperLink(:12) 사용자는 문서의 URI에 대한 정보를 기억하고 있어야 한다. 또한 여러개의 문서를 링크시켜야할 필요가 있을 경우 링크의 리스트를 생성시켜야만 한다. 링크의 리스트는 좋은 방법이긴 하지만, 문맥의 흐름을 깬다는 단점을 가진다. 다른 문서의 socket(:12) 에 대해서도 동일한 작업을 해주어야 한다.

문서의 양이 늘어나면 늘어날 수록 HyperLink를 통한 정보의 연결은 점점 더 힘들어지게 된다.

이러한 문제를 해결하기 위해서 Meta정보 페이지를 생성하게 된다. Meta 정보 페이지의 가장 전형적인 예는 검색엔진이다. 검색엔진은 각 단어와 연관된 문서의 메타정보를 가지고 있다. 여기에 사용자가 검색어를 입력하면, 해당 검색어와 연관있는 문서의 URI(:12)를 넘겨준다.

Joinc의 Meta Page 구조

기본 개념

Joinc 역시 이러한 식의 Meta Page를 유지할 수 있도록 해 놓았다. 구조는 아래와 같다.

attachment:meta.png

페이지내에서 관심있는 단어를 클릭하면 관련된 메타페이지로 이동을 하는 방식이다. 메타 페이지는 링크되어 있는 웹페이지로 자동으로 보내거나 혹은 (파란색 선으로 표현된) 페이지의 목록을 보여주고 가고 싶은 페이지를 선택하도록 할 수 있다. 아래는 어떻게 작동하는지를 보여주는 예제 시뮬레이션 페이지다. 
                                      |    |
     Page 1   +-----------------------|->>-|-------------+ 
    +---------|--------------------+  |    |    +--------|------------------+ 
    | 네트워크프로그래밍(:12)을    |  |    |    |  Site/Network_Programing  |
    | 쉽게하려면 TCP(:12), IP(:12) |  |    |    +---------------------------+
    | Socket(:12)에|대한 개념을 ...|  |    |    +---------------------------+ 
    +---|----------|---------------+  |    |    | man/2/socket              |
        |          |                  |    |    +-------+-------------------+
        +----------|------------------|->>-|------------+
                   |                  |    |    +---------------------------+
                   +------------------|->>-|----| man/2/socket              |
                                      |    |    +---------------------------+
네트워크프로그래밍, TCP, IP, Socket 등을 클릭하면 Meta Page로 넘어가고, Meta Page에 의해서 리다이렉트 되거나 관련된 페이지의 목록을 보여주는걸 확인할 수 있을 것이다. 이렇게 Meta Page를 통해 문맥의 단어와 Page의 네트워크가 만들어지게 된다. 여기에 더불어 구글과 같은 검색엔진으로 쿼리 결과도 보여줄 수 있을 것이다.

태그와의 차이점

의미있는 단어와 의미있는 문서를 연결시켜준다는 점에서 태그와 비슷한 것으로 볼 수 있을 거 같다. 그러나 태그의 문제와 한계점은 오래전부터 지적되어고 있다.

attachment:tag.png

태그는 단순하게는 전체 문서셋에 포함된 단어의 색인을 만들고 카운팅한 결과의 모음이라고 단순하게 생각할 수 있다. 위의 문서를 보면 이게 의미하는 바를 알 수 있을 것이다.

그러나 우리가 문서를 읽을 때는 해당문서에 포함된 용어들 중 의미있는 용어와 이것에 대한 정보를 포함한 문서의 링크 정보를 얻기 원한다. 초반에는 그나마 양호했지만 최근에는 태그가 남용되면서 실제문서와는 별로 관련없는 단어들의 나열이 되어가고 있다. 이런 이유들로 비슷한 관심사를 공유하는 서비스로는 사용할 수 있겠지만, 정보와 정보를 연결하는 수단으로 사용하기는 힘들거 같다.

태그류의 서비스는 비슷한 관심을 가지고 사이트를 방문하는 사람에게 요즘 이러한게 관심사입니다를 알려주기 위한 변형된 추천서비스로 봐야 할 것이다. 태그가 앞으로 어떻게 발전할지 모르겠지만, 이 한계를 극복하기가 쉽지 않을 거라 생각된다.

링크기반의 wikipedia(:12)가 보여주는 정보연결능력의 강력함과 비교해보면, 역시 현재까지 나온 가장 좋은 정보네트워크 도구는 HyperLink인거 같다.

링크 컨텐츠 생성

정보와 연관되는 컨텐츠를 위한 Meta Page는 참여에 의해서 쉽게 작성될 수 있어야 할 것이다. 이를 위해서 다음과 같은 방식을 사용했다.
  1. 관심있는 단어에 대한 Meta Page 작성을 위해서 단어 + ([:]*[0-9]*)를 사용한다. TCP(:12) ---> TCP(:12), socket(2) ---> socket(2)
  2. :는 카테고리 분류가 들어감을 의미한다. 예를 들어 :12 는 컴퓨터용어(:12) 사전용 메타페이지를 참고하겠다는 뜻이다. 굳이 카테고리를 명시할 필요는 없다. 카테고리를 명시하지 않을경우에는 모든 카테고리를 뒤져서, 일치하는 단어를 찾게 된다. :이 사용되지 않는 경우는 카테고리 분류가 없음을 의미한다. 정규표현식에 대한 내용은 정규표현(:12)을 참고하기 바란다.
  3. 만약 해당 단어의 정보를 가진 Meta Page가 있다면, 이동을 할 것이다. 그렇지 않을 경우 페이지 만들기 페이지가 뜨게 된다.

현재 방식의 문제점

지금 방식을 이용해서 컨텐츠끼리 잘 연결되려면 다음의 조건을 만족해야 한다는 문제점이 있다. 컨텐츠 생산에 적극적으로 참여하는 일정수 이상의 유저가 있어야 한다. 그렇지 않다면, 단편적인 정보들이 나열된 사이트가 될 확률이 크다. 방문자의 약 1% 정도가 컨텐츠를 수정하거나 생성하는데 관심을 보인다면, 이 방식은 잘 먹혀들 확률이 크다. 실제 wikipedia(:12)도 적극적으로 참여하는 유저는 1%내외일 거라고 생각된다. 그러나 내 사이트의 경우 5년간 사이트를 운영해본 결과 위키에서 페이지를 생성하는 유저는 0.1% 도 안된다. Q&A를 제외하고 보자면, 다른 사이트도 마찬가지일 거라고 생각된다.

결국 사람의 자발적인 참여에 맡기는 것만으로는 좋은 시스템을 만들수가 없다는 결론에 도달한다. 사실 참여만으로라는 것은 매우 이상주의적인 생각이다. 참여가 매우 중요하다고 생각되는 민주주의 이념도, 교통/통신시설 수많은 법/제도적인 장치가 있었기 때문에 지금 정도의 수준에 이르렀다고 판단된다.

시스템 고안

Related Rink의 기본개념은 지금의 Meta Page를 이용하는 방식과 크게 다르지 않다. 여기에 그동안 사람이 - 거의 혼자서 했던 - 작업을 컴퓨터가 처리하도록 해서 효율성을 높이도록 할 것이다.

attachment:meta3.png

Wiki Document

위키를 이루는 문서들이다. 이들 문서는 다음 두개의 포맷으로 저장이 된다. Index(색인)을 만들기 위해서는 문서를 수집해야 하는데, wiki 문법을 따르는 문서를 수집할경우 wiki 문서를 해석하기 위한 엔진을 별도로 제작해야 하는 불편함이 따른다. 그러므로 해석이 끝난 HTML 포멧 문서를 기준으로 수집하도록 할 것이다.

Crawler

내부의 문서만을 수집하면 되므로 일반적인 웹 검색엔진(:12)처럼 링크를 검사해서 그래프 자료구조를 가지는 webDB를 만들지는 않을 것이다. wiki의 모든 페이지는 특정 디렉토리에 파일형태로 저장되어 있으니, 이들 파일 이름을 이용해서 문서들을 순환할 것이다.
  1. scandir(3)등의 함수를 이용해서 wiki문서 목록을 얻어온다.
  2. wiki문서 목록을 순환하면서, w3m(:12)을 이용해서 HTML 테그를 제거한 plain/text 문서를 얻어온다. 
    # w3m -dump http://www.joinc.co.kr
  3. 얻어온 문서는 동일한 이름으로 파일로 저장한다.

Indexer

사전제작

색인기를 만들기 위해서는 우선 단어사전이 만들어져야 한다. 여기에서 필요한 단어사전은 일반문서에 대한 단어사전이 아니므로, 단순한 방법으로 만들도록 할 것이다. 사전을 위한 데이터는 Crawer를 통해 수집된 문서들이 사용된다. 데이터는 sqlite(:12) 에 저장할것이다. 속도의 문제로 사전데이터를 DB 시스템에 넣는 경우는 없겠으나, 속도가 중요한 서비스를 할 생각은 아님으로 쉽게 구현하도록 하겠다. 수행시간이 비효율적일 경우 별도의 DB로 가져갈 수도 있다.

다음은 조사를 제거하는 간단한 코드다.

Document DID 테이블

최종적인 색인 DB는 <Term, Document List> 자료구조가 될 것이다. 이때 seek(2)를 통한 빠른 검색이 가능하도록 사이즈를 고정시킬 필요가 있다. 이를 위해서 Value가 되는 Document 이름을 Int 형 숫자로 바꾸도록 할 것이다. Int형 Document ID를 DID라고 명명한다. 다음과 같은 테이블을 유지하게 될것이다.
필드명 TYPE 크기 설명
Term Char 20 색인어
DID Int 4 문서번호
이후 색인자료구조를 위한 모든 필드값에 Term과 DID가 사용된다.

색인

<Document Name, Term> 자료구조를 만들고, 이를 다시 <Term, {DID List}> 자료구조로 만든다. 문서와 Term의 갯수가 그리 많지 않다고 생각됨으로 메모리를 소비하는 방식으로 Invert Document Frequence DB를 생성하도록 하겠다. <Term, {DID List}>를 Invert Document Frequency 라고 한다. 해당 Term을 포함한 문서의 갯수와 문서이름을 보여준다.

다음과 같은 구조를 가지는 색인 Table을 생성할 것이다.

attachment:tis.png

총 3개의 테이블로 이루어진다. || 필드명 || Type || 크기 || 기타 ||
Term Char 20
DF Int 4 Document Frequency
DFP Int 4 Term을 포함한 Document목록의 시작점
|| 필드명 || Type || 크기 || 기타 ||
DID Int 4 문서번호 : 정열
TF Int 4 Term Frequency
|| 필드명 || Type || 크기 || 기타 ||
TermP Int 4 Term Index에서의 블럭 위치
예를들어서 Linux라는 단어가 검색어로 주어진다면, 다음과 같은 과정을 거쳐서 Linux(:12)를 포함한 문서를 얻어오게 된다.

Score

검색엔진의 가장 중요한 과제는 중요도가 높은 문서를 상위에 노출시키는 것일 것이다. 이를 위해서 Score 알고리즘과 PageRank 와 같은 것들을 이용해서 문서의 중요도를 계산하게 된다. 일반적으로 사용되는 Score 공식은 Nutch 검색엔진을 참고하기 바란다.

Score 공식은 TF * IDF로 요약할 수 있다. Term이 몇개의 문서에서 발결되었는지와 하나의 문서에서 몇개의 Term이 발견되었는지를 곱하는 것이다.

이 방식을 사용하는 것 만으로도 문서검색의 품질을 상당히 높일 수 있지만, 커다란 문제점이 있다. 바로 문서에서 발견되는 Term의 갯수인 TF를 조작할 수 있다는 문제다. 별내용 없이 동일한 단어를 반복해서 출현하게 한다든지 하는게 대표적인 방법이다. 실제 초기 검색엔진은 이러한 TF조작에 취약성을 보여주었다. PageRank는 이러한 문제를 해결하기 위해서 구글에서 도입한 개념으로, 해당 문서를 참고하는 링크가 몇개인지를 계산한다. 좋은 문서는 많이 참고될 것이다라는 전제하에 문서의 중요도를 검사하는 방식이다.

Joinc의 경우 TF의 조작 염려가 없고, 단지 하나의 단어에 대해서만 문서의 Score를 적용하면 되므로 오직 TF만을 가지고 문서의 순위를 메길 것이다. 단 기존의 man(:12)으로 시작되는 meta page에 대해서는 가중치를 더 줘서 최상위에 노출되도록 할 것이다.

코딩

우선 사전제작을 해서, 처리해야할 Term이 몇개인지 확인하고, 사전을 수정하기 위한 웹인터페이스를 제작한다. 이들 데이터를 가지고 어떤 DB를 이용할건지, 어떤 방식을 사용할건지 (품질 우선 혹은 속도 우선)를 결정하도록 한다.

사전제작

문서를 tokenizing한다음, 뒤에 붙는 조사만 제거해서 최소한의 사전데이터를 만든다. 때문에 정확하지 않은 사전이 생성될 것이다. 이것은 제공되는 인터페이스를 통해서 직접 수정하도록 한다. (아마도) 수천개 내외의 사전이 생성될 것으로 생각되니, 어느정도 수준으로 다듬는데 그리 큰 시간이 소모되리라 생각되지는 않는다. 또한 기술단어들을 중심으로 하기 때문에, 일반단어에 대한 사전정보는 중요하지 않다. 이렇게 만들어진 사전제작 프로그램은 낮은 수준의 것으로, 일반적으로 사용가능하게 하려면 많은 시간을 투자해야 할 것이다. 일단 위의 규칙으로 파싱하는 프로그램을 만들어서, 대략적으로 사전정보를 작성한뒤에 관리프로그램을 이용해서 교정을 한다. 서전데이터는 SQLite(:12)로 유지한다.

관리 인터페이스는 다음과 같은 기능을 가진다. 이렇게 만들어진 사전데이터는 지속적으로 유지된다.

Test Code

여기에는 단위 테스트코드들이 들어간다.
제목 저자 변경일

사전데이터

명사사전만을 유지할 것이다. Joinc의 모든 문서를 파싱하고 기본적인 조사를 제거한다음 노가다를 뛰어서 사전을 만들어가고 있다. 아래의 결과물은 완성된 사전은 아니며, 계속 수정/추가되어야 할 것이다. 우선은 아래의 단어를 이용해서 사전을 만들 생각이다.

아래의 것은 가공되지 않은 원본이다. 가공된 정보는 아래의 사전파일들을 통해 유지할 것이다.

사전 파일들

제목 저자 변경일

디렉토리 관리

제목 저자 변경일