多维对称空间的压缩存储及其应用研究

发布时间：2019-01-12 14:12

【摘要】：自然界中到处都存在着对称性，对于具有对称性的信息，在存储时可根据它的特征进行压缩存储。比如，如果平面图形在二维坐标系中是对称的，则可以只存储一半（不考虑对角线）的信息就可以表示出这个图形，即可以存储为一个上（或下）三角矩阵。类似的如果三维坐标系是对称的，就可以只存储1/6（不考虑对角线）的信息，至于怎么存储却并不像二维对称那样简单。在现实世界中，我们能够观察到的也就是三维，加上时间也才四维，但是在很多领域，经常需要处理三维及三维以上的信息，，有时候这些多维信息，在维与维之间存在着对称性。如果能够像上（下）三角矩阵剥离二维对称一样去剥离多维信息中的对称性，将可以极大地减少信息量，进而降低存储空间和处理时间。本文针对上述问题，如果“多维空间”各维间具有对称性，则其冗余程度是非常大的，较为系统的介绍了消除其冗余性的方法，即称为“多维对称空间压缩存储”的方法，并且设计了“遍历多维对称空间正对角面”的几种高效的方法。首先，比较详细的分析了“多维空间”的对称性，通过坐标映射的方式设计了多维对称空间的压缩存储方法；然后分别设计了针对规整对称空间正对角面，规整对称空间，非对称空间，非规整对称空间的压缩存储方法；最后，还设计了“规整对称空间正对角面遍历”的方法。此外，本文还将所设计的“多维对称空间的压缩存储方法”应用在小规模的多目标0-1背包问题中，并经过实验验证了它的正确性与有效性。实验结果表明，所设计的压缩存储方法是很有效的。所设计的“多维对称空间的压缩存储方法”是一个非常有用的算法工具，可以极大的减少某些特定问题的内存需要，进而大大减少时间耗费。
[Abstract]:Symmetry exists everywhere in nature. Information with symmetry can be compressed and stored according to its characteristics. For example, if a plane graph is symmetric in a two-dimensional coordinate system, it can be represented by only half of the information (not taking into account diagonals), that is, it can be stored as an upper (or lower) triangular matrix. Similarly, if the 3D coordinate system is symmetric, it can store only 1 / 6 of the information (without considering the diagonal), but how to store it is not as simple as the two-dimensional symmetry. In the real world, what we can observe is three dimensions, plus four dimensions of time, but in many areas, we often have to deal with three dimensional and more information, sometimes this multidimensional information. There is symmetry between dimension and dimension. If the symmetry in multidimensional information can be stripped off like the upper (lower) triangular matrix, the amount of information can be greatly reduced, and the storage space and processing time will be reduced. In order to solve the above problems, if there is symmetry among the dimensions of "multidimensional space", the degree of redundancy is very large. This paper systematically introduces the method of eliminating the redundancy, that is, the method of "multidimensional symmetric space compression storage". Several efficient methods of ergodic positive diagonal plane in multidimensional symmetric space are designed. Firstly, the symmetry of multidimensional space is analyzed in detail, and the compression storage method of multidimensional symmetric space is designed by coordinate mapping. Then, the compression storage methods for regular symmetric space, regular symmetric space and irregular symmetric space are designed, respectively, and the method of "regular symmetric space traversing positive diagonal plane" is also designed. In addition, the "compressed storage method of multidimensional symmetric space" is applied to the small scale multi-objective 0-1 knapsack problem, and its correctness and validity are verified by experiments. Experimental results show that the designed compression storage method is very effective. The "compressed storage method of multidimensional symmetric space" is a very useful algorithm tool, which can greatly reduce the memory needs of some specific problems, and thus greatly reduce the time consumption.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP333

【参考文献】