Distance of binary strings to produce the lexicographical order

Question

Indexing objects like elements of a Cantor Set or nodes of a Binary Tree can result in a enconding system of binary strings like illustrated bellow:

The illustrated indexes form a finite set, $$C_3=\{0,00,000,001,... ,111\}$$

We can provide the set $C_3$ of a comparison operation, offering the same elements in a sequence with the lexicographical order (also illustred with the sequence into square breakets), that is a total order relation.

The same set can be mapped into a set of numerical pairs (bitLength,value), $$V_3=\{(1,0), (2,0), (3,0), (3,1), (2,1), ... , (3,7)\}$$ where 0=(1,0), 00=(2,0), 000=(3,0), 001=(3,1), 01=(2,1), ... etc. Any element $x$ is a pair $(x_{bitLength},x_{value})$. A generic $V_k$ have elements with $bitLength \le k$. In fact this generic set was defined in this other question as:

$$V_k = \{\forall x = (l,n) ~|~ l,n \in \mathbb{N} ~\land~ bitLength(n) \le l \le k \}$$

where the function $bitLength(n>0)=\lceil log_2(n)+1 \rceil$ and the bit-length of zero is one.

Now we can express a distance $d(x,y,k)$ of two elements $x$ and $y$ of $V_k$, that can be used as mathematical reference to the lexicographical order... What is the $d(x,y,k)$ function?
How to proof that is the correct function for any $k$?

---

... Or more simples, What the comparison function $cmp(x,y,k)$?

There are no special "metric", the aim is to sort, that is, to check the value of comparison. As usual convention is $cmp(x,y,k)=1$ when $x>y$, $cmp(x,y,k)=0$ when $x=y$ and $cmp(x,y,k)=-1$ when $x>y$.

---

NOTES

Supposing that there are someting as dyadics that can be used in the proof... Seems good in some tests, but I do not know how use mathematical foundations or how to proof:
d(x,y) = x.value/2^x.bitLength - y.value/2^y.bitLength

Some raw data to tests, illustrating with all elements of $C_4$ and $V_4$:

(bits,value)    Binary representation
(1,0)           0
(2,0)           00
(3,0)           000
(4,0)           0000
(4,1)           0001
(3,1)           001
(4,2)           0010
(4,3)           0011
(2,1)           01
(3,2)           010
(4,4)           0100
(4,5)           0101
(3,3)           011
(4,6)           0110
(4,7)           0111
(1,1)           1
(2,2)           10
(3,4)           100
(4,8)           1000
(4,9)           1001
(3,5)           101
(4,10)          1010
(4,11)          1011
(2,3)           11
(3,6)           110
(4,12)          1100
(4,13)          1101
(3,7)           111
(4,14)          1110
(4,15)          1111

Some distances to test:

• d(00,01) = d(10,11)
• |d(000,0)| = |d(1,111)|
• d(1101,11) < d(1100,1101)
• ...

Answer 1

The distance function $d(x,y,k)$ is arbitrary and can be simple... With scalar values we can use $d(x,y)=x-y$. In this problem $x$ and $y$ are vectors: $x=(x_l,x_n)$ and $y=(y_l,y_n)$. To keep simple we can suppose that exists a "score function" that transforms the vectors into scalars.

Lets start with the suggested score, based on dyadic numbers: $score1(x)=x_n/2^{x_l}$. The only problem is about 0, 00, etc. (also 101 and 1010, etc.) that need different scores. A simple correction is to add a fraction $\alpha x_l$ that is less tham the minor value of $score1$, that is $\alpha k<score1(1)$. So:

$$score2(x,k) ~=~ score1(x)+\alpha_k x_l ~=~ x_n/2^{x_l}+\frac{x_l}{k \times 2^{k+1}}$$

Using the example of $k=4$ (the set $V_4$), the result is:

x               Binary      Score1      Score2
(1,0)           0           0.000       0.008
(2,0)           00          0.000       0.016
(3,0)           000         0.000       0.023
(4,0)           0000        0.000       0.031
(4,1)           0001        0.063       0.094
(3,1)           001         0.125       0.148
(4,2)           0010        0.125       0.156
(4,3)           0011        0.188       0.219
(2,1)           01          0.250       0.266
(3,2)           010         0.250       0.273
(4,4)           0100        0.250       0.281
(4,5)           0101        0.313       0.344
(3,3)           011         0.375       0.398
(4,6)           0110        0.375       0.406
(4,7)           0111        0.438       0.469
(1,1)           1           0.500       0.508
(2,2)           10          0.500       0.516
(3,4)           100         0.500       0.523
(4,8)           1000        0.500       0.531
(4,9)           1001        0.563       0.594
(3,5)           101         0.625       0.648
(4,10)          1010        0.625       0.656
(4,11)          1011        0.688       0.719
(2,3)           11          0.750       0.766
(3,6)           110         0.750       0.773
(4,12)          1100        0.750       0.781
(4,13)          1101        0.813       0.844
(3,7)           111         0.875       0.898
(4,14)          1110        0.875       0.906
(4,15)          1111        0.938       0.969

Concluding: there are many possible functions, this one seems simple,

$$d(x,y,k)=score2(x,k)-score2(y,k) ~=~ x_n/2^{x_l}-y_n/2^{y_l}+\frac{x_l-y_l}{k \times 2^{k+1}}$$

---

Algorithm of lexicographical comparison

When using $d()$ as comparison function, it can be optimized; for example for $x_l=y_l$ can be replaced by the usual $d(x,y) ~=~ x_n-y_n$. Here a Javascript function to compare arbitrary-precision integers in the form x=(x.l,x.n), where x.l is the bitLength (a small integer) and x.n the value, a BigInt.

function cmp_lexic(a,b) {
  let bdif = a.l - b.l
  if (bdif) {
   dif = (bdif>0)
     ? a.n/BigInt(2**bdif) - b.n     // normalize a
     : a.n - b.n/BigInt(2**(-bdif)); // normalize b
   if (!dif) dif = bdif;
  } else
   dif = a.n - b.n
  return dif? ((dif>0n)? 1: -1) : 0;
}

The comparison not depends on the maximal length k.