CSR (압축) 편집하기

CSR (Compressed Sparse Row, 압축 행 기준)은 희소 행렬을 저장하고 연산할 때 행 중심 접근을 빠르게 지원하는 압축 저장 방식이다.
==개념==
CSR은 행렬의 각 행(row)에 대해, 0이 아닌 원소(nonzero)들만 순차적으로 저장하고, 각 행이 시작하는 지점을 인덱스로 관리하는 방식이다.  이 방식은 행 접근(row slicing)이나 행 단위 연산(예: 행‑벡터 곱셈)에 효율적이다.
==구성 요소==
CSR 방식은 보통 다음 세 개의 1차원 배열을 사용하여 희소 행렬을 표현한다:
*'''values''' — 행렬의 0이 아닌 원소들의 값을 저장한 배열
*'''colIndex''' — 각 비제로 원소가 속한 열(column) 번호를 저장한 배열
*'''rowPtr''' — 각 행이 시작되는 위치를 나타내는 포인터 배열 (행 시작 인덱스)
rowPtr의 길이는 (행의 개수 + 1)이며, rowPtr[i]는 values 및 colIndex 배열 내에서 i번째 행의 첫 번째 비제로 원소가 저장된 인덱스를 가리킨다.  마지막 rowPtr[n]은 전체 비제로 원소 수, 즉 values 배열의 길이와 같다.
==동작 원리 및 접근==
행 i의 원소들을 순회하거나 접근할 때는 다음과 같은 방식으로 처리된다:
#시작 인덱스 = rowPtr[i]
#끝 인덱스 = rowPtr[i+1]
#values[k] 및 colIndex[k] (k = 시작 인덱스부터 끝 인덱스 − 1 까지)들을 통해:
##(i, colIndex[k]) 위치에 값 values[k] 존재
##나머지 위치는 0
==장점==
*행 중심 접근이 빠르다 — 행 벡터 곱(row-vector multiplication)에 유리하다
*메모리 절약 — 0 원소는 저장하지 않으므로 공간 효율성 증가
*행 범위 인덱싱(row slicing) 및 행 연산에 유리하다
==단점==
*열 방향 접근(column slicing)은 비효율적이다 — 열 인덱스를 직접 탐색해야 한다
*희소 구조 변경(예: 새로운 비제로 원소 삽입/삭제) 시 비용이 크다
*인덱스 배열 관리와 포인터 연산에 따른 오버헤드 존재
==응용 및 구현 사례==
*수치 해석, 선형 대수 계산, 그래프 인접 행렬 표현 등에서 널리 쓰인다
*Python의 SciPy 패키지에서 csr_matrix로 구현되어 있다
*CSR5 형식 등 고성능 개선 버전들이 연구되고 있다
==같이 보기==
*[[CSC (압축)]]
*[[희소 행렬 압축]]
*[[신경망 가지치기]]
*[[모델 압축]]
==참고 문헌==
*Wei, Y., Zhang, W., Li, Z., & Zhang, J. (2016). “Efficient Sparse Matrix-Vector Multiplication on GPUs using the CSR5 Format.”
*SciPy Documentation: scipy.sparse.csr_matrix
[[분류:데이터]]
[[분류:압축]]