Entropy(Hartley, Shannon) & Pattern Matching

Progressive Alignment(점진적 정렬)

점진적 정렬

시간복잡도 = k^2 * n

 

하트리(Hartley)의 공식 :

H(X) = log₂(n)

여기서 H(X)는 확률 변수 X의 엔트로피를 나타내며, n은 가능한 결과의 수입니다. 이 공식은 각 결과의 확률이 1/n이고 동일하다는 가정 하에, 이산 확률 변수의 엔트로피를 계산하는 데 사용됩니다.

예를 들어, 동전 던지기의 경우 가능한 결과가 2개(앞면 또는 뒷면)이며, 각 결과의 확률은 동일합니다(1/2). 따라서 하트리의 공식에 따라 동전 던지기의 엔트로피는 log₂(2) = 1입니다.

예시 1: 동전 던지기 동전 던지기는 2개의 결과가 가능하며, 앞면(Head)과 뒷면(Tail)이 각각 1/2의 확률로 발생합니다.

H(X) = -(P(Head) * log₂P(Head) + P(Tail) * log₂P(Tail)) = -(1/2 * log₂(1/2) + 1/2 * log₂(1/2)) = -(-1/2 - 1/2) = 1

 

샤논 엔트로피(Shannon Entropy) :

가장 널리 사용되는 엔트로피 형태로, 이산 확률 분포를 기반으로 계산됩니다. 

H(X) = -∑(P(x) * log₂P(x))

 

여기서 H(X)는 확률변수 X의 엔트로피이고, P(x)는 확률변수 X가 x 값을 가질 확률입니다. 엔트로피는 이러한 확률값들의 가중치를 고려하여 로그 값을 더하여 계산됩니다.

예시 1: DNA with 10,000 bps [염기 쌍이 10,000개인 DNA 서열]

A,T,C,G => 0.25확률 H(X) = -0.25 * log_2(0.25) * 4 = 2 A = 0.4 ,T = 0.4 ,C = 0.1 ,G = 0.1 H(X) = -0.4 * log_2(0.4) * 2 - 0.1 * log_2(0.1) *2 = ?

1 2 3 A A A A A G A A T A T C 첫 번째 위치: A = 4/4 = 1 두 번째 위치: A = 3/4, T = 1/4 세 번째 위치: A = 1/4, G = 1/4, T = 1/4, C = 1/4 첫 번째 위치의 샤논 엔트로피: H(1) = -(P(A) * log₂P(A)) = -(1 * log₂1) = 0 두 번째 위치의 샤논 엔트로피: H(2) = -(P(A) * log₂P(A) + P(T) * log₂P(T)) = -(3/4 * log₂(3/4) + 1/4 * log₂(1/4)) ≈ 0.244 세 번째 위치의 샤논 엔트로피: H(3) = -(P(A) * log₂P(A) + P(G) * log₂P(G) + P(T) * log₂P(T) + P(C) * log₂P(C)) = -(1/4 * log₂(1/4) + 1/4 * log₂(1/4) + 1/4 * log₂(1/4) + 1/4 * log₂(1/4)) = 0.602

문자열 관련 용어 재정리:

접두사(Prefix):  문자열 S[1 .. n]의 S[1 .. j]는 접두사입니다. 여기서 j ≤ n입니다. 문자열 X가 문자열 Y의 접두사이면, 어떤 문자열 Z에 대해 X∙Z = Y가 됩니다. 예: 'app'은 'apple'의 접두사입니다.

접미사(Suffix):  문자열 S[1 .. n]의 S[i .. n]은 접미사입니다. 여기서 1 ≤ i입니다. 문자열 X가 문자열 Y의 접미사이면, 어떤 문자열 Z에 대해 Z∙X = Y가 됩니다. 예: 'ple'은 'apple'의 접미사입니다.

부분 문자열(Substring):  문자열 S에서 연속된 문자들로 이루어진 문자열입니다. S[i .. j]는 문자열 S[1 .. n]의 부분 문자열이며, 1 ≤ i 및 j ≤ n입니다. S의 부분 문자열은 S의 접미사의 접두사입니다. 예: 'app', 'ppl', 'appl' 등은 'apple'의 부분 문자열입니다.

빈 문자열(Empty String):  i > j인 경우, S[i .. j]는 빈 문자열입니다. 빈 문자열은 길이가 0인 문자열을 의미하며, 모든 문자열의 접두사이자 접미사로 간주됩니다. 예: ''(따옴표 사이에 아무 것도 없음)은 빈 문자열입니다.

 

Proper Prefix, Proper Suffix, Proper Substring: 자기 자신을 제외한 나머지

Proper Prefix (적절한 접두사):  문자열 S의 접두사 중에서 문자열 S 자체와 빈 문자열을 제외한 접두사입니다. 예: 'apple'의 적절한 접두사는 'a', 'ap', 'app', 'appl'입니다.

Proper Suffix (적절한 접미사):  문자열 S의 접미사 중에서 문자열 S 자체와 빈 문자열을 제외한 접미사입니다. 예: 'apple'의 적절한 접미사는 'e', 'le', 'ple', 'pple'입니다.

Proper Substring (적절한 부분 문자열):  문자열 S의 부분 문자열 중에서 문자열 S 자체와 빈 문자열을 제외한 부분 문자열입니다. 예: 'apple'의 적절한 부분 문자열은 'a', 'p', 'p', 'l', 'e', 'ap', 'pp', 'pl', 'le', 'app', 'ppl', 'ple', 'appl', 'pple'입니다.

 

Terminology & Properties

Reflexivity (반사성): 앞서 설명했듯이, 적절한 접두사, 적절한 접미사, 적절한 부분 문자열은 반사적 성질을 갖지 않습니다. 그러나 일반 접두사, 접미사, 부분 문자열의 경우에는 문자열이 자기 자신과 관계를 갖기 때문에 반사적입니다.

Anti-symmetry (반대칭성): 적절한 접두사, 적절한 접미사, 적절한 부분 문자열은 반대칭적이지 않습니다. 이들 관계에서 문자열 X와 Y가 동시에 서로의 적절한 접두사, 접미사, 부분 문자열이 되는 것은 불가능합니다.

Transitivity (전이성): 전이성은 다음과 같은 관계를 말합니다. X가 Y와 관계 R을 갖고, Y가 Z와 관계 R을 갖는다면, X는 Z와도 관계 R을 갖습니다. 일반 접두사와 접미사에 대한 전이성은 성립하지 않습니다. 그러나 부분 문자열에 대해서는 전이성이 성립합니다.

X가 Y의 접미사이면, 어떤 문자열 Z에 대해 X∙Z는 Y∙Z의 접미사입니다.  즉, 문자열 Y의 접미사에 동일한 문자열 Z를 추가하면, 결과 문자열에서도 X가 접미사로 유지됩니다. 예: 'ple'은 'apple'의 접미사이고, 'Z'를 'day'라고 하면, 'ple'∙'day' = 'pleday'는 'apple'∙'day' = 'appleday'의 접미사입니다. X가 Z의 접미사이고, Y가 Z의 접미사이며, |X|≤|Y|인 경우, X는 Y의 접미사입니다.  즉, 동일한 문자열 Z의 두 접미사 X와 Y에서 X의 길이가 Y보다 작거나 같다면, X는 Y의 접미사입니다. 예: 'ple'은 'apple'의 접미사이고, 'pple'도 'apple'의 접미사입니다. |'ple'| ≤ |'pple'|이므로, 'ple'은 'pple'의 접미사입니다.