Lossless Set Compression by Binary Tree Coding

A set of categorical items is a common data structure used in various applications, such as customer orders in online shopping. With the rise of big data and e-commerce, there is an increasing need to store such a large number of set data efficiently. This paper presents a novel lossless compression method that uses binary trees for set compression. The compressed code is generated by performing a depth-first search for items in the set on the binary tree. We prove that finding the optimal tree for minimizing the total code length for a given collection of sets is NP-hard, and the problem even remains NP-hard when we only need to assign items to the leaf nodes of a given tree. A heuristic algorithm is then proposed for building trees. To further improve the compression efficiency, we incorporate the entropy coding method into the coding process. Moreover, we reveal the underlying probabilistic expression of the binary tree model and present the conditional independence structure of the model. To validate the effectiveness of the proposed method, empirical studies are conducted on two real-world online e-commerce datasets. The results show that the proposed coding method significantly reduces the storage space required for set data and the tree structure for compressing sets can help identify conditional independent items.