Author: Andrew Gyakobo

This project mainly aims to utilize a sparse matrix as form of matrix or image value compression by basically implementing a special kind of data structure where it omits one continuously recurring value ultimately saving space only for the "important" variables.

$ sudo gcc -ansi -Wpedantic -Wextra -Wall main.c -o exe

Giving a sample matrix of numbers:

We immediately notice the overwhelming issue with this matrix that it has too many 0's which don't necessarilly need to use up space hence they could just be left out.

The Sparse Matrix's compression rate fully depends on the rate of the recurrent value is being omitted.

1. As the program scans the txt file row by row each non-omitted number is subsequently stored in a sample "node" in a struct called Element. Each essential value is then saved in the value integer in struct Element. The code snippet is as follows:

struct Element {
    int value;
    int row;
    int column;
    struct Element * rowElement; // Pointer to next row Element
    struct Element * colElement; // Pointer to next column Element
};

2. Afterwards, after the struct Element object is created, alongside it two more concomitant objects are created as well. Here this is where we'd have to utilize pointers and a little bit of our imagination. Using void* malloc we allocate space for (basically create) two struct Header structs, each of which would be pointing to both the aforementioned created element and the next struct Header element. If you haven't noticed already we're creating a table of sorts with specific column and row objects pointing to said element objects. The struct Header objects would also connect to each other using once again pointers struct Header * header;

struct Header {
    int index;
    struct Header * header;
    struct Element * element;
};

3. The entire structure can then be saved by just having two pointers to the column and row headers:

struct Header * headRowHeader;
struct Header * headColHeader;

The headers in their place would contain the said element structure. We could also add other elements to the struct Matrix like number of rows, columns, and the arbitrary recurrent value that would be omitted.

struct Matrix {
    struct Header * headRowHeader;
    struct Header * headColHeader;

    int rows;
    int cols;
    int fillValue;
};

To hearken back to the matrix back in our introduction:

This is a visual representation of how our data structure would ultimately look like:

When it comes to compression rates let's test the program out on the following data:

main.c would then output the following snippet:

index: 1
val: 1
val: 1

index: 2
val: 1
val: 1

==========================

index: 1
val: 1
val: 1

index: 2
val: 1
val: 1


Size of sparse mtrx: 96
Size of simpler mtrx: 8

As we can see from the displayed sizes of the sparse matrix and just a normal array the array is uses 16 bytes and the sparse matrix utilizes 96 bytes. You might immediately mention that the sparse matrix data structure is not efficient with this example and you'd be definitely right. Let's however take another example into consideration. Below is practically the same data table but skewed to the right:

In this case we get the following sizes. As you can see the sparse matrix remains unscaved in its size 96 bytes, however, the array only increments with every new number. Current array size: 32 bytes.

Size of sparse mtrx: 96
Size of simpler mtrx: 32

Such behaviour would be encountered repeatedly until the size of the said examined data structure would surpass the array itself.

Here are a list of examples proving the previous point:

Size of sparse mtrx: 96
Size of simpler mtrx: 48

Size of sparse mtrx: 96
Size of simpler mtrx: 64

MIT