Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a sequence of motions from images and I need to store all these values. For example:

  • a) 1, 2, 3, 4, 3, 2, 1
  • b) 1, 2, 3, 2, 3, 4, 5, 4, 3, 2, 1

In order to save space, it would be necessary to have some function that could generate unique numbers to represent each of these sequences. But also, there is another problem: I need representations which could be compared, so, suppose I have

  • a) 1, 2, 3, 4, 4, 3, 2, 1
  • b) 1, 2, 3, 4, 3, 2, 1

The motion in a) is very similar to b), so I would need some way to represent similarity. There is two patterns for increment/decrement in these sequences, either by 1 or 0, or any other integer value.

I am starting to read about pairing functions and some other similar topics here but I am not sure if I can apply for this (like this topic).

share|improve this question
1  
I notice that in your examples, the differences are $1$, $0$, or $-1$. Is that always the case? Is the length of these sequences bounded? –  Lubin Apr 1 '12 at 23:46
    
Consider $1, 2, 3, 4, 4, 3, 2, 1.$ (resp. $1, 2, 3, 4, 3, 2, 1.$) You only need to know length $8$ (resp. $7.$) The sequences is $1, 2, \ldots, i-1, i, j, j-1, j-2,\ldots 2, 1.$ If length $= n$ is odd, then $i = 1 + \lfloor n/2 \rfloor$ and $j = i+1.$ If length $= n$ is even, then $i = j = n/2.$ Only store $n.$ –  user2468 Apr 1 '12 at 23:54
    
@Lubin Edited the question, thanks. –  IHawk Apr 1 '12 at 23:56
add comment

2 Answers 2

For a unique number to represent the sequence, you could consider a hash function. However, hash functions will give you ugly output that won't be readable and may not be easily reversible. It doesn't seem like that's what you're looking for. If you can't say for sure that your function will have integers, a hash table is a good way to do this. But, the hash values still won't be directly comparable in the way that you seem to want.

For the sequence 1, 2, 3, 4, 3, 2, 1, you could simply consider the unique number 1234321. This might depend on the range of your numbers - it would help/may only be reasonable if you can put some bound on the numbers in your sequence. (if you know all the numbers are integers between 0 and 9, this is fine - we can extend this to numbers between 0 and N (or a and a+N) by representing the sequence in base N+1). This may not save you any space, though - certainly not compared to a hash table.

If you know for sure that your terms will only go up and down by 0 or 1, you could represent them by the string $+++0−−0−$, for example, or equivalently as the number $22201101$ (where 2 is up, 1 is down). As an aside, this could be stored very efficiently by working in base 3. This seems like a good solution for you.

Similarity can be measured in several ways (e.g Hamming distance). In the case of your example, where you have a "deletion" (a 4 has disappeared), it seems sensible to consider the Levenshtein distance. Levenshtein distance applies to strings of text characters, really, but you can easily represent your sequence this way as described in the paragraph above.

It's difficult to understand exactly what you want without more context, but I hope this will help you to research what you need! Further comments welcomed.

share|improve this answer
add comment

If you have some upper bound $n$ on the length of the sequences, then you could store them using the Cantor pairing function as follows. Let $\langle x,y\rangle$ denote the output of the pairing function given $x,y$. Then let $$f(x_1,x_2,\ldots,x_k)=\langle \underset{n+1\text{ times}}{\cdots} \langle k,x_1\rangle,x_2\rangle\cdots,x_k\rangle,0\rangle,\cdots,0\rangle$$ which allows you to code for both the length of the sequence and its terms by iterating the standard pairing function until it has coded for all the information. However, if you don't have such an upper bound $n$, the only approach I know of is to let $$f(x_1,x_2,\ldots,x_k)=p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k}$$ where $p_i$ denotes the $i$th prime number. Obviously this is much less efficient.

share|improve this answer
    
Factoring is hard! –  user2468 Apr 2 '12 at 0:05
2  
I know, which is why I said "much less efficient". Side note: you should see some of the algorithms used in computability theory. It is not uncommon to see something along the lines of "Search over integers $n$. Factor each $n$, then factor each exponent, then factor each exponent of the result. Using [pre-determined map] interpret this as a program and run." –  Alex Becker Apr 2 '12 at 0:07
    
hi @AlexBecker, I need to ask you some questions that is off this topic, could you possible email me at v29vm2mc9@yahoo.com your email? –  Heijden Apr 2 '12 at 0:40
    
@Heijden That is what chat is for. –  Alex Becker Apr 2 '12 at 1:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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