[Algorithm] KMP algorithm

String match algorithm인 KMP algorithm은 text에서 뛰어넘을 수 있는 만큼 뛰어넘으면서 string이 match되는지 확인한다. 여기서 얼마나 뛰어넘을 수 있는지에 대한 정보를 얻기 위해 Failure function이라는 함수를 이용한다.

Failure function은 찾으려는 string의 각 위치마다 공통인 prefix와 suffix의 최대 길이를 찾아 저장해둔다. 예를 들면, “ababa” 는  { 0, 0, 1, 2, 3 } 과 같이 저장한다. 구현 시에는 -1 해서 저장한다. 예에서의 값은 { -1, -1, 0, 1, 2 } 이 된다.

void get_failure_function(char str[], int len, int failure[])
{
	int i;

	failure[0] = -1;

	for (i = 1; i < len; i++) {
		int f = failure[i - 1];

		while (1) {
			if (str[i] == str[f + 1]) {
				failure[i] = f + 1;
				break;
			}
			if (f <= -1) {
				failure[i] = -1;
				break;
			}
			f = failure[f];
		}
	}
}

 

찾을 때는, 위에서 계산한 값을 이용해 string을 찾는 도중에 틀리면 바로 이전까지 맞았던 부분의 failure function value를 찾아 이전까지 같은 부분을 건너뛰고 다음 부분부터 비교한다. 예를 들어, 위의 string을 찾으려고 할 때, text가 “ababcababa” 라면, string의 처음부터 비교하다가 5번째에서 틀리면, 4번째까지는 맞으므로, 4번째의 failure function value를 찾으면 2이다. 이는 앞의 2글자는 맞다는 말이므로, text에서 4-2 만큼을 건너뛴 후, string의 3번째부터 다시 비교한다. string의 3번째도 틀리므로, 2번째의 failure function value를 찾으면 0인데, 이는 0만큼 맞다는 말(=하나도 안맞다는 말)이므로 text를 2-0 만큼 건너뛴 후, string의 1번째와 다시 비교한다. string의 첫번째와 다르면  1만큼만 이동하고, 다시 1번째와 비교한다. 맞았을 때도 맞은 부분만큼을 이용해서 건너뛴다(5번째에서 맞았으므로, 3글자가 맞고, 5-3만큼 이동한 후, 4번째부터 비교).

아래 구현은 match되는 개수를 return하도록 하였다.

int get_matched_count(char text[], int text_len, char string[], int str_len, int failure[])
{
	int count = 0;
	int t = 0;
	int s = 0;

	while (t < text_len - str_len + 1) {
		while (s < str_len) {
			if (text[t + s] != string[s])
				break;
			s++;
		}

		if (s == str_len) {
			// MATCH!
			count++;
		}

		if (s < 1) {
			t++;
			s = 0;
		} else {
			t += s - 1 - failure[s - 1];
			s = failure[s - 1] + 1;
		}
	}

	return count;
}

 

앞 부분과 공통 부분이 없는 string인 경우, 더 빨리 건너뛴다. 예를 들면, “abababababc” 에서 “ababc”({ 0, 0, 1, 2, 0 })를 찾는 경우, 5번째에서 틀리면, 앞에서부터 0글자가 같으므로, 4-0만큼 이동한 후, 1번째부터 다시 비교한다.

위 두 구현 함수의 사용 부분은 다음과 같이 될 것이다.

		int T, S;
		int count;
		int *failure_function = NULL;

		char *text = "ababcababababababababa";
		char *string = "ababa";

		T = strlen(text);
		S = strlen(string);

		failure_function = (int *)malloc(sizeof(int) * S);
		// skip the check of the memory allocation

		get_failure_function(string, S, failure_function);

		count = get_matched_count(text, T, string, S, failure_function);

		printf("%d matched\n", count);

 

[Algorithm] Union & Find – Disjoint-set structure

Union & find 연산은 서로 다른 그룹을 하나의 그룹으로 합칠 때 사용한다. Minimum spanning tree를 만드는 Kruskal 알고리듬 등에서 사용한다.

어떤 A B C D E F G H의 8개의 항목들이 1~4까지의 그룹에 속해 있을 때, 각 항목의 그룹이 다음과 같이 있다고 하자.

{ A – 1, B – 1, C – 2, D – 2, E – 3, F – 3, G – 3, H – 4 }

여기서 각 항목이 가진 그룹만 보면 { 1, 1, 2, 2, 3, 3, 3, 4 } 와 같다.

언뜻 생각해보면, B 항목이 속한 그룹(1번 그룹)과 G 항목이 속한 그룹(3번 그룹)을 합쳐서 { 1, 1, 2, 2, 1, 1, 1, 4 } 와 같이 만든다고 하면, G가 속한 그룹(3번 그룹)을 찾아서 이 그룹인 모든 항목(E, F, G)을 찾아서 1번 그룹으로 바꿔주어야 하므로 모든 노드를 확인해서 3인 그룹이 있다면 1로 바꾸어야 한다. 이걸 모든 노드를 돌면서 확인하면서 바꾸지 않아도 할 수 있게 만드는 게 disjoint-set structure의 union & find 연산이다.

그룹을 합칠 때는, 둘 중 어느 하나를 parent로 만드는 tree 구조를 이용한다. 즉, 하나의 tree에 있는 모든 노드는 하나의 그룹이 된다. 이걸 다시 쓰면, 어떤 노드의 root 노드와 다른 어떤 노드의 root가 같다면, 같은 그룹이다.

 

n개의 항목이 있다면 다음과 같이 n개 항목에 대한 배열(parent)을 잡아 각각의 항목의 index로 그룹명을 잡는다(rank 배열은 모두 1로 하고, union 연산에서 설명한다).

void makeset(int parent[], int rank[], int n)
{
	int i;
	
	for (i = 0; i < n; i++) {
		parent[i] = i;
		rank[i] = 1;
	}
}

 

Find 연산은 어떤 항목이 속한 그룹 번호, 즉, tree에서의 가장 상위 노드, root 노드의 번호를 반환한다. Optimization을 위해 어떤 항목이 find 연산 도중에 parent를 거쳐서 root까지 도달한다면, 그 항목과 그 parent모두를 해당 노드의 parent만 찾으면 root가 되도록 parent를 root로 바꾸어준다. 예를 들어, { A, B, C, D, E, F, G, H }가 { 0, 0, 2, 2, 0, 4, 3, 3 }과 같이 있을 때의 그림은 다음 그림의 왼쪽 그림과 같다. 이 때, F 항목에 대해 Find 연산을 하면 root 까지 가는 과정 중에 있는 노드들을 모두 parent가 root가 되도록 다음 그림의 오른쪽 그림과 같이 바꾼다. 이로써 parent 노드들 및 자신 중 어떤 노드가 어떤 그룹에 속하는지를 나중에 찾을 때(root까지 갈 때), 바로 찾아갈 수 있도록 한다.

 

int Find(int parent[], int x)
{
	if (x != parent[x])
		parent[x] = find(parent, parent[x]);

	return parent[x];
}

 

Union 연산은 두 항목의 root를 같게 만들어 두 항목이 속한 두 그룹을 하나의 그룹으로 합친다. 다시 쓰면, 자신들의 root를 찾아, 이 root 중 한 노드를 다른 root노드의 parent로 만들어 하나의 root로 만든다. 이 과정에서 각각의 항목이 find 연산을 하게 되는데, 이 때, 위에서와 같이 각각의 root까지 찾아가면서 거치는 모든 parent들도 모두 각각의 root를 바로 위 parent로 갖게 만들어 tree의 깊이를 낮춘다. Tree의 깊이가 깊어지면 자신의 그룹이 어떤 것인지를 아는데(root까지 찾아가는데) 시간이 오래 걸리므로, tree의 깊이를 깊게 하지 않기 위해서 find에서 깊이를 낮추는 것 외에 union 연산을 할 때, rank를 이용한다. 두 root 노드의 rank를 비교해 두 root 노드 중 rank가 높은 노드가 새로운 root가 된다. 또한, rank는 어떤 노드가 자신과 rank가 같은 다른 노드의 parent가 되면 1씩 증가한다. 따라서 rank 값은 자신의 sub tree가 최대로 깊이가 깊어졌을 때 rank + 1이 된다. find 연산을 거치면 깊이가 낮아지지만, rank가 증가한 후, root부터 어떤 leap node까지의 모든 노드가 한번도 find를 수행하지 않았다면, 최악의 경우 rank 깊이의 노드가 존재한다. 하지만, 서로 다른 rank의 두 root 가 합쳐진다 rank가 낮은 root노드의 tree는 항상 rank가 더 높은 tree의 sub tree가 된다. 이는 항상 최대 깊이를 rank 이하로 보장한다. 위의 예에서 F와 H의 그룹끼리 합친다고 하면 다음 그림과 같이 된다. 빨간색으로 표시한 값은 rank 값이다.

int Union(int parent[], int rank[], int x, int y)
{
	int rootX = find(parent, x);
	int rootY = find(parent, y);

	if (rootX == rootY)
		return 0;

	if (rank[rootX] < rank[rootY]) {
		parent[rootX] = rootY;
	} else if (rank[rootX] > rank[rootY]) {
		parent[rootY] = rootX;
	} else {
		parent[rootX] = rootY;
		rank[rootY]++;
	}
	
	return 1;
}

쓰고나니 주저리주저리 너무 길다.

[맛집] 한국커피 – 경기도 광주 능평리

오늘 핸드 드립 커피 전문점이라는 기흥의 ‘떼레노시떼’라는데 왔는데 커피 맛은 한국커피가 제일 맛있었던 것 같다.

여기선 브라질과 마일드를 마셨는데, 좋은 편이다. 괜찮은 걸 마셨더니 더 맛있던 게 생각나서 적는다.

[맛집] 신승반점 – 판교 현대 백화점

판교 현대 백화점 갈 때 마다 줄이 엄청 길게 서있던데, 오늘은 좀 일찍 갔더니 줄이 짧아서 한 번 가보았다.

이 집의 추천 메뉴는 찹쌀 탕수육과 유니 짜장면이란다. 찹쌀 탕수육은 맛있다. 익힌 돼지고기가 찹쌀 튀김옷에 싸여 있다. 유니 짜장면은 맛이 그냥 그렇다. 둘다 줄을 길게 서서 기다려서 먹을만큼 맛있지는 않다.

[맛집] 초당 순두부

초당 순두부는 김영애 할머니와 김정옥 할머니, 두 집이 라이벌 구도로 맛있다고 한다.

최영업씨 말로는 김영애 할머니 댁이 자기 입맛에 딱 맞아서 아침마다 갔다고 한다. 자기가 어디가서 연속 두번 간 가게는 처음이라며…

추천 맛집도 기록해두고 필요할 때 찾고자 한다.

해외 직구, 미국내 오배송 시 물건을 찾을 수도 있는 방법

미국내 배송 중간에 물건이 사라져 맘고생하고 있을 해외 직구 이용자들을 위해 남깁니다.

해외 직구 이용시, 많은 사람들이 세금 문제로 배송대행지(이하 배대지)로 델라웨어Delaware를 많이 씁니다.  배대지 주소를 제대로 적고, 트래킹 번호도 제대로 적었는데도 배송 상태에는 도착(Delivered) 상태로 바뀌었지만 실제 입고되지 않는 사례들이 있습니다. 그래서 배송업체의 트래킹 정보를 찾아보면, 수령인 사인이 있는데, 자신이 이용한 배대지에서 자신들의 수령인 사인과 다르다며 구매처나 배송처로 연락해보라고 합니다. 이런 경우는 대부분 델라웨어 배대지들이 같은 우편번호를 쓰기 때문에 구매처에서 배대지로의 배송과정에서 물건이 섞여 다른 배대지로 운송되는 경우가 많기 때문인 듯 보입니다(그래서 뽐뿌의 해외 포럼같은 경우 이용자들 자체적으로 수령인 사인을 모아서 공유하기도 합니다).

Fedex나 USPS, UPS같은 배송업체의 잘못이지만 배대지로서도 자신들에게 오지 않은 상품을 책임져주지는 않습니다. 물론 제 생각엔, 배대지에서 검수 시나, 패키지 확인 시 자신들의 주소로 오지 않은 상품을 다시 배송업체로 반송해주거나 원래 가야할 주소로 보내주면 해결되는 문제지만, 그럴 생각은 별로 없는 거 같아 보입니다. 다시 반송을 해주는지, 잘못 온 물건은 자기 돈 내고 산 물건도 아닌데 그냥 그대로 먹는지, 어쩌는지 확인할 방법은 없습니다.

아무튼 그래서 구매자인 우리가 할 수 있는 방법은, 구매처에 일단 클레임을 거는 1차적인 방법 외에, 같은 우편번호를 쓰는 모든 배대지에 가입해서 배송대행신청서를 작성하는 겁니다. 배대지에서 대부분의 경우, 트래킹번호를 스캔해서 이와 맞는 배송대행신청서를 찾으므로 다른 배대지로 배송된 경우, 해당 배대지에 내가 신청서를 작성하고, 1:1 문의로 Order ID와 Tracking number로 문의해서 있다면, 배송대행결제 대기 상태로 바뀌면서 결제하라고 알려줍니다. 유명 배대지의 경우 뽐뿌 해외 포럼게시판 상단의 “배대지 가격비교”를 보면 DE를 이용할 수 있는 배대지를 확인할 수 있습니다. 이 외에 DE 중 같은 우편번호를 사용하는 배대지를 직접 검색해서 가입해도 됩니다.

실제로 제가 이렇게 찾았습니다. 오마X집으로 보낸 물건이 고X송에 가있는 것이 아니겠어요(둘다 같은 우편번호를 사용합니다)?! 자기네 물건도 아닌데 까서 착실히 검수까지 하고 사진까지 찍어두었습니다. 어이가 없습니다. 타 업체와 아무리 경쟁 상대라지만, 이러면 안되는거 아닌가 싶습니다.

꼭 물건 찾으시기를 바랍니다. 물건 찾는데 도움이 되었으면 하네요.

오마X집의 대처
고X송에서 결제대기 문자가 왔다. 착실하게 사진까지 찍어 검수까지 해뒀다. 자기네 물건 아닌데….

[git] git tips 한국어판

​https://github.com/mingrammer/git-tips/blob/master/README.md

감옥으로부터의 사색 – 청구회 추억

읽는 중 입꼬리가 슬슬 올라가게 만드는 흐뭇하면서도 유머있는 글이었다. 마지막 부분의 어찌보면 희극적인 비극을 제외하면.

60-70년대의 우리 글은 너무나도 정답고, 의젓하며, 점잖으면서도 정겹다. 우리말의 맛이 난다.

아! 이런 글, 너무 좋아!

[RaspberryPi] minidlna-transcode 설치

라즈베리 파이로 DLNA 뷰어를 통해 동영상을 보려니 코덱 문제로 음성이 안나오는 것들이 있어서 minidlna-transcode로 트랜스코딩을 시도해 보았다. 결론만 말하면 실패. 컴퓨팅 파워 문제인지 툭툭 끊긴다.

원리는 설정된 특정 코덱을 사용하는 동영상은 보내기 전에 설정한 스크립트에서 ffmpeg를 통해 인코딩을 해서 쏘는 것으로 보인다. 설치하다보니 Debian에서 ffmpeg가 avconv로 이름이 바뀌었다는 것도 알게 됐다.

minidlna는 라즈베리안의 경우 현재 1.1.2버전을 apt-get으로 그냥 설치할 수 있다. 트랜스코딩없이 쓴다면 그냥 패키지 설치하는게 맘 편할 수 있겠다. 내가 시도한 방법은 소스 컴파일 설치이다.

  1. 소스 컴파일 설치

먼저 git으로 clone해온다.

$ git clone -b transcode https://bitbucket.org/stativ/readymedia-transcode.git

컴파일에 필요한 패키지를 설치한다.

$ sudo apt-get install libexif-dev libjpeg-dev libid3tag0-dev libflac-dev libvorbis-dev libsqlite3-dev libavformat-dev libavutil-dev libavcodec-dev  libmagickwand-dev autoconf autopoint gettext libav-tools libav-dev mpv

아래 패키지는 이름이 그럴듯해서 그냥 설치해봤는데 확실치 않다. mpv의 경우, mencoder가 또 저걸로 바뀌었대서 깔았는데, mencoder를 이용하진 않아서 잘 모르겠다.

$ sudo apt-get install libavcodec-extra libavcodec-extra-56 mpv

컴파일한다.

$ ./autogen.sh
$ ./configure
$ make

그럼 다음과 같은 컴파일 에러가 난다.

minidlnad-upnphttp.o: In function `SendResp_dlnafile':
/home/pi/src/readymedia-transcode/upnphttp.c:2041: warning: the use of `tmpnam' is dangerous, better use `mkstemp'

tmpnam()이 위험하니까 mkstemp()를 이용하라는 거니까 찾아서 바꿔준다.

$ vi upnphttp.c

char tmp[L_tmpnam];
mkdtemp(tmp);

다시 컴파일하면 잘 된다. 설치를 sudo make install로 해줘도 되는데(사실 이렇게 한 후에 checkinstall을 사용했다-_-), 패키지를 만들어 설치하면 나중에 제거가 편하다. checkinstall이 없으면 설치(sudo apt-get install checkinstall)한 후에 아래 명령을 준다.

$ sudo checkinstall

아래와 같은 게 나오면 ‘Y’

아래와 같은게 나오면 난 MiniDLNA Version 2015-06-18 Compiled June 18, 2017 라고 입력했다.

그럼 아래와 같은게 나오는데, 여기서 3번, 버전만 숫자로 시작해야해서 아래처럼 2015-06-18 로 입력했다.

3 - Version: [ transcode ]
3 - Version: [ 2015-06-18 ]

 

2. 설정

이제 소스 내에 있는 설정 파일을 /etc/ 아래로 복사해서 설정을 시작하자.

$ sudo cp minidlna.conf /etc/minidlna.conf

sudo를 매번 입력하기 귀찮으니 sudo -i 를 입력해서 root shell로 작업하자.

# vi /etc/minidlna.conf

설정 파일에서 아래 “media_dir”, “friendly_name”을 각자 환경에 맞게 적자. “media_dir”은 예상하듯이, 미디어가 있는 경로, “friendly_name”은 DLNA 기기에서 나타나는 이름이다.

media_dir=V,/mnt/NAS/Videos
friendly_name=DasomOLI DLNA

“audio_codecs”나 “video_codecs” 에 적혀있는 코덱에 해당하는 미디어 파일이 재생되면, 그 아래의 “transcode_audio_transcoder”혹은 “transcode_video_transcoder” 에 적혀 있는 스크립트를  실행한다. 원하는 코덱을 transcoding하고 싶다면 해당 코덱을 적어주자. 어떤 것을 적어야 하는지는 avconv -formats 라고 입력하면 찾아볼 수 있다.

transcode_audio_codecs=flac/vorbis/dts
transcode_audio_transcoder=/usr/local/share/minidlna/transcodescripts/transcode_audio
transcode_video_transcoder=/usr/local/share/minidlna/transcodescripts/transcode_video

transcoding 스크립트는 /usr/local/share/minidlna/transcodescripts/ 아래에 있다. 옵션을 변경하고 싶다면 해당 스크립트를 수정한다. 옵션을 변경하지 않더라도 수정을 해주어야 하는데 ffmpeg 대신 avconv를 사용해야 하기 때문이다.

# vi /usr/local/share/minidlna/transcodescripts/transcode_audio

#!/bin/sh

SOURCE=$1
STARTPOSITION=$2
DURATION=$3

#ffmpeg -ss $STARTPOSITION -t $DURATION -i "$SOURCE" -loglevel quiet -acodec pcm_s16le -f s16le -ar 44100 pipe:1
avconv -ss $STARTPOSITION -t $DURATION -i "$SOURCE" -loglevel quiet -acodec libmp3lame -f mp3 -ar 44100 -ab 224k pipe:1

# vi transcodescripts/transcode_video

#!/bin/sh

SOURCE=$1
STARTPOSITION=$2
DURATION=$3

avconv -ss $STARTPOSITION -t $DURATION -i "$SOURCE" -loglevel quiet -threads auto -async 2 -target pal-dvd pipe:1

# vi transcodescripts/transcode_video-hq

#!/bin/sh

SOURCE=$1
STARTPOSITION=$2
DURATION=$3

avconv -ss $STARTPOSITION -t $DURATION -i "$SOURCE" -loglevel quiet -threads auto -async 2 -vcodec mpeg2video -b:v 20000k -f mpegts pipe:1

위와 같이 ffmpeg가 적힌 곳에 avconv를 써주면 된다.

이제 실행하려면 다음과 같이 한다. -R 옵션은 DB update를 해주는 거니까 매번 하진 말자.

/usr/local/sbin/minidlnad -R -f /etc/minidlna.conf

 

3. 자동 실행

매번 위처럼 실행하긴 귀찮으니까, 부팅될 때마다 자동 실행 되도록 하자. /etc/init.d/안에 minidlna 파일을 새로 생성해서 아래와 같이 내용을 채운다. Process가 2개 되는 경우가 보여서 참고로 보았던 글에 있는 스크립트를 좀 수정했다.  잘안되면, 뭐 또 수정해야지..

# vi /etc/init.d/minidlna

#!/bin/bash
# Mini DLNA
### BEGIN INIT INFO
# Provides:          scriptname
# Required-Start:    $remote_fs $syslog
# Required-Stop:     $remote_fs $syslog
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Start daemon at boot time
# Description:       Enable service provided by daemon.
### END INIT INFO

case "$1" in
'start')
        /usr/local/sbin/minidlnad -f /etc/minidlna.conf
        echo Started
        ;;
'stop')
        PIDS=`/bin/pidof minidlnad`
        if [ "${PIDS}" != "" ];
        then
                for PID in ${PIDS};
                do
                        kill -SIGTERM ${PID}
                done
        else
                echo Already Stopped
        fi
        ;;
'restart')
        PIDS=`/bin/pidof minidlnad`
        if [ "${PIDS}" != "" ];
        then
                for PID in ${PIDS};
                do
                        kill -SIGTERM ${PID}
                done
        fi
        /usr/local/sbin/minidlnad -f /etc/minidlna.conf
        echo Restarted
        ;;
'status')
        PID=`/bin/pidof minidlnad`
        if [ "${PID}" != "" ];
        then
                echo Running. Process ${PID}
        else
                echo Stopped
        fi
        ;;
'rescan')
        PIDS=`/bin/pidof minidlnad`
        if [ "${PIDS}" != "" ];
        then
                for PID in ${PIDS};
                do
                        kill -SIGTERM ${PID}
                done
        fi
        /usr/local/sbin/minidlnad -R -f /etc/minidlna.conf
        echo Rescanning
        ;;
*)
        echo "Usage: $0 { start | stop | restart | status | rescan }"
        ;;
esac
exit 0

위 파일에 실행 권한을 주자.

# chmod a+x /etc/init.d/minidlna

실행되도록 rc.d를 업데이트 하자.

# sudo update-rc.d minidlna defaults

 

참고:

https://www.htpcbeginner.com/install-minidlna-on-ubuntu-ultimate-guide/