(알고리즘) Manver-Myers 알고리즘(접미사 배열)

접미사 배열은 주어진 문자열에 대한 모든 접미사를 나열한 다음 알파벳순으로 정렬하는 배열입니다.

일반적으로 접미사 배열을 만드는 절차는 다음과 같습니다.

1. 문자열의 모든 접미사를 생성합니다.
   
   
2. 생성된 접미사를 첫 글자로 정렬합니다.
   
   
3. 이후 정렬 기준은 처음부터 2번째 문자, 3번째 문자 등으로 증가하며 문자열의 최대 길이인 n번째 문자로 변경하여 정렬한다.
   
   

위 과정에 따르면 1회 정렬하는데 $O(n log n)$의 시간이 소요되며 총 시간복잡도는 $O(n^2 log n)$가 되어 함께 표시된다.

이것은 Manver-Myers 알고리즘에 의해 $O(n log^2 n)$의 시간 복잡도로 줄일 수 있습니다.

이제 정렬이 어떻게 작동하는지 봅시다!

위의 표에서 바나나를 예로 들었습니다.

banana라는 접미사가 나열되는데 모두 배열에 넣으면 메모리 낭비가 심해질 수 있어 실제 배열은 접미사의 시작 부분을 갖는다.

실제 문자열에 있는 위치보여 주었다

다음으로 각 접미사를 유사한 접미사로 같은 그룹으로 묶고 각 그룹에 순위를 부여하기 위해 다음과 같은 배치를 추가로 한다.

위의 표는 각 색인과 관련된 접미사의 순위를 보여줍니다.

각 접미사의 첫 글자를 기준으로 순위를 매겼으며, “a”의 아스키 코드 값과의 차이로 계산하였다.

이제 우리는 첫 글자로 정렬합니다!

한 번 정렬하면 위와 같은 결과를 얻습니다.

첫 번째 문자 비교를 마친 후 두 번째 문자 비교로 이동합니다.

이를 수행하기 전에 위에서 정의한 순위 배열을 업데이트해야 합니다.

기존 랭크 배열은 각 접미사의 첫 번째 문자를 기준으로 했으므로 이번에는 두 번째 문자를 기준으로 랭크 배열을 초기화합니다.

위 표를 그룹으로 표현하면 다음과 같다.

1차 정렬 후 위와 같이 그룹이 분할되면 다시 한 번 분할하여 다음을 생성한다.

이때 원래 랭크가 같으면 첫 번째 캐릭터에서 2 떨어진 캐릭터를 기준으로 비교한다.

정렬 후 결과는 다음과 같습니다.

첫 번째 그룹이었던 A는 그룹에서 분리되어 앞으로 나아갑니다.

a의 경우 첫 번째 문자에서 2번째 떨어진 위치가 범위를 벗어나므로 순위를 -1로 계산하여 정렬했습니다.

이제 순위가 다시 계산되는데 이때 각 접미사 앞의 두 번째 글자를 기준으로 순위가 부여된다.

이 시점에서 na의 경우 처음부터 두 번째 문자가 없으므로 순위를 -1로 간주하고 계속합니다.

정렬 후 순위 배열이 다시 초기화됩니다.

순위 배열 초기화 프로세스를 자세히 살펴보겠습니다.

먼저 현재 접미사 배열의 맨 앞에 있는 접미사의 순위를 0으로 설정합니다.

이제 접미사 배열의 두 번째 위치에 있는 접미사와 첫 번째 위치에 있는 접미사를 비교합니다.

이 시점에서 이전 순위 값이 같으면 처음부터 t 위치에 있는 캐릭터의 순위를 비교합니다.

즉, 지금은 2입니다.

현재 anana와 a의 이전 순위를 비교하면 둘의 순위 값이 0인 것을 알 수 있습니다.

따라서 거리 2에 있는 문자를 비교하는데, a의 경우 거리 2에 있는 위치가 범위를 벗어나므로 비교를 위해 순위 값을 -1로 설정한다.

따라서 a의 rank 값이 anana의 rank 값보다 작기 때문에 둘은 서로 다른 rank를 가져야 함을 알 수 있으며 anana의 rank 값은 a의 rank 값에 +1, 0을 더하면 1이 된다.

이제 ana는 접미사 배열의 다음 위치에서 비교되며 이전 접미사 anana와 이전 순위 값은 모두 처음부터 두 번째 문자와 같기 때문에 해당 접미사는 anana와 동일한 순위 값을 갖습니다.

다음으로 이전 접미사 ana와 이전 순위 값도 다르기 때문에 ana보다 순위가 높은 바나나를 확인합니다.

위와 같은 방법으로 배열을 초기화하면 다음과 같은 결과를 얻을 수 있습니다.

의지 후 결과는 다음과 같습니다.

이번에는 처음부터 4번째 캐릭터를 기준으로 순위가 결정됩니다.

순위 배열의 가장 큰 값이 문자열의 길이와 같기 때문에 더 이상 정렬이 진행되지 않음을 알 수 있습니다.

따라서 마지막으로 정렬한 결과가 마지막 접미사 배열이 되고 반복문이 종료된다.

이때 현재 순위 값이 같으면 현재 위치 wo에서 떨어진 위치 t에 있는 문자를 기준으로 비교한다고 합니다.

t는 1에서 시작하여 2배 증가합니다.

. 이렇게 하면 문자열 길이만큼 정렬하지 않고 정렬 횟수를 $log n$로 표시할 수 있습니다.

Manver-Myers 알고리즘을 코드로 구현한 결과는 다음과 같습니다.

def sort_suffixes(text):
	n = len(text)
	suffixes = ()
	group = (0) * n
	group.append(-1) # 현재 위치에서 t만큼 떨어진 위치가 없는 경우 rank를 -1로 설정

	for i in range(n):
    	    suffixes.append(i)
    	    group(i) = ord(text(i)) - ord('a')

	while t < n:
    	    suffixes.sort(key=lambda x:(group(x), group(min(x+t, n))))
    	    new_group = (0) * n
    	    new_group.append(-1)
    
    	    for i in range(1, n):
        	    if group(suffixes(i-1)) !
= group(suffixes(i)) or group(min(suffixes(i-1)+t, n)) !
= group(min(suffixes(i)+t, n)):
                        # rank가 다르면 서로 다른 rank 값을 갖게함
            	        new_group(suffixes(i)) = new_group(suffixes(i-1)) + 1
        	    else:
                        # rank가 같은 경우 서로 같은 rank
            	        new_group(suffixes(i)) = new_group(suffixes(i-1))
    
    	    group = new_group
    	    if new_group(n-1) == n-1:
        	    break
    	    t *= 2
	return suffixes