稀疏矩阵的压缩存储

简介

 稀疏数组是为了减少大型数组中的无效数据对计算机存储空间的浪费。
复制代码

• 例子

 普通数组：
        0 0 0 0 0 0 0
        1 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 

对于这么一个五行七列的数组，其中大部分都是无效数据0，完整存储将造成存储空间的巨大浪费。

因此完全可以另外创建一个数组，使其只保存数组中的有效数据。这个数组一般是一个n行3列的数组。

例如上面数组压缩过后的三元数组为：
      5 7 3     //第一行数据保存的是，行数，列数，有效数据数（非0的数量）
      1 0 1     //第二行保存的是第一个有效数据在数组中的位置以及自身的值
      2 4 2     //第三行保存的是第二个有效数据在数组中的位置以及自身的值
      4 0 3     // 依次类推。。。第n行保存的是第n个有效数据在数组中的位置以及自身的值

复制代码

• 代码实现

public class SparseArray {

    //创建稀疏数组
    public int[][] createSparseArray(){

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

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

        System.out.println("------------原稀疏数组------------");
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }

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

    //稀疏数组转为三元数组进行数据存储,保存到磁盘上
    public int[][] transferToThreeArray(int[][] sparseArray) throws IOException {

        //获取行、列的值
        int rowLen = sparseArray.length;
        int colLen = sparseArray[0].length;

        //创建一个三元数组进行数据存储

        //step1：获取到稀疏数组的值的个数，对三元数组进行个数的确定
        int valueCount = 0;   //稀疏数组行个数 = valueCount + 1
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                if (anInt != 0){
                    valueCount ++;
                }
            }
        }

        // step2：三元数组的第一行的数据
        int[][] threeArray = new int[valueCount+1][3];
        threeArray[0][0] = rowLen;
        threeArray[0][1] = colLen;
        threeArray[0][2] = valueCount;

        //step2：遍历稀疏数组，确定有效值的位置，并存入三元数组
        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];

                }
            }
        }

        //三元数组
        System.out.println("------------三元数组------------");
        for (int[] ints : threeArray) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }
        System.out.println("------------------------------");

        //数组存储，NIO方式
        File file = new File("./threeArray.txt");

        FileOutputStream fileOutputStream = new FileOutputStream(file);

        FileChannel channel = fileOutputStream.getChannel();

        //为了更好的在文件中查看，使其转化为json字符串
        byte[] bytes = JSONObject.toJSONBytes(threeArray);

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


        return threeArray;
    }

    //三元数组转稀疏数组
    public int[][] transferToSparseArray(int[][] threeArray){

        //获取到稀疏数组的行、列数
        int rowLen = threeArray[0][0];
        int colLen = threeArray[0][1];

        //step1：创建稀疏数组
        int[][] sparseArray = new int[rowLen][colLen];


        //step2：遍历三元数组，将值赋给稀疏数组
        for (int i = 1; i < threeArray.length; i++) {
            sparseArray[threeArray[i][0]][threeArray[i][1]] = threeArray[i][2];
        }

        System.out.println("------------还原后的稀疏数组------------");
        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);

        new SparseArray().transferToSparseArray(threeArray);


    }


}
复制代码