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 em [KraEtAll2019], implementação das operações em git.osm.codes/NaturalCodes.

Aplicações: geocódigos, indexadores, identificadores hierárquicos, rotuladores, hashes, descritores de estados quânticos 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, então será o mesmo que 7; mas se digo que é um código, devo considerar 007 e 7 como entidades distintas.

Podemos conceituar com mais precisão um "tipo de cadeia" dizendo que ela é elemento de um conjunto específico de cadeias de bits. Por exemplo uma cadeia do tipo "tamanho 3" é elemento do conjunto de todas as cadeias de 3 bits. Podemos criar ainda mais tipos se descrevermos operações válidas entre os elementos do conjunto.

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 formalizado em [KraEtAll2019], junto com a 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, 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).

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.

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. Matematicamente 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>1\\P_{1},&{\text{if }}k=0\end{cases}}$

onde $P_{k}$ é o conjunto dos números naturais de k bits, convertidos para bit strings.
Ou seja, os elementos de $P_{k}$ são representações binárias de tamanho fixo k dos valores $0$ até $2^{k}-1$.

Por exemplo, para k=1 até k=8 temos os seguintes conjuntos $X_{k}$:

${\begin{aligned}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}=\{0,00,000,001,01,010,011,1,\cdots ,111\},\\\vdots \\X_{8}&=P_{8}\cup X_{7}=\{0,00,000,000,\cdots ,11111110,11111111\}\end{aligned}}$

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.

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 bitstrings (cadeias de bits). Ilustrando abaixo o uso dos pares (l,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 pelo Teorema de Cantor. Portanto, matematicamente, size-value é um tradutor mais rigoroso para expressões em $\mathbb {N}$.

Inovação tecnológica nas representações

A sequência de células 1 a 16 pode ser rotulada pela base 4 com 2 dígitos.

Oito células rotuladas hierarquicamente pela base4h.

A demanda por geocódigos eficientes deu origem a uma inovação tecnológica, desenvolvida pela AddressForAll. Foi matematicamente generalizada como "repesentação posicioal de Código Natural". Assim como os números decimais (base 10), binários (base 2), 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") é o sistema de numeração mais simples para se representar geocódigos curtos (mais curtos do que a cadeia de bits). Usa somente os dígitos 0 a 3. A sequência numérica decimal [0, 1, 2, 3, 4, 5, 6] por exemplo, em base 4 se torna [0, 1, 2, 3, 10, 11, 12].

A ilustração abaixo destaca onde falha a base 4 tradicional e como a inovação da base 4h resolve o problema:

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

 

 

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.

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, $B\in C$. Então C é uma coleção de conjuntos aninhados se:

${\begin{aligned}\forall H,K\in C:H\cap C\neq \emptyset \implies H\subset K\lor K\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}$

e que a coleção C_k é uma ordem parcial para “⊂”, portanto, uma ordem estrita de inclusão. Em outras palavras, podemos dizer que X₃ é o pai de X₂ que é o pai de X₁. A convenção do índice i garante que  i<a  implica X_i⊂X_a.

A hierarquia dos elementos, mais importante e comentada anteriormente, pode ser expressa pelas relações entre os prefixos dos elementos de um conjunto X_i  e seu pai 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}$.

Cadeia de bits e notação base2h

Cadeias de bits podem ser representadas por números binários, mas, como exposto acima, devido à eliminação dos zeros à esquerda da representação numérica, uma parte das cadeias de bits não pode ser representada por números.

Para diferenciar 001 de 1 é necessário tomar o cuidado de dizer que a sequência de bits não é um "número na base 2", mas um "código na base 2h", onde "h" é relativo a hierárquico.

Base4h

Como converter as cadeias de bits 0 e 1, de um dígito, para base4? Ou cadeias de bits como 000?

Certas traduções, de cadeias de bits para números na base 4, fazem sentido; por exemplo [00]_2h=[0]₄ e [01]_2h=[1]₄. Mas não há uma convenção conhecida para traduzir cadeias de bits de 1 bit, 3 bits, 5 bits etc. Por exemplo: [0]_2h=[?]₄ ; [1]_2h=[?]₄ ; [000]_2h=[?]₄. Ver ilustração acima.

A solução é usar um dígito falso que represente esses valores. Para evitar confusão com letras hexadecimais podemos usar "G" para representar a cadeia 0 e "Q" para representar 1. É denominado “dígito não-hierárquico” (nhDigit), pois, apesar de acomodar representação hierárquica, não é membro da hierarquia. A “base4 estendida para hierarquia” foi abreviada para “Base4h”. Nas listagens ilustrativas são apresentadas todas as representações Base4h do conjunto X₄.

Os códigos Base4h são strings com o padrão base4 usual e o nhDigit como sufixo opcional. Esta regra de sintaxe, para reconhecimento de códigos Base4h arbitrários, pode ser expressa por uma expressão regular:
  /^([0123]*)([GQ]?)$/

O inverso, para traduzir da cadeia de bits com b bits, quando b é par, podemos usar a conversão base4 comum e, quando b é ímpar, concatenar o nhDigit. Dividindo (por exemplo, com Javascript) o valor binário como partes de prefixo e sufixo,
  let part = bitString.match(/^((?:[01]{2,2})*)([01]*)$/)
o prefixo (part[0]) será convertido para o número base4 usual e o sufixo (part[1]), quando existir (um último bit restante), será traduzido para nhDigit por este mapa JSON: {"0": "G","1":"Q"}.

Exemplo: converter 001010010 em base4h, dividindo em partes, part[0]=00101001 dos blocos de 2 bits de início, que resultará em “0221”, e parte[1]=0 do bit restante, resultando em “G”. Concatenando os resultados das partes, “0221G”.

Base8h

...

Base16h

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

Esta extensão de codificação para base16 (RFC 4648, sec 8) foi inspirada na codificação Base4h. Ele usa o mesmo conceito nhDigit: uma sintaxe complementar à representação de base comum onde o último dígito pode usar um alfabeto alternativo para representar valores parciais (com menos bits) de dígitos comuns.

Podemos usar representação hexadecimal para qualquer número inteiro, mas ao controlar o comprimento de bit, podemos usar apenas comprimentos compatíveis com Base16: 4 bits, 8 bits, 12 bits, ... múltiplos de 4.

Então, como transformar em Base16 as cadeias de bits como 0, 1, 00, 01, 10, ... ?

A solução é estender uma representação hexadecimal, de maneira semelhante à anterior usada para base4h: o último dígito como um dígito falso que pode representar todos esses valores incompatíveis — portanto, usando os valores nhDigit G e Q para valores de 1 bit , e incluindo mais valores para 2 bits (4 valores) e 3 bits (8 valores). O total é 2+4+8=14 valores, eles podem ser representados pelas letras "G" a "T" ou qualquer outro conjunto de 14 letras — a tabela 3 mostra nossas escolhas.

O conjunto foi otimizado excluindo vogais ("I", "O", "U") e símbolos que podem ser facilmente confundidos entre si (como L), e excluindo "X" porque é usado como prefixo de conversão hexadecimal (por exemplo, x0123).

O nome desta nova representação é base16h, porque é a “base16 ordinária estendida para hierarquia”: /^([0-9a-f]*)([GHJKMNP-TVZY])?$/

O inverso, para traduzir de uma string de bits com b bits, há b%4 últimos bits a serem traduzidos para um nhDigit. Dividindo (por exemplo, com Javascript) o valor como partes de prefixo e sufixo,

let part = bitString.match(/^((?:[01]{4,4})*)([01]*)$/)

o prefixo (parte[0]) será traduzido para o número hexadecimal usual, e o sufixo (parte[1]), quando existir (com 1, 2 ou 3 últimos bits), será traduzido por este "últimos bits para nhDigit" Mapa JSON:

{ "0":"G", "00":"H", "000":"J", "001":"K", "01":"M", "010":"N", " 011":"P",
  "1":"Q", "10":"R", "100":"S", "101":"T", "11":"V", "110":"Z", "111 ":"S"
}

Exemplo: para converter 0010100101 em Base16h, divida em part[0]=00101001 de blocos de 4 bits desde o início, e part[1]=01, dos bits restantes. Converta parte[0] em hexadecimal comum (00101001 é “29”) e part[1] pela tabela JSON acima (01 é “M”), resultando em “29M”.

Bases de interesse prático

Podemos supor que as bases com maior leque de aplicações são 2h, 4h e 16h. Destacaremos também a base32h como semi-compatível com a base 4h. A justificativa a seguir se restringe ao contexto da utilização dos Códigos Naturais como geocódigos, principalmente GGeohash.

A rigor a base mais simples para a representação de geocódigos é a base 4, pois cada célula é subdividida em 4 células-filhas.

Os dígitos da base 4 ocupam 2 bits, e sua representação geométrica é sempre simétrica — se a célula de nível L0 for quadrada, as células rotuladas por geocódigos da base 4 também serão sempre quadradas.

A base 4 é importante, tem aplicação relevante por ser essencial à representação de geocódigos. Será que outra base N, com N menor ou maior que 4 terá também aplicação nesse contexto?

A base 2 (binária) é a mais fundamental, com dígitos de 1 bit, mas geocódigos binários com número ímpar de bits serão associados a "grades degeneradas", com células retangulares. Portanto buscamos base N com N≥4. A base 2 todavia é fundamental nos sistemas digitais: apenas bases N com N≥4 pertencendo ao conjunto das potências de 2, $N\in \{2^{2},2^{3},2^{4},...\}$, é que terão dígitos fazendo uso integral dos bits que os representam. Por exemplo a base 10 do sistema numérico decimal usual, requer 4 bits por dígito, descartando informação (usa valores 0 a 9 e descarta 10 a 15).

Iniciamos em N=4, e daí em diante os geocódigos serão úteis se compatíveis com a base 4 e a base 2. Resumindo os requisitos que justificamos até aqui:

base N com N≥4 para ter uma representação mais compacta, e que tenha N múltiplo de 4, para que suas células resultem sempre em células quadradas. Além disso N precisa ser potência de dois.
Portanto N no conjunto {4, 8, 16, 64, …}

O valor de N todavia tem um limite superior bem conhecido para o alfabeto das línguas ocidentais: 26 letras do alfabeto mais dígitos 0 a 9, resultando no máximo de 36 caracteres. As tentativas de uso da base 64 falham principalmente pela dificuldade do ser humano em distinguir maiúsculas e minúsculas. Há portanto o requisito de

N≤36

As bases mais compactas portanto ficam restritas a $N\in \{8,16\}$ onde o máximo, para máxima compressão, é o 16. A representação hexadecimal portanto é a eleita.

Para algumas aplicações, todavia, como a adoção do geocódigo como código postal, maior compressão é solicitada. A experiência com a tecnologia Geohash clássica demonstrou que, apesar de envolver grades degeneradas, nas aplicações logísticas o base 32 seria uma alternativa. Ela não chega a ser totalmente incompatível com a base 4: geocódigos base 32 com quantidade de dígitos par (2, 4, 6, etc.) são compatíveis. A ilustração abaixo mostra o "bate" entre a quantidade de bits, há compatibilidade para múltiplos de 10.

Tomando o caso concreto da grade de um país continental como Brasil, que requer 20 níveis para subdividir L0 até chegar no metro. Fica nítido pelo emparelhamento dos bits que apenas três níveis das grades base 32 e hexadecimal serão comuns: L0, L10 e L20. Abaixo a ilustração da interface para seleção de níveis, com todos e com seus filtrados.

Por fim, por garantir a representação "humanamente legível" de todas as grades, a base 16h é adotada como canônica dos geocódigos. Sua representação geométrica é ilustra abaixo.

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