희소행렬과 희소행렬의 자료구조 저장법

희소행렬

 

희소행렬(sparse matrix)은 행렬의 값이 대부분 0인 경우를 가리키는 표현이다. 그와 반대되는 표현으로는 밀집행렬(dense matrix), 조밀행렬이 사용된다. 개념적으로 희소성은 시스템들이 약하게 연결된 것에 해당한다. 한 줄로 나열된 공과 공이 스프링으로 양 옆으로 하나씩 연결되었을 때 이것은 희소 시스템이다. 그와 반대로 한 줄의 공들이 여러 방향의 공들과 스프링으로 연결되었을 때 이 시스템은 밀집 행렬이 될 수 있다. 희소의 개념은 조합론과 네트워크 이론 등과 같은 응용분야에서 유용하다.

 

희소행렬의 자료구조 저장법

Dictionary of keys

사전식 키(Dictionary of keys,DOK)방법은 행렬을 매핑된 연관 배열로 저장한다. 이때 키는 (행번호, 열번호)가 되며, 그에 대응하는 값은 행렬의 해당 값이 된다. 이때 행렬값이 0인 키는 저장하지 않는다.일반적으로이 형식으로 행렬을 구성한 다음 처리를 위해 보다 효율적인 다른 형식으로 변환하는것이 가능하다.

List of lists (LIL)

LIL(List of lists)은 링크드 리스트 알고리즘을 이용한 저장 기법으로 내용의 추가와 삭제가 용이하지만 CSR과 CSC에 비해 메모리가 낭비 되는 단점이 있다.

Coordinate list (COO)

좌표리스트(Coordinate list ,COO)는 COO는 (행, 열, 값)의 튜플 목록으로 저장된다. 이상적으로, 이러한 튜플목록의 항목들은 임의 액세스 시간을 향상시키기 위해 (행 색인 다음에 열 색인별로) 정렬될수있다. 이는 점진적 행렬 구성에 유용한 또 다른 형식이다.

Compressed sparse row (CSR or CRS)

가로의 순서대로 재정렬하는 방법으로 행에 관여하여 정리 압축한 것을 CSR이라고 한다.

예일포맷(Yale format)은 행 압축 희소행렬(Compressed sparse row ,CSR , CRS)의 인스턴스이다.

Compressed sparse column (CSC or CCS)

가로와 세로의 순서대로 재정렬하는 방법으로 행에 관여하여 정리한 것을 CSR 열에 관하여 정렬한 것을 CSC라고 이름한다. 저장 알고리즘은 동일한다. LIL에 비하여 메모리를 70%이상 줄일 수 있는 장점이 있고, 단점으로는 추가와 삭제가 용이 하지 않다.

 

---

좌측의 희소행렬을 우측의 compression행렬에 저장하기

 

  1) Compression행렬은 2차원 행렬로 보이지만 1차원 행렬로 표현해줄 수 있습니다.
     구조체 선언을 통해서요. 이때, Element는 Compression행렬의 한 요소가 됩니다.

 

2) 이제 SparseMatrix를 CompMatrix로 바꾸는 함수를 구현해보겠습니다.
  우선 아래는 타겟이 되는 행렬입니다.

 3) cnt변수에는 행렬에 0이 아닌 값의 갯수를 세어 담아줍니다.
   이후 CompMatrix를 cnt+1만큼 크기로 생성합니다.  
  +1 이 붙은 이유는 CompMatrix의 0번째 요소는 row, col, value에 대한 정보를 담기  때문입니다.

 4) Compress 함수
# 행렬들 이름이 길어서 그렇지, 한번 보시면 단순한 구조입니다.

  4-1) CompMatrix의 0번째 요소엔 SparseMatrix에 대한 정보를 담습니다.
  4-2) 이후 SparseMatrix의 요소를 탐색하며 0이 아닌 값이 나오면 CompMatrix에 저장해줍니다.

 

 

 

출처:

희소행렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

[C언어] Sparse matrix 희소행렬 : 네이버 블로그 (naver.com)