2023. 6. 11. 20:39ㆍAlgorithm
이번 글에서는, 문자열 정렬과 (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
- 각 key의 빈도수를 계산해, count[key+1]에 저장한다.
(count[a[i]+1]++) - 각 key의 첫 item의 정렬 위치를 계산한다. (by 빈도수 누적 계산을 통해)
(count[r+1] += count[r]) - 각 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
맨 오른쪽 문자부터 맨 왼쪽 문자까지 차례대로 정렬한다.
- W번째 문자를 key로 사용하여, N개의 문자열을 정렬한다. (by key-indexed counting)
- W를 1 감소시킨다.
- 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
맨 왼쪽 문자부터 차례대로 정렬한다.
- $i$번째 문자를 key로 사용하여, 문자열들을 정렬한다. (by key-indexed counting)
- key($i$번째 문자)를 기준으로 문자열들을 partition한다.
즉, 같은 key를 가진 문자열들끼리 묶는다. - 각 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)로 두는 것이다.
때문에,
- 일반적인 3-way quicksort과 다르게, pivot 문자(char)를 재조사하지 않는다.
- 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
- 전처리(=preprocess): 말뭉치의 suffix array를 만든 후, 이를 정렬한다.
- 질의(=query): 이진 탐색을 통해, 질의 문자열과 일치하는 문자열의 모든 위치를 찾은 후, 문맥을 찾는다.
2. Longest repeated substring
매우 긴 말뭉치(length=N)가 주어졌을 때, 가장 긴 반복 문자열을 찾는 문제다.
Algorithm
- 전처리(=preprocess): 말뭉치의 suffix array를 만든 후, 이를 정렬한다.
- 정렬된 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하다.
'Algorithm' 카테고리의 다른 글
[Algorithm Part 2] 8. Substring Search (0) | 2023.06.19 |
---|---|
[Algorithm Part 2] 7. Tries (0) | 2023.06.17 |
[Algorithm Part 2] 5. Mincut/Maxflow (0) | 2023.05.23 |
[Algorithm Part 2] 4. Shortest Paths (0) | 2023.05.22 |
[Algorithm Part 2] 3. Minimum Spanning Tree (0) | 2023.05.08 |