자료구조(2) : 배열(2, 完) - 희소 행렬, 문자열
희소 행렬(Sparse Matrices)
앞서 배열을 사용하는 예시를 계속 봤다. 고차원 배열의 대표적인 예시가 바로 행렬이다. 사실 행렬은 2차원 배열이라
그렇게 고차원은 아니지만, 그래도 다루었기 때문에 소개하도록 하겠다.
행렬은 선형대수학을 수강했다면 이미 아는 내용일 것이다.
a[m][n] 사이즈의 행렬이 있다고 하면,
- m : 행의 수
- n : 열의 수
- m x n : 전체 요소의 개수(기수라고도 부른다)
크게 세 개의 행렬에서의 주요 값들이 존재한다.
그림으로 보는 것이 더 직관적으로 이해하기 쉽다. 가로를 행, 세로를 열이라고 부르니 꼭 기억하자. 헷갈리면 큰일난다.
추가로 행렬에서 자주 쓰는 연산에 대해서 간단하게만 설명하면,
- 행렬 생성(Creation)
- 행렬 전치(Transpose) : 주대각선을 기준으로 대칭되는 위치에 있는 값을 바꾸는 것
- 행렬의 사칙연산(곱과 나눗셈은 스칼라값)
- 행렬 곱(Multiplication) : 기존에 알던 곱셈과 다른 연산이다.
이 중 우리는 전치와 행렬곱에 대해서 조금 더 자세히 알아볼 것이다.
그럼 이제 희소 행렬에 대해서 알아보면, 희소 행렬이란 우측처럼 0이 아닌 요소의 개수가 적을 때를 이야기한다.
num of nonzero elements / num of total elements 가 매우 작은 값이 되는 경우다.
배열에서 이는 공간이 매우 많이 낭비되는 상황이므로, 시공간적으로 효율을 따지려면 다른 방법이 필요하다.
가장 쉬운 방법은 0이 아닌 요소만 저장하는 것인데, 이를 표현하는 방법에 대해 알아보자.
Efficient Sparse Matrix Representation
기본적으로, 행렬의 한 요소는 {행, 열, 값} 세 개의 정보로 특정 가능하다.
그래서 우리는 MatrixTerm 이라는 새로운 클래스를 만들고, 이를 저장하는 행렬 클래스를 또 만들 것이다.
그리고, 일반적으로 저장은 행 오름차순으로 하되, 행의 위치가 같다면 열 오름차순으로 정렬하여 저장한다!
앞서 다항식을 할 때 하나의 항 자체를 클래스로 만들어서 표현한 것과 비슷한 방식이다.
이때 중요한 것은, 행렬 관련 연산을 끝내기 위해서는 행렬 자체에 대한 정보를 필수적으로 제공해야 한다는 점이다.
즉, 우리는 희소 행렬을 표현하기 위해 0이 아닌 요소만 저장하지만, 행렬 전체에 대한 정보(행, 열, 0이 아닌 요소 수) 또한
같이 저장해주어야 연산을 할 때 정상적으로 종료시킬 수 있다. ( for문의 반복 횟수 지정을 생각하면 된다. )
class SparseMatrix; // forward declaration
class MatrixTerm {
friend class SparseMatrix;
private:
int row, col, value;
};class SparseMatrix {
private:
int rows, cols, terms, capacity;
MatrixTerm *smArray;
}
두 클래스가 이런 식으로 구현된다. 위는 각 행렬에 들어갈 요소에 대한 클래스로, <row, col, value> 의 triple로 구성된다.
아래는 그런 요소들을 모아서 표현되는 희소 행렬 클래스로, 전체 행, 열, 요소 개수와 배열의 크기를 저장하며 동시에
0이 아닌 요소들을 모은 배열의 포인터를 갖는다.
만약, 행렬 연산 중 0이 아닌 요소의 수가 늘어나게 된다면, 그에 따라 capacity 또한 늘어나는 작업이 필요할 것이다.
행렬 전치(Transpose Stored as Triples)
이제 행렬을 구현할 수 있으니, 구현된 희소 행렬에서 전치 연산에 대해 알아보겠다.
우선 전치 연산은 행렬 각 요소의 행과 열의 위치를 바꾸는 것이다. (2, 3)에 있던 요소가 (3, 2)로 이동하는 식이다.
이런 연산을 우리가 앞서 정의한 희소 행렬 클래스를 통해서 어떻게 진행할 수 있을까?
우선 필기를 적어둔 전체 사진을 보며 이야기하겠다.
빨간색으로 필기된 부분은 가장 일반적인 행렬의 전치 방식이다.
단순히 행과 열의 값을 바꾸고, 이를 다시 정렬하는 방식으로 해당 방식은 전치 이후 직접 정렬을 해주어야한다.
그러나 우리가 알아볼 전치 알고리즘은, 굳이 따로 정렬하지 않고 전치 과정에서 정렬을 포함하는 방식이다.
각각의 경우에 대해 시간 복잡도와 장단점을 알아보자!
먼저, 정렬을 하지 않는다고 가정하면 희소 행렬 전치의 시간복잡도는 $O(terms * cols)$가 소요된다.
우리는 행렬에 0이 아닌 요소만 저장했기 때문에, rows가 아닌 terms가 시간복잡도에 들어가는 것이다.
각 열마다 모든 요소를 전치시키므로, 해당 시간복잡도가 나온다.
그러나 해당 방법은 원본을 유지하면서 진행하므로, 생각보다 메모리 공간이 많이 필요하게 된다.
위 방법은 최악의 경우에 $O(row * {cols}^2}$가 소요된다.
우리는 클래스를 희소 행렬인 경우에 대해 작성했는데, 만약 해당 클래스의 객체 행렬이 모두 0이 아닌 요소만 이루어지면
terms 가 rows * cols가 되어버리기 때문이다. 이러한 행렬을 dense matrix 라고 부른다. 밀집도가 높은 행렬이다.
따라서 책에서 제안되는 방식은 오직 희소 행렬에 대해서만 시간적으로 유효한 방법이다.
그렇다면 정석적인 방법은 어떨까? 정석적인 방법은 당연히 $O(rows * cols)$가 소요된다.
모든 요소에 대해 다 전치시켜주는 것이다.
for(int j=0; j<columns; j++) {
for(int i=0; i<rows; i++) {
b[j][i] = a[i][j];
}
}
위와 같이 간단하게 표현할 수 있다.
그런데 우리는 이 알고리즘보다 빠른 전치 방식을 알고 싶은 것이다!
그래서 위에 소개된 방식에서 더 개선된 희소 행렬 전치 알고리즘인 'FastTranspose'에 대해서 알아보겠다.
FastTranspose with Analysis
해당 방법에서는 전치를 시키기 전에 미리 요소들의 열의 값을 조사하여 전치 행렬에서의 row 범위를 지정한다.
만약 원본 행렬에서 열의 값이 0인 것이 3개라면, 전치 행렬에서도 미리 3개의 인덱스는 행의 값이 0인 범위로 지정해준다.
이런 식으로 진행해주면, 굳이 전치 후에 정렬을 할 필요가 없어진다. 순서를 통해서 알아보자.
- 먼저, 원본 행렬의 각 열마다 요소가 몇 개 있는지 확인한다. $O(terms)$
- 해당 정보를 바탕으로 전치 행렬의 행의 개수를 지정한다.
- 1~2번을 통해, 전치 행렬에서 각 값이 몇 개씩 있는지 쉽게 알 수 있다.(스타팅 포인트 설정에 용이) $O(Columns)$
- 이제 원본 행렬의 각 요소를 하나씩 전치 행렬의 알맞은 위치에 옮긴다. $O(terms)$
3번에서는, 설명은 알 수 있다고 했지만 사실 알고리즘은 전치 행렬의 행의 인덱스를 지정해주는 것이므로, 원본 행렬의
열의 개수만큼 시간이 소요된다.
따라서, 전체 시간복잡도는 $O(columns + terms)$가 소요된다. 기존의 방식보다 많이 줄어든 모습이다!
처음 볼때는 조금 난해한 알고리즘일 수 있어, 잘 살펴보는 것을 추천한다!
희소 행렬 곱(Multiplying sparse matrices)
이제 행렬의 주요 연산 중 하나인 행렬 곱에 대한 알고리즘도 희소 행렬을 기준으로 알아보자.
우선 그러려면 행렬 곱부터 알아야하는데, 이미 알 것이라 생각해 간단하게 이야기 하겠다.
a(m*n), b(n*p) 행렬이 있을 때, 각 행렬의 행과 열을 하나씩 집어 대응되는 위치끼리 곱한 후, 더하는 연산 방식이다.
위의 사진처럼, 같은 모양으로 표시된 각 행렬의 행과 열들이 대응되는 것이고, 요소끼리 곱한 후 더한 값이
결과 행렬의 각 위치(대응되었던 행과 열의 번호를 기준)에 들어간다. 간단히 수식으로 표현 시, $d_{ij} = \sum_{k=0}^{n-1}a_{ik}b_{kj}$ 이다.
따라서, 기본적인 행렬곱 알고리즘 또한 매우 간단하게 3중 for문으로 작성된다.
for(int i=0; i<a.rows; i++) {
for(int j=0; j<b.cols; j++) {
sum = 0;
for(int k=0; k<a.cols; k++) {
sum += (a[i][k] * b[k][j]);
}
c[i][j] = sum;
}
}
for문에서 사용되는 각 변수에 대해 잘 기억하자. 시간복잡도는 $O(a.rows * a.cols * b. cols)$가 소요된다.
그런데 우리는 요소의 개수가 적은 희소 행렬에 대해서 사용하려고 하므로, 다른 방식이 필요하다.
Multiply with Analysis
먼저, 희소 행렬에서 우리는 행을 기준으로 연산할 것이다. 그렇다면 한 행에 대해서 계산하는 방식을 알아야한다.
행렬 a의 r번 행의 원소 개수를 $t_r$ 라고 하면, 한 행에 대해 b의 모든 열을 조사하며 0이 아닌 요소와 연산해야한다.
즉, 한 행을 계산하는데에는 $O(b.cols * t_r + b.terms)$의 시간이 소요된다. 여기서 행을 r개 가지고 있다고 하면,
전체 시간복잡도는 $O(b.cols * a.terms + a.rows*b.terms)$가 되는 것이다. 단순히 r을 곱한 값이다!
그래서 일반적인 희소 행렬의 경우, 정석적인 행렬 곱 알고리즘보다 해당 알고리즘이 더 빠른 시간에 수행된다.
그러나 이 알고리즘도 dense matrix의 경우 더 느린 시간을 갖는다. 10 x 10 정방행렬 두 개를 곱한다고 해보자.
정석적인 방법으로 연산 횟수를 계산하면 $10^3 = 1000$이다. 이 방법이 위의 알고리즘에 사용된다면,
$a.terms = b.terms = 10*10 = 100$이므로, 전체는 2000번의 연산이 필요하게 된다. 더 느림을 알 수 있다!
따라서 희소 행렬 파트에서 배운 알고리즘들은, 모두 희소 행렬이어야만 빠른 알고리즘임을 인지하자.
문자열 추상 데이터 타입(String Abstract Data Type)
문자열도 배열로 표현할 수 있다. 각 글자(char)가 배열의 한 인덱스에 하나씩 들어가게끔 하면 된다.
배열 S가 있다면, $S = s_0, s_1, s_2 ...., s_{n-1}$ 이 된다. 여기서 n=0이면 공백이거나 null string 이라고 한다.
문자열로 가능한 연산들은 다음과 같다.
- 새로운 빈 문자열을 만들거나, 문자열을 읽어들이거나 출력하는 연산
- 두 문자열을 합치는 연산(concatenation), 문자열 복사, 문자열 비교
- 특정 문자열을 다른 문자열에 삽입, 특정 문자열을 삭제, 문자열에서 패턴 찾기 등이 있다.
우리는 여기서 패턴을 찾는 연산에 알아볼 것이다.
Function 'Find', 'Knuth-Morris-Pratt Algorithm'(KMP)
정석적인 방법으로, 두 개의 문자열 s와 pat이 있다고 해보자. 이때 pat은 s에서 찾을 패턴을 담는 문자열이다.
함수의 호출은 s.Find(pat)과 같은 형태로 호출하게 된다. 리턴 값은, 해당 패턴이 시작되는 인덱스 i 를 반환한다.
만약 pat 문자열이 비어있거나, s에서 해당 패턴을 찾지 못했다면 -1을 반환해준다.
편의를 위해 LengthP = pat의 길이, LengthS = s의 길이로 새로운 변수를 추가하고, 만약 패턴을 찾는 도중
s에서 남은 탐색 길이가 LengthP보다 작은 경우에는 고려할 필요가 없기 때문에 빠져나간다.
이런 정석적인 find 함수는 s의 각 글자에 대해 pat의 길이만큼 탐색하므로, $O(LengthS * LengthP)$가 소요된다.
그러나 탐색과정을 고치면 더 시간을 줄일 수 있는데, 그 방법이 바로 실패 함수를 활용한 KMP 알고리즘이다.
주어진 pat = 'a b c a b c a c a b'이고, $s= s_0, s_1, s_2 ...., s_{m-1}$라고 하자. 두 문자열의 비교 과정은 다음과 같다.
| s | a | b | ? | ? | ? | ? | ? | ? | ? |
| pat | a | b | c | a | b | c | a | c | a |
3번째 글자에서 미스매치가 발생했다고 가정해보자. 그런 경우 원래 find 함수라면 b로 한 칸 땡겨서 다시 확인해야겠지만,
우리가 봐도 한 칸 옮기는건 시간을 낭비하는 행동이라는 것을 알고 있다. 이런 낭비를 없애기 위해, 2번째 글자는 넘긴다.
이후 빨간색으로 칠한 해당 부분으로 pat을 옮겨 다시 패턴과 일치하는지 탐색하게 되는 것이다.
KMP의 기본적인 방식이 이런 식으로 진행되고 이때 몇 칸을 넘어갈지는 이후 알아볼 '실패 함수'에 의해 결정된다.
실패함수는 문자열의 접두부와 접미부가 얼마나 일치하는지에 따라 그 값이 정해진다.
위의 사진을 보면, j가 증가함에 따라 접두부와 접미부가 겹치는 글자 수만큼 실패함수 값이 저장됨을 알 수 있다.
예를 들어, f(6) = 3인데, 이는 'abcabca' 에서 접두 abca와 접미 abca가 같아서, 실패가 발생할 경우
해당 문자열의 3번 인덱스에 있는 값이 6번 위치로 와도 똑같이 일치하게 다시 비교할 수 있다는 이야기이다.
이런 방식을 사용하게 되면, 패턴을 찾을 때 일일히 원본 한 글자마다 탐색할 필요 없이, 건너 뛰며 탐색할 수 있다.
int String::FastFind(String pat) {
int posP = 0, posS = 0;
int LengthP = pat.length(), LengthS = length();
while((posP < LengthP) && (posS < LengthS)) {
if(pat.str[posP] == str[posS] { // 글자가 일치할 경우
posP++;
posS++;
}
else if(posP == 0) posS++;
else posP = pat.f[posP-1] + 1; // posP - 1 까지는 일치했으므로(실패함수 활용)
}
if(posP < LengthP) return -1;
else return posS - LengthP;
}
알고리즘을 간단하게 구현하면 다음과 같다. 실패 함수는 구현되어있다고 가정하고 사용되었다.
이렇게 알고리즘이 작동할 경우, 원본 문자열의 각 글자마다 탐색할 필요가 없어서 사실상 LengthS 만큼만 탐색한다.
따라서 KMP가 적용된 FastFind 알고리즘의 시간복잡도는 $O(LengthS)$가 소요된다. 이는 실패 함수를 안다는 가정이고,
실패 함수를 아직 값을 구하지 않은 경우에는 실패 함수 값을 구해주는 만큼의 시간이 소모된다.
실패 함수는 pat 문자열을 한 번 순회하며 값을 결정해주므로, $O(LengthP)$만큼의 시간이 소요된다.
따라서 전체 KMP 알고리즘의 시간복잡도는 $O(LengthP + LengthS)$라고 할 수 있겠다.
사실 여기서는 알고리즘 시간이 아니다보니, 실패 함수와 KMP의 원리에 대해 자세히 다루지는 않았다.
혹여나 해당 알고리즘에 관심이 있다면, 따로 서칭하는 것을 추천한다.
해당 내용을 마지막으로 배열에 대한 포스트는 끝이다.
이후 내용은 아마 스택, 혹은 리스트가 될 것 같다. 앞으로 굵직하고 중요한 자료구조들을 배우게 되니,
추가적으로 더 찾아가며 공부하는 것을 추천한다. 화이팅!