# Is this a new compression approach?

I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is.

The approach is to:

1. Convert the message to a number
2. Find the smallest equation to represent the number

The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value.

The process can be reversed by evaluating the equation, and then converting the number back into the message.

Step 1. is similar to base conversion but has the following numerical sequence...

Given an alphabet of "abc"...

Message, Value
a,       0
b,       1
c,       2
aa,      3
ab,      4
ab,      5
ba,      6
...


Value "aa" shows the difference between base conversation. In normal base conversion the value of "aa" would be 0 because "a" is the first letter of the alphabet and has a value of 0, so two of them would also be zero.

The value is really the permutation sequence number for when the alphabet is iterated over (or "bruteforced"). (Aside: Useful when distributing "bruteforce" problems.)

For step 2. I plan on using state space search to generate the equation. The goal state will be the smallest equation. The search will be performed by applying and accepting a single math operation on the "remaining" value. Initially, the "remaining" value will the original number. By the end of the search it will be reduced to zero.

• This is very similar to Kolmogorov Complexity. – Tom van der Zanden Oct 2 '15 at 13:14
• What specifically do you want to know? Questions asking "Has anyone come up with this idea before?" are not necessarily answerable, because it's not at all unlikely that someone has come up with it but never written it down (for obvious reasons, such as that it's not workable or useful in practice). Asking "Does it have a name?" seems strange and not exactly computer science. How are you going to use the answer? It seems like it'd be better to jump ahead to the next step and just ask whatever you really want to know -- e.g., is this a good idea, is it effective, whatever. – D.W. Oct 2 '15 at 17:23
• Anyway, what research have you done? You should look at Kolmogorov complexity and the following questions: cs.stackexchange.com/q/23010/755, cs.stackexchange.com/q/40684/755, cs.stackexchange.com/q/40239/755. – D.W. Oct 2 '15 at 17:23
• You need to be clear on what you mean by "smallest equation", or perhaps "smallest representation of an equation". Once you have the basics of Kolmogorov complexity, check out Solomonoff's universal probability distribution. – Pseudonym Oct 3 '15 at 8:58

"The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value." If that were true, your scheme would be able to compress every input by at least one bit. This is provably impossible by a simple counting argument (there are $2^n$ $n$-bit strings but only $2^n-1$ strings of length less than $n$), so your claim cannot be true.
• There can't be significant reduction for most inputs. The same counting argument says that, for example, you can't even compress half of the possible inputs by two bits: half the $n$-bit strings would be $2^{n-1}$ strings but there are only $2^{n-1}-1$ strings of length $n-2$ or less. And that's before you get onto the computational complexity of finding and solving these equations. Note that, for example, large chunks of cryptography are predicated on the difficulty of finding the unique integer solution to the very simple equation $pq=z$ that has $p,q>1$. – David Richerby Oct 2 '15 at 22:47