Documentação

Código Natural/Notação posicional: mudanças entre as edições

Página Discussão

Código Natural/Notação posicional (ver código-fonte)

Edição das 23h05min de 25 de janeiro de 2024

6 921 bytes adicionados ,  25 janeiro
m
→‎Ilustrando em geocódigos
 
(19 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>00010010</code>||''10010''  || <code>1111</code> || ''1111''
|[[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>0102</code>||''102'' || <code>33</code> || ''33''
|[[wikipedia:Quaternary numeral system|Base 4. Quaternaria]] / Melhorou! ||<code>000102</code>||''102'' || ||<code>33</code> || ''33''
|-
|-
|[[wikipedia:Hexadecimal|Base 16. Hexadecimal]] / Mais compacta ||<code>12</code>||''12'' || <code>f</code> || ''f''
|[[wikipedia:Hexadecimal|Base 16. Hexadecimal]] / Compacta ||<code>012</code>||''12'' || ||<code>f</code> || ''f''
|}
|}


Alguns cuidados devem ser tomados, como o tratamento dos zeros a esquerda, importante diferenciador de códigos. Notar o exemplo {{baseNh|00010010|2}} que manteve seu zero a esquerda em {{baseNh|0102|4}}. E existem ainda códigos que não podem ser representados em certas bases. Por exemplo o código {{baseNh|010|2}} não pode ser representado na base 4. Se representar como {{baseNh|02|4}}  vai ser confundido com o binário {{baseNh|0010|2}}. Outros exemplos:
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 &mdash; 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 entre os dois limites:
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:
* base36 é o limite alfanumérico resiliente, onde não há confusão entre maiúsculas e minúsculas.
 
* 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'' &mdash; 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'',&nbsp;''L0.5'', ''L1'', ''L1.5'', ''L2'', ''L2.5'', ''L3, L3.5'',&nbsp;''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 ''M'' (no exemplo ''L4'' portanto ''M''=4), a Base&nbsp;16h resultará em um '''sistema completo de grades''', com ''(M+1)''×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'',&nbsp;''L0.5'', ''L1'', ''L1.5'', ''L2'', ''L2.5'', ''L3, L3.5'',&nbsp;''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&nbsp;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 &mdash; a orientação adotada nos eixos resulta em variantes da curva (N e И) e da sua ordenação.


[[Arquivo:XY-FlippedVertically.png|centro|semmoldura|420px]]
[[Arquivo:XY-FlippedVertically.png|centro|semmoldura|480px]]


[[Arquivo:BR-SciCode-Base16h.png|centro|720x720px]]
[[Arquivo:BR-SciCode-Base16h.png|centro|720x720px]]
Peter
2 402

edições

Disponível em “https://wiki.addressforall.org/doc/Especial:MobileDiff/2759...3513”