CSR (Compressed Sparse Row)（CSR: シーエスアール）

2025年10月21日

CSR (Compressed Sparse Row)（CSR: シーエスアール）

英語表記: CSR (Compressed Sparse Row)

概要

CSR (Compressed Sparse Row) は、データ構造の中でも特に「グラフ構造」をコンピュータ上で効率的に表現するための、非常に重要な表現方法の一つです。グラフ構造を扱う際、辺の接続情報を行列（隣接行列）として表現することが一般的ですが、グラフが大規模でかつ辺が少ない（疎である）場合、この行列の大部分はゼロで埋め尽くされてしまいます。CSRは、このような「疎行列（スパース行列）」から無駄なゼロ要素を徹底的に排除し、非ゼロ要素の値と位置情報のみを3つのシンプルな配列に圧縮して格納する手法なのです。これにより、メモリ使用量を劇的に削減し、大規模なグラフやネットワーク解析を高速に処理することが可能になります。

詳細解説

CSRがなぜデータ構造の「表現方法」として優れているのかを理解するには、まずグラフ構造と隣接行列の関係を把握する必要があります。

グラフ構造と疎行列の問題

私たちが扱うデータ構造の中でも、Webサイトのリンク関係、ソーシャルネットワークのつながり、有限要素法における物理シミュレーションなど、複雑な関係性を持つものは「グラフ構造」としてモデル化されます。このグラフをコンピュータで処理する際、どのノード（頂点）とどのノードが繋がっているかを記録するために「隣接行列（Adjacency Matrix）」がよく用いられます。これは $N \times N$ の正方行列で、ノード数が $N$ の場合、メモリには $N^2$ の領域が必要になります。

しかし、現実世界のグラフの多くは「疎（Sparse）」です。例えば、SNSのユーザーが数億人いたとしても、一人ひとりがフォローしている人数は全体のノード数に比べればごくわずかです。その結果、隣接行列のほとんどのエントリは「繋がりがない」ことを示すゼロで占められてしまいます。このゼロだらけの行列をそのままメモリに格納するのは、非常に非効率的で、メモリの浪費につながります。

CSRの仕組み：3つの配列による圧縮

CSRは、この疎行列の問題を解決するために考案されました。これは、無駄なゼロを無視し、非ゼロ要素の情報だけを以下の3つの配列（リスト）に分離して格納する表現方法です。このアイデアが非常に洗練されていて、私は感動します。

Value配列 (非ゼロ要素の値):
- 疎行列の中に存在する、ゼロではない実際の値（重みなど）を、行ごとに順番に並べたものです。これはグラフのエッジが持つ具体的な情報そのものですね。
Column Index配列 (列インデックス):
- Value配列の各要素が、元の行列の何列目に位置していたかを示すインデックス情報です。
Row Pointer配列 (行ポインター):
- これがCSRの肝となる部分です。これは、Value配列とColumn Index配列の中で、「新しい行がどこから始まるか」を示すインデックスを格納します。たとえば、Row Pointerの $i$ 番目の値は、元の行列の $i$ 行目の非ゼロ要素がValue配列のどこから始まるかを示します。

動作原理と効率性

CSRの動作原理は、このRow Pointer配列によって、特定の行に属する非ゼロ要素の範囲を瞬時に特定できる点にあります。

例えば、元の行列が100行あったとして、50行目の情報を取得したい場合を考えます。
Row Pointer配列の50番目の値を見れば、Value配列のどこから50行目のデータが始まっているかが分かります。そして、51番目の値を見れば、どこで50行目のデータが終わっているかが分かります。この「始まり」と「終わり」のインデックス情報さえあれば、必要なデータだけをピンポイントで読み出すことができるのです。

この仕組みにより、CSRは格納に必要なメモリ量を「非ゼロ要素の数に比例する量」にまで削減します。ノード数 $N$ が非常に大きく、非ゼロ要素の数 $NZ$ が $N^2$ より遥かに小さい場合、メモリ効率は劇的に向上します。これは、大規模なデータ構造（グラフ）を扱う現代の計算科学において、必須の表現方法となっているのです。

具体例・活用シーン

CSRは、特に大規模なシミュレーションやデータ解析の分野で大活躍しています。

活用シーン

大規模ネットワーク解析: ソーシャルグラフやWebグラフ（リンク構造）など、ノード数は膨大だが、一つ一つのノードの接続先は限られている（疎である）グラフの処理に用いられます。
数値計算（有限要素法など）: 物理現象をシミュレーションする際、生成される係数行列は非常に疎になることが多く、CSRはこれらの行列計算を効率化するために不可欠です。
機械学習: 特にグラフニューラルネットワーク（GNN）など、グラフ構造を扱うアルゴリズムの一部で、データの入出力形式としてCSRが採用されることがあります。

比喩：誰も借りない図書館の貸出記録

CSRの仕組みを理解するために、ある巨大な大学図書館の貸出記録を例に考えてみましょう。

この図書館には100万冊の本があり（ノード数 $N=100$ 万）、貸出記録は「どの本が」「何人目の学生に」貸し出されたかを行列で管理しているとします。しかし、実際によく借りられる本は全体の1%にも満たず、残りの99%の本は「誰も借りていない（値がゼロ）」という状態です。

隣接行列（非効率な表現方法）：
100万冊×100万人の巨大な表を作成し、誰も借りていない99%のマス目にひたすら「0」を書き込むようなものです。これは無駄ですよね。

CSR（効率的な表現方法）：
図書館の司書さんが「本当に必要な情報だけを抜き出してリスト化」することにしました。

Value配列: 実際に貸し出された本のタイトルや貸出回数（非ゼロの値）を、本の番号順に上から順番にリストアップします。
Column Index配列: その本を借りた学生のID（列インデックス）を、Value配列と対応させて記録します。
Row Pointer配列: ここがポイントです。このリストには、「1番目の棚の本の記録はリストの何行目から始まるか」「2番目の棚の本の記録はリストの何行目から始まるか」という「棚の区切り」だけを記録します。

もし「50番目の棚にある本の貸出状況を知りたい」となったら、司書さんはRow Pointerを見て「ああ、50番目の棚の記録は、メインリストの1,250行目から始まって、1,280行目で終わっていますよ」と瞬時に答えることができます。

このように、CSRは、膨大で無駄の多いデータ構造から、必要な情報へのアクセス経路（ポインター）と、その実データを分離することで、グラフ構造の表現を極限までスリム化しているのです。これは、大規模なデータ構造を扱う上で、本当に画期的な表現方法だと感じます。

資格試験向けチェックポイント

CSRは、特に基本情報技術者試験や応用情報技術者試験において、データ構造やアルゴリズムの分野で問われる可能性があります。グラフ構造の表現方法として、その効率性を他の手法と比較して理解しておくことが重要です。

疎行列（スパース行列）の概念:
- 「要素の大部分がゼロである行列」を指すことを理解してください。CSRは疎行列の効率的な格納法である、という基本定義が問われます。
隣接行列との比較:
- グラフ表現法として、隣接行列（$O(N^2)$ のメモリが必要）とCSR（$O(NZ)$、非ゼロ要素の数に比例）のメモリ効率の違いを把握しておきましょう。グラフが疎であるほど、CSRが有利であるという点が重要です。
3つの配列の役割:
- Value, Column Index, Row Pointerの各配列が具体的に何を格納し、どのような役割を果たしているかを理解しているかが出題されます。特にRow Pointerが「行の開始位置」を示すインデックスであることをしっかり覚えておきましょう。
- 例題として、小さな疎行列が与えられ、それをCSR形式で表現した際の3つの配列の内容を問う問題が典型的なパターンです。
分類上の位置づけ:
- この手法が、単なるデータ圧縮技術ではなく、「グラフ構造をコンピュータで扱うための表現方法」の一つであるという文脈を忘れないでください。隣接リストや隣接行列と並ぶ、重要な選択肢として認識しましょう。