圧縮行格納
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/05 07:50 UTC 版)
圧縮行格納（英: Compressed Row Storage, CRS）形式は行インデックス配列を圧縮する方式である。別名は Compressed Sparse Row（CSR）形式。 CSR方式ではまず2次元の行列を行方向に並べる。次に「存在しない値をゼロ要素とする」と定め、ゼロ要素をすべて削除する。この段階で行・列インデックスとともに並べると次のようになる。 data = [1 2 3 1 2 2 1] # 値IA = [1 1 1 2 3 3 4] # 行インデックスJA = [1 2 3 4 1 4 4] # 列インデックス ここで行インデックス配列（IA）に着目する。現在は各要素が明示的に行インデックスを持っているが、行の切れ目さえわかっていれば、これは自動的に導ける。例えば IA[1] = IA[2] = IA[3] = 1であるが、「1行目は1要素目から、2行目は4要素目から」とわかっていれば、IA[1:4]=[1 1 1]を即座に導ける。これはCSR方式が行ごとに並べたうえでゼロ要素を削除する規則に由来している。 この行インデックス表現は行headポインタの配列と見なせる。すなわちindptr = [ptr_row_1 ptr_row2 ...]である。インデックスを直接示す配列は列インデックス配列JAのみになったので、これをindicesと改名する。これにより得られる、 data = [1 2 3 1 2 2 1] # 値indices = [1 2 3 4 1 4 4] # 列インデックスindptr = [1 4 5 7] # 行Headポインタ が疎行列AのCSR形式による表現である。 CSR形式は行へのアクセスに優れている。1行目にアクセスする場合、データを data[indptr[1]:indptr[2]] で取得し列インデックスを indices[indptr[1]:indptr[2]] で取得できる（行インデックスは当然1）。対照的にCOO形式であればまず行インデックス配列IAを全長走査しIA[k] == 1に該当する要素番号kをリストアップし、そのうえでdata[k], indices[k]をによるアクセスを全kに関しておこなう必要がある。 対照的に、CSR形式は列へのアクセスに劣る。1列目にアクセスする場合、indicesを全長走査しindices[k] == 1に該当する要素番号kをリストアップしたのち、行インデックスを得るためにindptrを走査して各kに大してindptr[n] <= k <indptr[n+1]を満たすnを見つける必要がある。
※この「圧縮行格納」の解説は、「疎行列」の解説の一部です。
「圧縮行格納」を含む「疎行列」の記事については、「疎行列」の概要を参照ください。
- 圧縮行格納のページへのリンク
