고요한 하늘

우연히 알게된 페이지인데

동영상이 실행되고 마우스를 움직이면 마치 카메라맨이 된 것 처럼 화면이 마우스가 움직이는 대로(좌<->우)로 움직인다.

이런 기술이 나중에 상용화가 되어 영화나 드라마에서 적용된다면 드라마 보는 재미가 이전의 그것과는 다른 형태가 되지 않을까 싶다...

모두 같은 드라마를 보고 있지만 사실은 모두 다른 화면을 보게될지도 모르겠다.

화면을 정지 해놓고 마우스를 움직여 스샷을 찍어봤다.

http://demos.immersivemedia.com/fvdemo_1/data/AmongGiants/whales.php

모든 정보를 가지고 있어서 파일 크기를 열라 큰것 같긴하다.

일반적으로 리눅스에서 작업중 튜닝이 필요할때 프로파일링 작업을 한다.

가장 일반적인 방법이 컴파일 옵션에 -pg를 주고 pgrof로 프로파일링된 내용을 보는것인데

이것과는 조금 다른 프로파일링 기법이 있어서 소개한다.

이미 많은 개발자들이 사용하고 있는 valgrind의 서브 모듈인 callgrind가 바로 그것인데

아래에 간단한 사용법을 정리하였다

 실행 방법

> valgrind --tool=callgrind ./test < input.txt > /dev/null

실행된 내용은 가지고 출력 파일을 생성한다

>callgrind_annotate callgrind.out.7838 > callgrind.out.7838.txt

사용법 보기

> callgrind_annotate --help

함수별 결과보기

> callgrind_annotate --inclusive=yes callgrind.out.7842 > callgrind.out.7842.txt

호출한 함수 목록 보기

>callgrind_annotate --inclusive=yes --tree=caller callgrind.out.7842 > callgrind.out.7842.txt

>많은 정보 보기

>callgrind_annotate --inclusive=yes --tree=both --context=100 --auto=yes --threshold=10 callgrind.out.11328 > callgrind.out.11328.txt

I   <- instruction

D  <- data

r   <- read

w  <- write

l    <- level n cache
m  <- memory

공정한 시간 측정을 위해서

우리는 문자열 비교를 위한 strcmp 함수를 해쉬와 트리 검색시 동일한 코딩 스타일을 사용한  inline code로 교체하였다.

우리는 ternary tree와 hashing의  성능 평가를 하기 위해 동일한 사전을 사용한다.

우선 각 단어를 트리에 입력한다.

아래 그림은 3개의 서로 다른 머시에 데이터를 빌드하고 검색시의 시간 측정 결과이다.

ternary search trees는 검색에 실패할때에 항상 눈에 띌만큼   해싱 보다 빠르다.

 Ternary tree 에서 일부의 캐릭터로 검색결과가 없음을 알수 있는데 반해 해싱은 모든 키를 검사한후에야 알수 있다.

길이가 긴 키 데이터군과 앞부분 몇글자가 미스매치된 군에서 ternary tree는 해싱의 1/5정도의 시간이 소요된다.

함수 insert3과 search의 결합은  symbol table의 시간 효율을 가져온다

내 웹사이트에 기술된 일반적인 사전에서 ternary search trees는 해싱의 약 1/3정도의 공간만을 사용한다.

ternary search trees의 선택적인 표기는 좀더 공간효율이 좋다.

서브 트리가 싱글 스트링을 포함할때, 문자열 자체의 포인터를 저장한다(그리고 각 노드는 그 노드가 노드 또는 스트링을 가르키고 있는지를 표시하기 위해 3비트를 저장한다

이것은 코드가 덜 효율적임을 의미한다.그러나 해싱에서 사용한 공간에 가깝게 트리의 노드를 줄인다.

 우리는 여러면에서 Ternary Search Tree의 안좋은 성능에 대해서 The Analysis of Hybrid Trie Structures 논문에 분석해 놓았다.

 binary search tree의 대부분의 표준기술은 즉시 ternary cousins에 즉시 적용할수 있다.

예를 들면 우리는 재귀적 순회로 소팅된 순서로 트리에 있는 문자열을 보여줄수 있다.

void traverse(Tptr p)

{

if(!p) return;

traverse(p->lokid);

if( p->splitchar)

traverse(p->eqkid);

else

printf("%s\n",(char*)p->eqkid);

traverse(p->hikid);

}

단순한 재귀 검색은  모든 아이템의 주어진 범위내의 주어진 성분 또는 리스트의 전임자 또는 후임자를  발견할수 있다.

만약 모든 노드에 count 필드를 추가한다면 우리는 빠르게 주어진 범위의 선택한 mth번째 가장 긴 요소 또는  주어진 서브트링으로 시작하는 많은 문자열의 수를 알 수 있을 것이다.

ternary tree 에서 이런 대부분의 연산에는 로그 시간이 요구된다.그러나 hash table에서는 linear time이 요구된다.

이 글은 스프링노트에서 작성되었습니다.

htttp://www.ddj.com/windows/184410528

당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가

존과 로버트는 binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한 ternary search trees로 시작할  것을 제안했다.

--

당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가

당신은 문자열을 array에 뿌리는 해쉬테이블을 사용할수도 있다.

이방법은 접근이 빠르다. 하지만 상대적인 순서에 대한 정보를 잃어버린다.

다른 방법은 문자열을 순서대로 저장하고 비교적 빠른 binary search trees를 사용하는것이다.

아니면 당신은 가볍고 빠르지만 공간을 많이 소비하는 digital search tries를 사용하는 것이다.

이 기사에서 우리는 binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한ternary(3-wary) search trees를 실험한다.

일반적인 검색 문제에서 이방법은 해슁을 하는 방법보다 빠르다. 그리고 다양한 기능들을 제공한다.

Ternary searches은 해슁보다 빠르고 powerful하다.

우리는 1997년 심포지엄에서 ternary search trees에 대해서 설명하였다.

아래 그림은 binary search tree로 2개의 알파벳을 갖는 12개의 노드들을 표현한다.

모든 노드에 좌측에는 자신보다 작은 값을 우측에는 큰값을 갖는다.

검색은 root에서 시작한다.

"ON"이라는 단어를 찾기 위해서 우리는 먼저 "IN"과 비교하고 오른쪽 노드로 이동한다.

그리고 다시 "OF"와 비교하여 우측 노드로 이동하고  다시 "OR"과 비교하여 좌측의 "ON" 을 검색한다.

모든 비교과정에서 두단어의 모든 캐릭터에 접근해야 한다.

Digital search tries는 문자열의 캐릭터를(1byte)를 저장한다.

아래 그림은 12개 단어셋에 대해서 Digital search tries로 표현되었다.

 각 입력 문자열은  각 노드를 표현하는 노드 바래 아래에 보여진다.

트리의 각 노드는 26개의 서브 노드를 가지고 있다.

검색은 매우 빠르다. 만약 "is"를 검색한다면 root에서 시작하여 'i'노드로 이동하고 다시 's'로 이동한다. 이것으로 검색이 끝난다.

모든 노드에서 우리는 array에 직접 접근한다.

불행히도 search tries는 엄청난 공간을 요구한다.

노드마다 26개의 branch,를 가지기 때문에 104byte의 공간을 요구하고 256개의 노드는 kilobyte를 소비한다.

8개의 노드 34000개의 캐릭터를 표현하기 위해서는 megabyte이상의 메모리를 필요로 한다.

binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한ternary(3-wary) search trees는 캐릭터 단위로 진행하는점에 있어서 tries와 비슷한다.

각노드는 3개의 children을 가짐으로써 공간적인 효율을 기함으로써 binary search trie와 비슷하다.

검색시 비교는 노드에서 문자열의 한 캐릭터와 현재 키릭터를 비교한다.

만약 검색할 캐릭터가 작으면 좌측으로 분기하고 검색할 캐릭터가 크다면 우측으로 분기한다.

만약 같다면 middle child로 이동하여 검색하는 문자의 다음 글자로 다시 위의 작업을 진행한다.

아래그림은 12개의 단어셋을 가지는 balanced ternary search tree이다.

좌우 child는 실선으로 equal pointer는 점선으로 펴현했다.

입력 문자열의 터미널 노드에 표시했다.

'is' 검색시 루트에서 시작하여 'i' 노드에서 's'로 equal child로 이동한다.그리고 's'를 비교함으로써 검색이 종료된다.

--- continued ---

invalid-file

전에는 전혀 고민의 대상이 되지 않았던 것들이 큰 부담거리로 다가온다.

대학원에서 형태소 분석기의 입력은 모두 띄어쓰기가 올바로 되어 있다고 가정하고,

띄어쓰기 오류가 틀렸다고 하더라도 그건 형태소 분석기의 몫이 아니기 때문에

처리하지 않아도 되는냥 생각했었다.

그러나 실제 서비스를 하는 필드에 와서는 앞에서 언급한 가정들이 모두 무시된다.

사용자가 잘못한것도 수정을 하여야 하고, 검색엔진의 부담을 덜어주기 위해서도 수정이 필요하다.

띄어쓰기 오류가 있는 문장은 형태소 분석기로 보내기 전에 띄어쓰기 오류를 수정하여야 하고

하나의 어절과 같이 사용되어야 하는 복합명사 형태의 단일어는 떨어져 들어오더라도 붙여서 분석을

해주어야 검색엔진의 부담을 덜어줄수 있다.(검색엔진의 부담을 덜어준다는것은 검색엔진이 위치정보를 계산한다면 두개의 어절이 입력했는지 계산하는것보다 색인시에 단일어로 만들어주는것이 검색시 시간효율이 생긴다는 의미이다. 물론 이방법을 검색에 사용할 시간을 색인시에 사용하다로 이야기할수 있다)

전자는 띄어쓰기 모듈을 개발함으로써 해결할수 있는데 후자에 언급한 떨어져 들어오는 쿼리를 하나의 어절로 만들어주는건

어떤 방법으로 구현할까..

만약 저런식으로 처리해야할 대상 어절이 많다면....그 처리 속도는...

이런 고민을 해결할수 있도록 도와준 알고리즘이 aho-corasick(이하 AC)이다.

문자열 매칭 알고리즘중 유명한것이 BM(Boyer-Moore algorithm)과 KMP(Knuth-Morris-Pratt algorithm )인데 이둘은 하나의 단어를 문장에서 찾고자 할때 효과를 볼수 있는 방법이다.

이에 반해 AC는 하나의 어절보다는 찾고자 하는 패턴이 다수일때 성능이 발휘된다.

AC를 개발하기 알아두어야 할 내용은 다음과 같다.

TRIE : 어떤 TRIE도 상관은 없다. array를 사용하는 TRIE든 Linked-list를 사용하는 TRIE든 아니면 다른 TRIE든 하나의 Node에 하나의 엔트리만 저장하는 구조라면 상관없다.

FAIL FUNCTION : KMP나 BM에서 시간을 절약하기 위해 앞에 비교한 패턴정보를 다음에 비교할 패턴에 이용한다. 흔히 FAIL FUNCTION이라고 하는데 이것에 대한 이해가 있어야 한다.

팀에 프로그램 구현능력이 좋은 분이 계셔서 테스트 버전을 7-8시간정도 걸려서 구현한것 같다.

이렇게 구현된 AC로

대상 문서 1.5G 문서

대상 패턴 : 13만개

비교시간 : 5분(딱 5분)

서버 사양은 회사기밀이라서....

여러개의 패턴을 하나의 문서에서 찾고자 한다면 AC만큼 좋은것도 찾기 어려울것 같다.

관련 자료
http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html

http://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/

이 영화를 처음본건 내가 아직 사랑을 많이 알지 못할때 였다. 그래서 그런지 그때는 주인공들의 감정선을 따라잡을 수 없었다.

같은 영화를 몇년이 지난후에 다시 봤는데 전혀 다른 느낌이 들었다. 시작하는 사랑의 설레임, 깊어가는 사랑속에 줄다리기, 이별의 아픔...

사랑이 어떻게 변하니....

참고 : http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

         http://en.wikipedia.org/wiki/Viterbi_algorithm 

대학원때 POS 태거를 구현할때 처음 접했던 알고리즘인데 태거이외에도 많은 곳에서 사용되는듯하다.

HMM이 등장하는 곳에서는 처리 속도때문에 어김없이 따라 나오는 알고리즘으로 dynamic programming과도 밀접한 관련이 있다..

음성 처리와 언어처리에서 많이 사용되지만 HMM이 앞에 두분야 이외에도 확률이 수반되는 분야에는 빠지지 않고 등장하는것 같다.

c로 프로그램 하기에는 코딩시간도 오래걸리고 나중에 봐도 기억이 안나는 관계로 open office 스프레트 쉬트로 간단히 만들어 봤다.

open office로 아래 파일을 열면 데이터들이 보이는데 데이터들에 마우스 포인터를 찍으면 안에 수식이 나타난다. 수식은 곱셈이 전부이고 함수는 max()함수가 전부이다.

max()함수는 안에 인자들중 최대값을 선택하는 함수이다. 예를 들면(ex = max(1,2,3)) 이면 max의 리턴값은 3이 된다.

각 값들이 어떤 값을 참조했고 어떤 값에 종속적인지 보기 위해서

도구(alt+t->추적(alt+d)을 클릭하면 선례추적과 종속 추적이 있는데 항목별로 선택해보면 값들의 의존관계를 볼수 있다.

단축키 : shift + f7(선례), shift +f5(종속)


이미지 출처 :    http://www.telecom.tuc.gr/~ntsourak/demo_viterbi.htm

http://en.wikipedia.org/wiki/Bayes'_theorem

첫번째 바구니 : 초콜렛 쿠키(10), 일반쿠키(30)

두번째 바구니 : 초콜렛 쿠키(20), 일반쿠키(20)

쿠키를 하나 뽑았는데 일반 쿠키가 나왔다. 첫번째 바구니에서 뽑았을 확률

조건부 확률로 표현하면

일반쿠키를 선택했는데 첫번째 바구니일 확률

P(첫번째바구니 | 일반쿠키) = ?

첫번째 바구니 = A

일반 쿠키       = B

일반 쿠키를 뽑을 확률          P(일반쿠키)       = 50/80 ( 일반쿠키 / 전체쿠키 ) , P(B) = 0.625

첫번째 바구니를 선택할 확률 P(첫번째바구니) = 1/2 ( 첫번째바구니수 / 전체바구니수 ) ,P(A) = 0.5

첫번째 바구니를 선택하고서 일반쿠키를 선택할 확률 P(일반쿠키 / 첫번째 바구니)

(첫번째 바구니의 일반 쿠키수 / 첫번째 바구니의 전체 쿠키수) =  30/40 =  P ( B | A ) = 0.75

P(A | B)  = ( P ( B | A) * P(A)) / P(B) = (( 0.75 ) * 0.5) / 0.625 = 0.6

쿠키를 하나 뽑았는데 초코렛 쿠키가 나왔다. 첫번째 바구니에서 뽑았을 확률

P(첫번째바구니 | 초콜렛쿠리) = ?

첫번째 바구니  = A

초코렛 쿠키     = B

초코렛 쿠키를 뽑을 확률 P(B) = 30 / 80 = 0.375

첫번째 바구니를 선택할 확률 P(첫번째바구니) = 1/2 ( 첫번째바구니수 / 전체바구니수 ) ,P(A) = 0.5

첫번째 바구니를 선택하고서 초콜렛쿠키를 선택할 확률 P(초콜렛쿠키 / 첫번째 바구니)

(첫번째 바구니의 초콜렛 쿠키수 / 첫번째 바구니의 전체 쿠키수) , P ( B | A ) = 10 / 40 = 0.25

P(A | B)  = ( P ( B | A) * P(A)) / P(B) = (( 0.25 ) * 0.5) / 0.625 = 0.2 (
P(A | B) = ( P ( B | A) * P(A)) / P(B) = (( 0.25 ) * 0.5) / 0.375 = 0.3333

네이버에서 끝음절 차트라는걸 만들어서 네이버 탑에 걸었다.

예를 들면

~하는방법
~협회
~소
~서

와 같이 일정한 음절로 끝나는 쿼리들의 순위들을 보여주는 서비스이다.끝음절로 사용하는것이 조금 길게 되면 비교적 통일성있는 리스트들이 보여주는 반면 1음절로 끝음절이 짧으면 기대했던 것과는 다른리스트들이 많이 올라오는것 같다.
예전에 나도 이런 서비스 생각을 했었는데 여기서 한발 더나아가 가장 사용자가 많이 찾는 답까지 보여주고자 하다 막혔던 기억이 있다.

지금도 충분히 가이드 쿼리는 많은데 정작 사용자들이 찾고자 하는건 제대로 못찾아주는 것 같아 시도했었는데 뜻대로 잘 되지 않았다.