MP3-Beating Compression

You probably don't believe me, but if you're at all interested in my new "CAR" compression alogrithm, check this out:

The strange thing is, it works better on compressed files!
Zipping an MP3 file gives you 99% of original, but check this out!

**** TESTS ON UNCOMPRESSED FILES ****

TXT File Example
TXT File: 1,318,671
Savings: 1,308,940
CAR File: 9,731
Percent: 0.7%

WAV File Example
WAV File: 8,362,354
Savings: 8,323,477
CAR File: 38,877
Percent: 0.5%

EXE File Example
EXE File: 216,064
Savings: 213,336
CAR File: 2,728
Percent: 1.3%


**** TESTS ON ALREADY-COMPRESSED FILES ****

MP3 File Example
MP3 File: 4,961,773
Savings: 4,945,669
CAR File: 16,104
Percent: 0.3%


MPG File Example
MPG File: 5,976,068
Savings: 5,946,909
CAR File: 29,159
Percent: 0.5%

If you didn't see it first time, I compressed an MP3 file from 5 meg to 16kb.
What CAR actually does is obviously a complete secret, but I'm really really excited about it! I've been thinking of how to do it for years - but now, yay! (I figured it out playing around in QB, of all things!).
What I want to know is basically are there any sites that are relatively easy to understand that tell you how to do:

* Huffman Compression
* LZW Compression
* "Textbook" RLE Compression (I only know PCX's RLE)

I know that you use binary trees and nodes and so on but I have no idea for a software implementation!
Anyways you probably don't believe me, but I just wanna try to make the compression better.

Thanks from a very very excited
Kieren Johnstone

>>67
This is a reasonable viable transformation, which seems to lower entropy, just propagate all prior values with xor to the next values. There is also an inverse of this operation:


{-# LANGUAGE ViewPatterns #-}
module Mod where

import Math.NumberTheory.Logarithms
import Data.Word
import Data.List 
import Data.Bits
import Test.QuickCheck

-- calculating shannon entropy


entropy :: Ord a => [a] -> Double
entropy s =
 sum . map lg' . fq' . map (fromIntegral.length) . group . sort $ s
  where lg' c = (c * ) . logBase 2 $ 1.0 / c
        fq' c = map (\x -> x / (sum c)) c

--
-- x1 x2 x3
-- y1 = x1 xor 0 
-- y2 = x1 xor x2
-- y3 = x1 xor x2 xor x3
--
-- Reverse operation
-- x3 = y3 `xor` y2 = x1 `xor` x2 `xor` x3 `xor` x1 `xor` x2
--             = (x1 `xor` x1) `xor` (x2 `xor` x2) `xor` x3
--                  = x3
-- etc

downwardMixin :: [Word32] -> [Word32]
downwardMixin xs = reverse $ worker (reverse xs)
    where worker  (x:y:xs) = let b = x `xor` y in b : worker (y:xs)
          worker [] = []
          worker  [x] = [x]

upwardMixin :: [Word32] -> [Word32]
upwardMixin xs = worker 0 xs
    where worker z (x:xs) = let b = x `xor` z in b : worker b xs
          worker z [] = [] 

-- calculating entropy of downward, id, upward 
calculateVariants :: [Word32] -> (Double,Double,Double)
calculateVariants xs = (entropy $ downwardMixin xs, entropy xs,  entropy $ upwardMixin xs)

-- downwardMixin . upwardMixin
prop_rev_upwardmixin = property test
    where test :: [Word32] -> Bool
          test x = 
            downwardMixin (upwardMixin x) == x

-- downwardMixin . upwardMixin
prop_rev_downwardmixin  = property test
    where test :: [Word32] -> Bool
          test x = upwardMixin (downwardMixin x) == x