Código Natural/Notação posicional

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

A notação posicional em base-Nh para a representação compacta de códigos naturais é um modo de representação, adaptado das convenções da notação posicional numérica. Por exemplo o código 0125_8h não deve ser confundido com o número 125 decimal: a base não é 10 e por ter sufixo "h", 8h, deve ser interpretado como código, com seus zeros a esquerda.

O sufixo "h" significa “hiearchycal”, e uma notação Nh preserva a hierarquia do código natural expresso em cadeia de bits. A base 8h por exemplo é análoga da base 8 numérica (octal) e permite a expressão octal de qualquer cadeia de bits.

Para não confundir o "agente 7" com o "agente 007" destacamos 007_10rh. O sufixo "rh" na base significa “restricted hiearchy”, pois ao permitir zeros a esquerda está permitindo também a expressão de hierarquias, porém, restrita por não comportar todos os códigos naturais na base 10 (de fato não existe base 10h somente 10rh).

Bases padronizadas

Alfabetos e convenções da notação. 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	label	ID	bits	alphabet (depois do espaço os nhDigits)	Reference standard
2	h*	base2h	1	`01`	ECMA-262
4	js	base4js	2	`0123`	ECMA-262
4	h	base4h	2	`0123 GQ`	ECMA + nhDigits alphabet
8	js	base8js	3	`01234567`	ECMA-262
8	h	base8h	3	`01234567 GQ HMRV`	ECMA + nhDigits alphabet
16	js	base16js	4	`0123456789abcdef`	ECMA-262 and RFC 4648/sec8
16	h	base16h	4	`0123456789abcdef GQ HMRV JKNPSTZY`	ECMA + nhDigits alphabet
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 são exemplifiados em cada notação.

base ID	007, 33, ab12T
base2js	`007`_2h, `33`_2h e `ab12T`_2h
base4js	`007`_4js, `33`_4js e `ab12T`_4js
base4h	`007`_4h, `33`_4h e `ab12T`_4h
base8js	`007`_8js, `33`_8js e `ab12T`_8js
base8h	`007`_8h, `33`_8h e `ab12T`_8h
base16js	`007`_16js, `33`_16js e `ab12T`_16js
base16h	`007`_16h, `33`_16h e `ab12T`_16h
base32hex	`007`_32hex, `33`_32hex e `ab12T`_32hex
base32ghs	`007`_32ghs, `33`_32ghs e `ab12T`_32ghs
base32nvu	`007`_32nvu, `33`_32nvu e `ab12T`_32nvu
base32rfc	`007`_32rfc, `33`_32rfc e `ab12T`_32rfc
base64url	`007`_64url, `33`_64url e `ab12T`_64url
base64rfc	`007`_64rfc, `33`_64rfc e `ab12T`_64rfc

Bases h

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.

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.

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

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:

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 1048.58 km de lado (área de 1099511.63 km²);

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

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

16 células L2, filhas da 5: 50, 51, 52, 53, ..., , 5f; quadradas, com 262.14 km de lado (área de 68719.48 km²).