Hierarchical identifiers, labels and indexes... All can use digits as character-strings, differenciating $0$ and $00$, $1$ and $001$, but preserving all other numeric interpretations, like order ($002>001$) and freedom for represantation (some other radix).
To illustrate, suppose a typical labeling system: Geohashes are positive integer numbers with a representation where the number of digits make difference. For example the Geohash 01 is a cell identifier of a geographic location little below Ross Sea with ~115000 km², and 0001 a cell far below, with 3.5 km².
Question: what the name of this class of numeric representation where number of digits (including leading zeros) make diference?
How about sized integers, good name? There are some "official Mathematic naming rules", when a official name not exists for a mathematical structure?
NOTE
I am looking for the Mathematical name... but, if there are no one, we can use other sources.
There are in Computing the name "Fixed-width integers" (FWInt) to say for example "fixed-width integers of 64 bits", where "x bits" is the name of a subclass. So, as I show in the examples below, we need a name for the union of many subclasses of FWInt (e.g. union of FWInt of 1 bit, FWInt of 2 bits, FWInt of 3 bits... and FWInt of 8 bits).
Integers and its representations (encodings) are used extensively in Computing. The usual foundation to implent long-size integers is the arbitrary-precision integers (e.g. BigInt is a primitive Javascript datatype). So, a datatype that is an integer with controled size can be named sized BigInt.
Intuitive definitions and examples
It is a finite set (or must be a sequence?) of numeric representations... Limiting examples in 8 bits:
Example with binary representations: $X_1 = \{0, 1\}$ $X_2 = \{0, 00, 01, 1, 10, 11\}$ ... $X_k$ ... $X_8 = \{0,00,000,000, \ldots, 00000000, 00000001, \ldots, 11111111\}$
The same set $X_8$ without some (non-compatible) items, in radix 4 representation: $Y_8 = \{0, 00, 000, 0000, 0001, 0002, 0003, 001, 0010, 0011 \ldots, 3333\}$
Ordering the illustred elements... Well, order is arbitrary for a set, here is only to enhance "same prefix" grouping (the hierarchy) in the sequence, that is important in applications:
(size,value) Binary representation Radix4 representation
(1,0) 0
(2,0) 00 0
(3,0) 000
(4,0) 0000 00
(5,0) 00000
(6,0) 000000 000
(7,0) 0000000
(8,0) 00000000 0000
(8,1) 00000001 0001
(7,1) 0000001
(8,2) 00000010 0002
(8,3) 00000011 0003
(6,1) 000001 001
(7,2) 0000010
(8,4) 00000100 0010
(8,5) 00000101 0011
... ... ...
To sort a group, less digits first. When the number of digits are equal, use the natural number order. Same is valid for some other radix. Identifiers of the cells of Geohash global grid, for example, use the radix 32 as its "standard representation".
Spatial indexes based on Hilbert curve indexes adopt radix4 to express the spatial hierarchy (recurrent split into four regions) into the radix4 digits. The cell numbering system of S2 Geometry, and many others, use it.
Trying a formal definition
Each example is a set, $X_k$, so we can suppose that we need the name of a class of sets in $k$. The table illustrated also that the elements of $X_k$ of this (named) class of sets are ordered pairs $(l,n)$ of length $l$ and numeric value $n$.
Lets check some properties:
Each element of this set can be mapped into a size (bits or number of digits) and a Natural number (value). PS: the preferred term for "size of the string" is length (or bit-length).
The maximum bit-length of an element of $X_k$ is a finite k. In other words, using the range set $L_k=\{1, 2, \ldots, k\}$, we can say that all element of $X_k$ has a bit-length $l \in L_k$, and there are elements for each $l$.
The bit-length of a Natural number $n>0$ is a function $bitLength(n)=\lceil log_2(n)+1 \rceil$. The bit-length of zero is one.
Putting all together, the set $X_k$ is a class in a finite $k$:
$$X_k = \{\forall x = (l,n) ~|~ l,n \in \mathbb{N} ~\land~ bitLength(n) \le l \le k \}$$
There is also a function $toString(l,n)$ that uniquely converts the pair $(l,n)$ into a bit string of the binary representation of n, and fills the leading zeros to the length l.
Two elements $x$ and $y$ are the same when $toString(x)=toString(y)$ or when $l$ and $n$ are equal: $$x=y ~ \iff ~ l_x=l_y \land n_x=n_y$$
And, similarly, the element $x$ is greater than $y$ by a criterion based on $l$ and $n$... But it is free, we not need to impose order, there are no special compare-criterion. No criterion is valid.
I can't say the name this kind of set, but now (edited) we have a better definition of the object, $X_L$, that need a name.
No comments:
Post a Comment