1
$\begingroup$

S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]

I want to encode / decode natural numbers with the following scheme:

Encoding N: For natural number N return the binary string with index N in S: Code(N)=S[N]

Decoding Code: Return the index of the binary string Code in S: Decode(11)=5

Can you please suggest the name of this encoding and how to implement it?

Example of Numbers and Codes:

Number | Code
0  | 0
1  | 1
2  | 00
3  | 01
4  | 10
5  | 11
6  | 000
7  | 001
8  | 010
9  | 011
10 | 100
11 | 101
12 | 110
13 | 111
$\endgroup$
7
  • 3
    $\begingroup$ In you example, Decode(11) equals 5, not 4. $\endgroup$
    – Nathaniel
    Mar 29 at 17:46
  • $\begingroup$ Apparently the name of the encoding is Shortlex order. Apparently it is not an encoding but a sorting order. The naive algorithm would be to generate an array from 0 to N then sort using shortlex order then index into that array. Note that I disagree with your example as I would ignore the leading zeros. To me 1 and 01 and 00001 are exactly the same number. $\endgroup$
    – slebetman
    Mar 30 at 1:54
  • $\begingroup$ @slebetman They're not binary numbers, they're encodings of binary numbers. There's nothing to disagree with. OP is asking what to call this encoding, and you're complaining and saying "you shouldn't encode things that way". OP has explicitly defined 01 and 00001 not to be the same. So, if you're just ignoring the leading zeros, you're decoding it incorrectly because you didn't follow the spec. $\endgroup$ Mar 30 at 23:50
  • $\begingroup$ @Shufflepants The OP didn't define 01 and 00001 to not be the same number. There is nothing wrong with suggesting to the OP that he may be looking at his problem wrong $\endgroup$
    – slebetman
    Mar 31 at 1:57
  • $\begingroup$ @slebetman Yes, they did. The chart clearly has 1 = 1, 3 = 01, 7 = 001. You say "01 and 00001 are exactly same number" but they aren't numbers, they're encodings as is clearly laid out in the chart with one column for "number" and one column for "code". Would you still be trying to argue they were the same number if OP chose different symbols and used the encoding: 0 = X, 1 = G, 2 = XX, 3 = XG...? The codes themselves should be interpreted more as a string than as numbers. $\endgroup$ Mar 31 at 20:30

4 Answers 4

8
$\begingroup$

Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes.

Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove the MSB to get your encoding. In the other direction, add a leading one, and subtract $2$.

If you also allow the empty string, and you are only interested in encoding integers $n \geq 1$, then there is no need to add or subtract $2$ in the above recipe.

$\endgroup$
2
$\begingroup$

That's essentially bijective base 2. The only differences are that the set of digits used is $\{0, 1\}$ instead of $\{1, 2\}$, and that in the sequence of codes, the empty string is skipped.

As others have already suggested, you can encode a number by adding 2, writing it in binary, and removing the leading 1; and you can decode a number by adding a leading 1, decoding the result as binary, and then subtracting 2.

$\endgroup$
1
$\begingroup$

I don't know the name of this encoding, but notice that with $k$ digits you'll be able to encode exactly $2^k$ numbers. In particular, those starting from: $ \sum_{i=1}^{k-1} 2^i =2^{k}-2. $

It follows that, given an integer $n$, the number of digits of the encoding can be found as the largest value of $k$ such that $2^k \le n+2$, i.e., $k=\lfloor \log_2 (n+2) \rfloor$. Notice that $k$ is exactly one less than the number of digits needed to write $n+2$ in binary, so you can find it in time $O(\log n)$.

Then, you can also write down the actual digits in time $O(k)=O(\log n)$ by looking at the binary representation of $n-(2^k-2) = n-2^k+2$.

As an example, the encoding of $42$ consists of $k=\lfloor \log_2 (44) \rfloor = 5$ digits (since $2^5=32$ and $2^6=64$). These digits are $01100$ (notice the leading $0$) since $(42-32+2)_{10} = (12)_{10} = (1100)_2$.


To decode a number, you can do the reverse: count the number $k$ of digits in the encoded version, then add together $2^{k}-2$ and the number whose binary representation corresponds to the given digits. This also requires $O(k)=O(\log n)$ time.

For example, the encoded number $01100$ has $5$ digits, so the represented integer is $(2^5 -2)_{10} + (01100)_2 = (30 + 12 )_{10} =(42)_{10}$.

$\endgroup$
0
$\begingroup$

From shortlex to natural:

  • add $(10_b)^l-10_b$ to the binary value, where $l$ stands for the length (number of bits).

E.g. $011_s\to l=3\to11_b+1000_b-10_b=1001_b=9$.

From natural to shortlex:

  • the length is $l=\lfloor\log_2(n+2)\rfloor$,

  • subtract $2^l-2$,

  • fill left with zeroes.

E.g. $9\to l=\lfloor\log_2(11_d)\rfloor=3\to9-2^3+2=3=11_b\to011_s$

$\endgroup$

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.