본 문서는 Bogdan Dorohonceanu씨와 Craig Nevill-Manning 교수님에 의해 2000년 7월 1일에 의해 쓰인 내용을 편역하였다.
http://www.drdobbs.com/database/a-practical-suffix-tree-implementation/184404184?pgno=1
접미사 트리는 문자열 검색에 사용된다. 우리 저자들은 이론적으로 언급된 시간 복잡도를 유지하면서 최소한의 자원을 가지고 어떻게 일반화된 접미사 트리 자료 구조를 생성하는지 설명한다.
보그단씨는 대학원 조교이고, 크레이그씨는 Rutgers 대학교의 컴퓨터 과학과 교수님이시다. 그들은 각각 dbogdan@caip.rutgers.edu and nevill@cs.rutgers.edu 로 연락할 수 있다.
접미사 트리는 생물정보학에서 문자 검색을 위해서 사용된다 - DNA 시퀀싱, 단백질 서열 패턴 발견, 그런 종류의 데이터들. 이 분야에서, 패턴은 점수를 가진 문자열이다. 점수는 문자열에 있는 각 문자별로 고정된 값의 합이다. 그리고 각 점수는 문자열 내의 문자 위치에 따라 가중치가 적용되어 계산된다. 검색은 거의 대부분 매우 많은 양의 서열들에 대해 수행되기 때문에, 그들은 엄청난 양의 하드웨어 자원을 요구한다.
접미사 트리는 DDJ에 새롭지 않다. 마크 넬슨(Mark Nelson) 씨는 그의 글 "접미사 트리"(DDJ, 1996년 8월)에서 그들을 조사했다. 이 글에서, 우리는 마크씨의 설명들 기반으로 하되, 실제적인 문제를 설명한다: 어떻게 이론적으로 언급된 시간 복잡도를 유지하면서 최소한의 자원을 가지고 어떻게 일반화된 접미사 트리 자료 구조를 생성하는지에 대해서 설명한다. 우리는 또한 접미사 트리 구현(자바로 쓰임)을 제공할 것이고, 당신이 사용할 수 있는 테스트 데이터를 제공할 것이다. 완전한 소스 코드는 전자적으로 이용 가능하다. ("자원 센터" 페이지 5 를 보기 바란다.)
SuffixTree-Dr.Dobb.zip단백질 서열에서 검색하는 것은 DNA 서열에서 검색하는 것보다 더 복잡하다. 왜냐하면, 알파벳이 더 많고(4개 문자 대신에 24개 문자), 서열이 상대적으로 길기 때문이다(내 경험 상은 다른 느낌인데, DNA가 문자 수가 더 적어서 더 분명하게 서열이 나눠지지 않아 더 복잡하다.). 같은 문제가 문자열을 검색할 때도 나타난다. 한 개의 단백질에 대해서, 문자열의 한 문자들은 아미노산과 특수 기호로 이뤄져 있다. 문자열 안의 문장에 대해서, 서열은 그 문장 안의 단어 배열일 것이다. 이처럼, 한 문자열은 단어의 다수 서열로 볼 수 있다.
수많은 서열을 다룰 때, 패턴을 발견하기 위해서 한 서열당 요구되는 시간은 개선될 수 있다(예를 들어, 단백질 발견에 대해서 40 퍼센트 이상의 개선). 만약, 우리가 특수 기호로 나눠지고 연결된 다수의 서열로부터 생성된 일반화된 접미사 트리를 사용한다면 말이다.(가령, DNA 서열의 경우 ATCG*ATCG*ATTCA...) 운나쁘게도, 다중 서열들은 대부분 매우 길고, 알파벳 수가 많고, 서열의 갯수가 큰 상황에서는 이론대로 구현한 접미사 트리의 경우 너무 많은 시간과 공간을 요구한다.
전통적인 접미사 트리 구현은 원래의 서열이 매우 길 때, 트리를 선형 시간에 생성하기 위해 요구되는 정보 때문에 커다란 저장 공간을 요구한다. 만약, 주요 구현이 객체 지향적이면, 우리는 운치 않는 메모리 조각 효과를 경험하게 된다. 왜냐하면, 각 에지, 노드, 또는 접두사는 하나의 객체를 표현하고, 프로그램은 그것의 실행 시간 대부분은 메뢰 관리에 허비하기 때문이다. 이런 동작은 더 많은 공간 뿐만 아니라(객체를 다루기 위해 요구되는 정보가 요구되고, 그것은 어디엔가 저장되어야 한다) 더 많은 시간을 요구한다. 시간은 메모리 관리 덕에 더 이상 선형적이지 않게 된다.
이 문제에 관련된 것은 너무 많은 객체들과 너무 많은 선행 계산된 정보들이다. 전자는 전통적인 프로그래밍 문제이며 접미사 트리와는 관련이 없다; 해결책은 기본(primitive) 데이터 구조를 이용하는 것이다. 우리는 노드를 객체로 표현하는 것 대신 정수의 긴 배열(int array) 형태로 동일한 트리를 얻을 수 있다.
우리가 트리에 노드를 삽입할 때 우리는 무엇을 하는가? 우리는 어떻게 배열 상에서 에지, 노드, 그리고 접미사, 혹은 쪼개진 에지들을 옮기는가? 우리는 그것의 특별한 자료 구조에 대해서 모르는 것처럼 여기고 구현함으로써 이런 문제들을 피할 수 있다. 즉, 전통적인 다중 노드 트리로 여기는 것이다. 그런까닭에, 정보는 에지에 저장되지 않는다.
모든 정보가 노드들로 이동되더라도, 우리는 여전히 노드 크기 문제를 가지고 있다. 자식 노드가 삽입될 때마다, 그 부모 노드의 크기는 자식으로의 연결로 인해 추가된 공간만큼 증가한다. 부모 노드는 배열 안의 셀의 서열처럼 저장되고, 다른 노드들은 아마 그 뒤에 저장될 것이다. 부모의 크기를 키우는 것은 부모 노드를 뒤따르는 모든 노드들의 셀들을 한칸씩 옮기는 것을 의미한다. 이것은 긴 배열 안에 있는 노드들을 다루는 것을 시간이 오래 걸리는 작업으로 만든다.
운좋게도, 우리는 노드들이 얼마나 많은 자식들을 가졌는지에 상관없이 모든 노드가 같은 크기를 가진 트리로 만들 수 있다. 다른 노드들로의 연결 갯수를 가변하는 대신에(다른 유요한 정보는 제쳐두고라도), 각 노드는 오직 두 연결들만 가질 수 있다. 바로 첫 자식 노드와 왼쪽 자매 노드이다.
그림 1 ANANAS 서열에 대한 접미사 트라이
그림 1은 ANANAS 서열에 대한 접미사 트라이이다 (서열 ANANAS에서 접미사를 그들의 색인 순서에 삽입함으로써 생성된다: 색인 순서 ANANAS, NANAS, ANAS, NAS, AS, 그리고 S)
그림 2 ANANAS 서열에 대한 접미사 트리
그림 2는 동일한 서열에 대한 접미사 트리로 변형된 접미사 트리이다. 전통적인 트리에서 접미사들에 대한 데이터를 유지하는 객체들과 우리의 트리에서 리프 노드들은 보이지 않았다.
공간 문제에 대한 해결책이 있다: 메모리 사용량을 줄이고 메모리 조각 효과를 피하기 위해서는 데이터가 기본(primitive) 타입(객체가 없다)으로 표현되어야 하고, 그들이 가진 자식 노드의 갯수에 상관 없이 모든 노드들은 같은 크기를 가져야 한다.
각 노드는 세 가지 필드들을 가진다:
- 색인번호 = index(노드), 다중 서열에서 부분 문자열의 시작 색인 번호
- 자식 = child(노드), 노드 배열의 첫 자식의 색인 번호, 양수로 저장되거나, 접미사 값이 하나의 null 혹은 음수로 저장됨
- 자매 = sibling(노드), 노드 배열에서 오른쪽 자매 노드의 색인 번호
에지에는 아무런 정보도 저장되지 않는다. 이 기술은 각 노드가 다중 서열들에서 유효한(valid) 접미사의 부분 문자열을 표현하도록 해준다. 이 때, 유효한 접미사라는 말은 이 접미사가 index(노드)의 색인 번호에서 시작해서 index(child(노드)) 바로 직전에 끝난다는 것을 뜻한다. 우리는 그 부분 문자열의 길이를 "노드 길이"라고 부르며, 그것은 length(노드) = index(child(노드)) - index (노드)의 값을 가진다. 동일한 기술은, 트리를 생성하는 와중에 노드 생성(노드 배열 끝에 추가)하고 노드 필드 값을 갱신하지만, 노드를 삭제 하지 않음을 보장한다. 그런 까닭에, 노드 필드는 배열을 압축적으로 표현한다.
트리를 생성할 때 트리의 중간에 접미사를 추가하는 경우는 어떠한가? 우리는 한 퀵 정렬 알고리즘을 사용해서 역으로 정렬된 접미사의 배열을 포함하는 접미사 배열을 먼저 생성함로써 그런 문제를 회피한다. 퀵 정렬은 그 자리에서 정렬을 하고, 메모리 관리에는 오버헤드가 없다. 그렇기 때문에, 접미사 배열을 생성하는 것은 O[NXlog(N)](여기에서 N은 입력 서열의 문자 갯수 이다.)에 두 접미사 간의 평균 공통 접미사에 의해 주어진 상수가 곱해진 시간이 걸린다. 실제로 필요한 시간은 log(N) 함수의 느린 증가 커브로 인해 실제적으로는 거의 선형에 가깝게 걸린다. 접미사 배열 (역의 사전 순서)는 ANANAS (접미사 ANANAS, NANAS, ANAS, NAS, AS, 그리고 S)는 그림 3에 보인다.
그림 3 ANANAS 접미사 배열
우리는 다음으로 접미사 배열에 의해 주어진 순서에 따라 접미사들을 삽입함으로써 접미사 트리를 생성한다. 그리고 동시에 우리는 정확한 순서의 접미사를 가진 트리를 가지게 된다. 끝으로, 우리는 접미사 트리를 생성하면서 사용했던 메모리를 해제하게 된다.
우리가 사전 역순으로 정렬된 접미사들을 삽입함으로써 트리를 생성했기 때문에, 노드 삽입은 항상 루트 노드의 자식(즉, 한 리프 노드를 가진 노드) 혹은 이전 삽입 동안에 방문한 경로에 있는 리프 노드 둘 중 한 가지에서만 일어난다. 우리는 그 경로를 "삽입 경로"라고 부르며, 그 경로는 언제나 루트 노드에서 시작해서 마지막 노드(리프 노드)를 제외하고 각 노드의 child(노드)를 따라간다. 현재의 삽입 경로에서, 루트 노드에서 삽입 지점까지의 모든 노드들은 그들의 색인 필드를 갱신하게되고, 그들은 동일한 유효 접미사를 가리키게 된다(그것은 바로 삽입된 접미사를 나타냄).
이 기술은 첫 자식 노드들로의 연결들에 의해 생성된 경로 상에 새로운 접미사를 언제나 삽입하게 해주고, 필요하다면 그 경로로 부터 노드를 쪼갤 수 있도록 해준다. 그런 까닭에, 우리는 결코 자매 노드들 사이의 (수평의) 연결들로 순회하지 않으며, 노드 삽입 간에 메모리 접근 횟수는 최소화된다. 우리는 오직 새로운 노드들을 생성한다. 전통적인 접미사 트리에서 에지를 쪼개는 것은 우리의트리에서 한 노드를 쪼개는 것과 동일하다. 이것은 다시 말해, 새로운 한 개 또는 두 개의 노드를 생성하고, 쪼개진 노드의 첫 자식 노드로의 연결을 갱신하는 것을 의미한다.
모든 접미사들을 삽입하는데 요구되는 시간은 
이차항 시간 복잡도는 문제인 것처럼 보인다. 왜냐하면, 이론적인 알고리즘 중 선형 시간에 접미사 트리를 생성할 수 있는 알고리즘이 있기 때문이다. 운좋게도, 실제 상황에서 요구되는 시간은 O[N] 선형 시간 복잡도를 가지는데, 이것은 왜냐하면 확률적으로 평균 공통 접미사 값이 매우 적고, N에 관련이 있는 것이 아니라 서열의 문자의 출현 빈도에 더욱 관련이 있기 때문이다. 더구나, 만약 우리가 다중 서열에서 서열들을 모두 연결하게 되면, N의 길이의 평균 공통 접미사 변이는 급격하게 적어진다. 예를 들어, SwissProt 데이터베이스로부터의 단백질 서열(http://www.expasy.ch/sprot/sprot-top.html)에 대해서 평균 공통 접두사는 우리가 서열의 갯수를 1000개(0.4M 입력 문자들)에서 59,000(21M 입력 문자들)로 증가시켰을 때, 24에서 18로 감소한다. 그런 까닭에, 실제 응용 프로그램에서, 그것의 값은 상대적으로 작은 상수로 여겨질 수 있다. 이전에 언급했듯이, 우리는 실제 문제를 다루고 있고(매우 많은 수의 서열들), 이런 관점이 여기에서는 도움이 된다. 다음 코드는 한 노드를 삽입하는 수도 코드를 보인다.
만약 삽입된 접미사가 접미사 배열의 첫 접미사 이면,
루트 노드를 생성하고, 한 리프 노드를 가진 자식 노드를 추가한다.
아니면,
(l = 접미사 배열의 이전 접미사와 현재 접미사 사이의 최장 공통 접두사)를 계산한다.
만약 l = 0이면,
한 리프 노드를 가진 자식 노드를 루트 노드에 추가한다.
아니면,
(s = 삽입된 접미사의 시작 색인 번호)로 둔다. 삽입 경로에 있는 각 노드 n을 따라서 index(n)
을 s로 갱신해서 그것으 현재 삽입된 접미사를 가리키게 하고 (l == 0) 또는 (l < length(node))
가 될 때까지 s와 l의 값을 length(n)의 값으로 감소시킨다. 다음으로 만약 (l == 0) 이면,
노드 n에 리프 노드를 추가하고 아니면, 노드 n을 쪼갠다 (쪼갠 후에, 갱신된 노드 n은 두 자식
노드를 가지게 될 것이다:
1) child(n)노드는 리프 노드이거나 한 리프 노드를 가진 노드이고, 새롭게 삽입된 경로를 연결
해 나간다.
2) sibling(child(n))노드인데, child(n)은 쪼개진 노드의 모든 자식 노드를 가진 노드이다.
그림 4는 ANANAS에 대한 접미사 트리를 생성하는 단계를 설명한다(사전 역순으로 접미사 배열로부터 접미사들을 삽입하는 단계로 만든다: S, NAS, NANAS, AS, ANAS, 그리고 ANANAS). 트리 구조는 패턴 검색에 좋으며 이는 한 패턴이 검색될 때 모든 트리 구조가 순회되어야 하기 때문이다. 다음에 보이듯이 트리를 순회하는 것은 직관적이다.
그림 4 ANANAS에 대한 접미사 트리를 생성하는 단계
Call: visit(child(root));
void visit (int node) {
if(child(node > 0)) {
// 내부 노드, 내부 노드를 여기에서 처리한다.
for (int child = child(node);
child > 0; child = sibling(child)) {
visit(child);
}
}
else {
// 리프 노드, 리프 노드를 여기에서 처리한다.
}
}
접미사 트리 역시 접미사의 시작 색인 번호에 대한 정보를 저장해야 한다. 그런 정보를 더 빨리 접근하기 위해서 리프 노드에 그런 정보를 보관했다고 가정해 보자. 첫 자식 노드의 한 색인 번호로 써, 한 리프 노드는 음수를 가지고 있으며, 이것은 노드의 색인을 의미하는 것이 아니라 눠래 서열에서 접미사를 나타내는 것이다. 음수 기호는 내부 노드들과 리프 노드들을 구분짓는다. 그런 까닭에, 노드의 종류를 나타내기 위해서 아무런 부가 정보가 필요하지 않다. 즉, 내부 노드인지 리프 노드인지 나타내는 정보가 필요하지 않다.
N개 문자 서열로부터 생성된 접미사 트리는 최대 2N개 노드들 가진다. 왜냐하면, 서열에는 N개의 접미사들이 있고, 우리는 트리와 리프 노드들에 접미사에 대한 정보를 보관하기로 결정했기 때문에 최종 트리는 아마 최대 3N 개의 노드들을 가지게 될 것이다. 이것은 이론과 다른 점이 아니다. 왜냐하면, 우리의 트리 (최대 2N의 크기)의 내부 노드들은 실제 접미사 트리를 표현하기 때문이다. 우리는 오직 접근하기 쉬운 방법으로 데이터를 정렬했기 때문이다. 세 노드 필들들은 세 정수 배열들에 있는 연속적인 셀들로 표현되고, 전체 트리는 최대 9N의 정수의 저장소를 필요로 한다(그리고 추가적인 정보는 없다). 그런 까닭에, 공간 요구도는 O[N]이다.
이것은 마크 넬슨씨에 의해 설명된 구현에 비교해서 메모리 사용량을 증가 시키지 않는다. 그의 구현은 각 리프 노드들로 부터 가리켜진 접미사들에 대한 정보를 가진 객체를 가지고 있고, 그런 까닭에 에지와 자식 노드에 대한 정보를 가진 최대 2N 개의 노드들(각각 한 정수 값 마다), 정보를 가진 최대 2N 개의 에지들(각각 4개의 정수 값 마다), 그리고 접미사에 대한 정보를 가진 N 개의 소위 말하는 "접미사 객체들"(각각의 3개의 정수 값 마다)를 가지고 있다. 전체적으로 보면, 그것은 대략 (2N×1+2N×4+N×3)=13N 개의 정수로 표현되는 최대 5N개의 객체들을 사용하고, 트리를 관리하기 위해 필요한 다른 데이터 구조도 있다(에지에 대한 2N 크기의 해시 테이블과 노드들에 대한 연결을 가진 2N 개의 고정된 배열).
비교를 위해서, 우리는 N=21M 문자열들(혹은 접미사들)을 가진 서열을 선택하고, 51M 개의 노드들을 가진 접미사 트리를 생성했다. 우리의 트리는 생성하는데 5분이 걸렸으며, 580MB 의 용량을 소모했다. 마크 씨의 구현은 훨씬 더 긴 시간을 요구했고, 에지를 위한 해시테이블과, 객체 관리에 이용되는 오버헤드 메모리를 제외하고 에지, 노드, 그리고 접미사에 850 MB를 이용했다(전체 적으로, 그것은 1GB 이상의 메모리를 소모한다.)
언제나 구현을 이론과 실제, 선형-시간과 선형-공간 요구 사항, 그리고 우리가 접미사 트리를 사용하려고 하는 응용의 종류 사이에서 조율할 때 들어가는 기회 비용이 있다.
우리가 단일의 긴 서열에서 접미사 트리와 관련된 주요 문제를 해결한 후에, 우리는 계속적으로 일반화된 접미사 트리에 대해 고려했다; 그것은, 접미사 트리가 서열의 배열(다중 서열)들로부터 생성되는 것이다. 이론적으로, 다중 서열은 서열을 연결하고 그들을 유일한 식별자로 쪼갬으로써 생성할 수 있다.
만약 우리가 M 개의 서열들로 시작한다면, 우리는 서열 안에 포함되지 않은 알파벳들에 속하지 않은 M 개의 유일한 식별자들이 필요하게 된다. 만약 M이 크게 된다면, 각 식별자는 여러 바이트로 표현되어야 한다 (즉 한 개 이상의 문자열), 그리고 그들을 저장하고 관리하는 것은 상당량의 시간 오버헤드를 생성한다. 또한, 식별자를 가진 다중 서열의 접미사는 완전히 유용하지 않다. 왜냐하면, 그것의 유용한 점은 그것의 시작 부분 부터 첫 식별자가 나타나기 전까지 이기 때문이다.
두 서열을 생각해 보자 - BMBK와 BK이다. 그들로 부터 생성된 서열은 BMBK<*1>BK<*2>이고, <*1>과 <*2>는 이 예제의 유일한 식별자이다. 다중 서열 MBK<*1> BK<*2>로부터, 부분 문자열 MBK만이 유용하다(유효하다). 왜냐하면, 그것은 다중 서열의 원래 서열 (BMBK)의 한 접미사 이기 때문이다.
그런 까닭에, 우리는 유효한 접미사, 유효한 접미사 배열, 그리고 유효한 접미사 트리를 정의한다. 한 유효한 접미사는 다중 서열 안에 포함된 서열 안의 한 접미사를 표현하는 그 다중 서열의 부분 문자열이다. 유효한 접미사의 시작 식별 번호들은 접미사 트리 안에서 리프 노드들로 저장되어야 한다. 왜냐하면, 같은 접미사가 한 다중 서열 안에서 여러번 나타날 수 있기 때문이다.
유효한 접미사 배열은 다중 서열의 유효한 접미사들로부터 생성된 접미사 배열이다. 유효한 접미사 트리는 유효한 접미사 배열로 부터 생성된 접미사 트리이다.
이 접근법은 몇몇 장점이 있다. 다중 서열 안의 식별자는 같은 값을 가질 수 있다. 패턴 검색을 위해 순회하는 동안에 서열 식별자들에 대해서 아무런 테스트도 필요하지 않다(이것은 전통적인 접미사 트리 구현과 다른 점이다). 트리 안의 경로는 유효한 접미사를 표현하고, 유효한 접미사에 대한 필요한 모든 정보를 가지고 있고, 다중 접미사에 대한 정보들을 가지고 있는 것이 아니다. 우리의 트리 안에 있는 경로들은 전통적인 접미사 트리 보다 짧거나 같은 경 길이를 가진다. 우리의 트리는 전통적인 접미사 트리보다 적은 노드와 경로들을 가진다. 왜냐하면, 그것은 식별자로 시작하는 다중 서열 접미사를 가지지 않기 때문이다(즉, <*1>BK<*2>와 같은 접미사는 없다).
다중 서열 BMBK*BK*(*는 공통의 서열 식별자이다)의 유효한 접미사들은 정확히 원래 서열의 접미사들이다: BMBK, MBK, BK, K (첫번째 서열 BMBK로 부터), BK, 그리고 K (두번째 서열 BK로 부터). 다중 서열로부터 생성된 유효한 접미사 배열은 그림 5에 보인다.
그림 5 다중 서열로부터 생성된 유효한 접미사 배열
배열로부터 생성된 유효한 접미사 트리는 그림 6에 보인다(접미사에 대한 정보를 가진 리프 노드들을 따라서 그려짐). 거기에는 * 식별자로 시작하는 다중 서열의 접미사에 대한 정보를 저장하기 위해 메모리를 사용하지 않았다.
그림 6 배열로부터 생성된 유효한 접미사 트리
우리가 여기에 보인 접미사 트리 구현은 다중 서열을 표현하고 다중 서열에서 문자열들이나 패턴들을 검색하기 위해서 설계되었다. 그것은 실제적으로 생성하는데 거의 선형의 시간과 선형의 공간을 요구하고, 메모리 관리 오버헤드가 없다. 표 1은 다중 서열(서열은 단백질 서열이다)의 크기를 증가시켜가며 생성한 다른 크기의 접미사 트리에 대한 몇몇 실험적 결과를 보인다. 모든 결과는 단일 PC에서 단일 프로세서 500-MHz 펜티엄과 1 GB 메모리를 사용해서 얻어졌다.
참고
단 구스필드, 문자열, 트리, 그리고 서열에 대한 알고리즘들-컴퓨터 과학과 컴퓨테이셔널 생물학, 캠브리지 대학 출판사, 1997년(Gusfield, Dan. Algorithms on Strings, Trees, and Sequences-Computer Science and Computational Biology, Cambridge University Press, 1997).
폴 비간스키, 존 리들, 존 칼리스. "생물학적 서열 데이터를 위한 일반화된 접미사 트리: 응용과 구현," 미네소타 대학, 1994년, http://www.cbc.umn.edu/VirtLibrary/ Bieganski/htree/htree-paper.ss.html (
Bieganski, Paul, John Riedl, and John Carlis. "Generalized Suffix Trees for Biological Sequence Data: Applications and Implementation," University of Minnesota, 1994, http://www.cbc.umn.edu/VirtLibrary/ Bieganski/htree/htree-paper.ss.html.)
마크 R. 넬슨 "접미사 트리를 이용한 빠른 문자열 검색,", DDJ, 1996년 8월(
Nelson, Mark R. "Fast String Searching With Suffix Trees," DDJ, August 1996)
댓글