2 402
edições
Código Natural/Notação posicional: mudanças entre as edições
Código Natural/Notação posicional (ver código-fonte)
Edição das 23h08min de 21 de julho de 2023
, 21 de julho de 2023revisando , ainda draft
mSem resumo de edição |
(revisando , ainda draft) |
||
| 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}} ou [0125]<sub>8h</sub>.]] | ||
[[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. | ||
| Linha 29: | Linha 21: | ||
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: | 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: | ||
{| 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> || <code>00</code> || <code>0000</code> || <code>010</code> || <code>1010</code> || <code>10100</code> | ||
|- | |- | ||
| Linha 60: | Linha 52: | ||
=== Base N === | === Base N === | ||
{| class="wikitable" | :{| class="wikitable" | ||
|'''base''' | |'''base''' | ||
|'''label''' | |'''label''' | ||
| Linha 136: | Linha 128: | ||
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'''<br/>{{baseNh|000000000111|2h}}, {{baseNh|1111|2h}} e {{baseNh|1010101100010010101|2h}} | |'''007''', '''33''', '''ab12T'''<br/>{{baseNh|000000000111|2h}}, {{baseNh|1111|2h}} e {{baseNh|1010101100010010101|2h}} | ||
| Linha 177: | Linha 169: | ||
{| class="wikitable" | :{| class="wikitable" | ||
|'''base''' | |'''base''' | ||
|'''label''' | |'''label''' | ||
| Linha 216: | Linha 208: | ||
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''' | ||
| Linha 235: | Linha 227: | ||
==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, 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. | 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". | |||
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: | 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: | ||
| Linha 243: | Linha 253: | ||
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? | ||
''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). | 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 259: | Linha 276: | ||
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 352: | Linha 386: | ||
[[Arquivo:Base32nvu-firstDivs.png|centro|semmoldura|820px]] | [[Arquivo:Base32nvu-firstDivs.png|centro|semmoldura|820px]] | ||