Is there a reversible transform that reduces the number of distinct values?

Question

The idea is to take a sequence like $\langle 1,2,3,4 \rangle$ and reduce it to something like $\langle 1,2,2,3 \rangle$, or something similar. The key point is that there are fewer distinct values $\{1,2,3\}$ vs $\{1,2,3,4\}$. In the case that the number of distinct values cannot be reduced, i.e. $\langle 0,0,0,0 \rangle$, it would output the same value $\langle 0,0,0,0 \rangle$. An algorithm that doesn't always decrease the number of distinct values is ok, as long as it doesn't increase the number of distinct values, or as long as it does so only rarely. The output sequence length can be less than or equal to the input sequence length, and the input sequence is bounded by $[0,255]$, but the output sequence need not be, though they should be integers in the range $(-\infty,+\infty)$. Another restriction on the input, if it helps at all, is that it's a restricted growth string. A property of restricted growth strings that might be useful is that the first $0$ in the sequence always comes before the first $1$, the first $1$ before the first $2$, and so on. So a valid sequence might look something like $\langle 0,0,1,0,2,1,1,0,2 \rangle$.

As an example, consider this simple algorithm. First, construct a "dictionary" from the input sequence consisting of all distinct values in the input. So, for the input sequence $\langle 1,2,2,3 \rangle$, the dictionary would be $\langle 1,2,3 \rangle$. It then iterates over the input, doing two things: replacing the input value with its position in the dictionary, and rotating the dictionary left by one. For most inputs, this will do little to reduce the number of distinct values, but for the input sequence $\langle 1,2,3,4 \rangle$, it will output $\langle 0,0,0,0 \rangle$. This can be inverted by applying a similar algorithm. Starting with the same dictionary, iterate over the output, successively replacing the values in the output with the value in the dictionary at that output value's index (that is, if $D$ is our dictionary and $i$ is a value in our output sequence, replace that value with $D_i$) and then rotate the dictionary to the left by one.

Answer 1

There are many reversible transformations that take a list of (let's say) non-negative integers and output a single integer. Here are two examples: $$ 2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdot 7^{a_4} \cdot 11^{a_5} \cdots \\ \langle a_1, \langle a_2, \langle a_3, \ldots, \langle a_{n-1}, a_n \rangle \cdots \rangle, \quad \langle a,b \rangle = \binom{a+b+1}{2} + a. $$

Answer 2

What do you mean by "reduces the number of distinct values"?

• If you mean an invertible function whose input is, for example, $k$ things and whose output is fewer than $k$ things, the answer is yes. Yuval's answer gives two examples. Here's another example, which will make you laugh/cry/want to slap me/other (delete as applicable): the input is $k$ integers; the output is a list of those integers. There's just one list!

• If you mean an invertible function $f$ whose input ranges over some set $I$ and whose output ranges over some strictly smaller set $O$, then the answer is no. By the pigeonhole principle, there must be at least two distinct values $a,b\in I$ such that $f(a)=f(b)$, which means that the function cannot be invertible.

• If you mean something else, I'm gonna have to edit or delete this answer.

Answer 3

You're looking for a reversible function that takes a (long) list of integers in the range [0,255] and produces a very short list of integers in the range [-infinity, infinity]? Easy:

Add in base 255.

func(list)
  int result = 0
  for i = 0 => list.length
    result = (result * 256) + list[i]
  return result

... except that that loses leading 0s, so tweak the base and count inputs:

    result = (result * 256) + list[i] + 1

I mean, it's cheating, but func (a) will never produce more values than it was fed, and (b) can easily give you back the original list from the result. However, func will also (c) not work in the real world for any but the shortest of input lists.

If you want an actual list as the output, look for three or more duplicate values in a row; when you find one, output -1 * the count of identical values then a single copy of the value; eg:

{ 1, 2, 2, 3, 3, 3, 3, 4 } -> { 1, 2, 2, -4, 3, 4 }

(you can do "two or more" instead of "3 or more", but you don't save anything on pairs)

Answer 4

If I understand the problem correctly, your aim is to reduce the entropy of the source sequence, by reducing the number of possible symbols. Then the closest thing you could do is apply a compression algorithm of your choice (LZMA, ZIP et al.). Modern compression leaves you with the minimal number of symbols neccesary to represent the information stored in the sequence.

If "reversible" means reversible with losses, see below. There are methods of approxization which might yield even greater savings if you allow for lossy compression.

What it will do is actually reduce the count of distinct patterns/numbers to the minimum possible amount, while maintaining the information that these numbers carry. If you discard this information (As I understand you did when transforming <1, 2, 3, 4> to <1, 2, 2, 3>), you will never ever be capable of reversing your transformation, unless you "cheat" by having this information hardcoded into your algorithm.

One example would be Entropy encoding, specifically MQ Coding, which I fathom would be adaptable, with some modifications, to work on integer granularity. A word of warning if you plan to use this in a commercial setting: There are patents pending on this method.

If a loss of information is acceptable, then you might use simple binning, but that is not reversible.

For certain special cases, you might be able to fit a mathematical function to your values, so you do not even need to maintain any list at all, just a number of parameters to that function, but as said, this only works in special cases (such as {1, 2, 3,4} - A linear function).

A possible option for more complex functions would be an approximization via (multiple) gaussian functions. When bounding the stored information to the list size, this will not be lossless however. Keyword: Radial Basis Function

edit

After reading your comment, I guess im way off the problem. But the way you ask for it is not possible. If each of your symbols has a different meaning, there is no reversible way in which you can reduce the number of symbols without discarding information. Any method you chose will have to rely on your sequence having a certain structure and will not be applicable every possible sequence.

Kudos to @minnmass. Why not invert his idea. If the list size does not matter, why aren't you just looking at individual bits? Then you only have two different values - 0 and 1. That does not really decrease entropy and would be reversible - just consume a bunch (8, 16, 32, whatever) of bits at once and you are back to your original representation.

Answer 5

Here's an interesting approach, based on the fact that my input is always a restricted growth string. Given the sequence $\langle a_1, a_2, ..., a_n \rangle$, we know that $a_{i+1} \leq max(a_1,a_2,...,a_i)+1$. We can thus split our sequence into subsequences based on their greatest possible value. I.e., $\langle 0,1,0,1,1,2,1,0 \rangle$ would be split into $\langle 0 \rangle$, $\langle 1,0,1,1 \rangle$, and $\langle 2,1,1 \rangle$. The first sequence has a greatest possible value of $0$, the second of $1$, and the third of $2$. Since we know that each sequence will start with the greatest possible value, and may or may not contain lesser values, we may be able to reduce the number of distinct values by mapping each sequence to the range $[1,-\infty)$ by changing the first value in the sequence to $1$ and subtracting the max value in the sequence from the remaining values.

The rationale for this is that if the range of a given subsequence is $[n,m]$, if $n$ is close to $m$, then there will be overlap between the values in this sequence and the previous sequence. For example, the three sequences $\langle 2,1,2,1 \rangle$, $\langle 3,2,3 \rangle$, and $\langle 4,3,3,4 \rangle$, would be mapped to $\langle 1,-1,0,-1 \rangle$, $\langle 1,-1,0 \rangle$, and $\langle 1,-1,-1,0 \rangle$, reducing the distinct values from $\{1,2,3,4\}$ to $\{-1,0,1\}$. The reason for always starting with $1$ is so that when we combine these subsequences back into one sequence we will be able to distinguish between subsequences, and thus be able to reconstruct the original sequence.

In practice this doesn't reduce the number of distinct values by very much. Also, in the worst case scenario it will increase the number of distinct values slightly.