Related Link Project
2016-01-16 15:44:51
목차
현재- 2006/02/28 - Joinc에 포함된 wiki(:12)문서의 갯수는 2000개를 넘기고 있다. 많다면 많은 정보일 수 있는데, 이들 정보가 지식으로써의 위상을 가지기 위해서는 관련있는 문서끼리 연결되어서 네트워크(:12)를 구성할 수 있어야 한다.
위키의 단점 중 하나는 관리를 제대로 해주지 않을 경우, 각개의 정보들이 독립적으로 존재하고 되어서
유용한 정보를 가진 페이지들이 바다에 떠있는 섬처럼 될 수 있다는 점이다. 이를테면 고급정보를 포함한 낙서장이 될 수 있다라는 얘기다.
개인적으로 이러한 문제를 해결하기 위해서 다음과 같은 장치를 마련했다.
유사한 성격의 데이터를 분류하기 위한 가장 일반적인 방법은 다중의 카테고리를 이용하는 것이다. 이 방법은 고대에서 부터 지금까지도 널리 사용되는 방식이다. Joinc의 wiki도 이러한 방식을 도입해서 페이지를 관리하고 있으며, 이를 위해서
subindex와 같은 디렉토리 관리 메크로도 사용하고 있다.
즉 아래와 같은 구조를 가지게 된다.
Site ---+-- C --+-- Documents ----+---- HowTo
| | |
| | +---- Debug
| |
| +-- Sample -------+---- Hello.C
|
+-- Mysql
방문자는 해당 카테고리내에서 비슷한 주제를 가지는 문서를 쉽게 탐색할 수 있게 된다.
Site 위키페이지를 방문해보면 어떻게 관리되는지 확인할 수 있을 것이다.
디렉토리 구조는 좋은 방식이긴 하지만, 문서단위로 관리가 되어지기 때문에 문서에 포함된
정보를 가진 단어 수준에서의 탐색을 지원하지는 못한다. 다행히도 우리는
HyperLink 라는 매우 훌륭한 도구를 이용해서 단어 단위에서의 탐색을 할 수 있음을 알고 있다.
HyperLink는 대체로 사용하기 쉽지만 효과적으로
단어와 문서를 연결시켜주는 도구는 아니다. 게다가 한번에 하나의 페이지만 링크시킬 수 있다. 예를 들어 socket(:12) 이라는 단어가 있다면, 이 단어에 대한 정보를 제공하는 여러개의 문서가 있을 수 있다. 소켓함수를 설명하는 문서, 네트워크 프로그래밍 관련된가 이에 해당될 것이다. 이 경우 HyperLink(:12) 사용자는 문서의 URI에 대한 정보를 기억하고 있어야 한다. 또한 여러개의 문서를 링크시켜야할 필요가 있을 경우
링크의 리스트를 생성시켜야만 한다. 링크의 리스트는 좋은 방법이긴 하지만, 문맥의 흐름을 깬다는 단점을 가진다. 다른 문서의 socket(:12) 에 대해서도 동일한 작업을 해주어야 한다.
문서의 양이 늘어나면 늘어날 수록 HyperLink를 통한 정보의 연결은 점점 더 힘들어지게 된다.
이러한 문제를 해결하기 위해서
Meta정보 페이지를 생성하게 된다. Meta 정보 페이지의 가장 전형적인 예는 검색엔진이다. 검색엔진은 각 단어와 연관된 문서의 메타정보를 가지고 있다. 여기에 사용자가 검색어를 입력하면, 해당 검색어와 연관있는 문서의 URI(:12)를 넘겨준다.
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
태그는 단순하게는 전체 문서셋에 포함된 단어의 색인을 만들고 카운팅한 결과의 모음이라고 단순하게 생각할 수 있다. 위의 문서를 보면 이게 의미하는 바를 알 수 있을 것이다.
그러나 우리가 문서를 읽을 때는 해당문서에 포함된 용어들 중 의미있는 용어와 이것에 대한 정보를 포함한 문서의 링크 정보를 얻기 원한다. 초반에는 그나마 양호했지만 최근에는 태그가 남용되면서 실제문서와는 별로 관련없는 단어들의 나열이 되어가고 있다.
- 문서의 양이 적을 때는 유용하게 보이지만, 시간이 지나서 문서가 쌓여갈 수록 태그의 유용성이 사라진다.
- 태그는 카테고리와 비슷하며, 카테고리 분류에서와 같은 관리상의 문제가 발생한다. 카테고리가 늘어나면 이를 병합하거나 분할해야 한다. 예를 들어 C(:12), Perl(:12), Java(:12), D(:12)와 같은 태그가 계속 늘어난다면, 이들을 프로그래밍(:12)카테고리로 병합할 필요가 생긴다. 반면 C에 대한 내용이 계속 쌓이다 보면, 시스템프로그래밍(:12), 네트워크프로그래밍(:12), C입문(:12), 관련서적, 교육기관 등등으로 분할해야 한다. 이러한 작업은 거의 전적으로 수작업에 의존해야 한다.
이런 이유들로 비슷한 관심사를 공유하는 서비스로는 사용할 수 있겠지만, 정보와 정보를 연결하는 수단으로 사용하기는 힘들거 같다.
태그류의 서비스는 비슷한 관심을 가지고 사이트를 방문하는 사람에게 요즘 이러한게 관심사입니다를 알려주기 위한 변형된
추천서비스로 봐야 할 것이다. 태그가 앞으로 어떻게 발전할지 모르겠지만, 이 한계를 극복하기가 쉽지 않을 거라 생각된다.
링크기반의 wikipedia(:12)가 보여주는 정보연결능력의 강력함과 비교해보면, 역시 현재까지 나온 가장 좋은 정보네트워크 도구는 HyperLink인거 같다.
정보와 연관되는 컨텐츠를 위한 Meta Page는 참여에 의해서 쉽게 작성될 수 있어야 할 것이다. 이를 위해서 다음과 같은 방식을 사용했다.
- 관심있는 단어에 대한 Meta Page 작성을 위해서 단어 + ([:]*[0-9]*)를 사용한다.
TCP(:12) ---> TCP(:12), socket(2) ---> socket(2)
- :는 카테고리 분류가 들어감을 의미한다. 예를 들어 :12 는 컴퓨터용어(:12) 사전용 메타페이지를 참고하겠다는 뜻이다. 굳이 카테고리를 명시할 필요는 없다. 카테고리를 명시하지 않을경우에는 모든 카테고리를 뒤져서, 일치하는 단어를 찾게 된다. :이 사용되지 않는 경우는 카테고리 분류가 없음을 의미한다. 정규표현식에 대한 내용은 정규표현(:12)을 참고하기 바란다.
- 만약 해당 단어의 정보를 가진 Meta Page가 있다면, 이동을 할 것이다. 그렇지 않을 경우 페이지 만들기 페이지가 뜨게 된다.
지금 방식을 이용해서 컨텐츠끼리 잘 연결되려면 다음의 조건을 만족해야 한다는 문제점이 있다.
컨텐츠 생산에 적극적으로 참여하는 일정수 이상의 유저가 있어야 한다. 그렇지 않다면, 단편적인 정보들이 나열된 사이트가 될 확률이 크다. 방문자의 약 1% 정도가 컨텐츠를 수정하거나 생성하는데 관심을 보인다면, 이 방식은 잘 먹혀들 확률이 크다. 실제 wikipedia(:12)도 적극적으로 참여하는 유저는 1%내외일 거라고 생각된다.
그러나 내 사이트의 경우 5년간 사이트를 운영해본 결과 위키에서 페이지를 생성하는 유저는 0.1% 도 안된다. Q&A를 제외하고 보자면, 다른 사이트도 마찬가지일 거라고 생각된다.
결국 사람의 자발적인 참여에 맡기는 것만으로는 좋은 시스템을 만들수가 없다는 결론에 도달한다. 사실
참여만으로라는 것은 매우 이상주의적인 생각이다. 참여가 매우 중요하다고 생각되는 민주주의 이념도, 교통/통신시설 수많은 법/제도적인 장치가 있었기 때문에 지금 정도의 수준에 이르렀다고 판단된다.
Related Rink의 기본개념은 지금의
Meta Page를 이용하는 방식과 크게 다르지 않다. 여기에 그동안 사람이 - 거의 혼자서 했던 - 작업을 컴퓨터가 처리하도록 해서 효율성을 높이도록 할 것이다.
attachment:meta3.png
위키를 이루는 문서들이다. 이들 문서는 다음 두개의 포맷으로 저장이 된다.
- wiki 문법 : Moniwiki 고유의 문서형식으로 저장된다. 이들은 wiki 해석엔진에 의해서 HTML(:12)로 변환된다음 브라우저에 뿌려진다.
- HTML 문법 : Cache(:12)에 저장되어 있는 문서들이다. 여기에는 wiki 해석엔진에 의해서 해석이 끝난 HTML 포맷의 문서가 저장되어 있다.
Index(색인)을 만들기 위해서는 문서를 수집해야 하는데, wiki 문법을 따르는 문서를 수집할경우 wiki 문서를 해석하기 위한 엔진을 별도로 제작해야 하는 불편함이 따른다. 그러므로 해석이 끝난 HTML 포멧 문서를 기준으로 수집하도록 할 것이다.
내부의 문서만을 수집하면 되므로 일반적인 웹 검색엔진(:12)처럼 링크를 검사해서 그래프 자료구조를 가지는 webDB를 만들지는 않을 것이다. wiki의 모든 페이지는 특정 디렉토리에 파일형태로 저장되어 있으니, 이들 파일 이름을 이용해서 문서들을 순환할 것이다.
- scandir(3)등의 함수를 이용해서 wiki문서 목록을 얻어온다.
- wiki문서 목록을 순환하면서, w3m(:12)을 이용해서 HTML 테그를 제거한 plain/text 문서를 얻어온다.
# w3m -dump http://www.joinc.co.kr
- 얻어온 문서는 동일한 이름으로 파일로 저장한다.
색인기를 만들기 위해서는 우선
단어사전이 만들어져야 한다. 여기에서 필요한 단어사전은 일반문서에 대한 단어사전이 아니므로, 단순한 방법으로 만들도록 할 것이다. 사전을 위한 데이터는 Crawer를 통해 수집된 문서들이 사용된다.
- 한글의 경우 최소한의 조사만 제거한다.
- token은 다음과 같다. [ -,()\";:{}'+]
- 영어는 대소문자를 구분하지 않는다.
- 예전에 예제로 만들어본 색인기(:12)를 수정하도록 할것이다.
- 사전은 조정되어야 하며 이를 위한 인터페이스를 제작한다.
데이터는 sqlite(:12) 에 저장할것이다. 속도의 문제로 사전데이터를 DB 시스템에 넣는 경우는 없겠으나, 속도가 중요한 서비스를 할 생각은 아님으로 쉽게 구현하도록 하겠다. 수행시간이 비효율적일 경우 별도의 DB로 가져갈 수도 있다.
다음은 조사를 제거하는 간단한 코드다.
최종적인 색인 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개의 테이블로 이루어진다.
- Term Index : 색인된 단어의 목록으로 정렬되어 있다. 하나의 레코드는 다음과 같은 필드로 구성된다.
|| 필드명 || Type || 크기 || 기타 ||
Term | Char | 20 | |
DF | Int | 4 | Document Frequency |
DFP | Int | 4 | Term을 포함한 Document목록의 시작점 |
- Term Frequency : 해당 Term을 포함한 Document의 목록
|| 필드명 || Type || 크기 || 기타 ||
DID | Int | 4 | 문서번호 : 정열 |
TF | Int | 4 | Term Frequency |
- TermInfo Index : Term Index Table에 대한 Index 테이블. 64개 블럭정도로 나누어서 Term Index를 검색하는 시간을 줄인다. 64를 skip interval 이라고 하자.
|| 필드명 || Type || 크기 || 기타 ||
TermP | Int | 4 | Term Index에서의 블럭 위치 |
예를들어서
Linux라는 단어가 검색어로 주어진다면, 다음과 같은 과정을 거쳐서 Linux(:12)를 포함한 문서를 얻어오게 된다.
- TermInfo Index 테이블에서 이진검색을 이용해서 블럭값을 찾는다. 약 2번의 검색을 통해서 Large의 레코드에 있는 TermP 블럭을 검색하면 됨을 알 수 있다. Term Index 테이블에서 (skip Interval * 4) ~ (skip Interval * 5) 사이에 Linux라는 단어가 있는지 확인하면 될것이다.
- seek(2)와 간단한 수치연산을 이용해서 Term Frequency 테이블의 블럭위치를 찾아간다음 DF만큼 값들을 읽어오면 된다.
검색엔진의 가장 중요한 과제는 중요도가 높은 문서를 상위에 노출시키는 것일 것이다. 이를 위해서 Score 알고리즘과 PageRank 와 같은 것들을 이용해서 문서의 중요도를 계산하게 된다. 일반적으로 사용되는 Score 공식은
Nutch 검색엔진을 참고하기 바란다.
Score 공식은
TF * IDF로 요약할 수 있다.
Term이 몇개의 문서에서 발결되었는지와 하나의 문서에서 몇개의 Term이 발견되었는지를 곱하는 것이다.
이 방식을 사용하는 것 만으로도 문서검색의 품질을 상당히 높일 수 있지만, 커다란 문제점이 있다. 바로 문서에서 발견되는 Term의 갯수인 TF를
조작할 수 있다는 문제다. 별내용 없이 동일한 단어를 반복해서 출현하게 한다든지 하는게 대표적인 방법이다. 실제 초기 검색엔진은 이러한 TF조작에 취약성을 보여주었다. PageRank는 이러한 문제를 해결하기 위해서 구글에서 도입한 개념으로, 해당 문서를 참고하는 링크가 몇개인지를 계산한다.
좋은 문서는 많이 참고될 것이다라는 전제하에 문서의 중요도를 검사하는 방식이다.
Joinc의 경우
TF의 조작 염려가 없고, 단지 하나의 단어에 대해서만 문서의 Score를 적용하면 되므로 오직 TF만을 가지고 문서의 순위를 메길 것이다. 단 기존의 man(:12)으로 시작되는 meta page에 대해서는 가중치를 더 줘서 최상위에 노출되도록 할 것이다.
우선
사전제작을 해서, 처리해야할 Term이 몇개인지 확인하고, 사전을 수정하기 위한 웹인터페이스를 제작한다. 이들 데이터를 가지고 어떤 DB를 이용할건지, 어떤 방식을 사용할건지 (품질 우선 혹은 속도 우선)를 결정하도록 한다.
문서를
tokenizing한다음, 뒤에 붙는 조사만 제거해서 최소한의 사전데이터를 만든다. 때문에 정확하지 않은 사전이 생성될 것이다. 이것은 제공되는 인터페이스를 통해서 직접 수정하도록 한다. (아마도) 수천개 내외의 사전이 생성될 것으로 생각되니, 어느정도 수준으로 다듬는데 그리 큰 시간이 소모되리라 생각되지는 않는다. 또한 기술단어들을 중심으로 하기 때문에, 일반단어에 대한 사전정보는 중요하지 않다. 이렇게 만들어진 사전제작 프로그램은 낮은 수준의 것으로, 일반적으로 사용가능하게 하려면 많은 시간을 투자해야 할 것이다.
- token : [ -,()\";:{}'+*&]
- 유효한 단어 : [0-9a-zA-Z가-하_\.]+
- 제거할 조사 : 단어+은,는,이,가,을,으로,부터,까지,처럼,....
일단 위의 규칙으로 파싱하는 프로그램을 만들어서, 대략적으로 사전정보를 작성한뒤에 관리프로그램을 이용해서 교정을 한다. 서전데이터는 SQLite(:12)로 유지한다.
관리 인터페이스는 다음과 같은 기능을 가진다.
- 단어 목록 출력
- 단어 수정 : 오타 수정, 원형복원
- 단어 추가 : 복합명사일 경우 새로운 단어 추가 ( 예: 검색엔진시스템 = 검색엔진 + 시스템 + 검색엔진시스템)
이렇게 만들어진 사전데이터는 지속적으로 유지된다.
여기에는 단위 테스트코드들이 들어간다.
명사사전만을 유지할 것이다. Joinc의 모든 문서를 파싱하고 기본적인 조사를 제거한다음 노가다를 뛰어서 사전을 만들어가고 있다. 아래의 결과물은 완성된 사전은 아니며, 계속 수정/추가되어야 할 것이다. 우선은 아래의 단어를 이용해서 사전을 만들 생각이다.
아래의 것은 가공되지 않은 원본이다. 가공된 정보는 아래의
사전파일들을 통해 유지할 것이다.
- attachment:dic_eng.txt 영어 단어사전
- attachment:dic_kor.txt 한글 단어사전