数据结构与算法：稀疏数组

前言

• 此文以整型元素的二维数组为例，阐述稀疏数组的思想。
• 其他类型或许有更适合压缩算法或者其他结构的稀疏数组，此文暂不扩展。

稀疏数组的定义

在一个二维数据数组里，由于大量的元素的值为同一个值，比如 0或者其他已知的默认值，在处理此类数据的数据的时候，为了某种目的(如节省存储空间)而将 0 值或默认剔除方式，使用一个新数组来组织的剩余数据（此文称为存储有效数据，简称有效数），此时将该新数组称为稀疏数组。

简而言之，存储原二维数组中有效数据信息的数组称为稀疏数组。

如下图中的 0 值是最多的元素，可以将 0 值视为要剔除储存的值，此文称为 剔除数。

此处是压缩思想在数组上的应用，稀疏数组一般用于数据的压缩存储，已达到节省空间的目的。

稀疏数组的结构

二维数据的元素是数值

稀疏数据一般为 N*3的矩阵，N 为非剔除数据的个数，行列式的第一行描述元素的结构信息，如行列数，有效数的个数；其他行描述有效数的具体信息，如所在原数组中的位置。

第一列	第二列	第三列
行号	列号	值

• 第1行，第1列为原始数据的行数
• 第1行，第2列为原始数据的列数
• 第1行，第3列为原始数据的有效数的个数 n ，这个决定了稀疏数组的行数N( N= n+1)

第1行（原数组结构信息）	18（原数组的行数）	18（原数组的列数）	68（原数组中有效数的个数）
第2行（原数组中元素的信息）	0（值所在的行）	0（值所在的列）	7（值为 7）

二维数据的元素是字符

稀疏数据一般为 N*3的矩阵，N 为非剔除数据的个数

• 第1行，第1列为原始数据的行数
• 第1行，第2列为原始数据的列数
• 第1行，第3列为原始数据的有效数的个数 n ，这个决定了稀疏数组的行数N( N= n+1)

稀疏数组的应用场景

1. 数据元素中存在相同值较多且需要存储的情况。
2. 网络数据传输的时候，可以根据传输的数据结构，采用稀疏数据的思想

总之，就是可以压缩存储或者压缩传输的时候，都可以考虑此稀疏思想。

案例

该案例演示了一个二维数组（业务数组）和与其匹配的稀疏数组（存储数组），仅为演示二者相互转换，未考虑转换中涉及到的算法优化，仅仅展示存储优化的设计思想。

• 原始数组大小为：18*18=324
• 稀疏数组大小为：68*3=204

转换后节省了 (324-204)/324*100%=37%的空间

package com.jj;import org.junit.jupiter.api.Test;public class TestAlgArray {@Testpublic void test() {int countRow = 18;int countCol = 18;int[][] arr = new int[countRow][countCol];for (int i = 0; i < countCol; i++) {arr[0][i] = 8;arr[7][i] = 5;arr[i][0] = 7;arr[i][7] = 3;}//输出int valueCount = 0;for (int i = 0; i < countCol; i++) {for (int j = 0; j < countCol; j++) {System.out.print(arr[i][j] + " ");if (arr[i][j] != 0) {valueCount++;}}System.out.println();}System.out.println("valueCount:" + valueCount);//生成一个稀疏数组int[][] saveData = new int[valueCount + 1][3];saveData[0][0] = countRow;saveData[0][1] = countCol;saveData[0][2] = valueCount;int index = 1;for (int i = 0; i < countCol; i++) {for (int j = 0; j < countCol; j++) {if (arr[i][j] != 0) {saveData[index][0] = i;saveData[index][1] = j;saveData[index][2] = arr[i][j];index++;}}}//输出 saveDatafor (int i = 0; i < saveData.length; i++) {for (int j = 0; j < saveData[i].length; j++) {System.out.print(saveData[i][j] + " ");}System.out.println();}//恢复业务数组int[][] newArr = new int[saveData[0][0]][saveData[0][1]];for (int i = 1; i < saveData.length; i++) {newArr[saveData[i][0]][saveData[i][1]] = saveData[i][2];}//输出业务数组for (int i = 0; i < newArr.length; i++) {for (int j = 0; j < newArr[i].length; j++) {
//                System.out.print(newArr[i][j] + " ");if (newArr[i][j] == 0) {System.out.print(" ");} else {System.out.print(newArr[i][j] + " ");}}System.out.println();}}
}

• 原始数组（业务数据）:18x18的矩阵

7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 5 5 5 5 5 5 3 5 5 5 5 5 5 5 5 5 5 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 

• 稀疏数组（存储数据）：68x3 的矩阵

18 18 68 
0 0 7 
0 1 8 
0 2 8 
0 3 8 
0 4 8 
0 5 8 
0 6 8 
0 7 8 
0 8 8 
0 9 8 
0 10 8 
0 11 8 
0 12 8 
0 13 8 
0 14 8 
0 15 8 
0 16 8 
0 17 8 
1 0 7 
1 7 3 
2 0 7 
2 7 3 
3 0 7 
3 7 3 
4 0 7 
4 7 3 
5 0 7 
5 7 3 
6 0 7 
6 7 3 
7 0 7 
7 1 5 
7 2 5 
7 3 5 
7 4 5 
7 5 5 
7 6 5 
7 7 3 
7 8 5 
7 9 5 
7 10 5 
7 11 5 
7 12 5 
7 13 5 
7 14 5 
7 15 5 
7 16 5 
7 17 5 
8 0 7 
8 7 3 
9 0 7 
9 7 3 
10 0 7 
10 7 3 
11 0 7 
11 7 3 
12 0 7 
12 7 3 
13 0 7 
13 7 3 
14 0 7 
14 7 3 
15 0 7 
15 7 3 
16 0 7 
16 7 3 
17 0 7 
17 7 3 

• 数据恢复

7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 5 5 5 5 5 5 3 5 5 5 5 5 5 5 5 5 5 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0