[태그:] Algorithm
[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;
}
쓰고나니 주저리주저리 너무 길다.
ssh 접속 시 no matching key exchange method found. 문제
OpenSSH가 7.0이상이면, 요 키 교환 알고리즘이 기본으로 켜져 있지 않아서 나는 문제인데, 다음과 같은 방법으로 해결 가능하다.
이걸 명령 줄 때마다 하긴 귀찮으니까 ~/.ssh/config 파일 안에 다음 내용을 추가하면 된다.
KexAlgorithms +diffie-hellman-group1-sha1