2 402
edições
m (→Base16h) |
|||
(47 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}} | [[Arquivo:Code-PositionalNotation-Terms.png|miniaturadaimagem|300px|Termos utilizados na notação posicional de códigos. Em texto: {{baseNh|0125|8h}}.]] | ||
[[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, basta permitir zeros a esquerda. Exemplos: | |||
{| 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 — 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'' bits pode ter seus elementos representados por base 2, base 3, base 4, ..., até base ''N'', com <math>N \le 2^k</math>. | |||
O conjunto dos [[Código natural|códigos naturais de zero a ''k'' 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'' 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 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 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 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 2h e base 2 são equivalentes. Convenciona-se base 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 2: <math>X_k = P_0 \cup P_1 \cup P_2 \cup \dots \cup P_k</math>. | |||
{| class="wikitable" | == 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”. | |||
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" | |||
|'''base''' | |'''base''' | ||
|'''label''' | |'''label''' | ||
|'''ID''' | |'''ID''' | ||
|'''bits''' | |'''bits''' | ||
|'''alphabet''' | |'''alphabet''' | ||
|'''Reference standard''' | |'''Reference standard''' | ||
|- | |- | ||
|4 | |4 | ||
Linha 31: | Linha 68: | ||
|2 | |2 | ||
|<code>0123</code> | |<code>0123</code> | ||
|ECMA-262 | |{{xref|ECMA-262}} | ||
|- | |- | ||
|8 | |8 | ||
Linha 46: | Linha 76: | ||
|<code>01234567</code> | |<code>01234567</code> | ||
|ECMA-262 | |ECMA-262 | ||
|- | |- | ||
|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 | ||
|- | |- | ||
|32 | |32 | ||
Linha 113: | Linha 129: | ||
|} | |} | ||
Exemplos | 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}} | ||
|- | |- | ||
|''base4js'' | |''base4js'' | ||
| {{baseNh| | | {{baseNh|000013|4js}}, {{baseNh|33|4js}} e {{baseNh|?|4js}} | ||
|- | |- | ||
|''base8js'' | |''base8js'' | ||
| {{baseNh| | | {{baseNh|0007|8js}}, {{baseNh|?|8js}} e {{baseNh|?|8js}} | ||
|- | |- | ||
|''base16js'' | |''base16js'' | ||
| {{baseNh|007|16js}}, {{baseNh| | | {{baseNh|007|16js}}, {{baseNh|f|16js}} e {{baseNh|?|16js}} | ||
|- | |- | ||
|''base32hex'' | |''base32hex'' | ||
| {{baseNh| | | {{baseNh|k7|32hex}}, {{baseNh|?|32hex}} e {{baseNh|?|32hex}} | ||
|- | |- | ||
|''base32ghs'' | |''base32ghs'' | ||
| {{baseNh| | | {{baseNh|n7|32ghs}}, {{baseNh|?|32ghs}} e {{baseNh|?|32ghs}} | ||
|- | |- | ||
|''base32nvu'' | |''base32nvu'' | ||
| {{baseNh| | | {{baseNh|N7|32nvu}}, {{baseNh|?|32nvu}} e {{baseNh|?|32nvu}} | ||
|- | |- | ||
|''base32rfc'' | |''base32rfc'' | ||
| {{baseNh| | | {{baseNh|UH|32rfc}}, {{baseNh|?|32rfc}} e {{baseNh|?|32rfc}} | ||
|- | |- | ||
|''base64url'' | |''base64url'' | ||
| {{baseNh| | | {{baseNh|?|64url}}, {{baseNh|?|64url}} e {{baseNh|?|64url}} | ||
|- | |- | ||
| ''base64rfc'' | | ''base64rfc'' | ||
| {{baseNh| | | {{baseNh|?|64rfc}}, {{baseNh|?|64rfc}} e {{baseNh|?|64rfc}} | ||
|} | |} | ||
=== | A interrogação, "<code>?</code>", indica que a representação da cadeia de bits daquele tamanho não existe naquela base. | ||
==== 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 | 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 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: <blockquote>apenas ''bases N'', com ''N'' sendo uma [[wikipedia:Power of two|potência de 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 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).</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 ''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 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<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 16 e base 32, regulando-se uma ou outra pelo critério de "ainda expressar hierarquia". | |||
[[Arquivo: | 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: | |||
[[Arquivo:OSMC-refinamentoCelulaQuadrada1.png|centro|620px]] | |||
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 ''L''0 for quadrada, as células rotuladas por geocódigos da base 4 também serão sempre quadradas. | 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 ''L''0 for quadrada, as células rotuladas por geocódigos da base 4 também serão sempre quadradas. | ||
A base 4 é | A base 4 é essencial nesta aplicação, analisaremos agora se outras bases podem ser úteis. Tentaremos responder à pergunta<br/> Será que outra base ''N'', com ''N''≠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, <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 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). | ''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, <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 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:<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, 64, …}</blockquote> | 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:<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, 64, …}</blockquote> | ||
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 [[wikipedia:Geohash|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. | 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 [[wikipedia:Geohash|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. | ||
Linha 190: | Linha 288: | ||
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. | 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: | |||
# <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 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 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 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 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 230: | Linha 345: | ||
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, <code>x0123</code>). | 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, <code>x0123</code>). | ||
[[arquivo:KraEtAll2019-fig11-ordBases.png|thumb|300px|Tabela da representação dos códigos naturais de até 4 bits, em bases 2h, 4h, 8h e, com um dígito, 16h. ]] | |||
O nome desta nova representação é base16h, porque é a “base16 ordinária estendida para hierarquia”: | O nome desta nova representação é base16h, porque é a “base16 ordinária estendida para hierarquia”: | ||
<code>/^([0-9a-f]*)([GHJKMNP-TVZY])?$/</code> | <code>/^([0-9a-f]*)([GHJKMNP-TVZY])?$/</code> | ||
O inverso, para traduzir de uma | 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, | ||
<syntaxhighlight lang="javascript"> | <syntaxhighlight lang="javascript"> | ||
let part = bitString.match(/^((?:[01]{4,4})*)([01]*)$/) | let part = bitString.match(/^((?:[01]{4,4})*)([01]*)$/) | ||
Linha 241: | Linha 358: | ||
<syntaxhighlight lang="json"> | <syntaxhighlight lang="json"> | ||
{ "0":"G", "00":"H", "000":"J", "001":"K", "01":"M", "010":"N", " 011":"P", | { "0":"G", "00":"H", "000":"J", "001":"K", | ||
"1":"Q", "10":"R", "100":"S", "101":"T", "11":"V", "110":"Z", "111 ":"S" | "01":"M", "010":"N", " 011":"P", | ||
"1":"Q", "10":"R", "100":"S", "101":"T", | |||
"11":"V", "110":"Z", "111 ":"S" | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
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 <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 == | |||
* 2 células ''L0.5'', filhas da <code>7</code>: <code>7Q</code>, <code>7G</code>; retangulares, com lados 524,29 km × 1048.58 km (área de | 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 <code>82</code>. 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: | ||
[[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, 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. | |||
[[Arquivo:XY-FlippedVertically.png|centro|semmoldura|480px]] | |||
[[Arquivo:BR-SciCode-Base16h.png|centro|720x720px]] | |||
Da direita para a esquerda temos: | |||
*1 célula-mãe (''L0''), identificada pelo código {{baseNh|8|16h}}, quadrada, com ''h''<sub>0</sub>=1048.58 km de lado (área de 1099511.63 km²); | |||
*2 células ''L0.5'', filhas da <code>7</code>: <code>7Q</code>, <code>7G</code>; retangulares, com lados ''h''<sub>0</sub> × ''h''<sub>0</sub>/2 = 1048.58 km × 524,29 km (área de 549756 km²); | |||
*4 células ''L1'', filhas da <code>6</code>: <code>6H</code>, <code>6M</code>, <code>6R</code>, <code>6V</code>; quadradas, com lados ''h''<sub>0</sub>/2 = 524,29 km × 1048.58 km (área de 274878 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 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: | |||
[[Arquivo:Base32nvu-firstDivs.png|centro|semmoldura|820px]] | |||
[[Categoria:Código natural]] |
edições