Código Natural

Uma cadeia de bits.

Um código qualquer é representado internamente, no computador, por uma cadeia de bits; que por sua vez é meramente uma sequência de símbolos dentro do computador (tipicamente zeros e uns). O conceito é mais abrangente e não deve ser confundido com o conceito de número: aplicamos apenas aos números a regra de "eliminar zeros à esquerda". Se digo que 007 é um número, então será o mesmo que 7; mas se digo que é um código, devo considerar 007 e 7 como entidades distintas.

O conjunto dos números naturais (ℕ) é munido das operações de soma, multiplicação e de regras de notação posicional (decimal, binária, hexadecimal, etc.). Similarmente o "tipo de código", e as operações que podemos efetuar sobre o tipo, é sempre referente a um conjunto de códigos. O conjunto dos Códigos Naturais foi formalizado em [KraEtAll2019], junto com a formalização das operações de ordenação, soma, subtração e regras de notação posicional.

Apresentação formal

Os três primeiros conjuntos X_k da hierarquia dos códigos naturais: X₁, X₂ e X₃.
Na ilustração ressaltamos a equivalência entre a árvore binária completa e o Conjunto de Cantor.

Por existirem mais possibilidades de combinar símbolos na forma de códigos do que na forma de números, podemos afirmar que o conjunto dos símbolos que representam elementos de ℕ é subconjunto dos códigos naturais. Matematicamente o conjunto dos códigos naturais, X_∞, pode ser induzido do conjunto X_k, relativo a k bits, gerado pela seguinte recorrência:

onde P_k é o conjunto dos números naturais de k bits, convertidos para bit strings. Ou seja, representações de tamanho fixo k dos valores zero até 2^k-1. Por exemplo para k=1 até k=8 temos:

  X₁ = P₁ = {0, 1};
  X₂ = P₂ ∪ X₁ = {00, 01, 10, 11} ∪ {0, 1} = {0, 00, 01, 1, 10, 11};
  X₃ = {0, 00, 000, 001, 01, 010, 011, 1, ..., 111};
  X_k = ...;    X₈ = {0, 00, 000, 000, ..., 11111110, 11111111}.

Números binários são representações válidas da notação posicional base2, e podem ser representados de forma mais compacta (mais amigável para o ser humano) através de bases maiores, tais como base8 (sistema octal) ou base10 (sistema decimal). Códigos, todavia, não possuem um sistema posicional adequado, não existe um padrão para se representar todos os códigos naturais, nem sequer na base4.

Outro problema é a ordem: códigos naturais, para exibirem a ordem hierárquica, precisam ser ordenados lexicograficamente (ao invés de numericamente). Em X₂ por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc.

A noção de código natural nos ajuda estudar esses problemas, e valorizar as eventuais soluções.

Definição alternativa

O conjunto dos códigos naturais pode ser expresso através de números naturais. Podemos usar os pares numéricos tamanho-valor, com o tamanho variando de zero a k bits, e valores n variando de zero ao máximo permitido pelos k bits:

   (size,value)         BitString        Base4          Base4h          hbit
   (1,0)                0                ?              G               10
   (2,0)                00               0              0               100
   (3,0)                000              ?              0G              1000 
   (4,0)                0000             00             00              10000
   (5,0)                00000            ?              00G             100000 
   (6,0)                000000           000            000             1000000
   (7,0)                0000000          ?              000G            10000000 
   (8,0)                00000000         0000           0000            100000000 
   (8,1)                00000001         0001           0001            100000001
   (7,1)                0000001          ?              000Q            10000001
   (8,2)                00000010         0002           0002            100000010
   (8,3)                00000011         0003           0003            100000011
   (6,1)                000001           001            001             1000001 
   (7,2)                0000010          ?              001G            10000010 
   (8,4)                00000100         0010           0010            100000100 
   (8,5)                00000101         0011           0011            100000101
    ...                 ...             ...             ...             ...

A coluna hbit é relativa à representação das bitstrings em formato "hidden bit", definido em [KraEtAll2019]; que consiste em acrescentar o 1 na frente da bitstring, para que não lhe cortem os zeros à esquerda, ao interpretá-la como número inteiro positivo.

Apresentação didática

A sequência de 1 a 16 pode ser representada pela base 4 com 2 dígitos.

Oito células numeradas hierarquicamente pela base4h.

A base 4 (ou "sistema de numeração quaternário") é o sistema de numeração mais simples para se representar geocódigos, garantindo códigos mais curtos do que a cadeias de bits. Usa somente os dígitos 0 a 3. A sequência numérica [0, 1, 2, 3, 4, 5, 6] por exemplo, em base4 se torna [0, 1, 2, 3, 10, 11, 12].

A ilustração abaixo destaca onde falha a base 4 tradicional e como a base4h resolve o problema.

 

 

As questões de ordenação são resolvidas por algoritmos de comparação aplicados à representação interna do código, em geral a binária. A ordem lexicográfica dos bits é a mesma que a chamada "preorder" de uma árvore binária. A "level order" pode ser útil para certas situações, mas não é considerada a ordem nativa dos códigos naturais.

Histórico

O Instituto AddressForAll propôs em 2019 uma nova notação para os códigos naturais, similar à notação hexadecimal, e garantindo que a hierarquia entre códigos seja preservada, tal como na cadeia de bits.

Tecnicamente é uma notação posicional para transformar cadeias de bits com quantidade arbitrária de bits, que preserva a hierarquia e é compatível com a representação numérica hexadecimal comum.

O documento [KraEtAll2019] foi registrado na Fundação Biblioteca Nacional sob o protocolo número 2801/19, garantindo que nenhuma patente ou direito autoral possam ser reclamados quanto à notação criada (base4h, base8h e base16h).

Listagens ilustrativas

Na tabela abaixo é apresentada uma amostragem das bitstrings ordenadas de X₈. A coluna count é um contador de linhas para o humano acompanhar em representação decimal a sequência, as colunas b4h e b15h são as representações em base4h e base16h respectivamente.

A coluna hbit é a representação "hidden bit", onde a inclusão à esquerda do dígito 1 na bitstring resulta em um valor decimal maior. Por exemplo as bitstrings 0, 1 e 00 com o 1 na frente serão 10, 11 e 100, que em decimal serão 2, 3 e 4.

Nota. A coluna count faz a contagem de bitstrings ordenadas, de modo que a primeira linha (count 1) seria relativa à biststring vazia... Adotamos no entanto a noção de "zerézima linha", para compatibilizar com a coluna hbit (o próprio marcador tem valor 1). A rigor a noção de "zerézimo" é também adotada pela numeração ordinal em Matemática. Reparar que o acréscimo da linha zero garante também a compatibilização entre a quantidade de linhas (511) e o valor final de hbit, 511.

count	bitstring	hbit	b4h	b16h
0		1
1	0	2	G	G
2	00	4	0	H
3	000	8	0G	J
4	0000	16	00	0
5	00000	32	00G	0G
6	000000	64	000	0H
7	0000000	128	000G	0J
8	00000000	256	0000	00
9	00000001	257	0001	01
10	0000001	129	000Q	0K
11	00000010	258	0002	02
12	00000011	259	0003	03
13	000001	65	001	0M
14	0000010	130	001G	0N
15	00000100	260	0010	04
16	00000101	261	0011	05
17	0000011	131	001Q	0P
18	00000110	262	0012	06
19	00000111	263	0013	07
20	00001	33	00Q	0Q
21	000010	66	002	0R
22	0000100	132	002G	0S
23	00001000	264	0020	08
24	00001001	265	0021	09
25	0000101	133	002Q	0T
26	00001010	266	0022	0a
27	00001011	267	0023	0b
28	000011	67	003	0V
29	0000110	134	003G	0Z
30	00001100	268	0030	0c
31	00001101	269	0031	0d
32	0000111	135	003Q	0Y
33	00001110	270	0032	0e
34	00001111	271	0033	0f
35	0001	17	01	1
36	00010	34	01G	1G
37	000100	68	010	1H
38	0001000	136	010G	1J
39	00010000	272	0100	10
40	00010001	273	0101	11
41	0001001	137	010Q	1K
42	00010010	274	0102	12
...	...	...	...	...
244	01111000	376	1320	78
245	01111001	377	1321	79
246	0111101	189	132Q	7T
247	01111010	378	1322	7a
248	01111011	379	1323	7b
249	011111	95	133	7V
250	0111110	190	133G	7Z
251	01111100	380	1330	7c
252	01111101	381	1331	7d
253	0111111	191	133Q	7Y
254	01111110	382	1332	7e
255	01111111	383	1333	7f
256	1	3	Q	Q
257	10	6	2	R
258	100	12	2G	S
259	1000	24	20	8
260	10000	48	20G	8G
261	100000	96	200	8H
262	1000000	192	200G	8J
263	10000000	384	2000	80
264	10000001	385	2001	81
265	1000001	193	200Q	8K
266	10000010	386	2002	82
...	...	...	...	...
499	11111000	504	3320	f8
500	11111001	505	3321	f9
501	1111101	253	332Q	fT
502	11111010	506	3322	fa
503	11111011	507	3323	fb
504	111111	127	333	fV
505	1111110	254	333G	fZ
506	11111100	508	3330	fc
507	11111101	509	3331	fd
508	1111111	255	333Q	fY
509	11111110	510	3332	fe
510	11111111	511	3333	ff

Demais fundamentos

...

Cadeia de bits e notação base2h

...

Base4h

...

Base16h

O alfabeto da base 16h, para representar os primeiros 30 códigos naturais.

...

Algoritmos

Ver https://git.osm.codes/NaturalCodes