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