[Algorithm Part 2] 6. String Sort

이번 글에서는, 문자열 정렬과 (suffix array를 활용한) 문자열 탐색에 대해 살펴볼 것이다.

 

효율적인 문자열 정렬 및 탐색을 하기 위해서는,

문자열 자료형(e.g., Java: String, Python: str)의 내부 구현 방식이 숙지되어 있어야 한다.

---

이전 정렬 알고리즘은 $N\log N$번의 비교 연산으로 모든 유형의 자료형을 정렬한다.

하지만, 문자열을 더 빠르게 정렬하는 방법이 존재한다. (이때, 비교 연산을 사용하지 않는다.)

0. Key-indexed counting

key 개수가 유한한 N개의 item을 정렬하는 알고리즘이다.

Assumption

배열 index를 key로 표현하기 위해, key를 0 ~ R-1사이의 정수로 고정한다.

 Algorithm

1. 각 key의 빈도수를 계산해, count[key+1]에 저장한다.
   (count[a[i]+1]++)
2. 각 key의 첫 item의 정렬 위치를 계산한다. (by 빈도수 누적 계산을 통해)
   (count[r+1] += count[r])
3. 각 item을 정렬 위치에 배치시킨다. 
   (aux[count[a[i]]++] = a[i])

 Performance

time-complexity	space-complexity
N + R	N + R

위 정렬 알고리즘은 STABLE하다!!

---

key-indexed counting 알고리즘을 활용해 유용한 문자열 정렬 알고리즘을 만들 수 있다.

1. Least-significant-digit-first string sort (LSD string (radix) sort)

"문자열 길이(=L)가 동일한 N개의 문자열을 정렬"하는 알고리즘이다.

Algorithm

맨 오른쪽 문자부터 맨 왼쪽 문자까지 차례대로 정렬한다. 

1. W번째 문자를 key로 사용하여, N개의 문자열을 정렬한다. (by key-indexed counting)
2. W를 1 감소시킨다.
3. W가 0이 될 때까지 반복한다.

key-indexed counting 알고리즘은 stable하기 때문에, 위 알고리즘은 정확(=correctness)하다.

Question. How to sort one million 32-bit integers

 

Algorithm	Quick sort	LSD sort
Performance	$6 \times 10^6 \log 10$	$2 \times 32 \times 10^6$

Answer. LSD sort is faster than quick sort

---

2. Most-significant-digit-first string sort (MSD string (radix) sort)

"N개의 문자열을 정렬"하는 알고리즘이다.

Algorithm

맨 왼쪽 문자부터 차례대로 정렬한다. 

1. $i$번째 문자를 key로 사용하여, 문자열들을 정렬한다. (by key-indexed counting)
2. key($i$번째 문자)를 기준으로 문자열들을 partition한다.
   즉, 같은 key를 가진 문자열들끼리 묶는다.
3. 각 partition에 속해 있는 문자열들을 정렬한다.
   (만약, 2개 이상의 partition으로  쪼갤 수 있다면, 재귀를 통해 정렬한다.)

Observation

LSD string sort	MSD string sort
모든 문자 조사	필요한 문자만 조사 (but 재귀 호출 overhead)

LSD string sort는 모든 문자열의 문자를 조사한다. 그에 반해, MSD string sort는 정렬에 필요한 문자만 조사한다. 즉, MSD string sort의 문자 조사 횟수가 상대적으로 적다. 

 

하지만, 재귀 호출로 인한 count[] 추가 할당으로, 상당한 메모리 및 실행 시간 overhead가 생긴다.

때문에, 중간에 재귀 호출을 중단하고, 삽입 정렬을 사용해 overhead를 줄이는 방법이 있다.

MSD string sort vs quicksort for strings

 

MSD string sort	Quick sort for string
count[] 추가 할당	$N\log N$문자열 비교 연산 (연산 비용 ↑)
명령어가 많은 반복문	불필요한 연산이 빈번함 (중복된 접두사(prefix)를 rescan함)
"무작위" 메모리 접근 (비효율적 cache)

---

3. 3-way string quicksort

이전 글에서 보았던, 3-way quicksort와 거의 비슷하다. 

차이점은 key를 문자열(string)로 두는 것이 아닌, $i$번째 문자(char)로 두는 것이다.

 

때문에,

1. 일반적인 3-way quicksort과 다르게, pivot 문자(char)를 재조사하지 않는다.
2. MSD string sort보다, overhead가 훨씬 적다.

algorithm	guarantee	random	extra space	stable
LSD	$2NW$	$2NW$	$N + R$	O
MSD	$2NW$	$N \log_R N$	$N + DR$	O
3-way quicksort	$1.39N \log R$	$1.39N \log R$	$\log N + W$	X

---

이번에는 suffix arrray(접미사 배열)을 활용한, 문자열 탐색 알고리즘에 대해 살펴보겠다.

1. Keyword-in-context search

매우 긴 말뭉치(length=N)가 주어졌을 때, 질의 문자열과 일치하는 모든 문맥(context)을 찾는 문제다.

Algorithm

1. 전처리(=preprocess): 말뭉치의 suffix array를 만든 후, 이를 정렬한다.
2. 질의(=query): 이진 탐색을 통해, 질의 문자열과 일치하는 문자열의 모든 위치를 찾은 후, 문맥을 찾는다.

---

2. Longest repeated substring

매우 긴 말뭉치(length=N)가 주어졌을 때, 가장 긴 반복 문자열을 찾는 문제다.

Algorithm

1. 전처리(=preprocess): 말뭉치의 suffix array를 만든 후, 이를 정렬한다.
2. 정렬된 suffix array를 탐색하면서, 가장 진 반복 문자열을 찾는다.

Problem

만약 가장 긴 반복 문자열의 길이가 매우 길 경우, suffix array를 활용한 알고리즘은 매우 비효율적이다.

위 알고리즘은 문자 조사를 적어도 $1 + 2 + \cdots + D$번 한다. (D = length of longest match string)

왜냐하면, 가장 긴 반복 문자열의 부분 문자열들(=모든 접두사)의 문자를 모두 조사해야 하기 때문이다.

이때, $D = N/2$일 경우 문자 조사 횟수가  $N^2/2$이 되기에 매우 비효율적이다.

---

2.1. Manber-Myers algorithm

inverse[]: index는 각 suffix의 이름(=길이)을 의미하며, value는 suffix의 정렬 순서를 의미한다.

각 phase마다 inverse[]를 수정한다. 이때, phase i-1에서 만든 inverse[]를 inverse$_{i-1}$[]로 가정한다.

• phase 0: 첫 문자를 key로 사용하여, suffix array를 정렬한다. (by key-indexed counting)
• phase i: $2^{i-1}$번째 문자까지 정렬된 suffix array를 가지고, 
  $2^i$번째 문자까지 정렬된 suffix array를 만든다.
  (이때, inverse를 이용하면, sub string 비교 연산 시간이 constant하다.)
  (단계가 올라갈수록 고려해야할 문자 개수를 배로 증가한다.)

 

때문에, quick sort 혹은 merge sort를 같이 사용하면, $N \log N$ worst time complexity가 나온다.

더 나아가 3-way quick sort를 하면 더 빠르게 처리할 수 있다.

 

k와 l sub string($1$th char $\sim$ $2^i$th char) 비교 즉, suffix${_{2^i}}$[k]와 suffix${_{2^i}}$[l] 비교 연산

• suffix${_{2^{i-1}}}$[k]와 suffix${_{2^{i-1}}}$[l]은 동일하다고 가정하면, suffix${_{{2^{i-1}}+1\sim{2^{i}}}}$[k]와 suffix${_{{2^{i-1}}+1\sim{2^{i}}}}$[l]을 비교한다.
• suffix${_{{2^{i-1}}+1\sim{2^{i}}}}$[k]와 suffix${_{{2^{i-1}}+1\sim{2^{i}}}}$[l]의 관계는
  suffix${_{2^{i-1}}}$[k + $2^{i-1}$]와 suffix${_{2^{i-1}}}$[l + $2^{i-1}$]의 관계와 동일하다. (잘 생각해보십쇼!!)
• suffix${_{2^{i-1}}}$[] = inverse$_{i-1}$[]이기에, sub string($1$th char $\sim$ $2^i$th char) 비교 연산 시간이 constant하다.