접미사 배열 알고리즘 1
⛳️ 접미사 배열 알고리즘의 목적은 특정 문자열에서 접미사를 ‘사전 순서대로’ 배열하는 것입니다. 코세라에서 계속 lexiographic 이라고 해서 도대체 뭔가 싶었는데 사전식 배열을 의미하더라구요 !
이를테면, ‘a b a b a a’ 라는 문자열에서 가능한 접미사는
‘a’ - 시작인덱스 5
‘a a’ - 시작인덱스 4
‘b a a’ - 시작인덱스 3
‘a b a a’ - 시작인덱스 2
‘b a b a a’ - 시작인덱스 1
‘a b a b a a’ - 시작인덱스 0
이렇게 6가지가 있을 수 있습니다. 사전 순서대로 접미사를 배열하면,
‘a’ , ‘aa’, ‘abaa’, ‘ababaa’ , ‘baa’, ‘babaa’ 이렇게 배열해야합니다. 각 접미사에는 이름이 없으니 시작인덱스로 각 접미사의 이름을 지어줍시다 ! 그렇다면 suffix array 를 통해 접미사들은 [5,4,2,0,3,1] 로 정렬되게 됩니다.
1) SortCharacters
코세라 강의에 따르면 이 접미사 배열 알고리즘을 완성하기 위해 무려 네 가지 함수를 작성해야합니다. 정말 이것 공부하다가 뚝배기 깨질 뻔 하였습니다. 🤯
첫 번째 sort characters 는 문자열을 낱개로 다 분해하여서 그 낱개들의 순서를 정렬해주는 함수입니다.
수도코드를 보면, (코세라의 수도코드 정말 왜 이렇게 난해하게 쓰여있는지😩 )
우선
1) order <- array of size s
count <- zero array of size a
여기서 s = suffix array 를 실행하고 싶은 문자열이 됩니다. ‘ababaa$’ 라고 한다면,
($는 종료를 알리기 위해 추가해줍니다 ; 종료를 알려주는 문자열)
따라서 size of s = 문자열의 길이 = 7 이 됩니다.
a 는 해당 문자열에 존재하는 글자의 수 입니다. 문자열 전체 길이는 7이지만 알파벳은 총 3개 있습니다. (a,b,$) 따라서 size of a = 총 문자열 내 존재하는 알파벳 갯수 = 3 이 됩니다.
이 사이즈만큼 order 과 count 배열을 만들라고 하였으니까
order =[ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ] 이렇게 만들어놓고 차차 채워주면 됩니다.
실제 코드에서는 그냥 리스트 선언하고 나중에 append 시켜주면 될 것 같습니다 !
count = [ 0 , 0 , 0] 입니다. 그리고 count의 인덱스는 알파벳 순서가 제일 작은 순부터입니다. $ 와 같은 특수 기호는 모든 알파벳보다 순서가 먼저입니다. (하 코세라 이거 왜 안 알려주냐 햇갈리게 진짜)
따라서 count[0]=’$’ , count[1]=’a’, count[2]=’b’ 를 의미합니다.
2) for i from 0 to ( size a )- 1 :
count[s[i]] <- count[s[i]] + 1
s 는 문자열을 의미하므로 ‘ababaa$’ 입니다. 즉 s[0]=a,s[1]=b,s[3]=a … 입니다
count[[s[0]]] 이라고 한다면, s[0]=a 이므로 count[a] 가 되게 되고 a 는 count 에서 1번 인덱스이므로 count[1] 의 값이 1 증가합니다. 즉 이런 식으로 전체 문자열 인덱스를 돌며 $,a,b 각각의 글자가 총 몇 번 등장하는지가 count 에 담기게 됩니다.
3) for j from 1 to (size a) -1 :
count[j]=count[j]+count[j-1]
이를 실행하게 되면 문자열 s가 오름차순으로 정렬되었을 때 / 해당 알파벳이 마지막으로 등장하는 인덱스 값 +1 이 / count 각 인덱스에 담기게 됩니다. (특수기호 $ 제외)
s = ‘ababaa$’ 이므로 오름차순 정렬을 하게 되면 ‘$aaaabb’ 입니다. 알파벳 ‘a’는 인덱스 4에서 끝이 납니다. 알파벳 ‘b’는 인덱스 6에서 끝이 납니다.
현재의 count=[1,4,2] 입니다. 3) 을 실행하면 count=[1,5,6] 이 됩니다.
s = ‘ababaa$’ 이므로 오름차순 정렬을 하게 되면 ‘$aaaabb’ 입니다. 알파벳 ‘a’는 인덱스 4에서 끝이 납니다. 알파벳 ‘b’는 인덱스 6에서 끝이 납니다.
에서 실제 끝이 나는 인덱스보다 한 칸씩 밀린 것을 알 수 있습니다. 한 칸씩 밀린 이유는 실제 문자열 s 에서 $의 인덱스는 0인데 count 에서는 $의 값이 1이기 때문입니다. a가 정렬된 s 에서 끝나는 지점은 $인덱스 + 4칸인데 $인덱스인 0이 아니라 1 + 4칸을 하게 되니까 줄줄이 밀리게 되는 것입니다 !
4) for i from (size a) -1 down to 0:
c <-s[i]
Count[c] <- count[c] -1
Order[count[c]] <- i
return order
sort characters 는 문자열을 낱개로 다 분해하여서 그 낱개들의 순서를 정렬해주는 함수이므로 마지막 단계인 4)를 실행하게 되면 마침내 ‘ababaa$’ 이 [6,0,2,4,5,1,3] 으로 정렬됩니다.
하나 하나 보면 i 는 문자열 맨 끝 인덱스부터 돌면서 문자열의 해당 인덱스 글자의 count 를 1씩 낮춥니다.
맨 처음 i 는 (size a)-1 이므로 6입니다.
count 에서 ‘$’ 는 0번 인덱스이므로 count 는 이제 [1,5,6] 에서 [0,5,6] 으로 바뀌었습니다.
order[count[c]] <- i 이 부분은 정말 왜 이렇게 써놨는지를 모르겠는데 ㅋㅋㅋㅋㅋㅋ
결국 문자열 s 에서 해당 문자의 인덱스가 i 번째에 와야 함을 의미합니다. 그 이유는 결국
count[$] <- count[$] -1 까지 한 값이
s 를 오름차순 정렬했을 때의 인덱스 값이기 때문입니다. -1 을 해주었으므로 밀린 게 원상복귀 됩니다. count[$] = 0 으로 바뀌었으므로 , ‘$aaaabb’ 에서 0번 인덱스를 잘 가리키고 있습니다. 즉 “전체 문자열의 글자를 오름차순 정렬하면 ‘$aaaabb’ 순서인데 그 중 $는 0번 인덱스이므로 제일 먼저 와” 가 됩니다.
sort characters 는 문자열을 낱개로 다 분해하여서 그 낱개들의 순서를 정렬해주는 함수이므로 그러면 order =[ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ] 의 맨 처음 (0번 인덱스) 박스에는 $ 가 들어가야합니다. 즉 문자열 s 에서 $의 인덱스는 $ <-s[6] 이었으므로 6입니다. 따라서 order 은 이제 [ 6 ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ⬜️ ] 입니다. 한 칸이 채워졌습니다 !
두 번째 i 는 6부터 쭉 for 문을 내림차순으로 돌아가니까 5가 됩니다. c=s[5]=a입니다. 더 정확히 말한다면 문자열 s 에 ‘a’ 의 5번째 인덱스 a 입니다. (ababaa$)
이제부터 c는 문자열 s 의 5번째 인덱스 a 를 가리킨다고 다 바꾸어놓겠습니다.
Count[a] <- count[a] -1
이므로 count 는 이제 [0,5,6] 에서 [0,4,6] 으로 바뀌었습니다. 즉 “전체 문자열의 글자를 오름차순 정렬하면 ‘$aaaabb’ 순서인데 그 중 원 문자열 s 에서 5번째 인덱스이던 a는 정렬된 s에서 4번 인덱스이므로 네번째 와” 가 됩니다.
sort characters 는 문자열을 낱개로 다 분해하여서 그 낱개들의 순서를 정렬해주는 함수이므로 그러면 order =[ 6 ⬜️ ⬜️ ⬜️ 5 ⬜️ ⬜️ ] 의 4번째 인덱스 박스에는 원 문자열 s 에서 5번째 인덱스 a 가 들어가야합니다. c=s[5]=문자열 s 의 다섯번째 인덱스 a 였으므로 따라서 order[4]=5 입니다. 한 칸이 또 채워졌습니다.
이런 식으로 계속 하다보면 order = [6 0 2 4 5 1 3] (각 숫자는 s에서의 인덱스 넘버) 이 되어서 잘 정렬되게 됩니다.
s[6]=$, s[0]=a,s[2]=a,s[4]=a,s[5]=a,s[1]=b,s[3]=b 이렇게 성공적으로 정렬되었음을 알 수 있습니다.
자야겠다 🌝
현재 시각은 밤 12시 18분 . 안 자고 포스팅하는 이유는 오늘 6시간에 걸쳐서 접미사 배열을 겨우 이해했는데 정리를 안 해두면 리셋될게 두렵고, 또 저는 사실 안 심한 디스크 환자인데 아주 가끔 밤에 잠자리가 몹시 불편하기 때문입니다. 랜덤하게 찾아와요 그날의 컨디션에 따라서(방사통이 조금 있어도 너무 피곤하면 곯아떨어지기를 바라고 있어요)
내일의 나를 믿고 ^^ 내일 상쾌한 마음으로 🌞 마저 복습하고 내일은 무리 안 하고 닌텐도 할꺼에요 (굳은 의지) 오늘 css 가지고 놀려고 블로그 폰트를 바꿔봤는데 가독성이 너무 떨어지네요. 역시 나눔고딕이 짱입니다