6. 희소 행렬 추상 데이터 타입

in Study on Data Structure


dslogo

Overview

행과 열로 구성되는 수학의 행렬(matrix)은 여러 분야에 관한 문제를 푸는데 많이 이용되는 도구이다.

이 포스트에서는 이 행렬에서 동작하는 연산들이 효율적으로 수행될 수 있도록 하는 방법에 대해서 살펴본다.

일반적으로 행렬은 m개의 행과 n개의 열로 구성되는데, 이것을 m\(\times\)n(m by n)으로 표현하고 행렬의 차수(dimension)라 한다.

이 m\(\times\)n 행렬의 원소 수는 (m\(\times\)n)개가 된다.

만일 m과 n이 같으면 정방 행렬(square matrix)이라고 한다.

희소 행렬

다음 행렬 A는 3개의 행과 3개의 열로 된 3\(\times\)4 정방 행렬로서 9개의 원소를 가지고 있고, 행렬 B는 7개의 행과 6개의 열로 된 7\(\times\)6 행렬로서 42개의 원소를 가지고 있다.

A = \(\begin{pmatrix} 3 & 27 & -8 \\ 12 & 19 & 21 \\ -2 & 9 & 37 \end{pmatrix}\)

B = \(\begin{pmatrix} 76 & 0 & 0 & 0 & 13 & 0 \\ 0&0&0&0&0&0 \\ 0&0&0&0&0&3 \\ 0&25&0&0&0&0 \\ -19&0&0&56&0&0 \\ 0&0&0&0&0&13 \\ 0&0&3&0&0&0 \end{pmatrix}\)

행렬의 각 원소는 행과 열로 표현할 수 있기 때문에 m\(\times\)n 행렬 A를 2차원 배열 a[m, n]으로 표현하는 것이 아주 자연스럽다.

이렇게 되면 행렬의 각 원소는 a[i, j]로 표현하고 빠르게 접근할 수 있다.

위의 행렬 A, B를 각각 배열 a[], b[]로 표현하면 다음과 같다.

fig_4

그러나 무조건 이 행렬 크기와 똑같은 배열로 표현하는 데는 약간의 문제가 있을 수 있다.

예를 들어 위 그림의 행렬 B는 대부분 0을 원소 값으로 가지고 있어 배열 b의 원소 값도 대부분 0으로 채워져 있다.

이와 같이 전체 원소 수에 비하여 극소수의 원소만 0이 아닌 행렬을 희소 행렬(sparse matrix)이라 한다.

물론 이 희소 행렬을 구분하는 0의 비율이 명확하게 정해진 것은 아니지만 행렬 b 는 42개 원소중에 8개의 원소만 0이 아니기 때문에 분명히 희소 행렬이라 할 수 있다.

희소 행렬 추상 데이터 타입

희소 행렬은 대부분의 원소 값이 0이기 때문에 이들을 모두 그대로 저장하는 것은 데이터 공간의 낭비가 된다.

이를 대처할 수 있는 방법으로 0이 아닌 원소만 저장하는 방법을 생각할 수 있다.

하지만 이런 표현 방법을 고안하기 위해서는 먼저 희소 행렬에 적용할 수 있는 연산을 고려해 보아야 한다.

이 연산에는 최소한 희소 행렬의 덧셈(addition), 곱셈(multiplication), 전치(transpose)등이 포함된다.

다음 ADT는 이런 연산을 포함한 희소 행렬 추상 데이터 타입(sparse matrix abstract data type)을 기술한 것이다.

ADT Sparse_Matrix
데이터 : 3원소쌍 <i, j, v>의 집합.    i\(\in\)Row, j\(\in\)Column, v\(\in\)Value,
                Row={0, 1, …, m-1}, Column={0, 1, …, n-1}

연산 : a, b \(\in\) Sparse_Matrix; c\(\in\)Matrix; u, v, \(\in\) Value; i\(\in\)Row; j\(\in\)Column;
    spCreate(m,n) ::= return an empty sparse matrix with m\(\times\)n;
    spTranspose(a) ::= return c where c[j, i]=v when a[i, j]=v;
    spAdd(a,b) ::= if(a.dimension = b.dimension) then return c where
        c[i, j]=v+u when a[i, j]=v and b[i, j]=u
        else return error;
    spMuli(a,b) ::= if(a.no_of_cols=b.no_of_rows) then return c where
        c[i, j] = \(\sum_{k=0}^p (a[i,k] \cdot b[k,j])\), p=a.no_of_cols
        else return error;
End Sparse_Matrix

이제 이러한 연산을 구현하기 위해서는 희소 행렬의 표현 방법을 결정해야 한다.

행렬은 기본적으로 행과 열로 원소를 식별할 수 있기 때문에, 희소 행렬의 0이 아닌 원소들에 대한 <행, 열, 값>의 3원소 쌍을 열이 3인 2차원 배열로 표현하면 될 것이다.

이 때 3원소 쌍을 행 인덱스가 오름차순으로 되게 하고 같은 행 내에는 열 인덱스가 오름차순으로 저장 하면 연산을 더욱 효율적으로 수행할 수 있다.

희소 행렬의 연산을 수행하기 위해서는 이 0이 아닌 원소의 값과 함께 원래의 희소행렬의 행, 열, 0이 아닌 원소의 개수를 알아야 한다.

이 3가지 정보는 3원소 쌍 배열에 원소와 함께 저장할 수 있다.

다음 그림은 행렬 B를 배열 c[r, 3]으로 표현한 것이다.

여기서 r은 0이 아닌 원소수에 1을 더한 수, 즉 9가 된다.

그 이유는 배열의 첫 행은 희소 행렬의 정보를 저장하는데 사용하기 때문이다.

즉 c[0, 0]과 c[0, 1]은 각각 희소 행렬 B의 행수와 열수를 나타내고 c[0, 2]는 0이 아닌 원소 수를 나타내고 있으며 행 1에서 8까지는 0이 아닌 원소의 3원소 쌍 <행, 열, 값>을 나타내고 있다.

fig_5

희소 행렬의 전치

희소 행렬을 <행, 열, 값> 3원소 쌍으로 된 배열로 표현했을 때 먼저 이것을 전치시키는 연산에 대해 알아보자.

전치 행렬(transposed matrix)은 원소의 행과 열이 서로 교환된 행렬, 즉 원소 <i, j, v>가 <j, i, v>로 변환되어 만들어진 행렬이다.

만일 주어진 행렬이 일반 m\(\times\)n 행렬로서 단순히 a[m, n] 배열로 표현되었다면, 다음과 같은 간단한 방법으로 전치 행렬을 표현하는 배열 b[n, m]을 만들 수 있다.

이 방법에서는 배열 a[]를 열 별로 처리하는데 그 결과는 배열 b[]에 행별로 저장된다.

for(j = 0; j <= 0; j++) do
    for(i = 0; i <= m-1; i++) do
        b[j, i] = a[i, j];

이제 3원소 쌍 <i, j, v>으로 저장된 희소 행렬을 전치시켜 보자.

다음 그림은 위 행렬 c[9, 3]을 전치시켜 저장한 배열 d[]를 보여주고 있다.

이 예시에서 알 수 있는 것은 3원소 쌍 <행, 열, 값>으로 저장된 희소 행렬은 행 우선, 행 내에선 열 오름차순을 유지하고 있고, 전치된 희소 행렬도 독같이 행 우선, 행 내에서는 열 오름차순의 저장 특성을 유지하고 있다는 것이다.

이런 전치 행렬을 만들기 위해서는 주어진 행렬에서 각 열 별로 차례로 그 열에 속하는 모든 원소를 찾아 이들을 다시 행의 오름차순으로 전치 행렬에 저장하는 작업을 반복하여야 된다.

fig_6

이 방법에 따라 희소 행렬을 전치시키는 알고리즘을 설계해보면 다음과 같다.

transposeS(a[])  
    // 배열로 표현한 희소 행렬 a[t+1, 3]을 전치 희소 행렬 b[t+1, 3]으로 변환  
    m = a[0, 0];    // a[]의 행 수  
    n = a[0, 1];    // a[]의 열 수
    t = a[0, 2];    // a[]의 0이 아닌 원소 수
    b[0, 0] = n;    // b[]의 행 수 = a[]의 열 수
    b[0, 0] = m;    // b[]의 열 수 = a[]의 행 수
    b[0, 0] = t;    // b[]의 0이 아닌 원소 수
    if(t > 0) then {
        p = 1;                              // b[]에 대해 현재 행의 위치를 지시
        for(p = 0; p < n; p++) do {         // a[]의 열 별로 처리
            for(i = 1; i <= t; i++) do {    // 0이 아닌 원소 수에 대해
                if a[i, 1] == p then {      // 열 p의 원소 발견
                    b[p, 0] = a[i, 1];
                    b[p, 1] = a[i, 0];
                    b[p, 2] = a[i, 2];
                    p++;
                }
            }
        }
    }
    return b[];
end transposeS()

여기서 이 방법의 시간 복잡도를 살펴보자.

일반 m\(\times\)n 행렬에 대한 전치 알고리즘의 시간 복잡도는 중첩된 for 루프 때문에 \(O\)(m\(\times\)n)이 된다.

반면에 위 희소 행렬 전치 알고리즘 transposeS()는 두 개의 중첩 for 루프 때문에 \(O\)(n\(\times\)t)가 된다. : 여기서 t는 0이 아닌 원소 수

그러나 이 t는 최악의 경우 m\(\times\)n이 될 수 있으므로 \(O\)(n\(\times\)t)=\(O\)(m\(\times\)n\(^2\))가 되어 일반 m\(\times\)n 행렬을 이용하는 것 보다 더 나쁘게 된다.

따라서 효율적인 알고리즘을 만들기 위해 중첩 루프를 제거해야 한다.

이 루프를 제거하기 위해서는 배열 a[]의 각 원소들에 대해 배열 b[]에 저장시킬 정확한 위치를 알면 for 루프 하나를 제거할 수 있다.

이를 위해 다음 과정을 수행한다.

  1. 희소 행렬 전치 알고리즘에서 희소 행렬 A의 각 열에 대해 0이 아닌 원소수 계산 // 전치 행렬 B가 만들어 졌을 때 각 행의 0이 아닌 원소수를 계산하는 것과 같음
  2. 배열 a[]의 원소를 전치시켜 배열 b[]에 저장시킬 때 각 행의 시작점(인덱스)을 결정
  3. 배열 a[]의 원소를 처음부터 하나씩 차례로 그 열의 값에 따라 배열 b[]의 정확한 행의 위치로 저장시키면 \(O\)(n+t) 시간에 전치 가능

참고 문서

  • 이석호. (2004). 자료 구조와 JAVA. 정익사.



© 2019. by RaP0d

Powered by aiden