Código Natural/Notação posicional
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, por exemplo no tratamento dos zeros a esquerda, importante diferenciador de códigos.
E existem ainda códigos que não podem ser representados em certas bases. Por exemplo o código 010
a rigor não pode ser representado na base 4. Uma representação alternativa, base 4h, permite e é definida a seguir.
Definição
O conjunto dos números naturais de k bits, por exemplo, pode ter seus elementos representados pela base 3, base 4, ..., até base N, com .
O conjunto dos códigos naturais de zero a k bits, , 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 e valores de u múltiplos de ; mapeados no conjunto 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 .
Por exemplo base 4 permite valores de u restritos por , portanto permite representar o conjunto de códigos com u par: . Quanto à notação textual, nesta Wiki distinguimos o código007
8≠7
8 do número [007]8=[7]8 pelo uso dafonte
e dos colchetes.
- Códigos base Nh: permite a representação de todos os códigos naturais , ou seja, além de permite a representação de todos os códigos .
O sufixo "h" significa “hiearchycal”, pois a base Nh também preserva a hierarquia do código natural. Na prática, a base está limitada a , ou seja bases 2h, 4h, 8h e 16h; por não haverem convenções para bases maiores, nem hierarquia fora das potências de dois.
Em particular, para N=2 o termo base 2h é preferido. Como , todos os códigos naturais possuem representação base 2: . Portanto os conjuntos de códigos base 2h e base 2 são equivalentes.
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 log2 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, ab12T000000000111 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, , é 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.
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]4 e [01]2h=[1]4. 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=[?]4 ; [1]2h=[?]4 ; [000]2h=[?]4. 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 X4.
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
).
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 h0=1048.58 km de lado (área de 1099511.63 km²);
- 2 células L0.5, filhas da
7
:7Q
,7G
; retangulares, com lados h0 × h0/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 h0/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 h0/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: