Código Natural: mudanças entre as edições
(Bases de interesse prático em Geo) |
|||
| Linha 260: | Linha 260: | ||
|} | |} | ||
:<small>Nota. A coluna ''count'' faz a contagem de ''bitstrings'' ordenadas, | :<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 === | ||
=== Cadeia de bits e notação base2h === | === 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 <code>001</code> de <code>1</code> é 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 ''h''ierárquico. | |||
=== Base4h === | === Base4h === | ||
| Linha 277: | Linha 275: | ||
=== Base8h === | === Base8h === | ||
... | |||
=== Base16h === | === Base16h === | ||
[[arquivo:KraEtAll2019-fig11-ordBases.png|thumb|280px|O alfabeto da base 16h, para representar os primeiros 30 códigos naturais.]] | [[arquivo:KraEtAll2019-fig11-ordBases.png|thumb|280px|O alfabeto da base 16h, para representar os primeiros 30 códigos naturais.]] | ||
... | ... | ||
=== 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. | |||
[[Arquivo:Osmc-refinamentoQuadrada-v2.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. | |||
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, <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> | |||
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 conjunto portanto fica restrito a {8,16} 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 base32 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]] | |||
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 base32 e hexadecimal serão comuns a essas bases: ''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]] | |||
=== Ordenações lexicográfica e numérica === | === Ordenações lexicográfica e numérica === | ||