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

17 342 bytes adicionados ,  25 janeiro
m
→‎Ilustrando em geocódigos
 
(40 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 1: Linha 1:
[[Arquivo:Code-PositionalNotation-Terms.png|miniaturadaimagem|300px|Termos utilizados na notação posicional de códigos. Em texto: {{baseNh|0125|8h}} ou  [0125]<sub>8h</sub>.]]
[[Arquivo:Code-PositionalNotation-Terms.png|miniaturadaimagem|300px|Termos utilizados na notação posicional de códigos. Em texto: {{baseNh|0125|8h}}.]]


A '''notação posicional em base-Nh''' para a representação compacta de [[código natural|códigos naturais]] é um modo de representação, adaptado das convenções da [[wikipedia:Positional notation|notação posicional numérica]]. Por exemplo o código {{baseNh|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.
[[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&nbsp;''N'']], mais compacta que a representação binária para qualquer&nbsp;''N''>2.  


O sufixo "h" significa “''h''iearchycal”, e uma notação N''h'' preserva a hierarquia do código natural expresso em [[cadeia de bits]]. A base 8''h'' por exemplo é análoga da [[wikipedia:Octal|base 8]] numérica (octal) e permite a expressão octal de qualquer cadeia de bits.
A notação numérica pode ser facilmente adaptada para expressar códigos naturais, basta permitir zeros a esquerda. Exemplos:


Para não confundir o "agente 7" com o "agente 007" destacamos {{baseNh|007|10rh}}. O sufixo "rh" na base significa “''r''estricted ''h''iearchy”, 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 10''h'' somente 10''rh'').
{| class="wikitable"
|'''Notação / Característica'''
|'''Código'''
|'''''Número'''''
|
|'''Código'''
|'''''Número'''''
|-
|[[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>000102</code>||''102'' || ||<code>33</code> || ''33''
|-
|[[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"
|'''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 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 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 ==
Para distinguir a notação numérica binária, por exemplo [010]<sub>2</sub>=[10]<sub>2</sub>, da notação posicional para códigos binários e cadeias de bits, foi convencionado o uso da base 2h, por exemplo {{baseNh|010|2h}}≠{{baseNh|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 <math>P_k</math> dos números naturais de ''k''&nbsp;bits pode ter seus elementos representados por base&nbsp;2, base&nbsp;3, base&nbsp;4, ..., até base&nbsp;''N'', com&nbsp;<math>N \le 2^k</math>.
 
O conjunto dos [[Código natural|códigos naturais de zero a ''k''&nbsp;bits]], <math>X_k = P_k \cup X_{k-1}</math>, 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''&nbsp;bits, com <math>u \le k</math> e valores de ''u'' múltiplos de <math>log_2(N)</math>. Os códigos são representados através de números, mapeando-se o conjunto <math>\bigcup P_u</math> 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 <math>c=log_2(N)</math>, e a restrição dos múltiplos pode ser expressa como <math>u~\bmod c = 0</math>. É 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 [https://tc39.es/ecma262/multipage/text-processing.html#sec-string.prototype.padstart ''padstart''()] ([https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/padStart ex.]). <br/>Exemplo. A base&nbsp;4 (''c''=2) permite valores de ''u'' restritos por <math>u~\bmod~2 = 0</math>, portanto permite representar o conjunto de códigos com ''u'' par: <math>P_0  \cup  P_2  \cup  P_4 \cup \dots \cup P_k</math>. Quanto à notação textual, nesta Wiki distinguimos o código {{baseNh|007|8}}≠{{baseNh|7|8}} do número [007]<sub>8</sub>=[7]<sub>8</sub> pelo uso da <code>fonte</code> e dos colchetes.<br/>Exemplo.  O código {{baseNh|000000111|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]<sub>2</sub>=[111]<sub>2</sub>=[7]<sub>8</sub>. Em seguida o número precisa ser formatado como código de <math>u/c=9/3=3</math> dígitos, o que resulta na representação de código {{baseNh|007|8}}. <br/>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'', <math>v=\lceil log_2(x) \rceil</math>, pode ser comparada com  ''u'', indicando que são necessários <math>(u-v)/c</math> zeros a esquerda. No exemplo ''x''=7 e ''v''=3, portanto são necessários <math>(u-v)/c=6/3=2</math> zeros à esquerda de [7]<sub>8</sub>.
 
* '''Códigos base Nh''':  além de permitir a representação dos elementos de  <math>P_k</math>, permite a dos elementos de <math>X_{k-1}</math>; ou seja, permite a representação de todos os códigos naturais <math>X_k</math>. É detalhada abaixo nas seções [[Código_natural/Notação_posicional#Base_Nh|Base Nh]] e [[Código_natural/Notação_posicional#Algoritmos_base_h|Algoritmos base h]]. <br/>A base&nbsp;Nh também preserva a hierarquia do código natural. Na prática <math>N \in \{2,4,8,16\}</math> 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 [https://www.rfc-editor.org/info/rfc4648 RFC&nbsp;4648], com escopo na conversão de bytes (base256)  em baseN, oferece um padrão adequado para <math>N \in \{16, 32, 64\}</math>, 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&nbsp;2h e base&nbsp;2 são equivalentes. Convenciona-se base&nbsp;2h como canônica (preferível). A equivalência decorre de <math>log_{2}(2) = 1</math>, implicando que todos os códigos naturais <math>X_k</math> possuem representação base&nbsp;2: <math>X_k = P_0 \cup P_1 \cup P_2 \cup \dots \cup P_k</math>.
 
== 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 [[Wikipedia:Positional notation|conversão de base]], para as “bases potência de 2”.  


== Bases padronizadas ==
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 [[Wikipedia:Binary logarithm|log<sub>2</sub>]] da base. No alfabeto foram destacados os ''nhDigits'' (''non-hierarchical digits'') conforme notação [[Código natural|Natural Code]].


Alfabetos e convenções da notação. Lista completa de IDs com respectivos alfabetos-padrão para [[Wikipedia:Positional notation|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 [[Wikipedia:Binary logarithm|log<sub>2</sub>]] da base. No alfabeto foram destacados os ''nhDigits'' (''non-hierarchical digits'') conforme notação [[Código natural|Natural Code]].
===  Base N ===


{| class="wikitable"
:{| class="wikitable"
|'''base'''
|'''base'''
|'''label'''
|'''label'''
|'''ID'''
|'''ID'''
|'''bits'''
|'''bits'''
|'''alphabet''' (depois do espaço os ''nhDigits'')
|'''alphabet'''
|'''Reference standard'''
|'''Reference standard'''
|-
|2
|h*
|''base2h''
|1
|<code>01</code>
|ECMA-262
|-
|-
|4
|4
Linha 31: Linha 68:
|2
|2
|<code>0123</code>
|<code>0123</code>
|ECMA-262
|{{xref|ECMA-262}}
|-
|4
|h
|''base4h''
|2
|<code>0123 GQ</code>
|ECMA + nhDigits alphabet
|-
|-
|8
|8
Linha 46: Linha 76:
|<code>01234567</code>
|<code>01234567</code>
|ECMA-262
|ECMA-262
|-
|8
|h
|''base8h''
|3
|<code>01234567 GQ HMRV</code>
| ECMA + nhDigits alphabet
|-
|-
|16
|16
Linha 60: Linha 83:
|<code>0123456789abcdef</code>
|<code>0123456789abcdef</code>
|ECMA-262 and <nowiki>RFC 4648</nowiki>/sec8
|ECMA-262 and <nowiki>RFC 4648</nowiki>/sec8
|-
|16
|h
|''base16h''
|4
|<code>0123456789abcdef GQ HMRV JKNPSTZY</code>
|ECMA + nhDigits alphabet
|-
|-
|32
|32
Linha 115: Linha 131:
Exemplos. Os códigos {{baseNh|007|10rh}}, {{baseNh|33|4h}} e  {{baseNh|ab12T|16h}}, abaixo exemplifiados em cada notação:
Exemplos. Os códigos {{baseNh|007|10rh}}, {{baseNh|33|4h}} e  {{baseNh|ab12T|16h}}, abaixo exemplifiados em cada notação:


{| class="wikitable"
:{| class="wikitable"
|'''base ID'''
|'''base ID'''
|'''007''', '''33''', '''ab12T'''
|'''007''', '''33''', '''ab12T'''<br/>{{baseNh|000000000111|2h}}, {{baseNh|1111|2h}} e  {{baseNh|1010101100010010101|2h}}
|-
|''base2js''
| {{baseNh|000000000111|2h}}, {{baseNh|1111|2h}} e  {{baseNh|1010101100010010101|2h}}
|-
|-
|''base4js''
|''base4js''
| {{baseNh|000013|4js}}, {{baseNh|33|4js}} e  {{baseNh|?|4js}}
| {{baseNh|000013|4js}}, {{baseNh|33|4js}} e  {{baseNh|?|4js}}
|-
|''base4h''
| {{baseNh|000013|4h}}, {{baseNh|33|4h}} e  {{baseNh|222301022q|4h}}
|-
|-
|''base8js''
|''base8js''
| {{baseNh|0007|8js}}, {{baseNh|?|8js}} e  {{baseNh|?|8js}}
| {{baseNh|0007|8js}}, {{baseNh|?|8js}} e  {{baseNh|?|8js}}
|-
|''base8h''
| {{baseNh|0007|8h}}, {{baseNh|7q|8h}} e  {{baseNh|526112q|8h}}
|-
|-
|''base16js''
|''base16js''
| {{baseNh|007|16js}}, {{baseNh|f|16js}} e  {{baseNh|?|16js}}
| {{baseNh|007|16js}}, {{baseNh|f|16js}} e  {{baseNh|?|16js}}
|-
|''base16h''
| {{baseNh|007|16h}}, {{baseNh|33|16h}} e  {{baseNh|ab12T|16h}}
|-
|-
|''base32hex''
|''base32hex''
Linha 162: Linha 165:
A interrogação, "<code>?</code>", indica que a representação da cadeia de bits daquele tamanho  não existe naquela base.
A interrogação, "<code>?</code>", indica que a representação da cadeia de bits daquele tamanho  não existe naquela base.


=== Bases h ===
==== Base 32 ====
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 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 ===


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 [[cadeia de bits|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?  
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 [[cadeia de bits|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.
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.
:{| class="wikitable"
|'''base'''
|'''label'''
|'''ID'''
|'''bits'''
|'''alphabet''' (depois do espaço os ''nhDigits'')
|'''Reference standard'''
|-
|2
|h
|''base2h''
|1
|<code>01</code>
|{{xref|ECMA-262}}
|-
|4
|h
|''base4h''
|2
|<code>0123 GQ</code>
|ECMA + nhDigits alphabet
|-
|8
|h
|''base8h''
|3
|<code>01234567 GQ HMRV</code>
| ECMA + nhDigits alphabet
|-
|16
|h
|''base16h''
|4
|<code>0123456789abcdef GQ HMRV JKNPSTZY</code>
|ECMA + nhDigits alphabet
|}
Exemplos. Os códigos {{baseNh|007|10rh}}, {{baseNh|33|4h}} e  {{baseNh|ab12T|16h}}, abaixo exemplifiados em cada notação:
:{| class="wikitable"
|'''base ID'''
|'''007''', '''33''', '''ab12T'''
|-
|''base2h''
| {{baseNh|000000000111|2h}}, {{baseNh|1111|2h}} e  {{baseNh|1010101100010010101|2h}}
|-
|''base4h''
| {{baseNh|000013|4h}}, {{baseNh|33|4h}} e  {{baseNh|222301022q|4h}}
|-
|''base8h''
| {{baseNh|0007|8h}}, {{baseNh|7q|8h}} e  {{baseNh|526112q|8h}}
|-
|''base16h''
| {{baseNh|007|16h}}, {{baseNh|33|16h}} e  {{baseNh|ab12T|16h}}
|}


==Bases de interesse prático==
==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]].
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 [https://www.rfc-editor.org/rfc/rfc4648 RFC&nbsp;4648], sendo a base 16 a de uso mais amplo e consolidado.


A rigor a base mais simples para a representação de geocódigos é a base 4, pois cada célula é subdividida em 4&nbsp;células-filhas.
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]].


[[Arquivo:Osmc-refinamentoQuadrada-v2.png|centro|620px]]
A base&nbsp;2 (binária) é a mais fundamental, com dígitos de 1&nbsp;bit. A base&nbsp;2 é fundamental nos sistemas digitais: <blockquote>apenas ''bases&nbsp;N'', com ''N'' sendo uma [[wikipedia:Power of two|potência de&nbsp;2]], <math>N \in \{2^2, 2^3, 2^4, ...\}</math>, é que terão dígitos fazendo uso integral dos bits que os representam.<br/>Por exemplo a ''base&nbsp;10'' do sistema numérico decimal usual, requer 4&nbsp;bits por dígito, descartando informação (usa valores 0&nbsp;a&nbsp;9 e descarta 10&nbsp;a&nbsp;15).</blockquote>
 
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&nbsp;''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 [[wikipedia:Uniform Resource Identifier|URI]] e [[Geo URI]]. Segundo a RFC&nbsp;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&nbsp;letras do alfabeto mais dígitos 0&nbsp;a&nbsp;9, resultando no máximo de 36&nbsp;caracteres. As tentativas de uso da base&nbsp;64 falham principalmente pela dificuldade do ser humano em distinguir maiúsculas e minúsculas. Há portanto o requisito de<blockquote>N≤36</blockquote>
 
As bases mais compactas portanto ficam restritas às potências de dois menores que 36, ou seja,  <math>N \in \{4, 8, 16, 32\}</math>. Voltando ao critério subjetivo, as bases desse conjunto, com máxima compressão, são base&nbsp;16 e base&nbsp;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&nbsp;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&nbsp;células-filhas. Supondo uma célula-mãe identificada como "A", podemos batizar as suas filhas com sufixos base4 conforme ilustrado:
 
[[Arquivo:OSMC-refinamentoCelulaQuadrada1.png|centro|620px]]


Os dígitos da ''base&nbsp;4'' ocupam 2&nbsp;bits, e sua representação geométrica é sempre simétrica &mdash; se a célula de nível  ''L''0 for quadrada, as células rotuladas por geocódigos da base&nbsp;4 também serão sempre quadradas.  
Os dígitos da ''base&nbsp;4'' ocupam 2&nbsp;bits, e sua representação geométrica é sempre simétrica &mdash; se a célula de nível  ''L''0 for quadrada, as células rotuladas por geocódigos da base&nbsp;4 também serão sempre quadradas.  


A base&nbsp;4 é importante, tem aplicação relevante por ser essencial à representação de geocódigos. Será que outra base ''N'', com ''N'' menor ou maior&nbsp;que&nbsp;4 terá também aplicação nesse contexto? 
A base&nbsp;4 é essencial nesta aplicação, analisaremos agora se outras bases podem ser úteis. Tentaremos responder à pergunta<br/>&nbsp; Será que outra base&nbsp;''N'', com ''N''≠4, terá também aplicação nesse contexto?
 
''N''≠4
 
A base&nbsp;2 (binária) é a mais fundamental, com dígitos de 1&nbsp;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&nbsp;N'' com ''N''≥4.
 


A base&nbsp;2 (binária) é a mais fundamental, com dígitos de 1&nbsp;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&nbsp;N'' com ''N''≥4. A base&nbsp;2 todavia é fundamental nos sistemas digitais: apenas ''bases&nbsp;N'' com N≥4 pertencendo ao conjunto das potências de&nbsp;2, <math>N \in \{2^2, 2^3, 2^4, ...\}</math>, é que terão dígitos fazendo uso integral dos bits que os representam. Por exemplo a ''base&nbsp;10'' do sistema numérico decimal usual, requer 4&nbsp;bits por dígito, descartando informação (usa valores 0&nbsp;a&nbsp;9 e descarta 10&nbsp;a&nbsp;15).
A base&nbsp;2 todavia é fundamental nos sistemas digitais: apenas ''bases&nbsp;N'' com N≥4 pertencendo ao conjunto das potências de&nbsp;2, <math>N \in \{2^2, 2^3, 2^4, ...\}</math>, é que terão dígitos fazendo uso integral dos bits que os representam. Por exemplo a ''base&nbsp;10'' do sistema numérico decimal usual, requer 4&nbsp;bits por dígito, descartando informação (usa valores 0&nbsp;a&nbsp;9 e descarta 10&nbsp;a&nbsp;15).


Iniciamos em ''N''=4, e daí em diante os geocódigos serão úteis se compatíveis com a ''base&nbsp;4'' e a ''base&nbsp;2''. Resumindo os '''requisitos''' que justificamos até aqui:<blockquote>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. <br />Portanto ''N'' no conjunto {4, 8, 16,&nbsp;64,&nbsp;…}</blockquote>
Iniciamos em ''N''=4, e daí em diante os geocódigos serão úteis se compatíveis com a ''base&nbsp;4'' e a ''base&nbsp;2''. Resumindo os '''requisitos''' que justificamos até aqui:<blockquote>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. <br />Portanto ''N'' no conjunto {4, 8, 16,&nbsp;64,&nbsp;…}</blockquote>
O valor de ''N'' todavia tem um limite superior bem conhecido para o alfabeto das línguas ocidentais: 26&nbsp;letras do alfabeto mais dígitos 0&nbsp;a&nbsp;9, resultando no máximo de 36&nbsp;caracteres. As tentativas de uso da base&nbsp;64 falham principalmente pela dificuldade do ser humano em distinguir maiúsculas e minúsculas. Há portanto o requisito de<blockquote>N≤36</blockquote>As bases mais compactas portanto ficam restritas a <math>N \in \{8, 16\}</math> onde o máximo, '''para máxima compressão, é o&nbsp;16'''. A&nbsp;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&nbsp;experiência com a tecnologia [[wikipedia:Geohash|Geohash clássica]] demonstrou que, apesar de envolver grades degeneradas, nas aplicações logísticas o ''base&nbsp;32'' seria uma alternativa. Ela não chega a ser totalmente incompatível com a ''base&nbsp;4'': geocódigos ''base&nbsp;32'' com quantidade de dígitos par (2,&nbsp;4, 6,&nbsp;etc.) são compatíveis. A&nbsp;ilustração abaixo mostra o "bate" entre a quantidade de bits, há compatibilidade para múltiplos de&nbsp;10.
Para algumas aplicações, todavia, como a adoção do geocódigo como [[código postal]], maior compressão é solicitada. A&nbsp;experiência com a tecnologia [[wikipedia:Geohash|Geohash clássica]] demonstrou que, apesar de envolver grades degeneradas, nas aplicações logísticas o ''base&nbsp;32'' seria uma alternativa. Ela não chega a ser totalmente incompatível com a ''base&nbsp;4'': geocódigos ''base&nbsp;32'' com quantidade de dígitos par (2,&nbsp;4, 6,&nbsp;etc.) são compatíveis. A&nbsp;ilustração abaixo mostra o "bate" entre a quantidade de bits, há compatibilidade para múltiplos de&nbsp;10.
Linha 194: Linha 288:


Por fim, por garantir a representação "humanamente legível" de todas as grades,  a ''base&nbsp;16h'' é adotada como canônica dos geocódigos. Sua representação geométrica é ilustra abaixo.
Por fim, por garantir a representação "humanamente legível" de todas as grades,  a ''base&nbsp;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:
# <math>N \in \{2^1, 2^2, 2^3, 2^4, ...\}</math>. 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.
# <math>N \le 36</math> é 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.).
# <math>N=4</math> é válido. A ''base&nbsp;4'' tem aplicação fundamental em [[GGeohash]].
# <math>N > 4</math> é desejado, pois queremos representações mais compactas.
# Flexibilização: satisfazer apenas axioma-1 e axioma-2, deixando os demais axiomas como eventuais. <br/>O GGeohash permite grades degeneradas, então se uma certa base&nbsp;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 <math>N \in \{4^2, 4^3, ...\} = \{2^4, 2^6, 2^8, ...\} = \{16, 64, 256, ...\} </math>. 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 <math>N \in \{16\}</math>.
Obtemos uma solução, a base&nbsp;16 é a eleita, mas esperávamos mais de uma solução (!). Voltando ao axioma-5, entendemos que a flexibilização permitiria usar <math>N \in \{2, 4, 8, 16, 32 \}</math>.
De fato, é o que foi tecnicamente possível e padronizamos: bases 2h, 4h, 8h e 16h, e a base&nbsp;32. Para N=32 não temos uma "base 32h" porque as extensões "h" requerem ao todo um alfabeto de <math>N \times 2-2</math>, o que, para N=32 resultaria em 62, excedendo o limite de 36.


== Algoritmos base h ==
== Algoritmos base h ==
Linha 257: 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 264: 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:
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.
 
''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. Para qualquer que seja o nível máximo ''N'', a Base&nbsp;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.
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]]
Linha 284: Linha 497:
*16 células ''L2'', filhas da <code>5</code>:  <code>50</code>, <code>51</code>, <code>52</code>, <code>53</code>, ..., , <code>5f</code>; quadradas, com  ''h''<sub>0</sub>/4 = 262.14 km (área de 68720 km²).
*16 células ''L2'', filhas da <code>5</code>:  <code>50</code>, <code>51</code>, <code>52</code>, <code>53</code>, ..., , <code>5f</code>; quadradas, com  ''h''<sub>0</sub>/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'',&nbsp;''L2.5'', ''L5'', ''L7.5'', ''L10'',&nbsp;... 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:
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'',&nbsp;''L2.5'', ''L5'', ''L7.5'', ''L10'',&nbsp;... 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:


[[Arquivo:Base32nvu-firstDivs.png|centro|semmoldura|820px]]
[[Arquivo:Base32nvu-firstDivs.png|centro|semmoldura|820px]]
[[Categoria:Código natural]]
Peter
2 402

edições

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