Código Natural: mudanças entre as edições
(Bases de interesse prático em Geo) |
m (→Bases de interesse prático: format) |
||
Linha 295: | Linha 295: | ||
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, | 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> | ||
O valor de ''N'' todavia 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> | O valor de ''N'' todavia 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 a <math>N \in \{8, 16\}</math> onde o máximo, '''para máxima compressão, é o 16'''. A 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 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 | 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. | ||
[[Arquivo:Base4-bitsCorrelatedOtherBases.png|centro|semmoldura|520px]] | [[Arquivo:Base4-bitsCorrelatedOtherBases.png|centro|semmoldura|520px]] | ||
Tomando o caso concreto da grade de um país continental como Brasil, que requer 20 níveis para subdividir ''L''0 até chegar no metro. Fica nítido pelo emparelhamento dos bits que apenas três níveis das grades | Tomando o caso concreto da grade de um país continental como Brasil, que requer 20 níveis para subdividir ''L''0 até chegar no metro. Fica nítido pelo emparelhamento dos bits que apenas três níveis das grades ''base 32'' e hexadecimal serão comuns: ''L''0, ''L''10 e ''L''20. Abaixo a ilustração da interface para seleção de níveis, com todos e com seus filtrados. | ||
[[Arquivo:Osmc-levelFilters.png|centro|620px]] | [[Arquivo:Osmc-levelFilters.png|centro|620px]] |
Edição das 10h08min de 1 de julho de 2023
O conjunto dos Códigos Naturais foi definido em analogia ao 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 0010
por exemplo é distinto do código 10
, 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 [KraEtAll2019], implementação das operações em git.osm.codes/NaturalCodes.
Aplicações: geocódigos, indexadores, identificadores hierárquicos, rotuladores, hashes, descritores de estados quânticos 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.
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). 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, então será o mesmo que 7
; mas se digo que é um código, devo considerar 007
e 7
como entidades distintas.
Podemos conceituar com mais precisão um "tipo de cadeia" dizendo que ela é elemento de um 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.
O conjunto dos números naturais () é munido das operações de soma, multiplicação e de regras de notação posicional (decimal, binária, hexadecimal, etc.). Similarmente, o conjunto dos Códigos Naturais foi formalizado em [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.
Histórico
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 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.
O documento [KraEtAll2019] foi registrado na Fundação Biblioteca Nacional sob o protocolo número 2801/19
, garantindo que nenhuma patente ou direito autoral possam ser reclamados quanto à notação criada (base4h, base8h e base16h).
Apresentação formal
![](/w/images/thumb/a/a3/KraEtAll2019-fig09-Xn.png/340px-KraEtAll2019-fig09-Xn.png)
Na ilustração ressaltamos a equivalência entre a árvore binária completa e o 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 é subconjunto dos códigos naturais. Matematicamente o conjunto dos códigos naturais, , pode ser induzido do conjunto , relativo a cadeias de no máximo k bits, gerado pela seguinte recorrência:
onde é o conjunto dos números naturais de k bits, convertidos para bit strings.
Ou seja, os elementos de são representações binárias de tamanho fixo k dos valores até .
Por exemplo, para k=1 até k=8 temos os seguintes conjuntos :
Problemas típicos com códigos
Números binários são representações válidas da 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 por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc.
A noção de código natural nos ajuda estudar esses problemas, e valorizar as eventuais soluções.
Definição alternativa
O conjunto dos códigos naturais pode ser também expresso exclusivamente através de números naturais. Podemos usar os pares numéricos tamanho-valor, com o tamanho l variando de zero a k bits, e valores n variando de zero ao máximo permitido pelos k bits:
Os pares descrevem com exatidão e podem ser traduzidos para bitstrings (cadeias de bits). Ilustrando abaixo o uso dos pares (l,n), também designados "size-value pairs".
(size,value) BitString Base4 Base4h hbitBitstring hbit (1,0) 0
? G 10
2 (2,0) 00
0 0 100
4 (3,0) 000
? 0G 1000
8 (4,0) 0000
00 00 10000
16 (5,0) 00000
? 00G 100000
32 (6,0) 000000
000 000 1000000
64 (7,0) 0000000
? 000G 10000000
128 (8,0) 00000000
0000 0000 100000000
256 (8,1) 00000001
0001 0001 100000001
257 (7,1) 0000001
? 000Q 10000001
129 (8,2) 00000010
0002 0002 100000010
258 (8,3) 00000011
0003 0003 100000011
259 (6,1) 000001
001 001 1000001
65 (7,2) 0000010
? 001G 10000010
130 (8,4) 00000100
0010 0010 100000100
260 (8,5) 00000101
0011 0011 100000101
261 ... ... ... ... ... ...
A coluna "hbitBitstring" é relativa à representação das bitstrings em formato "hidden bit", definido em [KraEtAll2019]. Consiste em acrescentar o 1
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 notação posicional numérica da Base 4. A coluna "Base4h" é a inovação proposta em [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.
- 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 Teorema de Cantor. Portanto, matematicamente, size-value é um tradutor mais rigoroso para expressões em .
Inovação tecnológica nas representações
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.
A 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 a 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].
A ilustração abaixo destaca onde falha a base 4 tradicional e como a inovação da base 4h resolve o problema:
- permite representar cadeias de bits (bit strings) de qualquer tamanho;
- permite agrupar hierarquicamente.
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.
Listagens ilustrativas
- Resumodo de Código natural/Listagens com representações
Nas tabelas abaixo são apresentadas amostragens das bitstrings ordenadas de X1, X2 e X8. A coluna count é um contador de linhas para o humano acompanhar em representação decimal a sequência, as colunas b4h e b15h são as representações em base4h e base16h respectivamente.
A coluna hbit é a representação "hidden bit", onde a inclusão à esquerda do dígito 1 na bitstring resulta em um valor decimal maior. Por exemplo as bitstrings 0
, 1
e 00
com o 1 na frente serão 10
, 11
e 100
, que em decimal serão 2, 3 e 4.
- X1: códigos naturais com no máximo 1 bit,
count bitstring hbit b4h b16h 0 1 1 0
2 G G 2 1
3 Q Q
- X2: códigos naturais com no máximo 2 bits,
count bitstring hbit b4h b16h 0 1 1 0
2 G G 2 00
4 0 H 3 01
5 1 M 4 1
3 Q Q 5 10
6 2 R 6 11
7 3 V
- ...
- X8: códigos naturais com no máximo 8 bits,
count bitstring hbit b4h b16h 0 1 1 0
2 G G 2 00
4 0 H 3 000
8 0G J 4 0000
16 00 0 5 00000
32 00G 0G 6 000000
64 000 0H 7 0000000
128 000G 0J 8 00000000
256 0000 00 9 00000001
257 0001 01 10 0000001
129 000Q 0K 11 00000010
258 0002 02 12 00000011
259 0003 03 13 000001
65 001 0M 14 0000010
130 001G 0N 15 00000100
260 0010 04 16 00000101
261 0011 05 17 0000011
131 001Q 0P 18 00000110
262 0012 06 19 00000111
263 0013 07 20 00001
33 00Q 0Q 21 000010
66 002 0R 22 0000100
132 002G 0S 23 00001000
264 0020 08 24 00001001
265 0021 09 25 0000101
133 002Q 0T 26 00001010
266 0022 0a 27 00001011
267 0023 0b 28 000011
67 003 0V 29 0000110
134 003G 0Z 30 00001100
268 0030 0c ... ... ... ... ... 509 11111110
510 3332 fe 510 11111111
511 3333 ff
- 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 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.
Demais fundamentos
Hierarquia como coleção de conjuntos aninhados
Cadeia de bits e notação base2h
Cadeias de bits podem ser representadas por números binários, mas, como exposto acima, devido à eliminação dos zeros à esquerda da representação numérica, uma parte das cadeias de bits não pode ser representada por números.
Para diferenciar 001
de 1
é necessário tomar o cuidado de dizer que a sequência de bits não é um "número na base 2", mas um "código na base 2h", onde "h" é relativo a hierárquico.
Base4h
...
Base8h
...
Base16h
...
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.
A rigor a base mais simples para a representação de geocódigos é a base 4, pois cada célula é subdividida em 4 células-filhas.
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 L0 for quadrada, as células rotuladas por geocódigos da base 4 também serão sempre quadradas.
A base 4 é importante, tem aplicação relevante por ser essencial à representação de geocódigos. Será que outra base N, com N menor ou maior que 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, , é 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:
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.
Portanto N no conjunto {4, 8, 16, 64, …}
O valor de N todavia 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
N≤36
As bases mais compactas portanto ficam restritas a onde o máximo, para máxima compressão, é o 16. A 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 experiência com a tecnologia 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.
Tomando o caso concreto da grade de um país continental como Brasil, que requer 20 níveis para subdividir L0 até chegar no metro. Fica nítido pelo emparelhamento dos bits que apenas três níveis das grades base 32 e hexadecimal serão comuns: L0, L10 e L20. Abaixo a ilustração da interface para seleção de níveis, com todos e com seus filtrados.