Código Natural

Todo código natural pode ser expresso univocamente através de uma cadeia de bits.

O conjunto dos Códigos Naturais foi definido em analogia ao conjunto dos números naturais (ℕ). O conjunto dos Códigos Naturais é munido de regras e operações, tais como ordenação, regras de notação posicional e regras de estruturação hierárquica. Cada um de seus elementos pode ser designado código natural e expresso através de uma cadeia de bits.

Números naturais também podem ser mapeados em cadeias de bits, mas esse mapeamento não abrange todas as cadeias possíveis. O código natural 0010 por exemplo é distinto do código 10, de modo que existem mais códigos naturais do que números naturais: o conjunto ℕ mapeado em cadeias de bits forma um subconjunto dos códigos naturais.

Formalização e licença: em [KraEtAll2019], registrado como CC0.

Implementação das operações em git.osm.codes/NaturalCodes.

Aplicações: geocódigos, indexadores, identificadores hierárquicos (de classes estáveis), rotuladores, hashes etc. Existe uma infinidade de aplicações onde as cadeias de bits são mais convenientemente interpretadas como códigos naturais, do que como números naturais.

Resumo didático

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 de código é 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 usual, então será o mesmo que 7; mas se digo que é um código, devo considerar 007 e 7 como entidades distintas.

A cadeia de bit é um tipo de dado primitivo, bem simples, possui poucas operações e poucos métodos de conversão. Podemos conceber um tipo de dado derivado um pouco mais sofisticado, com operações adicionais, tais como soma e sucessão, e com métodos de conversão, tais como conversão para notação posicional.

Números, por exemplo, são tipos primitivos bem mais sofisticados, com muito mais recursos computacionais e interoperabilidade com outros tipos de dados. O conjunto dos números naturais ( $\mathbb {N}$ ) é munido das operações de soma, multiplicação e de regras de notação posicional (decimal, binária, hexadecimal, etc.). Similarmente, o conjunto dos Códigos Naturais foi definido em [KraEtAll2019] através da formalização das operações de ordenação, soma, subtração, regras de notação posicional e regras de estruturação hierárquica.

Histórico

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

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).

Apresentação formal

Os três primeiros conjuntos

X_{k}

da hierarquia dos códigos naturais:

X_{1},X_{2}{\text{ e }}X_{3}

.
Na ilustração ressaltamos a equivalência entre a árvore binária completa e o Conjunto de Cantor.

Sintaticamente, códigos e números podem usar os mesmos símbolos como dígitos, e, 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 $\mathbb {N}$ é subconjunto dos códigos naturais. Para tirar proveito dessa relação sintática, denominaremos $P_{k}$ o conjunto dos números naturais (de k bits) convertidos para cadeias de bits de tamanho fixo k.

O conjunto dos códigos naturais, $X_{\infty }$ , pode ser induzido do conjunto $X_{k}$ , relativo a cadeias de no máximo k bits, gerado pela seguinte recorrência:

X_{k}={\begin{cases}P_{k}\cup X_{k-1},&{\text{if }}k>0\\\emptyset ,&{\text{if}}~k=0\end{cases}}

onde $P_{1}=\{0,1\}$ e nos demais $P_{k}$ os elementos são representações binárias de tamanho fixo k dos valores $0$ até $2^{k}-1$ . Por exemplo, para k=0 até k=8 temos os seguintes conjuntos $X_{k}$ :

{\begin{aligned}X_{0}&=\emptyset ;\\X_{1}&=P_{1}=\{0,1\};\\X_{2}&=P_{2}\cup X_{1}=\{00,01,10,11\}\cup \{0,1\}=\{0,00,01,1,10,11\};\\X_{3}&=P_{3}\cup X_{2}=\{000,001,010,\cdots ,111\}\cup \{0,00,01,1,10,11\}\\&=\{0,00,000,001,01,010,011,1,\cdots ,111\};\\\vdots \\X_{8}&=P_{8}\cup X_{7}=\{0,00,000,0000,\cdots ,11111110,11111111\}.\end{aligned}}

Por indução podemos supor também o "conjunto dos números naturais de 0 bits", que corresponde ao conjunto vazio, $P_{0}=\emptyset$ . Sintaticamente, a cadeia de bits vazia, necessária em diversas situações.

O número total de elementos em X_k, ou seja, $|X_{k}|$ , pode ser inferido por $|P_{k}|=2^{k}$ . Usando a recorrência temos $|X_{k}|=2^{k}+|X_{k-1}|$ , que contém a conhecida série das potências de 2 sem o último termo de 2⁰, $|X_{k}|=2^{k}+2^{k-1}+\dots +2^{1}$ , resultando em $|X_{k}|=2^{k+1}-2$ .

Definição alternativa

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

X_{k}=\{x=(l,n)\mid {l,n}\in \mathbb {N} \land minBL(n)\leq l\leq k\}

minBL(n)={\begin{cases}\left\lceil log_{2}(n)+1\right\rceil ,&{\text{if }}n>0\\1,&{\text{if }}n=0\end{cases}}

Os pares descrevem com exatidão e podem ser traduzidos para cadeias de bits (bitStrings). Ilustrando o uso dos pares (l,n), também designados "size-value pairs", em notação decimal:

BitString	(size,value)		BitString	(size,value)
`0`	(1,0)		`000000`	(6,0)
`111`	(3,7)		`00000101`	(8,5)

Problemas típicos com códigos

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_{2}$ 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. A tabela abaixo, listando códigos em sua ordem natural (lexicográfica da expressão bitString), ilustra problemas da Base4 e a solução Base4h, bem como a solução hbit.

(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 pelo Teorema de Cantor. Portanto, matematicamente, size-value é um tradutor mais rigoroso para expressões em

\mathbb {N}

.

Tamanho do problema

Quantos códigos naturais de k bits deixam de ser representados na Base N?

Avaliando a seguir apenas bases com N em {4, 8, 16, 32} da RFC 4648 das aplicações da Internet e (base 4) das aplicações em geocódigos. São todas na forma $N=2^{n}$ , com n variando de 2 (4=2²) a 5 (32=2⁵). O valor de n fornece também o número de bits por dígito da base, por exemplo base N=8 temos n=3, portanto cada dígito da base 8 tem 3 bits.

Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de k, resultando em uma quantidade de códigos, $n\_codes=2^{k+1}-2$ , e nas quantidades de representações válidas a cada base.

		Base and occupancy rate of n_codes
k (bits)	n_codes	base4		base8		base16		base32
1	2	0	0%	0	0%	0	0%	0	0%
2	6	4	67%	0	0%	0	0%	0	0%
3	14	4	29%	8	57%	0	0%	0	0%
4	30	20	67%	8	27%	16	53%	0	0%
5	62	20	32%	8	13%	16	26%	32	52%
6	126	84	67%	72	57%	16	13%	32	25%
7	254	84	33%	72	28%	16	6%	32	13%
8	510	340	67%	72	14%	272	53%	32	6%
9	1022	340	33%	584	57%	272	27%	32	3%
10	2046	1364	67%	584	29%	272	13%	1056	52%
11	4094	1364	33%	584	14%	272	7%	1056	26%
12	8190	5460	67%	4680	57%	4368	53%	1056	13%
13	16382	5460	33%	4680	29%	4368	27%	1056	6%
14	32766	21844	67%	4680	14%	4368	13%	1056	3%
15	65534	21844	33%	37448	57%	4368	7%	33824	52%
16	131070	87380	67%	37448	29%	69904	53%	33824	26%
Average on stable cycle:			50%		33%		25%		20%
Loss, 100% - occupancy:			50%		67%		75%		80%

Os valores percentuais foram calculados com relação a n_codes, as médias finais de occupancy com relação aos ciclos.

O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%; em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%.

Conclusão: nas bases de aplicação mais frequente (as bases 8 e 16), entre 67% e 75% dos códigos naturais deixam de ser representados. É uma perda muito grande, vale a penas investir numa solução.

Problemas típicos com taxonomias

... indexação e recuperação da hierarquia num banco de dados relacional ...

Inovações tecnológicas

...

Na representação interna

Ver Código natural/Representação interna.

....

Na representação textual

A sequência de 16 células pode ser rotulada pela base 4h. Esses rótulos podem ser empregados como geocódigos.
Ao contrário da base 4 numérica, que remove zeros a esquerda, a base 4h os mantém, por representar códigos e não números.

Oito células rotuladas hierarquicamente pela base4h. Reparar que os prefixos da ilustração anterior são preservados. Por ex. na anterior 00 e 03 possuem mesmo prefixo 0 que 0G e 0Q. Todas ocupam geometricamente o mesmo "quadrante 0" da célula-mãe.

A demanda por geocódigos eficientes motivou uma inovação tecnológica, desenvolvida pela AddressForAll. Do ponto de vista matemático é uma generalização da representação posicional, aplicada a códigos naturais. Assim como os números (binários base 2, decimais base 10, hexadecimais base 16, etc.), os códigos podem ser representados nos meios de comunicação de forma mais compacta que cadeias de bits, através de diferentes bases.

A base 4 (ou "sistema de numeração quaternário") é simples e já representa números de maneira mais compacta que a notação binária. Usa somente os dígitos 0 a 3. A sequência numérica de 0 a 6 por exemplo, em notação binária [0,1,10,11,100,101,110]₂, convertida para base 4 se torna [0,1,2,3,10,11,12]₄, economizando 5 dígitos.

Abaixo é ilustrado o uso clássico da base 4 em códigos: tradição de adaptação da base numérica, permitindo zeros a esquerda ao representar códigos. Mostra como a adaptação falha para certos códigos, e como a inovação da base 4h resolve o problema:

permite representar cadeias de bits (bit strings) de qualquer tamanho;
permite agrupar hierarquicamente.

Inspiradas nesta inovação para a base 4, foram criadas também a base 8h e a base 16h.

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.

A ordem é indiferente ao conjunto, podem haver saltos na sequência. Por ex. ao ordenar lexicograficamente o conjunto de códigos binários {10, 0, 1, 001} obtemos a série [0, 001, 1, 10]_2h.

Portanto, dentro de um conjunto com tamanho fixo de k bits, P_k (onde todos os elementos estão no nível k da hierarquia), a preorder e a level order resultam em ordenações equivalentes. A ordenação é realizada através de um algoritmo de comparação de pares de códigos, que pode tirar vantagem dessa equivalência para ser mais rápido.

Listagens ilustrativas

Resumodo de Código natural/Listagens com representações

Nas tabelas abaixo são apresentadas amostragens das bitstrings ordenadas de X₁, X₂ e 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.

X₁: códigos naturais com no máximo 1 bit,

count	bitstring	hbit	b4h	b16h
0		1
1	`0`	2	G	G
2	`1`	3	Q	Q

X₂: códigos naturais com no máximo 2 bits,

count	bitstring	hbit	b4h	b16h
0		1
1	`0`	2	G	G
2	`00`	4	0	H
3	`01`	5	1	M
4	`1`	3	Q	Q
5	`10`	6	2	R
6	`11`	7	3	V

...

X₈: códigos naturais com no máximo 8 bits,

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
...	...	...	...	...
509	`11111110`	510	3332	fe
510	`11111111`	511	3333	ff

Nota. A coluna count faz a contagem de bitstrings ordenadas, mas não começa com o valor 1. Para a biststring vazia adotamos 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 e o valor final de hbit.

Demais fundamentos

Hierarquia como coleção de conjuntos aninhados

Um conjunto aninhado é um conjunto contendo uma cadeia de subconjuntos, formando uma estrutura hierárquica. Na Teoria dos Conjuntos, está relacionado à ordem parcial, e os conjuntos aninhados são usados como referência para quaisquer definições de hierarquia ou herança de classe.

Seja B um conjunto não vazio e C uma coleção de subconjuntos de B, com $B\in C$ . Então C é uma coleção de conjuntos aninhados se:
${\begin{aligned}\forall H,Q\in \mathbf {C} :H\cap \mathbf {C} \neq \emptyset \implies H\subset Q\lor Q\subset H\end{aligned}}$
Então podemos supor que a coleção C que representa a hierarquia dos k-Códigos Naturais é definida por
$C_{k}=\{X_{1},X_{2},\dots ,X_{k}\}=\{P_{1},~P_{1}\cup P_{2},~\dots ,~P_{1}\cup P_{2}\cup \dots \cup P_{k}\}$
onde as operações da união estão demonstrando que a segunda condição é satisfeita.

Então sempre é verdade que
$X_{1}\subset X_{2}\subset X_{3}\subset \dots \subset X_{k}$
ou, generalizando, que i<a implica X_i⊂X_a. A coleção C_k é uma ordem parcial para “⊂”, portanto, uma ordem estrita de inclusão.

Outro aspecto do conceito de hierarquia está na hierarquia dos elementos de X_i. Comentada anteriormente, pode ser expressa pelas relações sintáticas entre os prefixos dos elementos de um conjunto X_i e do seu conjunto-origem X_i-1. Cada elemento x de X_i com mais de um bit,

a representação da cadeia de bits é uma concatenação de um prefixo p e um sufixo s, x=p⊕s, onde p ∈ X_i-1.
na representação por par $x=(l,n)$ o prefixo p de x é dado por $p=(l-1,\lfloor n/2\rfloor )\in X_{i-1}$ .

Ambas representações garantem que, sintaticamente, os elementos p de X_i-1 são "pais" dos elementos x de X_i. Ao passo que as relações gerais de inclusão garantem que X_i-1⊂X_i (o conjunto dos elementos-pais está contido no conjunto dos elementos-filhos).

São facetas da mesma hierarquia em árvore, embutida na estrutura dos conjuntos e na sintaxe dos seus elementos.

Bases 2h, 4h, 8h e 16h

Resumo de Código natural/Base h.

... resumo...

Reproduzindo a preorder dentro de um número inteiro

A ordem lexigrográfica dos formadas por zeros e uns, que resulta na chamada *preorder* das árvores binárias, .. conceito de distância conforme https://math.stackexchange.com/q/3142409/70274

Ordenações lexicográfica e numérica

Para simplificar as convenções da base-h, reutilizamos os alfabetos:
alphabet(base4h) ⊂ alphabet(base8h) ⊂ alphabet(base16h).

Outra decisão importante, para manter as representações numéricas como um subconjuntos das representações de códigos base-h:
rep(base4) ⊂ rep(base4h); rep(base8) ⊂ rep(base8h); rep(base16) ⊂ rep(base16h).

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

Pagamos um preço alto pela última decisão quando estamos ordenando uma lista de Códigos Naturais: "ordem numérica base16" e "ordem bitstring base16h" são intercaladas. O objetivo é a ordem lexicográfica da cadeia de bits, conforme tabela ao lado, onde as células coloridas mostram o problema de intercalação.

O melhor que podemos fazer, para o leitor humano, é preservar a ordem no conjunto de dígitos hexadecimais e a ordem no conjunto nhDigits. A ordem completa (união de conjuntos) deve utilizar, por exemplo, uma tradução no último dígito do código.

Em um banco de dados SQL, assumindo uma coluna x de códigos naturais em base16h. O “ORDER BY x” falhará. Necessita de uma tradução de caracteres, aqui expressa em PostgreSQL:

 SELECT x FROM t ORDER BY traduzir(
     x,
   'GHJ01K23MN45R67QRS89TabVZcdYef',
    '0123456789ABCDEFGHIJKLMNOPQRST'
 ) -- ou apenas a tradução do último dígito

Para ser amigável, evitando traduções, os códigos base-h devem ser representados por texto com collation especial. Supondo que a base-h seja um padrão, é natural propor um agrupamento para ela. Imagine definir uma coluna como representação base16h:

 CREATE TABLE t (x text COLLATE "num_b16h");

Algoritmos

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

Ver também