SQL 답답

Data를 뽑은 지 일주일 째...

Database를 두고 작업 하는 걸 너무 만만하게 본 경향이 있는 듯 하기도 하다.

truncate id_table;
truncate thread_table;
truncate reply_table;

select count(distinct(id)) from id_table;

acrobat없이 pdf파일 만들기

이글의 출처는 이곳 입니다

-->
[STEP 1] 이미지 프린터 추가
1-1) 제어판 -> 프린터추가 -> 로컬검색 -> Apple -> Color LaserWrite 12/660 PS
(반드시 포스트스크립트가 지원되는 프린터를 선택한다)

[STEP 2] 인쇄 고급항목 설정
2-1) 트루타입폰트 : 소프트글꼴 다운로드
2-2) 포스트스크립트옵션에서 트루타입폰트 다운로드옵션 : 윤곽선

[STEP 3] 파일 설치
3-1) gs800w32.exe 파일 실행하여 고스트스크립트 설치 (기본값을 그대로 적용)
3-2) makepdf-0.03.exe 파일을 설치하고 "파일" 메뉴에서 "AutoConfig"를 선택(1번만)

[STEP 4] 변환
4-1) 변환하고자 하는 원본파일을 열고 위에서 설치한 ps 프린터로 "파일출력" 옵션으로 출력
--> 보통 *.prn 이나 *.ps 로 출력
4-2) makepdf.exe 파일을 실행하여 앞서 만들어진 *.ps 혹은 *.prn 파일을 마우스로 드래그하여 집어넣음

[STEP 5] 끝 (자동으로 pdf 파일 생성)

Issues in Machine Learning : Machine learning1 - 3

이번 장에서는 머신 러닝 분야에 있어서 혹은 머신 러닝을 프로젝트에 적용할 때 중요한 이슈가 되는 점들에 대해서 간단히 정리해 보도록 한다. 이 부분은 Tom M. Mitchell의 책 Machine Learning의15page에 해당하는 부분의 해석이라고 해도 무방하다.


1. 특정한 trainig examples에 대해서 범용적으로 사용될 수 있는 target function으로는 어떠한 것들이 있을 수 있을까? 그리고 충분한 training data가 주어졌다고 가정할 때, 어떤 알고리즘이 target function의 기능을 하기 위해 어떠한 setting들이 필요한가? problems와 representations의 유형들에 대해서 어떤 알고리즘들이 가장 효과적인가?

2. training data는 얼마정도가 적당한가? training data에 대해서 일반적으로 통용될 수 있는 boundary가 있는가?

3. 사전 지식이 언제, 그리고 어떻게 examples를 generalization하는데 이용될 수 있는가? 만약, 사전 지식이 잠정적으로 옳다고 생각되는 경우에도(절대적이 아닌) 도움이 될 수 있는가?

4. 가장 효과적으로 다음 training experiences를 선택하는 방법은 무엇인가? 그리고 이러한 방법이 learning problem의 복잡성을 어떻게 줄이는가?

5. learning task를 하나 이상의 function aproximation problems으로 바꾸는 가장 좋은 방법은 무엇인가?(즉, 학습을 target function을 설계하고 traning하는 실제적인 문제로 변환할 때 가장 좋은 방법은?) 시스템이 학습해야 하는 어떤 특별한 function들이 있는가? 그리고 이러한 과정은 자동적으로 수행되어질 수 있는가?

6. learner가 자동적으로 문제들을 target function으로 표현하고 학습하도록 할려면 어떻게 해야 하는가?

이클립스 디버그

언제까지 System.out.println()으로 버그를 잡으려 할 것인가.

이클립스에서 VC처럼 디버깅을 하자.


사실 디버깅은 처음 접하는 사람에겐 쉽지 않다.
책을 보고 따라하면 너무나 쉬운데 막상 프로그래밍하면서 적용하다 보면 애를 먹고는 한다.
그러다 과감하게 난 System.out.println()의 강력함을 알고 있다며 중요 요소에 값을 찍는다.
그러다 어디가 어디서 나오는 값인지 몰라서 갑갑하게 돼고,
그러다 이번 프로그래밍엔 문제가 많았어. 다시 짜지 뭐. 난 부지런하니까... 하게 돼고...
그러다 다시 디버깅 책을 찾아 따라하게 돼고....

그렇지만, 언젠가 좋아지겠지 하며 오늘도 이런 악순환을 계속해본다.
정말 언젠간 좋아지겠지.


이클립스에서 디버깅을 해본 사람은 알 것이다.
무료인데도 정말 너무나 훌륭한 녀석이다.

정말 고마운 분들이 세상엔 많이 계시고, 그 분들로 인하여 영광을 입은 이클립스 사용자들이 이클립스에서 디버깅을 위해서 가장 먼저 해야 할 것은 어디가 문제가 될 것인가를 아는 눈이다. 이건 그 사람의 내공의 깊이에 달려있는 문제이긴 하지만, 효과적인 툴의 도움을 받는다면 더욱 문제 해결의 실마리를 찾기 쉽게 된다.

.이클립스에서 디버깅을 하기 위해서 가장 먼저 문제가 될 만한 곳을 찾아라.
->결과(console 창)가 보이는 화면에서 Exception이나 오류가 발생했을 때의 해당 위치,
->논리적으로 뭔가 애매 모호한 프로그램 부근
->업무 시간이 끝날 때 즈음 급하게 나갈려고 대충 짠 부근
등이 주요 타겟이다.

1.브레이크포인트
의심이 되는 위치에 추가한다.
- 변수명에 설정하면 프로그램에서 이 변수를 사용할 때마다 프로그램이 정지한다.
- 프로그램 라인에 설정하면 해당 프로그램 라인을 지날 때 프로그램이 정지한다.

브레이크 포인트를 여러개 추가한 상태에서 포인트는 그대로 둔채 몇개를 잠시 끄고 싶을 때는 마우스 왼쪽 클릭해서 Disable Breakpoint를 설정하면 된다.(반대는 Enable Breakpoint)

2.Hit Count
브레이크 포인트가 추가되었을때 변수나 프로그램 라인이 몇번 째 호출 되었을때 멈추라는 명령은 Hit Count를 설정함으로서 수행할 수 있다. 이런 경우는 보통 for나 while문에서 몇번의 루프 반복 이후에 문제가 발생할 때 보다 편리하게 이용할 수 있다. '한 100번 쯤 뒤에 문제가 발생하던데' 하면 Hit Count를 95정도로 설정하면 될 테지.

3.멀티 쓰레드 디버깅
멀티 쓰레드 디버깅을 해보신적이 있으신가... 그렇다면 이 문서 자체가 유용하지 않으실 정도로 내공이 쌓인 분이시겠지만... 멀티 쓰레딩을 디버깅하는 아픔을 겪어보신 분이 아니라면, 그런 문제에 부딪히기 전에 이클립스에서 가상 머신(VM)을 아예 멈춰서 전체 쓰레드 동작을 정지시키는 훌륭한 옵션이 있음을 꼭 알고 계시길 바란다.
이 기능은 breakpoint를 설정한 상태에서 컨텍스트 메뉴에서 Suspend VM을 선택하면 된다. Suspend Thread는 원래대로 해당 Thread만 멈추게 된다. 혹 이해가 잘 안되는 사람을 위해 추가로 얘길 한다면 일반적으로 Thread programming을 하지 않고 static void main()을 이용한 기본적인(?) 프로그래밍을 하는 경우는 main이라는 one Thread만 동작하기 때문에 Suspend Thread나 Suspend VM이나 똑같은 작동을 한다.(신경쓰지 않아도 된다는 얘기다.)

4.스텝 단위 디버깅
성격이 급하신 분들이나, VC를 사용하다 이클립스를 쓰는 분들은 당장 이것들이 필요할 것이다.
Step Into(F5키):프로그램을 한 스텝진행, 다음 실행 문이 함수 안이면 함수 안으로 들어감.
Step Over(F6키):함수 호출을 지나치고 현재 위치에서 한 스텝씩 진행
Step Return(F7키):현재 함수 끝까지 바로 가서 리턴한 후 함수 호출부로 되돌아 간다.
Resume(F8키):멈추어 있던 쓰레드를 다시 진행시키고 다음 브레이크포인트까지 실행
Suspend:쓰레드를 일시 정지한다. 강제로 breakpoint를 현재 수행문에 지정한 것과 같다.
Drop to Frame:선택한 스택 프레임의 첫 행으로 실행 포인트를 옮긴다. 특정 함수를 실행하다 그 함수의 처음부터 다시 디버깅하려고 할때.
Terminate:종료

Run to Line(Ctrl+R):쓰레드가 정지된 상태에서 테스트 하고 싶은 곳을 에디터로 소스에서 선택한 뒤 Run to Line을 실행 하면 그 곳까지 프로그램 수행 후 자동 정지한다.

5. 스텝 필터링
F5키를 눌러 한 스텝씩 진행하다 보면 java가 제공하는 라이브러리 내부로 들어가는 경우가 발생한다. F6만 누른 다면 문제가 발생하지 않겠지만, 내가 만든 함수 안으로는 들어가보고 싶을 때 신경써서 F5, F6, F7을 누르는 건 상당히 피곤한 일이다. 이럴 때 사용할 수 있는 기능이 스텝 필터링이다. 말 그대로 한 발짝 움직일 때 하지 않았으면 하는 일을 지정해 주는 것이다. 이를 위해서 스텝 필터를 먼저 설정해야 한다.

6.Display
디버깅 중, 내가 만든 함수를 이용해 현재의 결과를 보고 싶어 할 수 있다. 예를 들면, isInteger()라는 함수를 만들었고, 이 함수가 함수 인자가 Integer형인지를 리턴 한다고 할때 디버깅 상황에서 현재 상태에 이 함수의 결과를 알고 싶다면, 디버깅을 중단하고 나가서 isInteger()코드를 추가하지 말아라.
단지, Window메뉴의 Show View메뉴의 Display를 켜고 isInteger()를 치고 눌러보자.
이 Display는 내가 만든 함수 뿐만 아니라 확인하고 싶은 수식을 직접 입력할 수도 있다.

7.Drop to Frame
F6키를 사정없이 눌러서 내가 보고 싶어하는 소스 코드 부분을 지나친 적이 있는가. 이럴 때 당신에게 필요한 기능이 Drop to Frame이다. Drop to Frame을 사용하면 현재 메서드의 첫 행으로 되돌아 간다.

8.Detail Formatter
String 객체의 배열을 다루는 class를 사용할 때 너무 많은 String 배열로 인해서 내가 원하는 부분을 찾는 데 어려웠던 적이 있는가? 예를 들면, 한 String 객체의 전체 문자열을 각 array 별로 보여주도록 (ex)S[0] = "나는 언제나")) 하기를 바랬던 적이 있냐 하는 말이다. 이럴 경우 Java메뉴의 Debug메뉴의 Detail Formatters를 통해서 내가 원하는 형태로 객체가 표시되도록 할 수 있다. 복잡한 코드에서는 강력한 기능을 발휘하는 메뉴이다.

소셜 네트워크 서비스 관련 글

이 글은 IR 그룹의 하얀 눈길님이 작성하신 글입니다.

원문은 여기에 있습니다.




소셜 네트워크 서비스에 대한 관련글들입니다.지속적으로 추가할 예정입니다.

* 소셜 네트워크 서비스의 7가지 요소
* 소셜 네트워크와 광고
* 소셜네트워크서비스 측면에서 라이클 기획의도
* 블로그, 소셜네트워크는 어떻게 진화할 것인가?
* 주목받는 해외서비스로 알아본 2007년 인터넷 트렌드
* 인터넷 북마크 서비스 딜리셔스를 아세요?
* 일본의 신세대 인터넷 기업들
* 웹2.0과 소셜 네트워크
* [커버스토리]누가 웹2.0 비즈니스 주도하는가?
* 소셜북마크 사이트와 포털의 소셜북마크 서비스의 차이

* 마가린 : 소셜네트워킹 태그
* 올블로그 : 소셜네트워크 태그

trie

IR group의 하얀 눈길님이 적으신 글 중 trie에 대한 설명이 있어서 스크랩 해 왔다.

원문은 여기서 볼 수 있다.



array-based trie
trie란 바이너리 트리의 특이한 경우로 보면 되겠다. 보통 문자열을 처리하기 위해 사용되며, 속도가 빠르고 공간을 적게 차지하기 때문에 검색엔진에서는 사전과 역화일의 인덱스 정보를 저장하는데 주로 사용한다. 여기서 구현할 trie의 구조는 다음과 같다.

예) “추석, 추억, 가을, 가나, 가나다라”을 저장하는 트라이

문자열에서 각 음절을 하나의 depth(자식노드)로 볼 수 있으며 같은 depth의 음절은 바로 앞의 음절이 같을 경우 형제노드로 볼 수 있다.
위 예에서 보면 처음 “추석”이 저장될 때 ‘추’ 가 루트가 되어고 ‘석’이 추의 자식노드로 저장된다. 다음에 “추억”이 저장될 때 ‘추’가 루트에 있으므로 첫음절은 같은 부모노드를 공유하고 ‘억’을 자식노드로 저장한다. 이때 자식노드에 이미 ‘석’이 있고 ‘석’과 ‘억’은 형제노드 관계에 있으므로 ‘석’의 오른쪽 노드에 ‘억’을 저장하게 된다.
다음에 “가을”을 저장할 때 ‘가’는 첫음절이므로 루트노드와 비교를 하고, 이미 ‘추’가 있으므로 ‘추’와 ‘가’는 형제노드가 되며, ‘가’가 더 작은 값이기 때문에 ‘추’의 앞에 ‘가’를 삽입하고 ‘가’의 오른쪽 노드를 ‘추’로 지정해 준다. 그리고 나서 ‘을’을 저장할 때 ‘가’의 자식노드가 되므로 왼쪽 노드를 추가하고 ‘을’을 저장한다.
다음에 “가나”가 입력되면, ‘가’가 루트노드에 존재하므로 ‘을’을 저장할 때 ‘가’와 같은 부모를 갖게 하고 자식노드를 삽입한다. 이때 자식노드에 이미 ‘을’이 있으므로 ‘나’와 ‘을’은 형제관계가 되고 ‘나’를 ‘을’ 앞에 삽입하게 된다.
“가나다라”가 입력되면, 마찬가지 방식으로 trie에 저장되게 된다.

웹 로봇 3 - 로봇 배제 표준

이 요약은 사용할 수 없습니다. 이 글을 보려면 여기를 클릭하세요.

웹 로봇 2 - HTML Parser

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.

소스를 vc++6.0로 바꾸려니 꽤나 갑갑하네요..
프로젝트 압축화일은 자료실에 올리겠습니다.

=================================================================================
HTML이란 Hypertext Markup Language의 약자로서 플랫폼에 의존되지 않는 하이퍼텍스트 문서를 생성할 때 사용되는 구조화된 마크업 언어이다.
현재 버젼 4.01까지 나와 있는 상태이며, 4.01에 대한 자세한 내용은 http://www.w3.org/MarkUp/를 참조하기 바란다.
또한 RFC 1866 문서(http://www.rfc-editor.org/rfc/rfc1866.txt)를 보면 HTML에 대한 문법 및 구조를 정확히 파악할 수 있다.

이 강좌에서는 문법에 대해서 논하기 보다 파서를 구현함에 있어서 알아야 할 기본적인 구조에 대해서만 설명하겠다. 프로그램은 c++로 구현하겠다. 참고로 필자는 c++을 c처럼 쓰는 사람이라 c++에 대한 오류나 더 쉬운 방법이 있다면 제안해 주기 바란다.

다음 예를 보자.

<!DOCTYPE html PUBLIC "-//IETF//DTD HTML 2.0//EN">
<title>HTML 테스트</title>
<p>테스트 페이지입니다.<em>&#42;^_^*</em></p>

예1. html 코드 예제

위 예1. 을 파서가 해석한다면 다음과 같은 형태로 인식하게 될 것이다.

1. 시작태그 : title
2. 데이타 문자들 : "HTML 테스트"
3. 종료태그 : title
4. 시작태그 : p
5. 데이타 문자들 : "테스트 페이지입니다."
6. 시작태그 : em
7. 데이타 문자들 : "*^_^*"
8. 종료태그 : em
9. 종료태그 : p

처음 "<!DOCTYPE..." 은 주석이므로 큰 의미가 없다. 단지 사용자 에이전트가 알 수 있도록 HTML의 버젼과 범용적인 정보를 표시한 것이다. 여기서 7의 항목은 HTML을 위해 정의된 SGML 문법에 따라 *가 "*"로 변환 된 것이다.

위 시퀸스들을 파싱하게 되면 다음 구조가 된다.

도표 1을 보면 html 자체를 하나의 트리로 파싱될 수 있음을 알 수 있다.
HTML, HEAD, BODY 태그는 예1에 존재하지 않지만 HTML 문법상 기본적인 구조를 이루는 것이므로 파싱된 결과에 태그는 없다 하더라도 반영된 것을 볼 수 있다. 이런 식으로 HTML 전체 문서를 파싱하여 트리를 만드는 것으로 파싱 프로그램을 구현하도록 하겠다.

HTML의 기본적인 구조가 있다고 하더라도 원문에 없을 경우 뼈대를 생성할 이유는 없다고 본다. html 문서를 만드는 대부분의 사용자들이 이런 뼈대에 별로 민감하지 않다. 없는 경우도 많고 어떤 경우는 HTML 태그 자체도 여러번 나타날 수 있다. 그래서 이 강좌에서 구현할 파서를 위해 도표1 을 좀더 단순화 하겠다.

도표 2.를 보면 예1의 시퀸스와 부합되어 더 쉽게 이해할 수 있을 것이라 본다.

불필요한 뼈대를 모두 제거했다.

그리고 태그들의 정보와 문자들을 단순한 트리에 연결시킨 것이다.

다음 예2는 예1을 좀더 확장한 것이다.

<title>HTML 테스트</title>
<p id=t1 align=right>테스트 페이지입니다.<em>&#42;^_^*</em></p>

예2. 확장된 HTML 코드 예제

예2에서 확장된 것은 p 태그에 대한 것이다.

태그는 속성을 가질 수 있으며 여러개의 속성을 가질 경우 위 예와같이 계속적으로 나열하여 태그를 구성할 수 있다.

이러한 태그의 속성까지 파싱한 것이 다음 도표 3이다.

다음 그림 도표 3을 보자.

우리의 최종 목표는 도표3과 같은 형태로 파싱하기 위한 파서를 만드는 것이다.

도표 3의 트리는 이진트리로서 왼쪽 노드는 다음 태그를 가리키게 되고, 오른쪽 노드는 현재 태그의 속성을 가리키게 된다. 하나의 오른쪽 노드(속성)는 왼쪽 노드를 가질 수 없으며 다음 속성을 가리키기 위해 계속 오른쪽 노드만 추가하게 된다.

알고리즘은 다음과 같다.
1. 원문에서 처리되지 않은 처음 문자를 읽는다. 그렇지 않으면 종료한다.
2. 공백이면 스킵하고 1로 돌아간다.
3. 종료태그이면 스킵하고 1로 돌아간다.
4. 유효한 시작태그이면 트리에 새로운 태그노드를 삽입한다. 그렇지 않으면 6으로 건너뛴다.
5. 태그 속성을 파싱하여 태그노드에 속성을 연결한후 1로 돌아간다.
6. 데이타 문자열에 현재 문자를 추가한 후 1로 돌아간다.

그럼 지금 부터 실제 코드를 보자.

사실 HTML Parser와 관련된 많은 오픈 소스들이 배포되었고 좋은 성능을 내고 있다. 실제 개발 과정에서는 이러한 라이브러리를 찾아 써도 상관 없지만, 기본적인 개념을 알고 있어야 효과적으로 제어하고 활용할 수 있다.

파싱 트리를 표현하기 위한 클라스는 다음과 같다.

class HtmlTag
{
public:
// Member Variables
HtmlTag *nextHtmlTag; // 다음번 HtmlTag를 가리킴
TagVar *firstTagVar; // HtmlTag안의 첫번째 Variale이 저장될 TagVar를 가리킴
TagVar *lastTagVar; // HtmlTag안의 첫번째 Variale이 저장될 TagVar를 가리킴

HtmlTag();
~HtmlTag();

// get Function
TagVar *getTagVar(char *szName) const;
char *getTagName() const;

// set Function
int setTagName(char *name);

// ETC.
int addTagVar(TagVar *tv);
void print() const;

private:
char szTagName[NAME_SIZE]; // Tag Name 저장

};

태그의 속성을 표시하기 위한 클라스는 다음과 같다.

class TagVar
{
public:
// Member Variables
TagVar *nextTagVar;

TagVar();
~TagVar();

// set Function
int setVar(char *var);
int setVal(char *val);

// get Function
char *getVar() const;
char *getVal() const;

private:
char *szVar, *szVal; // 변수이름과 값을 저장

};

HtmlTag 클라스는 한개의 태그에 대한 정의이다. 이 클래스의 내용을 보면 다음 태그를 트리로 연결하기 위해 멤버변수로 HtmlTag 타입의 nextHtmlTag 포인터를 가지고 있다. 이는 도표 3.의 왼쪽 노드가 된다.

태그의 속성을 표시하기 위해 TagVar 클라스 포인터를 멤버 변수로 가지고 있다. firstTagVar 포인터가 바로 그것이며 이 녀석이 태그의 첫번째 속성을 가지게 된다.
TagVar 클래스의 내용을 보면 다음 속성을 가지기 위해 nextTagVar 포인터를 멤버변수로 가지고 있는 것이 보인다. 이것이 도표3에서의 오른쪽 노드가 되는 것이며 실제는 링크드리스트로 구현된다.

다음은 위 두개의 클래스를 묶어서 전체 HtmlParser 클래스로 정의된 클래스이다.

class HtmlParser
{
public:
HtmlTag *firstHtmlTag; // 문서의 첫번째 HtmlTag를 가리킴.
HtmlTag *lastHtmlTag; // 문서의 첫번째 HtmlTag를 가리킴.

HtmlParser();
~HtmlParser();

int exeParser(char *szHtmlTxt);
void print() const;

private:
int addHtmlTag(HtmlTag *ht);
HtmlTag *parseHtmlTag(char **buf);
HtmlTag *parseTextData(char **buf);
HtmlTag *parseComment(char **buf);
int parseVarVal(HtmlTag *ht, char **buf);
};

HtmlParser 클래스는 Htmltag 클래스를 멤버변수로 가진다. 이 멤버는 html의 처음 태그 위치를 나타내게 된다. lastHtmlTag 멤버는 큰 의미는 없다.

실제 파싱을 수행하는 메소드가 exeParser로서 html 문자열을 입력받아 순차적으로 처리하게 된다. 이 메서드가 위에서 설명한 파싱 알고리즘을 처리하는 부분이다.
print 메소드는 결과 검증을 위해 화면에 출력하도록 만든 테스트용이다.
private의 메소드들은 모두 exeParser 메소드에서 필요에 의해 호출하는 함수들로 세부 내용은 피하도록 하겠다.

다음은 exeParser의 내용이다.

int HtmlParser::exeParser(char *szHtmlTxt)
{
HtmlTag *ht;

if(!szHtmlTxt)
return 0;

while(szHtmlTxt)
{
if(*szHtmlTxt == '' *szHtmlTxt == EOF)
break;
ht = NULL;
skipBlank(&szHtmlTxt);

if(!*szHtmlTxt)
break;

if(*szHtmlTxt == CLOSE_TAG)
{
szHtmlTxt++;
skipBlank(&szHtmlTxt);
continue;
}
else if(*szHtmlTxt == OPEN_TAG)
{
szHtmlTxt++;
skipBlank(&szHtmlTxt);

switch(whatIsTag(szHtmlTxt))
{
// COMMENT TAG
case COMMENT_TAG:
ht = this->parseComment(&szHtmlTxt);
break;

// 여기에선 VALID, INVALID 모두 처리한다.
case VALID_TAG:
case INVALID_TAG:
ht = this->parseHtmlTag(&szHtmlTxt);
break;

// ETC.
default:
continue;
}
}
// OPEN_TAG가 아니면 TEXT_DATA로 간주한다.
else
ht = this->parseTextData(&szHtmlTxt);

if(ht)
this.addHtmlTag(ht);
}

return 1;
}

함수에서 인자로 받는 것은 HTML 스트링이다.
while 루프를 보면 처음에 skipBlank 함수가 있다.

이것은 현재 처리중인 문자가 공백인 것을 무시하고 다음 문자로 넘어가는 것이다.
'CLOSE_TAG'는 '>'를 재정의 한 것이다. OPEN_TAG는 '<'를 재정의 한 것이다. 태그를 분석하는 단계를 3가지로 분류하여 두었다. if 구문을 보면 알 수 있듯이, CLOSE_TAG, OPEN_TAGE, 그외의 일반 데이타로 분리하여 조건문으로 처리하였다. 1. 처음 시작하자마자 CLOSE_TAG가 나타난다면 태그로서 의미를 가지지 않는 일반 텍스트와 동일하다고 보고 루프의 처음으로 돌아가게 된다. 2. OPEN_TAG가 나타나게 되면 OPEN_TAG 바로 다음에 공백이 나올경우를 위해 skipBlank를 한번더 해주고 실제 태그를 파싱하게 된다. Comment tag같은 경우 모양이 약간 틀리기 때문에 case 구문으로 구분하여 별도 처리하였다. 유효한 태그인지 아닌지는 parseHtmlTag 함수에서 처리하며 유효할 경우는 생성된 태그 클라스를, 그렇지 않으면 널값을 리턴한다. 3. Open 태그가 아닐경우는 Text 데이타로 간주하고 다음 Open Tag가 나타날 때 까지를 파싱하여 결과를 저장해 둔다.

마지막으로 위 3가지 조건을 처리하였을 때 새로 생성된 태그가 있다면 html 클라스에 새로운 태그를 추가한다. 이 역할을 addHtmlTag 함수가 수행하게 된다.

Html을 파싱하는 전체 골격은 위와 같이 아주 간단하다.
그렇다면 Valid, Invalid, Text 태그를 파싱하는 함수들을 살펴보자.

우선 parseHtmlTag 함수이다.

HtmlTag * HtmlParser::parseHtmlTag(char **buf)
{
HtmlTag *ht;
char name[NAME_SIZE+1], *tmp;
int nIdx=0;

// Tag Name이 나오기 전까지의 공백 문자를 무시한다.
skipBlank(buf);

// Tag Name을 저장한다.
// Tag Name은 공백이 나오거나 CLOSE_TAG '>'가 나오거나
// '' 문자가 나올때까지.... 읽어서 저장한다.
*********************************************************/
while(**buf != ' ' && **buf != ' ' && **buf != CLOSE_TAG &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;& **buf)
{
// Tag 중간에 새로운 Tag가 시작하면...
if(**buf == OPEN_TAG)
{
tmp = *buf;
(*buf)++;
skipBlank(buf);
if(whatIsTag(*buf) == VALID_TAG)
{
*buf = tmp;
ht = new HtmlTag();
if(!ht)
return NULL;

// 생성된 HtmlTag의 이름을 세팅.
name[nIdx] = '';
ht->setTagName(name);
ht->nextHtmlTag = NULL;
return ht;
}

*buf = tmp;
}

name[nIdx++] = **buf;
(*buf)++;

// 이름이 NAME_SIZE보다 커질경우 예외처리....
// CLOSE_TAG가 나올때까지.. 무시한다!
if(nIdx >= NAME_SIZE)
{
skipUntilCloseTag(buf);
return NULL;
}
}

ht = new HtmlTag();
if(!ht)
return NULL;

// 생성된 HtmlTag의 이름을 세팅.
name[nIdx] = '';
ht->setTagName(name);

this->parseVarVal(ht, buf);

return ht;
}

처음 while 루프에서는 태그의 이름을 잘라내기 위한 부분이다. '<' 다음에 또다시 '<'가 나오는 경우 처리를 위해 한번더 조건문 처리를 해 주었다. while 루프의 조건이 인 경우 ' ' 인 경우 CLOSE_TAG 인경우, NULL인 경우 까지를 잘라낸다. 한 문자씩 잘라내면서 name 배열에 저장하여 두고 만일 태그 명의 길이가 너무 길어지게 되면 태그로 보지 않고 버리게 된다. while 루프가 끝나게 되면 태그명을 제대로 잘라낸 것이다. 이후에 HtmlTag 클라스를 하나 할당 받은후 setTagName 함수로 태그명을 세팅하고 태그의 하위 변수들이 정의되어 있다면 parseVarVal함수를 사용하여 해당하는 변수들을 잘라내고 세팅하게 된다.

다음은 Text 데이타를 파싱하는 함수이다.

HtmlTag * HtmlParser::parseTextData(char **buf)
{
char *begin, *end, *szVal;
HtmlTag *ht;
TagVar *tv;
int nSize;

skipBlank(buf);
if(**buf &&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; **buf != OPEN_TAG)
{
begin = *buf;

while((end=getTerm(buf, "<"))) { (*buf)++; skipBlank(buf); if(**buf == '<') continue; if(whatIsTag(*buf) != INVALID_TAG) break; } *buf = end;

if(!begin)
return NULL;
if(!end)
{
szVal = new char [strlen(begin)+1];
if(!szVal)
return NULL;
strcpy(szVal, begin);
}
else
{
nSize = (unsigned int)(end) - (unsigned int)(begin);
if(nSize < 1)
return NULL;
szVal = new char [nSize+1];
if(!szVal)
return NULL;
strncpy(szVal, begin, nSize);
szVal[nSize] = '';
}

// 새로운 태그 추가
ht = new HtmlTag();
if(!ht)
{
if(szVal)
delete szVal;
return NULL;
}
ht->setTagName("TEXT_DATA");
ht->nextHtmlTag = NULL;

// 태그에 텍스트 데이터 연결
tv = new TagVar();
if(!tv)
{
if(szVal)
delete szVal;
if(ht)
delete ht;
return NULL;
}
tv->setVar("TEXT");
tv->setVal(szVal);
tv->nextTagVar = NULL;
ht->addTagVar(tv);
delete szVal;
}
return ht;
}

이 함수의 용도는 텍스트 데이타도 하나의 태그로 인식하도록 하기 위한 함수이다.
그래서 태그명을 'TEXT_DATA'로 붙여주고, 실제 데이타를 TEXT_DATA 태그의 한 변수로서 'TEXT'라는 변수를 부여하고 이 변수의 값에 실제 데이타를 넣게 된다.
이러한 복잡한 과정을 거치지 않고 직접 넣어도 무방하겠지만 전체 html 트리를 순회하는 동안 모든 태그들을 HtmlTag라는 클라스 하나로 제어하기 위해 이런방식으로 통일하였다.
함수 내부에서 특이할 만한 사항은 택스트 태그가 종료되는 시점은 html 문자열의 끝이나 OPEN_TAG가 나타나는 시점이라는 것이다. while 루프 안에서 이러한 위치를 찾은 후
실제 태그를 parseHtmlTag와 같은 방식으로 추가해 주게 된다.

여기까지 파싱 방법이나 소스상에 중요한 부분에 대한 설명을 마치도록 하겠다.
세부 내용은 실제 소스를 자료실에 올려 놓을 예정이니 참고하기 바란다.
필자는 로봇 프로그램을 작성할 때 이 소스를 개선하여 html 파싱을 전담하도록 하였다.
성능은 그리 빠른 편은 아니나 앵커를 추출하거나 기타 부가 정보를 추출할 때 아주 쉽게 구현 할 수 있었다.
무엇보다 기존 모듈이나 소스를 파악해서 내 것으로 소화하는 것보다 내 맘대로 만든 것이라 내맘대로 조작하는데 편해서
html 파싱에 관련한 부분이 필요하면 이 소스를 응용하고 있다.

이 프로그램은 사실 최적화 된 것이 아니며 여러 부분에서 성능 개선의 여지가 있다.
이런 것은 개발자들이 실제 사용하면 해결해 보는 것도 재미있을 것 같다. ^_^
끝.

==============================================================================================

오늘 강좌는 여기서 끝내겠습니다.
이론과 소스를 설명하려니 꽤 양이 많아졌습니다. 첨부터 훓어보니 사실 그리 많은 내용이 아닌듯 하긴 하네요...
물론 버그도 있습니다~ ^_^; 알아서 해결해 보시길..

그럼 좋은 하루 되세요~

웹 로봇 1 - 개요

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.





웹 로봇에 대한 강좌를 시작하겠습니다.
대용량 웹문서 수집용 분산처리 로봇을 구현 하려면 사실 많은 부분에서 어려움이 있습니다. 필요한 장비도 없는 실정이네요.. T.T 그래서 최종 목표를 멀티쓰래드를 활용한 기본적인 로봇구현으로 정하겠습니다.차근차근 한단계씩 밟아가 보지요...

강의 계획은 다음과 같습니다.
1. 개요
2. html 기본구조 및 파서 작성
3. http 구조
4. 로봇 배제표준
5. 기본 라이브러리 작성 - 동적 array, tree, trie, socket, thread
6. 소켓 타임아웃에 대하여
7. single thread robot
8. multi thread robot
9. 대용량 처리를 위한 자료구조 제안

적어보니 꽤 양이 많네요...한달 분량은 되지 않을까 싶습니다.
프로그램 부분은 리눅스에서 gnu c++을 사용할 예정입니다. 문제는 제가 장비가 없네요.. T.T실제 돌려보지는 못하고.. 있는 소스를 설명하는 수준으로 진행하겠습니다.물론 예전에 잘 돌던 프로그램이구요~ ^_^

각설하고...강의를 시작하겠습니다.

==================================================================================================웹 로봇을 개발하자!

1. 개요
검색엔진에서 말하는 로봇이란 다음과 같이 정의할 수 있다.

컴퓨터를 사용하여 주기적, 비 주기적으로 데이타를 능동적으로 수집하는 자동화된 프로그램.

여기서 "수많은 정보"들은 단순한 HTML문서가 될 수도 있고, XML, 워드문서, 이미지, 멀티미디어 정보, DB 데이타등도 포함된다. "주기적, 비주기적"이란 말은 로봇이 특정 대상을 지속적으로 감시하면서 데이타를 수집할 수도 있고, 그렇지 않을 수도 있다는 것이다. "능동적으로 수집"한다는 의미는 어떤 정보로부터 새로운 정보를 얻어내어 연관된 다른 정보를 스스로 찾아다닌다는 것을 말한다.
한가지 예를 들면, 매체사로부터 뉴스기사를 전송받아 DB에 저장하는 데몬이 있다고 하자. 이러한 녀석도 데이타를 수집하기 위한 장치임에 분명하나 로봇이라 부르지 않는다. 이유는 매체로부터 전송된 데이타를 수동적으로 받는 입장이며, 새롭게 받은 데이타에서 추가적인 정보를 유추해 내어 새로운 정보를 찾아내지도 않는다. 물론 로봇도 새로운 정보를 찾지 않고 이미 입력된 몇몇의 시드만을 사용하여 데이타를 수집하도록 할 수 있다. 그렇더라도 수집의 주체인 로봇 자체가 능동적으로 해당 데이타를 찾아가서 전송받게 된다는 것이 위의 예와는 차이라 볼 수 있다. IE와 같은 웹브라우져도 넓은 의미에서는 로봇이라 볼 수 있다. 보통은 agent라는 용어를 쓰기도 하지만 브라우져 또한 로봇과 다를게 없다. 위 의미에 맞춰 생각해보면 이해할 수 있으리라 본다.

위 의미를 좀더 확장하여 웹로봇을 정의하면 다음과 같이 말할 수 있겠다. 인터넷상에 존재하는 수많은 정보들을 주기적 또는 비 주기적으로 수집하는 자동화된 프로그램.

위 정의의 의미는 로봇은 로봇인데 특정한 DB에 직접 접속하여 정보를 수집하는 것이 아니라 인터넷을 사용하여 인터넷 상에 존재하는 정보를 수집하는 로봇을 웹로봇이라고 보겠다는 것이다.
얼마전 필자는 로봇과 크롤러, 에이전트의 차이점에 대한 질문을 받은 적이 있다. 솔직히 세분하자면 용어를 사용한 사람들의 말을 직접 들어 봐야 할 것이다. 그러나 일반적인 통념상 로봇, 크롤러, 에이전트, 게더러 등등은 동일한 말이라 봐도 무방할 것이다. 단지 세분화 한다면 인터넷의 데이타를 수집하는 것은 웹로봇, 웹크롤러 등등으로 말하고 DB정보를 수집하는 것을 DB 로봇, DB 크롤러등으로 명명하는 것이 보통이다.

* 다음은 "효율적인 웹 로봇의 설계 및 구현에 관한 연구" 1997. 심해청 학위논문에서 발취한 내용이다. 웹로봇의 필요성에 대한 간략한 설명이라고 보면 되겠다.
하루가 다르게 변하는 정보화 사회에서 인터넷이라는 거대한 공간 속에서 노아의 홍수와 같은 엄청난 정보가 넘쳐나고 있다. 이러한 정보의 홍수 속에서 사용자가 원하는 정보를 찾는다는 것은 모래사장에서 바늘 찾기 보다 더 어렵다. 검색도구는 이렇게 찾기 힘든 정보를 쉽게 찾을 수 있도록 도와주는데 큰 도움을 주고 있으며 그 위치는 하루가 다르게 높아가고 있다. 그래서 인터넷 상에는 많은 검색 도구들이 등장하고 있다. 이러한 검색 도구들은 수동, 또는 웹로봇을 이용하여 자동으로 정보를 수집하는데 지금은 거의 웹 로봇을 사용하고 있다.그러나 대부분 상업적인 목적으로 인하여 그 기술이나 특징에 대해 공개되지 않아 검색 도구의 특징을 보고 어림잡을 뿐이다. 검색 도구들은 보통 정보를 수집하기 위한 웹 로봇(Web Robot, Robot agent)과 수집되 자료에서 정보를 검색하는 검색엔진 부로 이루어져 있다.검색엔진부는 정보검색이라는 분야로서 많은 연구가 이루어져 있으나 웹로봇은 그다지 맣은 연구가 이루어지지 않았다. 또한 이러한 웹로봇은 쉽게 작성할 수 있다는 이유로 아주 작은 부분으로 취급되어 지기도 한다. 그러나 검색엔진부는 수집된 자료가 있어야만 수행되어질 수 있으며 수집된 자료가 빈약할 경우 당연히 서비스의 질이 떨어지게 된다. 그러므로 웹 로봇의 위치는 아주 중요한 위치에 있는 것이다.

* 웹로봇의 구성요소
웹로봇에는 HTML 파서, HTTP 프로토콜, 소켓, 쓰래드, 대용량 데이타 저장 구조 등이 필요하다. HTML 파서는 html안에서 새로운 url을 추출하여 반복적인 데이타 수집을 하기 위해 필요하다. 웹로봇용으로 쉽게 파서를 구현하려면 strstr함수를 사용하여 href만 찾아내어 문자열을 짤라내어 버리면 된다. html 구조 자체가 간단하다 하더라도 초보자가 html 파서를 제작하는 것은 조금 버거운 일일 수 있다. 그래서 많은 프로그래머들이 공개된 소스나 모듈들을 많이 사용하고 있다. 그러나 이 강의에서는 html 파서를 직접 제작할 것이다. 누누히 강조하지만 원리를 모르는 상태에서 있는 모듈을 쓰기만 하는 프로그래머는 프로그래머가 아니다. 단지 코더일 뿐이다. HTTP 프로토콜은 웹로봇 자체가 인터넷의 정보를 수집하는 기능이기 때문에 반드시 필요한 것이다. 이 프로토콜도 아주 잘 만들어진 오픈소스나 모듈들이 많이 있다. 그러나 만들것이다. ^_^; 소켓은 HTTP프로토콜 자체가 tcp/ip기반으로 동작하는 프로토콜이므로 반드시 필요한 부분이다. tcp/ip에 대해서는 본 강의 범위를 넘어서게 되므로 관련 책자를 참고하기 바란다. 이 강의에서는 소켓라이브러의 사용법과 멀티 쓰래딩 시의 타임아웃 처리에 대해 집중적으로 다룰 것이다. 쓰래드는 고속 처리를 위해서는 반드시 사용해야 할 구조이다. 웹로봇의 특성상 수천만건의 데이타를 빠른 시일안에 수집하기 위해서는 단일 쓰래드로는 무리가 있다. 만일 단일 쓰래드로 로봇을 만든다면 하루종일 데이타를 수집해도 10000~30000개의 문서를 수집하기도 힘들 것이다. 대용량 데이타 저장구조는 소량의 데이타를 수집할 목적의 로봇이라면 필요치 않다. 그러나 웹로봇의 경우는 앞서말한 모든 기술적 이슈보다도 오히려 큰 문제로 대두된다. 웹로봇 수행시간에서 가장 많은 시간을 소모하는 것이 url을 저장하고 관리하는 부분이다. 보통 천만개의 문서를 수집한다면 처리해야 할 url의 개수는 적개는 수억에서 많게는 수십, 수백억개의 url이 될 수 있다. 이는 개수 뿐만이 아니라 용량에도 아주 많은 영향을 받게 된다. 본 강의에서는 대용량 데이타 저장구조에 대한 제안을 하는 것으로 가름하고 실제 구현은 여러분에게 맡기겠다.(이 부분의 소스는 공개되면 안되는 이유가 있어서.. 양해바란다.) 참고로 대량의 데이타를 처리할 경우는 DB를 사용하지 않기를 권한다.

=================================================================================================두서없이 적은 글이라 많이 어지럽네요...오류나 문제제기 할 것이 있으면 사소한 것이라도 질문하시기 바랍니다.

그럼 좋은 하루 되세요..

검색 엔진 5 - 검색기 구조

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.

참고로 그림은 원문에서 찾을 수 없어서 이미지 검색을 통해서 얻은 그림으로 대치되었습니다. 따라서 원래 이미지와 맞지 않는 쌩뚱맞는 것일수도 있지만, 읽어본 결과 맞는 것 같습니다.

왼쫀 아래에 보면 dic(사전)들이 있습니다. 이것은 형태소분석기에서 사용하는 사전으로 색인시에 사용했던 사전들과 동일한 구조로 되어 있는 것이 바람직합니다. 물론 서비스 구성에 따라 형태소분석기 세팅 자체를 서로 다르게 할 수도 있습니다. 바로 옆에 있는 시소러스 사전은 별도로 동작하게 할 수도 있으나 대부분 형태소 분석기에서 사전과 같이 처리하는 것이 일반적인 예입니다. 이런 시소러스사전류는 검색시 입력되는 질의를 확장한다거나 할 경우 많이 사용됩니다.

여기서 질의를 확장한다라는 의미는 뭘까요? 쇼핑몰 검색을 예로 봅시다. 어떤 구매자가 나이키의 조깅화를 구입하려 하는데 갑자기 조깅화란 단어가 떠오르지 않는다면 어떤식으로 질의를 입력 할까요? 보통 나이키, 아니면 운동화 정도로 우선 검색을 할 것입니다. 이때 운동화라는 개념을 좀더 확장하여 조깅화, 런닝화, 축구화, 등등의 키워드들을 추가하여 검색하게 된다면 보다 쉽게 최종 결과에 도달할 수 있을 것입니다. 단, 부적절한 질의확장은 검색성능이나 결과 개수에 악영향을 미칠 수 있으므로 많은 연구가 필요할 것입니다. 당연히 시소러스 사전 자체도 서비스에 맞게 잘 구성되어 있어야 합니다.

다음으로.. 바로옆에 있는 index db는 색인기가 만들어 놓은 색인 정보들입니다. 이전 강좌에서 설명했던 내용이니 확인해 보시면 될 것이구요.. 다른것 하나는 term cluster dic인데 검색 엔진의 기본기능이 아닌 관계로 넘어가겠습니다. ^_^;

사용자가 검색질의 엔진에 던지게 되면 방식은 여러가지가 있습니다. 물론 서비스를 구성하는 것에 따라 방법이 달라지게 되구요. 많이 쓰이는 것들은 인터넷 검색엔진들이 되겠지요. 보통 CGI를 통해 질의를 받아서 CGI가 엔진으로 전달하고 결과를 받게 됩니다.

엔진에서 클라이언트 API를 제공하거 어떤 프로토콜을 제공해 준다면 윈도용 어플리케이션에서도 결과를 받아볼 수 있겠지요. 어차피 소켓통신을 하는 데몬이기에 프로토콜만 알게 되면 어떠한 응용 프로그램에서도 엔진과 바로 맞붙어서 데이타를 주고 받을 수 있습니다.(당연하겠지요?) 그래서 이런 경우에는 client api, activeX 콘트롤, 일반 APPs, 관리도구 등에서 다양하게 접속하여 엔진의 결과를 받을 수 있습니다.

그러나 검색포탈이나 SI업체들의 검색엔진은 프로토콜을 공개하지 않습니다. 이유는 당연하겠지요. 네이버가 검색 프로토콜을 공개한다면 하루에도 수십번 해킹을 당할 수 있을 것입니다. 하지만 검색엔진을 직접 개발하는 한 그룹내에서는 이런한 프로토콜을 공개하는 것이 개발시 도움이 될 수 있습니다.

아무튼, 클라이언트에서 입력된 검색질의는 엔진에서 받아들이게 되면 맨 처음 질의분석기(Query Analayzer)라는 녀석이 받아들입니다. 그래서 유효한 검색질의인지, 유효하다면 엔진이 이해할 수 있는 방식으로 검색질의를 파싱한 후 어떤식으로 검색을 수행할지, 어떤 필드에서 검색을 할지, 키워드를 확장할지 등등을 결정하게 됩니다.

결정이 되면 바로 연산기(calculator)로 파싱된 질의를 전달하여 질의에 대한 연산을 수행합니다. 이때 연산기는 자연어처리모듈, 논리연산 처리모듈, 숫자처리 모듈들을 내장하여 검색옵션에 맞게 결과를 계산하게 됩니다.

연산기가 계산대상이 되는 데이타를 먼저 로딩하기 위해 파싱된 텀별로 index DB의 데이타를 읽기 위해 Retriever에게 질의를 던지게 되면 Retriever는 필요한 정보들을 index DB에서 로딩하여 연산기로 전달해 줍니다.

연산기가 모든 연산을 마치게 되면 결과는 순위화된 문서들의 일련번호와 문서들의 랭킹점수등이 남게 됩니다. 이러한 내용들을 Stream Generator로 전달하게되고 Stream Generator는 최종 사용자가 확인할 수 있는 결과(제목, 본문, URL, 기타 부가정보등등)를 만들어서 다시 질의분석기 에게 돌려주게 됩니다.

그러면 질의분석기는 정해진 프로토콜에 맞게 Stream을 정리하여 클라이언트에 전달하게 되고 최종 검색결과를 클라이언트에서 마음대로 조작한 후 보여지게 됩니다.

그림에서 오른쪽에 Summary Server와 Log Server가 있습니다. 후자는 일반검색엔진과는 별 상관이 없는 부분입니다. Summary Server는 보통 검색엔진 내에 요약정보를 따로 두는 경우가 많습니다. 그러나 대용량 데이타일 경우는 요약정보가 하나의 서버에 같이 존재하게 되면 Disk I/O문제도 발생할 수 있으며 여러가지 성능에 안좋은 영향을 미칠 수 있으므로 위와 같이 요약서버 자체를 분리하여 구성할 수도 있습니다.

이상 간단한 검색기 구조였습니다.

검색 엔진 4 - 색인기 구조

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

참고로 그림은 원문에서 찾을 수 없어서 이미지 검색을 통해서 얻은 그림으로 대치되었습니다.따라서 원래 이미지와 맞지 않는 쌩뚱맞는 것일수도 있지만, 읽어본 결과 맞는 것 같습니다.

우선 색인 대상 데이타로 HTML, DB, W/P용 문서들, 기타 등등 Text-base의 모든 데이타는 색인 대상이 될 수 있습니다. 이러한 데이타를 검색엔진(특히 색인기)이 인지하려면 각각의 포맷을 알야아 할 것입니다. 그래야 필요한 정보를 추출할 수 있겠지요.

어제는 그러한 부분은 Dumper라고 간략히 말씀드렸읍니다. 이녀석을 오늘은 좀 다른말로 표현해보지요. 여기서는 Document Recognizer(문서 인식기)라고 표현하였습니다.
물론 인터넷 어디를 뒤져봐도 이런 용어를 찾기 쉽지 않을 거구요. ^^;
이녀석의 역할을 각각의 문서 포맷별로 필터를 가지고 있어서 해당 문서를 정확히 분석하여 F-TXT를 생성하는데 있습니다. 여기서 F-TXT는 검색엔진이 이해할 수 있는 형식화된 텍스트 문서입니다. 만일 색인기가 F-TXT형식으로 XML을 사용하겠다면 색인기는 XML파서만 있으면 되겠지요? 이런 경우라면 Document Recognizer는 각각의 문서들을 분석하여 XML로 재구성한 후 저장해 둘 것입니다.
일반적인 엔진들은 Document Recognizer를 필요에 의해서 간단한 프로그램을 작성하기도 합니다. F-TXT의 형식은 정해질 지라도 검색 대상 문서들의 포맷을 모두 지원하지 못하기 때문에 서비스를 구성할 때 간단한 프로그램으로 색인 대상 데이타를 F-TXT로 변환합니다. 결국 색인기는 F-TXT라는 형식만 인식하는 구조로 작성하고 Document Recognizer를 서비스 개발자가 직접 작성하게 하면 아주 유연한 엔진이 될 수 있을 것입니다.

다음은 F-TXT의 구성 예입니다.

DOCID : 1

TITLE : 정보검색시스템이란 무엇인가.

BODY : 정보검색이란... 어쩌구저쩌구.. 지화자 좋구나....

DATE : 20040520 130222

SIZE : 3428

URL :http://내도메인/data/ir.html

위 예는 간단한 예일 뿐입니다. 엔진 구성하는 사람의 마음이죠. ^^;

F-TXT가 만들어 지면 F-TXT 파서는 퍼블리슁이 필요할 경우 HTML Generator에게 파싱된 데이타를 전달하여 서비스 페이지를 만들게 됩니다. 또한 index Generator에게도 파싱된 데이타를 전달하여 실제 색인을 하도록 도와줍니다. 결국 핵심이 되는 것은 index Generator로서 이 녀석이 모든 색인DB를 생성하고 화일들을 관리하게 되지요.

Index Generator는 형태소분석기를 내장합니다. 물론 형태소 분석기는 여러가지 사전을 가지고 있어서 이런 사전정보와 경험정보, 규칙들을 사용하여 형태소 분석을 수행합니다. 형태소분석기를 사용하는 이유는 이전 강좌에서 간단히 말씀드렸던것 같네요.. 다시 말하자면 한국어 특성을 고려한 색인어를 추출하기 위함입니다. 물론 형태소분석기가 없더라도 색인어는 추출할 수 있습니다. 또한 어떤 경우는 형태소분석기가 오히려 색인어를 제대로 추출하지 못하는 경우도 있습니다. 그러나 여기서 보여드리는 색인구조는 국내의 엔진들이 일반적으로 사용하는 구조를 말씀드리는 것이구요. 아무튼.. 색인기는 형태소분석기를 통해 색인어를 추출하고 추출된 색인어를 기반으로 역화일을 생성합니다. 그리고 최종 요약정보도 생성하고 색인 과정을 마치게 됩니다. 이때 생성되는 화일들이 mapping table, term(keyword) trie, posting file, summary file 등입니다. 여기서 term trie와 posting화일을 역화일구조로 작성하게 됩니다.

위의 F-TXT 예를 기초로.. 검색서비스를 구성할 때 title에서만 검색, body에서만 검색, 날짜구간 검색 등의 검색서비스를 구축할 수 있을 것입니다. 이때 title, body, 날짜등은 별도의 역화일로 구성하면 의미상 명확할 뿐 아니라 검색효율을 상당히 높일 수 있습니다. 이유는 필터링을 할 필요가 없기 때문인데요.. 이렇게 구성하게 될 때 사용자가 title에서만 검색하는 명령을 내리게 되면 엔진에서는 title 필드에 해당하는 역화일을 찾아갈 수 있어야 합니다. 이런 부분을(title은 몇번째 역화일이다 라고 하는) 명시하는 것이 mapping table입니다.

term(keyword) trie는 index Generator가 생성한 모든 term(keyword)들을 트리형태로 표현하고 있는 색인 정보 입니다. 엔진마다 b-tree, b+ tree, trie, p tree등 다양한 방법을 사용합니다. 성격에 맞는 자료구조를 사용하면 되겠네요.. term trie는 posting file의 offset을 가지고 있어서 어떤 term이 나타난 문서들의 목록을 posting화일로 찾아가 구할 수 있도록 합니다.

posting화일은 문서들의 목록을 가지는 화일입니다. 단순히 문서번호를 나열해 둔 화일로서 term-trie에서 이 화일을 참조하여 문서목록을 가져옵니다. 여기서 문서목록이란 쉽게 생각하면 검색결과 목록이 될 수 있습니다.

summary file은 요약화일로서 검색결과를 화면에 보여줄 대 화면에 출력 가능한 데이타들을 모아둔 화일입니다. 쉽게 구성한다면 F-TXT를 그대로 사용해도 무방하겠지요.

그외의 모듈들은 사실 반드시 필요한 모듈들은 아닙니다. 필요에 의해 만들어 둘수도 있는 모듈들이라 설명은 하지 않겠습니다.

이상 간단한 색인기 구조였습니다.

검색 엔진 3 - 검색 엔진 구조도

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.

참고로 그림은 원문에서 찾을 수 없어서 이미지 검색을 통해서 얻은 그림으로 대치되었습니다.
따라서 원래 이미지와 맞지 않는 쌩뚱맞는 것일수도 있지만, 읽어본 결과 맞는 것 같습니다.

골치아픈 검색 모델을 잠시 접어두고 일단 시스템 구조가 어떻게 되어 있는지 구경해 보도록 하겠습니다. 아주 일반적인 사항이므로 대부분의 검색엔진들이 이러한 모양새를 갖추고 있다고 보면 되겠네요.

단, 아래 그림의 저작권은 제게 있으므로 함부로 도용하지 마시길..
=============================================================================
검색엔진 구조도

그림의 좌측을 보면 index target이 있습니다. 여기에는 html, 상용DB, 일반문서, 기타 여러 형식의 문서들이 존재할 수 있습니다. 이중 html문서들은 일반적으로 웹로봇을 통해 수집합니다. index target을 검색엔진이 색인하여 검색서비스를 제공하기 위한 기본 데이타들입니다.
index target들은 특정한 필터들을 통해 검색엔진에서 인지할 수 있는 일반적인 형태의 텍스트 문서로 변환합니다. 저는 이러한 작업을 하는 녀석을 dumper라고 이름 붙였습니다. 이 dumper가 각 문서의 형식에 맞는 필터들을 가지고 있어서 html은 html parser를 호출해서 F-TXT를 만들고 doc는 doc 필터를 통해, hwp는 hwp 필터를 통해 F-TXT를 만듭니다.
F-TXT는 형식화된 문서라는 의미로 formated-text라고 불렀습니다. F-TXT가 생성되고 나면 비로소 검색엔진의 색인 시스템이 인식할 수 있는 기본 문서들이 완성된 것입니다.
물론 F-TXT 로 변환하지 않고 색인기가 직접 필터를 가지고 문서들을 분석하여 색인할 수 있습니다. 이것은 단순히 구현의 차이이지요.
아래에 있는 스케쥴러는 주기적으로 변경되는 문서들을 색인하기 위한 것입니다. 웹문서라면 보통 보름에서 한달, 다른 컬렉션의 경우 서비스 용도에 맞게 하루 또는 여러방식으로 색인 주기를 설정할 수 있겠지요. 이런 작업을 스케쥴러가 총괄하게 될 것입니다.
Indexer에서 빼 놓을 수 없는 것이 형태소분석기입니다. 물론 형태소분석기가 없다고 하더라고 검색엔진 구성은 가능합니다. 색인 텀(term, 키워드)을 어떻게 생성할 것인가에 따라 형태소 분석기는 사용될 수도 있고 아닐 수도 있습니다. 한글 정보검색시스템에서는 형태소분석기에 따라 성능차이가 많이 나기 때문에 거의 대부분 선호하고 있습니다.
indexer는 형태소분석기를 통해 색인 텀을 생성하고 생성된 텀에 대해 문서번호와 함께 특수한 자료구조로 저장합니다. 보통 index db라고 쉽게 말하기도 하는데요. 역화일(도치 파일이라고도 합니다)이라는 구조로 색인 정보들을 저장합니다.
이렇게 역화일에 분석되어 저장된 문서는 검색기에 의해 검색이 이루어집니다.

색인기 부분을 보면 cache generator라는 것이 있습니다. 이것은 특수한 검색질의 같은 경우 연산시간이 너무 오래 걸릴 수 있기 때문에 미리 캐쉬로 만들어 두면 아주 좋은 속도를 낼 수 있습니다. 그래서 이런 모듈을 사용하여 캐쉬정보를 생성합니다. 캐쉬는 다양한 방법으로 구현할 수 있습니다만 보통 정적색인컬렉션이라면 웹서버에 검색결과 페이지 자체를 미리 만들어 두는 방법이 유용합니다.
로그서버는 검색어로깅 및 시스템 로깅을 위해 사용합니다.
요약서버는 별도로 구성하는 경우는 드믈며 색인기에서 역화일을 생성하면서 같이 만들어 두고 검색기에서 직접 읽는 방법을 많이 씁니다.
저같은 경우 위 그림을 만들면서 실험적으로 요약서버를 분리하여 테스트해 봤습니다.
생각외로 성능이 좋았습니다. 이유는 역화일과 요약정보가 하나의 서버에 존재하게 되면 disk i/o 버틀렉이 발생하여 역효과를 발생시켰었습니다. 그래서 서버를 분리하여 이 부분을 해소했었습니다.

위 그림은 일반적인 엔진의 모습이며 실제 응용에 들어가게 되면 많은 부분이 달라질 수 있습니다. 서비스별로 특수한 엔진을 만드는 것이 바람직하기 때문에 위 내용이 반드시 정답이라고 할 수는 없네요.

끝.
==============================================================================

시간이 나는대로 검색기, 색인기, 로봇, 요약서버 등등의 각 구조를 올려보겠습니다.
제가 글재주와 말주변이 없어서 설명에 자신은 없군요.

질문은 되도록 쉬운걸로... 오류는 반드시 지적을...

그럼 오늘도 한단계 앞으로 나아가시길..

검색 엔진2 - 검색 기법

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.




드디어.. 5개월만에 새로운 글을 쓰게 되었습니다.
회사 이직과 맞물려 너무 정신이 없었습니다.바쁘다는 핑계로.. 이렇게 소홀하게 되다니...
==============================================================================
검색 기법
다음은 BELKIN, NICHOLAS J.and CROFT, W. BRUCE,"Retrival Techniques," ARIST, 22(1987), PP. 109-145 에서 발취한 내용들이다.
BELKIN, NICHOLAS J.and CROFT, W. BRUCE등에 의해 제안된 검색기법의 분류방법
+-- Exact match
+-- Partial match --+-- Individual --+--- Structure-based
+-- Network +--- Feature-based

1. Exact match techniques(완전일치 기법)
검색된 도큐먼트들의 표현(representation)이 질문의 표현과 완전하게 일치된 것만 검색하는 방식이다. 초창기 대규모 검색시스템들에서 대부분 사용하던 방식이다. 이런 방법의 적용 예로는 불리언 검색, 전문검색, 스트링검색등이 있다.
단점으로는 다음과 같은 것들이 지적되어 왔다.
1) 이용자의 질의에 부분적으로 일치되는 경우의 텍스트들이 그 유용성에도 불구하고 검색에서 누락되는 예가 많다.
2) 검색된 텍스트들에 대한 적절성의 순위를 정하지 못한다.
3) 질문 및 텍스트 내에 존재하는 상호관련성이 있는 중요개념들을 전혀 고려하지 않는다.
4) 질문의 논리적 형성과정이 까다롭다.
5) 이용자의 질의 표현과 텍스트의 표현 비교가 오직 동일어휘로만 한정되어 있다.

이러한 단점에도 불구하고 초창기 많이 쓰이게 된 이유는 다음과 같다.
1) 검색기법을 변경하는데 드는 비용이 너무 많기 때문에 비경제적이다.
2) "exact match"기법이외의 대체기법들을 아직까지 대규모 시스템 환경에서 운영(테스트)해 본적이 없다.
3) 그러한 대체 기법들 조차도 실험적인 시스템 환경에서 테스트해 본 결과 그다지 만족스러운 것이 아니었다.
4) 이용자의 정보요구나 질의를 표현하는데 있어서 블리안 기법이 비교적 우수하다고 볼 수 있다.
그러나 현재 진보된 검색시스템들을 보게되면 위의 3,4번에 대한 이유가 무색해 진다. 현재 사용되고 있는 대부분의 상용 검색엔진들은 경험적으로나 이론적으로나 위의 3,4번에 대한 경우가 잘못된 생각임을 증명하고 있다.


2. Partial match techniques(부분일치 기법)
검색된 도큐먼트들의 표현이 질문의 표현과 부분적으로 일치된 경우의 것들로 함께 검색하는 방식이다. 여기서 Individual 방법은 이용자 질의를 각각의 개별 도큐먼트들과 비교 하는 방식을 말하며 Network 방법은 이용자 질의를 개별 도큐먼트들의 표현과 비교하는 것이 아니라 개별 도큐먼트들 및 이와 관련된 다른 도큐먼트들과의 관계성 에 중점을 두어 작성되는 표현들과 비교한 검색기법이다. 이러한 네트웍 검색기법 에서는 개별 도큐먼트들의 내용에만 전적으로 의존하여 검색이 이루어지기 보 다는 이들과 관련을 맺고 있는 네트웍 기법으로는 cluster에 근거한 검색기법 과 Browsing기법 및 Spreading activation기법이 있다.

2.1 Individual, Feature-based
이용자의 질의 및 도큐먼트들의 표현방식을 "색인어"와 같은 일련의 특징들로 표현하는 방식
->이러한 일련의 Features(특징)들은 각각 가중치로 표현될 수 있으며, text내에서 나오는 보다 복잡한 현상들을 표현하기에 적합하다. 이러한 feature-based기법에는 다시 Formal mode(여기에 해당되는 기법으로, Vector space model, 확률모델, fuzzy set model 등이 있다)과 Ad-hoc model이 있다. 이러한 범주의 기법들은 이용자의 질의를, 일련의 특징들 혹은 색인어들로 나타내는 도큐먼트 표현과 비교하는 방식을 취하고 있다. 이때의 도큐먼트 표현물들은 수작업이나 자동색인의 방식으로 도큐먼트의 텍스트 상으로 부터 추출되어지며, 마찬가지로 이용자 질의용어 역시 자연어로 표현된 질문으로 부터 직접 추출되거나, 색인어휘상의 용어를 사용하기도 한다. 여기에서 "feature"로 채택되는 요소들은, 단어나 어근, 구 혹은 개념들로서 이들과 관련된 가중치(weighte)값을 지니게 된다. 이러한 가중치들은, 그러한 각 요소들이 한 도큐먼트에 출현하는 빈도수나 혹은 이의 역 빈도수에 의하여 측정될 수 있다. 이러한 가중치의 표현방법이나 사용방법 및 계산방법 등은 각 시스템이 채택하고 있는 검색기법에 따라 다를 수가 있다.
(Formal) ==> Vector space model, probabilistic model, fuzzy set model.

2.1.1 Vector space model(벡터 공간 모델)
벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간속의 벡터들로 취급되며, 이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(tf)와 이의 역빈도수를 조합하여 계 산한다.
2) "낮은 식별치"(poor discriminatin value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며 구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 "코사인"상관도(cosine correlation)에 의해 계산된다(벡터 공간내에서 이 용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해 낸다)

2.1.2 Probabilistic model(확률모델)
확률모델은 지금까지의 검색기술에 새로운 방법론을 제시한 것으로서, 그 기술적 기반은 위의 벡터공간 모델로 부터 나온 것이다. 이 모델의 기본적인 목적은 이용자의 질의에 대한 적절성의 고확률순으로 도큐먼트의 순위를 정하여 검색하는 것이다. 즉, 각각의 도큐먼트를 구성하는 용어의 가중치가 "1"혹은 "0"의 값을 가질 수 있고 또한 이러한 각각의 용어들은 다른 용어들에 대해서 독립성을 지녔다고 가정하여 각 도큐먼트들의 순위를 정하는 방법이다.

2.1.3 Fuzzy set(퍼지 집합 이론)
이것은 검색기법 상으로 볼 때 블리언 질문기법과 도큐먼트 순위 매김기법을 통합한 기법이나 벡터공간 모델에 기초한 확장된 블리언 검색기법과 비교해 볼 때, 이러한 통합에는 한계가 있음이 드러났다.

2.1.4 Ad hoc(애드 혹 모델)
이 모델의 기본은 질의 용어군과 도큐먼트 용어군과의 겹침(over-lap)의 정도를 측정하여 그 유사성의 정도에 의하여 문헌을 검색하는 기법이다.


2.2 Individual, Structure-Based Techniques(개별적, 구조기반 기술)
이러한 범주에 드는 검색모델의 특징은 이용자 질의나 도큐먼트의 내용을, 색인어 등의 방식이 아닌 좀 더 복잡한 구조적 형태(structure)로 표현하여 이를 비교하는 방식이다. 이러한 검색기술은 특히, 특정한 전문주제분야에 적용되는 것이 적절하다.

2.2.1 Logic(논리모델)
도큐먼트의 텍스트가 담고있는 핵심적인 정보는 몇개의 짧은 문장으로 표현될 수 있으며, 이러한 문장들은 일정한 논리식으로 표현이 가능하다. 이와 마찬가지로 이용자의 질의도 논리식에 의한 표현이 가능하며, 이러한 질의는 논리식과 연계된 추론법칙에 의해서 그 해답이 가능하다.
예) 도큐먼트의 주제내용. "If a company sells computer, it is financially viable".
==> 논리식으로 표현 ==> (for all(x) (if (sells x computer) (viable x)))
이때 이용자의 질문(viable?)의 경우 "forward chaming"으로 해답이 가능하다. 이러한 모델의 가장 커다란 어려움은 각 텍스트들을 논리식으로 전환하는 작업인데, 현재는 수작업으로 하고 있다.

2.2.2 Graph(그래프 모델) 이 모델은 그래프 형태의 표현방법을 이용한 검색기법이다. 즉, 그래프 형태의 표현방법은 노드들과 이러한 노드들간의 edges(links)들로 이루어져 있는데, 이러한 노드들과 edges들은 주로 자연어 처리과정을 통해서 얻어지는 의미망(semantic nets), 혹은 의미프레임(semantic frames)으로 표현된다. 검색기법은 질의어의 그래프 구조와 도큐먼트의 그래프 구조를 서로 비교하여 그 유사성에 의거하여 문헌을 검색하거나 그 순위를 정하는 방식이다.


2.3 Network(네트웍 모델)

2.3.1 Cluster(클러스터 모델)
클러스터란, 내용이 유사한 일련의 도큐먼트군을 의미한다. 이것은 SMART프로젝트에 채택된 검색기법으로서, 클러스터 계층구조(CLUSTER HIERACHY)에 의한 것이었다.
* 클러스터 계층구조
--> 전체의 도큐먼트들을 몇개의 클러스터들로 나눈후에 각각의 클러스트들을 또다시 작은 클러스터들로 나누는 반복된 작업구조.
검색방법은 이용자의 질의내용을 최상위의 클러스터로 부터 최하위의 클러스터들 까지 하향식으로 비교하여 그 유사성의 큰 것부터 차례대로 검색해 내는 방식.

2.3.2 Browsing(브라우징 기법)
각각의 도큐먼트, 색인용어, 서지적 정보들을 시스템상에서 노드와 컨넥터들로 표현된 네트웍 구조로 만들 수 있다면, 이 때, 이용자는 이러한 네트웍을 훌터나가면서(Browsing) 필요한 도큐먼트들을 검색하는 기법. 이러한 Browsing기법에서 주목할 사항은 검색기법상 이용자 질문식의 형성(query formulation)에는 중점을 덜 두는 반면에, 이용자로 하여금 Browsing과정 중에서, 즉각적인 피드백을 강조하는 시스템이다.
I R 시스템의 예
노드(node) --> 도큐먼트, 색인어, 주제영역지식, 저자, 저널명.
링크(links) --> 색인정보, 시소러스 정보, 인접노드정보, 인용, 저자사항.

2.3.3 Spreding activation(스프래딩 액티베이션 모델)
위의 Browsing기법과 유사한 모델
네트웍 상에서 이용자의 질문에 해당되는, 어느 한 부분의 노드(색인어 혹은 도큐먼트) 및 이와 관련된 또 다른 노드들만 활성화(activate)시켜 가면서 최종 도큐먼트를 검색해 내는 방식.
예를들어 이용자의 질문에 의해서 어느 한 색인어가 선택되어 졌을 때, 이 색인어와 연결된 도큐먼트들 및 관련 색인들 역시 함께 활성화시키게 되는 방식.

2.4 Feedback Methods(피드백 기법)
이 기법은, 원래 "Feature-based"기법에서 발전되어 온 것으로서 현재는 모든 검색기법에서 응용되고 있다. 이 기법의 핵심은, 질의 용어에 대한 기준치를 검색도중에 수정해 가면서 최적의 도큐먼트들을 검색해 내는 방식이다. 이러한 가중치의 수정은, 적합한 것으로 판단된 도큐먼트들 속에 포함된 색인어들의 빈도수에 의해서 결정된다. 10-20%.



Relative Performance of Retrieval! Techniques(검색기법의 상호성능 비교)
(Comparation Performance Studies)
1) 전반적으로 완전일치(exact match)기법보다는 부분일치(paricial-match)기법에 의 한 검색 결과가 더우수한 것으로 나타났다.
2) Feature-based기법 중에서는 특히 색인어에 대한 가중치 부여 기법을 사용한 확률 모델 기법이 가장 우수한 것으로 조사되었으며, 이때 용어의 가중치를 주는 방식 에 따라 그 검색성능이 크게 달라졌음이 밝혀졌다.
3) 클러스터 검색기법의 경우 "individual feature-based"검색에 버금가는 성능을 지녔으며, 특히 다른 검색기법들에 비해서, 높은 정확율을 가져온 것으로 나타났다. 따라서 클러스터 기법은 "individual feature-based"모델을 대체할 수 있는 좋은 기법이다.
==============================================================================
오늘도 하나 배워가는 하루가 되시길...

검색 엔진 1 - 구성 요소

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.

1주일에 한번씩 올리려 한 것이 개인적인 사유로 많이 늦어지고 있습니다.(핑계지요 )
이번에 올릴 글을 작성하다 보니 글이 길어지는 것 같아 두 부분으로 나누었습니다.
뒷부분은 별도 제목으로 하여 따로 올리려 합니다.
두서없이 정리한 것이라 내용이 역시 부실하군요.

============================================================================
정보검색시스템의 구성요소

1. 정보검색시스템이란?
정보 수요자가 필요하다고 예측되는 정보나 데이터를 미리 수집, 가공, 처리하여 찾기 쉬은 형태로 축적해 놓은 데이터 베이스로부터 요구에 적합한 정보를 신속하게 찾아내어 정보 요구자에게 제공하는 시스템을 말한다.

2. 배경학문
자료구조론 (Speed & Memory Trade-off)
데이터베이스론 (DB Indexing)
검색알고리즘
AI의 Search, NLP, Story understanding Algorithm
ES의 Inferencing

3. 구성요소
3.1) 웹로봇
웹상에 존재하는 문서들을 가져오기 위해서 웹의 하이퍼텍스트 구조를 자동적으로 추적하여 참조되어지는 모든 문서들을 재귀적으로 검색하는 프로그램을 말한다. 여기서 '재귀적으로'라는 의미는 어떤 명시된 트래버스 알고리즘으로 유한하게 정의되어지는 것이 아님을 주목하라. 비록 로봇이 문서 선택을 위해 몇몇의 발견적인 학습법을 허락한다거나 방문하기 위한 문서의 순서를 정한다거나 하더라도 여전히 로봇이다. 일반적인 웹브라우저는 로봇이 아니다. 왜냐하면 그것들은 인간에 의해 수행되어진다. 그리조 참조되어지는 문서들을 자동적으로 수집하지 않는다. 크롤러(crawler), 스파이더(spider), 개더러(gatherer), 웸(worms), 안츠(ants) 등 다양한 이름으로 불리우지만 일반적인 명칭으로는 로봇이라 칭하는 비율이 높은듯 하다. 로봇을 얘기하면서 빼 놓을 수 없는 것이 로봇 배제 표준(robot exclusion standard)이다. 봇은 상당히 무책임한 프로그램이 될 수 있으며, 심한 경우는 웸바이러스와 같은 행동을 보일 수 있다. 필자의 경우 회사에서 로봇을 구동시키던 도중 국내의 유명 쇼핑몰의 DB를 죽여버린 경우가 있었다. 다행히 관용을 베풀어 주셔서 조용히 넘어갈 수 있었지만 돌이켜 보면 무척이나 위험한 상황이었다. 이처럼 잘못 구성된 로봇으로 인해 특정 사이트를 죽여버리거나 망 자체를 마비시킬 수도 있는 것이 로봇이다. 이런 로봇의 위험에서 자신의 웹사이트를 보호하기 위한 표준적인 방법이 로봇 배제 표준이라 생각하면 된다. 하지만 대다수의 로봇들이 이러한 표준을 지켜주는 것이 아니란 것을 명심하라. 독자가 로봇을 만들 생각이라면 반드시 이 표준을 지켜주기를 권장한다. 로봇 배제표준에 대한 자세한 설명은 시간이 나는대로 따로 간단한 강좌를 만들겠다.

3.2)스토리지
검색엔진에서 사용할 색인용 데이타를 컴퓨터의 저장장치에 기록하여 두는 곳을 말한다. 초창기 상용화된 검색엔진들은 일반적인 DBMS를 사용하여 데이타를 저장하였다. 이는 관리 및 사용이 아주 용이하기 때문에 매우 효과적으로 수행될 수 있었으나 데이타가 대용량화 되어지고 알고리즘이 복잡해 지면서 점차 화일 시스템을 직접 제어하여 데이타를 저장하는 방식을 많이 사용한다. 단순하게는 화일에 필요한 키워드 정보와 포스팅화일 요약화일을 저장하는 방식에서 좀더 성능을 향상시키기 위해 물리적인 계층에서 저장장치(보통 하드디스크)를 제어하여 자체의 검색엔진 전용 화일 시스템을 구축하는 경우도 있다. 몇몇 공개된 소프트웨어 중에서는 검색엔진 전용 색인 DB를 만들어 배포하는 곳도 있다. 검색엔진을 구축하다보면 용도에 따라 Read-only 시스템으로 구축하는 경우와 read-write 시스템으로 구현하는 경우가 있다. 전자의 경우는 화일 시스템을 구성하는 것이 무척이나 간단한 문제이지만 후자일 경우는 아주 심각해진다. 허나 후자와 같은 시스템을 요구하는 업체들의 비중이 점점 높아지는 추세이며 업계에서는 이런 부분에 많은 투자를 하고 있는 시점이다. 검색엔진에서 사용되는 기본적인 스토리지의 구성은 보통 3단계로 구성되며, 이는 텀리스트, 포스팅 화일, 요약화일로 구성된다.

3.3)색인기
웹로봇을 통해 수집된 문서들을 빠르고 정확하게 검색하기 위해 문서의 중요 키워드를 추출하고 이러한 키워드들의 상관관계나 문서들의 상관관계를 정의하여 스토리지에 저장하는 프로그램이다. 키워드를 추출하기 위해 형태소분석기나 스테머등을 사용하거나 또는 n-gram 방식을 사용하기도 한다. read-write시스템의 경우는 색인기와 검색기가 하나의 시스템으로 구성되기 때문에 임계영역에 대한 문제가 대두된다. 다양한 랭킹 알고리즘에 의해 색인기의 모양은 달라지게 되면 알고리즘의 복잡도와 추출되는 색인어의 양에 의해 색인 속도에 많은 영향을 주게 되며, 이러한 색인 속도는 색인기의 전체 성능을 평가하는 기준이 되기도 한다. 스토리지는 색인기의 일부분으로 구성될 수 있으며 결국 스토리지의 구조는 검색 모델(또는 랭킹 알고리즘)에 의해 결정되어진다.

3.4)형태소분석기
형태소 분석이란 여러 형태소들의 묶음이 표층 형태로 나타나는 하나의 어절로부터 의미를 갖는 최소 단위인 각 형태소를 분석해는 내는 것으로 정의된다.(강승식) 문서의 핵심 키워드를 추출하는 기본적인 시스템이다. 검색엔진에서는 보통 형태소분석기의 모든 기능을 사용하지 않고 색인어 추출만 하기위해 특정 형태소만 취하는 경우가 대부분이다. 초기 정보검색에서는 색인어로 적합한 형태소는 명사로 국한하였다. 허나 발전을 거듭하면서 현재는 각 형태소의 구조적인 관계 및 의미관계까지 고려한 색인어를 추출하기도 하며, 이러한 방식은 자연어 검색의 기본이 된다.

3.5)스테머
보통 어근 추출용으로 많이 사용되었으며 영어권 언어에 대해서 많이 적용된다. 언어적 특성상 한국어와 같은 교착어는 어미변화와 활용형들이 아주 심한 편이어서 단순한 스테밍 알고리즘만으로 처리하기에는 문제점이 있기 때문에 한국어는 형태소분석기를 주로 사용한다. 영어같은 경우 몇가지의 간단한 룰만 적용하여 스테머를 구성할 수 있기 때문에 속도가 빠르고 효율적인 시스템을 구성할 수 있다.

3.6)검색기
사용자가 입력한 검색 질의를 색인기가 생성하여 둔 스토리지에서 정의된 검색 모델(랭킹 알고리즘)에 의해 가장 유사한 문서를 추출하여 검색하여 주는 기능이다. 질의 분석기가 별도로 내장되어 있어야 하며 특성상 대량의 정보를 빠른 시간안에 주어진 알고리즘으로 계산해 내는 능력이 필요하다. 순위화를 위해 랭커를 가지고 있으며 보다 빠른 검색을 위 캐쉬를 사용하기도 한다.

3.7)브로커
검색엔진에서 사용하는 컬렉션은 다양한 여러 종류로 구성될 수 있다. 이러한 다양한 컬렉션에 대해 하나의 질의로 검색을 할 경우 어느 컬렉션을 검색할지 최종 검색된 컬렉션별 결과들을 어떻게 취합할지에 대한 문제가 발생하게 된다. 이러한 문제를 해결해 주는 것이 브로커이다. 입력된 질의를 분석하여 검색할 대상을 찾고 각 컬렉션에서 결과를 검색한 후 이에 대한 최종 결과를 취합하여 전달해 주는 역할을 하게된다. 포탈 사이트의 통합검색 CGI도 넓은 의미에서 브로커라 할 수 있겠다.

3.8)요약기
문서의 핵심이 되는 내용을 간결한 문장으로 축약하여 주는 기능이다. 검색된 문서의 모든 내용을 보여주기에는 그 양이 너무 많기 때문에 검색자의 편의를 위해 잘 정제된 요약 내용을 보여줄 필요가 있다. 경우에 따라서는 검색기에 이런 요약기능을 부여하기도 하며 별도의 서버로 구축될 수도 있다. 자동요약 분야는 아직도 많이 연구가 되어지고 있는 분야이다.

3.9)각종 필터
다양한 포맷의 문서들에서 텍스트 정보를 추출하기 위한 기능이다. doc 화일 같은 경우 binary로 구성되어 있기 때문에 실제 text정보를 추출해 주는 doc 필터가 필요하다. 또한 html문서도 그대로 색인시 html tag도 색인이 되어질 수 있으므로 html parser를 통해 필터링을 걸쳐 text정보만을 색인하게 된다. 이런식으로 text-based 검색엔진에서는 다양한 문서들에 대한 검색 서비스를 하고자 할 경우 각각의 문서 포맷에 맞는 개별적인 필터가 있어야만 한다.

3.10)랭커
검색 결과에 대한 순위를 매겨주는 기능이다. 검색 모델 및 랭킹 알고리즘에 맞게 구성되어지는 것이 보통이며 검색기의 일 부분으로 동작하게 된다. 주된 기능은 질의에 대한 각 문서들의 연관성을 수치화 하는 기능과 결과 정렬 기능이다. 실제 검색 속도에 가장 영향을 많이 주는 부분은 포스팅화일을 스토리지에서 메모리로 로딩하는 과정과 이 랭커에서 랭킹을 하는 두 부분이다.

3.11)질의분석기
사용자가 입력한 비 정규적인 질의를 파싱하여 검색에 적합하도록 정의된 정규화된 질의 문법으로 변환하는 기능이다. 입력된 질의는 대다수 내부적인 연산에 적합하게 구성되지 않는다. 이를 최대한 연산하기에 적절한 문법으로 변환하기 위한 필수 과정이다. 분석기는 때때로 형태소분석기나 기타 토큰 분리기 등을 포함하고 있어서 질의중에 꼭 필요한 키워드만 추출할 수 있도록 하기도 한다. 논리연산을 위해서 정의된 기호들을 연산자로 대치하기도 하고 질의에 대한 파스트리를 생성하기도 한다. 또한 주어진 컬렉션들 중에 어디에서 검색할 것인가를 명확히 표현해 주기도 한다.

3.12)파서
문자열 파서가 대부분이다. 경우에 따라서는 오토마타, 형태소분석기, 기타 토큰분리기 등을 사용한다. 색인기에서 색인어 추출을 위해 사용하기도 하며 검색기에 포함되어 있는 질의 분석기에서 질의를 분석하기 위해서 사용하기도 한다.

3.13)오토마타
유한오토마타를 사용하여 주어진 질의나 문서를 파싱하기 위해 사용한다.

3.14)컬렉션
검색 대상이 되는 집합을 말한다. 웹문서 검색일 경우 로봇이 수집한 HTML문서등이 하나의 컬렉션이 될 수 있다. 다양한 조건 및 여러 필드 검색을 지원하기 위해 컬렉션은 여러개로 나뉘어 질 수 있으며 웹문서하나도 여러개의 컬렉션으로 쪼개어 구성시킬 수 있다. 예를 들어 www.yahoo.co.kr 하위의 문서 중에 '꾸러기'라는 키워드로 검색하고자 할 경우, 웹문서들의 text부분을 모아서 하나의 컬렉션으로 구성하고, url부분을 모아서 다른 하나의 컬렉션으로 구성한 후 두개의 컬렉션중에 url은 url 컬렉션에서 찾고, 키워드는 text 컬렉션에서 찾은 후 두 결과를 and 연산을 통해 최종 결과를 산출한다. 이런식으로 데이타 성격이 다른 여러개의 집합들을 개별 컬렉션으로 구성하여 다양한 연산을 통해 복잡하면서도 잘 정의된 검색 결과를 계산할 수 있다.

3.15)DB
색인기가 생성한 색인 정보들을 저장할 DB를 말한다. 일반적인 상용 RDB를 사용하여 색인 DB를 구성할 수도 있으며 속도를 위해 파일 시스템을 제어하여 별도의 화일시스템으로 구성할 수도 있다. 컬렉션의 크기와 종류가 작을 경우는 상용 RDB를 사용하는 것이 사용하기에 아주 편리하다. 그러나 대용량 컬렉션일 경우는 파일 시스템을 직접 제어하는 것이 성능상 더 효율적일 경우가 많다. 검색엔진 전용으로 연구되어진 DB들이 몇몇 대학의 연구소를 중심으로 발표되어 있긴 하나 상용으로 적용된 사례가 많지 않다. 버클리 DB를 사용하여 동적 색인을 가능케 한 검색엔진들이 발표되어 있긴 하나 성능이 만족할 만 한지는 의문이다.

3.16)프리뷰어
검색된 페이지를 직접 방문하지 않고 검색엔진 자체에 저장되어 있는 문서를 사용하여 엔진 자체에서 미리보기 형식으로 보여주는 기능이다. 웹로봇이 문서를 수집할 당시에 살아 있던 링크라 하더라도 검색하는 시점에서는 이미 삭제되어 버린 문서일 수도 있다. 또는 속도가 느려서 실제 페이지를 방문할 때 브라우져를 통해 보기가 만만찮을 경우도 있다. 이런 경우 엔진에서 저장하고 있는 데이타를 사용하여 미리보기 형식으로 데이타를 보여주어 사용자의 편의를 도모할 수 있다.

3.17)중복제거기
최근 검색엔진들의 비약적인 발전으로 인해 검색 결과에서 중복되는 문서들이 나타나는 경우는 드물다. 실제 엔진 내부에는 중복된 내용을 가지는 문서들이 상당수 존재하는 것이 일반적인 현상이며, 이러한 중복 문서를 제거하기 위해 별도의 중복 제거기가 필요하다. 크게 3부분에서 중복문서를 제거시킬 수 있으며, 첫째로 로봇에서 문서를 수집하는 시점 또는 수집후에 모든 문서들을 비교해서 중복 문서를 제거할 수 있다. 둘째로 색인 시점에서 색인과 동시에 중복되는 문서를 제거시킬 수 있으며, 마지막으로 검색한 결과에 대해서 검색기에서 검사하여 결과를 조절하는 방식으로 제거시킬 수 있다. 구글이나 네이버에서는 마지막 방법까지 사용하여 중복문서를 제거한다. 이러한 방식 때문에 실제 검색 결과와 마지막에 보여지는 개수에 차이가 보여지기도 한다.

3.18)역화일
파일 시스템 또는 데이터베이스 등과 같이 대량의 자료가 관리되는 곳에서 보다 빠르게 자료를 검색하기 위하여 각각의 자료에 대한 색인이 구성되어 있는 파일을 지칭하는 용어. 이러한 파일에는 각각의 데이터 레코드에 대한 키 값과 이러한 키 값에 의하여 지칭되는 레코드의 위치가 하나의 쌍을 이루고 있다. 키워드를 빠르게 찾기 위해 B+tree나 B-tree, trie, 페트리샤트리 등을 사용한다.


=============================================================================
다음 강좌는 검색기법에 대해 간단히 정리하여 보겠습니다.
그럼 좋은 하루 되세요.

DBEdit로 이클립스에서 DB작업을 간편하게..

DBEdit..

dbEdit와 혼동 말자.

DBEdit는 이클립스에서 Database를 보다 간편하게 사용하기 위한 tool이다.

소스포지의 DBEdit홈페이지를 가서 DBedit를 다운받자.

다운 받은 압축 파일을 풀면 features와 plugins디렉토리가 나타나는데 각 폴더 내용들을 이클립스의 features와 plugins폴더로 옮겨놓는다.

그리고 이클립스를 실행해보자.

그림에서 볼 수 있는 바와 같이 Window메뉴의 Open Perspective의 Other메뉴를 보면 DBEdit가 새로 추가된 걸 볼 수 있다.

실행해보면 그림에서처럼 새로운 Tables와 관련된 바가 새로 나타난다.

Database를 연결하기 위해서 Tables바 안 빈칸 아무곳에나 마우스 포인터를 옮겨 놓고 좌측 버튼을 클릭해보면 메뉴가 뜬다.

이 메뉴에서 New>Connection을 실행하면 연결 설정 다이얼로그가 뜬다.

1.다이얼로그에서 classpath탭을 선택해 JDBC 드라이버 파일을 클래스패스에 등록한다.(MySQL은 mysql-connector-java-x.x.x-bin.jar파일이 있는 것을 연결, Oracle은 class12.zip)

2.Common 탭에서 JDBC Driver 콤보박스의 드랍다운 버튼을 누르면 사용 가능한 JDBC 드라이버의 목록이 나오는데 적절한 것을 선택하면 된다.(org.gjt.mm.mysql.Driver)

3.JDBC 드라이버를 설정하면 바로 아래 Server URL항목에 해당 드라이버에 대한 JDBC URL 템플릿이 팝업으로 표시된다. 이를 선택해 Server URL난을 채운다.(host->localhost,dbname->해당DB이름)

4.다음 서버주소, 포트번호, SID등을 적절히 편집한다.(port는 MYSQL의 경우 대부분 3306)

5.사용자 아이디와 패스워드 등을 지정한 다음 Connect버튼을 누른다.

ex)

그러면 데이터 베이스에 연결이 될것이다!!!!!

참고로 DBEdit는 기본 설정으로 100개씩의 row data만을 가지고 온다. 이를 해결하기 위해서는 preferences(Window메뉴에 있는)의 DBEdit 메뉴에서 설정해줘야한다.

또한 Shift + Ctrl + E를 누르면 조건에 맞는 data만 추려서 볼 수 있다.

Tables 뷰의 컨텍스트 메뉴에서 New>SQL File을 선택하면 SQL Editor가 열리며, 여기서 SQL문을 이용해 작업할 수 있다.

마지막으로 혹시 "Fetching children of MySQL"이라는 Error메시지를 보았다면, 다른 버전으로 다시 까는게 가장 빠른 해결책이라고 할 수 있다.

현재 글이 씌여지는 시점에도, 아직 근본적인 해결책은 찾지 못하고 있다고 전하고 있다. 나 역시 1시간 동안 해결책을 찾은 결론 끝에, 다시 깔았고.... 1분 만에 제대로 된 화면을 보았다... ㅜㅜ

Determining term subjectivity and Term orientation for opinion mining

Opinion mining관련한 굵직한 논문들을 서베이하는 것은 이걸로 대충 마무리 지어질 것 같다.
물론, 그 동안 읽었던 논문들을 아직 블로그에는 다 기록하지 못했지만...

이 논문은, Andrea esuli와 Fabrizio sebastiani의 작품이다.

이 논문은 자동적으로 sentiment orientation을 확장하고 재생산 하는 알고리즘에 대한 힌트나 영감 혹은 subjectivity를 판단하는 데 있어서 어떤 감을 얻을 수 있을까 해서 읽었는데 소기의 목적을 달성하지는 못한 듯 싶다.

논문에서는 기존 연구들(opinion mining관련한)이 sentiment orientation을 찾고 그걸 이용해 positive, negative한 글들로 분류하는 것에 대해 문제를 제기하고 있다.
글이나 단어들은 opinion이나 emotion이 확연하게 드러나는 것들도 있지만, 그렇지 않은 것들도 많다. 따라서 먼저 주관적인 글과 객관적인 글 혹은 단어로의 구분을 한 뒤 positive, negative로의 구분이 순서에 맞다고 주장한다.
따라서 opinion mining과 관련한 연구나 작업은 크게 3부류로 나눌 수 있다.
먼저, 주관성 객관성을 파악하는 일 하나.
그리고, positive 혹은 negative한 걸로 분류하는 것 둘.
마지막으로, mild한 positive인지 strong한 negative인지 강도를 파악하는 것 셋.

andrea와 fabrizio 두 사람의 방법은 다음과 같다.
positive한 것과 negative한 것을 semi-supervised learning algorithm을 이용해 trainng한다.
semi-supervised라고 한 이유는 training의 일부 셋은 맨 처음 labeling이 되어 있기 때문이다.
즉, seed set이라고 할 수 있는 positive, negative한 집합을 맨 처음 만든다. 그리고 이 집합을 이용해 순차적으로 training의 셋을 넓혀간다.

처음 :
positive = positive seed set
negative = negative seed set
두번째:
positive = 기존positive seed set+기존positive set의 유의어 set+기존negative seed set의 반의어 set
negative = 기존negative seed set+기존negative set의 유의어 set+기존positive seed set의 반의어 set
...
K번째:
positive = (K-1)positive seed set+(K-1)positive set의 유의어 set+(K-1)negative seed set의 반의어 set
negative = (K-1)negative seed set+(K-1)negative set의 유의어 set+(K-1)positive seed set의 반의어 set
이런 방법으로 sentiment orientation data set을 확장해 나간다.

다음 방법은 한 단어에 대해서 word net gloss(즉, 단어 정의 혹은 뜻풀이)들을 합쳐서 textual representation을 만든다. 그리고 이 textual representation을 text indexing 기법인 vetorial form으로 변형한다. 그 후 stop words(이 의미를 잘 모르겠다.)를 지우고 남은 단어들은 consine-normalized tfidf로 weight를 설정한다.(아마도 turney논문에서 살펴본 기본이 되는 nice, good같은 단어들만을 남긴다는 의미 같은 데 확실히 모르겠다.) 이것은 비슷한 orientation을 갖는 단어들은 비슷한 gloss를 가질 것이라는 가정에 따른 것이다. 예를 들면, 정직과 진취는 가치를 높이는 단어들이 공통적으로 들어가겠지만 불신과 방해는 가치를 손상시키는 단어들이 뜻풀이에 공통적으로 들어갈 것이다.

이 논문은 evaluation이나 result분석에 큰 의의를 둘 수 있는 논문이지만...

지금은 필요하지 않은 관계로 조금 후에 시간이 되면 하도록............ 헉헉

SVM의 개념

SVM은 상당히 다룰 내용이 많은 learning algorithm이다.

하지만, 아직은 SVM을 제대로 공부한 적이 없는 필자와 같은 상태의 사람들은 논문을 보거나 SVM을 프로젝트에 이용하려 할때 기본 개념을 알고 있을 필요가 있다.



SVM(Support vector machine)은 2개의 범주를 분류하는 이진 분류기이다.

다음 그림은 SVM의 개념을 설명하는 것이다. feature들은 그림과 같은 vector공간에 vector로 표시된다. 그림에서 보는 것처럼 하얀 색 vector들을 A그룹에 속하는 white point라고 하고, 그 반대로 검은색 vector들을 B그룹에 속하는 black point라고 하자.



이러한 벡터 가운데 같은 범주를 기준으로 바깥으로 위치한 벡터들의 연결선으로 이루어진 닫혀진 다각형을 convex hull이라고 한다. convex hull안의 벡터들은 그룹을 분류하는 데 그다지 큰 영향을 미치지 않는다. 그룹을 분류하는데 가장 큰 영향을 미치는 것들은 바깥에 위치한 벡터들이다. 그룹을 분류하는 선, 면을 hyperplane이라고 한다.
그림에서 보는 것처럼 그룹을 나눌 수 있는 hyperplane은 무수히 많다.
하지만, 직관적으로 그룹들의 convex hull에 속한 벡터들 중 가장 가까운 벡터와 수직거리로 가장 먼 거리를 가진 hyperplane이 2그룹을 효과적으로 분류할 것이다.
이러한 hyperplane을 maximum hyperplane이라고 부르고 이때 가장 가까운 벡터들을 support vector라고 한다. hyperplane이 재조정 될때는 support vector역시 재계산 되어야 한다. hyperplane은 선형 또는 비선형 모든 형태로 표현이 가능하며 일정 수식의 방정식으로 표현이 가능하기 때문에 간단한 수식으로 두 그룹을 분류할 수 있다.

이제 해야 할 일은 이 두 그룹 간의 거리를 최대한으로 하여 categorization할 때 발생할 수 있는 오류를 최소화 해야 한다. 그룹 간 거리를 최대한으로 하기 위해서 공업 수학 시간에 배운 적이 있을(공학도라면) 다변수 함수의 최대, 최소 값 찾는 데 이용되는 라고랑지의 미정계수법을 사용한다. 라고랑지 미정계수법의 원리는 그리 어려운 내용이 아니다.(수학적 내용 Lable의 라고랑지의 미정계수법 참고)

그런데 SVM 역시 두 그룹간의 거리를 최대로 하는 가중치 값들(다변수)을 정하는 것이므로 다른 머신 러닝 방법과 유사한 측면이 있다. 그렇다면, 왜 Decision tree, Concept learning, 그리고 neural network같은 걸 쓰지 않고 SVM을 쓰는 걸까? 그것을 바로 target이 2그룹 중 하나로 분류되는 경우에 특화되어 있기 때문이다. 예를 들면, 2가지 그룹으로 분류하는 방법으로 Decision tree를 쓸 수도 있고, neural network를 쓸수도 있고 Concept learning을 할 수도 있다. 만약 training set이 선형적인 hyperplane으로 나눠질 수 있다면 모든 경우가 거의 비슷한 성능을 할 것이다. 하지만 비 선형적인 경우 neural network가 가장 좋은 성능을 내게 될 것이라고 하자. 하지만, 만약 이 비선형성이 보다 높은 차원에서 볼 때 선형성을 뛴다고 하면 차원을 확대해서 보다 더 빠르고 쉬운 선형적 머신 러닝 알고리즘을 사용할 수 있지 않을까? 우리는 두 개의 그룹으로 분류하기 때문에 차원의 수를 아주 많이 확대하지 않고도 training set을 선형적으로 바꿀 수 있을 것이라고 직관적으로 생각할 수 있다. 그런 의미에서 SVM이 효과적인 측면을 갖는다고 말할 수 있다.

SVM을 이용한 악성 댓글 판별 시스템의 설계

음.....

강승식 교수님께 형태소 분석기를 문의 드리면서,
하려고 하는 프로젝트에 설명을 드렸더니...
정말 친절하시게도 논문 2편을 보내주셨다.
이 논문은 김묘실씨와 강승식 교수님의 작품이다.

관련된 논문은 많이 있지만... 한국에서 비슷한 연구를 수행했다니 신기했다.
역시... 악성 댓글로 머리 아픈 한국에서 이런 연구 하나 없었다면 말이 되지 않겠지만...

SVM을 이용한 이유는 누차 얘기했지만...
Turney의 논문에 따른 결과라고 할 수도 있겠고,
직관적으로 비방과 비방이 아닌 글의 2 그룹으로의 분류이기 때문이기도 하다.

SVM을 이용하기 때문에 적절한 feature를 뽑아내는 게 가장 중요한 일이다.
본 논문에서는 적절한 feature들을 뽑기위해 HAM(형태소 분석기)을 이용해 악성 댓글에서 자주 쓰이는 단어나, 서술어를 뽑아 data화 하였다.
그 후 SVM을 적용해 trainng하였고, test하였다.

평가 결과는 다음과 같다.
먼저 긍정적인 댓글에 대한 결과이다.
Accuracy = 0.615
Precision = 0.505
Recall = 0.79
F1-measure = 0.62

악성 댓글에 대한 실험 결과는 10-fold cross validation방식으로 측정하였다.
cross validation이란 한 data set을 2개로 나눠서 하나는 training으로 다른 하나는 test로 이용하는 것이다. k-fold cross validation은 data set을 k개로 나누고, 하나는 test로 다른 k-1개의 data는 training으로 이용하는 것이다.

여기서는 대략 70%정도의 F1-measure결과가 나왔다.

70%정도의 성능이라면 대단히 우수하다고 볼 수 있지만,
data set의 크기를 고려해보면 아직 유의한 결과라고 볼 수 없다.
더 큰 data set을 고려해서 test한 결과를 생각해 보아야 할 것이다.

주목할 만한 결과는 명사만을 feature로 선택했을 경우가 다른 품사를 포함하는 경우보다 성능이 1.1%정도 높았다고 한다. 1.1%면 유의한 의미를 지닌다고 얘기하기 힘들수도 있겠지만...
또한, 어절자체를 포함한 경우가 어절을 포함하지 않고 명사만을 고려한경우보다 1.5%정도 성능 향상의 결과를 가져왔다. 이것은 네티즌들이 유행처럼 사용하는 신조어의 영향 때문이라고 보았는데 이런 신조어가 악성 리플에 자주 등장한다고 볼 수 있겠다. 또한 이런 신조어를 잘 살펴보는 것이 악성 댓글 검출의 성능 향상시킬 수 있는 방법이 될 수도 있다고 할 수 있다.
여기서도 100자 미만의 문장 내에서 파악할 수 있는 감정의 크기의 한계가 드러난다는 언급이 있다.

이 논문에서의 한계점을 또 지적하자면.
무엇보다 인터넷 상에서 다양한 파생어가 발생하고,
자주 쓰이는 것들을 고려하기 위해선 자동적으로 단어 data를 만들고 이들의 sement orientation을 찾는 알고리즘이 적용되어야 한다.
또한 성능 개선을 위해 , text에서 단어들로 구분 되지 않는 룰들도 적용되어질 수 있을 것이다.



그건 그렇고....

형태소 분석기를 도데체 어디서 구할 수 있을까....

한국어 형태소 분석기는 너무 구하기가 힘들다..

이런 문제에 부딪힐 줄이야.

Opinion Analysis based on Lexical clues and their expansion

2007년 ICU 봄학기 IR수업에서 프로젝트로 했던 것과 연관된 한 논문이다.
이때... IR 수업을 들었어야 했는데...

너무 너무 아쉽다...


그래도 지나간 일은 어쩔 수 없으니 사설은 그만하고 시작해볼까.
논문은 IR랩의 김영호씨와 맹성현 교수님의 작품이다.

Opinion analysis는 기본 개념에 대해서 앞선 글에서 자세히 다뤘기 때문에 어려운 내용은 아니다. 이 논문에서는 기존 Opinion analysis에서는 다루지 않았던 opinion holder를 찾는 문제도 포함하고 있다.

논문은 세가지 문제를 다루고 있는데 subjectivity를 파악하고 semantic orientation을 찾고 마지막으로 opinion holder를 찾는 것이다.

System을 자세히 살펴보자.
1)Determining the subjectivity and its polarity

Histogram equalization

웬 뜬금 없는 Image Processing이냐 하시겠지만,
처음 관심 있었던 것이 사용자 표정 인식이었었기 때문에...

히스토그램 균등화란 gray-level에서 좁은 영역에 존재하는 픽셀들을 gray-level 전 영역으로 확장시켜 이미지의 pixel 값들이 전체 gray-level에 넓게 퍼져 이미지가 좀 더 잘 보이도록 만드는 것이다.

예를 들면 만약 한 이미지가 gray-level 0에서 10에 분포하고 있다고 하자. 이러한 이미지는 너무 어두워 식별하기가 거의 불가능 하다. 이때 Histogram Equlalization을 사용해서 0-10의 gray-level에 존재하는 pixel값들을 0-255등의 넓은 영역의 gray-level로 확장시킨다. 그러면 어두워 식별이 어려웠던 이미지가 개선되어질 것이다.

수식으로 복잡한 Histogram Equalization을 한 예로 이해해 보자.
앞서 설명한 것처럼 0-10의 gray-level에 픽셀들이 다음 처럼 존재한다고 생각하자.
gray-level pixel개수
0 5
1 5
2 3
3 2
4 8
5 10
6 3
7 5
8 1
9 2
10 6

Step1 : pixel의 전체 개수를 구한다.
5 + 5 + 3 + 2 + 8 + 10 + 3 + 5 + 1 + 2 + 6 = 50

Step2 : 각 gray-level의 확률 분포를 구한다.
gray-level 누적 확률
0 5/50 = 0.1
1 (5/50 = 0.1) + 0.1 = 0.2
2 (3/50 = 0.06) + 0.2 = 0.26
3 (2/50 = 0.04) + 0.26 = 0.3
4 (8/50 = 0.16) + 0.3 = 0.46
5 (10/50 = 0.2) + 0.46 = 0.66
6 (3/50 = 0.06) + 0.66 = 0.72
7 (5/50 = 0.1) + 0.72 = 0.82
8 (1/50 = 0.02) + 0.82 = 0.84
9 (2/50 = 0.04) + 0.84 = 0.88
10 (6/50 = 0.12) + 0.88 = 1.0

Step3 : 확장하고 싶은 gray-level의 최대 값을 각 확률에 곱해 전 영역에 골고루 퍼지도록 한다.
gray-level 균등화된 새로운 gray-level 값
0 0.1 * 255 = 25.5(반올림) = 26
1 0.2 * 255 = 51
2 0.26 * 255 = 66.3 = 66
3 0.3 * 255 = 76.5 = 77
4 0.46 * 255 = 117.3 = 117
6 0.66 * 255 = 168.3 = 168
7 0.72 * 255 = 183.6 = 187
8 0.82 * 255 = 209.1 = 209
9 0.84 * 255 = 214.2 = 214
10 0.88 * 255 = 224.4 = 224

Step4 : 이제 다시 이미지를 그려준다.
0의 gray값을 같던 pixel들은 26의 그레이 값으로,
4의 gray값을 같던 pixel들은 117의 그레이 값으로,
10의 gray값을 같던 pixel들은 224의 그레이 값으로, 등등

결국 0-255의 전체 그레이레벨로 확장될 것이다.