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, basta permitir zeros a esquerda. Exemplos:
Notação / Característica | Código | Número | Código | Número | |
Base 2. Binária / Ilegível | 000000010010 |
10010 | 1111 |
1111 | |
Base 4. Quaternaria / Melhorou! | 000102 |
102 | 33 |
33 | |
Base 16. Hexadecimal / Compacta | 012 |
12 | f |
f |
Notar o exemplo do código 000000010010
2 que manteve seus zeros a esquerda na sua representação quaternária, 000102
4. Os zeros a esquerda são importantes diferenciadores dos códigos, todavia existem restrições. Existem códigos binários que não podem ser representados nas bases numéricas usuais. Exemplos:
Base2 0
(1 dígito)00
(2 dígitos)0000
(4 dígitos)010
(3 dígitos)1010
(4 dígitos)10100
(5 dígitos)010100
(6 dígitos)00010100
(8 dígitos)Base4 ?
0
00
?
22
?
110
0110
Base16 ?
?
0
?
a
?
?
14
O código 010
2 não pode ser representado na base 4 pois se permitíssimos algo como "02
4" seria confundido com o binário 0010
2. Assim nas demais interrogações da base 4, apenas os binários com uma quantidade par de dígitos (2, 4 e 6) podem ser representados. As interrogações da base 16 surgem quando a quantidade de dígitos binários não é divisível por quatro — temos interrogações em 1, 2, 3, 5 ou 6 dígitos binários.
Definição
Para distinguir a notação numérica binária, por exemplo [010]2=[10]2, 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 dos números naturais de k bits pode ter seus elementos representados por base 2, 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: é restrita, permite apenas a representação de códigos de u bits, com e valores de u múltiplos de . Os códigos são representados através de números, mapeando-se o conjunto no conjunto dos números naturais de u bits. Esses números estão representados na base N, onde cada dígito consome c bits, com , e a restrição dos múltiplos pode ser expressa como . É esperado que o código na base N tenha u/c dígitos, de modo que, havendo menos na representação numérica, deve-se preencher com zeros à esquerda. Formalmente, o preenchimento é a função de formatação padstart() (ex.).
Exemplo. A base 4 (c=2) 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.
Exemplo. O código000000111
2 tem comprimento u=9 e pode ser representado na base 8, que tem dígitos de c=3 bits. O código é tomado como número e transformado na base 8: [000000111]2=[111]2=[7]8. Em seguida o número precisa ser formatado como código de dígitos, o que resulta na representação de código007
8.
Nota. Não tem uso prático, mas matematicamente o número de zeros pode ser previsto. A quantidade v de bits do valor numérico x, , pode ser comparada com u, indicando que são necessários zeros a esquerda. No exemplo x=7 e v=3, portanto são necessários zeros à esquerda de [7]8.
- Códigos base Nh: além de permitir a representação dos elementos de , permite a dos elementos de ; ou seja, permite a representação de todos os códigos naturais . É detalhada abaixo nas seções Base Nh e Algoritmos base h.
A base Nh também preserva a hierarquia do código natural. Na prática 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 , 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 , implicando que todos os códigos naturais possuem representação base 2: .
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, ab12T 000000000111
2h,1111
2h e1010101100010010101
2hbase4js 000013
4js,33
4js e?
4jsbase8js 0007
8js,?
8js e?
8jsbase16js 007
16js,f
16js e?
16jsbase32hex k7
32hex,?
32hex e?
32hexbase32ghs n7
32ghs,?
32ghs e?
32ghsbase32nvu N7
32nvu,?
32nvu e?
32nvubase32rfc UH
32rfc,?
32rfc e?
32rfcbase64url ?
64url,?
64url e?
64urlbase64rfc ?
64rfc,?
64rfc e?
64rfc
A interrogação, "?
", indica que a representação da cadeia de bits daquele tamanho não existe naquela base.
Base 32
Ver wikipedia:Base 32 e acima em Base N as variantes (base32hex, base32ghs, etc.). Para aplicações que requerem maior grau de compactação, a base 32 é a potência de 2 que se encontra ainda abaixo do limite superior. São dois limites, conforme o tipo de aplicação:
- base 36 é o limite alfanumérico resiliente, onde não há confusão entre maiúsculas e minúsculas.
É o limite adotado em aplicações que envolvem interpretação ou comunicação humanas, tais como voz, chat, URLs curtas, aplicações cartoriais, placas, etc. Algumas tecnologias, como QR-Codes também se beneficiam do case-insensitive. Como 36 não é potência de 2 (portanto não é interoperável), o 32 é preferido como máximo.
- base 64 é o limite alfanumérico (10 + 26*2 + 2 caracteres ASCII usuais).
É o limite para aplicações onde é permitida a diferenciação maiúsculas/minúsculas. A bsase32 seria preferível à base64 em códigos de poucos bits, onde o ganho de compactação seja notado, e a oferta de hierarquia tenha um papel importante.
Até o momento foram aceitas apenas 4 "variantes padronizadas", conforme tabela acima: base32hex, base32ghs, base32nvu e base32rfc.
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 e1010101100010010101
2hbase4h 000013
4h,33
4h e222301022q
4hbase8h 0007
8h,7q
8h e526112q
8hbase16h 007
16h,33
16h eab12T
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.
Na discussão a seguir, para justificar a preferência por estas bases, acrescentaremos o contexto de aplicação. Focaremos no contexto da utilização dos Códigos Naturais como geocódigos, principalmente GGeohash.
A base 2 (binária) é a mais fundamental, com dígitos de 1 bit. A base 2 é fundamental nos sistemas digitais:
apenas bases N, com N sendo uma potência 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).
Existe um limite prático para N, tendo em vista que a função precípua de uma base N>2 é proporcionar a visualização do código para os seres humanos. Requisitos subjetivos da base N:
- "quanto mais compacto melhor" (portanto os humanos desejam N o maior possível),
- "a hierarquia precisa ser percebida" (portanto N não pode ser grande demais).
O limite prático, todavia, está nos meios de comunicação: o código base N precisa ser legível e não-ambíguo no meio textual, em voz, e em protocolos internet, tais como URI e Geo URI. Segundo a RFC 4648, a base64 (portanto N≤64) seria o limite superior para esse uso mais amplo.
O critério de não-ambiguidade (resiliência ao "telefone sem fio") 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 às potências de dois menores que 36, ou seja, . Voltando ao critério subjetivo, as bases desse conjunto, com máxima compressão, são base 16 e base 32, regulando-se uma ou outra pelo critério de "ainda expressar hierarquia".
estabelecendo um 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 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 é essencial nesta aplicação, analisaremos agora se outras bases podem ser úteis. Tentaremos responder à pergunta
Será que outra base N, com N≠4, terá também aplicação nesse contexto?
N≠4
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, …}
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.
Resumo formal matemático
Os requisitos e justificativas foram formulados de maneira axiomática, cada item representa um axioma:
- . Apenas potências de 2 são válidas, pois apenas elas garantem a utilização integral da informação carregada por cada dígito da base.
- é o limite superior. Queremos apenas representações alfanuméricas não-ambíguas e legiveis ao humano, válidas para qualquer protocolo ou meio de comunicação usual (voz, texto, URI, etc.).
- é válido. A base 4 tem aplicação fundamental em GGeohash.
- é desejado, pois queremos representações mais compactas.
- Flexibilização: satisfazer apenas axioma-1 e axioma-2, deixando os demais axiomas como eventuais.
O GGeohash permite grades degeneradas, então se uma certa base N permitir a representação de ambas, grades degeneradas e não-degeneradas, será aceitável.
O axioma-5 é uma contradição, ignoremos ele para obter uma primeira conclusão racional.
Do axioma-3 e do axioma-4 concluímos que . As potências de 4 são válidas, conseguem satisfazer o axioma-3 e ao mesmo tempo representar valores de forma mais compacta, satisfazendo o axioma-4. Percebemos que essas potências também satisfazem o axioma-1. Resta portanto aplicar o axioma-2, resultando em .
Obtemos uma solução, a base 16 é a eleita, mas esperávamos mais de uma solução (!). Voltando ao axioma-5, entendemos que a flexibilização permitiria usar .
De fato, é o que foi tecnicamente possível e padronizamos: bases 2h, 4h, 8h e 16h, e a base 32. Para N=32 não temos uma "base 32h" porque as extensões "h" requerem ao todo um alfabeto de , o que, para N=32 resultaria em 62, excedendo o limite de 36.
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”.
Encode e decode Nh
A seguir os algoritmos completos, expressos como funções linguagem PLpgSQL: "encode" codifica em base Nh, e "decode" decodifica a base Nh.
No padrão SQL:1992 a representação interna em cadeia de bits foi denominada BIT VARYING, sendo descontinuada em 2003. No PostgreSQL, todavia, o tipo de dado e seus operadores e funções foram mantidos, sendo abreviado como varbit — e nos nomes de função da biblioteca NatCod abreviada como vbit.
O "encode" é a conversão "vbit to base-h", o "decode" é a conversão "base-h to vbit". Daí os nomes de função vbit_to_baseh()
e baseh_to_vbit()
, com implementação completa no SQL-schema NatCode. A seguir os algoritmos simplificados.
Função simplificada de "encode bitstring", converte uma cadeia de bits em texto base-h.
CREATE FUNCTION natcod.vbit_to_baseh(
p_val varbit, -- input
p_base int DEFAULT 16 -- 16 for base16h (default), 8 for base8h, 4 for base4h or 2 for base2h.
) RETURNS text AS $f$
DECLARE
vlen int;
pos0 int;
ret text := '';
blk varbit;
bits_per_digit int;
tr int[] := '{ {1,2,0,0}, {1,3,4,0}, {1,3,5,6} }'::int[]; -- --4h(bits,pos), 8h(bits,pos)
tr_selected JSONb;
trtypes JSONb := '{"2":[1,1], "4":[1,2], "8":[2,3], "16":[3,4]}'::JSONb;
trpos int;
baseh "char"[] := array[ -- the standards for Baseh:
'[0:15]={G,Q,x,x,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --1. 1 bit in 4h,8h,16h
'[0:15]={0,1,2,3,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --2. 2 bits in 4h
'[0:15]={H,M,R,V,x,x,x,x,x,x,x,x,x,x,x,x}'::"char"[], --3. 2 bits 8h,16h
'[0:15]={0,1,2,3,4,5,6,7,x,x,x,x,x,x,x,x}'::"char"[], --4. 3 bits in 8h
'[0:15]={J,K,N,P,S,T,Z,Y,x,x,x,x,x,x,x,x}'::"char"[], --5. 3 bits in 16h
'[0:15]={0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}'::"char"[] --6. 4 bits in 16h
-- Hexadecimals by standard alphabet of https://tools.ietf.org/html/rfc4648#section-6
]; -- jumpping I,O and L,U,W,X letters.
BEGIN
vlen := bit_length(p_val);
tr_selected := trtypes->(p_base::text);
IF p_base=2 THEN
RETURN $1::text; -- bit string as string
END IF;
bits_per_digit := (tr_selected->>1)::int;
pos0 := (tr_selected->>0)::int;
trpos := tr[pos0][bits_per_digit];
FOR counter IN 1..(vlen/bits_per_digit) LOOP
blk := substring(p_val FROM 1 FOR bits_per_digit);
ret := ret || baseh[trpos][ varbit_to_int(blk,bits_per_digit) ];
p_val := substring(p_val FROM bits_per_digit+1);
END LOOP;
vlen := bit_length(p_val);
IF p_val!=b'' THEN
trpos := tr[pos0][vlen];
ret := ret || baseh[trpos][ varbit_to_int(p_val,vlen) ];
END IF;
RETURN ret;
END
$f$ LANGUAGE PLpgSQL IMMUTABLE;
Função geral de "decode base Nh". Converte o texto base-h para sua representação interna bitstring.
CREATE FUNCTION natcod.baseh_to_vbit(
p_val text, -- input (enforced lower case)
p_base int DEFAULT 16 -- selecting base2h, base4h, base8h, or base16h.
) RETURNS varbit AS $f$
DECLARE
tr_hdig jsonb := '{
"G":[1,0],"Q":[1,1],
"H":[2,0],"M":[2,1],"R":[2,2],"V":[2,3],
"J":[3,0],"K":[3,1],"N":[3,2],"P":[3,3],
"S":[3,4],"T":[3,5],"Z":[3,6],"Y":[3,7]
}'::jsonb;
tr_full jsonb := '{
"0":0,"1":1,"2":2,"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,
"9":9,"a":10,"b":11,"c":12,"d":13,"e":14,"f":15
}'::jsonb;
blk text[];
bits varbit;
n int;
i char;
ret varbit;
BEGIN
ret = '';
blk := regexp_match(p_val,'^([0-9a-f]*)([GHJKMNP-TVZY])?$');
IF blk[1] >'' THEN
FOREACH i IN ARRAY regexp_split_to_array(blk[1],'') LOOP
ret := ret || CASE p_base
WHEN 16 THEN (tr_full->>i)::int::bit(4)::varbit
WHEN 8 THEN (tr_full->>i)::int::bit(3)::varbit
WHEN 4 THEN (tr_full->>i)::int::bit(2)::varbit
END;
END LOOP;
END IF;
IF blk[2] >'' THEN
n = (tr_hdig->blk[2]->>0)::int;
ret := ret || CASE n
WHEN 1 THEN (tr_hdig->blk[2]->>1)::int::bit(1)::varbit
WHEN 2 THEN (tr_hdig->blk[2]->>1)::int::bit(2)::varbit
WHEN 3 THEN (tr_hdig->blk[2]->>1)::int::bit(3)::varbit
END;
END IF;
RETURN ret;
END
$f$ LANGUAGE PLpgSQL IMMUTABLE;
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, conforme a ilustração acima. Para qualquer que seja o nível máximo LM (no exemplo L4 portanto M=4), a Base 16h resultará em um sistema completo de grades, com (M+1)×2-1 níveis.
Abaixo células L0 de cobertura base16 do Brasil, ilustrando caso concreto de grades de diferentes níveis. Elas foram rotuladas pela Curva-Z espelhada verticalmente — a orientação adotada nos eixos resulta em variantes da curva (N e И) e da sua ordenação.
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 base16h é utilizada na chamada "grade científica" do Brasil, ilustrada acima. A representação em base32 também foi adotada no Brasil, para expressar a "grade logística", que requer maior compressão (menos dígitos).
Mais especificamente, foi adotada a Base32nvu. Geometricamente, ela faz uso de um subconjunto da Grade Científica, 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 é um conjunto completo. 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: