A New Table Compression Method Based on STR Algorithm

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 ShortSTR2 and STR2 algorithm; compared with STRbit algorithm, the compression rate of STRO algorithm is bigger, and it can save more space and replace STRbit algorithm on time.