3) SortDoubled(S,L,order,class)
sortdoubled 에서 L은 얼만큼 shift 해줄지입니다.
sortdoubled 함수는 L 만큼 shift 된 문자열 n개 (n;기존 order이 알파벳 몇 개를 기준으로 정렬되었는지) + 기존에 의해 정렬된 알파 n개 로 하여 사이즈를 2배로 늘려준 후 (인덱스도 L만큼 shift 된 기준으로 변환) 다시 정렬한 순서를 order 에 반환해주는 함수입니다.
말로 하면 설명을 정말 잘 못하겠는데 그림을 그려보면 생각보다 간단합니다. ㅡ
현재 order = [6,0,2,4,5,1,3] 입니다. 그리고 이 order 은 전체 문자열을 단일 글자 1개씩 비교해주며 순서를 정렬해준 것입니다. 따라서 n=1이 됩니다. 즉 L로 정한 크기만큼 order 의 각 인덱스보다 먼저 오는 인덱스 글자 n개를, 기존 order 의 인덱스에 해당하는 글자 앞에 추가해줍니다.
구분을 위해 편의상 order 의 맨 마지막열을 그림에서 빨간색 1로 표시했습니다.
Order[6]=s[3] 에 빨간색 1번으로 표시되어있습니다. 그런데 L을 1로 정했고, order이 현재 단일 글자 1개씩을 비교해준 것이므로 (sortcharacters 함수) 앞으로 한 칸 더 간 파란색 1번만 앞에 덧붙여주게 됩니다. 그러면 b가 아니라 ab가 됩니다. 그런데 이제 ab는 더 이상 s[6] 이 아니라 s[2] 입니다.
이런 식으로 하면 2L 갯수만큼 비교할 문자열 갯수가 늘어나게 됩니다.
Order[0]=s[5]부터 2개=a$
Order[1]=s[6]부터 2개=$a
Order[2]=s[1]부터 2개=ba
Order[3]=s[3]부터 2개=ba
Order[4]=s[4]부터 2개=aa
Order[5]=s[0]부터 2개=ab
Order[6]=s[2]부터 2개=ab
다시 사전 순서대로 정렬해주면 order=[6,5,4,0,2,1,3] 이 되어야합니다. 즉 sortdoubled 는 L=1일 때 [6,5,4,0,2,1,3] 을 반환해야합니다.
1) count <- zero array of size s
newOrder <- array of size s
이므로 count = [0,0,0,0,0,0,0]
newOrder=[⬜️,⬜️,⬜️,⬜️,⬜️,⬜️,⬜️] 입니다. 사실 count 에서 0,1,2,번 인덱스만 쓰는데 왜 굳이 7칸을 만들라고 했는지 의문이 듭니다.
2) for i from 0 to (size s) -1:
count[class[i]] <- count[class[i]] +1
기존 sortcharacters 함수와 동일하게 s 인덱스를 쭉 돌며 등장한 알파벳 갯수를 세어줍니다. sort characters 와 동일하게 이때 인덱스는 $,a,b 순입니다.
그러면 count=[1,4,2,0,0,0,0] 이 됩니다. ($는 1번 등장,a는 4번 등장,b는 2번 등장)
3) for j from 1 to (size s) -1:
count[j] <-count[j] + count[j-1]
이것도 sortcharacters 함수와 동일하게 이를 실행하게 되면 문자열 s가 오름차순으로 정렬되었을 때 / 해당 알파벳이 마지막으로 등장하는 인덱스 값 +1 이 / count 각 인덱스에 담기게 됩니다. (특수기호 $ 제외). 단 차이가 있다면 count 의 size 가 문자열 s에 존재하는 전체 알파벳 글자 수보다 많으므로 인덱스 0,1,2 이후의 인덱스에서도 값이 증가한 채 존재합니다.
count=[1,4,2,0,0,0,0] 에서
count=[1,5,7,7,7,7,7] 으로 바뀝니다.
4) for i from (size s) - 1 down to 0 :
start <- (order[i]-L+size s) % size s
cl <-class[start]
count[cl] <-count[cl] -1
newOrder[count[cl]] <- start
start <- (order[i]-L+size s) % size s 부터 보면 order[i]-L은 L만큼 shift된 후의 인덱스를 의미하고 +size s 를 하게 되면 7칸을 돌아서 제자리로 다시 돌아오게 됩니다. 이후 %size s 를 하면 결국 L만큼 shift 된 후의 인덱스 값이 start 가 됩니다.
근데 이렇게 할꺼면 바로 (order[i]-L) %7로 하지 왜 이렇게 굳이 썼는지 의문입니다. 🤨
Order[6]=s[3] 은 원래 ‘b’ 였는데 이제 start는 s[2] 인 a가 됩니다.
그 후 cl <-class[start] 를 통해 start 의 알파벳이 0($),1(a),2(b) 중 몇 번째 클래스에 속하는지 알아냅니다. class 함수는 computecharclasses 함수를 통해서 [1,2,1,2,1,1,0] 으로 구해졌습니다. 따라서 cl=1입니다.
그 후 count[cl] <-count[cl] -1 를 통해 “전체 문자열의 글자를 오름차순 정렬하면 ‘$aaaabb’ 순서인데 그 중 s[2]는 4번 인덱스이므로 네 번째에 와” 가 됩니다.
따라서 newOrder=[⬜️,⬜️,⬜️,⬜️,2,⬜️,⬜️] 가 되었습니다.
이런 식으로 쭉 실행하면 L=1일 때 [6,5,4,0,2,1,3] 이 성공적으로 반환됩니다.
$a
a$
aa
ab
ab
ba
ba ($ 앞이 접미사 !)
L=1일 때 이렇게 성공적으로 정렬이 되었는데 new order 의 각 인덱스인 2L개의 문자열이 전체 문자열 s의 어느 부분인지는 확실하지 않으나 2L개는 순차적으로 이어졌음은 확실합니다. 즉 new order[2]=s[5]부터 시작하여 2개 (2L개)=’a$’ 에서 $ 이전에 a 가 온다는 것은 확실합니다. 즉 어떠한 2L개의 문자열에는 $가 들어있고 접미사의 정의가 $ 이전에 오는 부분 문자열이므로 이 때는 접미사가 들어갔다고 할 수 있습니다. L=1일 때는 접미사가 1개가 나왔습니다. 그리고 L을 넣으면 2L개의 문자열이 정렬된 newOrder 이 반환된다는 것도 알고 있습니다.
아이디어 🤔
그렇다면 어떠한 L에 대해서 2L > size of s 이라면 이 때 반환되는 2L개의 문자열은 적어도 s의 모든 글자를 한번씩은 포함함을 의미합니다. 그렇다면 이 경우에는 반환되는 총 7개의 (각 2L개 문자열) 모두에 접미사가 있을 것입니다. 그런데 해당 함수는 2L개의 문자열이 정렬된 newOrder 을 반환하으로 따라서 2L>size of s 인 경우에 정렬된 접미사의 순서가 new order 에 반환되므로 suffix array 가 성공적으로 가능합니다 !
- 2L > size of s 인 경우 실제 neworder
전체 수도코드,시간복잡도
