'알고리즘'에 해당되는 글 2건

  1. 2010.03.11 Google Distance + TTA + KNN
  2. 2008.12.03 이진 탐색 (Binary-Search) (4)

Naver Perl Community & Study Cafe


2010.03.11 13:40

Google Distance + TTA + KNN


최근에 간단간단하게 짜본 프로그램이 몇가지 있는데 그 중에 하나를 소개합니다.

유사도 측정에관한 논문을 분석 후 값을 한번 짜봤습니다.

관련 URL : http://www.cs.vu.nl/~frankh/postscript/WWW07.pdf

일단 Google Distance 입니다.




단어 두개를 가지고 Google에 검색된 결과값에 따른 Distance 를 구해주는 공식입니다.

저렇게 NGD를 뽑아내는 함수만 잘 만들어 주면 구현하는데 어렵지 않습니다.


Client 가 입력하는 50개정도의 단어를 Google 에 Search 를 한 뒤

50개에 대한 f(x) 값과 f(x,y) 값을 추출하여 파일에 저장합니다.




이렇게 50개의 단어를 Word 로 받아 온 뒤 f(x) 는 npc.txt 에 저장하였고 

f(x,y) 는 npc_both.txt에 차례대로 저장하였습니다.Perl 을 사용하여 구글에서 파싱을 하였으며, 50단어를 검색하여 

각각의 파일에 저장하는데 30분 가량 걸렸습니다.


문제는 TTA 입니다 일단 알고리즘 부터 먼저 보겠습니다.





 TTA 알고리즘을 사용하면 각 단어들의 유사도를 측정하여 클러스터링을 할 수 있으며,

이 값을 Tree로 뽑아 낼 수 있습니다. 

저 같은 경우에는 직접 Tree를 짜서 구현을 하였는데,

STL 같은 부분을 사용하기 보다 직접 자기가 이해하고 

구현해보는것이 중요하다는 느낌을 많이 받았습니다.



Tree 분류후 thresholds 값에 따라 유사도가 비슷한 단어끼리 그룹을 이루게 되며,

클러스터링이 마무리 됩니다.



왼쪽의 Tree가 각 그룹별로 묶여진 형태이며 마우스로 그룹을 선택하면 오른쪽 그림과 같이

리스트뷰에 각 그룹의 요소들과 검색된 값인 NPC 값을 확인 할 수 있습니다.



그룹의 나눠지는 단계를 볼 수 있도록 출력에 신경을 써서 만들었습니다.

위 그림은 다른 먹는(?) 부분에 관해서 뽑혀진 그룹입니다.




마지막으로 KNN 을 구현하는것이 남았는데,

이렇게 클러스터링 된 그룹에서 내가 어떤 단어를 넣었을 때

이 단어가 어느 그룹에 속해지는지를 판단해서 그 그룹을 찾는 기능입니다.


C++ / MFC 로 구현한 전체적으로 구현된 프로그램 입니다. ( 보다싶이 UI는 형편없습니다..)

Input Data 버튼을 눌렀을 시 mint 를 Google 에서 Search 를 하여

각 값들에 대한 유사도를 Check 한뒤 가장 유사도가 가까운 그룹을 알려줍니다.


mint 라는 값을 검색하니 

Peppermint Spearmint 가 있는 그룹에 속해져 있다고 결과가 잘 나오는군요 :)



위의 버튼중에 Server 를 켜게 되면 쓰레드로써 외부에서 접속을 할 수 있도록 설정이 됩니다.

그 후 소켓으로 단어를 입력 받으면 

구글에서 검색 을 하여 어느 그룹에 속해있는지 Check 를 한 뒤,

소켓을 보낸 사용자에게 다시 그 결과를 보내줍니다.


소켓으로 결과를 보내는 부분은 C로 간단하게 짰는데 아래와 같습니다.




결과만 확인하기 위해 콘솔로 짰지만.. 영 볼품이 없네요 ^^;

전체적인 System Architecture 입니다.



하는 일이 많아 구현하는데 보름 가까이 걸렸는데

상당히 재밌있는 프로그램 이었습니다.


간만에 Perl 도 만져보았고, 유익한 정보를 얻은 것 처럼 재밌었습니다.

그래도 하드코어한 C는 이제 그만 짜고 싶기도 하네요 ㅡ_ㅠ



어느 누군가 이것이 필요한 프로그램이 필요할 까 싶어 블로그에 올립니다.



P.S. 어제 김길태씨가 잡혀서 한시름 놓았습니다.  :)
신고
Trackback 0 Comment 0
2008.12.03 12:51

이진 탐색 (Binary-Search)


Perl로 배우는 알고리즘에서 좋은 내용을 발췌한다.



이진 탐색은 옛부터 알려진 탐색 방법중의 하나이며

어떠한 데이터를 우리가 원하는 테이블에서 검색을 할 때.

순차적으로 검색을 하는 것보다 더 효율적으로

반씩 끊어가면서 탐색을 하는 알고리즘을 이야기한다.


뜬구름 잡는 이야기 같아 죄송하지만...

실제코드부터 먼저 보기로 하자.


1
2
3
4
5
6
7
8
9
10
11
sub binary_search{
	my ($array,$word) = @_;
	my ($low,$high) = (0, @$array -1);
	while( $low <= $high){
		my $try = int( ($low+$high)/2);
		$low  = $try+1, next if $array->[$try] lt $word;
		$high = $try-1, next if $array->[$try] gt $word;
		return $try; # 값을 찾았을 때 해당 값 리턴 
	}
	return; # 찾지 못했을 때는 undef
}


저게 무엇인가.. 외계어인가? 뭥미? 후욱후욱


그래서 말로 한번 풀이해보려 한다.



하나의 배열에 A에서 H까지 저장이 되어있다고 생각하자.

  ( A B C D E F G H )

F라는 문자가 우리가 찾을 문자다.


처음부터 순차적으로 찾아나간다면...

6번을 검색한뒤 F를 찾을 수 있다.



자 이제 이진탐색을 한번 해보자.

일단 배열을 반으로 뚝...자른다.

그리고 그 반으로 자른 중간지점을 $try라고 치고 우리가 찾을 글자와 비교를 한다.

        요놈
          ↓
A B C (D) E F G H

$try 우리가 찾을 문자열(F)가 아니다.

그러면 이 중앙의 값($try)을 우리가 찾을 문자열과 비교하여

문자열이 이 값보다 크다면 위치를 한칸 이동을 시킨다.


   여기로 이동한다.
             ↓
A B C D (E) F G H

그리고 ABCD는 모두 버린다;;


어떤가??

단 한번의 검색만으로 F의 값에 근접해 가고 있지 않는가?

이제 이 4개의 테이블 만으로 검색을 해보자.


배열을 또 반으로 자른다.

  요놈
    ↓
E (F) G H

딱 걸렸다.

문자열을 찾았으니 이 값을 반환해주면 되는 것이다.

여기까의 검색횟수는 총 2밖에 소요되지 않았다.



이렇게 절반씩 접근해서 찾기 때문에 굉장히 효율적이며

빠르게 검색하면서 찾아나간다.

그런데 여기에는 한가지 문제점이 있다.

우리가 검색할 테이블이 정렬이 되어 있어야 한다는 것!



문자열의 아스키코드 값을 비교하며 검색하는 형태이기 때문에

데이터가 정렬이 되어 있지 않다면

이 알고리즘은 대부분 무한루프가 돌 것이다.



자.. 이제 위의 소스를 다시한번 보길 바란다.

그리고 이해를 하려고 노력하자.

이해가 다 되셨다면 실제 코드에 적용시켜 활용해 보도록 하겠다.

bsearch.pl

#!/usr/bin/perl
#
# bearch - 알파벳순으로 정렬된 리스트에서 단어를 탐색
#
# 사용법 : bsearch word filename

$word = $shift;                            # 첫번째 인자를 $word에 할당
chomp(@array = <>);                        # 파일의 단어들을 읽어드린다.
                                           # 줄바꿈 문자는 제거 (chomp)
($word,@array) = map lc,($word, @array);   # 모두 소문자로 바꾼다.

sub binary_search{
	my ($array,$word) = @_;
	my ($low,$high) = (0, @$array -1);
	while( $low <= $high){
		my $try = int( ($low+$high)/2);
		$low  = $try+1, next if $array->[$try] lt $word;
		$high = $try-1, next if $array->[$try] gt $word;
		return $try; #값을 찾았을 때 해당 값 리턴 
	}
	return; #찾지 못했을 때는 undef
}

http://codepad.org/mmb8qizI

이 코드를 실제로 적용시켜 테스트를 해봐도 좋다.


개인적인 소견으로는 저 perlish한 코드를 눈에 익히고 활용하려면...

perl을 꾀 오래 써야 겠다는 생각이 든다.
신고
Trackback 0 Comment 4