Código Natural/Notação posicional

Termos utilizados na notação posicional de códigos. Em texto: 0125_8h ou [0125]_8h.

Cadeias de bits são a forma mais simples para se registrar números ou códigos naturais, mas para o ser humano elas são muito longas e difíceis de ler. No caso dos números existe a notação posicional em base N, mais compacta que a representação binária para qualquer N>2.

A notação numérica pode ser facilmente adaptada para expressar códigos naturais. Exemplos:

Notação / Característica	Código	Número	Código	Número
Base 2. Binária / Ilegível	`00010010`	10010	`1111`	1111
Base 4. Quaternaria / Melhorou!	`0102`	102	`33`	33
Base 16. Hexadecimal / Mais compacta	`12`	12	`f`	f

Alguns cuidados devem ser tomados, como o tratamento dos zeros a esquerda, importante diferenciador de códigos. Notar o exemplo 00010010₂ que manteve seu zero a esquerda em 0102₄. E existem ainda códigos que não podem ser representados em certas bases. Por exemplo o código 010₂ não pode ser representado na base 4. Se representar como 02₄ vai ser confundido com o binário 0010₂. Outros exemplos:

Base2	`0`	`00`	`0000`	`010`	`1010`	`10100`
Base4	?	`0`	`00`	?	`22`	?
Base16	?	?	`0`	?	`a`	?

Definição

Para distinguir a notação numérica binária, por exemplo [010]₂=[10]₂, da notação posicional para códigos binários e cadeias de bits, foi convencionado o uso da base 2h, por exemplo 010_2h≠10_2h. O sufixo "h" destaca que queremos preservar a hierarquia.

Para além da base 2, outras convenções e cuidados precisam ser tomados. O conjunto $P_{k}$ dos números naturais de k bits pode ter seus elementos representados por base 2, base 3, base 4, ..., até base N, com $N\leq 2^{k}$ .

O conjunto dos códigos naturais de zero a k bits, $X_{k}=P_{k}\cup X_{k-1}$ , pode também ser representado de maneira compacta, através de uma adaptação da notação posicional numérica, nas seguintes situações:

Códigos base N: permite a representação de códigos de u bits, com $u\leq k$ e valores de u múltiplos de $log_{N}(2)$ ; mapeados no conjunto $\bigcup P_{u}$ de números de u bits. A conversão numérica deve ser acrescida de zeros a esquerda (até atingir o tamanho fixo compatível com o tamanho u da origem).
A restrição dos múltiplos pode ser expressa como $u~{\bmod {l}}og_{2}(N)=0$ .
Por exemplo base 4 permite valores de u restritos por $u~{\bmod {~}}2=0$ , portanto permite representar o conjunto de códigos com u par: $P_{0}\cup P_{2}\cup P_{4}\cup \dots \cup P_{k}$ . Quanto à notação textual, nesta Wiki distinguimos o código 007₈≠7₈ do número [007]₈=[7]₈ pelo uso da fonte e dos colchetes.

Códigos base Nh: além de permitir a representação dos elementos de $P_{k}$ , permite a dos elementos de $X_{k-1}$ ; ou seja, permite a representação de todos os códigos naturais $X_{k}$ .
A base Nh também preserva a hierarquia do código natural. Na prática $N\in \{2,4,8,16\}$ por não haverem convenções para bases maiores, nem hierarquia fora das potências de dois. Ou seja Nh está limitado às bases 2h, 4h, 8h e 16h.

Outras notações: o "padding" descrito na RFC 4648, com escopo na conversão de bytes (base256) em baseN, oferece um padrão adequado para $N\in \{16,32,64\}$ , mas não para a baseNh, justamente porque, mesmo com o recurso de "padding" orientado ao tamanho arbitrário de bytes, falha em expressar códigos com tamanho arbitrário de bits.

Em particular, para N=2 as notações base 2h e base 2 são equivalentes. Convenciona-se base 2h como canônica (preferível). A equivalência decorre de $log_{2}(2)=1$ , implicando que todos os códigos naturais $X_{k}$ possuem representação base 2: $X_{k}=P_{0}\cup P_{1}\cup P_{2}\cup \dots \cup P_{k}$ .

Notações padronizadas

Alfabetos e demais convenções da notação posicional de códigos naturais. Lista completa de IDs com respectivos alfabetos-padrão para conversão de base, para as “bases potência de 2”.

O identificador é a concatenação da palavra “base” com o valor da base e o rótulo (label) do alfabeto. O número de bits por dígito é o log₂ da base. No alfabeto foram destacados os nhDigits (non-hierarchical digits) conforme notação Natural Code.

Base N

base	label	ID	bits	alphabet	Reference standard
4	js	base4js	2	`0123`	ECMA-262
8	js	base8js	3	`01234567`	ECMA-262
16	js	base16js	4	`0123456789abcdef`	ECMA-262 and RFC 4648/sec8
32	hex	base32hex	5	`0123456789abcdefghijklmnopqrstuv`	ECMA-262 and RFC 4648/sec7
32	ghs	base32ghs	5	`0123456789bcdefghjkmnpqrstuvwxyz`	Geohash
32	nvu	base32nvu	5	`0123456789BCDFGHJKLMNPQRSTUVWXYZ`	No-Vowels except U (near non-syllabic)
32	rfc	base32rfc	5	`ABCDEFGHIJKLMNOPQRSTUVWXYZ234567`	RFC 4648/sec6
64	url	base64url	6	`ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_`	RFC 4648/sec5
64	rfc	base64rfc	6	`ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/`	RFC 4648/sec4
All base32 here are using with leading zeros, they are valid instances of “restricted hiearchy”, base32rh.

Exemplos. Os códigos 007_10rh, 33_4h e ab12T_16h, abaixo exemplifiados em cada notação:

base ID	007, 33, ab12T `000000000111`_2h, `1111`_2h e `1010101100010010101`_2h
base4js	`000013`_4js, `33`_4js e `?`_4js
base8js	`0007`_8js, `?`_8js e `?`_8js
base16js	`007`_16js, `f`_16js e `?`_16js
base32hex	`k7`_32hex, `?`_32hex e `?`_32hex
base32ghs	`n7`_32ghs, `?`_32ghs e `?`_32ghs
base32nvu	`N7`_32nvu, `?`_32nvu e `?`_32nvu
base32rfc	`UH`_32rfc, `?`_32rfc e `?`_32rfc
base64url	`?`_64url, `?`_64url e `?`_64url
base64rfc	`?`_64rfc, `?`_64rfc e `?`_64rfc

A interrogação, "?", indica que a representação da cadeia de bits daquele tamanho não existe naquela base.

Base Nh

A regra de "eliminar zeros a esquerda", que caracteriza números, deve ser eliminada quando expressamos códigos. No contexto binário os códigos são equivalentes a cadeias de bits justamente por isso. Mas tão logo desejarmos usar uma base maior, por exemplo base 4, surge um novo problema: garantir que todas as possíveis cadeias de bits serão traduzidas para a base?

Exceto pela base2h, portanto, todas as outras bases-h (4h, 8h, etc.) requerem um sistema mais sofisticados para se manterem hierárquicas, e, para que sejam compatíveis entre si, não há margem para a eleição de alfabetos alternativos.

base	label	ID	bits	alphabet (depois do espaço os nhDigits)	Reference standard
2	h	base2h	1	`01`	ECMA-262
4	h	base4h	2	`0123 GQ`	ECMA + nhDigits alphabet
8	h	base8h	3	`01234567 GQ HMRV`	ECMA + nhDigits alphabet
16	h	base16h	4	`0123456789abcdef GQ HMRV JKNPSTZY`	ECMA + nhDigits alphabet

Exemplos. Os códigos 007_10rh, 33_4h e ab12T_16h, abaixo exemplifiados em cada notação:

base ID	007, 33, ab12T
base2h	`000000000111`_2h, `1111`_2h e `1010101100010010101`_2h
base4h	`000013`_4h, `33`_4h e `222301022q`_4h
base8h	`0007`_8h, `7q`_8h e `526112q`_8h
base16h	`007`_16h, `33`_16h e `ab12T`_16h

Bases de interesse prático

Podemos supor que as bases com maior leque de aplicações são 2h, 4h e 16h, destacando também a base32, por ser semi-compatível com a base 4h e suprir representação mais compacta. As bases 16 e 32 também são destacadas na RFC 4648, sendo a base 16 a de uso mais amplo e consolidado. A discussão a seguir, para justificar a preferência por certas bases, se restringe ao contexto da utilização dos Códigos Naturais como geocódigos, principalmente GGeohash.

A base mais simples para a representação de geocódigos é a base 4, pois cada célula é subdividida em 4 células-filhas. Supondo uma célula-mãe identificada como "A", podemos batizar as suas filhas com sufixos base4 conforme ilustrado:

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.

Algoritmos base h

Algoritmos de reconhecimento e conversão dos códigos expressos em bases hierárquicas.

As funções de referência foram escritas em SQL, ver git.osm.codes/GGeohash/src/step03def-lib.sql.

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

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

Tabela da representação dos códigos naturais de até 4 bits, em bases 2h, 4h, 8h e, com um dígito, 16h.

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 cadeia 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"
}

A tabela ao lado resume as convenções adotadas, e demonstra que há consistência entre as bases 4h, 8h e 16h.

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

Ilustrando em geocódigos

Geocódigos do tipo GGeohash identificam células de grades quadriláteras. Podemos imaginar, sobre um mapa geográfico, a célula-mãe de 512 km de lado, rotulada pelo ID 82. Ela pode ser subdividida recursivamente em 4 partes para manter a forma quadrada nas grades resultantes, ou ainda ser subdivida recursivamente em 2, resultando em grades quadradas e retangulares alternadamente:

Na Base 16h portanto apresenta rótulos para todos os níveis, do L0 ao L4 e seus intermediários:

L0, L0.5, L1, L1.5, L2, L2.5, L3, L3.5, L4. Resulta em um sistema com 5×2-1=9 grades hierárquicas. Para qualquer que seja o nível máximo N, a Base 16h resultará em um sistema completo de grades, com N×2-1 níveis.

Abaixo células L0 de cobertura do Brasil, ilustrando caso concreto de grades de diferentes níveis. Elas foram rotuladas pela Curva-Z espelhada verticalmente.

Da direita para a esquerda temos:

1 célula-mãe (L0), identificada pelo código 8_16h, quadrada, com h₀=1048.58 km de lado (área de 1099511.63 km²);

2 células L0.5, filhas da 7: 7Q, 7G; retangulares, com lados h₀ × h₀/2 = 1048.58 km × 524,29 km (área de 549756 km²);

4 células L1, filhas da 6: 6H, 6M, 6R, 6V; quadradas, com lados h₀/2 = 524,29 km × 1048.58 km (área de 274878 km²);

16 células L2, filhas da 5: 50, 51, 52, 53, ..., , 5f; quadradas, com h₀/4 = 262.14 km (área de 68720 km²).

A Base32nvu faz uso de um subconjunto do sistema completo de grades, com níveis múltiplos de dois e meio: L0, L2.5, L5, L7.5, L10, ... Não possuindo representação textual para outros níveis, portanto não é perfeitamente hierárquico. A Base32nvu garante a hierarquia apenas por reconhecer os zeros a esquerda. Devido à intercalação entre níveis inteiros e níveis-meio, alterna quadrados e retângulos: