5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One interesting things about your examples is that they are all in sorted order. If that's the case, encoding differences is a common technique. In fact, looking into inverted indexes might be worth a look. $\endgroup$ – Pseudonym Aug 4 '16 at 0:07
  • 4
    $\begingroup$ Are you trying to ask about compressability? $\endgroup$ – Mehrdad Aug 4 '16 at 0:39
  • $\begingroup$ @Merhdad, in a way, yes. But I'm not interested in actually reducing the size of the input, I just want to reduce the number of distinct values. $\endgroup$ – Jordy Dickinson Aug 4 '16 at 20:01
  • $\begingroup$ @Pseudonym, although my examples are in order, the input sequence need not be. However, I've added an additional restriction on the input sequence that may be relevant. $\endgroup$ – Jordy Dickinson Aug 4 '16 at 20:50
10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting idea, but that cannot work of any sequence given, just special cases. Otherwise, why would we struggle with compression? $\endgroup$ – antipattern Aug 4 '16 at 0:27
  • 5
    $\begingroup$ Actually it does work for any given sequence, though in the second example you need to know its length (this can be fixed). There's no connection to compression, though. $\endgroup$ – Yuval Filmus Aug 4 '16 at 4:59
  • $\begingroup$ @antipattern The reason this is not compression is that the output number is at least as big as all the input numbers. $\endgroup$ – user253751 Aug 4 '16 at 5:56
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ I don't really need the sequence of integers to be short, I just need the output to contain fewer distinct values. $\endgroup$ – Jordy Dickinson Aug 3 '16 at 22:43
  • $\begingroup$ Ah. Sorting the input will help, but there are cases in which there will be more values. { 1, 1, 1 }, for instance. Hrm... $\endgroup$ – minnmass Aug 3 '16 at 22:53
  • 2
    $\begingroup$ Sorting isn't valid, because this requires a reversible transform, and sorting is an operation that can't be undone (e.g., [1,2] and [2,1] will map to the same thing). $\endgroup$ – D.W. Aug 4 '16 at 5:38
  • $\begingroup$ @JordyDickinson, this solution meets all of the requirements you listed. With this solution, every input maps to an output that has only one distinct integer -- a great reduction in the number of distinct integers! So it's a perfectly valid solution according to the requirements you've listed in your question. If it additionally happens to produce a list that is shorter than the input, why is that a bad thing? If you have some objection to this answer then that suggests you have some additional requirement you haven't listed in the question. $\endgroup$ – D.W. Aug 4 '16 at 5:39
  • $\begingroup$ @D.W., you're right, it is perfectly valid. It won't work to solve my particular problem, but I'm having difficulty explaining why. In any case, I like the answers I've gotten so far, so I'd say my question as it is isn't too far off from what I'm really trying to ask. That said, I'll put some thought into how I could revise my question. $\endgroup$ – Jordy Dickinson Aug 4 '16 at 20:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The last paragraph is nice. The rest of the answer seems off-base, though. Your next-to-last paragraph is wrong; it is possible. I'd suggest deleting all but the last paragraph of this answer -- I think that would make this a better answer. $\endgroup$ – D.W. Aug 4 '16 at 5:41
  • $\begingroup$ @D.W. number of symbols mulitplied with the lenght is the information contained. If one tries to reduce either one without increasing the other, information is irretrievably lost, unless some domain specific knowledge is brought in. I'd appreciate if you substanciate that claim with a link. About that first part, it was written before OP overhauled his question, making it more clear what he was asking about. $\endgroup$ – antipattern Aug 15 '16 at 10:27
  • $\begingroup$ For substantiation: Take a look at the other answers. You say it's impossible; but some other answers show it is possible (they show how to do it). $\endgroup$ – D.W. Aug 15 '16 at 15:33
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @D.W. yes! I will edit to clarify. $\endgroup$ – Jordy Dickinson Aug 5 '16 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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