Suffix array
From CSBLwiki
Seq = 'ABCABBAC'
group = {A,B,C}
nodes P |seq(node)
1.ABCABBAC
2.BCABBAC
3.CABBAC
4.ABBAC
5.BBAC
6.BAC
7.AC
8.C
위 노드들을 다시 알파벳 순으로 정렬,
position \ node \ LCP
4 \ 1.ABBAC 0
1 \ 2.ABCABBAC 2
7 \ 3.AC 1
6 \ 4.BAC 0
5 \ 5.BBAC 1
2 \ 6.BCABBAC 1
8 \ 7.C 0
3 \ 8.CABBAC 1
각 node 를 정렬 할때 LCP를 계산 (n-1 과 n )
- 1 2 3 4 5 6 7 8
- A B C A B B A C
- o x + o x x o +
- {4,1,7,6,5,2,8,3}
각 포지션 에는 LCP 를 저장 하고 , LCP 에 저장 된 값에 포함된 노드의 위치까지를 소환 하여
비교 합니다.
여기서 만약 비교할 seq 가 'ABB'라면 !
A -> {4,1,7}
- AB -> {4,1} ! / {7}
- ABB -> {4} ! /{1} /{7}
(여러가지 더 좋은 방법 이 많지만 , 제가 확실하게 아는것은....앞으로 더 공부 하도록 하겠습니다.제가 제대로 이해 하지못해 죄송합니다.)
긴 시퀀스 라면,
첫번째 문자 와 같은 그룹 을 위 ABB 를 탐색 하는 과정 처럼 탐색 하고 , 더 이상 일치 하지 않으면,일치하는 노드의 포지션과 LCP + 일치하는 숫자 까지 저장 (예- ABBCCA - {4}) 그 문자열과 동일한
그룹을 다시 검색, 하고 다시 같은 과정을 거치고 다시 저장 하는 방법 을 사용 하면 될 것 이라고 이해 했습니다.
ABCDE
ABCGHERADE
- |
- |
ABC------DE
ABCCGHERADE
제가 혹시 완전히 잘못이해 한것 일까요 교수님?
제가 완전히 이해하고 충분히 잘 활용 할수 있을때 까지 조금 시간이 걸릴 것 같습니다 ..
그리고 계속 업데이트 하도록 하겠습니다.
