Compressed storage of sparse matrices

Introduction to the

Sparse arrays are designed to reduce the waste of computer storage space by invalid data in large arrays.Copy the code

• example

Plain array: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 for such an array of five rows of seven columns, most of them are invalid data 0, the full will cause a huge waste of storage space. Therefore, it is perfectly possible to create a separate array that holds only valid data from the array. This array is typically an array of n rows and 3 columns. For example, if the array above is compressed, the triplet is: 5, 7, 3 // The first row stores the number of rows, number of columns, 1 0 1 // The second line stores the position of the first valid data in the array and its own value 2 4 2 // The third line stores the position of the second valid data in the array and its own value 4 0 3 // and so on... The NTH line holds the position of the NTH valid data in the array and its own valueCopy the code

• Code implementation

public class SparseArray {

    // Create a sparse array
    public int[][] createSparseArray(){

        int[][] sparseArray = new int[6] [7];

        sparseArray[1] [5] = 1;
        sparseArray[3] [2] = 2;

        System.out.println("------------ original sparse array ------------");
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }

        System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
        return sparseArray;
    }

    // Sparse arrays are converted to triples for data storage and saved to disk
    public int[][] transferToThreeArray(int[][] sparseArray) throws IOException {

        // Get the row and column values
        int rowLen = sparseArray.length;
        int colLen = sparseArray[0].length;

        // Create a triplet for data storage

        //step1: Obtain the number of values of the sparse array, and determine the number of the triplet
        int valueCount = 0;   // Number of sparse array rows = valueCount + 1
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                if(anInt ! =0){ valueCount ++; }}}// step2: The first row of the triplet
        int[][] threeArray = new int[valueCount+1] [3];
        threeArray[0] [0] = rowLen;
        threeArray[0] [1] = colLen;
        threeArray[0] [2] = valueCount;

        //step2: iterate through the sparse array, determine the position of valid values, and save the triplet
        int tempLen = 0;
        for (int i = 0; i < sparseArray.length; i++) {

            for (int i1 = 0; i1 < sparseArray[i].length; i1++) {
                if(sparseArray[i][i1] ! =0){
                    ++tempLen;
                    threeArray[tempLen][0] = i;
                    threeArray[tempLen][1] = i1;
                    threeArray[tempLen][2] = sparseArray[i][i1]; }}}// Triples
        System.out.println("------------ triplet ------------");
        for (int[] ints : threeArray) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }
        System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");

        // Array storage, NIO
        File file = new File("./threeArray.txt");

        FileOutputStream fileOutputStream = new FileOutputStream(file);

        FileChannel channel = fileOutputStream.getChannel();

        // Convert it to a JSON string for better viewing in the file
        byte[] bytes = JSONObject.toJSONBytes(threeArray);

        channel.write(ByteBuffer.wrap(bytes));


        return threeArray;
    }

    // Ternary to sparse array
    public int[][] transferToSparseArray(int[][] threeArray){

        // Obtain the number of rows and columns in the sparse array
        int rowLen = threeArray[0] [0];
        int colLen = threeArray[0] [1];

        //step1: Create a sparse array
        int[][] sparseArray = new int[rowLen][colLen];


        //step2: iterate over the triplet and assign the value to the sparse array
        for (int i = 1; i < threeArray.length; i++) {
            sparseArray[threeArray[i][0]][threeArray[i][1]] = threeArray[i][2];
        }

        System.out.println("------------ restored sparse array ------------");
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }
        System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --");
        return null;
    }

    public static void main(String[] args) throws IOException {
        int[][] sparseArray = new SparseArray().createSparseArray();

        int[][] threeArray = new SparseArray().transferToThreeArray(sparseArray);

        newSparseArray().transferToSparseArray(threeArray); }}Copy the code