Permutation techniques in lossless compression
Ziya Arnavut · Lincoln (University of Nebraska) · 1996
Permutation techniques, such as ranking and Cayley permutations have been analyzed and used for dictionary and text compression. However, they have never been investigated or taken as a method for image compression. The topic of this dissertation was to investigate the use of permutation techniques primarily for image and secondarily for text compression. The cost per symbol of data transmission can be greatly reduced by first sorting and decorrelating the raw data by taking differences of consecutive elements prior to transmission. To recover the original data we also need to transmit one of the sorting permutations. However, it turns out that the communication of such a permutation, may cost more than merely transmitting the raw data itself. In this dissertation new techniques for data compression are introduced based on inversions, inversions on multiset permutations and inversion frequencies. Experimental results have shown that treating images as multiset permutations and applying inversions to them can create more compact data. Therefore, inversions on multiset permutations improve the ability of predictive techniques, such as JPEG. Furthermore, it is shown that when principal of locality holds in a data, inversion frequencies do as well as move-to-front coding, and often better.