Documentação

Código Natural: mudanças entre as edições

Página Discussão

Código Natural (ver código-fonte)

Edição das 18h16min de 6 de janeiro de 2024

11 448 bytes adicionados ,  6 janeiro
m
Peter moveu Código natural para Código Natural: nme próprio
(→‎Listagens ilustrativas: reduzindo listagem e jogando para outra página)
m (Peter moveu Código natural para Código Natural: nme próprio)
 
(34 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 1: Linha 1:
[[Arquivo:BitString-infiniteTape.png.png|miniaturadaimagem|Todo código natural pode ser expresso univocamente através de uma ''cadeia de bits''.]]
[[Arquivo:BitString-infiniteTape.png.png|miniaturadaimagem|Todo código natural pode ser expresso univocamente através de uma ''cadeia de bits''.]]


O conjunto dos Códigos Naturais foi definido em analogia ao  [[wikipedia:natural number|conjunto dos '''números naturais''']] (ℕ). O conjunto dos Códigos Naturais é munido de regras e operações, tais como  ordenação, regras de notação posicional e regras de estruturação hierárquica. Cada um de seus elementos pode ser designado '''código natural''' e expresso através de uma [[cadeia de bits]].
O conjunto dos Códigos Naturais foi definido em analogia ao  [[wikipedia:natural number|conjunto dos '''números naturais''']] (ℕ). O conjunto dos Códigos Naturais é munido de regras e operações, tais como  ordenação, regras de notação posicional e regras de estruturação hierárquica. Cada um de seus elementos pode ser designado '''código natural''' e expresso através de uma [[cadeia de bits]].


Números naturais também podem ser mapeados em cadeias de bits, mas esse mapeamento não abrange todas as cadeias possíveis. O código natural <code>0010</code> por exemplo é distinto do código <code>10</code>, de modo que existem mais códigos naturais do que números naturais: o conjunto ℕ mapeado em cadeias de bits forma um subconjunto dos códigos naturais.
Números naturais também podem ser mapeados em cadeias de bits, mas esse mapeamento não abrange todas as cadeias possíveis. O código natural <code>0010</code> por exemplo é distinto do código <code>10</code>, de modo que existem mais códigos naturais do que números naturais: o conjunto ℕ mapeado em cadeias de bits forma um subconjunto dos códigos naturais.


Formalização em {{xref|KraEtAll2019}}, implementação das operações em [https://git.osm.codes/NaturalCodes git.osm.codes/NaturalCodes].
: '''Formalização e licença''': em {{xref|KraEtAll2019}}, registrado como [[CC0]].
: '''Implementação''' das operações em [https://git.osm.codes/NaturalCodes git.osm.codes/NaturalCodes].
: '''Aplicações''': [[geocódigos]], [[wikipedia:Database index|indexadores]], identificadores hierárquicos (de [[wikipedia:Statistical classification|classes estáveis]]), [[wikipedia:Graph labeling|rotuladores]], [[wikipedia:Hash function|''hashes'']]<!-- , descritores de [[wikipedia:Quantum state|estados quânticos]] (quando incluso indefinido)--> etc. Existe uma infinidade de aplicações onde as cadeias de bits são mais convenientemente interpretadas como códigos naturais, do que como  números naturais.  


Aplicações: [[geocódigos]], [[wikipedia:Database index|indexadores]], identificadores hierárquicos, [[wikipedia:Graph labeling|rotuladores]], [[wikipedia:Hash function|''hashes'']], descritores de [[wikipedia:Quantum state|estados quânticos]] etc. Existe uma infinidade de aplicações onde as cadeias de bits são mais convenientemente expressas como códigos naturais do que como números naturais.  
== Resumo didático ==
 
Um '''código''' qualquer é representado internamente, no computador, por uma [[cadeia de bits]]; que por sua vez é meramente uma sequência de símbolos dentro do computador (tipicamente zeros e uns). <!-- E cadeias de bits podem estar representando qualquer coisa, como um texto (código alfanumérico) ou um [[wikipedia:natural number|número natural]] (código numérico).--> O conceito de ''código'' é mais abrangente e não deve ser confundido com o conceito de ''número'':  aplicamos apenas aos números a regra de "eliminar zeros à esquerda". Se digo que 007 é um número usual, então será o mesmo que 7; mas se digo que é um código, devo considerar <code>007</code>  e <code>7</code>  como entidades distintas.
 
A cadeia de bit é um [[wikipedia:Primitive data type|tipo de dado primitivo]], bem simples, possui poucas operações e poucos métodos de conversão. Podemos conceber um tipo de dado derivado um pouco mais sofisticado, com operações adicionais, tais como soma e sucessão, e com métodos de conversão, tais como conversão para notação posicional.


== Resumo didático ==
Números, por exemplo, são tipos primitivos bem mais sofisticados, com muito mais recursos computacionais e interoperabilidade com outros tipos de dados. O [[wikipedia:natural number|conjunto dos '''números naturais''']] (<math>\mathbb{N}</math>) é munido das operações de soma, multiplicação e de regras de [[wikipedia:Positional notation|notação posicional]] (decimal, binária, hexadecimal, etc.). Similarmente,  o '''conjunto dos Códigos Naturais''' foi definido em {{xref|KraEtAll2019}} através da formalização das operações de ordenação, soma, subtração, regras de notação posicional e regras de estruturação hierárquica.
 
=== Histórico ===
O Instituto AddressForAll propôs em 2019  uma nova notação para os códigos naturais, similar à notação hexadecimal, garantindo que a hierarquia entre códigos seja preservada, tal como na cadeia de bits; batizando-a mais tarde de base16h. <!--Tecnicamente é uma [[wikipedia:Positional notation|notação posicional]]:  traduz cadeias de dígitos-base2 (''cadeias de bits'') em cadeias de dígitos-base16h, tendo os números como subconjunto (de ambos os lados da tradução). A base16h preserva a hierarquia e é compatível com a representação numérica hexadecimal comum.-->


Um '''código''' qualquer é representado internamente, no computador, por uma [[cadeia de bits]]; que por sua vez é meramente uma sequência de símbolos dentro do computador (tipicamente zeros e uns). <!-- E cadeias de bits podem estar representando qualquer coisa, como um texto (código alfanumérico) ou um [[wikipedia:natural number|número natural]] (código numérico).--> O conceito de ''código'' é mais abrangente e não deve ser confundido com o conceito de ''número'':  aplicamos apenas aos números a regra de "eliminar zeros à esquerda". Se digo que <code>007</code> é um número, então será o mesmo que <code>7</code>; mas se digo que é um código, devo considerar <code>007</code>  e <code>7</code>  como entidades distintas.
O documento {{xref|KraEtAll2019}} foi registrado na [https://antigo.bn.gov.br/sobre-bn/deposito-legal Fundação Biblioteca Nacional] sob o protocolo número '''<code>2801/19</code>''', garantindo que nenhuma patente ou direito autoral possam ser reclamados quanto à notação criada (base4h, base8h e base16h).
<!--
Quando os elementos de um conjunto aninhado são rotulados com números naturais, a estrutura hierárquica não é preservada; mas quando os rótulos numéricos são substituídos por cadeias de bits de comprimento variável, distinguindo zeros iniciais (00 e 0 como entidades distintas), é possível expressar rótulos com sintaxe hierárquica, preservando a estrutura aninhada original e hexadecimais clássicos como subconjunto.


Podemos conceituar com mais precisão um "tipo de cadeia" dizendo que ela é elemento de um [[wikipedia:Set theory|'''conjunto''']] específico de cadeias de bits. Por exemplo uma cadeia do tipo "tamanho 3" é elemento do conjunto de todas as cadeias de 3 bits. Podemos criar ainda mais tipos se descrevermos operações válidas entre os elementos do conjunto.
Apresentamos uma definição formal desse tipo de sistema de rotulagem numérica, chamando-o de Códigos Naturais. Também mostramos que ela pode ser transformada em codificações legíveis por humanos (notações posicionais como base4, base8 ou base16), as extensões de notação base base4h, base8h e base16h para representação hierárquica. O modelo de referência adotado é o conjunto finito de Cantor com grau hierárquico k — a rigor, o conjunto Ck é a “árvore hierárquica do conjunto de Cantor”, que é isomorfo a uma árvore binária completa —, propondo um processo de rotulagem simples, mapeando elementos de Ck em elementos dos Códigos Naturais.


O [[wikipedia:natural number|conjunto dos '''números naturais''']] (<math>\mathbb{N}</math>) é munido das operações de soma, multiplicação e de regras de [[wikipedia:Positional notation|notação posicional]] (decimal, binária, hexadecimal, etc.). Similarmente,   o '''conjunto dos Códigos Naturais''' foi formalizado em {{xref|KraEtAll2019}}, junto com a formalização das operações de ordenação, soma, subtração, regras de notação posicional e regras de estruturação hierárquica.
A proposta das extensões de notação de base introduz um complemento à sintaxe de base ordinária, onde o último dígito pode utilizar, quando necessário, um alfabeto complementar para representar valores parciais (com um bit a menos que os dígitos ordinários). A representação hierárquica é um superconjunto, diferenciando-se da notação de base comum por este último dígito, que é um membro não hierárquico da representação (denominado nhDigit). Também oferecemos algoritmos para implementar a conversão das extensões de base e discutimos otimizações.
-->


== Apresentação formal ==
== Apresentação formal ==
Linha 21: Linha 33:
[[Arquivo:KraEtAll2019-fig09-Xn.png|thumb|340px|Os três primeiros conjuntos <math>X_{k}</math> da hierarquia dos códigos naturais: <math>X_{1}, X_{2} \text{ e } X_{3}</math>.<br/>Na ilustração ressaltamos a equivalência entre a [[wikipedia:Binary tree|árvore binária completa]] e o  [[wikipedia:Cantor set|Conjunto de Cantor]].]]
[[Arquivo:KraEtAll2019-fig09-Xn.png|thumb|340px|Os três primeiros conjuntos <math>X_{k}</math> da hierarquia dos códigos naturais: <math>X_{1}, X_{2} \text{ e } X_{3}</math>.<br/>Na ilustração ressaltamos a equivalência entre a [[wikipedia:Binary tree|árvore binária completa]] e o  [[wikipedia:Cantor set|Conjunto de Cantor]].]]


Por existirem mais possibilidades de combinar símbolos na forma de códigos do que na forma de números, podemos afirmar que o conjunto dos símbolos que representam elementos de <math>\mathbb{N}</math> é subconjunto dos códigos naturais. Matematicamente o '''conjunto dos códigos naturais''', <math>X_{\infty}</math>, pode ser induzido do conjunto <math>X_{k}</math>, relativo a [[cadeia de bits#Cadeias de tamanho fixo|cadeias]] de no máximo ''k'' bits, gerado pela seguinte recorrência:
Sintaticamente, códigos e números podem usar os mesmos símbolos como dígitos, e, por existirem mais possibilidades de combinar símbolos na forma de códigos do que na forma de números, podemos afirmar que o conjunto dos símbolos que representam elementos de <math>\mathbb{N}</math> é subconjunto dos códigos naturais. Para tirar proveito dessa relação sintática, denominaremos '''<math>P_k</math>''' o conjunto dos números naturais (de ''k''&nbsp;bits) convertidos para '''cadeias de&nbsp;bits de tamanho&nbsp;fixo&nbsp;''k'''''.
 
O '''conjunto dos códigos naturais''', <math>X_{\infty}</math>, pode ser induzido do conjunto <math>X_k</math>, relativo a [[cadeia de bits#Cadeias de tamanho fixo|cadeias]] de no máximo ''k'' bits, gerado pela seguinte recorrência:


:<math>
:<math>
X_{k} =
X_{k} =
\begin{cases}
\begin{cases}
P_k \cup X_{k-1}, & \text{if }k>1 \\
P_k \cup X_{k-1}, & \text{if } k>0 \\
P_1, & \text{if }k=0
\empty, & \text{if}~k=0
\end{cases}
\end{cases}
</math>
</math>


onde <math>P_{k}</math> é o conjunto dos números naturais de ''k'' bits, convertidos para ''bit strings''. <br/>Ou seja, os elementos de <math>P_{k}</math> são representações binárias de tamanho fixo ''k'' dos valores <math>0</math> até <math>2^k-1</math>.
onde <math>P_1 = \{0, 1\}</math> e nos demais <math>P_k</math> os elementos são representações binárias de tamanho fixo ''k'' dos valores <math>0</math> até <math>2^k-1</math>.  
 
Por exemplo, para ''k''=0 até ''k''=8 temos os seguintes conjuntos <math>X_k</math>:
Por exemplo, para ''k''=1 até ''k''=8 temos os seguintes conjuntos <math>X_k</math>:


:<math>
:<math>
\begin{align}
\begin{align}
X_1 &= P_1 = \{0, 1\},\\
X_0 &= \empty;\\
X_2 &= P_2 \cup X_1 = \{00, 01, 10, 11\} \cup \{0, 1\} = \{0, 00, 01, 1, 10, 11\},\\
X_1 &= P_1 = \{0, 1\};\\
X_3 &= P_3 \cup X_2 = \{0, 00, 000, 001, 01, 010, 011, 1, \cdots, 111\},\\
X_2 &= P_2 \cup X_1 = \{00, 01, 10, 11\} \cup \{0, 1\} = \{0, 00, 01, 1, 10, 11\};\\
X_3 &= P_3 \cup X_2 = \{000, 001, 010, \cdots, 111\} \cup \{0, 00, 01, 1, 10, 11\} \\
&= \{0, 00, 000, 001, 01, 010, 011, 1, \cdots, 111\};\\
  \vdots \\
  \vdots \\
X_8 &= P_8 \cup X_7 = \{0, 00, 000, 000, \cdots, 11111110, 11111111\}
X_8 &= P_8 \cup X_7 = \{0, 00, 000, 0000, \cdots, 11111110, 11111111\}.
\end{align}
\end{align}
</math>
</math>


=== Problemas típicos com códigos ===
Por indução podemos supor também o "conjunto dos números naturais de 0&nbsp;bits", que corresponde ao conjunto vazio, <math>P_0=\empty</math>. Sintaticamente, a cadeia de bits vazia, necessária em diversas situações.
Números binários são representações válidas da [[wikipedia:positional notation|notação posicional]] base2, e podem ser representados de forma mais compacta (mais amigável para o ser humano) através de bases maiores, tais como base8 (sistema octal) ou base10 (sistema decimal). Códigos, todavia, '''não possuem um sistema posicional adequado''', não existe um padrão para se representar todos os códigos naturais, nem sequer na base4.
 
Outro problema é a '''ordem''': códigos naturais, '''para exibirem a ordem hierárquica''', precisam ser ordenados lexicograficamente (ao invés de numericamente). Em <math>X_{2}</math> por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc. <!-- A ordem numérica por nível seria 0, 1, 00, 01, etc.-->


A noção de ''código natural'' nos ajuda estudar esses problemas, e valorizar as eventuais soluções.
O número total de elementos em ''X''<sub>k</sub>, ou seja, <math>|X_k|</math>, pode ser inferido por <math>|P_k|=2^k</math>. Usando a recorrência temos <math>|X_k|=2^k+|X_{k-1}|</math>, que contém a [https://math.stackexchange.com/a/1990146/70274 conhecida série das potências de 2] sem o último termo de 2<sup>0</sup>, <math>|X_k|=2^k+2^{k-1}+\dots + 2^1</math>, resultando em <math>|X_k|=2^{k+1}-2</math>.  


=== Definição alternativa ===
=== Definição alternativa ===
Linha 66: Linha 78:
</math>
</math>


Os pares descrevem com exatidão e podem ser traduzidos para ''bitstrings''. Ilustrando abaixo o uso dos '''pares&nbsp;(''l'',''n'')''', também designados "size-value&nbsp;pairs".
Os pares descrevem com exatidão e podem ser traduzidos para cadeias de bits (''bitStrings''). Ilustrando o uso dos '''pares&nbsp;(''l'',''n'')''', também designados "size-value&nbsp;pairs", em notação decimal:
 
:{| class="wikitable"
!BitString !!(size,value) !!&nbsp;!!BitString !!(size,value)
|-
|<code>0</code> || (1,0) ||&nbsp;|| <code>000000</code>||(6,0)
|-
|<code>111</code> || (3,7) ||&nbsp;|| <code>00000101</code>|| (8,5)
|}
 
=== Problemas típicos com códigos ===
Números binários são representações válidas da [[wikipedia:positional notation|notação posicional]] base2, e podem ser representados de forma mais compacta (mais amigável para o ser humano) através de bases maiores, tais como base8 (sistema octal) ou base10 (sistema decimal). Códigos, todavia, '''não possuem um sistema posicional adequado''', não existe um padrão para se representar todos os códigos naturais, nem sequer na base4.
 
Outro problema é a '''ordem''': códigos naturais, '''para exibirem a ordem hierárquica''', precisam ser ordenados lexicograficamente (ao invés de numericamente). Em <math>X_{2}</math> por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc. <!-- A ordem numérica por nível seria 0, 1, 00, 01, etc.-->
 
A noção de ''código natural'' nos ajuda estudar esses  problemas, e valorizar as eventuais soluções. A tabela abaixo, listando códigos em sua ordem natural (lexicográfica da expressão ''bitString''), ilustra problemas da Base4 e a solução Base4h, bem como a solução ''hbit''.


<pre>
:{| class="wikitable"
  (size,value)         BitString       Base4         Base4h         hbitBitstring   hbit
!(size,value) !!BitString !! Base4 !! Base4h !! hbitBitstring !! hbit
  (1,0)               0               ?             G               10             2
|-
  (2,0)               00               0             0               100             4
| (1,0)|| <code>0</code> || '''?''' || G || <small><code>10</code></small> || 2
  (3,0)               000             ?             0G             1000           8
|-
  (4,0)               0000             00             00             10000           16
| (2,0) || <code>00</code> || 0 || 0 || <small><code>100</code></small> || 4
  (5,0)               00000           ?             00G             100000         32
|-
  (6,0)               000000           000           000             1000000         64
| (3,0) || <code>000</code> || '''?''' || 0G || <small><code>1000</code></small> || 8
  (7,0)               0000000         ?             000G           10000000       128
|-
  (8,0)               00000000         0000           0000           100000000       256
| (4,0) || <code>0000</code> || 00 || 00 || <small><code>10000</code></small> || 16
  (8,1)               00000001         0001           0001           100000001       257
|-
  (7,1)               0000001         ?             000Q           10000001       129
| (5,0) || <code>00000</code> || '''?'''|| 00G || <small><code>100000</code></small> || 32
  (8,2)               00000010         0002           0002           100000010       258
|-
  (8,3)               00000011         0003           0003           100000011       259
| (6,0) || <code>000000</code> || 000 || 000 || <small><code>1000000</code></small> || 64
  (6,1)               000001           001           001             1000001         65
|-
  (7,2)               0000010         ?             001G           10000010       130
| (7,0) || <code>0000000</code> || '''?'''|| 000G || <small><code>10000000</code></small> || 128
  (8,4)               00000100         0010           0010           100000100       260
|-
  (8,5)               00000101         0011           0011           100000101       261
| (8,0) || <code>00000000</code> || 0000 || 0000 || <small><code>100000000</code></small> || 256
    ...                 ...             ...             ...             ...
|-
</pre>
| (8,1) || <code>00000001</code> || 0001 || 0001 || <small><code>100000001</code></small> || 257
|-
| (7,1) || <code>0000001</code> || '''?'''|| 000Q || <small><code>10000001</code></small> || 129
|-
| (8,2) || <code>00000010</code> || 0002 || 0002 || <small><code>100000010</code></small> || 258
|-
| (8,3) || <code>00000011</code> || 0003 || 0003 || <small><code>100000011</code></small> || 259
|-
| (6,1) || <code>000001</code> || 001 || 001 || <small><code>1000001</code></small> || 65
|-
| (7,2) || <code>0000010</code> || '''?'''|| 001G || <small><code>10000010</code></small> || 130
|-
| (8,4) || <code>00000100</code> || 0010 || 0010 || <small><code>100000100</code></small> || 260
|-
| (8,5) || <code>00000101</code> || 0011 || 0011 || <small><code>100000101</code></small> || 261
|-
| ... || ... || ... || ... || ... || ...
|}


A coluna "''hbitBitstring''" é relativa à representação das ''bitstrings'' em formato "hidden bit", definido em {{xref|KraEtAll2019}}. Consiste em acrescentar o <code>1</code> na frente da ''bitstring'', para que não lhe cortem os zeros à esquerda, ao interpretá-la como número inteiro positivo (em formato decimal na coluna ''hbit'').
A coluna "''hbitBitstring''" é relativa à representação das ''bitStrings'' em formato "hidden bit", definido em {{xref|KraEtAll2019}}. Consiste em acrescentar o <code>1</code> na frente da ''bitString'', para que não lhe cortem os zeros à esquerda, ao interpretá-la como número inteiro positivo (em formato decimal na coluna ''hbit'').


A coluna "Base4" é a tentativa ('''frustrada''') de representar as ''bitstrings'' com o algoritmo da [[wikipedia:Quaternary numeral system|notação posicional numérica da ''Base 4'']]. '''A coluna "Base4h" é a inovação''' proposta em {{xref|KraEtAll2019}}, que adaptou o algoritmo para expressar códigos ao invés de  números, permitindo zeros a esquerda e quantidade variável de dígitos.
A coluna "Base4" é a tentativa ('''frustrada''') de representar as ''bitStrings'' com o algoritmo da [[wikipedia:Quaternary numeral system|notação posicional numérica da ''Base 4'']]. '''A coluna "Base4h" é a inovação''' proposta em {{xref|KraEtAll2019}}, que adaptou o algoritmo para expressar códigos ao invés de  números, permitindo zeros a esquerda e quantidade variável de dígitos.


:<small>Nota. Conjuntos finitos de códigos naturais sempre podem ser expressos como conjuntos de ''hbits'', portanto através de números naturais. O conjunto de todos os Códigos Naturais todavia é infinito, e neste caso particular (com infinitos elementos), a representação ''hbit'' não é permitida pelo [[wikipedia:Cantor's theorem|Teorema de Cantor]]. Portanto, matematicamente, ''size-value'' é um tradutor mais rigoroso para expressões em <math>\mathbb{N}</math>.</small>
:<small>Nota. Conjuntos finitos de códigos naturais sempre podem ser expressos como conjuntos de ''hbits'', portanto através de números naturais. O conjunto de todos os Códigos Naturais todavia é infinito, e neste caso particular (com infinitos elementos), a representação ''hbit'' não é permitida pelo [[wikipedia:Cantor's theorem|Teorema de Cantor]]. Portanto, matematicamente, ''size-value'' é um tradutor mais rigoroso para expressões em <math>\mathbb{N}</math>.</small>


== Inovação tecnológica nas representações ==
==== Tamanho do problema ====
Quantos códigos naturais de ''k'' bits deixam de ser representados na Base ''N''?


[[Arquivo:Zcutve-base4.png.png|miniaturadaimagem|A sequência de células 1 a 16 pode ser rotulada pela '''base 4''' com 2 dígitos.]]
Avaliando a seguir apenas bases  com ''N'' em {4, 8, 16, 32} da [https://datatracker.ietf.org/doc/html/rfc4648 RFC&nbsp;4648] das aplicações da Internet e (base 4) das aplicações em [[geocódigos]]. São todas na forma <math>N=2^n</math>, com ''n'' variando de 2 (4=2<sup>2</sup>) a 5 (32=2<sup>5</sup>). O valor de ''n'' fornece também o número de bits por dígito da base, por exemplo base ''N''=8 temos ''n''=3, portanto cada dígito da base&nbsp;8 tem 3&nbsp;bits.
[[Arquivo:Zcurve-8cells base4h.png.png|miniaturadaimagem|Oito células rotuladas hierarquicamente pela '''base4h'''.]]


A demanda por [[geocódigos]] eficientes deu origem a uma inovação tecnológica, desenvolvida pela [[AddressForAll]]. Foi matematicamente generalizada como "repesentação posicioal de Código Natural". Assim como os números decimais (base 10), binários (base 2), hexadecimais (base 16) etc., os códigos podem ser representados nos meios de comunicação de forma mais compacta que cadeias de bits, através de diferentes ''bases''.
Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de ''k'', resultando em uma quantidade de códigos, <math>n\_codes=2^{k+1}-2</math>, e nas quantidades de representações válidas a cada base.  


A [[wikipedia:Quaternary numeral system|'''base 4''']] (ou "sistema de numeração quaternário") é o sistema de numeração mais simples para se representar geocódigos curtos (mais curtos do que a cadeia de bits). Usa somente os dígitos 0&nbsp;a&nbsp;3. A sequência numérica decimal [0, 1, 2, 3, 4, 5, 6] por exemplo, em ''base 4'' se torna [0, 1, 2, 3, 10, 11, 12].
{| class="wikitable"
|
|
| colspan="8" rowspan="1" |            '''Base and occupancy rate of n_codes'''
|-
|'''''k''''' (bits)
|'''n_codes'''
|'''base4'''
|
|'''base8'''
|
|'''base16'''
|
|'''base32'''
|
|-
|1
|2
|0
|0%
|0
|0%
|0
|0%
|0
|0%
|-
|2
|6
|4
|67%
|0
|0%
|0
|0%
|0
|0%
|-
|3
|14
|4
|29%
|8
|57%
|0
|0%
|0
|0%
|-
|4
|30
|20
|67%
|8
|27%
|16
|53%
|0
|0%
|-
|5
|62
|20
|32%
|8
|13%
|16
|26%
|32
|52%
|-
|6
|126
|'''84'''
|'''67%'''
|72
|57%
|16
|13%
|32
|25%
|-
|7
|254
|'''84'''
|'''33%'''
|72
|28%
|16
|6%
|32
|13%
|-
|8
|510
|340
|67%
|72
|14%
|'''272'''
|'''53%'''
|32
|6%
|-
|9
|1022
|340
|33%
|'''584'''
|'''57%'''
|'''272'''
|'''27%'''
|32
|3%
|-
|10
|2046
|1364
|67%
|'''584'''
|'''29%'''
|'''272'''
|'''13%'''
|'''1056'''
|'''52%'''
|-
|11
|4094
|1364
|33%
|'''584'''
|'''14%'''
|'''272'''
|'''7%'''
|'''1056'''
|'''26%'''
|-
|12
|8190
|5460
|67%
|4680
|57%
|4368
|53%
|'''1056'''
|'''13%'''
|-
|13
|16382
|5460
|33%
|4680
|29%
|4368
|27%
|'''1056'''
|'''6%'''
|-
|14
|32766
|21844
|67%
|4680
|14%
|4368
|13%
|'''1056'''
|'''3%'''
|-
|15
|65534
|21844
|33%
|37448
|57%
|4368
|7%
|33824
|52%
|-
|16
|131070
|87380
|67%
|37448
|29%
|69904
|53%
|33824
|26%
|-
| colspan="3" rowspan="1" |Average on '''stable cycle''':
|50%
|
|33%
|
|25%
|
|20%
|-
| colspan="3" |Loss, 100% - occupancy:
|50%
|
|67%
|
|75%
|
|80%
|}
 
Os valores percentuais foram calculados com relação a ''n_codes'', as médias finais de ''occupancy'' com relação aos ciclos.
 
O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%;  em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%.
 
Conclusão: nas bases de aplicação mais frequente (as bases 8 e 16), entre 67% e 75% dos códigos naturais deixam de ser representados. É uma perda muito grande, vale a penas investir numa solução.
 
=== Problemas típicos com taxonomias ===
 
... indexação e recuperação da hierarquia num banco de dados relacional ...
 
== Inovações tecnológicas ==
...
=== Na representação interna ===
: Ver [[Código natural/Representação interna]].
 
....
 
=== Na representação textual ===
[[Arquivo:Zcutve-base4.png.png|miniaturadaimagem|A sequência de 16&nbsp;[[Generalized Geohash/pt#Representação geométrica|células]] pode ser rotulada pela '''base&nbsp;4h'''. Esses rótulos podem ser empregados como geocódigos.<br/>Ao contrário da base&nbsp;4 numérica, que remove zeros a esquerda, a base&nbsp;4h os mantém, por representar códigos e não números.]]
 
[[Arquivo:Zcurve-8cells base4h.png.png|miniaturadaimagem|Oito células rotuladas hierarquicamente pela '''base4h'''. Reparar que os prefixos da ilustração anterior são preservados. Por ex. na anterior <code>00</code> e <code>03</code> possuem mesmo prefixo <code>0</code>  que <code>0G</code> e <code>0Q</code>. Todas ocupam geometricamente o mesmo "quadrante&nbsp;<code>0</code>" da célula-mãe.]]
 
A demanda por [[geocódigos]] eficientes motivou uma inovação tecnológica, desenvolvida pela [[AddressForAll]]. Do ponto de vista matemático é uma generalização da [[wikipedia:Positional notation|representação posicional]], aplicada a códigos naturais. Assim como os números (binários base 2, decimais base 10, hexadecimais base 16, etc.), os códigos podem ser representados nos meios de comunicação de forma mais compacta que cadeias de bits, através de diferentes ''bases''.
 
A [[wikipedia:Quaternary numeral system|'''base&nbsp;4''']] (ou "sistema de numeração quaternário") é simples e já representa números de maneira mais compacta que a notação binária. Usa somente os dígitos 0&nbsp;a&nbsp;3. A&nbsp;sequência numérica de 0 a 6 por exemplo, em notação binária [0,1,10,11,100,101,110]<sub>2</sub>, convertida para ''base 4'' se torna [0,1,2,3,10,11,12]<sub>4</sub>, economizando 5 dígitos.


A ilustração abaixo destaca onde falha a base 4 tradicional e como a inovação da '''base 4h''' resolve o problema:
Abaixo é ilustrado o uso clássico da base&nbsp;4 em códigos: tradição de adaptação da base numérica,  permitindo zeros a esquerda ao representar códigos. Mostra como a adaptação falha para certos códigos,  e como a inovação da [[base4h|'''base&nbsp;4h''']] resolve o problema:
* permite representar cadeias de bits (''bit strings'') de qualquer tamanho;
* permite representar cadeias de bits (''bit strings'') de qualquer tamanho;
* permite agrupar hierarquicamente.
* permite agrupar hierarquicamente.
Linha 111: Linha 390:


&nbsp;[[Arquivo:KraEtAll2019-fig03-awns.png]]
&nbsp;[[Arquivo:KraEtAll2019-fig03-awns.png]]
Inspiradas nesta inovação para a base&nbsp;4, foram criadas também a [[base8h|base&nbsp;8h]] e a [[base16h|base&nbsp;16h]].


As questões de ordenação são resolvidas por algoritmos de comparação aplicados à representação interna do código, em geral a binária. A ordem lexicográfica dos bits é a mesma que a chamada "preorder" de uma árvore binária. A "level order" pode ser útil para certas situações, mas não é considerada a ordem nativa dos códigos naturais.
As questões de ordenação são resolvidas por algoritmos de comparação aplicados à representação interna do código, em geral a binária. A ordem lexicográfica dos bits é a mesma que a chamada "preorder" de uma árvore binária. A "level order" pode ser útil para certas situações, mas não é considerada a ordem nativa dos códigos naturais.
Linha 116: Linha 397:
[[Arquivo:KraEtAll2019-fig05-orders.png|480px|center]]
[[Arquivo:KraEtAll2019-fig05-orders.png|480px|center]]


== Histórico ==
A ordem é indiferente ao conjunto, podem haver saltos na sequência. Por ex. ao ordenar lexicograficamente o conjunto de códigos binários {<code>10</code>, <code>0</code>, <code>1</code>, <code>001</code>} obtemos a série [<code>0</code>, <code>001</code>, <code>1</code>, <code>10</code>]<sub>2h</sub>.  
O Instituto AddressForAll propôs em 2019  uma nova notação para os códigos naturais, similar à notação hexadecimal, e garantindo que a hierarquia entre códigos seja preservada, tal como na cadeia de bits.  


Tecnicamente é uma [[wikipedia:Positional notation|notação posicional]] para transformar ''cadeias de bits'' com quantidade arbitrária de bits, que preserva a hierarquia e é compatível com a representação numérica hexadecimal comum.
Portanto, dentro de um conjunto com tamanho fixo de ''k'' bits, ''P''<sub>k</sub> (onde todos os elementos estão no nível ''k'' da hierarquia), a ''preorder'' e a ''level order'' resultam em ordenações equivalentes. A ordenação é realizada através de um [https://math.stackexchange.com/a/3145814/70274 algoritmo de comparação de pares de códigos], que pode tirar vantagem dessa equivalência para ser mais rápido.
 
O documento {{xref|KraEtAll2019}} foi registrado na [https://antigo.bn.gov.br/sobre-bn/deposito-legal Fundação Biblioteca Nacional] sob o protocolo número '''<code>2801/19</code>''', garantindo que nenhuma patente ou direito autoral possam ser reclamados quanto à notação criada (base4h, base8h e base16h).
 
<!--
Quando os elementos de um conjunto aninhado são rotulados com números naturais, a estrutura hierárquica não é preservada; mas quando os rótulos numéricos são substituídos por cadeias de bits de comprimento variável, distinguindo zeros iniciais (00 e 0 como entidades distintas), é possível expressar rótulos com sintaxe hierárquica, preservando a estrutura aninhada original e hexadecimais clássicos como subconjunto.
 
Apresentamos uma definição formal desse tipo de sistema de rotulagem numérica, chamando-o de Códigos Naturais. Também mostramos que ela pode ser transformada em codificações legíveis por humanos (notações posicionais como base4, base8 ou base16), as extensões de notação base base4h, base8h e base16h para representação hierárquica. O modelo de referência adotado é o conjunto finito de Cantor com grau hierárquico k — a rigor, o conjunto Ck é a “árvore hierárquica do conjunto de Cantor”, que é isomorfo a uma árvore binária completa —, propondo um processo de rotulagem simples, mapeando elementos de Ck em elementos dos Códigos Naturais.
 
A proposta das extensões de notação de base introduz um complemento à sintaxe de base ordinária, onde o último dígito pode utilizar, quando necessário, um alfabeto complementar para representar valores parciais (com um bit a menos que os dígitos ordinários). A representação hierárquica é um superconjunto, diferenciando-se da notação de base comum por este último dígito, que é um membro não hierárquico da representação (denominado nhDigit). Também oferecemos algoritmos para implementar a conversão das extensões de base e discutimos otimizações.
-->


== Listagens ilustrativas ==
== Listagens ilustrativas ==
Linha 159: Linha 429:
|2 || <code>00</code>      ||    4 || 0    || H
|2 || <code>00</code>      ||    4 || 0    || H
|-
|-
|3 || <code>01</code>      ||    5 || Q   || Q
|3 || <code>01</code>      ||    5 || 1   || M
|-
|-
|4 || <code>1</code>        ||    3 || Q    || Q
|4 || <code>1</code>        ||    3 || Q    || Q
Linha 165: Linha 435:
|5 || <code>10</code>      ||    6 || 2    || R
|5 || <code>10</code>      ||    6 || 2    || R
|-
|-
|6 || <code>11</code>      ||    7 || Q   || Q
|6 || <code>11</code>      ||    7 || 3   || V
|}
|}


Linha 244: Linha 514:
|}
|}


:<small>Nota. A coluna ''count'' faz a contagem de ''bitstrings'' ordenadas, de modo que a primeira linha (''count'' 1) seria relativa à ''biststring'' vazia... Adotamos no entanto a noção de "zerézima linha", para compatibilizar com a coluna ''hbit'' (o próprio marcador tem valor 1). A rigor a noção de "zerézimo" é também adotada pela [[wikipedia:Ordinal number#Von_Neumann_definition_of_ordinals|numeração ordinal]] em Matemática. Reparar que o acréscimo da linha zero garante também a compatibilização entre a quantidade de linhas  e o valor final de ''hbit''.</small>
:<small>Nota. A coluna ''count'' faz a contagem de ''bitstrings'' ordenadas, mas não começa com o valor 1. Para a ''biststring'' vazia adotamos a noção de "zerézima linha", para compatibilizar com a coluna ''hbit'' (o próprio marcador tem valor 1). A rigor a noção de "zerézimo" é também adotada pela [[wikipedia:Ordinal number#Von_Neumann_definition_of_ordinals|numeração ordinal]] em Matemática. Reparar que o acréscimo da linha zero garante também a compatibilização entre a quantidade de linhas  e o valor final de ''hbit''.</small>


== Demais fundamentos ==
== Demais fundamentos ==
...
 
=== Hierarquia como coleção de conjuntos aninhados ===
=== Hierarquia como coleção de conjuntos aninhados ===
Um ''conjunto aninhado'' é um conjunto contendo uma cadeia de subconjuntos, formando uma estrutura hierárquica. Na Teoria dos Conjuntos, está relacionado à [[wikipedia:Partially_ordered_set|ordem parcial]], e os conjuntos aninhados são usados como referência para quaisquer definições de hierarquia ou herança de classe.
Seja ''B'' um conjunto não vazio e '''''C''''' uma coleção de subconjuntos de ''B'', com <math>B \in C</math>. Então '''''C''''' é uma [[wikipedia:Nested_set#Formal_definition|coleção de conjuntos aninhados]] se:
<br/>&nbsp; <math>\begin{align}
\forall H, Q \in \mathbf{C}: H \cap \mathbf{C} \ne \empty \implies H \sub Q \lor Q \sub H
\end{align}</math><br/>
Então podemos supor que a coleção '''''C''''' que representa a hierarquia dos k-Códigos Naturais é definida por<br/>&nbsp;
<math>
C_k = \{X_1, X_2, \dots, X_k\}
    = \{ P_1, ~P_1 \cup P_2 , ~\dots, ~P_1 \cup P_2 \cup \dots \cup P_k\}
</math>
<br/>onde as operações da união estão demonstrando que a segunda condição é satisfeita.


=== Cadeia de bits e notação base2h ===
Então sempre é verdade que<br/>&nbsp; <math>X_1 \sub X_2 \sub X_3 \sub \dots \sub X_k</math>
...
<br/>ou, generalizando, que  ''i''<''a''  implica ''X''<sub>i</sub>⊂''X''<sub>a</sub>. A coleção ''C''<sub>k</sub> é uma ordem parcial para “⊂”, portanto, uma [[wikipedia:Inclusion order|ordem estrita de inclusão]].
 
Outro aspecto do conceito de hierarquia está na hierarquia dos elementos de ''X''<sub>i</sub>. Comentada anteriormente, pode ser expressa pelas relações sintáticas entre os prefixos dos elementos de um conjunto ''X''<sub>i</sub>  e do seu conjunto-origem ''X''<sub>i-1</sub>. Cada elemento ''x'' de ''X''<sub>i</sub>  com mais de um bit,
 
* a representação da cadeia de bits é uma concatenação de um prefixo ''p'' e um sufixo ''s'',  ''x''=''p''⊕''s'',  onde  ''p'' ∈ ''X''<sub>i-1</sub>.
* na representação por par <math>x=(l,n)</math>  o prefixo ''p'' de ''x'' é dado por  <math>p=(l-1, \lfloor n / 2 \rfloor) \in X_{i-1}</math>.
 
Ambas representações garantem que, sintaticamente, os elementos ''p'' de ''X''<sub>i-1</sub> são "pais" dos elementos ''x'' de ''X''<sub>i</sub>. Ao passo que as relações gerais de inclusão garantem que ''X''<sub>i-1</sub>⊂''X''<sub>i</sub> (o conjunto dos elementos-pais está contido no conjunto dos elementos-filhos).
[[Arquivo:NatCodes-hierarchy2.png|centro|semmoldura|420x420px]]
São facetas da mesma hierarquia em árvore, embutida na estrutura dos conjuntos e na sintaxe dos seus elementos.
 
=== Bases 2h, 4h, 8h e 16h ===
::<small>Resumo de [[Código natural/Base h]].</small>
 
... resumo...


=== Base4h ===
=== Reproduzindo a preorder dentro de um número inteiro ===
...
A ordem lexigrográfica dos  formadas por zeros e uns, que resulta na chamada *preorder* das árvores binárias,
.. conceito de distância conforme https://math.stackexchange.com/q/3142409/70274


=== Base8h ===
=== Base16h ===
[[arquivo:KraEtAll2019-fig11-ordBases.png|thumb|280px|O alfabeto da base 16h, para representar os primeiros 30 códigos naturais.]]
...


=== Ordenações lexicográfica e numérica  ===
=== Ordenações lexicográfica e numérica  ===
Para simplificar as convenções da base-h, reutilizamos os alfabetos:
<br/>&nbsp; ''alphabet''(base4h) ⊂ ''alphabet''(base8h) ⊂ ''alphabet''(base16h).
Outra decisão importante, para manter as representações numéricas como um subconjuntos das representações de códigos base-h:
<br/>&nbsp; ''rep''(base4) ⊂ ''rep''(base4h);&nbsp; ''rep''(base8) ⊂ ''rep''(base8h);&nbsp; ''rep''(base16) ⊂ ''rep''(base16h).
[[arquivo:KraEtAll2019-fig11-ordBases.png|thumb|300px|O alfabeto da base 16h, para representar os primeiros 30 códigos naturais.]]
Pagamos um preço alto pela última decisão quando estamos ordenando uma lista de Códigos Naturais: "ordem numérica base16" e "ordem bitstring base16h" são intercaladas. O objetivo é a ordem lexicográfica da cadeia de bits, conforme tabela ao lado, onde as células coloridas mostram o problema de intercalação.
O melhor que podemos fazer, para o leitor humano, é preservar a ordem no conjunto de dígitos hexadecimais e a ordem no conjunto ''nhDigits''. A ordem completa (união de conjuntos) deve utilizar, por exemplo, uma tradução no último dígito do código.
Em um banco de dados SQL, assumindo uma coluna ''x'' de códigos naturais em base16h. O “ORDER BY x” falhará. Necessita de uma tradução de caracteres, aqui expressa em PostgreSQL:
<syntaxhighlight lang="sql">
SELECT x FROM t ORDER BY traduzir(
    x,
  'GHJ01K23MN45R67QRS89TabVZcdYef',
    '0123456789ABCDEFGHIJKLMNOPQRST'
) -- ou apenas a tradução do último dígito
</syntaxhighlight>
Para ser amigável, evitando traduções, os códigos base-h devem ser representados por texto com collation especial. Supondo que a base-h seja um padrão, é natural propor um agrupamento para ela. Imagine definir uma coluna como representação base16h:
<syntaxhighlight lang="sql"> CREATE TABLE t (x text COLLATE "num_b16h");</syntaxhighlight>


== Algoritmos ==
== Algoritmos ==


Ver https://git.osm.codes/NaturalCodes
Ver https://git.osm.codes/NaturalCodes
== Ver também ==
* [[Código natural/Identificação taxonômica]]
* [[Código natural/Notação posicional]]
* [[Código natural/Requisitos e motivações]]
* [[Código natural/Representação interna]]
[[Categoria:Conceitos]]
[[Categoria:Conceitos]]
[[Categoria:Código natural]]
Peter
2 435

edições

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