CSC (압축)

CSC(Compressed Sparse Column, 압축된 희소 열 형식)은 희소 행렬을 저장할 때 열 중심(column‑oriented)으로 비제로(non‑zero) 원소를 압축하는 방식이다.

개념

CSC 방식은 비제로 원소들을 열 단위로 순서대로 저장하며, 각 열의 시작 위치를 나타내는 포인터 배열을 함께 유지한다. 구체적으로 세 개의 배열을 사용한다:

•  ‘data’ — 비제로 원소들의 값 배열
•  ‘indices’ — 해당 값들의 행 인덱스 배열
•  ‘indptr’ — 각 열이 시작되는 ‘data’ 배열 내 위치를 가리키는 포인터 배열

예컨대 열 j에 포함된 비제로 원소들은 data[indptr[j]:indptr[j+1]] 에 위치하며, 그에 대응되는 행 인덱스는 indices[indptr[j]:indptr[j+1]] 로 얻을 수 있다.

구성 요소

주요 구성 요소는 다음과 같다:

• data — 모든 비제로 원소의 값이 열 우선 순서(column‑major order)로 저장된 배열
• indices — 위 값들과 동일 순서로 각 값이 속한 행(row) 인덱스를 저장한 배열
• indptr — 열 별로 ‘data’와 ‘indices’ 내에서 해당 열이 시작하는 위치를 저장한 배열. 길이는 (열 수 + 1) 이고, 마지막 요소는 전체 비제로 개수이다.

특징 및 동작

• 열 중심 저장이기 때문에 열 슬라이싱(column slicing)이나 전치(transpose) 연산 등에 유리하다.
• 반대로 행 슬라이싱(row slicing)이나 동적 구조 변경(structure modification)에는 비효율적이다.
• 구현은 비교적 단순하고, 저장 메모리 면에서 희소 패턴에 따라 큰 이득을 준다.
• 일반적인 구축단계에서는 다른 형식(예: COO)으로 만든 뒤 CSC로 변환하는 방식이 많다.

장점

• 열 단위 접근(Column‑oriented)이 자주 발생하는 알고리즘(예: 선형대수 분해, 고유값 계산)에서 매우 효율적이다.
• 비제로 원소만 저장하므로 메모리 사용이 훨씬 적을 수 있다.
• 저장 구조가 단순하며 내부 구현이 널리 지원된다(예: SciPy의 csc_matrix).

단점

• 행을 중심으로 한 연산(row slicing, 행 우선 접근)이 많을 경우 성능이 떨어진다.
• 희소 구조(positions of non‑zeros)가 변경되는 경우(예: 원소 삽입, 삭제)에는 재구성이 필요해서 비용이 크다.
• 열 수보다 행 수가 월등히 많고 “행 중심(row‑wise)” 연산이 빈번한 경우에는 다른 형식이 적합할 수 있다.

응용 및 변환

• 과학컴퓨팅 라이브러리인 SciPy에서는 `csc_matrix` 클래스로 CSC 형식을 제공한다.
• “생성 또는 수정” 단계에서는 CO­­O 형식 등을 사용하고, “연산” 단계에서는 CSC 또는 CSR 형태로 변환해 사용한다.
• 다른 형식(예: CSR)과 상호변환이 가능하며, 상황에 따라 적절히 선택된다.

예시

다음은 3×3 희소 행렬을 CSC 형식으로 표현한 예이다:

행렬:   [ 0   0    1 ]   [ 4   0    0 ]   [ 0   0    3 ]

이 행렬을 CSC 형식으로 표현하면(열 우선) 다음과 같다:

• data = [4, 1, 3]
• indices = [1, 0, 2]
• indptr = [0, 1, 1, 3]

해석:

• 첫 번째 열(0번째 열)에는 비제로 원소 4가 있으며 행 인덱스 1 → data[0]=4, indices[0]=1
• 두 번째 열(1번째 열)에는 비제로 원소가 없으므로 indptr[1]=1, indptr[2]=1
• 세 번째 열(2번째 열)에는 비제로 원소 1(행0)과 3(행2)가 있으며 → data[1:3]=[1,3], indices[1:3]=[0,2]

코드 예시

다음은 Python의 SciPy 라이브러리를 사용하여 CSC 형식의 행렬을 생성하고 활용하는 예제이다:

import numpy as np
from scipy.sparse import csc_matrix

# 비제로 원소의 좌표와 값
row = np.array([0, 1, 2, 2, 0])
col = np.array([2, 0, 0, 1, 2])
data = np.array([3, 22, 7, 5, 1])

# CSC 형식으로 희소 행렬 생성
sparse_mat = csc_matrix((data, (row, col)), shape=(4, 4))

# 밀집 행렬(dense matrix)로 변환하여 출력
print(sparse_mat.toarray())

실행 결과 예:

[[ 0  0  3]
 [22  0  0]
 [ 7  5  1]
 [ 0  0  0]]

같이 보기

• CSR (압축)
• COO (압축)
• 희소 행렬 압축
• 텐서 압축

참고 문헌

• Kushwaha, Hemant. “Sparse matrix formats and efficient storage.” *International Journal of Computer Applications*, vol. 170, no. 8, pp. 24‑30, 2017.
• Saad, Y. *Iterative Methods for Sparse Linear Systems*. SIAM, 2003.