Código Natural/Notação posicional
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 log2 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, , é 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 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.