0
$\begingroup$

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.

Non-answer feedback is welcome as comments on the question.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ This is very similar to Kolmogorov Complexity. $\endgroup$
    – Tom van der Zanden
    Commented Oct 2, 2015 at 13:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Oct 2, 2015 at 17:23
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Oct 2, 2015 at 17:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pseudonym ♦
    Commented Oct 3, 2015 at 8:58

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Haha, thanks. Actually hadn't considered the limits yet. There will be sentences that can't be reduced. For example, if the smallest value is 1 and input value is also 1 then the smallest equation will just be the value itself. My gut feeling is that for most inputs there will be significant reduction. Too early to make claims yet though :D $\endgroup$
    – gahrae
    Commented Oct 2, 2015 at 22:15
  • 1
    $\begingroup$ 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$. $\endgroup$
    – David Richerby
    Commented Oct 2, 2015 at 22:47
  • 2
    $\begingroup$ @gahrae Sure. And I'm pointing out that, for the great majority of numbers, you can't make any progress by this mechanism. For almost all numbers, there's no representation that's significantly shorter than just writing out the digits. All practical compression schemes use some property of the data being compressed: for example, English text has rules of spelling and grammar that mean you don't care about most strings; photographs have large areas of light and dark that look very different from random pixels, and so on. $\endgroup$
    – David Richerby
    Commented Oct 3, 2015 at 0:07
  • 2
    $\begingroup$ @gahrae it seems to me that you have trouble understanding that compression cannot yield anything on the average. Here is a question on that topic. $\endgroup$
    – john_leo
    Commented Oct 3, 2015 at 8:31
  • 1
    $\begingroup$ @john_leo That seems to be the issue, yes. I think the expectation mismatch is because, if you run a compression program on a file on your hard drive, it usually does manage to make it smaller. So it looks like compression really does work on average whereas, really, it's because files on hard drives are kinda special, in that they're not random. $\endgroup$
    – David Richerby
    Commented Oct 3, 2015 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.