[SW Expert Academy] Advanced-7 문자열 탐색
문자열 처리는 다음과 같이 많은 응용 분야에서 중요한 요소로 쓰인다.
1. 정보 검색: 키워드 기반의 웹페이지 검색
2. 통신 시스템: 텍스트 메세지/이메일 전송, 전자책 다운로드
3. 프로그래밍 시스템: 컴파일러, 인터프리터
4.유전학: 유전자(DMA)를 문자열 형태(A,C,T,G)로 표현해서 처리
구글이나 네이버 검색 엔진 면접을 보게 된다면, 반드시 공부하고 가야 할 내용이다.
플로우 1. 해싱 2. 문자열 매칭(패턴 매칭) 3. 압축 4. 트라이
ti++, pi++
3. 압축
count = 1
prev = '\0'
while input remains:
curr = get next symbol
if prev = cur AND count<MAXCOUNT:
count++
else
output(prev, count)
count = 1
prev = curr
output(curr, count)
REDecoding():
while input remains:
cur = get symbol
count = get count
while count>0:
output(cur)
count--
4. 트라이(Trie): 문자열의 집합을 표현하는 Tree로 정보검색에 사용한다.
그림1과 같이, 트라이의 각 간선은 하나의 문자에 대응한다. 그리고 루트에서 단말 노드까지 이른 경로가 하나의 문자열이 된다.
정수를 이진 탐색 트리로 검색하면 O(logN)이 걸린다.
하지만, 문자열을 이진 탐색 트리로 검색하면 O(MlogN)이 걸린다(M은 문자열 길이).
트라이는 문자열을 O(M)만에 검색하도록 해주는 자료구조이다.
(https://jason9319.tistory.com/129)
4-1. 접미사 트라이(suffix trie): 문다열의 모든 접미사를 Trie로 표현한다. (그림2 참조)
길이가 n인 문자열 A = a0|a1|a2|...|an-1|
A = ai|ai+1|...|an-1|인 n개의 접미사 (0<=i<=n-1)
활용 방식
1. 부분 문자열 검사
문자열의 모든 부분 문자열은 결국 어떤 접미사의 접두사임
suffix trie는 모든 부분 문자열에 대응되는 노드를 가지게 된다.
-ANAN은 ANANS의 접두사이이므로 트라이 상에 존재
이를 통해 부분 문자열을 빠르게 찾아낼 수 있음
2. 두 접미사의 최장 공통 접두사 찾기
3. 사전적 순서로 정렬된 k번째 접미사 찾기
4-2. 접미사 트리: 문자열 연산에 필요한 알고리즘을 빠르게 구현 가능하다.
기존 suffix trie의 단점은 지나친 메모리를 낭비한다는 점이다. 예를 들어 문자열 길이가 1000개이면, 접미사 길이의 합은 50만이나 된다.
이를 해결하기 위해 접미사 트리(suffix tree)(그림3)을 구현한다. 접미사 트리는 한 간선에서 여러 문자를 저장하여, suffix trie의 분기가 없는 경로를 하나의 간선으로 통합시킨다.
-응용: 문자열 매칭, 부분문자열 매칭, 최장 공통 부분문자열(Longest common ssubstring) 찾기
->알고리즘 문제에 잘 사용안한다고 함. 오히려 접미사 배열을 많이 쓴다고 함.
4-3*. 접미사 배열(suffix array)
문자열의 맥가이버 칼이라 불리며, 다양한 문자열 문제에 적용이 가능하다.
문자열 S의 모든 접미사를 사전순으로 정렬한다(그림 4).
-접미사 배열 생성하기 (원시적인 방식)
코드
//두 접미사 시작 위치 i,j가 주어질 때 두 접미사 중 어느 쪽이 앞에 와야 할지 비교한다.
struct SuffixComparator{
const string& s;
SuffixComparator(const string& s) : s(s) {}
bool operator () (int i, int j){
return strcmp(s.c_str() + i, s.c_str() + j ) < 0; //c_str()은 string 오브젝트의 포인터 반환 -> string을 char*로 변환할 때 사용
};
//s의 접미사 배열을 계산한다.
vector<int> getSuffixArrayNaive(const string& s){
vector<int> perm;
for(int i=0; i<s.size(); ++i) perm.push_back(i);
sort(perm.begin(), perm.end(), SuffixComparator(s));
return perm;
}
-생성하는데 걸리는 시간 복잡도: O(|n|^2*log|n|)
sort()의 시간 복잡도는 O(nlogn)이지만, 각 두 원소 비교가 O(n)만큼 걸리기 떄문이다.
하지만, 실제로는 모든 글자를 비교(O(n))하는 일은 거의 없기 때문에 더욱 빠르게 수행된다.
-접미사 배열 생성하기 (맨버-마이어스 알고리즘)
-> 시간 복잡도를 줄이기 위한 방법이다.
-> 다음에 공부해서 보충할 예정
-예제: 문자열 검색 (원 문자열 길이: H, 탐색 문자열 길이: N)
부분 문자열은 어떤 접미사의 접두사이다.
접미사 배열을 이진 탐색해서, 각 문자열이 출연하는 위치를 찾는다. O(log|H|)
각 문자열을 비교하는 데 걸리는 시간: O(|N|)
시간 복잡도: O(|N|log|H|)
1. 정보 검색: 키워드 기반의 웹페이지 검색
2. 통신 시스템: 텍스트 메세지/이메일 전송, 전자책 다운로드
3. 프로그래밍 시스템: 컴파일러, 인터프리터
4.유전학: 유전자(DMA)를 문자열 형태(A,C,T,G)로 표현해서 처리
구글이나 네이버 검색 엔진 면접을 보게 된다면, 반드시 공부하고 가야 할 내용이다.
플로우 1. 해싱 2. 문자열 매칭(패턴 매칭) 3. 압축 4. 트라이
1. 해싱
특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아 가는 방법
시간 복잡도: O(1)
배열 (직접 번지 테이블): key가 인덱스가 되어서 배열에 저장하는 방법
-전체 key들의 집합(U)이 작은 경우에 효율적임
-전체 key들의 집합(U)이 커지면, 현실적인 메모리 공간에서 테이블(T) 생성이 불가능해짐
-전체 key들의 집합(U)에 비해 실제 키 집합(K)가 작으므로 T의 메모리 공간이 낭비됨
해시 테이블: 해시 함수(h(k))를 이용하여 키값이 k인 자료를 h(k)위치에 저장한다.
-집합 U에 비해 K가 작을 때 사용함
-테이블의 인덱스 범위를 줄여준다.
-배열 방식보다 메모리 공간이 적게 필요함 (θ(|K|))
충돌(Collision): 서로 다른 키 값을 해시 함수에 적용할 때, 반환된 해시 함수가 동일한 경우
-해시 함수가 자료를 공평하게 분배해도, 해시 테이블에 저장되는 키에 해당하는 자료의 수가 증가하면 충돌은 불가피하다.
-해결 방법
(1). Chaining: 하나의 버킷에 여러개의 키 값을 저장하도록 연결 리스트를 활용
(2). Open Address: 해쉬 함수로 구한 주소에 빈 공간이 없어 collision되면, 그 다음 위치에 빈 공간이 있는지 조사
-빈 공간이 있을 경우 -> key에 대한 item을 저장
-빈 공간이 없을 경우 -> 빈 공간이 나올 때까지 탐색 반복
2. 문자열 매칭 (패턴 매칭)
2-1. 고지식한 패턴 검색 알고리즘
본문 문자열을 처음부터 끝까지 순회하면서, 패턴 내의 문자들을 일일히 비교함
-불일치가 발생하면 텍스트(t)는 이전 시작의 다음 위치로 두고, 패턴(p)는 항상 처음부터 다시 시작한다.
-수도 코드
BrutoForce(p[], t[]):
pi <- 0, ti <- 0
while ti < tn and pi < pn: // tn: 텍스트 길이, pn: 패턴 길이
if t[ti] != p[pi]:
ti <- ti - pi
pi <- -1
ti++, pi++
if pi==pn: return ti-pn
else : return ti
-시간 복잡도: O(tn*pn)
2-2. 카프-라빈(Karp-Rabin) 알고리즘
패턴의 해쉬 값과 텍스트 내의 패턴 길이만큼의 문자열에 대한 해쉬 값 비교
-시간 복잡도: O(tn*pn)
-평균적으로 선형에 가까운 빠른 속도를 가진다.
-고려 사항
(1) 처음 해시 값을 구할 때, 찾고자 하는 문자열에서 패턴 길이만큼 읽어서 구한다.
(2) 패턴의 길이가 커지면 모듈러 연산을 취하여 자릿수를 맞춘다. -> 해쉬 값이 표현 범위를 넘을 수 있기 때문임.
(3) 해시 값이 일치할 경우 실제 문자열이 일치하는지 검사한다. -> 모듈러를 취했으므로, 해쉬 값이 같아도 문자열이 다를 수 있다.
-예시
텍스트 문자열은 10개 숫자 문자열이라고 하자.
t[] = 6843212431
p[] = 4321
해시 값: 패턴을 십진수로 보고, 각 자리의 숫자에 자리값을 곱하고 모두 더한다.
4*1000+3*100+2*10+1 = 4321
해시값을 구할 때, 새로 추가되는 문자와 그 전에 계산한 값을 이용한다.
-Reference:https://idea-sketch.tistory.com/24
-한 문제 풀어봤으면 좋겠음.
2-3. KMP 알고리즘
불일치가 발생한 텍스트 문자열의 앞에 어떤 문자가 있는지 이미 알고 있으므로, 다시 비교를 하지 않는다.
-불일치가 발생하면 다음 비교 위치를 미리 계산하여 불필요한 시작을 최소화함.
-next: 불일치 발생 시, 돌아갈 곳을 저장하는 배열
-> 현재 인덱스보다 이전까지의 패턴(p) 중, 접두사 = 접미사인 최대 갯수를 저장
-> 접두사 = 접미사인, 접두사의 최대 인덱스+1를 저장함
-수도 코드
(1) next 구하기
KMP_Preprocess(p[], next[]):
ri <- 0, fi <- -1 // fi: 접두사 인덱스, ri: 접미사 인덱스
next[i] <- -1
while ri<pn:
while fi >= 0 && p[ri] != p[fi]:
fi <- next[fi]
ri++, fi++
next[ri] <- fi
(2) 문자열 매칭하기
KMP_Search(t[], p[], next[]):
ti, pi <- 0
while(ti<tn):
while (pi >= 0 && t[ti] != p[pi]/*next[pi]*/): //잘못 표기된 듯
pi <- next[pi]
ti++, pi++
if (pi == pn): return ti-pi
return -1
-예시
t[]: a a a a b c d e a b c d a b c e f
p[]: a b c d a b c e f // a b a b a b c // a a a a a
next[]:-1 0 0 0 0 1 2 3 0 -1 0 0 1 2 3 4 -1 0 1 2 3
-시간 복잡도: O(tn+pn)
t[]의 인덱스(ti)는 멈추지 않고 연속적으로 진행되므로 O(tn+tp)임. (tn>tp라면 O(tn)이라 표현 가능)
2-4. 보이어-무어 알고리즘
대부분의 상용 소프트웨어에서 채택한 알고리즘이다.
오른쪽 끝에서 왼쪽으로 문자열을 비교하는 알고리즘
-앞부분보다 끝부분에 불일치가 일어날 확률이 높은 성질 이용
-패턴의 오른쪽 끝 문자에서 불일치가 발생하면, 텍스트의 문자가 패턴내에 없으면 패턴의 길이만큼 이동할 수 있다.
플로우
-패턴과 텍스트를 인덱스 0부터 비교해나간다.
-패턴의 오른쪽 끝부터 역순으로 텍스트의 범위에서 비교한다.
-일치하지 않다면,
->해당 텍스트가 패턴에 없다면 이동거리만큼 한번에 이동
-> 만일 해당 텍스트가 패턴에 있다면 일치하도록 이동 (스캡 배열을 사용함)
-스킵 배열: 오른쪽 끝 문자가 불일치하여, 패턴 내 문자가 있거나 없을 때, 몇칸을 이동해야하는 지 알려준다.
예: p[] = rithm 일때 스킵 배열은 다음과 같다.
|m|h|t |i |r |다른 모든 문자|
|0 |1|2|3|4| 5 |
->시간 복잡도: O(tn*pn)이지만, 일반적으로 O(tn)보다 시간 소요가 적다.
3. 압축
압축은 텍스트, 이미지, 음원, 영상 데이터 등 거의 모든 응용 분야에서 사용된다. 주 목적은 데이터 저장 공간을 절약하고, 네트워크로 데이터를 전송하는 시간을 단축하는 것이다. 데이터의 용량이 줄어들면, 데이터 전송 시간도 함께 줄어든다.
Encoding이란 데이터를 압축하는 것을 말한다. 반대로 Decoding이란 데이터를 원래 상태로 복구하는 것을 의미한다.
3-1 Run-length Encoding
동일한 값(코드)가 몇 번 반복되는지를 나타내는 방식이다.
E(ABBBBBBBCC) = A1B7C2
이미지 파일 포맷인 BMP 파일 포맷의 압축 방법으로 사용된다.
-수도코드
RLEncoding(input[]):count = 1
prev = '\0'
while input remains:
curr = get next symbol
if prev = cur AND count<MAXCOUNT:
count++
else
output(prev, count)
count = 1
prev = curr
output(curr, count)
REDecoding():
while input remains:
cur = get symbol
count = get count
while count>0:
output(cur)
count--
3-2 Huffman Code
기호의 빈도: 정체 데이터 안에서 기호가 차지하는 비율
허프만 트리: 각 기호에 이진 코드를 부여하기 위해 생성하는 이진 트리
고정 길이 코드: 기호에 대응하는 코드값의 길이가 똑같은 코드 체계 (ASCII)
접두사 코드: 가변 길이 코드의 한 종류로, 어느 코드가 다른 코드의 접두사가 되지 않는 코드 체계 {0, 11, 100, 101}
-> 공간량은 줄이되, 접두사가 겹치면 구분하는게 어려워지는 문제를 해결하기 위함.
허프칸 코드는 코드의 빈도가 높을 수록 작은 접두사 코드를 대입한다.
-허프만 트리 생성
단말 노드는 기호와 빈도를 저장하며, 부모 노드는 빈도만 저장한다.
(1) 각 기호와 빈도를 노드 형태로 리스트에 저장한다. [ f:5 -> e:9 -> c:12 -> b:13 -> d:16 -> a:45 ]
(2) 빈도수가 가장 적은 노드 2개를 선택한다. (f:5, e:9)
-2개의 노드를 자식으로 하는 부모 노드를 생성한다.
-부모 노드의 빈도는 자식 노드의 빈도의 합이다. (14)
-리스트는 다음과 같이 변한다. [c:12 -> b:13 -> 14(자식: f:5, e:9) -> d: 16 -> a:45]
-이 과정을 반복하여 이진 트리(허프만 트리)를 생성한다.
-허프만 트리를 베이스로, 루프로부터 기호가 있는 단말 노드까지의 경로가 접두사 코드(허프만 코드)가 된다.
3-3 Lampel-Ziv-Welch Encoding
고정 길이 코드: 기호에 대응하는 코드값의 길이가 똑같은 코드 체계 (ASCII)
접두사 코드: 가변 길이 코드의 한 종류로, 어느 코드가 다른 코드의 접두사가 되지 않는 코드 체계 {0, 11, 100, 101}
-> 공간량은 줄이되, 접두사가 겹치면 구분하는게 어려워지는 문제를 해결하기 위함.
허프칸 코드는 코드의 빈도가 높을 수록 작은 접두사 코드를 대입한다.
-허프만 트리 생성
단말 노드는 기호와 빈도를 저장하며, 부모 노드는 빈도만 저장한다.
(1) 각 기호와 빈도를 노드 형태로 리스트에 저장한다. [ f:5 -> e:9 -> c:12 -> b:13 -> d:16 -> a:45 ]
(2) 빈도수가 가장 적은 노드 2개를 선택한다. (f:5, e:9)
-2개의 노드를 자식으로 하는 부모 노드를 생성한다.
-부모 노드의 빈도는 자식 노드의 빈도의 합이다. (14)
-리스트는 다음과 같이 변한다. [c:12 -> b:13 -> 14(자식: f:5, e:9) -> d: 16 -> a:45]
-이 과정을 반복하여 이진 트리(허프만 트리)를 생성한다.
-허프만 트리를 베이스로, 루프로부터 기호가 있는 단말 노드까지의 경로가 접두사 코드(허프만 코드)가 된다.
3-3 Lampel-Ziv-Welch Encoding
4. 트라이(Trie): 문자열의 집합을 표현하는 Tree로 정보검색에 사용한다.
 |
| 그림 1. 알고리즘 문제 해결 전략, 구종만, p782 |
정수를 이진 탐색 트리로 검색하면 O(logN)이 걸린다.
하지만, 문자열을 이진 탐색 트리로 검색하면 O(MlogN)이 걸린다(M은 문자열 길이).
트라이는 문자열을 O(M)만에 검색하도록 해주는 자료구조이다.
(https://jason9319.tistory.com/129)
4-1. 접미사 트라이(suffix trie): 문다열의 모든 접미사를 Trie로 표현한다. (그림2 참조)
길이가 n인 문자열 A = a0|a1|a2|...|an-1|
A = ai|ai+1|...|an-1|인 n개의 접미사 (0<=i<=n-1)
 | |
|
 |
| 그림 3. 알고리즘 문제 해결 전략, 구종만, p786 |
활용 방식
1. 부분 문자열 검사
문자열의 모든 부분 문자열은 결국 어떤 접미사의 접두사임
suffix trie는 모든 부분 문자열에 대응되는 노드를 가지게 된다.
-ANAN은 ANANS의 접두사이이므로 트라이 상에 존재
이를 통해 부분 문자열을 빠르게 찾아낼 수 있음
2. 두 접미사의 최장 공통 접두사 찾기
3. 사전적 순서로 정렬된 k번째 접미사 찾기
4-2. 접미사 트리: 문자열 연산에 필요한 알고리즘을 빠르게 구현 가능하다.
기존 suffix trie의 단점은 지나친 메모리를 낭비한다는 점이다. 예를 들어 문자열 길이가 1000개이면, 접미사 길이의 합은 50만이나 된다.
이를 해결하기 위해 접미사 트리(suffix tree)(그림3)을 구현한다. 접미사 트리는 한 간선에서 여러 문자를 저장하여, suffix trie의 분기가 없는 경로를 하나의 간선으로 통합시킨다.
-응용: 문자열 매칭, 부분문자열 매칭, 최장 공통 부분문자열(Longest common ssubstring) 찾기
->알고리즘 문제에 잘 사용안한다고 함. 오히려 접미사 배열을 많이 쓴다고 함.
4-3*. 접미사 배열(suffix array)
문자열의 맥가이버 칼이라 불리며, 다양한 문자열 문제에 적용이 가능하다.
문자열 S의 모든 접미사를 사전순으로 정렬한다(그림 4).
 | |
|
코드
//두 접미사 시작 위치 i,j가 주어질 때 두 접미사 중 어느 쪽이 앞에 와야 할지 비교한다.
struct SuffixComparator{
const string& s;
SuffixComparator(const string& s) : s(s) {}
bool operator () (int i, int j){
return strcmp(s.c_str() + i, s.c_str() + j ) < 0; //c_str()은 string 오브젝트의 포인터 반환 -> string을 char*로 변환할 때 사용
};
//s의 접미사 배열을 계산한다.
vector<int> getSuffixArrayNaive(const string& s){
vector<int> perm;
for(int i=0; i<s.size(); ++i) perm.push_back(i);
sort(perm.begin(), perm.end(), SuffixComparator(s));
return perm;
}
-생성하는데 걸리는 시간 복잡도: O(|n|^2*log|n|)
sort()의 시간 복잡도는 O(nlogn)이지만, 각 두 원소 비교가 O(n)만큼 걸리기 떄문이다.
하지만, 실제로는 모든 글자를 비교(O(n))하는 일은 거의 없기 때문에 더욱 빠르게 수행된다.
-접미사 배열 생성하기 (맨버-마이어스 알고리즘)
-> 시간 복잡도를 줄이기 위한 방법이다.
-> 다음에 공부해서 보충할 예정
-예제: 문자열 검색 (원 문자열 길이: H, 탐색 문자열 길이: N)
부분 문자열은 어떤 접미사의 접두사이다.
접미사 배열을 이진 탐색해서, 각 문자열이 출연하는 위치를 찾는다. O(log|H|)
각 문자열을 비교하는 데 걸리는 시간: O(|N|)
시간 복잡도: O(|N|log|H|)
Reference
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만, 인사이트
댓글
댓글 쓰기