疎行列の圧縮

以前の記事で「性癖ごとの組み合わせ」をCSV出力した。
テーブルで出力した、すなわち形式としては行列であり、なおかつ１作品内に添えられるタグは最高６つであるため、数が増えれば増えるほど0要素が増え、疎行列となる。
そして天地の狭間にある総てを欲するは人の業というものなので、疎行列は圧縮してしかるべきとなる。
今回は配列３つを使ったCSR方式で圧縮する。まずは実践の前に、サンプル行列を対象に試行する。

#include <stdio.h>
#include <string.h>

// Sparse Matrix size define
#define _SPROW_SIZE 4
#define _SPCOL_SIZE 5

// CSR用３配列
struct _csrData{
    int row[_SPROW_SIZE + 1]; // 縦軸
    int col[_SPROW_SIZE * _SPROW_SIZE]; // 横軸
    int val[_SPROW_SIZE * _SPROW_SIZE]; // 実際の要素
} typedef csrData;

void Dbg_ShowSomeVal(int*, int);
void Dbg_ShowMatrix(int*, int, int);
void Dbg_ShowCSRStruct(csrData*, int);
int CountNonZeroValues(int*, int);
int CreateCompactMatrix(int*, csrData*);

// メイン処理
void main()
{
    // CSR管理用構造体定義・アドレス獲得
    csrData csr;
    csrData *csr_p;
    csr_p = &csr;

    // ベースとなる疎行列
    int sparseMatrix[_SPROW_SIZE][_SPCOL_SIZE] =
    {
        {0 , 0 , 3 , 0 , 4},
        {0 , 0 , 5 , 7 , 0},
        {1 , 0 , 0 , 0 , 0},
        {0 , 2 , 6 , 0 , 0}
    };

    // 疎行列再現用エリア確保　ゼロクリアしておく
    int sparseMatrix_recon[_SPROW_SIZE][_SPCOL_SIZE];
    memset(sparseMatrix_recon, 0, sizeof(sparseMatrix_recon));

    // CSR管理構造体初期化
    memset(csr_p, 0, sizeof(csr));

    // 疎行列に対応するCSR情報取得
    int non0size = CreateCompactMatrix((int*)sparseMatrix, (csrData*)csr_p);

    // まずは元となる疎行列を二重ループで素直に表現
    printf("元々\n");
    Dbg_ShowMatrix((int*)sparseMatrix, _SPROW_SIZE, _SPCOL_SIZE);

    // 上で描いた疎行列に関するCSR情報表示
    Dbg_ShowCSRStruct((csrData*)csr_p, non0size);
    /*
    CSR
    ROW :  0  2  4  5  7  2  4
    COL :  2  4  2  3  0  1  2
    VAL :  3  4  5  7  1  2  6
    */

    // 最初はROWの 0 to (2-1)から得た値を使用し、COLの[0]to[1]へアクセス。
    // 再現対象の一行目の「２番目・４番目」には「３・４」の値が入っていることがわかる。
    // ROWの次は 2 to (4-1)の値を得て、COLの[2]to[3]へアクセス…　と繰り返すことで配列３つから二次元行列を再現が可能になる。

    // CSR要素から「どこに何が入るのか」を(x, y) = value形式で表示
    printf("復活(要素)\n");
    int v = 0;
    int r = 0;
    int loopCnt = 0;
    for( int i = 0; i < _SPROW_SIZE ; i++ )
    {
        for( int j = csr_p->row[i]; j <= csr_p->row[i+1]-1 ; j++ )
        {
            int c = csr_p->col[j];
            int v = csr_p->val[j];
            printf("(%2d, %2d) => %2d\n", r, c, v);

            // ついでに再現用行列の当該カラムに値をぶち込んでおく
            sparseMatrix_recon[r][c] = v;

            loopCnt++;
        }
        r++;
    }

    // 再現用行列を二重ループで描く。CSR情報のみで行列の再現が可能なことが判断できる。
    printf("復元(二次元)\n");
    Dbg_ShowMatrix((int*)sparseMatrix, _SPROW_SIZE, _SPCOL_SIZE);

    printf("\n");
    printf("Size spMat = %lu -> CSR =%lu, loopCount = %d\n", sizeof(sparseMatrix), sizeof(csr), loopCnt);
}

// 配列の中身を先頭から指定数表示する（Debug用）
void Dbg_ShowSomeVal(int *adr, int range)
{
    for( int i = 0; i < range ; i++ ) printf("%2d ", *(adr + i));
    printf("\n");
}

// 二次元配列の内容表示
void Dbg_ShowMatrix(int *topMtx, int rowLength, int colLength)
{
    int c = 0;
    for( int i = 0; i < rowLength ; i++ )
    {
        for( int j = 0; j < colLength ; j++ )
        {
            printf("%2d ", *(topMtx + c));
            c++;
        }
        printf("\n");
    }
}

// CSR処理用各配列内容表示
void Dbg_ShowCSRStruct(csrData *csr_p, int non0size)
{
    printf("CSR\n");
    printf("ROW : ");   Dbg_ShowSomeVal(csr_p->row, non0size);
    printf("COL : ");   Dbg_ShowSomeVal(csr_p->col, non0size);
    printf("VAL : ");   Dbg_ShowSomeVal(csr_p->val, non0size);
}

// 疎行列内の非0要素数を数え返却する。
int CountNonZeroValues(int *array, int length)
{
    int cntNonZ = 0;
    for( int i = 0; i < length ; i++ ) if(*(array + i) != 0) cntNonZ++;
    return cntNonZ;
}

// 疎行列からCSR用小配列を作成する。
// sparseMatrix = 入力:疎行列
// compactMatrix = 出力:CSR配列
int CreateCompactMatrix(int *sparseMatrix, csrData *csr)
{
    int *spMtx;
    spMtx = sparseMatrix;

    int size = CountNonZeroValues(spMtx, (_SPROW_SIZE * _SPCOL_SIZE));

    int k = 0;
    int c = 0;
    int tgtVal;
    for( int i = 0; i < _SPROW_SIZE ; i++ )
    {
        for( int j = 0; j < _SPCOL_SIZE ; j++ )
        {
            tgtVal = *(spMtx + c);
            if(tgtVal != 0)
            {
                csr->col[k] = j;
                csr->val[k] = tgtVal;
                k++;
            }
            c++;
        }
        csr->row[i + 1] = k;
    }
    return size;
}

サンプル用疎行列は以下を使用する。

\begin{pmatrix}
0 & 0 & 3 & 0 & 4 \\
0 & 0 & 5 & 7 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 2 & 6 & 0 & 0
\end{pmatrix}

これをCSRの３配列へ変換すると以下の値が得られる。

CSR各値

CSR
ROW :  0  2  4  5  7  2  4 
COL :  2  4  2  3  0  1  2 
VAL :  3  4  5  7  1  2  6

ROW[0] to ROW[1]-1, ROW[1] to ROW[2]-1, ROW[2] to ROW[3]-1, ROW[3] to ROW[4]-1の値に注目する。
各ROW値は0 to 1, 2 to 3, 4 to 4, 5 to 6になる。
これによりCOL[0:1], COL[2:3], COL[4:4], COL[5:6]の各値がそれぞれ0,1,2,3行目の値が存在する列を示していることがわかる。
今回のケースの場合、各COL値は2, 4, 2, 3, 0, 1, 2になる。
以上より、0行目の2, 4列目に値が存在、1行目の2, 3列目に値が存在……という情報が取れる。
具体的に入っているが値が何かはVAL[n]配列に左→右/上→下の順で格納しているので順にこの値を取ることで最終的に行列の再現が可能。
普通はこのまま行列計算に使用するが、あえて再び行列を再現すると入力の疎行列と一致する。

出力結果

元々
 0  0  3  0  4 
 0  0  5  7  0 
 1  0  0  0  0 
 0  2  6  0  0 
CSR
ROW :  0  2  4  5  7  2  4 
COL :  2  4  2  3  0  1  2 
VAL :  3  4  5  7  1  2  6 
復活(要素)
( 0,  2) =>  3
( 0,  4) =>  4
( 1,  2) =>  5
( 1,  3) =>  7
( 2,  0) =>  1
( 3,  1) =>  2
( 3,  2) =>  6
復元(二次元)
 0  0  3  0  4 
 0  0  5  7  0 
 1  0  0  0  0 
 0  2  6  0  0 

Size spMat = 80 -> CSR =148, loopCount = 7

次の課題

スクレイピングによる元データの取得が完了した。
pythonによるデータの行列化が完了した。
C言語による疎行列の圧縮方法は思い出した。
次はpython側からのC言語で記述した処理の呼び出しになるだろう。
確かCythonだっけ…
人によって何に悦びを見出すかは異なるだろうが、個人的には今回のように文脈の異なる技術の連携により欲する最終出力を得るプロセスが面白いところだと思う。
とはいえ環境設定はすぐにダレるので、python+Cのセットアップはできれば簡単に終わってほしい……

参考記事