Article in PDF format, compression.pdf

A new compression and decompression algorithm for files and packets

James A. Riechel

November 30, 2007

Abstract:

A new algorithm for compressing and decompressing data is presented which is not computationally expensive, produces interesting partially encoded and non-encoded output, performs well on all types and different types of input, and which might be appropriate for the compression and decompression of files, as well as packets traveling across a network. The algorithm requires computation on the order of $O(n)$, where $n$ specifies the linear size of the input. We make a logical argument that the time complexity of both algorithms is $O(n)$, and empirical evidence supports running times of $O(n)$ for both the compression and the decompression algorithms. We consider the case of compressing and decompressing completely random data, using a random number generator which we will not describe. Both the compression and decompression algorithms require $O(n)$ time to compress and to decompress completely random data, and the output of the compression algorithm is not much larger than the completely random input.

Hosted by www.Geocities.ws