[입 개발] mecab 설치 with 은전한닢 (mac)

1. Download Files
– 은전한닢 mecab & dic
* https://bitbucket.org/eunjeon/mecab-ko
* https://bitbucket.org/eunjeon/mecab-ko-dic/downloads/mecab-ko-dic-1.6.1-20140515.tar.gz
– python binding
* https://bitbucket.org/eunjeon/mecab-python-0.996

2. Build
– mecab-ko
* ./configure
* make
* make install

3. mecab-ko-dic
* ./autogen.sh
* ./configure
* make
* make install

4. python binding
* python setup.py build
* python setup.py install

5. Test

import MeCab
m = MeCab.Tagger('-d /usr/local/lib/mecab/dic/mecab-ko-dic')
ret = m.parse("아버지가 방에 들어가신다.")

아버지	NNG,*,F,아버지,*,*,*,*,*
가	JKS,*,F,가,*,*,*,*,*
방	NNG,*,T,방,*,*,*,*,*
에	JKB,*,F,에,*,*,*,*,*
들어가	VV,*,F,들어가,*,*,*,*,*
신다	EP+EF,*,F,신다,Inflect,EP,EF,시/EP+ᆫ다/EF,*
.	SF,*,*,*,*,*,*,*,*
EOS

[입 개발] org.apache.commons.codec.binary.Base64 decoding 동작에 관해서…

원래 개인적으로 삽질을 잘 하긴 하지만, 다시 최근에 큰 삽을 한번 팠습니다. 일단, 제가 자바를 잘 모르고, 초보다 보니, 남들 다 아는 지식을 모르고 넘어가는 경우가 많은데, 웬지 딴분들은 다 아셔서 이런일이 안생길것 같지만, 그냥 정리 차원에서 적어둡니다.

먼저 발생한 사건은 다음과 같습니다. 제 아이디인 charsyam 을 base64로 인코딩하면 다음과 같은 값이 나옵니다.

“Y2hhcnN5YW0=”

그리고 이걸 다시 decode 하면 “charsyam” 이라는 값이 나올겁니다. 그런데… 이제 보통 c/c++의 구현을 보면…
하다가 이상한 문자가 있으면 오류가 발생합니다. 즉 위의 “Y2hhc###nN5YW0=” 이런 글자가 있으면 일반적인 기대값은 오류라고 생각합니다.(아니라면 T.T)

그런데… apache coomons의 Base64구현은 조금 재미납니다.

“Y2hhc###nN5YW0=”
“Y2hhc#n#N#5YW0=”
“Y2hhc$$$nN5YW0=”
“Y2hhc$#n4N5YW0=”
“###Y2hhcnN5YW0=”
“###Y2hhcnN5YW0#=”
“Y2hhcnN5YW0=”

이런 것들이 모두 동일하게 “charsyam”으로 제대로 디코딩이 됩니다. 이것은 해당 코드가 DECODE_TABLE이라는 것을 가지고 여기에서 사용하지 않는 문자들은 전부 버린 뒤에 사용하기 때문에 일어나는 동작입니다. 다만 저 같은 사람은… 일단 제 코드를 의심하기 때문에, 삽질이 흑흑흑

먼저 다음과 같이 DECODE_TABLE 이 정의되어 있습니다.

    private static final byte[] DECODE_TABLE = {
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
            -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, 62, -1, 63, 52, 53, 54,
            55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4,
            5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
            24, 25, -1, -1, -1, -1, 63, -1, 26, 27, 28, 29, 30, 31, 32, 33, 34,
            35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51
    };

DECODE_TABLE 에서 -1에 지정되는 문자들은 전부 버리는 거죠. 사실 이게 apache commons base64의 문제(?)는 아닙니다. base64 에서 사용하는 table 이 사용하는 도메인에 따라서 조금씩 다르기 때문에, 이걸 전부 만족하도록 하게 구현이 되어 있는것입니다. 사실 더 많이 고려된 것이기도 하죠. 자세한건 여기(http://en.wikipedia.org/wiki/Base64)에서 확인하시면 됩니다.

그럼 이제 실제 구현을 살펴보면, 제가 말한 대로 DECODE_TABLE[value]의 값이 0 보다 클 경우에만 사용하게 되어있습니다.

   @Override
   void decode(final byte[] in, int inPos, final int inAvail, final Context context) {
       if (context.eof) {
           return;
       }
       if (inAvail < 0) {
           context.eof = true;
       }
       for (int i = 0; i < inAvail; i++) {
           final byte[] buffer = ensureBufferSize(decodeSize, context);
           final byte b = in[inPos++];
           if (b == PAD) {
               // We're done.
               context.eof = true;
               break;
           } else {
               if (b >= 0 && b < DECODE_TABLE.length) {
                   final int result = DECODE_TABLE[b];
                   if (result >= 0) {
                       context.modulus = (context.modulus+1) % BYTES_PER_ENCODED_BLOCK;
                       context.ibitWorkArea = (context.ibitWorkArea << BITS_PER_ENCODED_BYTE) + result;
                       if (context.modulus == 0) {
                           buffer[context.pos++] = (byte) ((context.ibitWorkArea >> 16) & MASK_8BITS);
                           buffer[context.pos++] = (byte) ((context.ibitWorkArea >> 8) & MASK_8BITS);
                           buffer[context.pos++] = (byte) (context.ibitWorkArea & MASK_8BITS);
                       }
                   }
               }
           }
       }

       // Two forms of EOF as far as base64 decoder is concerned: actual
       // EOF (-1) and first time '=' character is encountered in stream.
       // This approach makes the '=' padding characters completely optional.
       if (context.eof && context.modulus != 0) {
           final byte[] buffer = ensureBufferSize(decodeSize, context);

           // We have some spare bits remaining
           // Output all whole multiples of 8 bits and ignore the rest
           switch (context.modulus) {
               case 0 : // impossible, as excluded above
               case 1 : // 6 bits - ignore entirely
                   // TODO not currently tested; perhaps it is impossible?
                   break;
               case 2 : // 12 bits = 8 + 4
                   context.ibitWorkArea = context.ibitWorkArea >> 4; // dump the extra 4 bits
                   buffer[context.pos++] = (byte) ((context.ibitWorkArea) & MASK_8BITS);
                   break;
               case 3 : // 18 bits = 8 + 8 + 2
                   context.ibitWorkArea = context.ibitWorkArea >> 2; // dump 2 bits
                   buffer[context.pos++] = (byte) ((context.ibitWorkArea >> 8) & MASK_8BITS);
                   buffer[context.pos++] = (byte) ((context.ibitWorkArea) & MASK_8BITS);
                   break;
               default:
                   throw new IllegalStateException("Impossible modulus "+context.modulus);
           }
       }
   }

나름 더 정확한 내용을 알 수 있게 되긴 했지만, 제 멍청함으로 인한 삽질한 시간들은 흑흑흑… 역시… 진리는 소스입니다. 흑흑흑

[입 개발] Python Package 등록하기 – pypi

Python을 써 본 것은 오래되었지만, 실제로 이걸로 패키지를 만들어본 적은 거의 없었습니다. python c extension을 몇번 만들기는 했지만, 뭐, 내부적으로 잠시만 써봤기 때문에, 그런데 이번에 python-guoid를 만들어보면서,  이걸 pip로 인스톨되게 pypi에 어떻게 등록할 수 있을까에 대해서 찾아보고 적용르 해보았습니다.

따로, 인증을 받는 과정이 특별히 없기 때문에, 그렇게 어렵지는 않습니다. 먼저 setup.py만 잘 만들면 거의 모든게 끝납니다. 그리고 http://pypi.python.org/pypi 에서 일단 계정을 생성합니다. 그리고 다음과 같은 순서를 지키면 등록이 됩니다. 자세한 정보는 다음 페이지를 보시면 됩니다. http://docs.python.org/2/distutils/index.html

1. 먼저 pypi를 계정 정보를 가져와야 합니다.

<br /><br />python setup.py register<br /><br />

이러면 다음과 같은 선택지가 나오게 됩니다.

<br />&lt;pre&gt;running register<br />We need to know who you are, so please choose either:<br /><%%KEEPWHITESPACE%%>    1. use your existing login,<br /><%%KEEPWHITESPACE%%>    2. register as a new user,<br /><%%KEEPWHITESPACE%%>    3. have the server generate a new password for you (and email it to you), or<br /><%%KEEPWHITESPACE%%>    4. quit<br />Your selection [default 1]:&lt;/pre&gt;<br />

아까 계쩡을 만들어 뒀다면 그냥 1을 선택하고 아이디 패스워드를 입력하면 됩니다. 그러면 ~/.pypire 라는 파일이 생성되고 안의 내용이 다음과 같은지 확인합니다.

<br />&lt;pre&gt;[distutils]<br />index-servers =<br /><%%KEEPWHITESPACE%%>    pypi<br /><br />[pypi]<br />repository: &lt;repository-url&gt;<br />username: &lt;username&gt;<br />password: &lt;password&gt;&lt;/pre&gt;<br />

그 다음은 이제 실제로 올린 패키지를 만듭니다.

<br /><br />python setup.py sdist<br /><br />

sdist는 소스 패키지를 만드는 것이고 bdist를 이용해서 바이너리 패키지도 만들 수 있지만 이것은 필요없습니다.

최종적으로 다음 명령으로 등록이 가능합니다. 

<br /><br />python setup.py sdist upload<br /><br />

ps. 제가 잘못 알고 있던 부분을 수정합니다. python setup.py upload 만으로 올라가지 않고 python setup.py sdist upload 를 이용해야 합니다. 홍민희님과 박영록님 말씀을 빌리자면,

python setup.py a b c 이런 식으로 쓰는게 단순히 python setup.py a; python setup.py b; python setup.py c 이렇게 쓰는 것과 같은 게 아니구요. distutils 디자인 디테일을 좀 알명 설명하기 쉬운데, 내부적으로 Distribution 이라는 컨셉이 있고 그걸 명령어 순서대로 파이프라이닝한다고 생각하시면 됩니다. 앞쪽 명령어들에서 provide하는 메타데이터를 뒤쪽에서 consume해요.

 라고 합니다. ㅎㅎㅎ, 제가 업로드가 끝나고 나서 정리하면서 실수를 했습니다. 

 

이제 pip 명령으로 다운로드 받아지는지 확인하면 됩니다.

<br /><br />pip install guoid<br /><br />

뭐, 어줍잖은 기능이긴 하지만, 맨날 pip를 이용해서 남의 것만 설치하다가 자신의 package를 다운로드/설치가 된다는 건 참 재미있는 일입니다. 따로, 인증 과정이 없으니, 아무나 올릴 수 있다는 것도 장점입니다. 그럼 모두들 고운 하루되세요.

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – N번째 리스트 구하기

Given a singly linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned.

 

Limitations are below:

1] O(n) Time Complexity

2] O(1) space Complexity

 

solve] at first, I tried to travel twice. of course, it is very easy. but there is a better solution.

Just scan once. The main algorithm is very easy. just after kth node, traveling kth_node from head together. when list node reach the tail node, kth_node can reach kth_node.

 


void travel(int k){
 List *list = head;
 List *kth_node = head;
 int count = 0;
 while( list != NULL ){
 printf("(%d)\n", list->value);
 if( count > k ){
 kth_node = kth_node->next;
 }
 list = list->next;
 count++;
 }
 printf("(%d)th node from end is (%d)\n", k, kth_node->value );
 }

 

 

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – BST에서 중복 개수 새기

Write an algorithm to print out how many extra duplicates there are in a binary search tree. and using global value for count and value

 

example]

———– 3

—2—————– 3

– 1 —2 ——————4

———————3 ———4

————————————–5

———————————————–5

output :

2  1

3  2

4  1

5  1

 

solve) Focus on, O(n) time complexity and O(1) space just travel this BST tree using inorder sequence.

 


void _traversePrint(Node *node){
 if( node->left ){
 _traversePrint(node->left);
 }

if( count && (value == node->data) ){
 count++;
 }else{
 if( count > 1 ){
 printf("(%d):(%d)\n", value, count);
 value = node->data;
 count = 1;
 }else{
 count = 1;
 value = node->data;
 }
 }

if( node->right ){
 _traversePrint(node->right);
 }

if( node == root && count > 1 ){
 printf("(%d):(%d)\n", value, count);
 }
 }

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 공통 선조 찾기

Design an algorithm to find the least common ancestor of two nodes in a Binary tree(Note: Its not a binary search Tree)
Node Structure is given as

Class Node{
int data;
Node leftchild;
Node Rightchild;
}

solution) I just think that if one node notice that there are 2 nodes that we want to find. it is the common ancestor of two nodes. so it's solution is really easy to understand.


int find_node2( Node *node, int value1, int value2 ) {
 int ret = 0;
 if( node->data == value1 || node->data == value2 ) {
 ret++;
 }

if( node->left ) {
 ret += find_node2( node->left, value1, value2 );
 }

if( node->right ) {
 ret += find_node2( node->right, value1, value2 );
 }

if( ret == 2 ){
 printf("this node is common parent: %d(%d,%d)\n",
 node->data, value1, value2);
 }

return ret > 0 ? 1 : 0;
}

[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 꼬여있는 코일

• Given an 4n X 4n Matrix, where n is a positive integer taken as input. Imagine the matrix consisting of two interleaved coils whose centers are at the centre of the matrix. Implement a java program which takes an integer (n) as input and prints the two coils in two seperate lines.

Please have a look at the below examples to get a sense of what the two coils are :
• Example 1:
• Input: 1
• Matrix:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16

• Output the Two Coils as:
– Coil1: 10 06 02 03 04 08 12 16
– Coil2: 07 11 15 14 13 09 05 01

 

Solution.

I can easily guess. there are some rules. the start point are always (2n, 2n+1) and (2n+1, 2n) and there are 4 directions which follow this order: UP, RIGHT, DOWN, LEFT. and  In (2n,2n+1)  case it starts from UP, and (2n+1, 2n), it starts from DOWN. so I can easily calculate next values.

 


#include <stdio.h>
#include <stdlib.h>

#define DIRECTION_NUMBER 4
#define STEP 2
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

void find_direction( int x, int y, int n, int direction ) {
 int end = n * n * 4 * 2;
 int step = STEP;
 int current_direction = direction;
 int pos_x = x;
 int pos_y = y;
 int delta = 0;
 int count = 1;

int seed = (y-1)*4*n+(x);
 printf("%d", seed);
 while( count < end ) {
 for( int i = 0; i < STEP; i++ ) {
 switch( direction ){
 case UP:
 delta = -(4*n);
 break;
 case RIGHT:
 delta = 1;
 break;
 case DOWN:
 delta = 4*n;
 break;
 case LEFT:
 delta = -1;
 break;


 }

for ( int j = 0; j < step && count < end; j++ ) {
 seed += delta;
 printf(" %d", seed, delta );
 count++;
 }

direction++;
 if( DIRECTION_NUMBER == direction ){
 direction = UP;
 }
 }
 step += STEP;
 }
 printf("\n");
}

int main( int argc, char *argv[] ){
 int n = atoi(argv[1]);
 find_direction( 2*n , 2*n+1, n, UP );
 find_direction( 2*n+1, 2*n , n, DOWN );
 return 0;
}