MP3-Beating Compression

http://www.youtube.com/watch?v=kfIMy-ebZRk

PROTOFROZENVOID

The future is now:
http://www.opus-codec.org/comparison/
http://en.wikipedia.org/wiki/Opus_%28audio_format%29#Quality_comparison_and_low_latency_performance
http://www.octasic.com/en/tech/opus_audio_codec.php
http://auphonic.com/blog/2012/09/26/opus-revolutionary-open-audio-codec-podcasts-and-internet-audio/

lol

MP3-Beating Compression
MIDI, MOD, IT, XM, ...

Kieren Johnstone
Looks like a real dude. Every once in a while some retard re-invents infinity compression again.

America even has a few patents on this: http://www.patentstorm.us/patents/5533051.html


Recently on Russian TV there was a story about undergrad student compressing blue-ray discs down to few kbs: http://engineerblog.ru/algoritm-arhivatsii-babushkina/

>>56
compressing blue-ray discs down to few kbs
Also known as "downloading a .torrent file".

I agree with the fact that you can create an infinite algorithm (ie, recursive) compression, but superfluous to some minimum limit. However, to completely agree with the fact that the author of a patent is not the order of the head when he said that "you can always compress any sequence of 2 bits up to 1!"

It is very similar to the invention of recursive compression - working ... However, the program runs very slowly. Compresses to a certain limit. And slowly - this is because currently work function blunt brute force because of what you have to wait a data compression (pre-modern as concise archiving software) by several dozen KB to 1-2KB already for weeks, even months! And all that is required for the super-fold increase in the efficiency of my program - so it's help in writing a long arithmetic modules as efficiently utilizing the resources of modern CPUs. If you wish to participate in this PROJECT - I do not need financial aid (at this stage) - that will appreciate such a module by writing a long arithmetic. I myself would be happy to pay for your work in case of success. To contact e-mail: wvanea@yahoo.com

frozenvoid's school of retards

It is mathematically impossible to create a program compressing without loss
*all* files by at least one bit (see below and also item 73 in part 2 of this
FAQ). Yet from time to time some people claim to have invented a new algorithm
for doing so. Such algorithms are claimed to compress random data and to be
applicable recursively, that is, applying the compressor to the compressed
output of the previous run, possibly multiple times. Fantastic compression
ratios of over 100:1 on random data are claimed to be actually obtained.

Such claims inevitably generate a lot of activity on comp.compression, which
can last for several months. Large bursts of activity were generated by WEB
Technologies and by Jules Gilbert. Premier Research Corporation (with a
compressor called MINC) made only a brief appearance but came back later with a
Web page at http://www.pacminc.com.  The Hyper Space method invented by David
C. James is another contender with a patent obtained in July 96. Another large
burst occured in Dec 97 and Jan 98: Matthew Burch <apoc@pipeline.com> applied
for a patent in Dec 97, but publicly admitted a few days later that his method
was flawed; he then posted several dozen messages in a few days about another
magic method based on primes, and again ended up admitting that his new method
was flawed. (Usually people disappear from comp.compression and appear again 6
months or a year later, rather than admitting their error.)

Other people have also claimed incredible compression ratios, but the programs
(OWS, WIC) were quickly shown to be fake (not compressing at all).

Compression doesn't have to be two way. There are a lot of algorithms, which compress data.  But there is no sensible inverse for these functions. These algorithms are not loss less.

Your function also hasn't a sensible inverse. The entropy in a mp3 file, the amount of redundant information, is not enough to compress it loss less in the amount of data you describe. Thus your algorithm is a one way compression function, which looses information.

With the amount of information you are storing (16 kilobytes), you can label all stars (~10^24) in 10^39432 universes. And we only have one universe. 

There are a lot of one way compression algorithms which perform much better than your retarded CAR algorithm. The "top" performers in this field can label all stars (and more) into 512 bits with almost zero change of collision. Even 256 bits are enough.

>>60
but it's almost trivial if you don't count storing the length of the original file..

well, you can represent -1 + 2^n sequences using all 2^1 ... 2^(n-1) sequences.. =)

then all you really need to do is find a good way to efficiently 'point' to where you want to start counting ^^

Compression works different on different entropy levels.
1.low entropy content like bitmaps compresses excellent.
2.high-entropy like 7zip files don't compress at all.
If there was a way to convert the high-entropy data into a low-entropy form, it would be possible to recursively compress data to some minimal block, but the information required to convert the low-entropy data to high-entropy data will also grow:
meaning even if such compression existed it would have a concrete limit depending on initial entropy.
I think there is potential to use some bit-reordering algorithms like http://en.wikipedia.org/wiki/Delta_encoding
example:
011101011010101110101110011010 can be encoded as difference between 2 bits(starting from initial(not in string) 0, with 1 as 'change' and 0 as 'no change') like:
010011110111111001111001010111 and again
011010001100000101000101111100 and again
010111001010000111100111000010 each time entropy of the string changes, the problem is finding the one with lower entropy.
now if we have a string of bits, and number of times to delta encode(or some other method) it to a slightly lower entropy form we can compress the results string to smaller size, and the process could be repeated again until the 'number of encode passes' metadata would grow to nullify any further compression.

>>65

This is what a burrows wheeler transformation does on a somewhat higher level.

some Bit reordering ideas >>65 :
00101110 each 2bit groups can be rotated to make
00011101 [12345678]->[21436587] or some arbitrary order like [12345678]->[84173265] for each and then rotated .
Another approach would be XORing with some short binary string(finding a random string which would lower entropy would be hard, especially if its larger than 4-5 bytes) crafted to decrease the entropy of majority of input.

>>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

>>67
>00101110 each 2bit groups can be rotated
Its equivalent to 1to1 character tables since it doesn't leave the boundary of a byte, and thus cannot change any entropy.
XORing with some short binary string
You have to find something that results in a lot of repeating zero or one but 'xoring short string' will only work for rare cases which are "close to the string" and in the rest will increase entropy.

>>65
What if the number of such delta encoding steps is in the trillions or more? the permutation space for a relatively large (e.g. 1MB) binary string grows at power of 2^nbits(string length~ 2^(8e6) for 1MB) and searching trillions of delta permutations to find one which has lower entropy would take years. Shorter strings have lower permutation spaces but they also have less chance to reduce entropy since the length of string for which entropy is lowered is substantially smaller(and for very short strings, insignificant).

>>70
Yeah, compressing a few bytes in short string is counter-productive but it serves a purpose of demonstrating the effect. example(we assume the metadata about number of steps is not counted as part of compressed output):
we have string
0101 and want to compress it with delta :
0111 this has 3 1's and single zero at start
0100
0110
0101 cycle ends with same number
Obviously some of these string are better for compression(theoretically), especially 0111.
now with 5 bits
11001 delta:
10101
11111 <--entropy reduced at step 3
10000
11000
10100
11110
10001
11001 cycle ends.

Dude, where's my "CAR"?
Right next to my "CDR"!

>>70
Wrong! The permutation space is only n for n bits(8 million for 1 MB file which can be easily checked on modern computer).

>>73
8 million permutations of delta encoded file will take
(assuming 1 billion ops/sec, 1mb file should be delta encoded in ~125k substitutions(with int delta tables) and ~125k jumps(to switch between zero/one tables) and checking entropy for each step would take a lot more, at least a few seconds.
Multiplying this by 8 million gives 16-32 millions of seconds which is 185-370 DAYS for all permutations of 1MB file.

>>55
This is a quicker link:
http://en.wikipedia.org/wiki/Module_file

But I completely agree. Just pointing which is the best lossy type. MIDI master race

>>57
Nah, any magnet link or distributed file in a mesh network.

>>58
Why we make deltas:
http://en.wikipedia.org/wiki/Delta_compression
We are making CTM @Freebsd. You are welcome to join us.

>>60
Wat?:
http://en.wikipedia.org/wiki/Lossless_compression
 --LZMA2

>>65
High five?

>>51-75
I am surprised that this thread was revived by >>51. But our points have been taken into consideration.

checked em >> 77

checkem

nikita is a cunt, and PHP rULEZ

>>77
checked. lol i know rite

>>78

lol :D I put my full fist in my sisters cunt xD

>>79
Ouch xD, I hope she's ok lol :D

>>71

That idea is implemented in:

>>68

Some of those cycle you mention have a shannon entropy of 0. Which is quite good from a compression perspective.

>>81

But on the average it performs not too great. It lowers on pseudo-random lists of 100 word32's on average the entropy with 0.11 and a mean deviation of 6.35*10^-2. Maybe on more structured data it performs better. I suspect it would, but have not test it.

If one adds somewhat more structure, it is heightened to 0.2. (Word32's between 0 255).

If you ISE PHP hyou cannot go wrong. Zend Framework has a standard code snippets, which you can use: http://www.zend.com//code/codex.php?ozid=954&single=1

You can download all the code snippets to enhance your zend experience. This is called modeular programming.

checked em with aryan pride! >>88

thank

you

>>85-san

>>71
Increasing state space might help with entropy.
The state space of transitions from byte to byte is 1 bit(from zero-initial to one-initial for 1bit comparisions). If you increase the state space to more bits it would be like this 2bit transition states.
examples:state [xx...] where x=1 signify that change  in that position occurs
00:to:00: state 00(no change)
00:to:01: state 01(rightbit change)
00:to:10: state 10(leftbit change)
00:to:11: state 11(twobit change)