Código Natural/Representação interna: mudanças entre as edições
| Linha 61: | Linha 61: | ||
===Exemplo mais completo=== | ===Exemplo mais completo=== | ||
Para codificar | Para codificar hInt16 em um inteiro de 16 bits são consumidos 1 bit com o sinal (sempre positivo) e 4 bits com o cache de comprimento, restando 11 bits para a representação efetiva do código. | ||
<pre> | <pre> | ||
Edição das 20h00min de 7 de agosto de 2023
Apesar de existirem diversas estratégias de implementação, cada qual com suas vantagens e desvantagens, foi eleita uma como "nativa" dos Códigos Naturais, a Cache-length strategy. Ela satisfaz todos os requisitos e apresenta boa performance.
O requisito mais difícil de se obter na representação interna com inteiros, é a ordem lexicográfica. Por identificar unicamente os elementos de conjuntos de aninhados, precisa garantir que os ramos da hierarquia dos conjuntos possam ser recuperados dentro um único intervalo, tal como na modelagem SQL por conjuntos aninhados.
Cache-length strategy
Qualquer cadeia de até n bits pode ser copiado dentro de um inteiro de m bits (cópia à esquerda preenchendo com zeros à direita) com a seguinte estrutura:
Definição: 1 bit, 0, para o sinaln bits para a cópia à esquerda log2(m) bits para cache do comprimento m=16 bits: 0xxxxxxxxxxx(n=11 bits)cccc(4 bits)m=32 bits: 0xxxxxx...xxxxx(n=26 bits)ccccc(5 bits)m=64 bits: 0xxxxxx...xxxxx(n=57 bits)cccccc(6 bits)
O tipo de dado relativo a essa representação foi apelidado como "hInt" (do inglês "hierarchical Integer"), com as variantes acima apelidadas hInt16, hInt32 e hInt64 respectivamente. O valor inteiro hInt além de preservar a integridade da cadeia de bits original no seu interior, preserva a ordem lexicográfica.
Abaixo um exemplo com o conjunto completo de todas as cadeias de até 3 bits (coluna bitString), e a representação de cada uma delas como hInt16 — seu valor em representação decimal na coluna "hInt16_dec" e sua representação interna dentro do inteiro de 16 bits na coluna "internal_16bits".
bitstring | hInt16_dec| internal_16bits | value_dec | len_dec -----------+-----------+--------------------+-----------+--------- 0 | 1 | 0 00000000000 0001 | 0 | 1 00 | 2 | 0 00000000000 0010 | 0 | 2 000 | 3 | 0 00000000000 0011 | 0 | 3 001 | 4099 | 0 00100000000 0011 | 256 | 3 01 | 8194 | 0 01000000000 0010 | 512 | 2 010 | 8195 | 0 01000000000 0011 | 512 | 3 011 | 12291 | 0 01100000000 0011 | 768 | 3 1 | 16385 | 0 10000000000 0001 | 1024 | 1 10 | 16386 | 0 10000000000 0010 | 1024 | 2 100 | 16387 | 0 10000000000 0011 | 1024 | 3 101 | 20483 | 0 10100000000 0011 | 1280 | 3 11 | 24578 | 0 11000000000 0010 | 1536 | 2 110 | 24579 | 0 11000000000 0011 | 1536 | 3 111 | 28675 | 0 11100000000 0011 | 1792 | 3
A coluna "len_dec" fornece o valor decimal dos 4 bits de cache-length (facilmente extraído pela operação bitwise hInt16 & 15), e a coluna "value_dec" o valor decimal dos 11 bits centrais (extraído por hInt16>>4).
A preservação da ordem lexicográfica é conseguida devido à "cópia à esquerda", como podemos notar pela coluna "value_dec". Em seguida a coluna "len_dec" mostra que o cache-length faz também o papel de ajuste fino, nas linhas onde os valores "value_dec" se repetem (ver 0, 512 e 1024).
A ordem garante que cada ramo da hierarquia esteja contido dentro de um único intervalo hInt. Por exemplo 00 e seus "filhos" (000 e 001), estão entre os valores hInt 2 e 4099. Analogamente todos os "filhos de 1" estão entre os valores hInt 16385 e 28675.
- Requisito R1.1: sim, o hInt pode ser "enbutido" em inteiros de qualquer comprimento, e preserva a integridade da bitstring dentro do inteiro. A performance de encode/decode para bitstrings também é alta, justamente pelo uso do cache de comprimento.
- Requisito R1.2: sim, existe a função succ(hInt), podendo ser aplicada a identificadores ou prefixos.
- Requisito R1.3: sim, permite a ordenação lexicográfica com alta performance, e ordenação por nível com acréscimo de apenas uma operação.
- Requisito R1.4: sim, é escalável. Novos sucessores podem ser acrescentados por simples concatenação aos IDs originais.
Exemplificando R1.4. Um código originalmente em hInt16, p. ex. 0100.0001100 tem como prefixo 0100 e seu último sucessor é 0100.1111111, quando copiado em hInt32 continua sendo o mesmo código, e o sucessor do seu último, 0100.11111110, passa a existir, assim como 0100.111111100 e demais milhares de sucessores dentro do mesmo prefixo.
PS: a eleição de novos IDs não pode usar apenas a função succ(ID), deve-se "saltar" os IDs antigos, que estarão intercalados.
Exemplo mais completo
Para codificar hInt16 em um inteiro de 16 bits são consumidos 1 bit com o sinal (sempre positivo) e 4 bits com o cache de comprimento, restando 11 bits para a representação efetiva do código.
bitstring | hInt16 | internal_16bits | value_dec | len_dec -------------+----------+--------------------+-----------+--------- 0 | 1 | 0 00000000000 0001 | 0 | 1 00 | 2 | 0 00000000000 0010 | 0 | 2 000 | 3 | 0 00000000000 0011 | 0 | 3 0000 | 4 | 0 00000000000 0100 | 0 | 4 00000 | 5 | 0 00000000000 0101 | 0 | 5 000000 | 6 | 0 00000000000 0110 | 0 | 6 0000000 | 7 | 0 00000000000 0111 | 0 | 7 00000000 | 8 | 0 00000000000 1000 | 0 | 8 000000000 | 9 | 0 00000000000 1001 | 0 | 9 0000000000 | 10 | 0 00000000000 1010 | 0 | 10 00000000000 | 11 | 0 00000000000 1011 | 0 | 11 00000000001 | 27 | 0 00000000001 1011 | 1 | 11 0000000001 | 42 | 0 00000000010 1010 | 2 | 10 00000000010 | 43 | 0 00000000010 1011 | 2 | 11 00000000011 | 59 | 0 00000000011 1011 | 3 | 11 000000001 | 73 | 0 00000000100 1001 | 4 | 9 0000000010 | 74 | 0 00000000100 1010 | 4 | 10 00000000100 | 75 | 0 00000000100 1011 | 4 | 11 00000000101 | 91 | 0 00000000101 1011 | 5 | 11 0000000011 | 106 | 0 00000000110 1010 | 6 | 10 00000000110 | 107 | 0 00000000110 1011 | 6 | 11 00000000111 | 123 | 0 00000000111 1011 | 7 | 11 00000001 | 136 | 0 00000001000 1000 | 8 | 8 000000010 | 137 | 0 00000001000 1001 | 8 | 9 0000000100 | 138 | 0 00000001000 1010 | 8 | 10 00000001000 | 139 | 0 00000001000 1011 | 8 | 11 00000001001 | 155 | 0 00000001001 1011 | 9 | 11 0000000101 | 170 | 0 00000001010 1010 | 10 | 10 00000001010 | 171 | 0 00000001010 1011 | 10 | 11 00000001011 | 187 | 0 00000001011 1011 | 11 | 11 000000011 | 201 | 0 00000001100 1001 | 12 | 9 0000000110 | 202 | 0 00000001100 1010 | 12 | 10 00000001100 | 203 | 0 00000001100 1011 | 12 | 11 00000001101 | 219 | 0 00000001101 1011 | 13 | 11 0000000111 | 234 | 0 00000001110 1010 | 14 | 10 00000001110 | 235 | 0 00000001110 1011 | 14 | 11 00000001111 | 251 | 0 00000001111 1011 | 15 | 11 0000001 | 263 | 0 00000010000 0111 | 16 | 7 00000010 | 264 | 0 00000010000 1000 | 16 | 8 000000100 | 265 | 0 00000010000 1001 | 16 | 9 ... 111111011 | 32457 | 0 11111101100 1001 | 2028 | 9 1111110110 | 32458 | 0 11111101100 1010 | 2028 | 10 11111101100 | 32459 | 0 11111101100 1011 | 2028 | 11 11111101101 | 32475 | 0 11111101101 1011 | 2029 | 11 1111110111 | 32490 | 0 11111101110 1010 | 2030 | 10 11111101110 | 32491 | 0 11111101110 1011 | 2030 | 11 11111101111 | 32507 | 0 11111101111 1011 | 2031 | 11 1111111 | 32519 | 0 11111110000 0111 | 2032 | 7 11111110 | 32520 | 0 11111110000 1000 | 2032 | 8 111111100 | 32521 | 0 11111110000 1001 | 2032 | 9 1111111000 | 32522 | 0 11111110000 1010 | 2032 | 10 11111110000 | 32523 | 0 11111110000 1011 | 2032 | 11 11111110001 | 32539 | 0 11111110001 1011 | 2033 | 11 1111111001 | 32554 | 0 11111110010 1010 | 2034 | 10 11111110010 | 32555 | 0 11111110010 1011 | 2034 | 11 11111110011 | 32571 | 0 11111110011 1011 | 2035 | 11 111111101 | 32585 | 0 11111110100 1001 | 2036 | 9 1111111010 | 32586 | 0 11111110100 1010 | 2036 | 10 11111110100 | 32587 | 0 11111110100 1011 | 2036 | 11 11111110101 | 32603 | 0 11111110101 1011 | 2037 | 11 1111111011 | 32618 | 0 11111110110 1010 | 2038 | 10 11111110110 | 32619 | 0 11111110110 1011 | 2038 | 11 11111110111 | 32635 | 0 11111110111 1011 | 2039 | 11 11111111 | 32648 | 0 11111111000 1000 | 2040 | 8 111111110 | 32649 | 0 11111111000 1001 | 2040 | 9 1111111100 | 32650 | 0 11111111000 1010 | 2040 | 10 11111111000 | 32651 | 0 11111111000 1011 | 2040 | 11 11111111001 | 32667 | 0 11111111001 1011 | 2041 | 11 1111111101 | 32682 | 0 11111111010 1010 | 2042 | 10 11111111010 | 32683 | 0 11111111010 1011 | 2042 | 11 11111111011 | 32699 | 0 11111111011 1011 | 2043 | 11 111111111 | 32713 | 0 11111111100 1001 | 2044 | 9 1111111110 | 32714 | 0 11111111100 1010 | 2044 | 10 11111111100 | 32715 | 0 11111111100 1011 | 2044 | 11 11111111101 | 32731 | 0 11111111101 1011 | 2045 | 11 1111111111 | 32746 | 0 11111111110 1010 | 2046 | 10 11111111110 | 32747 | 0 11111111110 1011 | 2046 | 11 11111111111 | 32763 | 0 11111111111 1011 | 2047 | 11
Operações essenciais
O tipo de dado hInt vem munido de um conjunto de operações com aplicações relevantes:
Função ou operação sobre x Descrição Aplicação x & max_len Máscara do cache-length. Retorna o comprimento da bitstring ordenação por nível, recorte da bitstring, etc. succ(x) Sucessor, como gerador serial de identificadores. Contadores e geradores de identificador serial. p=prefix(x,k) Prefixo p de k bits. ... p=prefix(x,y) Prefixo comum de x e y. ... prefix_to_max(p) Valor hInt que corresponde ao máximo valor de um "filho" de p. Resgatar elementos com prefixo p, ou seja, um ramo inteiro da árvore. ... ... ...
Operações de busca e ordenação: ref,
- Ordenar lexicograficamente: direto
SELECT x FROM t ORDER BY x.
- Ordenar por level-order:
SELECT x FROM t ORDER BY x&63, x.
- Encontrar todos os descendentes de um nó p da árvore:
SELECT x FROM t WHERE x BETWEEN p+1 AND prefix_to_max(p).
No caso de "inclusive p", trocarp+1porp.
- Encontrar todos os ancestrais de um nó p da árvore, ou seja, os seus prefixos:
SELECT x FROM t WHERE x BETWEEN prefix(p,1) AND p-1.
- Encontrar todos os descendentes de um nó p a partir de uma certa profundidade k:
SELECT x FROM t WHERE x &63>k AND x BETWEEN p+1 AND prefix_to_max(p).
Hidden-bit strategy
Simplesmente "protege os zeros a esquerda" acescentando-se o bit 1 à esquerda, no encode da bitstring, e removendo-se no decode da bitstring. É dito "hidden bit" porque justamente o bit 1 fica "escondido" do usuário.
...
Outras estratégias
Citar a estratégia do S2 Geometry ...