ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (12): 2734-2740.doi: 10.7544/issn1000-1239.2018.20170529

Previous Articles     Next Articles

A New Table Compression Method Based on STR Algorithm

Dong Aidi, Li Zhanshan, Yu Haihong   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
  • Online:2018-12-01

Abstract: 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.

Key words: constraint propagation, constraint programming, table constraint, table compression method, bit-wise operation, generalised arc consistent (GAC), simple tabular reduction (STR)

CLC Number: