2 402
edições
(→Ilustrando em geocódigos: melhor explicação) |
|||
(21 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 3: | Linha 3: | ||
[[Cadeia de bits|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 [[wikipedia:Positional notation|notação posicional em base ''N'']], mais compacta que a representação binária para qualquer ''N''>2. | [[Cadeia de bits|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 [[wikipedia:Positional notation|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: | A notação numérica pode ser facilmente adaptada para expressar códigos naturais, basta permitir zeros a esquerda. Exemplos: | ||
{| class="wikitable" | {| class="wikitable" | ||
Linha 9: | Linha 9: | ||
|'''Código''' | |'''Código''' | ||
|'''''Número''''' | |'''''Número''''' | ||
| | |||
|'''Código''' | |'''Código''' | ||
|'''''Número''''' | |'''''Número''''' | ||
|- | |- | ||
|[[wikipedia:Binary number|Base 2. Binária]] / Ilegível ||<code> | |[[wikipedia:Binary number|Base 2. Binária]] / Ilegível ||<code>000000010010</code>||''10010'' || ||<code>1111</code> || ''1111'' | ||
|- | |- | ||
|[[wikipedia:Quaternary numeral system|Base 4. Quaternaria]] / Melhorou! ||<code> | |[[wikipedia:Quaternary numeral system|Base 4. Quaternaria]] / Melhorou! ||<code>000102</code>||''102'' || ||<code>33</code> || ''33'' | ||
|- | |- | ||
|[[wikipedia:Hexadecimal|Base 16. Hexadecimal]] / | |[[wikipedia:Hexadecimal|Base 16. Hexadecimal]] / Compacta ||<code>012</code>||''12'' || ||<code>f</code> || ''f'' | ||
|} | |} | ||
Notar o exemplo do código {{baseNh|000000010010|2}} que manteve seus zeros a esquerda na sua representação quaternária, {{baseNh|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: | |||
:{| class="wikitable" | :{| class="wikitable" | ||
|'''Base2''' || <code>0</code> || <code>00</code> || <code>0000</code> || <code>010</code> || <code>1010</code> || <code>10100</code> | |'''Base2''' || '''<code>0</code>''' <br/><small>(1 dígito)</small>|| '''<code>00</code>''' <br/><small>(2 dígitos)</small> || '''<code>0000</code>''' <br/><small>(4 dígitos)</small>|| '''<code>010</code>''' <br/><small>(3 dígitos)</small> || '''<code>1010</code>''' <br/><small>(4 dígitos)</small> || '''<code>10100</code>''' <br/><small>(5 dígitos)</small> || '''<code>010100</code>''' <br/><small>(6 dígitos)</small> || '''<code>00010100</code>''' <br/><small>(8 dígitos)</small> | ||
|- | |- | ||
|'''Base4''' || ? || <code>0</code> || <code>00</code> || ? || <code>22</code> || ? | |'''Base4''' || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>0</code> || <code>00</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>22</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>110</code>|| <code>0110</code> | ||
|- | |- | ||
|'''Base16''' || ? || ? || <code>0</code> || ? || <code>a</code> || ? | |'''Base16''' || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>0</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>a</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code style="color:red;font-size: x-large; font-weight:bold">?</code> || <code>14</code> | ||
|} | |} | ||
O código {{baseNh|010|2}} não pode ser representado na base 4 pois se permitíssimos algo como "{{baseNh|02|4}}" seria confundido com o binário {{baseNh|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 == | == Definição == | ||
Linha 163: | Linha 166: | ||
==== Base 32 ==== | ==== Base 32 ==== | ||
Ver [[wikipedia:Base 32]]. Para aplicações que requerem maior grau de compactação, a base 32 é a potência de 2 que se encontra | Ver [[wikipedia:Base 32]] e [[#Base_N|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 64 é o limite alfanumérico (10 + 26*2 + 2 caracteres ASCII usuais). | * ''base 36'' é o limite alfanumérico resiliente, onde não há confusão entre maiúsculas e minúsculas.<br/>É 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).<br/>É 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 [[#Base N|tabela acima]]: ''base32hex'', ''base32ghs'', ''base32nvu'' e ''base32rfc''. | |||
=== Base Nh === | === Base Nh === | ||
Linha 361: | Linha 368: | ||
Exemplo: para converter <code>0010100101</code> em Base16h, divida em <code>part[0]=00101001</code> de blocos de 4 bits desde o início, e <code>part[1]=01</code>, dos bits restantes. Converta <code>parte[0]</code> em hexadecimal comum (<code>00101001</code> é “29”) e <code>part[1]</code> pela tabela JSON acima (<code>01</code> é “M”), resultando em “29M”. | Exemplo: para converter <code>0010100101</code> em Base16h, divida em <code>part[0]=00101001</code> de blocos de 4 bits desde o início, e <code>part[1]=01</code>, dos bits restantes. Converta <code>parte[0]</code> em hexadecimal comum (<code>00101001</code> é “29”) e <code>part[1]</code> pela tabela JSON acima (<code>01</code> é “M”), resultando em “29M”. | ||
=== Encode e decode Nh === | |||
A seguir os algoritmos completos, expressos como funções [[wikipedia:PL/pgSQL|linguagem PLpgSQL]]: "''encode''" codifica em base Nh, e "''decode''" decodifica a base Nh. | |||
No [[wikipedia:SQL:1992|padrão SQL:1992]] a representação interna em [[cadeia de bits]] foi denominada ''BIT VARYING'', sendo [[wikipedia:SQL:2003|descontinuada em 2003]]. No PostgreSQL, todavia, [https://www.postgresql.org/docs/current/datatype-bit.html o tipo de dado] e seus [https://www.postgresql.org/docs/current/functions-bitstring.html 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 <code>vbit_to_baseh()</code> e <code>baseh_to_vbit()</code>, com implementação completa no [https://git.osm.codes/NaturalCodes/tree/main/src-sql SQL-schema NatCode]. A seguir os algoritmos simplificados. | |||
Função simplificada de "encode bitstring", converte uma cadeia de bits em texto base-h. | |||
<syntaxhighlight lang="sql"> | |||
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; | |||
</syntaxhighlight> | |||
Função geral de "decode base Nh". Converte o texto base-h para sua representação interna ''bitstring''. | |||
<syntaxhighlight lang="sql"> | |||
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; | |||
</syntaxhighlight> | |||
== Ilustrando em geocódigos == | == Ilustrando em geocódigos == | ||
Linha 368: | Linha 479: | ||
[[Arquivo:GGeohash-ilustra4.png|centro|720x720px]] | [[Arquivo:GGeohash-ilustra4.png|centro|720x720px]] | ||
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 ''M'', a Base 16h resultará em um '''sistema completo de grades''', com ''M''×2-1 níveis. | 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. | 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. | ||
[[Arquivo:XY-FlippedVertically.png|centro|semmoldura| | [[Arquivo:XY-FlippedVertically.png|centro|semmoldura|480px]] | ||
[[Arquivo:BR-SciCode-Base16h.png|centro|720x720px]] | [[Arquivo:BR-SciCode-Base16h.png|centro|720x720px]] |
edições