Código Natural
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
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 Xk, relativo a k bits, gerado pela seguinte recorrência:
onde Pk é 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é 2k-1. Por exemplo para k=1 até k=8 temos:
X1 = P1 = {0, 1};
X2 = P2 ∪ X1 = {00, 01, 10, 11} ∪ {0, 1} = {0, 00, 01, 1, 10, 11};
X3 = {0, 00, 000, 001, 01, 010, 011, 1, ..., 111};
Xk = ...;
X8 = {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 X2 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:
Os pares descrevem com exatidão e podem ser traduzidos para bitstrings. Ilustrando abaixo o uso dos pares (k,n), também designados "size-value pairs".
(size,value) BitString Base4 Base4h hbitBitstring hbit (1,0) 0 ? G 10 2 (2,0) 00 0 0 100 4 (3,0) 000 ? 0G 1000 8 (4,0) 0000 00 00 10000 16 (5,0) 00000 ? 00G 100000 32 (6,0) 000000 000 000 1000000 64 (7,0) 0000000 ? 000G 10000000 128 (8,0) 00000000 0000 0000 100000000 256 (8,1) 00000001 0001 0001 100000001 257 (7,1) 0000001 ? 000Q 10000001 129 (8,2) 00000010 0002 0002 100000010 258 (8,3) 00000011 0003 0003 100000011 259 (6,1) 000001 001 001 1000001 65 (7,2) 0000010 ? 001G 10000010 130 (8,4) 00000100 0010 0010 100000100 260 (8,5) 00000101 0011 0011 100000101 261 ... ... ... ... ...
A coluna "hbitBitstring" é relativa à representação das bitstrings em formato "hidden bit", definido em [KraEtAll2019]. 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 (em formato decimal na coluna hbit).
A coluna "Base4" é a tentativa (frustrada) de representar as bitstrings com o algoritmo da notação posicional numérica da Base 4. A coluna "Base4h" é a inovação proposta em [KraEtAll2019], que adaptou o algoritmo para expressar códigos ao invés de números, permitindo zeros a esquerda e quantidade variável de dígitos.
- Nota. Conjuntos finitos de códigos naturais sempre podem ser expressos como conjuntos de hbits, portanto através de números naturais. O conjunto de todos os Códigos Naturais todavia é infinito, e neste caso particular (com infinitos elementos), a representação hbit não é permitida.
Apresentação didática
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 X8. 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
...
Hierarquia como coleção de conjuntos aninhados
Cadeia de bits e notação base2h
...
Base4h
...
Base8h
Base16h
...