'IT' 카테고리의 글 목록

About ZooKeeper

IT/개념 2017. 4. 19. 11:29

분산 작업 제어 트리 형태의 데이터 저장소
- 분산된 어플리케이션들을 위한 분산 Coordination 서비스입니다.
- Coordination이란 다양한 노드가 함께 잘 어울릴 수 있도록 동작하도록 조정하는 행위

Zookeeper의 Cluster를 Ensemble(앙상블)이라 부름.

위 Zookeeper 클러스터는 자동으로 Leader를 선정하며 이 Leader는 데이터 저장을 주도합니다.
클라이언트가 Follower 노드로 데이터 저장 요청이 들어오면 Follower는 Leader에게 전달하고
Leader는 과반 이상의 Follower가 쓰기 가능한 상태가 되면 Follower에게 쓰기 명령을 한다.
반면, 데이터 읽기 요청은 어떤 노드(Leader or Followers)로 들어와도 즉시 데이터를 리턴한다.

클라이언트는 단일 Zookeeper 서버에 연결하고, TCP 연결을 유지합니다.
TCP 연결이 끊어지면 다른 서버에 연결을 시도합니다.

활용 용도

분산 서버간의 정보 공유
서버 투입 / 제거 시 이벤트 처리
서버 모니터링
시스템 관리
분산 락 처리
장애 상황 판단
데이터 변경을 감시

위 활용도 중에 데이터 변경 감시를 위한 Watcher 활용도가 가장 높습니다.
데이터가 변경되면 Data Polling없이 특정 Node에 등록되어 있는 Watcher의 콜백으로 알려줍니다..
그러나, 주의하셔야 할 것이 자주 변경되는 데이터를 감시하는 곳에는 사용하지 않는 것이 좋습니다.
Zookeeper가 버벅댑니다 ㅠ.ㅠ

Zookeepr가 데이터를 디렉토리 구조로 저장을 하고,
지속성(Persistent)을 위해 트랜잭션 로그, 스냅샷 파일을 디스크에 저장을 합니다.
서버를 재시작을 해도 서비스가 유지되도록 하기 위합니다.

또한, 중요한 기능 중에 하나는 노드별 ACL(Access Control List)를 제공해줍니다.
Zookeeper와 같은 코디네이션 시스템은 중요한 상태 정보나 설정 정보를 유지하기 때문에 시스템에 망가지면 전면 장애로 이어지는 경우가 발생할 수 있어서 적어도 이중화를 유지하여 고가용성을 유지합니다.
그러다 보니, Zookeeper를 유지함에 있어서 물리적으로는 시스템 낭비가 심한 경우에 포함이 되죠.
다만, 하나의 클러스터를 구성하여 여러 어플리케이션이 사용하면 시스템 낭비를 줄일 수 있는데,
여기서 문제점은 여러 어플리케이션이 여러 노드에 접근 가능하여 오히려 보안성에 문제가 발생할 수 있는데
이럴 경우에는 ACL 기능을 사용하면 좋겠습니다.

저작자표시

'IT > 개념' 카테고리의 다른 글

[웹 2.0] 소개 (0)	2008.05.22
Mash-up 이란... 오십세주 (0)	2008.02.18

쩐의시대

나답게 살아가고 나답게 살아가자

,

쉘에서 정렬(sort)하고 유니크(uniq)한 내용 추출

IT/shell 위 댄스 2017. 4. 5. 21:46

<쉬어 가는 코너>

sort | uniq를 사용합니다.

그러나, 위 명령보다는 sort -u가 I/O 소모가 덜합니다.

기왕 사용하는 거 효율적인 방법으로 사용하는게 좋겠죠?

저작자표시

'IT > shell 위 댄스' 카테고리의 다른 글

쉘에서 문자열 조작하기 (0)	2017.04.19
쉘에서 문자열 치환하기 (0)	2017.04.05
쉘에서 배열 사용하기 (0)	2017.04.03
디렉토리에서 확장자가 없는 파일 찾기(find, ${#변수명}, ${변수명:n:m}) (0)	2008.10.07
배열 활용 (0)	2008.02.27

쩐의시대

나답게 살아가고 나답게 살아가자

,

쉘에서 문자열 치환하기

IT/shell 위 댄스 2017. 4. 5. 21:45

쉘에서 문자열을 치환하는 방법은 여러가지 방법이 존재합니다.
그 중에 대표적인 방법 2가지를 살펴보도록 합니다.

1. tr (translate)를 사용합니다.
문자열을 변환하거나 삭제하기 위한 간단한 변환기입니다.
먼저, 변환하는 방법에 대해서 살펴보겠습니다.

용법 : tr 'A' 'B' -> translate A to B
예제
- echo 'This is a that' | tr 'This' 'That' -> That at a that
a) "is"가 전부 "at"으로 변환됨에 주의하세요.

- echo 'THIS IS A THAT' | tr '[A-Z]' '[a-z]' -> this is a that
a) 대문자를 소문자로 변환합니다.
b) echo 'THIS IS A THAT' | tr '[:upper:]' '[:lower:]'와 동일합니다.

- echo 'THIS IS A THAT' | tr '\t' ' ' -> THIS IS A THAT
a) tab 문자를 하나의 공백으로 변환합니다.
b) echo 'THIS IS A THAT' | tr '[:blank:]' ' '와 동일하지만 [:blank:]는 tab 문자 뿐만 아니라, 공백 문자도 처리하게 됩니다.

다음은 삭제하는 방법에 대해서 살펴보겠습니다.
용법 : tr -d 'A' -> translate A to ''
예제 : echo 'THIS IS A THAT' | tr -d 'A' -> THIS IS THT

2. sed를 사용합니다.
문자열의 스트림을 변경할 때는 sed를 사용합니다.
위 예제를 sed로 변경해 보도록 하겠습니다.

예제
- echo 'This is a that' | sed 's/This/That/g' -> That is a that
a) 위 예제와 결과에 차이가 있습니다. "This"와 매칭되는 문자

- echo 'THIS IS A THAT' | sed 's/$.*$/\L\1/'-> this is a that
a) echo 'this is a that' | sed 's/$.*$/\U\1/' -> THIS IS A THAT

- echo 'THIS IS A THAT' | sed 's/\t/ /g' -> THIS IS A THAT
a) tab 문자를 하나의 공백으로 변환합니다.

- echo 'THIS IS A THAT' | sed 's/A//g' -> THIS IS THT
a) A 문자를 없앱니다

좀 더 세부적인 문자열을 다루는 것은 실전에서는 tr보다는 sed를 많이 쓰는 경향이 있습니다.

조만간 sed에 대한 정리를 한 번 하면 좋을 거 같네요^*

저작자표시

'IT > shell 위 댄스' 카테고리의 다른 글

쉘에서 문자열 조작하기 (0)	2017.04.19
쉘에서 정렬(sort)하고 유니크(uniq)한 내용 추출 (0)	2017.04.05
쉘에서 배열 사용하기 (0)	2017.04.03
디렉토리에서 확장자가 없는 파일 찾기(find, ${#변수명}, ${변수명:n:m}) (0)	2008.10.07
배열 활용 (0)	2008.02.27

쩐의시대

나답게 살아가고 나답게 살아가자

,

쉘에서 배열 사용하기

IT/shell 위 댄스 2017. 4. 3. 22:42

shell에서 Array를 어떻게 사용 할까요?
shell에서 Array를 사용 할 수 있긴 할까요?

기본 sh에서는 딱히 방법이 없습니다.
그러나, 배열처럼 사용할 수는 있지요.

#!/bin/sh

vArray="A,B"

for i in `echo ${vArray} | tr ',' '\n'` ; do

echo ${i}

done

위 결과는 다음과 같이

A

B

로 나옵니다.

"tr"은 문자열 변환, 삭제에 사용하는 명령어인데, 이 명령어를 사용하면 마치 Array에서 가져오는 것처럼 사용할 수는 있으나, direct access는 힘듭니다.

위 프로그램은 vArray 변수를 출력하면서 "," -> "\n"로 변환하여 한 라인씩 처리하기 위함입니다.

기본 shell에서는 안되지만, POSIX 계열인 bash에서는 사용 가능합니다.

#!/bin/bash

declare -a vArray

vArray=("A" "B")

vArraySize=${#vArray[@]}

vNo=0

while [ $vNo -lt $vArraySize ]

do

echo ${vArray[$vNo]}

vNo=`expr $vNo + 1`

done

unset vArray

vArray에서 ""로 값들을 나열하고 있으며, vArray의 size도 구할 수 있습니다. ${#vArray[@]}

sh에서 안 되는 direct access도 가능합니다. ${vArray[$vNo]}

Array 변수 사용은 반드시 괄호를 사용해야 합니다.

그리고, 1차원 배열은 지원합니다.

declare와 unset은 사용하지 않아도 됩니다.

이런 Array를 함수의 인자로도 전달 가능할까요?

#!/bin/bash

vArray1=("A" "B")

vArray2=("C" "D")

#-------------- [print_array function] -----------------

print_array()

{

vArray=("${!1}")

vArraySize=${#vArray[@]}

vNo=0

while [ $vNo -lt $vArraySize ]

do

echo ${vArray[$vNo]}

vNo=`expr $vNo + 1`

done

}

echo "================="

print_array vArray1[@]

print_array vArray2[@]

vArray1=(${vArray1[@]} "a")

unset vArray2[1]

echo "================="

print_array vArray1[@]

print_array vArray2[@]

위의 결과는 다음과 같습니다.

=================

A

B

C

D

=================

A

B

a

C

함수를 호출할 경우에는 함수명 뒤에 vArray[@], 함수 내에서는 ("${!1}")로 표현해야 합니다.

함수 내에서 사용하는 표현이 약간 어렵죠? 그냥 외웁시다.

참고로, 표현 내의 숫자("${!1}")는 몇 번째 인자인지 나타냅니다.

${vArray[@]}은 배열 전체를 의미합니다.

${#vArray[@]}은 배열의 크기를 의미합니다.

위 프로그램에서 배열에 값을 추가하고 삭제하는 표현도 두었습니다.

배열에 값을 추가하는 것은 vArray=(${vArray[@]} "a")

배열에 값을 삭제하는 것은 unset vArray[1]

쉘에서도 배열을 자유자재로 사용한다면 프로그래밍이 쉬워지지 않을까요?

저작자표시

'IT > shell 위 댄스' 카테고리의 다른 글

쉘에서 정렬(sort)하고 유니크(uniq)한 내용 추출 (0)	2017.04.05
쉘에서 문자열 치환하기 (0)	2017.04.05
디렉토리에서 확장자가 없는 파일 찾기(find, ${#변수명}, ${변수명:n:m}) (0)	2008.10.07
배열 활용 (0)	2008.02.27
파일 처리 (0)	2008.02.27

쩐의시대

나답게 살아가고 나답게 살아가자

,

Threading : 쓰레드를 다루는 모듈

IT/python 2017. 3. 31. 22:58

import threading

import time

class MyThread(threading.Thread):

def __init__(self, msg):

threading.Thread.__init__(self)

self.g_msg = msg

self.g_daemon = True

# End of __init__

def run(self):

while True:

time.sleep(1)

print self.g_msg

# End of MyThread

for v_msg in ['I', 'love', 'you']:

v_thread = MyThread(v_msg)

v_thread.start()

# for

for i in range(100):

time.sleep(0.1)

print i

# for

Python에서 쓰레드를 가능하게 해주는 모듈은 "threading.Thread"

MyThread class는 threading.Thread를 상속받고 MyThread(threading.Thread)
쓰레드를 클래스로 정의할 경우에는 __init__ 함수에서 부모 클래스의 생성자 threading.Thread.__init__(self)를 반드시 호출 !!
MyThread의 instance의 start 함수를 실행하면 MyThread 클래스의 run 함수가 자동 실행

클래스를 사용하지 않고 함수 내에서 thread를 사용하고 싶을 경우에는 어떻게 해야 할까요?

import threading

def MyThread():

def consumer(v_value):

print "{} => {}".format(threading.currentThread().getName(), v_value)

# End of consumer

for i in range(10):

threading.Thread(target=consumer, args=(i, )).start()

# End of MyThread

간단합니다.

함수 내의 함수 (nested function)를 정의 후 이 또한 threading.Thread로 호출해주면 됩니다.

클래스로 구현한 경우에는 클래스 내에서 __init__함수와 run 함수를 구현해줘야 하지만,

함수 내에서는 target과, args를 정의하고 start를 해주면 됩니다.

위의 경우에는 잘 다룬다면야 상관없지만, 값의 범위를 미리 알아야 하고 그 개수만큼 쓰레드를 생성해야 합니다.

다시 말해서, 2~3개의 쓰레드 개수로도 충분히 해결할 수 있는데, 쓸데없이 더 많은 쓰레드를 생성해야 하는 상황입니다.

그럼, 2~3개의 쓰레드만 생성하고 10 혹은 100개의 값을 처리하고자 할 때는 어떻게 할까요?

일반적으로, 프로그램을 설계할 때 Queue를 많이 사용합니다.

비단, Python으로만 국한되지 않고, C/C++, Java와 같이 어떤 언어에서라도 Queue를 많이 도입합니다.

import sys

import threading

import Queue

def MyThread():

v_queue = Queue.Queue()

def consumer():

while True:

try:

v_value = v_queue.get(False, 10)

print "{} => {}".format(threading.currentThread().getName(), v_value)

v_queue.task_done()

except Exception:

pass

if v_queue.empty():

break

# End of consumer

for i in range(1000):

v_queue.put(i)

for _ in range(5):

threading.Thread(target=consumer).start()

v_queue.join()

# End of MyThread

이러 방식으로 Queue를 발행 후, produce(put 함수)와 consume(get함수)을 한다면 값의 개수에 따라 쓰레드를 생성하지 않아도 시스템을 효율적으로 사용할 수도 있겠습니다.

마지막으로, 1번째 클래스를 이용한 방법과 3번째 Queue를 이용하는 방법을 믹스합니다.

위의 방법을 사용하는 건데, 프로그램을 작성하다 보면 깔끔하게 작성해야 합니다.

1번처럼 작성하다 보면 하나의 파일에 너무 많은 코드가 들어가면서 복잡해지겠죠?

최종적으로 다음과 같이 합니다.

Producer와 Consumer가 같은 Queue를 바라봐야 합니다. -> Queue는 전역처럼 관리되어야겠죠?
당연히 쓰레딩이 되도록 합니다.

import sys

import threading

import Queue

class Consumer(threading.Thread):

def __init__(self, v_queue):

# for thread

threading.Thread.__init__(self)

self.setDaemon(True)

# for queue

self.g_queue = v_queue

# End of __init__

def run(self):

while True:

try:

v_value = self.g_queue.get() # if queue is empty, queue is blocked

print "{} => {}".format(threading.currentThread().getName(), v_value)

self.g_queue.task_done()

except Exception:

pass

if self.g_queue.empty():

break

# while

# End of run

# End of Consumer

def MyThread():

v_queue = Queue.Queue()

for i in range(5):

v_consumer = Consumer(v_queue)

v_consumer.start()

for i in range(1000):

v_queue.put(i)

v_queue.join()

# End of MyThread

Queue를 전역 변수로 생성 후 사용해도 되겠지만, 실전에서는 그렇게 하면 안 되겠죠?

함수에서 Queue를 생성 후 Consumer thread에 인자로 전달했습니다.

참고로,

이번에는 MyThread 함수에서 Consumer thread가 먼저 호출되고, Producer가 작업토록 했습니다.

왜일까요?

그렇지 않고, Producer 작업 후 Consumer해도 되지만, 시스템 상으로 좋아 보이지가 않습니다.

Producing을 다 한 후 Consuming을 한다는 의미는 값들을 메모리 상에 전부 올려놓고 처리하겠다는 말과 같겠지요.

그래서, Consumer가 Queue에 값들이 들어오는지 안 오는지 모니터링하고 있다가 Producer가 값들을 넣자 말자 Consuming해서 처리한다면 시스템을 좀 더 효율적으로 사용한다고 봐야겠습니다.

Python에서 Threading 어렵지 않죠??

저작자표시

쩐의시대

나답게 살아가고 나답게 살아가자

,

YUV (YCbCr) 컬러모델

IT/멀티미디어 2009. 12. 21. 16:55

YCbCr은 컬러 정보로부터 밝기값과 색차 신호를 분리하여 표현하는 컬러모델이다.
밝기값은 Y로 기호화되고 색차신호는 CbCr로 기호화된다.

subsampling이나 양자화 과정에서 압축을 하게 되는데,
사람의 눈이 컬러 정보에 둔감하기 때문에 사람의 눈으로 화질의 차이를 별로 느끼지 않으면서 압축율을 높일 수가 있게 된다.

양자화 과정에서는 Y 값은 작은 양자화 값으로 양자화하고 CbCr 값은 큰 양자화 값으로 양자화를 하게 되면 정보 손실이 많게 된다.
그러나, 색차 신호에 대한 많은 정보 손실은 사람의 눈으로 차이를 별로 느끼지 못하기 때문에 상관은 없다.

RGB 컬러 모델은 3 개의 요소가 시각적으로 균일한 정보를 가지는 반면, YUV는 밝기값과, 색차 신호로 서로 다른 정보를 가지고 있기 때문에 JPEG 압축과 MPEG 비디오 압축에서 주로 이용하게 된다.
즉, RGB는 각각의 상호상관성이 높아서 서로 중복되는 정보를 가지고 있지만, YUV는 중복되는 정보가 없다.

아래 공식은 RGB 값과 YUV 값의 상호 변환하는 식이다.

RGB -> YUV로 변환하는 식에서, R, G, B값이 8 비트로 표현되어 [0. 255] 사이의 값을 가질 경우, Y, Cb, Cr 값도 8비트로 표현되어 [0, 255] 사이의 값을 가지도록 오프셋(+128)된 식이다.

참고로, Cb는 파란색의 색차 신호이고, Cr은 빨간색의 색차 신호이다.

참조
1. 멀티미디어 신호 처리(이론 및 실습, 조재수/강현수/김흥수/김성득 저)
2. http://fourcc.org/yuv.php

** 관련 글 **
2009/12/21 - [IT/멀티미디어] - RGB 컬러 모델

저작자표시

'IT > 멀티미디어' 카테고리의 다른 글

RGB 컬러 모델 (0)	2009.12.21

쩐의시대

나답게 살아가고 나답게 살아가자

,

RGB 컬러 모델

IT/멀티미디어 2009. 12. 21. 16:53

RGB 컬러 모델을 소개하기 전에 컬러 모델부터 알아보자.
블로그에서 다룰 모델은 RGB 컬러 모델과 YUV 컬러모델이다.

컬러모델(color model)이란 어떤 특정 상황에서 컬러의 특징을 설명하기 위한 방법이다. 그런데 하나의 컬러 모델을 사용하여 컬러의 모든 성질을 설명하기는 불가능하기 때문에 일반적으로 컬러의 특성을 표현하기 위하여 여러 종류의 컬러 모델을 정의하여 사용한다.

주요한 컬러 모델에는 다음과 같이 존재한다.

1. RGB 모델
   - 컬러 CRT 모니터와 컴퓨터 그래픽스 시스템들에서 사용
2. YUV(YCbCr) 모델
   - 비디오 영상 압축 등에서 사용
   - CCIR( International Radio Consultive Committee, 국제전기통신연합) 권고안 601-1
   - JPEG 압축과 MPEG 비디오 압축에서 사용하는 전형적인 컬러모델.
3. HSI(Hue, Saturation, Intensity) 모델
   - 색상, 채도, 명도를 각각 다루어야 하는 시스템들에서 사용

RGB 모델은 빛의 삼원색인 적색, 녹색, 청색이 기본이 되는 컬러모델이다.

빛은 여러 컬러의 빛이 더해질수록 흰색을 나타내며, 빛이 전혀 없으면 검은색을 나타낸다. RGB 모델은 이러한 빛의 성질을 이용하여 컬러를 표현하는 컬러모델이다.
RGB 모델은 기본이 되는 세 가지 색을 더하여 색을 만들어 내기 때문에 가산 모델(additive model)이라고 한다. 적색, 녹색 그리고 청색의 컬러 요소들은 상호상관성(cross correlation)이 너무 크기 때문에 몇몇 영상처리 알고리즘들은 수행이 어렵다. 히스토그램 평활화와 같은 많은 영상처리 기술들은 영상의 밝기 값만으로 영상처리한다. 이러한 처리들은 HSH 컬러 모델을 사용함으로써 구현하기가 더 쉽다.

참조 :: 멀티미디어 신호 처리(이론 및 실습, 조재수/강현수/김흥수/김성득 저)

** 관련 글 **
2009/12/21 - [IT/멀티미디어] - YUV (YCbCr) 컬러모델

저작자표시

'IT > 멀티미디어' 카테고리의 다른 글

YUV (YCbCr) 컬러모델 (0)	2009.12.21

쩐의시대

나답게 살아가고 나답게 살아가자

,

fwrite 함수로 작성했으나, linux와 windows에서 사이즈가 ...

IT/일반 2009. 7. 27. 10:46

지금껏 Unix, linux용 프로그램만 작성하다가 회사를 옮긴 후 windows 프로그램을 하고 있다.
나에게 필요한 라이브러리들을 만들어서 사용하다가 이 곳에서도 그 프로그램을 이용하게 되었는데, 문제가 발생했다.

분명 나는 80byte만 쓰라고 fwrite()로 사이즈를 지정 했음에도 불구하고, windows에서는 81byte가 들어가 있었다.
이 문제를 찾느라 하루를 허비해버렸는데...

FILE *pFP;
int i, j;

pFP = fopen("test.txt", "w");

for( i = 1, j = 0; i < 11; i++, j++) {
fwrite(&j, sizeof(int), 1, pFP); // 0~9까지의 숫자를 쓰기
fwrite(&i, sizeof(int), 1, pFP); // 1~10까지의 숫자를 쓰기
}

fclose(pFP);

8byte를 10번 루프를 돌면서 작성을 하기 때문에 당연히 결과는 80byte만 작성이 되어야 함에도 불구하고, windows에서는 81byte가 엄연히 작성되어 있다.

그 이유는...
파일 종류 중에서 일반 바이너리 모드와 텍스트 모드와의 차이점은 개행문자('\n', Line Feed, LF)의 처리 방식 때문이였다.

Unix, Linux 등에서 개행문자 '\n'은 아스키코드10(0x0A)으로서 1문자 길이가 되지만, MS-DOS나 Windows 계통의 OS, 혹은 프린터라든지 기타 통신에 사용되는 텍스트에서의 개행은 CR(Carriage Return, 0x0D, '\r', 행리턴)과 LF를 연결해서 사용하므로 2byte가 된다.

그런 이유로 위 프로그램을 수행 후 생성된 파일을 Hex Code로 마지막을 보게 되면 0x0D, 0x0A 로 어처구니 1byte가 더 사용하게 되어 있음을 보게 되었다.
웃기는 건 fwrite() 함수 자체가 바이너리로 작성하게 되어 있는데, 그렇게 안 되니 참...
windows 시스템이 웃기는건지, 아님 그런 상황을 이해 못하는 내가 웃기는건지..

어쨌든, 해결 방법은 간단하다.
fopen 시 텍스트 모드가 아니라, 바이너리 모드로 옵션을 조정해줘야 한다.

pFP = fopen("test.txt", "wb");

저작자표시

'IT > 일반' 카테고리의 다른 글

Naming Rule for C/C++ (2)	2008.02.27
struct의 size 값은?? (0)	2008.02.22

쩐의시대

나답게 살아가고 나답게 살아가자

,

Indentification of Common Molecular Subsequences (Smith-Waterman 알고리즘)

IT/검색엔진 2009. 6. 25. 21:03

Smith-Waterman local sequence alignment 알고리즘은 computational 분자 생물학 분야에서 가장 중요하게 사용되는 기법 중의 하나임은 분명하다. 이 알고리즘은 잘 보존된 부분을 찾고 그렇지 않은 부분을 제거하도록 설계되어졌다.

두 개의 sequence를 A=a₁a₂…a_n과 B=b₁b₂…b_m이라 가정하자. 유사성 S(a, b)는 sequence element a와 b 사이에 주어진다. 일반적으로 dynamic programming에서 이 값은 a와 b가 같으면 1, 다르면 0이다. 그러나 W_k는 1.0 + 1/3 * k 이다.
유사성이 높은 segment 쌍을 찾기 위해 matrix H를 셋업한다.

H의 준비된 값은 H_ij가 a_i와 b_j내의 두 segment의 최대 유사성인 해석을 가진다. 이러한 값을 최대화하는 고전적 dynamic programming으로부터 획득되어진다.

4가지 인자들 중 "0"은 새로운 alignment를 시도하는 것에 해당된다. 이 점에서 alignment 값은 증가할 수 있고 이 점에 이르는 동안 alignment 값의 합은 음수로 되어 임의로 align했을 경우 alignment 값은 도리어 낮아지는 결과가 되므로 차라리 새로운 alignment를 찾는 것이 지금까지 맞춰온 것을 확장하는 것보다 낫다는 의미가 된다. 따라서, alignment 값을 구하는 matrix의 최 상단과 좌측 열은 모두 0으로 셋팅된다.

아래 예제에서 보듯이, 최대 유사성을 가지는 segment 쌍은 matrix H의 최대 element를 갖는 점에서 시작하여 back trace를 함으로써 alignment를 찾아내는 방식이다. 따라서 최대값을 갖는 matrix의 셀을 계속 유지하고 있어야 한다. 이 최대 element에서 back trace를 하면서 0.0인 element까지 반복하면서 찾는다. 참고로, 아래의 예제에서 최대 element를 갖는 점은 (10, 8)인 element로서 3.3이라는 값을 가진다.

이 간단한 예제에서 alignment는 아래와 같이 획득했다.

mismatch와 내부적인 삭제를 포함한다. 이 알고리즘은 수학적으로 엄격한 기본으로 하는 가장 유사한 segment들의 쌍을 찾을 수 있을 뿐만 아니라, 컴퓨터 상에서 효과적이고 간단한 프로그램을 할 수 있다.
단점으로는 실제로 중요한 subsequence alignment가 있음에도 불구하고 sequence가 길다는 점만으로 이를 포함하여 불필요한 alignment가 발생한다는 것이다.
조금 더 자세히 설명하면, 유전적으로 잘 보존되지 못한 부분이 전체 alignment에 포함되어 잘 보존된 부분과 섞여 있을 때, 이것이 alignment를 왜곡시키는 결과로 나타나는 경우가 발생한다. 그 이유로 Smith-Waterman local alignment 알고리즘은 최고의 점수를 갖는 local alignment를 찾지만 초고의 유사성, 최고의 일치도를 갖는 local alignment를 찾지 못하는 문제가 알고리즘 자체에 포함되기 때문이다.

정리를 하면, sequence alignment에서 비유사도(non-similarity)가 높은 시작 부분과 끝 부분 조각을 제거하는데는 효과적이나 비유사성을 갖는 조각이 잘 보존된 alignment 사이에 위치해 있을 때는, 최고의 유사성과 일치도를 갖는 것을 찾지 못한다.

** 관련 글 **
문장 비교
Edit Distance (Edit Operations) using Dynamic Programming

http://www.bioinformatics.uwaterloo.ca/~cs882/Old_courses/W03/sw.pdf
http://naver.nanet.go.kr:8080/dl/CommonView.php?u=c7CN1fs8fKOZt5%2FZ7PKh1up8cOAz15Hbgk6iGtYZ%2FAkCXcdQoJVjN9rsPZreYnbUd0QDUcaGIGPw7Yl11smJnw%3D%3D

저작자표시

'IT > 검색엔진' 카테고리의 다른 글

문장 비교 (0)	2009.05.04
Deterministic Skip Lists (DSL) (2)	2009.05.03
Language Independent Extractive Summarization (TextRank) (1)	2009.04.24
Edit Distance (Edit Operations) using Dynamic Programming (0)	2009.04.24
2. The term vocabulary and postings lists (2.1 Document delineation and character sequence decoding) (2)	2009.02.11

쩐의시대

나답게 살아가고 나답게 살아가자

,

'IT'에 해당되는 글 67건

쉘에서 문자열 조작하기

'IT > shell 위 댄스' 카테고리의 다른 글

About ZooKeeper

'IT > 개념' 카테고리의 다른 글

쉘에서 정렬(sort)하고 유니크(uniq)한 내용 추출

'IT > shell 위 댄스' 카테고리의 다른 글

쉘에서 문자열 치환하기

'IT > shell 위 댄스' 카테고리의 다른 글

쉘에서 배열 사용하기

'IT > shell 위 댄스' 카테고리의 다른 글

Threading : 쓰레드를 다루는 모듈

YUV (YCbCr) 컬러모델

'IT > 멀티미디어' 카테고리의 다른 글

RGB 컬러 모델

'IT > 멀티미디어' 카테고리의 다른 글

fwrite 함수로 작성했으나, linux와 windows에서 사이즈가 ...

'IT > 일반' 카테고리의 다른 글

Indentification of Common Molecular Subsequences (Smith-Waterman 알고리즘)

'IT > 검색엔진' 카테고리의 다른 글

공지사항

카테고리

태그목록

최근에 받은 트랙백

글 보관함

달력

링크

쩐의시대

LATEST FROM OUR BLOG

LATEST COMMENTS

BLOG VISITORS

티스토리툴바

« 2024/04 »
일	월	화	수	목	금	토
	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	26	27
28	29	30