'분류 전체보기'에 해당되는 글 219건

애드센스가 구글 Analytics에 통합이 되었다.
물론, 기존 애드센스 화면은 그대로 유지가 된다.

통합해서 사용을 하면 다 알다시피 한 사이트에서 필요한 여러 부분들을 관리할 수 있어 좋다는 장점이 있다.

일단, 구글 Analytics에 로그인을 한 후, 왼쪽 메뉴에 "콘텐츠"를 클릭하게 되면 최하단에 "애드센스"라는 메뉴가 존재한다.

이 메뉴를 클릭을 하게 되면 기존 애드센스의 화면을 좀 더 자세하게 볼 수가 있다.
그 각 기능들에 대해서 살펴보자.

애드센스 메뉴를 클릭하면 나오는 첫 화면이다.
기본적으로 한 달 기준으로 나오는데, 기간을 달리해서 보고 싶다면 오른쪽 상단에 ▼을 클릭하면 원하고자 하는 기간에 대한 분석 결과가 나온다.
일단, 기본적인 한 달을 보자.
수익이랑 수익률은 애드센스 정책에 어긋나서 지웠다.
아직 초짜라서 수익률이 많지는 않다. ㅠ.ㅠ
어쨌든, 기간 동안의 수익율을 그래프로 표현이 되니, 한 눈에 알아보기 쉽다.
그 아래 정보로는 애드센스 수익에 대한 세부적인 정보를 보여준다.
애드센스 수익, 1000회당 방문당 애드센스 수익, 애드센스 광고 클릭수, 방문당 애드센스 광고 클릭수, 애드센스 클릭율, 애드센스 유효 CRM....
각 정보를 다시 클릭을 하게 되면 날짜별로 비율 막대 그래프로 표시가 된다.
위 화면은 애드센스 수익을 막대그래프로 보여주는데, 수익 또한 삭제를 했다.

최근 애드센스 수익이 많이 발생한 포스트는 어떤 것인가도 궁금할 것이다. 이런 것들을 파악하기 위해 clickaider와 같은 클릭 발생 로그 프로그램을 이용하곤 했는데, 굳이 그럴 필요가 있을까 라는 생각도 들긴 한다.

이러한 궁금증도 "애드센스 세부정보"에 자세하게 나온다.
애드센스 인기 포스트와 나의 포스트를 추천해주는 사이트 순위가 나온다.

아래 사진은 애드센스 인기 포스트를 수익률 기준으로 내림차순으로 보여준다.
이걸 안다면 주로 어떤 포스팅을 해야 클릭이 자주 발생할까를 고민할 수 있을 것이다. 그러나, 전문 블로거가 아니라면 해당 내용을 계속해서 기고할 수 있을까라는 생각이 든다.
나같이 널부리는 스타일이라면 쉽지는 않을 것이다. 그래도 관련된 내용을 향후에라도 포스팅을 하게 된다면 좀 더 정성스럽게 작성하지 않을까 싶다.

아래 사진은 내 블로거를 방문하는 사용자들이 어떤 경로로 오는지를 알아볼 수 있다.
나 같은 경우에는 주로 네이버 검색을 통해 들어온 방문객들이 클릭하는 확률이 높았다. 그렇다면 내 블로거가 네이버 검색에서 상위에 올라오게 하기 위한 전략을 세워야한다.

기존 광고프로그램인 애드센스보다 더 자세하게 나와 있지만, 이건 분석용으로 사용하는 것으로 만족하는 것이 나을 거 같고, 수입에 대한 내용은 간단하지만 한 눈에 들어오는 기존 애드센스를 이용하는 게 나아 보인다.

** 관련 글 **
블로그 로그, 통계관리 (구글 통계, Google Analytics)

어린이 날 경남 고성 공룡 세계 엑스포에 갔다가 애들한테 기념이 될 만한 몇 가지를 샀다.
다른 곳에서 파는 기념물과 차별화가 있기도 하고 해서 선뜻 손이 가게 되었다.
첫째 놈에게는 스테고사우루스 조립 킷과 공룡 퍼즐, 둘째 놈에게는 물먹는 공룡...


첫째 놈이 어린이집 다녀오자 말자 만들잔다...
 나두 같이 놀아주기 위해 포장지를 뜯었다.
허걱, 좀 사이즈 큰 놈으로 샀는데, 4개나 있다.

일단 해보자는 생각에 다 뜯긴 했는데, 젠장할 설명서가 없다.
"이게 모지... 설명서도 없이 어떻게 이걸 조립하지?"
그냥 맞춰볼려구 하다가 도저히 할 수가 없었다.
'설명서가 있을거야'라며 다시 뒤져봐도 없는 것이다.
거의 포기하다 시피하다가 표지 뒷면에 있는 3개의 타국어로 되어 있는 설명서를 보았다.
제품이 made in china라서 그런지 아래 사진의 표지 뒷면에 외국어로 간단한 설명이 있었다.
젠장~
애들하고 간단히 놀려구 하는데두  외국어 실력이 필요하다니...
찬찬히 영어로 된 설명을 읽었더니, 1번과 1번, 2번과 2번, 3번과 3번을 matching 시키란다.

그리하여, 직접 끼우는 건 애한테는 힘들어 보여서 첫째 놈은 해당 번호에 해당 킷을 찾아 나에게 주면 나는 조심스레 끼우기 시작했다.
첫째 놈도 번호 찾는 것도 재미있어 하구, 해당 킷을 찾는 것도 재미있어해서 다행이었다.
또한, 하나 하나 완성되어 가는 공룡 모형도를 보고 더 신났다.

사실, 첫째 놈이 직접 만들었으면 더 좋았을 걸 하는 생각이 들긴 했는데, 그러기엔 무리였다.
그리하여, 30여분간의 시간을 소요한 후 드디어 완성했다.

중국산이라서 그런지 딱딱 안 맞는 것이 있었다. 공간이 헐거운 부분이 있었다.
눈에 보이지 않게 종이로 부족한 공간을 메꿨더니 훌륭한 스테고사우루스가 되었다.

50여개의 작은 킷을 하나 하나 맞추다보니 집중력이 배가가 되긴 했다.

위 사진이 아래 사진과 비슷한가?
첫째 놈은 스테고사우루스의 조립 모형도를 들고
"할아버지, 할머니, 이거 스테고사우루스 뼈예요~, 멋있죠???"
ㅋㅋ

이거 모양으로만 봐서는 육식공룡인 줄 알았더니, 찾아보니 초식공룡이네..
암튼, 아들 놈과 간만에 하나의 목표를 위해 즐거워했다.

** 관련 글 **
2009 경남 고성 공룡 세계 엑스포

어린이날 어디 갈까 고민하다가 아내의 전 직장 동료가 고성 공룡 엑스포로 간다는 소식에 우리도 가자라고 급조하여 가게 되었다.

요즘 길을 찾거나 지도를 보게 될 일이 있으면 꼭 다음 지도를 사용하게 된다.
각 교차점이나 포인트별로  좌측에 자세한 설명이 나와 있다. 게다가 거리 뿐만 아니라 시간과 택시 요금까지 안내가 된다. 덕분에 우리는 네비게이션이 없음에도 불구하고 제 길로 빠른 시간 내에 다녀올 수가 있었다.

아무튼, 우리는 당일로 다녀와야 했기에 아침에 준비해서 일찍 출발한다고 했는데 역시 어린이날 이라서 마산시내 지나자 말자 고성 당항포관광지까지는 밀리기 시작했다.
밀리기 시작하면 누구나 짜증이 나기 마련이다. 그래서, 혹시나 하는 마음에 미리 봐둔 해안도로로 길을 잡았다. 마산 요양병원 좀 지나서 암하삼거리에서 77번 지방도로로 접어들었다.
그냥 시내로 둘러서 가는 것보다 해안도로로 가는 것이 기분도 좋을 거 같았고, 거리나 시간상으로도 5분 정도 빨랐기 때문에 선택한 길이였는데, 의외의 수확을 얻었다.
이 길이 한국의 아름다운 길 중에 하나였던 것이었다.

이 곳에서 10여분 정도 가면 드디어 공룡 엑스포가 열리는 당항포 관광지이다. 우리는 환영의 문을 통해 입장을 하였다.
입장료는 어른 14,000원, 어린이 8,000원이고, 36개월 미만은 무료이다. 현대카드로 결재를 하면 동반 3인까지 2,000원씩 할인이 되어서 우리는 4식구에 30,000원을 입장료로 지불했다. 할인을 받았지만 그래도 가격이 높다는 생각이 들긴했다.

우리는 미리 준비해간 김밥과 주먹밥을 도시락 먹는 장소에서 맛있게 먹고, 본격적으로 관람에 나섰다. 어린이날이라서 로보트 복장을 한 아저씨들과 포토 타임도 있었다.

전 날부터 애들이 아빠 지금 공룡 보러 가자고 얼마나 재촉하던지...
그 덕인지 애들은 공룡 앞에서 갖가지 포즈를 취하면서 사진을 찍었다.
그런데,  나는 공룡 이름들을 잘 모르겠던데, 첫째 놈은 이건 모고, 저건 모다 라고 척척 말하는 것이 놀라울 따름이였다.

좌(左)에서 우(右)로 조바리아, 이구아나돈, 양추아노사우루스 헤핑엔시스

우상(右上) 트리케라톱스,  좌하(左下) 에우오플로케팔루스, 우하(宇下) 수코미무스

참으로 이름이 어렵다... ㅋㅋ
한반도 공룡 발자국 화석관은 각종 화석과 돌 종류, 발자국, 찰흙 체험이 있었는데, 이 날따라 너무 더워서 빨리 나오고 싶었다.
많은 사람들이 좁은 공간을 줄지어 가느라 구경보다 짜증부터 밀려 나왔으니 말이다.

나오자 말자, 바로 중생대 공룡관으로 바로 들어갔는데, 이 곳은 탁 트인 곳에 공룡 화석을 조립해 놓아서 덥지는 않았다.

이 공룡은 초식 공룡인지 모형에서도 나뭇잎을 먹는 모습을 보여주고 있다.
이 공룡은 단순히 모형이 아니라, 내부에 1, 2층으로 이루어져서 공룡시대의 생활상들을 커리어쳐들로 보여주고 있는데, 공간은 좁은데다가 사람들이 많아서 공기가 안 좋았다.

더운 날씨에 애들이 힘들어 하길래, 잠시 기다리라고 해 놓구선 20분을 줄서서 기다려 사 온 아이스크림을 먹여주고 있다.
이 더운 날씨에 아이스크림은 애들에겐 오아시스처럼 보였는지 너무나 좋아했다.

언덕 너머로 가니 군함이 정박하여 어린이날 행사를 하고 있었다.
군함 옆의 요트 정박지에는 수상 자전거를 이용할 수 있도록 해 놓았다.
물론, 애들이고 어른이고 두당 4,000원이다. 36개월 미만은 무료이구..
20분간 타도록 되어 있는데, 누가 시간 재는 사람도 없고 해서 힘겹고 지겨울 때까지 탄다.
공주님은 무릎에 앉히고, 왕자님은 앞 의자에 앉혔는데, 아무래도 자세가 나오지 않아, 왕자님은 서게 하고 공주님은 앞 의자에 앉혔더니, 10분 뒤에서 앉아서 잔다... ㅠ.ㅠ

첫째 놈은 재미있다고 빨리 가자고 성화구, 이제 그만 타자고 해두 "2바퀴만 더~", "1바퀴만 더~"... 정말 첫째 놈이 지겨워질 때까지 탔다. 둘째 놈이 자던지 말던지... ㅋㅋ
그 덕에 나는 다리에 알이 박히구... ㅠㅠ.

수상자전거 체험장을 나와 자연사 박물관을 거쳐 거북선 체험관으로 가는 도중 해변이 아름다워 한 컷...
둘째 놈은 자다가 깨서 멍한지 엄마만 찾는다~

휴~
한쪽에는 공룡과 화석에 관련된 공간이 3~4만평 정도 되구, 반대편은 충무공 이순신 장군과 관련된 공간이 3~4만평이다.
정말 걷다 걷다 지쳐버린다.
반대편까지 가서는 도저히 되돌아 올 힘이 없어 두당 1,000원씩 주고 셔틀 버스를 타고 왔다.
그 시각이 6시 정도였는데, 애들이 아쉬워하는 거 같아 페이스 페인팅도 해주고, 부메랑 사서 부메랑 던지며 놀았는데...

그때 저편에서 지나가는 아내의 전 직장 동료... 남기훈씨...
만나서 수다 떨다가 기훈씨가 애들 데리고 로봇바이크를 태워준다.
로봇이라는 놈이 우스꽝스러운 걸음으로 바이크를 이동시켜준다.
보고 있노라면 정말 웃긴다.

기훈씨는 하루 더 묵고 온다고 하여 우리는 7시 30분 경에 고성에서 출발하여 집으로 돌아왔다.
돌아오는 2시간여 동안 애들은 정말 신나게 놀고 즐겼는지 곤히 잠들었고, 아내도 피곤이 몰려온다며 잠을 청할려구 했구, 나 또한 전날 4시간 잔 탓과 5시간의 운전과 7시간의 움직임에 완전 파김치가 되었지만 정말 행복했었다.

간만에 애들을 행복하게 해 줄 수 있어서 좋았고, 간만에 아빠 노릇을 한 거 같아 좋았다.
이 날 이후 공주님은 엄마보다 아빠가 더 좋단다. ㅋㅋ

** 관련 글 **
아들과 함께 한 스테고사우루스 (Stegosaurus) 조립 킷

최근에 받은 문제 중 하나가 이런 내용이 있었다.

두 문장의 차이점을 출력하는 프로그램을 작성하라. 두 문장은 동일한 문장을 조금 바꾼 것으로 아래와 같은 3개의 차이점이 있을 수 있다.
- Text could be deleted.
- Text could be inserted.
- Text could be changed.
원래 문장과 새로운 문장의 차이점을 모두 출력한다.

<Input>
텍스트 파일을 입력으로 한다.
비교할 두 개의 문장을 입력 받는다. 각 문장은 줄바꿈 문자로 구분하며, 각 문장을 text1, text2라 할 때 text1은 원래 문장, text2는 새로운 문장이 된다.

<Output>
다음과 같은 형태의 두 문장의 차이점을 모두 출력한다.
- deletion : 삭제된 문자와 그 위치 그리고 삭제된 문자의 개수

위 내용이 논문에 소개된 글이다. 정말 재미있는 소개글이지 싶다. 우리가 흔히 들어왔던 로그 함수를 그리는 데이터 구조를 이해하고 구현하는 것이 얼마나 어려운가?, 로그적인 시간 내에 사전적인 문제를 풀기 위해 프로그래머의 머리 속에서 얼마나 많은 뉴런들이 타버려야 하는가?
나는 위 소개글을 읽고 한바탕 웃고 말았다. 그런 반면 Skip List에 대한 기대감에 차게 만들었다.

특징 몇 가지를 살펴보자.
1. 똑같은 입력 값이라고 하더라도, 입력 순서에 따라 트리의 모양은 달라진다.
2. 실 구현은 배열과 Linked List로 구현 가능하다.
3. 구현하기가 일반 다른 알고리즘보다 훨씬 간단하다.
4. Top-Down 방식으로 삽입, 검색, 삭제가 이루어진다.
5. 최악의 검색 비용 log(n)을 가지는 몇몇 deterministic version(1-2 Skip List, 1-2-3 Skip List)을 표현한다.


1-2 Skip List에서 최대 개수의 포인터는 절대 2n을 초과하지 않는다. (배열 구현시)
배열 구현시 삽입과 삭제시 비용이 높아진다. 삽입시 비용이 높아지는 것은 다른 알고리즘과 비슷하여 큰 문제가 되지 않으나, 삭제시 그 만큼의 비용이 발생한다는 것은 문제이다. (삭제 연산이 많이 발생하지 않는다면 상관없다.) 따라서 이 문제를 해결하기 위해서 우리는 배열 구현을 Linked List로 구현을 하면 된다. 그러나, 배열 구현보다 3배의 요구 공간(6n)이 요구된다. Linked List로 구현한다는 것은 노드를 올리거나 내리기 위해 단지 몇몇 포인터만 변경만 하면 되기 때문이다.

1-2 Skip List는 높이 h-1에 1 또는 2 노드가 존재하고 있다.  1-2 Skip List와 2-3 tree간의 비교는 쉽게 일반화되어진다. 또한 1-2-3 Skip List는 높이 h-1에 최소 1개 최대 3개의 노드가 존재한다. 이 또한 2-3-4 트리와의 비교가 쉽게 된다. 삽입, 검색, 삭제 알고리즘은 하단에 Pseudo Code가 있으니 별도의 설명은 생략을 하며, 필요하신 분들은 논문을 직접 읽어보면 될 듯하다.
 

아래의 Pseudo Code는 Linked List를 기반으로 한 Pseudo Code이며 배열 코드는 인터넷에 검색을 해보면 코드들이 많이 있다.

1. Search Pseudo Code
논문에 나와 있는 내용이다. 검색 모듈이 2개가 있는데, 1번째는 거의 Binary Search Tree와 같다. 위 모듈은 bottom이 아닌 말단 노드까지 진행을 해야 한다.

2. Insert Pseudo Code
위 모듈을 한 번 그려보면, 거의 포인터만 옮기는 수준이다. 다른 알고리즘에 비하면 정말 간단하다. 이 모듈 또한 논문에서 제공이 된다.

3. Delete Pseudo Code
위 삭제 알고리즘은 내가 직접 구현한 내용이다. 약간 모자라는 부분이 있지만, 삭제하면서도 1-2-3 Skip List를 유지해야 하므로, 삽입 알고리즘보다 약간은 길다. 약간 어설프긴 하지만 돌아가는데에는 무리가 없다. 시간 나는대로 손을 봐서 좀 더 완벽한 모듈을 구현해야 하는 숙제가 남아 있다.

아무튼, 위 논문대로 복잡도라든지 코드 구현 내용이라든지 전혀 다른 알고리즘에 비해 뒤질 것이 없어 보인다. 역시 사람은 공부해야 하는가보다. 공부를 안 하면 이런 좋은 알고리즘이 있는지 없는지 조차 모르니 말이다.

** 관련 글 **
http://research.cs.queensu.ca/home/daver/235/C2102557243/E20070330101410/Media/SkipList.pdf
http://www.cs.ucr.edu/cs141/cs141_04sum/
http://en.literateprograms.org/Skip_list_(C_Plus_Plus)
http://www.cosc.canterbury.ac.nz/research/RG/alg/dict.html
http://www.ddj.com/184404217
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

요약을 추출하는 알고리즘은 전형적으로 구문 추출에 대한 기술에 기반을 둔다. 그리고, 그러한 구문 셋을 인식하고자 하는 시도는 주어진 하나의 문서에 대한 이해에 있어서 굉장히 중요하다. 

요약을 추출하기 위해 많은 알고리즘들은 언어 지식에 의지를 많이 하고 있으며, 특히, 다른 언어로 이루어진 문서에 대해서는 상당히 많은 수정을 해야한다.
게다가 성능을 측정하기 위해서 다듬어진 데이터 셋을 통해 자신만의 편리성을 추구하는 경우도 많다.
TextRank는 이러한 제약에서 자유롭다고 볼 수 있다.
특징은 다음과 같다.

일반 랭킹 알고리즘은 각 문서들을 하나의 정점(Vertex)로 바라보지만, TextRank는 하나의 문서에서 각 sentence를 하나의 정점(Vertex)으로 인식을 한다.
또한, incoming, outgoing의 의미도 incoming은 다른 sentence에 현재 sentence에 존재하는 word가 있는지를 체크하고, outgoing도 마찬가지로 현재 sentence에서 다른 sentence에 word가 존재하는지를 체크한다. 이것을 content overlap이라 표현한다.

이 과정에서 몇가지 선행이 되어져야 한다. punctation 문자라든지, stopwords(불용어)에 대한 처리를 미리해야 된다. 굳이 의미없는 word는 삭제하겠다는 의미이다.

일단, 여러 랭킹 알고리즘 가운데 PageRank와 HITS에 포커스를 맞춰 살펴본다.

PageRank는 아마도 가장 유명한 알고리즘 중 하나이며, Web-link 분석에 대한 방법으로서 디자인되어졌다. 다른 그래프 랭킹 알고리즘과 달리 PageRank는 하나의 싱글 모델에 incoming과 outgoing 링크의 impact를 통합한다. 따라서, Score는 하나의 셋만 도출한다.

Out(Vj)는 그래프의 j번째 정점(Vj)에서 outgoing되는 edge의 개수.

이 결과에 d는 0과 1사이로 셋팅하는 파라메터이며, random walking model내에 random jump에 대한 임무를 지녔다. d는 일반적으로 0.85로 셋팅하는 걸로 되어 있다.

위 PageRank 식을 TextRank에 적용하면 다음과 같다.

이 등식 중 이 부분의  의미는 Vi로 outgoing하는 Vj에 incoming하는 정점의 weight들의 합계를 Vj의 pagerank의 값을 나눈 값에 weight를 곱한 것이다.
등식을 이해하는 것에 별 어려움이 없어 보인다.

HITS는 authority의 정도에 따라 Web Page를 랭킹하고자 디자인된 반복적인 알고리즘이다. HITS 알고리즘은 authority와 hubs를 구분한다.
"authority"는 incoming 링크를 가진 페이지로, "hubs"는 outgoing 링크를 가진 페이지로 정의한다.
각 정점에 대해서, HITS는 "authority" score와 "hubs" score라는 2개의 셋을 산출한다.

위 HITS 식을 TextRank에 적용하면 다음과 같다.
HITS 알고리즘은 incoming 랭킹 값이 우선시 되고, incoming 랭킹 값이 같을 경우 outgoing 랭킹 값을 비교한다.

그런데, PageRank나 HITS 알고리즘에서 기존 정점에 대한 랭킹은 어떻게 알까?
즉, 등식을 보더라도 PR(Vj)와 HITS(Vj) 값을 이용하게 된다. 그렇다면 이 값은 어떻게 알아내는 것일까?
답은 쉽다. 초기값을 0에서 1사이의 값으로 임의의 배정을 한 후 위 식들을 대입하되, 벡터간의 거리가 threshold 값에 근접(convergence)할 때까지 반복한다. 단, HITS는 쉽게 convergence가 되지 않는 경우도 발생하므로, 최대 10~20까지만 반복하는 조건이 필요하다.
일반적으로 threshold는 0.01 내지 0.001를 사용한다.

유사성(similarity)는 content overlap을 통해 획득하게 되는데, abusing 데이터를 처리하기 위해 normalization을 하게 된다.

분모에서 log 함수를 사용하는 것은 abusing 데이터를 처리하기 위한 normalization 작업이며, Wk는 두 sentence에 모두 존재하는 word이며 분자는 그런 word들의 개수가 된다.

이 정도만 알고 있다면, TextRank에 대한 구현은 어려운 문제는 아니다.
Matrix를 작성하고, 각 (i, j)의 값에 랭킹(PR(Vi), HITS(Vi), HITS(Vj))를 구하고, threshold값에 근접할 때까지 반복하기만 하면 된다. 단, 주의 사항은 PageRank에 대한 TextRank 등식을 보면 루프 구문을 3번 돌아야 한다. 한 문서에 1,000개의 구문이 존재한다면, 1,000 X 1,000 X 1,000 번의 루프를 돌아야 하는 비효율적이나, 등식을 잘 보면 1,000 X 1,000 + 1,000으로 변경할 수 있다.

다음은 TextRank를 구하기 위한 전체적인 알고리즘 diagram이다.


많은 연구 결과에서 요약에 대한 결과는 만족스러운 수준으로 나왔고, 사람의 눈으로 확인한 결과만큼이나 괜찮은 결과를 획득했다고 했다.

나 또한, 직접 프로그래밍을 한 후 그 결과를 확인해보고 깜짝 놀랄 말했다. 영어 문서이든 한글 문서이든 상당한 결과를 볼 수 있었다.

** 관련 글 **
http://www.aclweb.org/anthology-new/P/P05/P05-3013.pdf
http://www.aclweb.org/anthology-new/P/P04/P04-3020.pdf
http://www.icmc.usp.br/~taspardo/NAACL07-LeiteEtAl.pdf
http://users.dsic.upv.es/~dpinto/miniproject/ProjectTextRank.pdf

Edit Distance란?

위키피디어(http://en.wikipedia.org/wiki/Edit_distance)에 정의된 것을 보면,

일반적으로 어떤 Vertex간의 거리는 개념이 일반화가 되어 있어서 쉬우나, 정의를 보지 않고 문자열간의 거리라 함은 이해가 잘 안되기도 한다.
벡터간의 거리는 쉽게 유클리안 거리를 이용하면 되지만...
혹시, 문자열간의 거리도 벡터로 변환 후 유클리안 거리를 이용하나?
답은 정의를 보면 변환하기 위해 요구되어지는 연산의 수가 문자열간의 거리이다.

이때 필요한 연산의 수는 다음과 같이 정의가 된다.
변환(change), 삽입(insertion), 삭제(deletion) 3가지 연산이 필요하다.

change : symbols at corresponding positions are distinct
insertion : a symbol of y is missing in x at a corresponding position
deletion : a symbol of x is missing in y at a correspoinding position.
(in order to transform x into y)

예를 들어,
1. x: "abc" --> y:"abd"
   x 문자열을 y 문자열로 변환하기 위해서는 마지막 문자 "c"를 "d"로 바꾸기만 하면 된다.
   즉, change 라는 연산 한 번만 발생하기 때문에 x와 y의 거리는 1이다.

2. x: "park" --> y:"spake"
   이 문제는 조금 애매하지 않은가? 어떻게 변환을 할지...
   그러나, 조금만 생각해보면 x의 1번째 문자 앞에 y의 "s"를 삽입(insertion)하고,
   x의 3번째 문자 "r"을 "k"로 변환하고, x의 5번째 문자 "k"를 "e"로 변환을 하면 된다.
   1번의 삽입과 2번의 변환이 이루어졌으니, 거리는 3이다.

   또 다른 방법으로,  x:"p" -> y:"s", x:"a" ->y:"p", x:"r" -> y:"a", y:"e"를 x의 마지막 문자로
   삽입하는 경우도 가능하다. 이 경우는 3번의 변환과 1번의 삽입이 이루어졌으니,
   거리는 4가 된다.

   위 2번 예제에서 최적의 거리는 3이다.

이것이 edit distance이다.
그렇다면, 어떻게 최적의 거리를 찾을 것인가가 문제이다.
그 최적의 거리를 찾기 위해 우리는 Dynamic Programming Method를 사용한다.
물론, 그래프 알고리즘 가운데 다익스트라(Dijstra, 네덜란드인) 알고리즘을 사용해도 되나,
일반적으로 Dynamic Programming Method를 이용한다.

간단하게나마, Dynamic Programming Method를 살펴보자.
실행 시간의 정보를 기록한다는 의미이다. 즉, 중복되는 계산 결과를 기록해서 중복된 계산 결과가 필요한 경우, 최대한 재계산을 피하고자 하는 것이다.
다른 말로 해석하자면, 작은 문제들의 해를 먼저 구하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다.
한마디로, divide-and-conquer 이다. 분할 정복한다는 의미이다.
가장 이해하기 쉬운 것이 재귀호출로 여기면 될 것이다.

아무튼, Dynamic Programming Method 기법을 적용하여 Edit Distance를 구하고자 하는 식은 다음과 같다.
 

위의 예제에서 Edit Distance를 구하기 위해 작성된 Matrix 내용을 보자.

이로써, Edit Distance는 x라는 문자열을 y라는 문자열로 변환하기 위해 수행되는 연산의 수가 되면 그 연산은 Dynamic Programming을 통해 구해질 수 있다.

그러나, 우리가 Edit Distance를 구하기 위해 m X n의 matrix를 사용해야 되나? 라는 의문은 갖지 않는가? 희소행렬 (sparse matrix)를 이용해도 충분할텐데 말이다...

그러나, 우리가 Edit Operations을 구하기 위해서는 반드시 m X n의 matrix가 필요하다.
Edit Operations는 Back Tracking을 하면서 optimal path를 구하기 때문이다.
Edit Operations은 이미 위의 2번 예제에서 살펴보았다.
즉, 두 문자열간의 optimal path를 보여주는 과정이다.
연속된 문자들 "- a"는 문자 'a'를 삽입(insertion)한다는 의미이며, "a -"는 'a'를 삭제(deletion)한다는 의미이다. 즉, "- a"는 y의 문자가 "-"에 삽입되어져야 할 자리이며, "a -"는 x의 문자를 삭제해야 한다는 의미이다. 변환(change)는 굳이 작성하지 않아도 된다. 어떻게 보면 x와 y의 문자들을 서로 교환을 해야 된다는 의미인데 굳이 표현할 필요는 없다는 뜻도 된다.
위 2번 예제를 다시 보면,

즉, Edit Operations은 위와 같은 형태를 만드는 행위라 보면 된다.
이 행위 또한 Edit Distance를 획득하기 위해 만들어진 matrix를 사용해야 하며 위의 의미 그대로 작성하면 된다.

Edit Operations을 구하는 pseudo code는 아래와 같다.

이 과정을 수행하면서 다음과 같은 문자열에 대해서 테스트를 해보라.

optimal path는 3~4가지가 나올 수 있다.
그 중 하나의 값을 살펴보면 다음과 같다.
(참고, 그 결과를 보고 싶다면, http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/) 를 참조하라.

위 결과를 보고 짐작할 수 있듯, 삽입은 x의 문자열에서 발생을 하고, 삭제는 y의 문자열에서 발생을 한다.
즉, 의미상 x 문자열이 기준이 된다. x에 y의 문자를 삽입하고, x의 문자를 삭제하고..
예를 들어, mccoh-n은 y의 문자 'e'를 x에 삽입하고자 하는 것이며, --cohen은 x의 문자 'm'과 'c'를 삭제하겠다는 의미이다.

문자열간의 거리를 체크하여 두 문자열간의 유사성을 체크한다는 것은 재미있는 일이다.
검색에서의 사용을 예를 들자면, 두 문서의 제목에 대해서 Edit Distance를 사용하여 유사성을 체크할 수도 있는 일이다.
http://www-scf.usc.edu/~audhkhas/kws_audhkhasi_icassp07.pdf

Video, Image 처리 분야에서도 Edit Distance / Edit Operations을 이용을 많이 하는 것 같다.
자세하게 보지는 않았지만, 2개의 Image간의 유사성을 체크할 수 있지 않을까??
http://www-stat.stanford.edu/~idrori/Vidop.pdf
http://www.micc.unifi.it/publications/2006/BDN06a/bertini-civr06.pdf

한글에 대해서는 어떻게??
한글 검색어 간 유사도를 위한 Levenshtein distance 함수
이 블로그에서 잘 설명이 되어 있으니 참조를 하구...

** 관련 글 **
문장 비교
http://www.cs.umass.edu/~mccallum/courses/cl2006/lect4-stredit.pdf
http://www.cs.ucr.edu/~stelo/cpm/cpm05/cpm05_8_4_Touzet.pdf
http://www.cs.duke.edu/courses/fall05/cps230/L-04.pdf
http://www.aistudy.co.kr/math/shortest_johnsonbaugh.htm

** 소스 **

최근 시골에 내려와 유유자적 아이들과 아내와 시간을 보내고 있다.
물론, 몇 가지 준비를 하면서...

집 안에 쳐박혀 컴퓨터로만 무언가 하는 내가 안쓰러웠는지
어제 장모님이 유등제 가자고 하여 찾아간 곳이다.
올해로 3회를 맞이하는 역사가 그리 깊지 않은 축제이긴 하나,
이곳은 불교 단체가 주체가 되어 행사를 하기에 말 그대로 연등과 각종 불교 행사가 겹쳐 치뤄지고 있다.

장모님은 스님들의 승무를 그렇게 보고 싶다고 하셨는데, 불행히 그 행사는 전날 치루어졌던 모양이였다.
다른 축제에 비해 규모가 크지는 않았지만, 물에 떠 있는 대형 연등이 밤에 불을 밝히며 장관을 이루었고, 한 쪽에는 연꽃을 만드는 체험 코너와 갖가지 먹거리 코너가 마련되어 있었다.

누구나 그렇겠지만, 난 축제 행사장에 가면 항상 찾는 곳이 체험 코너이다.
아이들에게도 좋은 추억이 될 뿐만 아니라, 나 스스로도 체험하지 못한 많은 것들을 쉽게 경험할 수 있음에 반드시 하나는 체험하고 온다는 생각을 가지고 있다.
이 날도 첫째 놈이랑 연꽃을 만들어봤다.
막상 불교신자임에도 불구하고, 한 번도 연꽃을 만들어 보지 못했는데, 이날 좋은 경험을 했다.
첫째 놈은 꽃잎에 열심히 풀을 칠하고, 나는 종이컵에 열심히 붙이고...

그 결과 예쁜 연꽃을 만들었고, 옆에 있던 다른 여자 관람객분께서도 정말 예쁘게 잘 만들었다고 추켜 세워주셨다.

해지기 전까지는 날이 따뜻하더니, 해가 지고 나면서 바람도 세차고 기온이 급강하는 하는 바람에 굉장히 추웠다.

그걸 증명하기라도 하듯 강변에 떠 있는 부처님과 석탑 유등을 배경으로 사진을 찍는데, 첫째 놈의 저 리얼한 표정을 보면 굳이 내가 따로 설명하지 않아도 될 듯하다.

강 위에 떠 있는 몇몇 조형물들을 찍었는데, 많은 사진이 흔들리고 그나마 잘 나온 사진은 요거 밖에 없다.

정말 아담하고 이쁘지 않는가...(내 눈에만 이뻐 보이는감?? ㅋㅋ)
아무렴 어떠랴... 난 캄캄한 밤에 불빛을 밝히며 어두운 세상을 밝혀주는 저 유등이 이쁠 뿐이다.
요즘같이 정치나 경제가 캄캄할 때 저렇게 밝은 빛이 나와주면 얼마나 좋을까?

암튼, 그런 생각 속에 노래 자랑을 구경하던 중 낯익은 연예인들이 자리 배석함에 연신 셔터를 눌렀으나, 역시 카메라가 안 좋은 건지, 실력이 안 좋은지...
사회를 보는 이홍렬 아저씨와 심사를 보는 전유성 아저씨~

청도에 사시는 분들은 알테지만, 전유성 아저씨는 청도에서 찻집을 운영하며 살고 있고, 그런 인맥으로 이홍렬 아저씨가 직접 내려와서 사회를 보게 되지 않았을까라고 짐작해 본다.
이홍렬 아저씨가 무대 위에서 잠시 내려와 있을 때 사진을 같이 찍을려고 했으나, 젠장~
조금 덜 충전시킨 배터리 때문인지 카메라가 밥 달라는 아우성 때문에 포기하고 아쉬운 발걸음 뒤로 하고 돌아가야만 했다.

돌아오는 길 마지막으로 파랑새 다리를 배경으로 오늘의 축제를 아쉬움으로 달래야 했다.

최근에 재테크와 관련된 책들을 주로 읽고 있다.
재테크를 어떻게 하면 잘 할 수 있을까를 고민하면서도 제대로 공부해 본 적도 없었고,
어설픈 지식으로 실전에 대할 때마다 항상 깨지는 모습을 보면서 자책하는 모습도 싫었다.
아직, 읽고 공부해야 할 책들이 많고, 지금은 눈에 보이는대로 책을 읽고 있다.
눈에 보이는 책들 중에 이제 1/3 정도 읽은 거 같다.
그런데 아직 공허함이 남아 있다.

이 책은 제목에서 20대를 위한 책임을 나타내고 있지만,
재테크에 있어서는 나도 20대라는 생각으로 서슴없이 집어들어 읽었다.
물론, 나는 30대이고 가정도 있고 20대처럼 행하지는 못하지만 몇 가지 얻어 지식도 있다.


이 책에서도 말하지만, 장기 투자를 제대로 하려면 사회의 거시적인 흐름을 볼 줄 아는 안목이 필요하다. 인간과 사회를 탐구하는 역사학, 철학, 사회학에 대한 공부가 필요한 것이다.
지금껏, 재테크를 위해서 실용서적 위주로 읽었는데, 고전도 읽을 필요를 느꼈다.

<로마제국쇠망사>, 에드워드 기번
<역사란 무엇인가>, E.H 카
<군주론>, 마키아벨리
<동주 열국지>, 풍몽룡
<소유의 종말> <노동의 종말>, 제레미 리프킨
<세계화 이후의 부의 지배>, 레스터 C, 서로우
<돈, 사랑한다면 투자하라>, 앙드레 코스톨라니
<존 템플턴, 월가의 신화에서 삶의 법칙으로> 로버트 하만
적어도 이 책만은 읽어라고 권장하고 있다.
부자가 되는 길은 그리 평탄하고 쉽지만은 않다는 것을 새삼 느낀다.


가끔 뉴스를 통해 갈수록 우리나라 경제성장률이 낮아진다는 보도를 볼 때, 왜 그럴까라는 의문만 가졌지 알아볼 생각은 안 했다.
그 이유는 2가지로 볼 수 이다.

이로 인해 낮은 경제성장률과  함께 금리도 저금리도 간다. 개발도상국은 하루가 다르게 경제가 발전하기 때문에 돈 벌 기회가 많다. 이 때문에 많은 기업들이 은행에서 돈을 빌리려고 한다. 선진국이 되면 앞서 말한 여러가지 이유로 경제 성장률은 떨어지고 기업의 공격적 투자는 줄어들게 된다. 투자가 줄어들면 기업들이 은행에서 대출하려는 수요도 줄어든다. 당연히 은행 입장에서는 금리를 낮추어 기업들의 대출 수요를 높이려고 한다. 선진국이 될수록 금리는 계속 낮게 갈 수 밖에 없는 것이다.


주식과 채권의 차이는 알고 있는가?
주식투자는 기업의 가능성을 보고 자금을 투자한다는 개념이다. 하지만 채권은 기업이 발행한 회사채로 채권자가 기업에 돈을 빌려주고 이자를 받는 개념이다. 채권은 엄밀히 말해 투자보다는 '차용증서'의 개념에 가깝다.
예를 들면, 두 사람이 각각 동일한 회사의 '주식'과 '채권'을 보유하고 있다고 해보자. 만약 이 회사가 부도난다면 어떻게 될까? 결론은 간단하다. 주식을 가진 사람은 알거지가 되지만 채권을 가지고 있던 사람은 나중에 돌려받을 수 있다. 그 이유는 '주주'와 '채권자'라는 두 사람의 신분 차이 때문이다.


평소에 몇 가지 궁금했고 의문시되었던 점들을 이 책을 통해서 해결이 되었고, 조만간 아파트 입주를 앞두고 대출을 받아야 되는데, 고정금리가 유리한지 변동금리가 유리한지를 고민하고 있었는데, 어느 정도 해소가 되었다.
역시, 공부를 해야 한다.