우리가 머신러닝, 딥러닝, 혹은 거대한 추천 시스템(예: 넷플릭스 영화 추천)을 구축할 때 마주하는 데이터는 흔히 거대한 2차원 표(행렬, Matrix) 형태로 다뤄집니다. 1,000만 명의 사용자가 10만 개의 영화에 남긴 평점 데이터를 행렬로 만든다고 상상해 보십시오. 무려 1조 개의 칸이 생깁니다. 그런데 여기서 치명적인 문제가 발생합니다. 대부분의 사용자는 기껏해야 수십 편의 영화만 보았을 뿐이므로, 1조 개의 칸 중 99.9%는 평점이 없는 '빈칸(0)'으로 채워집니다. 이처럼 대부분의 원소 값이 0인 행렬을 컴퓨터 공학에서는 '희소 행렬(Sparse Matrix)'이라고 부릅니다. 이 엄청난 양의 0을 2차원 배열에 그대로 저장하는 것은 메모리 공간의 끔찍한 낭비일 뿐만 아니라, 행렬 곱셈 등 연산 시간을 기하급수적으로 늘리는 주범이 됩니다. 오늘은 이 메모리 낭비를 극적으로 줄여주는 희소 행렬의 데이터 압축 기법을 완벽하게 해부해 보겠습니다.
1. 일반 2차원 배열의 치명적인 한계
행 크기가 $M$, 열 크기가 $N$인 2차원 배열을 메모리에 올리면, 컴퓨터는 데이터가 0이든 100이든 상관없이 무조건 $M \times N$ 개의 공간을 강제로 할당합니다.
예를 들어 10,000 $\times$ 10,000 크기의 정수형(4바이트) 배열을 선언하면 1억 개의 칸이 생기고, 약 400MB의 RAM을 단숨에 집어삼킵니다. 만약 의미 있는 데이터(0이 아닌 값)가 단 100개밖에 없다면, 나머지 99,999,900개의 0을 위해 메모리를 낭비하고 있는 셈입니다. 이러한 현상을 해결하기 위해 "0은 아예 저장하지 말고, 의미 있는 진짜 데이터만 골라서 그 위치와 함께 저장하자"는 발상의 전환이 탄생했습니다.
2. 희소 행렬의 압축 기법 (Data Compression)
2-1. 좌표 리스트 방식 (COO: Coordinate List Format)
가장 직관적이고 코딩 테스트에서도 흔히 쓰이는 압축 방식입니다. 0이 아닌 유효한 데이터가 발견될 때마다 그 데이터의 (행 인덱스, 열 인덱스, 실제 값) 이 세 가지 정보를 묶어서 1차원 리스트나 튜플 형태로 저장하는 것입니다.
// 일반 행렬: [[0, 0, 5], [9, 0, 0], [0, 0, 0]]
// COO 압축 변환 후:
Row : [0, 1]
Col : [2, 0]
Value: [5, 9]
의미 있는 데이터가 K개라면, 저장 공간은 O(3K)로 극적으로 줄어듭니다. 데이터를 새로 추가하거나 수정하기 매우 쉽다는 장점이 있지만, 행렬 연산(곱셈 등)을 빠르게 수행하기에는 다소 비효율적입니다.
2-2. 압축된 희소 행 (CSR: Compressed Sparse Row Format)
파이썬의 SciPy 패키지나 딥러닝 프레임워크 내부에서 희소 행렬을 메모리에 적재할 때 가장 널리 사용되는 최적화 포맷입니다. COO 방식에서 행(Row)의 인덱스 정보를 한 번 더 압축하여 극한의 효율을 뽑아냅니다. CSR은 단 3개의 1차원 배열로 거대 행렬을 압축합니다.
- Values 배열: 0이 아닌 실제 값들만 왼쪽 위에서 오른쪽 아래 순서대로 긁어모아 저장합니다.
- Column Indices 배열: Values 배열에 있는 각 값들이 원래 몇 번째 열(Column)에 위치했었는지 그 열 인덱스를 저장합니다.
- Row Pointers 배열 (핵심): 각 행(Row)에 의미 있는 데이터가 몇 개나 들어있는지, 누적합(Prefix Sum) 형태로 인덱스를 저장합니다. 이를 통해 각 행의 데이터가 Values 배열의 어디서부터 어디까지인지 단숨에 점프하여 찾아낼 수 있습니다.
CSR 구조는 행 방향으로 데이터를 쭉 훑으며 연산하는 행렬과 벡터의 곱셈(SpMV)에서 엄청난 캐시 히트율을 보여주어 연산 속도를 비약적으로 상승시킵니다. (열 방향 기준인 CSC 포맷도 존재합니다.)
3. 압축의 트레이드오프 (Trade-off)와 적용 기준
이처럼 희소 행렬 압축 포맷을 적용하면 400MB를 차지하던 데이터를 단 몇 KB 수준으로 압축할 수 있습니다. 하지만 이 방식에도 대가가 따릅니다.
- 랜덤 액세스(Random Access)의 붕괴: 일반 배열은
arr[5][7]처럼 즉시 O(1)로 값에 접근할 수 있지만, 압축된 구조에서는 5행 7열에 데이터가 존재하는지 확인하기 위해 인덱스 배열을 이진 탐색 등으로 뒤져야 하므로 조회 속도가 O(log K) 혹은 O(K)로 느려집니다. - 데이터 변경의 어려움: 중간에 0이었던 자리에 새로운 값을 넣게 되면, 메모리에 딱 맞게 압축된 배열들을 뒤로 다 밀어내야(Shift) 하므로 삽입/삭제 오버헤드가 매우 큽니다.
따라서 "데이터의 값이 빈번하게 변하지 않고, 전체 데이터를 한 번에 쭉 읽어 들이며 거대한 곱셈 연산을 수행해야 하는 머신러닝/그래프 연산" 환경에서 희소 행렬 압축 구조는 선택이 아닌 필수입니다.
1. 희소 행렬(Sparse Matrix)은 데이터의 대부분이 0으로 이루어진 행렬로, 일반 2차원 배열로 저장하면 극심한 메모리 낭비와 연산 지연을 초래합니다.
2. 의미 있는 데이터와 그 위치(행, 열)만 저장하는 COO 방식과, 행의 누적 인덱스를 활용해 극강으로 압축하는 CSR(Compressed Sparse Row) 포맷을 통해 메모리를 획기적으로 절약합니다.
3. 특정 위치 값(랜덤 액세스)을 즉시 조회하거나 수정하는 것은 느려지지만, 머신러닝이나 빅데이터 분야의 행렬 곱셈 최적화에서는 압도적인 퍼포먼스를 발휘합니다.