[cpp] SCS(Shortest Common SuperString) 찾기 알고리즘

구현 환경

플랫폼 : WIN32
사용언어 : ANSI C/C++
외부 라이브러리 : NONE
사용 컴파일러 : Visual Studio .Net 2003 C/C++ Compiler

Basic Idea

Shortest Common Superstring은 입력으로 들어온 문자열을 모두 substring으로 가지는 가장 짧은 문자열을 구하는 것입니다. 대부분의 NP 문제들이 그러하듯 이 문제 또한 푸는 방식이나 검증하는 방식에 특별한 아이디어가 없습니다. 문제를 들으면 누구나 알 수 있듯이 문자열 간의 overlap 부분이 가장 큰 순서대로 배열하는 것이 이 문제를 푸는 핵심입니다.

Reduce to TSP (Traveling salesperson problem)

위에서 언급한 것에 근거해 보면 이 문제는 아주 손쉽게 TSP로 reduce 되는 것을 알 수 있습니다. TSP는 방향 그래프 G = (V, E)와 각각의 edge에 적용되는 가중치 w가 주어졌을 때, 가장 작은 가중치만 사용해서 모든 vertex를 순회하는 문제입니다.

여기서 G = (V, E)의 V에는 입력으로 들어온 임의의 한 문자열 s를, E는 해당 문자열 사이의 overlap 관계를, 그리고 가중치 w는 overlap 되는 문자열의 개수를 적용하면 됩니다. 이렇게 한 후 가중치 w가 가장 높은 여행 경로를 찾을 수 있고, 해당 여행 경로대로 문자를 중첩시켜 나열하면 superstring이 완성됩니다.

Suffix Trie

2장에서 언급한 것과 같이 TSP로 reduce해서 문제를 풀더라도 해결해야 하는 것이 두 문자열의 가장 긴 overlap 영역을 구하는 것 입니다. 이것을 brute-force 방식으로 구할 경우, TSP의 branch-bound에 소요되는 시간보다 문자열의 overlap 영역을 구하는데 더 많은 시간을 소요하게 됩니다. 이러한 문제를 해결하기 위해서 사용된 자료구조가 suffix trie입니다.

suffix tree내지는 compressed suffix tree를 사용하지 않은 이유는 해당 자료 구조의 경우 생각보다 construction 과정이 복잡하고, construction 후에 overlap 영역을 찾는 과정도 suffix trie보다 효율적이지 않았습니다. 해결해야 하는 overlap 영역을 찾는 과정에서는 suffix trie가 가장 효율적이었습니다. 단지 전자의 것에 비해서 공간을 많이 차지한다는 단점이 있었으나 문제에서 제시된 상한 값(200 x 100 문자)로 테스트 해 본 결과 수용 가능한 정도의 공간 이라고 판단되었습니다.

suffix trie 구현에 있어서의 핵심은 해당 트리를 construction 하는 과정입니다. 이 과정은 수업 시간에 소개된 직관적인 방법을 그대로 사용했습니다. 이 방법은 두 가지 단계로 이루어 집니다. 터미널 노드에 새로운 글자 노드를 추가하는 단계와 해당 글자를 suffix trie에 추가하는 과정입니다. 이 과정을 통해서 abab가 construction되는 과정을 보면 다음과 같습니다.


단계	터미널 노드에 추가(a)	suffix trie에 추가(b)
1: a		+- a
2: b	+- a - b	+- a – b
+- b
3: a	+-a-b-a
+-b-a	+a+-b-a
+ 0
+-b-a
4: b	+a+-b-a-b
+ b
+-b-a-b	+a+-b-a-b
+ b
+-b+-a-b
+ 0

위 표에서 1-a에 아무것도 없는 것은 시작 시에는 터미널 노드가 존재하지 않기 때문에 아무런 작업도 이루어지지 않은 것 입니다. 3-b 과정에서는 a 노드가 이미 존재하기 때문에 루트에 새로운 노드를 추가하지 않고 a노드 자식으로 0노드를 추가해서 a가 해당 문자열의 suffix로 존재함을 알립니다.

위 표에서 suffix trie를 만드는 과정이 잘못되는 부분이 4-a 부분입니다. 해당 부분에서는 터미널 노드에 b를 추가하는 과정을 나타내고 있습니다. 그런데 0으로 표시된 노드의 경우 글자가 없는 상태이기 때문에 단순히 위와 같이 그냥 b로 치환해 버릴 경우 위와 같은 문제가 생기게 됩니다. 4-a 부분이 정확하게 되기 위해서는 0을 b로 치환하는 것이 아닌 0노드를 a-b의 b노드의 자식으로 이동하는 작업입니다.

위에서 제시된 사항만 정확하게 따를 경우 손쉽게 suffix trie를 구성할 수 있습니다. 하지만 실제로 suffix trie를 구성해 보면 생각보다 많은 시간이 소요되는 것을 알 수 있습니다. 이 부분을 profiling 해 본 결과 a과정에서 병목 현상이 발생한다는 것을 알 수 있었습니다. a과정에서 터미널 노드를 찾기 위한 복잡한 재귀 호출 함수 속에서 대부분의 시간이 소요되었습니다. 이 과정을 줄이기 위해서 제출된 프로그램에서는 터미널 노드만을 별도의 리스트로 만들어서 관리하도록 하였습니다. suffix trie의 construction 과정에서 터미널 노드의 경우 삭제, 검색되지 않고 단순히 추가되기만 하는 형태를 지니므로 단일 링크드 리스트 구조를 통해서 터미널 노드를 연결시켜 두고, a과정에서는 해당 터미널 노드 리스트를 순회하면서 작업하도록 구현하였습니다. 실제로 이 과정을 통해서 100개 정도의 문자에 소요되던 클럭이 2000정도에서 10정도로 감소하였습니다.

Suffix Tree Construction 소스 코드

void CSuffixTree::\_AddChar(char ch)  
{  
    PTERMNODE t;  
    CNode   \*node, \*parent, \*prev, \*ln;  
    bool    find;  
  
    for(t=term\_; t!=NULL; t=t->next)  
    {  
        // 노드가 0인 경우  
        if(t->node->val() == 0)  
        {  
            find = false;  
  
            // 노드의 이전 노드를 검색  
            parent = t->node->parent();  
            if(parent->child() == t->node)  
                prev = NULL;  
            else  
            {  
                for(prev=parent->child();   
                    prev->next() != t->node;   
                    prev=prev->next())  
                    ;  
            }  
  
            // 노드의 형제들을 검색해서 추가하려는 문자와  
            // 동일한 형제가 있는지 검사  
            for(ln=parent->child(); ln!=NULL; ln=ln->next())  
            {  
                // 형제가 있는 경우 해당 노드의 자식으로 이동  
                if(ln->val() == ch)  
                {  
                    if(prev)  
                        prev->next(t->node->next());  
                    else  
                        parent->child(t->node->next());  
  
                    t->node->parent(ln);  
                    t->node->next(ln->child());               
                    ln->child(t->node);  
  
                    find = true;  
                    break;  
                }  
            }  
  
            // 형제 노드에 삽입하려는 값이 없는 경우  
            // 해당 노드의 값을 삽입하려는 값으로 치환  
            if(!find)  
                t->node->val(ch);  
        }  
        else  
        {  
            // 일반 터미널 노드인 경우 자식으로 추가  
            node = t->node->AddChild(ch);  
            t->node = node;  
        }  
    }  
}  
  
void CSuffixTree::\_AddNode(CNode \*n, char ch)  
{  
    CNode \*t, \*node;  
  
    for(t=n->child(); t!=NULL; t=t->next())  
    {  
        // 노드의 자식중에 추가하려는 값을 가진  
        // 노드가 있으면 해당 노드의 자식으로 0노드 추가  
        if(t->val() == ch)  
        {  
            node = t->AddChild(0);  
            \_AddTerm(node);  
            return;  
        }  
    }  
  
    // 일반적인 경우 자식으로 ch를 가진 노드 추가  
    node = n->AddChild(ch);  
    \_AddTerm(node);  
}  
  
void CSuffixTree::Construct(const char \*str)  
{  
    Clear();  
  
    for(int i=0; str[i] != '\0'; ++i)  
    {  
        \_AddChar(str[i]);  
        \_AddNode(&root, str[i]);  
    }  
}

Branch and Bound with TSP

TSP를 해결하기 위해서 branch and bound를 하는 방법은 간단합니다. Bound는 그래프의 각 edge에 할당된 가중치의 최적 값으로 결정합니다. 이 과정에 사용된 함수의 소스 코드는 아래와 같습니다.

_GetBound 소스 코드

int \_GetBound(PNODE n)  
{  
    int maxov;  
    int bound;  
    bound = \_GetLength(n->path); // ... \*  
  
    for(int i=0; i<nv\_; ++i)  
    {  
        if(!n->path.IsVisited(i))  
        {  
            maxov = 0;  
  
            for(int j=0; j<nv\_; ++j)  
            {  
                if(i == j)  
                    continue;  
  
                if(!n->path.IsVisited(j))  
                {  
                    if(weight\_[i\*nv\_+j] > maxov)  
                    {  
                        maxov = weight\_[i\*nv\_+j];  
                    }  
                }  
            }  
  
            bound += maxov; // ... \*  
        }  
    }  
  
    return bound;  
}

위 코드에서 중요한 핵심 부분은 *로 표시된 부분입니다. 처음 부분은 지금까지 방문한 노드에 대한 가중치가 되고, 그 다음 for를 돌면서 계산하는 부분은 앞으로 방문 가능한 노드에서 가장 최적값이 나올 수 있는 경우입니다. 즉, 이 노드를 탐색할 경우 최대한 이 정도의 bound를 가진다는 것을 의미합니다.

실행 화면

컴파일 타임이 안습이군요. 크리스마스에 이런거 하고 있었다니 ㅋㅋㅋ
2005년 크리스마스는 정말 악몽이었습니다. 컴파일러까지 ... ㅠㅠ

sftrie_src.zip sftrie_req.zip sftrie_exe.zip