一种基于STR算法的新表压缩方法

A New Table Compression Method Based on STR Algorithm

约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction,STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent,GAC)算法的运行速度.短支持方法是在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显.因此提出一种压缩约束表的新算法STRO(simple tabular reduction optimization),结合短支持压缩和位操作,在提高STR算法的运行速度的同时压缩表空间效果更好.实验结果表明:在约束表的平均大小不是特别小的情况下,STRO与ShortSTR2,STR2算法相比,速度更快、效率更高;与STRbit算法相比,在时间上可以替代STRbit算法,但STRO算法的表压缩率更大、更加节省空间.

Constraint propagation is one of the key methods of constraint programming,and it can be used for solving constraint satisfaction problems and also deal with industrial modeling issues.In recent years,simple tabular reduction(STR)algorithms have been frequently used in some constraint propagation algorithms to cut down the consumption of constraint table space,and at the same time increase running speed of the generalised arc consistent(GAC)algorithm.For the past few years,short support method was the most frequently used as a table compression method in constraint propagation algorithms.This method can propagate more constraints than original STR algorithms especially when the memory is small.But when the compression ratio is low,short support method improving the running speed effect is not obvious.In this paper,we present a new algorithm to compress constraint table,called simple tabular reduction optimization(STRO),combined short support compression method and bit-wise operation.STRO algorithm improves the running speed of STR algorithm,and at the same time,the compression of space effect is better.Experimental results show that when the average size of the table is not particularly small,STRO algorithm is faster and more efficient than ShortSTR2and STR2algorithm;compared with STRbit algorithm,the compression rate of STRO algorithm is bigger,and it can save more space and replace STRbit algorithm on time.