Código Natural/Representação interna

Códigos naturais podem ser visualizados por humanos e interpretados por máquinas, mas o processamento eficiente (em bancos de dados e algoritmos de manipulação dos códigos) requer uma representação interna no computador igualmente eficiente. Como se trata do conceito geral de código natural, a representação interna pode também ser descrita como "implementação do conceito de código natural". Existem dois modos de se implementar, bem distintos, cabendo ao algoritmo usuário decidir:

1. Implementação direta do código natural como bit string: é o ideal, mas tem ainda suas limitações porque a bit string não é ainda hoje, nas linguagens de programação e bancos de dados, um "cidadão de primeira classe".
   O PostgreSQL oferece varbit e é razoável por ser indexável por btree, mas não faz mais parte do padrão SQL ISO nem tem previsão de evolução no PostgreSQL. Uma variante, também presente em Parquet, é o UUID, mas requer tamanho fixo de 16 bytes.
2. Implementação indireta como número inteiro positivo: foi um grande desafio, mas acreditamos ter conseguido. A sua representação interna fica a cargo dos padrões numéricos mais populares, Int32 (inteiro de 32 bits com sinal - sobram 31 bits sem sinal) e Int64 (inteiro 64 bits = 8 bytes).
   São notorias as implementações H3 Uber e S2 Geometry, por suas células em identificadores int64. A ISO DGGS também parece sugerir IDs de 64 bits.
   No PostgreSQL temos ainda o smallInt (16 bits = 2 bytes); no Parquet (adotado pela Overture) tentou-se INT96 mas foi descontinuado. As variantes Parquet sem sinal também foram descontinuadas.

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.

Ilustrando a travessia pela árvore de 3 bits, na ordem lexicográfica (também dita pre-order).

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

Cadeias de até n bits podem ser copiadas (à esquerda e preenchendo com zeros à direita) em variantes do tipo de dado Inteiro conforme formato hInt, que acrescenta à direita do próprio valor o comprimento da cadeia. Esse formato garante a preservação de hierarquia e a ordenação lexicográfica na ordenação numérica.

Cadeias menores podem ser mixadas como sufixo ou prefixo hierárquico de contadores inteiros, conforme formatos hCount, hCount_prefix ou hCount_switch. Definição dos formatos nas respectivas seções abaixo.

Cada formato tem seu nicho de aplicações:

• hInt e hCount_prefix: indexação espacial e representação interna de GGeohash.
• contadores .. ver Código natural/Identificação taxonômica para "contadores classificados"

NOTA. A ideia da cache-length strategy é inédita, uma inovação tecnológica sugeita a patente. Surgiu do estudo de um score para a comparação lexicográfica de números. Ver discussão original e primeiros resultados de 2019.

hInt

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:	0 como sinal +	n bits para a cópia à esquerda	log2(m) bits para cache do comprimento
hInt16. m=16 bits:	0 (1 bit)	xxxxxxxxxxx (n=11 bits • 69%)	cccc (4 bits)
hInt32. m=32 bits:	0 (1 bit)	xxxxxx...xxxxx (n=26 bits • 81%)	ccccc (5 bits)
hInt64. m=64 bits:	0 (1 bit)	xxxxxx...xxxxx (n=57 bits • 91%)	cccccc (6 bits)

O tamanho do cache vai se tornando desprezível, a fração $m/log_{2}(m)$ diminui de ~30% para 9% conforme m cresce de 16 para 64. Ou seja, a eficiência de ocupação dos "n bits para a cópia" cresce de ~70% para 91%. Com m=128 seriam 94%.

O tipo de dado relativo a essa representação foi apelidado como "hInt" (do inglês "hierarchical Integer"), com as variantes hInt16, hInt32 e hInt64. 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 "hInt16_bin".

{ERRO?  conferir se copia à direita ou à esquerda}
 bitString | hInt16_dec|     hInt16_bin     | 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

Nota. A coluna hInt16_dec é função da coluna bitString, por ex. $dec[hInt16({\texttt {001}})]=4099$; hInt16_bin é função de hInt16, por ex. $bin[hInt16({\texttt {001}})]={\texttt {0001000000000011}}$; value_dec é função do segundo membro de hInt16_bin, por ex. $dec({\texttt {00100000000}})=256$; len_dec é função do terceiro membro de hInt16_bin, por ex. $dec({\texttt {0011}})=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.

Requisitos satisfeitos:

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   |     hInt16_bin     | 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,k)	Sucessor lexicográfico de x com pressuposto de máximo k bits.	Contadores com limite não-default.
succ(x)	Sucessor lexicográfico de x no contexto hInt64.	Mesmo que succ(x,57).
succ(x,p,k)	Sucessor lexicográfico, como contador serial x do prefixo p limitado a k.	Contadores e geradores de identificador serial de prefixo.
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", trocar p+1 por p.

• 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).

• Encontrar todos os pontos de endereço dentro de uma célula p: SELECT y FROM e WHERE y BETWEEN p AND succ(p,p&max_len).

• Encontrar todos os pontos de endereço dentro de uma cobertura (p1, p2, ..., pn): ... WHERE (y BETWEEN p1 AND succ(p1,p1&max_len)) OR (y BETWEEN p2 AND succ(p2,p2&max_len)) OR ...

hCount

Contador numérico usual combinado com prefixo de código natural para informar o path hierárquico. Variação que combina hInt com Int, aumentando o número de bits no contador e simplificando as operações com identificador serial. É a representação mais adequada às aplicações taxonômicas, que requerem uma estrutura compacta e funcional de classe-contador.

{revisar se mais um bit: questão de valores zero a x onde x ainda é potencia de 2}

Definição:	sinal	n bits para a cópia à esquerda	Contador
hCount16_48. m=64; p=16:	0	ppppppppppp cccc (11+4 bits)	xxxxxxxx...xxxxxxx (16+32=48 bits)
hCount32_32. m=64; p=26:	0	pppppp...pppppp ccccc (26+5 bits)	xxxxxx...xxxxx (32 bits)
?hCount56_8. m=64; p=26:	0	pppppp...pppppp ccc (40+3 bits)	xxxxxxxx (8 bits)

O tipo hCount16_48 é mais adequado às classes curtas, ou seja, com baixa diversidade e/ou pequeno número de níveis hierárquicos nas classes, ou, principalmente, quando algum dos contadores de classe não cabe em 32 bits. O tipo hCount32_32 é mais adequado quando há garantia de contadores limitados a 32 bits, ou a diversidade de classe é maior (requerendo também 32 bits).

A ordenação lexicográfica continua válida para a verificação de itens dentro de uma classe, e as demais operações continuam similares:

Função ou operação sobre x	Descrição	Aplicação
x & pmask16_48	Máscara do cache-length do prefixo. Retorna o comprimento da bitstring de classificação	permite ordenação por nível.
x & cmask16_48	Máscara do contador (bits menos significativos). Retorna o contador como inteiro	permite ordenação numérica dentro da classe, para verificação max(count_val) quando o serial não é controlado.
...	...	...
hCount16_48_succ(x)	Sucessor lexicográfico do prefixo de x.	...
hCount16_48_next(x)	Sucessor numérico (+1) do sufixo contador de x.	...
prefix_to_max(x)	Valor hInt que corresponde ao máximo valor de um "filho" do prefixo de x.	Resgatar elementos com prefixo de x, ou seja, um ramo inteiro da sua árvore.
...	...	...

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 hcount, com mínimo e máximo valores dentro da classe, ou seja, resultado do empacotamento de classe e contador através da função vBit_to_hCount16c48(bitstring,0) na coluna hcount0 e vBit_to_hCount16c48(bitstring,281474976710655) na coluna hcount_max.

 bitString_asClass |    hCount0_dec      |   hCount_max_dec      
-------------------+---------------------+---------------------
 0                 |     281474976710656 |     562949953421311
 00                |     562949953421312 |     844424930131967
 000               |     844424930131968 |    1125899906842623
 001               | 1153765929536978944 | 1154047404513689599
 01                | 2306405959167115264 | 2306687434143825919
 010               | 2306687434143825920 | 2306968909120536575
 011               | 3459608938750672896 | 3459890413727383551
 1                 | 4611967493404098560 | 4612248968380809215
 10                | 4612248968380809216 | 4612530443357519871
 100               | 4612530443357519872 | 4612811918334230527
 101               | 5765451947964366848 | 5765733422941077503
 11                | 6918091977594503168 | 6918373452571213823
 110               | 6918373452571213824 | 6918654927547924479
 111               | 8071294957178060800 | 8071576432154771455

Reparar que a ordem numérica entre máximo e mínimo é preservada e a ordem lexixográfica das classes também. Abaixo uma amostragem de vBit_to_hCount16c48(bitstring,123), destacando os blocos de bits.

 bitstring |     hcount_dec      |                             hcount_bin                              
-----------+---------------------+---------------------------------------------------------------------
 0         |     281474976710779 | 0 00000000000 0001 000000000000000000000000000000000000000001111011
 00        |     562949953421435 | 0 00000000000 0010 000000000000000000000000000000000000000001111011
 000       |     844424930132091 | 0 00000000000 0011 000000000000000000000000000000000000000001111011
 001       | 1153765929536979067 | 0 00100000000 0011 000000000000000000000000000000000000000001111011
 01        | 2306405959167115387 | 0 01000000000 0010 000000000000000000000000000000000000000001111011
 ...
 111       | 8071294957178060923 | 0 11100000000 0011 000000000000000000000000000000000000000001111011

A estrutura também permite a expressão das duas partes do código em destaque, e legíveis ao humano (apesar de não mais ordenável). A função hCount16c48_to_text() renderiza o identificador hc de forma mais legível ao humano, por exemplo para contadores pequenos pode-se usar base4h e decimal:

 h_bin  |c_dec|       hc_dec        | hc_human 
--------+-----+---------------------+---------
 0      | 123 |     281474976710779 | G-123
 0      | 223 |     281474976710879 | G-223
 000    | 123 |     844424930132091 | 0G-123
 000    | 204 |     844424930132172 | 0G-204
 000    | 208 |     844424930132176 | 0G-208
 001    | 123 | 1153765929536979067 | 0Q-123
 01     | 123 | 2306405959167115387 | 1-123
 010    | 123 | 2306687434143826043 | 1G-123
 010    | 182 | 2306687434143826102 | 1G-182
 1      |  20 | 4611967493404098580 | Q-20
 10     | 123 | 4612248968380809339 | 2-123
 10     | 138 | 4612248968380809354 | 2-138
 10     | 152 | 4612248968380809368 | 2-152
 11     |  66 | 6918091977594503234 | 3-66
 

Para contadores grandes pode ser mais conveniente a sua renderização por hexadecimal:

h_bin   |   c_dec   |       hc_dec        |  hc_human   
--------+-----------+---------------------+-------------
 0      |       123 |     281474976710779 | G-7b
 0      | 128668188 |     281475105378844 | G-7ab521c
 0      | 411903978 |     281475388614634 | G-188d27ea
 00     | 128668188 |     562950082089500 | 0-7ab521c
 00     | 417543142 |     562950370964454 | 0-18e333e6
 000    | 128668188 |     844425058800156 | 0G-7ab521c
 000    | 496198312 |     844425426330280 | 0G-1d9362a8
 001    | 128668188 | 1153765929665647132 | 0Q-7ab521c
 001    | 240966205 | 1153765929777945149 | 0Q-e5cda3d
 01     | 128668188 | 2306405959295783452 | 1-7ab521c
 ...
 0010101101  |       123 | 1561060220837298299 | 02231-7b
 0010101101  |  30931294 | 1561060220868229470 | 02231-1d7f95e
 0010101101  |  81288382 | 1561060220918586558 | 02231-4d85cbe
 00101011010 |       123 | 1561341695814008955 | 02231G-7b
 11010001    |       123 | 7532270376777154683 | 3101-7b
 11010001    |  30931294 | 7532270376808085854 | 3101-1d7f95e
 11010001    | 197513090 | 7532270376974667650 | 3101-bc5cf82
 1101000101  |       123 | 7541840525985316987 | 31011-7b
 1101000101  |  30931294 | 7541840526016248158 | 31011-1d7f95e
 1101000101  | 400011400 | 7541840526385328264 | 31011-17d7b088
 

hCount_prefix

Quando o contador é necessário como prefixo, ao invés do classificador. As células do padrão DGGS, tipicamente fazem uso de um "seletor de face" que a rigor é um contador com valor arbitrário, em geral valor pequeno, relativo ao número de faces do poliedro (4 a 120). Eventualmente, no Map Code Base4, um GGeohash de 4*9999 faces, é requerida contagem maior. Estrutura:

Definição:	sinal	n bits para a cópia à esquerda	Contador
?hCount_prf8_56. m=64; p=8:	0	pppppp...pppppp ccc (40+3 bits)	xxxxxxxx (8 bits)
hCount_prf16_48. m=64; p=16:	0	ppppppppppp cccc (11+4 bits)	xxxxxxxx...xxxxxxx (16+32=48 bits)
hCount_prf32_32. m=64; p=26:	0	pppppp...pppppp ccccc (26+5 bits)	xxxxxx...xxxxx (32 bits)

c=cache; f é prefixo de contagem de faces.

hCount_switch

Através desta opção o contador para ser chaveado, ou seja, conforme bits de controle pode-se decidir entre hierarquia ou contagem. A estrutura tem como inspiração a implementação GGeohash com "face oculta"

Mesmo que uma hierarquia pura com contador de faces f , porém elege-se um valor para dizer "os demais bits são contadores".

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 ...