2 583
edições
m (→Algoritmos) |
(→Inovação tecnológica nas representações: add link and review content) |
||
Linha 141: | Linha 141: | ||
== Inovação tecnológica nas representações == | == Inovação tecnológica nas representações == | ||
[[Arquivo:Zcutve-base4.png.png|miniaturadaimagem|A sequência de células 1 a 16 pode ser rotulada pela '''base | [[Arquivo:Zcutve-base4.png.png|miniaturadaimagem|A sequência de células 1 a 16 pode ser rotulada pela '''base 4h''' com 2 dígitos. Ao contrário da base 4 numérica, que remove zeros a esquerda, a base 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'''.]] | |||
[[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>.]] | |||
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 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 [[wikipedia:Quaternary numeral system|'''base 4''']] (ou "sistema de numeração quaternário") é | A [[wikipedia:Quaternary numeral system|'''base 4''']] (ou "sistema de numeração quaternário") é simples e representa números de maneira mais compacta que a representação binária. Usa somente os dígitos 0 a 3. A sequência numérica de 0 a 6 por exemplo, em 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>. | ||
Abaixo é ilustrado o uso clássico da base 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 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 159: | Linha 160: | ||
[[Arquivo:KraEtAll2019-fig05-orders.png|480px|center]] | [[Arquivo:KraEtAll2019-fig05-orders.png|480px|center]] | ||
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>. | |||
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. | |||
== Listagens ilustrativas == | == Listagens ilustrativas == |
edições